Lad os begynde med at genbesøge et velkendt begreb: tilstandsværdifunktionen, betegnet som $v_\pi(s)$. Den kan defineres som

Målet i dette kapitel er at estimere denne funktion ud fra data, under antagelse af at vi har en fast politik $\pi$, men ingen adgang til miljøets model.

Monte Carlo-estimering

Monte Carlo-metoder nærmer sig denne estimeringsopgave ved at udtage episoder af erfaring under politikken $\pi$ og derefter bruge disse prøver til at danne empiriske estimater af $v_\pi(s)$.

Generelt kan processen opdeles i følgende trin:

1. Generér en episode ved hjælp af politik $\pi$;
2. Gem den opnåede returværdi for hver tilstand, der optræder i episoden;
3. Gentag trin 1-2 i et stykke tid;
4. Beregn de nye værdier ved at tage gennemsnittet af returværdierne for hver tilstand.

Indsamling af afkast

Monte Carlo-estimering af værdifunktionen kræver indsamling af afkast fra genererede episoder. For at beregne disse afkast kan der anvendes to primære tilgange:

• Første-besøg: for hver tilstand $s$, der optræder i en episode, medtages kun afkastet efter dens første forekomst. Efterfølgende forekomster af samme tilstand i samme episode ignoreres ved estimeringen;
• Hver-besøg: hver forekomst af en tilstand $s$ i en episode anvendes. Det vil sige, at afkastet efter hvert besøg i tilstanden indgår i estimatet, selv hvis tilstanden optræder flere gange i samme episode.

Udforskende starttilstande

Forestil dig en simpel endimensionel verden repræsenteret af en linje, der strækker sig fra -10 til +10. Agenten starter ved position 0, og dens nuværende politik dikterer, at den altid bevæger sig til højre ved hvert tidssteg.

Hvis vi forsøger at generere episoder under denne politik, hvad sker der så? Agenten vil kontinuerligt bevæge sig mod den positive ende af linjen — besøge tilstande som 1, 2, 3 og så videre — men den vil aldrig besøge nogen negative tilstande. Som følge heraf kan vi ikke estimere værdifunktioner for tilstande til venstre for origo, simpelthen fordi agenten aldrig oplever dem.

Så hovedproblemet er: hvis visse dele af tilstandsrum aldrig udforskes, vil deres værdiestimater forblive unøjagtige eller udefinerede. En almindelig løsning på dette problem er brugen af exploring starts.

Med exploring starts begynder hver episode ikke i en fast starttilstand som 0, men i en tilfældig udvalgt tilstand. Når episoden begynder, følger agenten sin nuværende politik som sædvanligt. Over tid, ved at starte fra mange forskellige punkter i tilstandsrum, er agenten i stand til at besøge alle tilstande — ikke kun dem, dens politik naturligt ville føre den til. Dette gør det muligt for Monte Carlo-metoden at producere mere nøjagtige og komplette værdiestimater for hele tilstandsrum.

Pseudokode

Denne pseudokode anvender every-visit-tilgangen sammen med exploring starts.