Technische Samenvatting: Emergentie van Exploratie in Policy Gradient Reinforcement Learning via Retrying

1. Probleemstelling

In Reinforcement Learning (RL) wordt exploratie doorgaans gedreven door het toevoegen van expliciete bonussen (bijv. entropie, nieuwsgierigheid of count-based bonussen) aan het beloningssignaal, of door het hanteren van posterior sampling-methoden. De auteurs stellen een afwijkend mechanisme voor: exploratie zou natuurlijk moeten voortkomen uit de behoefte van de agent om beloningen te maximaliseren onder onzekerheid door middel van retrying (opnieuw proberen).

De kernintuïtie is dat in omgevingen waar een agent acties kan herhalen of vergelijkbare toestanden kan tegenkomen, een greedily beleid suboptimaal is als het de potentie voor hogere rendementen bij volgende pogingen negeert. Zonder de mogelijkheid om opnieuw te proberen, is de rationele keuze de actie die momenteel als de hoogste beloning wordt beschouwd. Echter, onder onzekerheid kan een beleid dat zich indekt tegen onzekerheid door alternatieve acties te verkennen, een hogere verwachte maximale return bereiken over meerdere pogingen. Bestaande methoden vereisen vaak complexe hulpmodellen om onzekerheid te schatten of bonussen te construeren; dit artikel vraagt zich af of exploratie puur geïnduceerd kan worden door een beloningsgestuurd doel te optimaliseren dat de waarde van retrying formaliseert.

2. Methodologie

2.1 Het ReMax-doel

De auteurs stellen ReMax (Retry Maximum) voor, een doelstelling die een beleid $\pi$ evalueert door het verwachte maximum over $M$ onafhankelijke monsters (pogingen), in plaats van het verwachte rendement van een enkele poging.

In een bandit-setting met actiewaarden $\mu$ en een distributie over deze waarden $\Pi$ (die epistemische onzekerheid vertegenwoordigt), wordt de ReMax-doelstelling gedefinieerd 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]$$
waarbij $A^{[M]}$ staat voor $M$ onafhankelijke trekkingen uit het beleid $\pi$.

• Mechanisme: Door het verwachte maximum over $M$ trekkingen te maximaliseren, stimuleert de doelstelling het beleid om waarschijnlijkheidsmassa toe te wijzen aan acties die een hoge beloning zouden kunnen opleveren, zelfs als ze niet de momenteel geschatte gemiddelde maximum zijn. Dit induceert stochasticiteit (exploratie) als een emergente eigenschap om in te dekken tegen onzekerheid.
• Deterministisch geval: Zelfs met vaste beloningen vormt ReMax de geometrie van de doelstelling opnieuw. Het verhogen van de retry-parameter $M$ vlakt de gradiënt nabij het optimum af, wat de convergentie vertraagt en exploratie in stand houdt, terwijl een kleinere $M$ de updates versnelt.

