Incrementele Implementaties

Het opslaan van elke opbrengst voor elk toestand-actie-paar kan snel het geheugen uitputten en de rekentijd aanzienlijk verhogen — vooral in grote omgevingen. Deze beperking beïnvloedt zowel on-policy als off-policy Monte Carlo-controle-algoritmen. Om dit aan te pakken, gebruiken we incrementele berekeningsstrategieën, vergelijkbaar met die in multi-armed bandit-algoritmen. Deze methoden maken het mogelijk om waarde-inschattingen direct bij te werken, zonder volledige opbrengstgeschiedenissen te bewaren.

On-Policy Monte Carlo-controle

Voor de on-policy methode lijkt de bijwerkstrategie op de strategie die wordt gebruikt in MAB-algoritmen:

waarbij $\displaystyle \alpha = \frac{1}{N(s, a)}$ voor de gemiddelde schatting. De enige waarden die moeten worden opgeslagen zijn de huidige schattingen van de actiewaarden $Q(s, a)$ en het aantal keren dat het toestand-actie-paar $(s, a)$ is bezocht $N(s, a)$.

Pseudocode

Off-Policy Monte Carlo-controle

Voor de off-policy methode met gewone importance sampling is alles hetzelfde als bij de on-policy methode.

Een interessantere situatie ontstaat bij gewogen importance sampling. De vergelijking ziet er hetzelfde uit:

maar $\displaystyle \alpha = \frac{1}{N(s, a)}$ kan niet worden gebruikt omdat:

1. Elke opbrengst wordt gewogen met $\rho$;
2. De uiteindelijke som wordt niet gedeeld door $N(s, a)$, maar door $\sum \rho(s, a)$.

De waarde van $\alpha$ die in dit geval daadwerkelijk kan worden gebruikt is gelijk aan $\displaystyle \frac{W}{C(s,a)}$ waarbij:

• $W$ een $\rho$ is voor de huidige traject;
• $C(s, a)$ gelijk is aan $\sum \rho(s, a)$.

En elke keer dat het toestand-actie-paar $(s, a)$ voorkomt, wordt de $\rho$ van de huidige traject toegevoegd aan $C(s, a)$:

Pseudocode