Låt oss börja med att återbesöka ett välbekant begrepp: tillståndsvärdesfunktionen, betecknad som $v_\pi(s)$. Den kan definieras som

Målet i detta kapitel är att skatta denna funktion utifrån data, givet att vi har en fast policy $\pi$ men ingen tillgång till miljöns modell.

Monte Carlo-skattning

Monte Carlo-metoder angriper denna skattningsuppgift genom att sampla episoder av erfarenheter under policyn $\pi$ och sedan använda dessa sampel för att skapa empiriska skattningar av $v_\pi(s)$.

Generellt kan processen delas upp i följande steg:

1. Generera en episod med hjälp av policyn $\pi$;
2. Spara det erhållna returvärdet för varje tillstånd som förekommer i episoden;
3. Upprepa steg 1-2 under en viss tid;
4. Beräkna de nya värdena genom att ta medelvärdet av returvärdena för varje tillstånd.

Insamling av avkastningar

Monte Carlo-estimering av värdefunktion kräver insamling av avkastningar från genererade episoder. För att beräkna dessa avkastningar kan två huvudsakliga metoder användas:

• Första-besök: för varje tillstånd $s$ som påträffas i en episod beaktas endast avkastningen efter dess första förekomst. Efterföljande förekomster av samma tillstånd inom samma episod ignoreras vid uppskattningen;
• Varje-besök: varje förekomst av ett tillstånd $s$ inom en episod används. Det vill säga, avkastningen efter varje besök i tillståndet inkluderas i uppskattningen, även om tillståndet förekommer flera gånger i samma episod.

Utforskande starter

Föreställ dig en enkel endimensionell värld representerad av en linje som sträcker sig från -10 till +10. Agenten börjar på position 0, och dess nuvarande policy innebär att den alltid rör sig åt höger vid varje tidssteg.

Om vi försöker generera episoder under denna policy, vad händer då? Agenten kommer kontinuerligt att röra sig mot den positiva änden av linjen — besöka tillstånd som 1, 2, 3 och så vidare — men den kommer aldrig att besöka några negativa tillstånd. Som ett resultat kan vi inte uppskatta värdefunktioner för tillstånd till vänster om origo, helt enkelt eftersom agenten aldrig upplever dem.

Så huvudproblemet är: om vissa delar av tillståndsrymden aldrig utforskas, kommer deras värdeuppskattningar att förbli inexakta eller odefinierade. En vanlig lösning på detta problem är användningen av utforskande starter.

Med utforskande starter börjar varje episod inte vid ett fast starttillstånd som 0, utan vid ett slumpmässigt valt tillstånd. När episoden har börjat följer agenten sin nuvarande policy som vanligt. Med tiden, genom att börja från många olika punkter i tillståndsrymden, kan agenten besöka alla tillstånd — inte bara de som dess policy naturligt skulle leda till. Detta gör att Monte Carlo-metoden kan ge mer exakta och fullständiga värdeuppskattningar för hela tillståndsrymden.

Pseudokod

Denna pseudokod använder every-visit-metoden tillsammans med exploring starts.