Policyutvärdering

Som du vet kan en state value function för en given policy bestämmas genom att lösa en Bellman-ekvation:

Om du har en fullständig modell av miljön (dvs. kända övergångssannolikheter och förväntade belöningar för alla tillstånd-handlingspar), är de enda okända variablerna som återstår i ekvationen tillståndsvärdena. Därför kan ekvationen ovan omformuleras som ett system av $|S|$ linjära ekvationer med $|S|$ okända.

Till exempel, om en MDP har 2 tillstånd ($s_1$, $s_2$) och 2 handlingar (flytta till $s_1$, flytta till $s_2$), kan tillståndsvärdesfunktionen definieras så här:

Detta kan lösas med standardtekniker inom linjär algebra.

En unik lösning för ett sådant linjärt system garanteras om minst ett av följande villkor uppfylls:

• Diskonteringsfaktorn uppfyller $γ < 1$;
• Policyn $\pi$, när den följs från ett godtyckligt tillstånd $s$, säkerställer att episoden så småningom avslutas.

Iterativ policyevaluering

Lösningen kan beräknas direkt, men en iterativ metod används oftare på grund av dess enkla implementering. Denna metod börjar med att tilldela godtyckliga initialvärden till alla tillstånd, förutom terminala tillstånd, vilka sätts till 0. Värdena uppdateras sedan iterativt med hjälp av Bellmans ekvation som uppdateringsregel:

Den uppskattade tillståndsvärdesfunktionen $v_k$ konvergerar så småningom till en sann tillståndsvärdesfunktion $v_\pi$ när $k \to \infty$ om $v_\pi$ existerar.

Strategier för värdebackup

Vid uppdatering av värdeuppskattningar beräknas nya uppskattningar baserat på tidigare värden. Processen att bevara tidigare uppskattningar kallas en backup. Det finns två vanliga strategier för att utföra backups:

• Full backup: denna metod innebär att de nya uppskattningarna lagras i en separat array, skild från den som innehåller de tidigare (backupade) värdena. Följaktligen krävs två arrayer — en för att behålla de tidigare uppskattningarna och en annan för att lagra de nyberäknade värdena;
• In-place backup: detta tillvägagångssätt behåller alla värden i en enda array. Varje ny uppskattning ersätter omedelbart det tidigare värdet. Denna metod minskar minnesanvändningen, eftersom endast en array behövs.

Vanligtvis föredras metoden in-place backup eftersom den kräver mindre minne och konvergerar snabbare tack vare den omedelbara användningen av de senaste uppskattningarna.

När ska uppdateringen stoppas?

Vid iterativ policyevaluering finns det ingen exakt punkt där algoritmen bör stoppas. Även om konvergens är garanterad i gränsen, är det onödigt i praktiken att fortsätta beräkningarna efter en viss punkt. Ett enkelt och effektivt stoppkriterium är att spåra den absoluta skillnaden mellan på varandra följande värdeuppskattningar, $|v_{k+1}(s) - v_k(s)|$, och jämföra den med en liten tröskel $\theta$. Om, efter en fullständig uppdateringscykel (där värden för alla tillstånd uppdateras), inga förändringar överstiger $\theta$, kan processen avslutas säkert.

Pseudokod