La oss starte med å se på et kjent konsept: tilstandsverdifunksjonen, betegnet som $v_\pi(s)$. Den kan defineres som

Målet i dette kapittelet er å anslå denne funksjonen ut fra data, gitt at vi har en fast politikk $\pi$, men ikke har tilgang til miljøets modell.

Monte Carlo-estimering

Monte Carlo-metoder tilnærmer denne estimeringsoppgaven ved å samle episoder av erfaring under politikken $\pi$, og deretter bruke disse prøvene til å danne empiriske estimater av $v_\pi(s)$.

Generelt kan prosessen deles inn i følgende trinn:

1. Generer en episode ved å bruke politikk $\pi$;
2. Lagre den oppnådde returverdien for hver tilstand som opptrer i episoden;
3. Gjenta trinn 1-2 over tid;
4. Beregn de nye verdiene ved å ta gjennomsnittet av returene for hver tilstand.

Innhenting av avkastning

Monte Carlo-estimering av verdifunksjonen krever innhenting av avkastning fra genererte episoder. For å beregne disse avkastningene kan to hovedmetoder benyttes:

• Første-besøk: for hver tilstand $s$ som oppstår i en episode, tas kun avkastningen etter første forekomst med i betraktningen. Senere forekomster av samme tilstand i samme episode ignoreres for estimeringsformål;
• Alle-besøk: hver forekomst av en tilstand $s$ i en episode benyttes. Det vil si at avkastningen etter hvert besøk til tilstanden inkluderes i estimatet, selv om tilstanden opptrer flere ganger i samme episode.

Utforskende starttilstander

Tenk deg en enkel endimensjonal verden representert av en linje som strekker seg fra -10 til +10. Agenten starter på posisjon 0, og dens nåværende policy tilsier at den alltid beveger seg til høyre ved hvert tidsskritt.

Hvis vi forsøker å generere episoder under denne policyen, hva skjer? Agenten vil kontinuerlig bevege seg mot den positive enden av linjen — besøke tilstander som 1, 2, 3, og så videre — men den vil aldri besøke noen negative tilstander. Som et resultat kan vi ikke estimere verdifunksjoner for tilstander til venstre for origo, rett og slett fordi agenten aldri opplever dem.

Hovedproblemet er altså: hvis visse deler av tilstandsrommet aldri utforskes, vil deres verdiestimat forbli unøyaktige eller udefinerte. En vanlig løsning på dette problemet er bruk av exploring starts.

Med exploring starts begynner hver episode ikke i en fast starttilstand som 0, men i en tilfeldig valgt tilstand. Når episoden starter, følger agenten sin nåværende policy som vanlig. Over tid, ved å starte fra mange forskjellige punkter i tilstandsrommet, får agenten besøkt alle tilstander — ikke bare de policyen naturlig ville ført den til. Dette gjør at Monte Carlo-metoden kan gi mer nøyaktige og komplette verdiestimat for hele tilstandsrommet.

Pseudokode

Denne pseudokoden bruker every-visit-tilnærmingen sammen med exploring starts.