Ein Algorithmus der dynamischen Programmierung, der wiederholt den Bellman-Optimalitätsoperator auf Zustandswertschätzungen anwendet und Backups über Zustände ausführt, bis die Wertfunktion unter Kontraktionseigenschaften konvergiert.

Prinzip

Die Kontraktionseigenschaft des Bellman-Optimalitätsoperators für diskontierte MDPs ausnutzen: iterative Anwendung des Backups V_{k+1}=T[V_k] konvergiert zur eindeutigen Fixpunktlösung V* und liefert durch gierige Extraktion eine optimale Politik.

Demonstration

Für ein finales MDP mit Diskontfaktor gamma∈(0,1) initialisiere V0 beliebig und iteriere V_{k+1}(s)=max_a{ R(s,a)+gamma sum_{s'} P(s'|s,a) V_k(s') } bis sup_s |V_{k+1}(s)-V_k(s)| < Toleranz, dann erstelle eine gierige Politik.

Fehlanwendung

Naives Value Iteration mit ungeeigneter Funktionsapproximation oder auf undiskontierten Problemen ohne Kontraktionsgarantie anwenden; in zu großen Zustandsräumen ohne Approximation führt dies zu unpraktikabler Laufzeit und Speicherbedarf.

Konsequenz

Unter Standardannahmen konvergiert Value Iteration zur optimalen Wertfunktion und liefert eine optimale Politik durch gierige Auswahl; es ist eine kanonische Basis für Planung und Reinforcement-Learning-Algorithmen.

Umkehrung

Policy Iteration wechselt zwischen expliziter Politikevaluation und Politikverbesserung und kann in weniger Iterationen konvergieren, erfordert jedoch pro Iteration teurere Auswertungsschritte.

Abgrenzung

Garantiert für diskontierte MDPs oder Situationen, in denen der Bellman-Operator ein Kontraktor ist; Vorsicht bei kontinuierlichen Zustandsräumen, partieller Beobachtbarkeit oder Funktionsapproximation, wo theoretische Garantien schwächer werden.

Semantische Spannung

Spannung zu Policy Iteration und Q-Learning: Value Iteration führt vollständige Backups über Werte aus und konvergiert unter Kontraktion, während Policy Iteration auf Evaluation/Verbesserung setzt und Q-Learning Aktionswerte aus Stichproben schätzt.

Synthese

Wertiteration = iterative Fixpunktberechnung mittels Bellman-Backups bis Konvergenz zu V*, dann gierige Politikextraktion; praxistauglich, wenn exakte Zustandsmodelle vorliegen und Kontraktionsbedingungen erfüllt sind.