Durch das Ersetzen des Schritts der Politikbewertung im Standardalgorithmus der Politikiteration durch die im vorherigen Kapitel beschriebenen Monte-Carlo-Schätzverfahren lässt sich bereits eine neue Variante der Politikiteration ableiten – eine, die auf gesampelten Erfahrungen anstelle von dynamischer Programmierung basiert.

Es gibt jedoch eine entscheidende Einschränkung. In der traditionellen Politikiteration hängt der Schritt der Politikverbesserung davon ab, dass ein vollständiges Modell der Umgebung vorliegt. Konkret wird zur Aktualisierung der Politik folgender Ausdruck verwendet:

Diese Gleichung setzt voraus, dass die Übergangswahrscheinlichkeiten $p(s', r | s, a)$ bekannt sind. Genau das ist jedoch das Problem: Monte-Carlo-Methoden sind für modellfreie Umgebungen konzipiert, in denen die Übergangsdynamik der Umgebung unbekannt ist. Wenn ein vollständiges Modell verfügbar ist, sollte man ohnehin dynamische Programmierung verwenden, auch für die Politikbewertung, da dies effizienter und präziser wäre.

Daher ist das Ersetzen der Wertschätzung durch Monte-Carlo-Methoden zwar ein Schritt in Richtung modellfreies Reinforcement Learning, aber wir müssen auch einen Weg finden, die Politikverbesserung ohne Kenntnis des Modells durchzuführen. Dies erfordert einen Wechsel von der Zustandswertfunktion zur Aktionswertfunktion.

Warum Aktionswerte?

Durch die Verwendung von Aktionswerten ist es möglich, die Politikverbesserung ohne ein Modell der Umgebung durchzuführen. Anstatt sich auf Übergangswahrscheinlichkeiten zu stützen, um erwartete Erträge zu berechnen, können direkt die Aktionen gewählt werden, die den höchsten Wert zu liefern scheinen. Der Schritt der Politikverbesserung wird dann zu:

Und es ist nicht schwer zu zeigen, dass die neue Politik nicht schlechter ist als die alte, da der Politikverbesserungssatz weiterhin gilt:

Und wie bei DP garantiert dieser Satz, dass entweder $\pi_{k+1}$ besser ist als $\pi_k$ oder dass beide gleich und optimal sind.

Schätzung der Aktionswertfunktion

Der Schätzungsprozess ist nahezu identisch zur Zustandswertfunktion. Alle Konzepte, die zur Schätzung von Zustandswerten verwendet werden, können auch zur Schätzung von Aktionswerten eingesetzt werden.

Pseudocode

Auf diese Weise sollten sich mit genügend Iterationen die geschätzten Aktionswerte den tatsächlichen Aktionswerten annähern.

Damit lässt sich bereits eine Methode ähnlich zur Policy Iteration entwickeln, die nicht auf ein Modell angewiesen ist. Dazu werden die Schritte Policy Evaluation und Policy Improvement durch die oben beschriebenen Prozesse ersetzt.

Optimierung

Obwohl der Evaluierungsschritt mit Monte-Carlo-Schätzung wie beschrieben durchgeführt werden kann, ist er in der Regel rechnerisch ineffizient. Wie bereits gezeigt, benötigen Monte-Carlo-Methoden typischerweise eine große Anzahl von Stichproben, um einigermaßen genaue Schätzungen zu liefern. Wenn wir eine Struktur ähnlich der Policy Iteration verfolgen, wird diese Ineffizienz noch verstärkt: Nach jeder Politikverbesserung muss die Monte-Carlo-Schätzung erneut ausgeführt werden, um die neue Politik zu bewerten – was zu erheblichem Mehraufwand und langsamen Lernprozessen führt.

Eine natürlichere Alternative besteht darin, die Politik unmittelbar nach der Verarbeitung jeder Episode zu aktualisieren. Anstatt auf eine vollständige Evaluierung der Politik zu warten, kann der Agent sein Verhalten Episode für Episode anhand der neuesten Aktionswertschätzungen verfeinern.

Dies führt zu einer Methode, die Value Iteration stärker ähnelt: Aspekte von Evaluierung und Verbesserung werden in einem einzigen Schritt kombiniert. Dadurch steigt die Stichprobeneffizienz und die Rechengeschwindigkeit erhöht sich.

Pseudocode

Dieser Algorithmus folgt einem GPI-Framework, da er Schritte zur Politikbewertung und Politikverbesserung enthält, und wird als Monte-Carlo-Kontrolle bezeichnet. Der größte Nachteil dieser speziellen Implementierung ist die Annahme von exploring starts. In den nächsten Kapiteln wird erläutert, warum dies ein Problem darstellt und wie damit umgegangen werden kann.