Achieving $\epsilon^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Technische Samenvatting: Bereiken van $\tilde{O}(\epsilon^{-2})$ Steekproefcomplexiteit voor Single-Loop Actor-Critic onder Minimale Aannames

Probleemstelling
Versterkend leren (RL) heeft tot doel Markov-beslissingsprocessen (MDP's) op te lossen via datagedreven methoden. Waar methods in de waardenruimte, zoals Q-learning, onder minimale aannames (specifiek het bestaan van een irreducibel gedragsbeleid) een steekproefcomplexiteit van $\tilde{O}(\epsilon^{-2})$ hebben bewezen, zijn methoden in de beleidsruimte, zoals actor-critic, historisch gezien achtergebleven wat theoretische garanties betreft. Bestaande analyses van actor-critic die een complexiteit van $\tilde{O}(\epsilon^{-2})$ bereiken, vertrouwen doorgaans op twee restrictieve voorwaarden:

1. Geneste-loop-implementaties: Waar de critic meerdere keren wordt bijgewerkt terwijl de actor vaststaat, een structuur die verschilt van praktische single-loop-algoritmen.
2. Sterke, algoritme-afhankelijke aannames: Zoals het vereiste dat alle beleidsplannen die tijdens het traject van het algoritme (of de volledige beleidsklasse) worden aangetroffen, irreducibele en aperiodieke Markov-ketens induceren met uniform begrenste mengsnelheden en exploratie-eigenschappen.

Deze aannames creëren een circulaire afhankelijkheid: het verifiëren van de mengeigenschappen vereist het beheersen van de beleidssequentie die door het algoritme wordt gegenereerd, wat precies het object is van de convergentieanalyse. Bovendien werken praktische actor-critic-algoritmen op een single-loop, single-timescale manier met off-policy leren, waarbij de critic een tijdsvariërend doelbeleid volgt. Dit introduceert uitdagingen met betrekking tot gekoppelde updatevergelijkingen en potentieel onbegrensde iteraten door importance sampling, uitdagingen waar bestaande theoretische kaders moeite mee hebben zonder sterke aannames.

Methodologie
De auteurs stellen een single-loop, single-timescale off-policy actor-critic-algoritme voor waarbij de actor en de critic gelijktijdig worden bijgewerkt bij elke iteratie. De actor maakt gebruik van incrementele updates naar een doelbeleid $\tilde{\pi}_t$ dat is afgeleid via benaderde beleidsiteratie (API) of natuurlijke beleidsgradiënt (NPG), terwijl de critic off-policy temporal-difference (TD)-lering uitvoert. De auteurs overwegen twee varianten van de critic:

• Importance Sampling (IS): Corrigeert distributieve mismatch met behulp van een importance weight-ratio.
• Expected Temporal Difference (ETD): Berekent direct de verwachte Q-functie bij de volgende toestand, waardoor expliciete importance weights worden vermeden.

De kern van de technische innovatie ligt in het analysekader. Om de koppeling tussen de actor- en critic-updates en het onbegrensde karakter van off-policy iteraten te hanteren, maken de auteurs gebruik van een gekoppeld Lyapunov-driftkader.

1. Lyapunov-functies: Ze construeren aparte Lyapunov-functies voor de actor ($V_t = \|Q^* - Q_{\pi_t}\|_\infty^2$) en de critic ($W_t = \|Q_t - Q_{\pi_t}\|_\nu^2$).
2. Driftongelijkheden: Ze stellen negatieve driftongelijkheden vast voor beide functies. Cruciaal bevatten deze ongelijkheden kruistermen die de fout uit het gekoppelde systeem vertegenwoordigen (bijvoorbeeld de critic-fout die verschijnt in de drift van de actor en vice versa).
3. Kruis-dominatie: De analyse vertrouwt op een eigenschap van "kruis-dominatie". Door zorgvuldig stapgrootteverhoudingen te selecteren en te waarborgen dat de koppelingsfouttermen worden gedomineerd door de negatieve drifttermen van de respectievelijke systemen, combineren de auteurs de twee driftongelijkheden tot één recursie voor $V_t + W_t$. Deze aanpak is geïnspireerd op small-gain-theorie in dynamische systemen, maar is hier aangepast om Markoviaanse ruis, tijdsvariërende doelen en onbegrensde iteraten op een uniforme manier te behandelen.

Belangrijkste Bijdragen en Resultaten
Het artikel vestigt de eerste convergentiesnelheden voor de laatste iteratie voor een single-loop actor-critic-algoritme dat onder minimale aannames een $\tilde{O}(\epsilon^{-2})$ steekproefcomplexiteit bereikt.

• Minimale Aannames: De enige vereiste aanname is het bestaan van een beleid dat een irreducibele Markov-keten over de toestandsruimte induceert. Dit beleid hoeft niet te worden bezocht door het algoritme, noch hoeft het algoritme de mengeigenschappen van de door het gegenereerde beleidsplannen te controleren. Dit staat in contrast met eerdere werken die uniforme ergodiciteit vereisten over het traject of de volledige beleidsklasse.
• Steekproefcomplexiteit: Onder deze minimale aanname bereikt het algoritme een $\tilde{O}(\epsilon^{-2})$ steekproefcomplexiteit om een $\epsilon$-optimaal beleid te vinden. Deze snelheid is near-minimax optimaal met betrekking tot $\epsilon$.
• Stapgrootte-schema's: De resultaten gelden voor constante, harmonische en polynoomiale stapgrootte-sequenties. Specifiek levert het gebruik van harmonische stapgroottes met geschikte parameters de optimale snelheid op.
• Algoritmevarianten: De analyse dekt zowel IS-gebaseerde als ETD-gebaseerde critics. Hoewel beide dezelfde complexiteitsorde bereiken, vertoont de ETD-variant een mildere afhankelijkheid van probleemparameters (grootte van de toestandsruimte $n$, grootte van de actieruimte $m$, en discontofactor $\gamma$) omdat het de extra stochastiek die door importance sampling-ratio's wordt geïntroduceerd, vermijdt.
• Onbegrensde Iteraten: Het kader behandelt succesvol de potentieel onbegrensde iteraten die worden veroorzaakt door off-policy leren (met name bij IS), een uitdaging die in eerdere literatuur vaak sterke begrenzingsaannames vereiste.

Betekenis en Claims
De auteurs claimen dat dit werk een significante theoretische kloof overbrugt tussen methoden in de waardenruimte en methoden in de beleidsruimte. Door aan te tonen dat actor-critic-methoden minimax-optimale steekproefcomplexiteit kunnen bereiken zonder geneste lussen of sterke, algoritme-afhankelijke mengaannames, daagt het artikel het idee uit dat methoden in de beleidsruimte inherent minder steekproefefficiënt zijn of sterkere voorwaarden vereisen.

Het analytische kader gebaseerd op gekoppeld Lyapunov-drift en kruis-dominatie wordt gepresenteerd als een bijdrage van onafhankelijk belang, mogelijk toepasbaar op andere gekoppelde iteratieve algoritmen met onbegrensde iteraten. Het artikel merkt expliciet op dat hoewel de afhankelijkheid van $\epsilon$ near-optimaal is, de afhankelijkheid van probleemspecifieke constanten ($n, m, (1-\gamma)^{-1}$) suboptimaal kan zijn in vergelijking met op waarden gebaseerde methoden, wat suggereert dat variansiereductietechnieken een richting voor toekomstige verbetering kunnen zijn. Het werk vermijdt claims over functiebenaderingssettings (de "dodelijke triade") of specifieke empirische toepassingen, en richt zich strikt op de tabulaire setting en theoretische garanties.