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 statt auf 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, kann dynamische Programmierung durchgehend verwendet werden, auch für die Politikbewertung, da dies effizienter und präziser wäre.

Daher ist das Ersetzen von Monte-Carlo-Methoden zur Wertschätzung zwar ein Schritt in Richtung modellfreies Reinforcement Learning, aber es muss auch eine Möglichkeit 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 DP 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ätzvorgang 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 der Policy-Iteration entwickeln, die nicht auf ein Modell angewiesen ist. Dazu werden die Schritte Policy-Bewertung und Policy-Verbesserung durch die oben beschriebenen Prozesse ersetzt.

Optimierung

Während der Schritt der Bewertung wie beschrieben mittels Monte-Carlo-Schätzung 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 eine Struktur ähnlich der Policy-Iteration verfolgt wird, verstärkt sich diese Ineffizienz: Nach jeder Policy-Verbesserung muss die Monte-Carlo-Schätzung erneut durchgeführt werden, um die neue Policy zu bewerten — dies führt zu erheblichem Mehraufwand und langsamem Lernen.

Eine natürlichere Alternative besteht darin, die Policy unmittelbar nach der Verarbeitung jeder Episode zu aktualisieren. Anstatt auf einen vollständigen Durchlauf der Policy-Bewertung zu warten, kann der Agent sein Verhalten Episode für Episode anhand der aktuellsten Aktionswertschätzungen verfeinern.

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

Pseudocode

Dieser Algorithmus folgt einem GPI-Rahmenwerk, 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.