Å lagre hver avkastning for hvert tilstand-handlingspar kan raskt tømme minnet og betydelig øke beregningstiden — spesielt i store miljøer. Denne begrensningen påvirker både on-policy og off-policy Monte Carlo-kontrollalgoritmer. For å håndtere dette, benytter vi inkrementelle beregningsstrategier, lik de som brukes i multi-armede bandittalgoritmer. Disse metodene gjør det mulig å oppdatere verdiestimatene fortløpende, uten å måtte lagre hele historikken av avkastninger.

On-policy Monte Carlo-kontroll

For on-policy-metoden ligner oppdateringsstrategien på strategien som brukes i MAB-algoritmer:

hvor $\displaystyle \alpha = \frac{1}{N(s, a)}$ for middelverdiestimat. De eneste verdiene som må lagres er de nåværende estimatene for handlingsverdiene $Q(s, a)$ og antall ganger tilstand-handlingsparet $(s, a)$ har blitt besøkt $N(s, a)$.

Pseudokode

Off-policy Monte Carlo-kontroll

For off-policy-metoden med ordinær importance sampling er alt det samme som for on-policy-metoden.

En mer interessant situasjon oppstår med vektet importance sampling. Ligningen ser lik ut:

men $\displaystyle \alpha = \frac{1}{N(s, a)}$ kan ikke brukes fordi:

1. Hver retur vektes med $\rho$;
2. Den endelige summen deles ikke på $N(s, a)$, men på $\sum \rho(s, a)$.

Verdien av $\alpha$ som faktisk kan brukes i dette tilfellet er lik $\displaystyle \frac{W}{C(s,a)}$ hvor:

• $W$ er en $\rho$ for nåværende trajektorie;
• $C(s, a)$ er lik $\sum \rho(s, a)$.

Og hver gang tilstands-handlingsparet $(s, a)$ oppstår, legges $\rho$ for nåværende trajektorie til $C(s, a)$:

Pseudokode