Zoals bekend kan een toestandswaardefunctie van een gegeven beleid worden bepaald door het oplossen van een Bellman-vergelijking:

Als u een compleet model van de omgeving heeft (d.w.z. bekende overgangswaarschijnlijkheden en verwachte beloningen voor alle toestand-actieparen), zijn de enige onbekende variabelen in de vergelijking de toestandswaarden. Daarom kan de bovenstaande vergelijking worden geherformuleerd als een systeem van $|S|$ lineaire vergelijkingen met $|S|$ onbekenden.

Bijvoorbeeld, als een MDP 2 toestanden heeft ($s_1$, $s_2$) en 2 acties (verplaats naar $s_1$, verplaats naar $s_2$), kan de toestandswaardefunctie als volgt worden gedefinieerd:

Dit kan worden opgelost met standaard lineaire algebra technieken.

Een unieke oplossing voor een dergelijk lineair systeem is gegarandeerd als aan ten minste één van de volgende voorwaarden wordt voldaan:

• De discontovoet voldoet aan $γ < 1$;
• Het beleid $\pi$, gevolgd vanuit elke toestand $s$, garandeert dat de episode uiteindelijk eindigt.

Iteratieve Beleidswaardering

De oplossing kan direct worden berekend, maar een iteratieve benadering wordt vaker gebruikt vanwege de eenvoudige implementatie. Deze methode begint met het toekennen van willekeurige beginwaarden aan alle toestanden, behalve voor terminale toestanden, die worden ingesteld op 0. De waarden worden vervolgens iteratief bijgewerkt met behulp van de Bellman-vergelijking als update-regel:

De geschatte toestandswaardefunctie $v_k$ convergeert uiteindelijk naar een werkelijke toestandswaardefunctie $v_\pi$ als $k \to \infty$, mits $v_\pi$ bestaat.

Waarde-backupstrategieën

Bij het bijwerken van waarde-inschattingen worden nieuwe schattingen berekend op basis van eerdere waarden. Het proces waarbij eerdere schattingen worden behouden, staat bekend als een backup. Er zijn twee gangbare strategieën voor het uitvoeren van backups:

• Volledige backup: deze methode houdt in dat de nieuwe schattingen worden opgeslagen in een aparte array, gescheiden van de array met de eerdere (back-up) waarden. Er zijn dus twee arrays nodig — één voor het bijhouden van de eerdere schattingen en één voor het opslaan van de nieuw berekende waarden;
• In-place backup: bij deze aanpak worden alle waarden in één enkele array bijgehouden. Elke nieuwe schatting vervangt direct de vorige waarde. Deze methode vermindert het geheugengebruik, omdat slechts één array nodig is.

Meestal heeft de in-place backup-methode de voorkeur, omdat deze minder geheugen vereist en sneller convergeert, dankzij het directe gebruik van de meest recente schattingen.

Wanneer stoppen met bijwerken?

Bij iteratieve beleidsevaluatie is er geen exact moment waarop het algoritme moet stoppen. Hoewel convergentie in de limiet gegarandeerd is, is het in de praktijk onnodig om de berekeningen eindeloos voort te zetten. Een eenvoudige en effectieve stopcriterium is het bijhouden van het absolute verschil tussen opeenvolgende waarde-inschattingen, $|v_{k+1}(s) - v_k(s)|$, en dit te vergelijken met een kleine drempelwaarde $\theta$. Als na een volledige updatecyclus (waarbij de waarden voor alle toestanden zijn bijgewerkt) geen enkele wijziging groter is dan $\theta$, kan het proces veilig worden beëindigd.

Pseudocode