2.2 Extensie naar RL (MDP's)

Het uitbreiden van ReMax naar Markov Decision Processes (MDP's) brengt uitdagingen met zich mee:

1. Onzekerheidseenheid: Onzekerheid in RL omvat de gehele omgeving (beloningen en transities).
2. Haalbaarheid van retries: Het fysiek resetten van een omgeving om meerdere acties vanuit dezelfde staat te proberen, is vaak onhaalbaar.

Om dit aan te pakken, definiëren de auteurs de ReMax-doelstelling met behulp van een Q-functie $Q^\pi_M(s, a)$, die het verwachte episodische rendement vertegenwoordigt. De doelstelling wordt geformuleerd als het verwachte maximum over $M$ trekkingen van Q-waarden op staat $s$:
$$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]$$
Hier vangt de distributie $\mathcal{Q}$ de onzekerheid over de Q-waarden op (ofwel via expliciete modellering zoals ensembles, ofwel impliciet via de niet-stationariteit van diepe critics).

2.3 Policy Gradient Formulering

Om ReMax efficiënt te optimaliseren, leiden de auteurs een nieuwe policy gradient (PG) estimator af die berekenbaar is vanuit single-trajectory returns.

• Falen van de Naïeve Aanpak: Een directe toepassing van de policy gradient theorem vereist het observeren van de rendementen voor alle $M$ gesamplede acties gelijktijdig, wat in episodische RL onhaalbaar is.
• Expected Improvement (EI) Herformulering: De auteurs introduceren een baseline gebaseerd op "Expected Improvement" (geleend uit Bayesiaanse optimalisatie). Ze deconstrueren de max-operator in een actie-specifieke term en een baseline die het maximum van de andere $M-1$ trekkingen representeert ($W_{-m}$).
• Closed-Form Oplossing: Door de Q-waarden te sorteren, leiden ze een closed-form expressie af voor de expected improvement term. Dit maakt het mogelijk om de gradiënt te schatten met behulp van een single-trajectory return $R(s, a)$ en de huidige Q-schattingen.
• Continue Parameter $m$: Het gehele getal $m$ (retry count $M$) wordt gegeneraliseerd naar een continue reële parameter $m > 0$. Dit maakt fijne controle mogelijk over de exploratie-exploitatie balans. De term $(1 - C_j)^{M-1}$ in de closed-form oplossing wordt vervangen door $(1 - C_j)^{m-1}$.

2.4 RePPO Algoritme

De auteurs implementeren ReMax binnen het Proximal Policy Optimization (PPO) framework, wat resulteert in ReMax PPO (RePPO).

• Architectuur: Een on-policy actor-critic methode met een Q-critic.
• Surrogaat Doelstelling: RePPO wijzigt de standaard PPO surrogaat door de standaard advantage te vervangen door een EI-gebaseerde advantage.
  $$A^+(t) = R^+(t) - b^+(s_t)$$
  waarbij $R^+(t) = \text{EIm}(R^\lambda_t, \pi_\theta, Q_\phi(s_t, \cdot))$ en $b^+$ de verwachte waarde is van de EI-getransformeerde Q-waarden.
• Q-Vervangingsstrategie: Om te voorkomen dat de critic de verbetering van de gesamplede actie overschat (door onderschatting van de Q-waarde), vervangen de auteurs de Q-waarde van de gesamplede actie door het werkelijke traject-rendement bij het berekenen van de EI-term. Dit zorgt ervoor dat de "verbetering" wordt gemeten tegen het werkelijke rendement, en niet tegen een potentieel bevooroordeelde schatting.

3. Belangrijkste Bijdragen

1. ReMax Doelstelling: Een nieuwe RL-doelstelling die exploratie induceert via greedy beloningsmaximalisatie onder onzekerheid (retrying) zonder expliciete exploratiebonussen.
2. Theoretische Afleiding: Een nieuwe policy gradient formulering voor ReMax die schatbaar is vanuit single-trajectory returns, gebruikmakend van een closed-form expressie voor het verwachte maximum over $M$ trekkingen.
3. Continue Controle: De generalisatie van de discrete retry count $M$ naar een continue parameter $m$, wat een precieze afstemming van de exploratie-exploitatie ratio mogelijk maakt.
4. RePPO Algoritme: Een praktisch deep RL algoritme (RePPO) dat ReMax implementeert binnen een PPO framework, waarmee wordt aangetoond dat exploratie voortkomt uit de doelstelling zelf.

4. Experimentele Resultaten

4.1 Bandit Experimenten

• Stochasticiteit: In een two-armed bandit induceert ReMax stochastic beleid voor $M \ge 2$, terwijl standaard RL ($M=1$) deterministische beleid oplevert.
• Adaptiviteit: ReMax past exploratie aan op de magnitude van de beloningsonzekerheid. Naarmate de variantie toeneemt, verhoogt de optimale ReMax-policy de exploratie om zeldzame hoog-belonende uitkomsten te vangen, in tegen tegenstelling tot de entropy-regularized softmax die vast blijft op basis van het gemiddelde.
• Regret: In posterior bandit settings (Beta-Bernoulli en Gaussian-Gaussian) vertoont ReMax empirisch sublineaire cumulatieve regret, vergelijkbaar met Thompson Sampling en UCB, en superieur aan een Softmax baseline.

4.2 MinAtar Benchmarks

Geëvalueerd op vier spellen (Breakout, Asterix, Freeway, Space Invaders):

• Prestaties: RePPO (met $m \in [1.2, 1.4]$) presteerde beter dan standaard PPO varianten (PPO-V, PPO-Q) en PPO met entropie-bonussen of Random Network Distillation (RND) bonussen.
• Exploratie: RePPO behield een hogere policy entropie tijdens de training vergeleken met PPO met een expliciete entropie-bonus, ondanks het ontbreken van een dergelijke bonus.
• Parametergevoeligheid: Prestaties piekten rond $m=1.2$ tot $1.4$. Grotere $m$ vertraagden de entropie-decay (wat exploratie in stand hield), terwijl kleinere $m$ leidden tot snellere convergentie maar lagere prestaties.
• Ablatie: Het verwijderen van de actie-onafhankelijke baseline of de Q-vervangingsstrategie degradeerde de prestaties aanzienlijk, wat hun noodzaak bevestigt.

4.3 Craftax Benchmark

Geëvalueerd op Craftax, een grootschalige, open-ended RL-omgeving:

• Prestaties: RePPO ($m=1.2$) behaalde competitieve prestaties (11.87% van de max reward) vergeleken met PPO varianten met entropie en RND bonussen (11.66% en 11.68%), en presteerde beter dan PPO zonder bonussen.
• Schaalbaarheid: RePPO behield een hogere entropie zonder expliciete bonussen, wat aantoont dat het mechanisme schaalt naar complexe, lange-horizon taken.

5. Betekenis en Claims

Het artikel claimt dat ReMax een veelbelovend alternatief biedt voor traditionele exploratiemethoden door:

• Het elimineren van de noodzaak voor expliciete bonussen: Exploratie komt natuurlijk voort uit het doel om het verwachte maximum rendement over retries te maximaliseren.
• Het vereenvoudigen van algoritmeontwerp: Het vermijdt de computationele overhead en complexiteit van het ontwerpen van nieuwsgierigheidsbonussen of het onderhouden van expliciete posterior modellen (hoewel het deze kan gebruiken voor onzekerheidsschatting).
• Het bieden van fijne controle: De continue parameter $m$ maakt een precieze afstemming van de exploratie-exploitatie balans mogelijk.

De auteurs merken op dat hoewel hun deep RL experimenten primair stochastische exploratie (verhoogde policy entropie) hebben aangetoond, het theoretische kader diepe exploratie (temporeel coherente informatieverzameling) ondersteunt indien gecombineerd met expliciete onzekerheidsmodellering (bijv. ensembles). Zij positioneren ReMax als een algemeen principe toepasbaar op domeinen waar retrying waardevol is, inclus\n bij reasoning taken met Large Language Models (LLMs), waarbij zij parallellen trekken met pass@K doelstellingen in dat veld.

Het werk is bescheiden in zijn theoretische claims, waarbij wordt opgemerkt dat formele regret bounds voor de deep RL setting aan toekomstig onderzoek worden overgelaten, en de huidige resultaten empirische demonstraties van effectiviteit zijn.