Värdefunktionsuppskattning

Vi börjar med att återbesöka ett välkänt 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, under antagandet att vi har en given policy $\pi$ men ingen tillgång till miljömodellens struktur.

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ärdefunktionen 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 tidsteg.

Om vi försöker generera episoder under denna policy, vad händer då? Agenten kommer att fortsätta 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 exploring starts.

Med exploring starts börjar varje episod inte i ett fast starttillstånd som 0, utan i ett slumpmässigt valt tillstånd. När episoden har börjat följer agenten sin nuvarande policy som vanligt. Med tiden, genom att starta 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 kompletta värdeuppskattningar för hela tillståndsrymden.

Pseudokod

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