Inkrementelle Implementeringer

Opbevaring af hver eneste return for hvert state-action-par kan hurtigt udtømme hukommelsen og markant øge beregningstiden — især i store miljøer. Denne begrænsning påvirker både on-policy og off-policy Monte Carlo kontrolalgoritmer. For at imødekomme dette anvendes inkrementelle beregningsstrategier, svarende til dem der bruges i multi-armed bandit-algoritmer. Disse metoder muliggør, at værdiskøn kan opdateres løbende, uden at hele return-historikken skal gemmes.

On-Policy Monte Carlo-kontrol

For on-policy-metoden ligner opdateringsstrategien den strategi, der anvendes i MAB-algoritmer:

hvor $\displaystyle \alpha = \frac{1}{N(s, a)}$ for middelværdiestimat. De eneste værdier, der skal gemmes, er de aktuelle estimater af action-værdierne $Q(s, a)$ og antallet af gange state-action-parret $(s, a)$ er blevet besøgt $N(s, a)$.

Pseudokode

Off-policy Monte Carlo-kontrol

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

En mere interessant situation opstår med vægtet importance sampling. Ligningen ser ud på samme måde:

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

1. Hver returnering vægtes med $\rho$;
2. Den endelige sum divideres ikke med $N(s, a)$, men med $\sum \rho(s, a)$.

Værdien af $\alpha$, der faktisk kan bruges i dette tilfælde, er lig med $\displaystyle \frac{W}{C(s,a)}$ hvor:

• $W$ er en $\rho$ for den aktuelle sekvens;
• $C(s, a)$ er lig med $\sum \rho(s, a)$.

Og hver gang state-action-parret $(s, a)$ optræder, lægges $\rho$ for den aktuelle sekvens til $C(s, a)$:

Pseudokode