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

Analogie

Stellen Sie sich vor, Sie befinden sich 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.

Das Ausprobieren eines neuen Geschmacks war basierend auf bisherigen Erfahrungen nicht unbedingt die logischste Wahl, 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 in der dynamischen Programmierung verwendeten deterministischen (harten) Politiken 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 die Definition einer stochastischen Politik, 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, durch gleichmäßiges Sampling).

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

Allerdings verlangt GPI nicht, dass die Politik sofort optimal wird – es ist nur erforderlich, dass jede Politik verbessert wird (oder gleich bleibt) im Vergleich zur vorherigen, sodass schrittweise die Optimalität erreicht wird. 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 der Agent sein verbessertes Wissen ausnutzt. Mit einem angemessen abnehmenden $\varepsilon$ konvergiert die Methode im Grenzfall zu einer optimalen Politik.

Pseudocode