Während On-Policy-Methoden durch das Befolgen und Verbessern derselben Politik lernen, führen Off-Policy-Methoden eine Besonderheit ein: Sie lernen über eine Politik (die Zielpolitik), während sie einer anderen folgen (der Verhaltenspolitik). Diese Trennung ist leistungsstark — sie ermöglicht es, eine Zielpolitik zu bewerten oder zu verbessern, ohne ihr während der Datenerhebung tatsächlich folgen zu müssen.

Analogie

Kehren wir zum Eissalon aus dem vorherigen Kapitel zurück. Du und dein Freund betreten das Geschäft, und wieder stehen die drei bekannten Sorten zur Auswahl: Schokolade, Vanille und Erdbeere. Schokolade ist dein persönlicher Favorit, und dein erster Impuls ist es, diese zu bestellen. Aber dieses Geschäft ist neu für dich, und du bist dir nicht sicher, ob Schokolade die richtige Wahl ist. Zum Glück ist dein Freund ein bekannter Eisliebhaber, der fast jeden Laden in der Stadt besucht hat. Du fragst nach seiner Meinung. "Die Schokolade hier ist in Ordnung", sagt er, "aber glaub mir — die Erdbeere ist außergewöhnlich." Aufgrund seiner Erfahrung entscheidest du dich, deine übliche Wahl zu überspringen und stattdessen Erdbeere zu nehmen.

Diese Entscheidung – sich auf die Erfahrungen anderer zu stützen, um die eigene Wahl zu treffen – ist das Wesen der Off-Policy-Methoden. Ziel ist es, die eigene Entscheidungsfindung mithilfe von Daten zu verbessern, die unter dem Verhalten anderer gesammelt wurden. Es handelt sich weiterhin um Exploration – jedoch geleitet durch externe Erfahrungen anstelle der eigenen.

Importance Sampling

Da der Agent während der Episodenerzeugung der Verhaltenspolitik folgt, muss die Diskrepanz zwischen dem, was die Verhaltenspolitik erzeugt, und dem, was die Zielpolitik erzeugen würde, berücksichtigt werden. Hier kommt das Importance Sampling zum Einsatz.

Importance Sampling bietet eine Methode, die unter der Verhaltenspolitik beobachteten Erträge so anzupassen, dass sie gültige Schätzungen für die Zielpolitik darstellen.

Betrachten wir eine Trajektorie, die von einem bestimmten Zustand $S_t$ ausgeht und einer bestimmten Politik $\pi$ folgt, bis die Episode zum Zeitpunkt $T$ endet. Konkret beobachten wir:

Wie hoch ist nun die Wahrscheinlichkeit, dass diese Trajektorie unter einer Politik $\pi$ auftritt? Sie hängt sowohl von den Aktionswahrscheinlichkeiten der Politik als auch von den Übergangsdynamiken der Umgebung ab:

Angenommen, die Trajektorie wurde tatsächlich von einer anderen Politik — der Verhaltenspolitik $b$ — erzeugt. Um diese Trajektorie korrekt zur Schätzung von Erwartungen unter der Zielpolitik $\pi$ zu verwenden, müssen wir berücksichtigen, wie viel wahrscheinlicher oder unwahrscheinlicher diese Aktionssequenz unter $\pi$ im Vergleich zu $b$ gewesen wäre.

Hier kommt das Importance Sampling Verhältnis ins Spiel. Es ist definiert als das relative Auftretenswahrscheinlichkeit der Trajektorie unter den beiden Politiken:

Letztlich kürzen sich die Übergangswahrscheinlichkeiten heraus, da beide Politiken in derselben Umgebung agieren, und der Wert von $\rho$ hängt nur von den Politiken ab, nicht von der Umgebung.

Warum das wichtig ist

Das Verhältnis $\rho$ gibt an, wie der unter der Verhaltenspolitik beobachtete Ertrag $G_t$ gewichtet werden muss, damit er eine unverzerrte Schätzung dessen wird, was der Ertrag unter der Zielpolitik gewesen wäre:

Mit anderen Worten: Auch wenn die Daten mit $b$ gesammelt wurden, können wir dennoch die erwarteten Erträge unter $\pi$ schätzen — vorausgesetzt, $b$ weist jeder Aktion, die $\pi$ wählen könnte, eine von Null verschiedene Wahrscheinlichkeit zu (Annahme der Abdeckung).

Praktische Überlegungen

Varianz beim Importance Sampling

Die Einbindung von Importance Sampling ist konzeptionell unkompliziert. Die geschätzte Aktionswertfunktion $q(s, a)$ wird angepasst, indem jede beobachtete Belohnung mit dem entsprechenden Importance-Sampling-Verhältnis gewichtet wird. Die einfachste Formulierung sieht folgendermaßen aus:

wobei:

• $\rho_i(s, a)$ das Importance-Sampling-Verhältnis für die $i$-te Trajektorie ab $(s, a)$ ist;
• $Returns_i(s, a)$ die Belohnung aus dieser Trajektorie ist;
• $N(s, a)$ die Anzahl der Besuche von $(s, a)$ ist.

Dies wird als gewöhnliches Importance Sampling bezeichnet. Es liefert eine unverzerrte Schätzung von $q(s, a)$, kann jedoch unter sehr hoher Varianz leiden, insbesondere wenn sich die Verhaltens- und Zielpolitik stark unterscheiden.

Um das Varianzproblem zu verringern, kann eine stabilere Alternative verwendet werden: gewichtetes Importance Sampling. Diese Methode normalisiert die Importance-Gewichte, wodurch der Einfluss großer Verhältnisse reduziert und ein stabileres Lernen ermöglicht wird:

In dieser Version ist der Zähler die gleiche gewichtete Summe der Belohnungen, aber der Nenner ist nun die Summe der Importance-Gewichte anstelle einer einfachen Zählung.

Dies macht die Schätzung verzerrt, aber die Verzerrung nimmt mit zunehmender Stichprobengröße ab. In der Praxis wird gewichtetes Importance Sampling bevorzugt, da es eine deutlich geringere Varianz und eine höhere numerische Stabilität bietet.

Politiken

Wie im On-Policy-Fall verwenden wir $\varepsilon$-gierige Politiken sowohl für die Zielpolitik $\pi(a | s)$ als auch für die Verhaltenspolitik $b(a | s)$.

Auf den ersten Blick erscheint es naheliegend, die Zielpolitik vollständig gierig zu gestalten – schließlich ist unser eigentliches Ziel eine gierige Politik. In der Praxis führt dies jedoch zu einem erheblichen Problem: Falls zu irgendeinem Zeitpunkt $\pi(a | s) = 0$ für die Aktion ist, die tatsächlich von der Verhaltenspolitik ausgeführt wurde, wird das Importance Sampling-Verhältnis $\rho$ zu null und der verbleibende Teil der Episode wird effektiv verworfen.

Durch die Verwendung eines kleinen $\varepsilon$ (z. B. $\varepsilon = 0.01$) in der Zielpolitik stellen wir sicher, dass $\pi(a | s) > 0$ für jede Aktion gilt, sodass $\rho$ niemals mitten in der Episode auf null fällt. Nach Abschluss des Trainings kann die erlernte $\varepsilon$-gierige Politik problemlos in eine strikt gierige Politik umgewandelt werden. Wie beim On-Policy-Lernen sollte $\varepsilon$ in der Verhaltenspolitik dekrementiert werden, diesmal jedoch hauptsächlich zur numerischen Stabilisierung, da $\rho$ dennoch während einer Episode auf null fallen kann, bedingt durch die Art und Weise, wie Zahlen im Computer dargestellt werden.

Pseudocode