Indem der Schritt der Politikbewertung im Standardalgorithmus der Politikiteration durch die im vorherigen Kapitel beschriebenen Monte-Carlo-Schätzverfahren ersetzt wird, 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 hier liegt 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 stattdessen durchgehend dynamische Programmierung verwendet werden, auch für die Politikbewertung, da dies effizienter und präziser wäre.

Daher ist das Ersetzen von Wertschätzungen durch Monte-Carlo-Methoden zwar ein Schritt in Richtung modellfreies Reinforcement Learning, aber es muss auch ein Weg gefunden werden, 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 auf Übergangswahrscheinlichkeiten zur Berechnung des erwarteten Ertrags angewiesen zu sein, können direkt die Aktionen ausgewä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 als die alte ist, da der Politikverbesserungssatz weiterhin gilt:

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

Schätzung der Aktionswertfunktion

Der Schätzungsprozess ist nahezu identisch mit der 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 der Policy-Iteration entwickeln, die nicht auf ein Modell angewiesen ist. Dazu werden die Schritte Policy-Evaluation und Policy-Verbesserung durch die oben beschriebenen Prozesse ersetzt.

Optimierung

Während der Schritt der Evaluation mithilfe der 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 ausreichend genaue Schätzungen zu liefern. Wenn wir eine Struktur ähnlich der Policy-Iteration verfolgen, wird diese Ineffizienz noch verstärkt: Nach jeder Policy-Verbesserung muss die Monte-Carlo-Schätzung erneut durchgeführt werden, um die neue Policy zu bewerten – was zu erheblichem Mehraufwand und langsamem Lernen führt.

Eine natürlichere Alternative besteht darin, die Policy unmittelbar nach der Verarbeitung jeder Episode zu aktualisieren. Anstatt eine vollständige Runde der Policy-Evaluation abzuwarten, kann der Agent sein Verhalten Episode für Episode anhand der aktuellsten Aktionswertschätzungen verfeinern.

Dies führt zu einer Methode, die der Value-Iteration stärker ähnelt: Aspekte von Evaluation 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 spezifischen 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.