Technisches Resümee: Emergenz von Exploration in Policy Gradient Reinforcement Learning durch Retrying

1. Problemstellung

In Reinforcement Learning (RL) wird Exploration typischerweise durch das Hinzufügen expliziter Boni (z. B. Entropie, Neugier oder count-basierte Boni) zum Belohnungssignal oder durch den Einsatz von Posterior-Sampling-Methoden vorangetrieben. Die Autoren postulieren einen distinkten Mechanismus: Exploration sollte natürlich aus dem Bedürfnis des Agenten entstehen, Belohnungen unter Unsicherheit durch Retrying (Wiederholen) zu maximieren.

Die Kernintuition ist, dass in Umgebungen, in denen ein Agent Aktionen wiederholen kann oder ähnlichen Zuständen begegnet, eine gierige (greedy) Policy suboptimal ist, wenn sie das Potenzial für höhere Erträge in nachfolgenden Versuchen ignoriert. Ohne die Möglichkeit des Wiederholens ist die rationale Wahl die Aktion, die derzeit als am höchsten belohnend gilt. Unter Unsicherheit kann jedoch eine Policy, die gegen die Unsicherheit absichert, indem sie alternative Aktionen exploriert, einen höheren erwarteten maximalen Ertrag über mehrere Versuche hinweg erzielen. Bestehende Methoden erfordern oft komplexe Hilfsmodelle, um Unsicherheit zu schätzen oder Boni zu konstruieren; dieses Paper fragt, ob Exploration rein durch die Optimierung eines belohnungsbasierten Objekts induziert werden kann, das den Wert des Retrying formalisiert.

2. Methodik

2.1 Das ReMax-Objektiv

Die Autoren schlagen ReMax (Retry Maximum) vor, ein Objektiv, das eine Policy $\pi$ durch den erwarteten maximalen Ertrag über $M$ unabhängige Stichproben (Versuche) bewertet, anstatt durch den erwarteten Ertrag eines einzelnen Versuchs.

In einem Bandit-Szenario mit Aktionswerten $\mu$ und einer Verteilung über diese Werte $\Pi$ (die epistemische Unsicherheit repräsentiert), ist das ReMax-Objektiv definiert als:
$$J^M_{\text{ReMax}}(\pi) := \mathbb{E}_{\mu \sim \Pi} \left[ \mathbb{E}_{A^{[M]} \sim \pi} \left[ \max_{m \in [M]} \mu_{A_m} \mid \mu \right] \right]$$
wobei $A^{[M]}$ $M$ unabhängige Züge aus der Policy $\pi$ darstellt.

• Mechanismus: Durch die Maximierung des erwarteten Maximums von $M$ Zügen wird das Objektiv die Policy dazu anregen, Wahrscheinlichkeitsmasse auf Aktionen zu legen, die hohe Belohnungen liefern könnten, selbst wenn dies nicht der aktuell geschätzte Maximalwert ist. Dies induziert Stochastizität (Exploration) als emergente Eigenschaft, um sich gegen Unsicherheit abzusichern.
• Deterministischer Fall: Selbst bei festen Belohnungen verändert ReMax die Geometrie des Objektivs. Ein Erhöhen des Retry-Parameters $M$ flacht den Gradienten nahe dem Optimum ab, was die Konvergenz verlangsamt und die Exploration aufrechterhält, während ein kleineres $M$ die Updates beschleunigt.

2.2 Erweiterung auf RL (MDPs)

Die Erweiterung von ReMax auf Markov-Entscheidungsprozesse (MDPs) stellt Herausforderungen dar:

1. Unsicherheitseinheit: Unsicherheit in RL umfasst die gesamte Umgebung (Belohnungen und Übergänge).
2. Machbarkeit von Retries: Das physische Zurücksetzen einer Umgebung, um mehrere Aktionen aus demselben Zustand heraus zu wiederholen, ist oft nicht praktikabel.

Um dies zu adressieren, definieren die Autoren das ReMax-Objektiv mithilfe einer Q-Funktion $Q^\pi(s, a)$, die den erwarteten episodischen Ertrag repräsentiert. Das Objektiv wird als das erwartete Maximum über $M$ Züge von Q-Werten im Zustand $s$ formuliert:
$$J^M_{\text{ReMax}}(\pi, s, Q) := \mathbb{E}_{Q \sim \mathcal{Q}} \left[ \mathbb{E}_{A^{[M]} \sim \pi} \left[ \max_{m \in [M]} Q(s, A_m) \right] \right]$$
Hierbei erfasst die Verteilung $\mathcal{Q}$ die Unsicherheit über die Q-Werte (entweder durch explizite Modellierung wie Ensembles oder implizit durch die Nicht-Stationarität tiefer Kritiker).

