Ein Algorithmus zur Lösung sequentieller Entscheidungsprobleme (häufig Markov-Entscheidungsprozesse), der zwischen Evaluation einer aktuellen Policy und einer darauf basierenden greedigen Policy-Verbesserung wechselt, bis eine optimale Policy erreicht ist.

Prinzip

Wechsle zwischen genauer oder approximativer Politikevaluation und Policy-Verbesserung: berechne Zustands- oder Zustand-Aktions-Werte für die aktuelle Policy und aktualisiere dann die Policy, indem Aktionen gewählt werden, die diese Werte maximieren; wiederhole bis zur Konvergenz.

Demonstration

Bei einem MDP mit endlichen Zuständen beginnt man mit einer beliebigen deterministischen Policy, löst die linearen Bellman-Gleichungen zur Bestimmung der Policy-Werte und erzeugt dann durch Auswahl erwartungsmaximaler Aktionen eine neue Policy; diese Schritte werden wiederholt, bis die Policy stabil ist.

Fehlanwendung

Die vollständige Policy-Iteration mit exakter Evaluation auf sehr großen oder kontinuierlichen Zustandsräumen ohne geeignete Approximation ist rechnerisch nicht praktikabel und kann zu übermäßigem Speicher- oder Zeitverbrauch führen; eine greedige Verbesserung auf stark verzerrten Bewertungen kann Oszillationen verursachen.

Konsequenz

Richtig angewendet auf endliche MDPs oder mit stabilen Approximationen konvergiert Policy Iteration in endlich vielen Schritten zu einer optimalen Policy und benötigt typischerweise weniger Iterationen als naive Value Iteration.

Umkehrung

Die Umkehrung des Konzepts ist Value Iteration: Wende wiederholt Bellman-Optimalitätsupdates auf die Werte an, ohne eine explizit evaluierte Policy zu führen, und leite erst nach Konvergenz eine Policy ab.

Abgrenzung

Gilt für sequentielle Entscheidungsprozesse, in denen Policies und Wertfunktionen definiert sind; ausgeschlossen sind nicht-sequentielle Optimierungsprobleme, adversariale Spiele ohne geeignete Reformulierung und Szenarien ohne markovsche Struktur oder definierte Übergangswahrscheinlichkeiten.

Semantische Spannung

Spannung zwischen genauer Evaluation (stabil, aber teuer) und approximativer oder stichprobenbasierter Evaluation (skalierbar, aber potenziell verzerrend und instabil für die Verbesserung).

Synthese

Policy Iteration ist ein alternierendes Evaluationsschema: eine feste Entscheidungsregel wird bewertet und anschließend durch greedige Auswahl auf Basis dieser Bewertung verbessert; die wiederholte Alternanz führt zu optimalen sequentiellen Entscheidungen im angenommenen Modell.