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 suboptimales Verhalten zu vermeiden, 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 außergewöhnlich lecker ist, und Sie entscheiden sich, künftig immer diese Sorte zu wählen, wenn Sie die Eisdiele besuchen.

Das Probieren 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, übernehmen wir das Konzept der $\varepsilon$-gierigen Exploration aus dem Multi-Armed-Bandit-Problem. Dies ermöglicht es, eine stochastische Politik zu 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, sodass jede Aktion eine von Null verschiedene Wahrscheinlichkeit hat, ausgewählt zu werden (auch die gierige Aktion, durch gleichmäßige Auswahl).

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

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 sie sich schrittweise der Optimalität nähert. 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 wirklich 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 der Agent sein verbessertes Wissen ausnutzt. Mit einem angemessen abnehmenden $\varepsilon$ konvergiert die Methode im Grenzfall zu einer optimalen Politik.

Pseudocode