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

Als u een volledig 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 zo'n 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$, zorgt ervoor 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.

Strategieën voor waarde-backup

Bij het bijwerken van waarde-inschattingen worden nieuwe schattingen berekend op basis van eerdere waarden. Het proces van het behouden van eerdere schattingen wordt een backup genoemd. 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. Hierdoor zijn er 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.

Doorgaans 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, zijn verdere berekeningen na een bepaald punt onnodig in de praktijk. 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$. Indien na een volledige updatecyclus (waarbij waarden voor alle toestanden zijn bijgewerkt) geen enkele wijziging groter is dan $\theta$, kan het proces veilig worden beëindigd.

Pseudocode