Technische Samenvatting: Hergebruik van Trajecten in Policy Gradients Maakt Snelle Convergentie Mogelijk

Probleemstelling

Policy Gradient (PG) methoden zijn effectief voor continue controleproblemen, maar lijden onder een slechte steekproefefficiëntie (sample efficiency). Standaard "vanilla" PG-algoritmen (bijv. REINFORCE, GPOMDP) vertrouwen uitsluitend op verse on-policy data, wat $O(\epsilon^{-2})$ trajecten vereist om een $\epsilon$-benaderend stationair punt te bereiken. Deze inefficiëntie komt voort uit de hoge variantie van gradiënt-schattingen, die niet verdwijnt omdat gradiënten altijd worden geschat op basis van nieuwe monsters.

Hoewel het hergebruik van het verleden (off-policy trajecten of gradiënten) een veelgebruikte strategie is om de efficiëntie te verbeteren, heeft bestaand theoretisch werk zich grotendeels gericht op gradiënt-hergebruik (bijv. SVRPG, SRVRPG, STORM-PG), waarbij snelheden tot $O(\epsilon^{-3/2})$ worden bereikt. Het hergebruik van het verleden van trajecten, hoewel intuïtief, is vanuit een rigoureus theoretisch perspectief grotendeels onontgonnen gebleven. Eerdere pogingen om trajecten te hergebruiken, misten ofwel convergentiegaranties, of vertrouwden op sterke aannames en complexe estimators (bijv. het vereisen van opslag van alle eerdere policies of het lijden onder hoge variantie door naïeve importance weighting).

De centrale vraag die wordt geadresseerd is: Kan het hergebruik van het verleden van off-policy trajecten leiden tot bewijsbare verbeteringen in de steekproefcomplexiteit van PG-methoden?

Methodologie

Het RT-PG Algoritme

De auteurs stellen RT-PG (Reusing Trajectories – Policy Gradient) voor, een nieuw algoritme dat de policy gradiënt schat door gebruik te maken van trajecten die zijn verzameld tijdens de meest recente $\omega$ iteraties. De kerninnovatie is de Multiple Power Mean (MPM) estimator, die on-policy en off-policy data combineert met behulp van een gecorrigeerd Multiple Importance Weighting (MIW) schema.

De MPM Estimator

Om de statistische uitdagingen van het hergebruik van data aan te pakken (specifiek de bias geïntroduceerd door de afhankelijkheid tussen de huidige policy-parameters en het verleden), gebruikt de MPM estimator twee belangrijke mechanismen:

1. Deterministische Coëfficiënten: In tegenstelling tot de Balance Heuristic (BH), die coëfficiënten gebruikt die afhankelijk zijn van alle eerdere policies (wat "cross-time bias" introduceert), gebruikt RT-PG deterministische coëfficiënten $\alpha_{i,k}$ die alleen afhangen van het iteratiegetal en de window-index. Dit elimineert cross-time bias.
2. Power Mean (PM) Correctie: Om ervoor te zorgen dat de importance weights begrensd blijven (een "defensieve" eigenschap) en om de bias te beheersen die wordt geïntroduceerd door de deterministische coëfficiënten, past de estimator een PM-correctie toe op de vanilla importance weights. De gecorrigeerde gewicht voor een traject $\tau$ verzameld onder policy $\pi_{\theta_i}$ en geëvalueerd onder $\pi_{\theta_k}$ is:
   $$\left( (1 - \lambda_{i,k}) \frac{p_{\theta_i}(\tau)}{p_{\theta_k}(\tau)} + \lambda_{i,k} \right)^{-1}$$
   waarbij $\lambda_{i,k} \in [0, 1]$ een correctieparameter is. Deze term vertegenwoordigt een harmonisch gemiddelde tussen de vanilla weight en 1, waardoor de gewicht begrensd blijft door $1/\lambda_{i,k}$.

Theoretische Analyse

De auteurs bieden een rigoureuze finite-time analyse van de MPM estimator:

• Concentratie-grenzen: Ze leiden high-probability concentratie-grenzen voor de estimator af met behulp van de Freedman-ongelijkheid voor martingalen en een covering-argument om de vector-waardige aard van de gradiënt te behandelen.
• Bias-controle: De analyse scheidt en controleert expliciet twee bronnen van bias:
  • Target Bias: Ontstaat omdat de doelparameter $\theta_k$ afhankelijk is van de historie van de trajecten. Dit wordt gecontroleerd via een covering-argument over een deelverzameling van de parameterruimte die de historie-afhankelijke doel bevat.
  • PM Bias: Ontstaat uit de PM-correctieterm. Dit wordt beheerd door zorgvuldig $\lambda_{i,k}$ te selecteren op basis van de batchgrootte en de $\chi^2$-divergentie-grens tussen de traject-distributies.

Belangrijkste Bijdragen

