Inkrementaaliset Toteutukset

Jokaisen tuoton tallentaminen jokaista tila-toimintoparia kohden voi nopeasti kuluttaa muistin loppuun ja merkittävästi lisätä laskenta-aikaa — erityisesti suurissa ympäristöissä. Tämä rajoitus koskee sekä on-policy- että off-policy-Monte Carlo -ohjausalgoritmeja. Tämän ratkaisemiseksi käytetään inkrementaalisia laskentamenetelmiä, jotka ovat samankaltaisia kuin multi-armed bandit -algoritmeissa käytetyt menetelmät. Näiden menetelmien avulla arviot voidaan päivittää välittömästi, ilman että koko tuottohistoriaa tarvitsee säilyttää.

On-policy Monte Carlo -ohjaus

On-policy-menetelmässä päivitysstrategia muistuttaa MAB-algoritmeissa käytettyä strategiaa:

missä $\displaystyle \alpha = \frac{1}{N(s, a)}$ keskiarvon estimaattia varten. Ainoat tallennettavat arvot ovat nykyiset toimintojen arviot $Q(s, a)$ sekä tila-toimintaparin $(s, a)$ käyntikertojen määrä $N(s, a)$.

Pseudokoodi

Off-policy Monte Carlo -ohjaus

Off-policy-menetelmässä tavallisella tärkeyspainotuksella kaikki on samanlaista kuin on-policy-menetelmässä.

Mielenkiintoisempi tilanne syntyy painotetulla tärkeyspainotuksella. Yhtälö näyttää samalta:

mutta $\displaystyle \alpha = \frac{1}{N(s, a)}$ ei voida käyttää, koska:

1. Jokainen tuotto painotetaan $\rho$:lla;
2. Lopullinen summa jaetaan ei $N(s, a)$:lla, vaan $\sum \rho(s, a)$:lla.

Tässä tapauksessa käytettävä $\alpha$ on yhtä suuri kuin $\displaystyle \frac{W}{C(s,a)}$, missä:

• $W$ on nykyisen trajektorian $\rho$;
• $C(s, a)$ on yhtä kuin $\sum \rho(s, a)$.

Ja joka kerta kun tila-toimintapari $(s, a)$ esiintyy, nykyisen trajektorian $\rho$ lisätään $C(s, a)$:aan:

Pseudokoodi