Inkrementella Implementationer

Att lagra varje avkastning för varje tillstånd-handlingspar kan snabbt förbruka minne och avsevärt öka beräkningstiden — särskilt i stora miljöer. Denna begränsning påverkar både on-policy och off-policy Monte Carlo-kontrollalgoritmer. För att hantera detta använder vi inkrementella beräkningsstrategier, liknande de som används i multi-armed bandit-algoritmer. Dessa metoder möjliggör att värdeuppskattningar uppdateras direkt, utan att hela avkastningshistoriken behöver sparas.

On-policy Monte Carlo-kontroll

För on-policy-metoden ser uppdateringsstrategin likadan ut som strategin som används i MAB-algoritmer:

där $\displaystyle \alpha = \frac{1}{N(s, a)}$ för medelvärdesuppskattning. De enda värden som behöver lagras är de aktuella uppskattningarna av handlingsvärden $Q(s, a)$ och antalet gånger tillstånd-handlingsparet $(s, a)$ har besökts $N(s, a)$.

Pseudokod

Off-policy Monte Carlo-kontroll

För off-policy-metoden med ordinär importance sampling är allt detsamma som för on-policy-metoden.

En mer intressant situation uppstår med viktad importance sampling. Ekvationen ser likadan ut:

men $\displaystyle \alpha = \frac{1}{N(s, a)}$ kan inte användas eftersom:

1. Varje retur viktas med $\rho$;
2. Den slutliga summan delas inte med $N(s, a)$, utan med $\sum \rho(s, a)$.

Värdet på $\alpha$ som faktiskt kan användas i detta fall är lika med $\displaystyle \frac{W}{C(s,a)}$ där:

• $W$ är $\rho$ för aktuell trajektoria;
• $C(s, a)$ är lika med $\sum \rho(s, a)$.

Och varje gång tillstånd-aktionsparet $(s, a)$ uppstår, adderas $\rho$ för aktuell trajektoria till $C(s, a)$:

Pseudokod