1. Eerste Rigoureuze Bewijs: Het artikel levert het eerste theoretische bewijs dat het hergebruik van het verleden van off-policy trajecten de convergentie van PG aanzienlijk kan versnellen.
2. Nieuwe Estimator (MPM): Introductie van de MPM estimator, die effectief on-policy data mengt met off-policy trajecten van de laatste $\omega$ iteraties, terwijl gebonden importance weights worden behouden en cross-time bias wordt geëlimineerd.
3. Verbeterde Steekproefcomplexiteit:
   • Partieel Hergebruik: Wanneer trajecten van de meest recente $\omega$ iteraties worden hergebruikt (waarbij $\omega < K$), bereikt RT-PG een steekproefcomplexiteit van $\tilde{O}(\epsilon^{-2}\omega^{-1})$.
   • Volledig Hergebruik: Wanneer alle beschikbare trajecten uit het verleden worden hergebruikt (waarbij $\omega \ge K$), bereikt het algoritme een steekproefcomplexiteit van $\tilde{O}(\epsilon^{-1})$. Dit komt overeen met de beste bekende snelheden in de literatuur voor PG-methoden en vertegenwoordigt een significante verbetering ten opzichte van de standaard $O(\epsilon^{-2})$ snelheid.
4. Praktische Implementatie: Een praktische variant van RT-PG wordt voorgesteld die off-policy data adaptief weegt op basis van empirische schattingen van de beleidsdissimilariteit (divergentie), waardoor de noodzaak voor de theoretische globale grens $D$ in de praktijk wordt weggenomen.

Resultaten

Theoretische Resultaten

Onder standaard aannames (begrensde $\chi^2$-divergentie tussen traject-distributies en regulariteit van de policy-klasse), bewijzen de auteurs dat RT-PG een $\epsilon$-benaderend stationair punt vindt met:

• $\tilde{O}(\epsilon^{-1})$ steekproefcomplexiteit in het regime van volledig hergebruik.
• $\tilde{O}(\epsilon^{-2}\omega^{-1})$ steekproefcomplexiteit in het regime van partieel hergebruik.

Deze resultaten gelden zonder dat het opslaan van eerdere policies vereist is (in tegenstelling tot BH-gebaseerde methoden); enkel het opslaan van eerdere trajecten is nodig.

Empirische Resultaten

Experimenten werden uitgevoerd op continue controle-taken (Cart Pole, Half Cheetah, Swimmer) met zowel lineaire Gaussische als diepe Gaussische policies.

• Steekproefefficiëntie: RT-PG presteert consistent beter dan standaard on-policy baselines (GPOMDP) en state-of-the-art variant-reducerende methoden (SVRPG, SRVRPG, STORM-PG, DEF-PG) in termen van steekproefefficiëntie. In de Half Cheetah omgeving behaalde RT-PG bijna tweemaal de uiteindelijke prestatie van de meeste baselines.
• Impact van Traject-hergebruik: Experimenten waarbij de window-grootte $\omega$ werd gevarieerd, toonden aan dat het vergroten van het hergebruik-window de convergentie versnelt. RT-PG vertoonde afnemende meeropbrengsten bij zeer grote windows, maar presteerde nog steeds aanzienlijk beter dan baselines, zelfs met een matig hergebruik.
• Vergelijking met Naïef Hergebruik: RT-PG presteerde aanzienlijk beter dan MIW-PG (die uniforme weighting gebruikt), wat de effectiviteit van de PM-correctie en het adaptieve weging-schema in het beheersen van variantie valideert.
• Geheugenefficiëntie: In tegenstelling tot BH-gebaseerde methoden die de opslag van alle eerdere policy-parameters vereisen om de gewichten te berekenen, vereist RT-PG alleen de opslag van eerdere trajecten, wat het schaalbaarder maakt voor hoog-dimensionale policy-ruimtes.

Betekenis en Claims

Het artikel claimt het eerste rigoureuze theoretische bewijs te leveren dat het hergebruik van trajecten een levensvatbare en krachtige mechanisme is om de convergentie van Policy Gradient te versnellen. Door het RT-PG algoritme en de MPM estimator te introduceren, overbruggen de auteurs de kloof tussen het intuïtieve idee van het hergebruiken van data uit het verleden en bewijsbare convergentiegaranties.

De betekenis ligt in:

1. Theoretische Vooruitgang: Het vaststellen dat het hergebruik van trajecten een $\tilde{O}(\epsilon^{-1})$ snelheid kan bereiken, wat voorheen als moeilijk werd beschouwd voor PG-methoden zonder sterke aannames of gradiënt-hergebruik.
2. Praktisch Nut: Het aantonen dat het hergebruik van trajecten de steekproefkosten vermindert zonder de leerstabiliteit in gevaar te brengen, wat een praktisch alternatief biedt voor gradiënt-hergebruik methoden die mogelijk grotere batches of complexe variant-reductie technieken vereisen.
3. Geheugenefficiëntie: Het bereiken van verbeterde snelheden zonder de geheugenoverhead van het opslaan van eerdere policy-parameterisaties, een beperking van andere traject-hergebruik benaderingen zoals de Balance Heuristic.

De auteurs blijven bescheiden over de beperkingen en merken op dat hun resultaten rusten op de aanname van een begrensde $\chi^2$-divergentie tussen traject-distributies en dat de steekproefcomplexiteit afhangt van de dimensie $d_\Theta$ van de parameters. Zij identificeren het verwijderen van deze aanname en het elimineren van de dimensie-afhankelijkheid als toekomstig werk.