Die Idee hinter On-Policy-Methoden ist intuitiv: Ein Agent lernt, indem er seiner aktuellen Politik folgt und diese Politik basierend auf den gemachten Erfahrungen verbessert. Um bessere Aktionen zu entdecken und zu vermeiden, in suboptimalem Verhalten stecken zu bleiben, integriert der Agent einen Grad an Zufälligkeit – gelegentlich probiert er alternative Aktionen aus, um die Erkundung zu fördern.

Analogie

Stellen Sie sich vor, Sie sind in einer Eisdiele und es gibt drei Sorten: Schokolade, Vanille und Erdbeere. Sie lieben Schokolade und wählen normalerweise diese Sorte. Doch eines Tages entscheiden Sie sich aus Neugier, stattdessen Erdbeere zu probieren. Es stellt sich heraus, dass das Erdbeereis in diesem Laden unglaublich lecker ist, und Sie entscheiden sich, künftig immer diese Sorte zu wählen, wenn Sie die Eisdiele besuchen.

Das Ausprobieren eines neuen Geschmacks war nicht unbedingt die logischste Wahl basierend auf bisherigen Erfahrungen, aber es bot die Möglichkeit, etwas Neues zu entdecken. Genau diese Art der Erkundung steht im Zentrum der On-Policy-Methoden.

Stochastische Politiken

Formal bedeutet die Übernahme dieses Konzepts, dass die deterministischen (harten) Politiken aus der dynamischen Programmierung durch stochastische (weiche) Politiken ersetzt werden, bezeichnet als $\pi(a | s)$, wobei:

Mit anderen Worten: Jede Aktion in jedem Zustand hat eine von Null verschiedene Wahrscheinlichkeit, ausgewählt zu werden. Dies stellt sicher, dass alle Teile der Umgebung letztlich erkundet werden können, was beim Lernen aus Erfahrung unerlässlich ist.

$\Large\varepsilon$-gierige Politiken

Um Exploration in die Politik zu integrieren, wird das Konzept der $\varepsilon$-gierigen Exploration aus dem Multi-Armed-Bandit-Problem übernommen. Dadurch lässt sich eine stochastische Politik definieren, die das Ausnutzen der besten bekannten Aktion mit dem Erkunden von Alternativen ausbalanciert:

Diese Politik verhält sich meist gierig — sie wählt die Aktion mit dem höchsten geschätzten Wert — aber mit Wahrscheinlichkeit $\varepsilon$ wird eine zufällige Aktion gewählt. Dadurch erhält jede Aktion eine von Null verschiedene Wahrscheinlichkeit, ausgewählt zu werden (auch die gierige Aktion kann erneut durch gleichmäßige Auswahl gewählt werden).

Auf den ersten Blick scheint dieser Ansatz problematisch: Da die Politik niemals rein gierig wird, wird sie niemals exakt zur optimalen Politik konvergieren. Somit erfüllt sie die Bedingungen für GPI nicht streng, wenn exakte Optimalität im Grenzfall erwartet wird.

Allerdings verlangt GPI nicht, dass die Politik sofort optimal wird — es ist lediglich erforderlich, dass jede Politik verbessert wird (oder gleich bleibt) im Vergleich zur vorherigen, sodass schrittweise eine Annäherung an die Optimalität erfolgt. Die $\varepsilon$-gierige Politik erfüllt diese Bedingung: Sie verbessert die Politik im Durchschnitt und gewährleistet fortlaufende Exploration zur Unterstützung besserer Schätzungen.

Um das Problem der Konvergenz zur tatsächlich optimalen Politik zu adressieren, kann $\varepsilon$ schrittweise reduziert werden. Diese Strategie ermöglicht es der Politik, im Verlauf des Lernens zunehmend gieriger zu werden. In den frühen Phasen unterstützt Exploration das Sammeln vielfältiger Erfahrungen, während in späteren Phasen das verbesserte Wissen ausgenutzt wird. Mit einem angemessen abnehmenden $\varepsilon$ konvergiert die Methode im Grenzfall zu einer optimalen Politik.

Pseudocode