Som du ved, kan en tilstandsværdifunktion for en given politik bestemmes ved at løse en Bellman-ligning:

Hvis du har en fuldstændig model af miljøet (dvs. kendte overgangssandsynligheder og forventede belønninger for alle tilstands-handlingspar), er de eneste ukendte variabler i ligningen tilstandsværdierne. Derfor kan ovenstående ligning omformuleres som et system af $|S|$ lineære ligninger med $|S|$ ubekendte.

For eksempel, hvis en MDP har 2 tilstande ($s_1$, $s_2$) og 2 handlinger (flyt til $s_1$, flyt til $s_2$), kan tilstandsværdifunktionen defineres således:

Dette kan løses ved hjælp af standard lineær algebra.

En entydig løsning til et sådant lineært system er garanteret, hvis mindst én af følgende betingelser er opfyldt:

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

Iterativ policy-evaluering

Løsningen kan beregnes direkte, men en iterativ tilgang anvendes oftere på grund af dens nemme implementering. Denne metode starter med at tildele vilkårlige startværdier til alle tilstande, undtagen terminale tilstande, som sættes til 0. Værdierne opdateres derefter iterativt ved hjælp af Bellman-ligningen som opdateringsregel:

Den estimerede tilstandsværdi-funktion $v_k$ konvergerer til sidst til den sande tilstandsværdi-funktion $v_\pi$, når $k \to \infty$, hvis $v_\pi$ eksisterer.

Strategier for værdi-backup

Ved opdatering af værdiestimater beregnes nye estimater baseret på tidligere værdier. Processen med at bevare tidligere estimater kaldes en backup. Der findes to almindelige strategier til at udføre backups:

• Fuld backup: denne metode indebærer lagring af de nye estimater i et separat array, adskilt fra det, der indeholder de tidligere (backede) værdier. Derfor kræves to arrays — et til at opretholde de tidligere estimater og et andet til at lagre de nyberegnede værdier;
• In-place backup: denne tilgang opretholder alle værdier i et enkelt array. Hvert nyt estimat erstatter straks den tidligere værdi. Denne metode reducerer hukommelsesforbruget, da kun ét array er nødvendigt.

Typisk foretrækkes in-place backup-metoden, fordi den kræver mindre hukommelse og konvergerer hurtigere, da de nyeste estimater straks anvendes.

Hvornår skal opdateringen stoppes?

Ved iterativ policy-evaluering findes der ikke et præcist tidspunkt, hvor algoritmen bør stoppe. Selvom konvergens er garanteret i grænsen, er det i praksis unødvendigt at fortsætte beregningerne ud over et vist punkt. Et simpelt og effektivt stopkriterium er at overvåge den absolutte forskel mellem på hinanden følgende værdiestimater, $|v_{k+1}(s) - v_k(s)|$, og sammenligne den med en lille tærskelværdi $\theta$. Hvis der efter en fuld opdateringscyklus (hvor værdierne for alle tilstande opdateres) ikke er nogen ændringer, der overstiger $\theta$, kan processen afsluttes sikkert.

Pseudokode