Som du vet kan en tillståndsvärdefunktion 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 till 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 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 Bellman-ekvationen som uppdateringsregel:

Den uppskattade tillståndsvärdesfunktionen $v_k$ konvergerar så småningom till den sanna tillståndsvärdesfunktionen $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:

• Fullständig backup: denna metod innebär att de nya uppskattningarna lagras i en separat array, skild från den som innehåller de tidigare (backade) 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 avslutas?

Vid iterativ policyevaluering finns det ingen exakt punkt då algoritmen bör avslutas. Även om konvergens är garanterad i gränsen, är det onödigt att fortsätta beräkningarna efter en viss punkt i praktiken. Ett enkelt och effektivt stoppkriterium är att övervaka 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 säkert avslutas.

Pseudokod