Som du vet, kan en state value function for en gitt policy bestemmes ved å løse en Bellman-ligning:

Hvis du har en fullstendig modell av miljøet (dvs. kjente overgangssannsynligheter og forventede belønninger for alle tilstands-handlingspar), er de eneste ukjente variablene som gjenstår i ligningen tilstandsverdiene. Derfor kan ligningen ovenfor omformuleres som et system av $|S|$ lineære ligninger med $|S|$ ukjente.

For eksempel, hvis en MDP har 2 tilstander ($s_1$, $s_2$) og 2 handlinger (flytt til $s_1$, flytt til $s_2$), kan tilstandsverdifunksjonen defineres slik:

Dette kan løses ved hjelp av standard lineær algebra.

En entydig løsning for et slikt lineært system er garantert dersom minst ett av følgende vilkår er oppfylt:

• Diskonteringsfaktoren tilfredsstiller $γ < 1$;
• Politikken $\pi$, når den følges fra en hvilken som helst tilstand $s$, sikrer at episoden til slutt terminerer.

Iterativ policy-evaluering

Løsningen kan beregnes direkte, men en iterativ tilnærming brukes oftere på grunn av enkel implementering. Denne metoden starter med å tildele vilkårlige startverdier til alle tilstander, unntatt terminaltilstander, som settes til 0. Verdiene oppdateres deretter iterativt ved å bruke Bellman-ligningen som oppdateringsregel:

Den estimerte tilstandsverdifunksjonen $v_k$ konvergerer til slutt mot en sann tilstandsverdifunksjon $v_\pi$ når $k \to \infty$ dersom $v_\pi$ eksisterer.

Strategier for verdi-backup

Ved oppdatering av verdiestimatene beregnes nye estimater basert på tidligere verdier. Prosessen med å bevare tidligere estimater kalles en backup. Det finnes to vanlige strategier for å utføre backups:

• Full backup: denne metoden innebærer å lagre de nye estimatene i et eget array, adskilt fra det som inneholder de tidligere (backede) verdiene. Dermed kreves to arrays — ett for å opprettholde de tidligere estimatene og ett for å lagre de nyberegnede verdiene;
• In-place backup: denne tilnærmingen holder alle verdier i ett enkelt array. Hvert nytt estimat erstatter umiddelbart den forrige verdien. Denne metoden reduserer minnebruken, ettersom kun ett array er nødvendig.

Vanligvis foretrekkes in-place backup-metoden fordi den krever mindre minne og konvergerer raskere, på grunn av umiddelbar bruk av de siste estimatene.

Når skal man stoppe oppdateringen?

I iterativ policy-evaluering finnes det ikke et eksakt tidspunkt hvor algoritmen skal stoppe. Selv om konvergens er garantert i det uendelige, er det unødvendig å fortsette beregningene etter et visst punkt i praksis. Et enkelt og effektivt stoppkriterium er å følge med på absoluttverdien av forskjellen mellom påfølgende verdiestimat, $|v_{k+1}(s) - v_k(s)|$, og sammenligne dette med en liten terskel $\theta$. Hvis det etter en full oppdateringssyklus (hvor verdiene for alle tilstander er oppdatert) ikke er noen endringer som overstiger $\theta$, kan prosessen trygt avsluttes.

Pseudokode