2.3 Policy Gradient Formulierung

Um ReMax effizient zu optimieren, leiten die Autoren einen neuen Policy-Gradient-Schätzer (PG) her, der aus Single-Trajectory-Returns berechenbar ist.

• Scheitern des naiven Ansatzes: Eine direkte Anwendung des Policy Gradient Theorems erfordert die Beobachtung von Erträgen für alle $M$ gesampelten Aktionen gleichzeitig, was in episodischem RL nicht praktikabel ist.
• Expected Improvement (EI) Reformulierung: Die Autoren führen einen Baseline ein, der auf der "Expected Improvement" basiert (entlehnt aus der Bayes'schen Optimierung). Sie zerlegen den Max-Operator in einen aktionsspezifischen Term und eine Baseline, die das Maximum der anderen $M-1$ Züge repräsentiert ($W_{-m}$).
• Geschlossene Lösung: Durch Sortieren der Q-Werte leiten sie einen geschlossenen Ausdruck für den Expected-Improvement-Term her. Dies ermöglicht es, den Gradienten unter Verwendung eines Single-Trajectory-Returns $R(s, a)$ und der aktuellen Q-Schätzungen zu schätzen.
• Kontinuierlicher Parameter $m$: Der ganzzahlige Retry-Zähler $M$ wird auf einen kontinuierlichen reellen Parameter $m > 0$ generalisiert. Dies ermöglicht eine feingliedrige Steuerung des Exploration-Exploitation-Trade-offs. Der Term $(1 - C_j)^{M-1}$ in der geschlossenen Lösung wird durch $(1 - C_j)^{m-1}$ ersetzt.

2.4 RePPO Algorithmus

Die Autoren instanziieren ReMax innerhalb des Proximal Policy Optimization (PPO) Frameworks und schaffen so ReMax PPO (RePPO).

• Architektur: Eine On-Policy Actor-Critic-Methode unter Verwendung eines Q-Kritikers.
• Surrogat-Objektiv: RePPO modifiziert das Standard-PPO-Surrogat, indem der Standard-Advantage durch einen EI-basierten Advantage ersetzt wird.
  $$A^+(t) = R^+(t) - b^+(s_t)$$
  wobei $R^+(t) = \text{EIm}(R^\lambda_t, \pi_\theta, Q_\phi(s_t, \cdot))$ und $b^+$ der erwartete Wert der EI-transformierten Q-Werte ist.
• Q-Ersetzungsstrategie: Um zu verhindern, dass der Kritiker die Verbesserung der gesampelten Aktion überschätzt (aufgrund einer Unterschätzung des Q-Wertes), ersetzen die Autoren den Q-Wert der gesampelten Aktion durch den tatsächlichen Trajektorien-Return, wenn der EI-Term berechnet wird. Dies stellt sicher, dass die "Verbesserung" gegen den wahren Ertrag gemessen wird und nicht gegen eine potenziell verzerrte Schätzung.

3. Wichtigste Beiträge

1. ReMax Objektiv: Ein neuartiges RL-Objektiv, das Exploration durch gierige Maximierung des Ertrags unter Unsicherheit (Retrying) induziert, ohne explizite Explorations-Boni zu benötigen.
2. Theoretische Herleitung: Eine neue Policy-Gradient-Formulierung für ReMax, die mittels eines geschlossenen Ausdrucks für das erwartete Maximum über $M$ Züge aus Single-Trajectory-Returns schätzbar ist.
3. Kontinuierliche Steuerung: Die Generalisierung des diskreten Retry-Zählers $M$ auf einen kontinuierlichen Parameter $m$, was eine präzise Abstimmung der Exploration-Rate ermöglicht.
4. RePPO Algorithmus: Ein praktischer Deep-RL-Algorithmus (RePPO), der ReMax innerhalb eines PPO-Frameworks implementiert und zeigt, dass Exploration aus dem Objektiv selbst entstehen kann.

4. Experimentelle Ergebnisse

4.1 Bandit-Experimente

• Stochastizität: In einem Two-Armed Bandit induziert ReMax stochastische Policies für $M \ge 2$, während Standard-RL ($M=1$) deterministische Policies liefert.
• Adaptivität: ReMax passt die Exploration an die Magnitude der Belohnungsunsicherheit an. Wenn die Varianz steigt, erhöht die optimale ReMax-Policy die Exploration, um seltene High-Reward-Outcomes zu erfassen, im Gegensatz zur Entropie-regulierten Softmax, die basierend auf dem Mittelwert fix bleibt.
• Regret: In Posterior-Bandit-Settings (Beta-Bernoulli und Gaussian-Gaussian) weist ReMax empirisch sublinearen kumulativen Regret auf, der vergleichbar mit Thompson Sampling und UCB ist und gegenüber einer Softmax-Baseline überlegen ist.

4.2 MinAtar Benchmarks

Evaluierung auf vier Spielen (Breakest, Asterix, Freeway, Space Invaders):

• Performance: RePPO (mit $m \in [1.2, 1.4]$) übertraf Standard-PPO-Varianten (PPO-V, PPO-Q) sowie PPO mit Entropie-Boni oder Random Network Distillation (RND) Boni.
• Exploration: RePPO hielt während des Trainings eine höhere Policy-Entropie aufrecht als PPO mit einem expliziten Entropie-Bonus, obwohl es keinen solchen Bonus besitzt.
• Parameter-Sensitivität: Die Performance erreichte ihren Höhepunkt um $m=1.2$ bis $1.4$. Größere $m$-Werte verlangsamten den Entropie-Abfall (was die Exploration aufrechterhielt), während kleinere $m$-Werte zu schnellerer Konvergenz, aber geringerer Performance führten.
• Ablation: Das Entfernen der aktionsunabhängigen Baseline oder der Q-Ersetzungsstrategie verschlechterte die Performance signifikant, was deren Notwendigkeit bestätigt.

4.3 Craftax Benchmark

Evaluierung auf Craftax, einer großskaligen, Open-Ended RL-Umgebung:

• Performance: RePPO ($m=1.2$) erreichte eine konkurrenzfähige Performance (11.87% des maximalen Rewards) im Vergleich zu PPO-Varianten mit Entropie- und RND-Boni (11.66% bzw. 11.68%) und übertraf PPO ohne Boni.
• Skalierbarkeit: RePPO behielt ohne explizite Boni eine höhere Entropie bei, was zeigt, dass der Mechanismus auf komplexe Aufgaben mit langen Zeithorizonten skalierbar ist.

5. Bedeutung und Behauptungen

Das Paper behauptet, dass ReMax eine vielversprechende Alternative zu traditionellen Explorationsmethoden bietet, indem es:

• Den Bedarf an expliziten Boni eliminiert: Exploration entsteht natürlich aus dem Ziel, den erwarteten maximalen Ertrag über Retries zu maximieren.
• Das Algorithmus-Design vereinfacht: Es vermeidet den Rechenaufwand und die Komplexität beim Design von Curiosity-Boni oder der Pflege expliziter Posterior-Modelle (obwohl es diese zur Unsicherheitsschätzung nutzen kann).
• Feingliedrige Kontrolle bietet: Der kontinuierliche Parameter $m$ ermöglicht eine präzise Justierung des Exploration-Exploitation-Trade-offs.

Die Autoren merken an, dass ihre Deep-RL-Experimente primstär stochastische Exploration (erhöhte Policy-Entropie) demonstriert haben, das theoretische Framework jedoch tiefe Exploration (zeitlich kohärente Informationsbeschaffung) unterstützt, sofern es mit expliziter Unsicherheitsmodellierung (z. B. Ensembles) kombiniert wird. Sie positionieren ReMax als ein allgemeines Prinzip, das auf Domänen anwendbar ist, in denen Retrying wertvoll ist, einschließlich Reasoning-Aufgaben mit Large Language Models (LLMs), wobei sie Parallelen zu pass@K-Objektiven in diesem Bereich ziehen.

Die Arbeit ist in ihren theoretischen Ansprüchen bescheiden und stellt fest, dass formale Regret-Bounds für das Deep-RL-Setting der zukünftigen Arbeit vorbehalten sind und die aktuellen Ergebnisse empirische Demonstrationen der Effektivität sind.