Memorizzare ogni ritorno per ciascuna coppia stato-azione può rapidamente esaurire la memoria e aumentare significativamente il tempo di calcolo — soprattutto in ambienti di grandi dimensioni. Questa limitazione interessa sia gli algoritmi di controllo Monte Carlo on-policy che off-policy. Per affrontare questo problema, si adottano strategie di calcolo incrementale, simili a quelle utilizzate negli algoritmi multi-armed bandit. Questi metodi permettono di aggiornare le stime dei valori in tempo reale, senza conservare l'intera cronologia dei ritorni.

Controllo Monte Carlo On-Policy

Per il metodo on-policy, la strategia di aggiornamento è simile a quella utilizzata negli algoritmi MAB:

dove $\displaystyle \alpha = \frac{1}{N(s, a)}$ per la stima della media. Gli unici valori che devono essere memorizzati sono le stime correnti dei valori d'azione $Q(s, a)$ e il numero di volte in cui la coppia stato-azione $(s, a)$ è stata visitata $N(s, a)$.

Pseudocodice

Controllo Monte Carlo Off-Policy

Per il metodo off-policy con campionamento di importanza ordinario tutto è uguale al metodo on-policy.

Una situazione più interessante si verifica con il campionamento di importanza pesato. L'equazione appare la stessa:

ma $\displaystyle \alpha = \frac{1}{N(s, a)}$ non può essere utilizzato perché:

1. Ogni ritorno è pesato da $\rho$;
2. La somma finale non è divisa per $N(s, a)$, ma per $\sum \rho(s, a)$.

Il valore di $\alpha$ che può effettivamente essere utilizzato in questo caso è pari a $\displaystyle \frac{W}{C(s,a)}$ dove:

• $W$ è il $\rho$ per la traiettoria corrente;
• $C(s, a)$ è pari a $\sum \rho(s, a)$.

E ogni volta che la coppia stato-azione $(s, a)$ si verifica, il $\rho$ della traiettoria corrente viene aggiunto a $C(s, a)$:

Pseudocodice