On-Policy-Monte-Carlo-Steuerung

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 gewissen 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 nehmen, wenn Sie die Eisdiele besuchen.

Die Wahl einer neuen Geschmacksrichtung war nicht unbedingt die logischste Entscheidung basierend auf bisherigen Erfahrungen, aber sie bot die Möglichkeit, etwas Neues zu entdecken. Und genau diese Art der Erkundung steht im Mittelpunkt von On-Policy-Methoden.

Stochastische Politiken

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

Anders ausgedrückt: 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 einzubringen, wird das Konzept der $\varepsilon$-gierigen Exploration aus dem Multi-Armed-Bandit-Problem übernommen. Damit 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 ausgewählt, sodass alle Aktionen eine von Null verschiedene Wahrscheinlichkeit haben, gewä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. Sie erfüllt also nicht streng die Bedingungen für GPI, wenn man exakte Optimalität im Grenzfall erwartet.

Allerdings verlangt GPI nicht, dass die Politik sofort optimal wird – es reicht, dass jede Politik besser wird (oder gleich bleibt) im Vergleich zur vorherigen und sich so schrittweise der Optimalität nähert. Die $\varepsilon$-gierige Politik erfüllt diese Bedingung: Sie verbessert die Politik im Durchschnitt und sorgt für fortlaufende Exploration, um bessere Schätzungen zu ermöglichen.

Um das Problem der Konvergenz zur wirklich optimalen Politik zu adressieren, kann $\varepsilon$ schrittweise reduziert werden. Dadurch wird die Politik im Verlauf des Lernens immer gieriger. In den frühen Phasen hilft Exploration, vielfältige Erfahrungen zu sammeln, 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