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 verfügbar ist. Insbesondere verwenden wir zur Aktualisierung der Politik den folgenden Ausdruck:

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 man ohnehin dynamische Programmierung verwenden, auch für die Politikbewertung, da diese 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 eine Möglichkeit 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 auf Übergangswahrscheinlichkeiten zur Berechnung des erwarteten Ertrags angewiesen zu sein, können direkt diejenigen 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ä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 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 mittels 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 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 ist es, 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 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.