Technische Samenvatting: Corruptietolerante Asynchrone Q-learning met Bijna-Optimale Snelheden

Probleemformulering

Dit artikel behandelt het probleem van het leren van een optimale beleidsregel in een afgekapte, oneindige-horizon Markov Beslissingsproces (MDP) in aanwezigheid van adversariaal verontreinigde beloningen. De setting omvat een agent die interactie heeft met een omgeving gemodelleerd als een MDP $(S, A, P, R, \gamma)$, waarbij data online wordt verzameld via een gedragsbeleid $\mu$ dat een Markov-keten induceert.

De kernuitdaging is het Huber-verontreinigingsmodel toegepast op beloningen. Op elk tijdstip $t$ observeert de agent met waarschijnlijkheid $1-\epsilon$ een beloning die is getrokken uit de ware verdeling $R(s_t, a_t)$, waarvan wordt toegestaan dat deze zware staarten heeft (alleen een eindige tweede moment toestaand). Met waarschijnlijkheid $\epsilon$ wordt de beloning getrokken uit een willekeurige, potentieel onbegrensde adversariale verdeling $Q$ die afhankelijk kan zijn van de geschiedenis. Het doel is om de optimale staat-actie-waardefunctie $Q^*$ te schatten met een foutgrens voor eindige tijd die met hoge waarschijnlijkheid geldt, ondanks de corruptie en het tijdsgecorreleerde karakter van de data (asynchrone, single-trajectum steekproefneming).

Methodologie

De auteurs stellen Robust Async-Q voor, een nieuwe variant van het Q-learning-algoritme ontworpen om asynchrone steekproefneming en adversariale corruptie het hoofd te bieden. Het algoritme integreert twee primaire mechanismen:

1. Robuste Beloningsschatting via Gereduceerde Gemiddelden:
   In plaats van ruwe steekproefgemiddelden te gebruiken, houdt het algoritme een geschiedenis van beloningen bij voor elke staat-actie-paar $(s, a)$. Het maakt gebruik van een univariate gereduceerde gemiddelde-schatter (gebaseerd op Lugosi & Mendelson, 2021) om een robuuste schatting van de verwachte beloning te berekenen. Deze schatter verdeelt de data in twee helften, gebruikt de ene helft om empirische kwantielen te berekenen voor filtering, en middelt de overige steekproeven in de tweede helft die binnen deze kwantielen vallen. Deze aanpak biedt robuustheid tegen verdelingen met zware staarten en een fractie van uitbijters.

2. Adaptieve Drempelwaarde:
   Om het probabilistische karakter van garanties voor robuuste gemiddelde-schatting (die kunnen falen bij zeldzame extreme gebeurtenissen) en het gebrek aan kennis over beloningsstatistieken in sommige settings aan te pakken, hanteert het algoritme een adaptief drempelwaarde-mechanisme.

   • Bekende Statistieken: Als grenzen voor het gemiddelde en de variantie van de beloning ($\bar{R}, \bar{\sigma}$) bekend zijn, wordt een adaptieve drempelwaarde $G_t$ geconstrueerd. Als de robuuste schatting deze drempelwaarde overschrijdt, wordt de schatting verworpen (op nul gezet). De drempelwaarde krimpt naarmate er meer steekproeven worden verzameld.
   • Beloningsagnostisch (Onbekende Statistieken): Wanneer beloningsstatistieken onbekend zijn, gebruikt het algoritme een "langzaam groeiende" functie van de tijd, $m(t) = t^p$, als proxy voor de onbekende grenzen. Dit zorgt ervoor dat de drempelwaarde uiteindelijk elke ware constante grens domineert, waardoor het algoritme kan functioneren zonder voorafgaande kennis van de schaal van de beloningsverdeling.

Het algoritme werkt de Q-waarden bij met behulp van deze gefilterde en gedrempelde beloningsproxies binnen de standaard asynchrone Q-learning-updateregel. Voor de Markov-setting met single-trajectum stellen de auteurs een sub-steekproefstrategie voor (het gebruik van elke $\tau$-de steekproef, waarbij $\tau$ gerelateerd is aan de mengtijd) om tijdsafhankelijkheden te ontkoppelen, waardoor het probleem effectief wordt gereduceerd tot een analyse die lijkt op die voor i.i.d.-data.

Belangrijkste Bijdragen

1. Nieuw Algoritme: Het artikel introduceert Robust Async-Q en zijn beloningsagnostische variant Robust Async-RAQ. Dit zijn de eerste algoritmen die garanties voor robuustheid in eindige tijd bieden voor asynchrone Q-learning onder adversariale corruptie en ruis met zware staarten.
2. Bovenkanten voor Eindige Tijd:
   • Onder i.i.d.-steekproefneming bewijzen de auteurs dat het algoritme convergeert naar $Q^*$ met een snelheid van $\tilde{O}(1/\sqrt{T})$, wat overeenkomt met de optimale snelheid voor standaard Q-learning, tot op een additieve term die schaalt met $\sqrt{\epsilon}$.
   • Onder Markov-steekproefneming (single-trajectum) worden de grenzen behouden tot op een inflatiefactor gerelateerd aan de mengtijd van de onderliggende keten, consistent met resultaten voor niet-robuste asynchrone Q-learning.
3. Informatietheoretische Ondergrens: De auteurs stellen een fundamentele ondergrens van $\Omega(\sqrt{\epsilon})$ vast voor de schattingsfout van $Q^*$. Dit bewijst dat de additieve corruptieterm in hun bovengrens onvermijdelijk is, zelfs in een synchrone setting waarbij alle staat-actie-paren gelijktijdig worden waargenomen.
4. Nieuwe Bewijstechnieken:
   • Gefijnde Azuma-Hoeffding Ongelijkheid: Een kritische technische bijdrage is de toepassing van een verfijnde variant van de Azuma-Hoeffding-ongelijkheid (Shamir & Spencer, 1987). Dit instrument is noodzakelijk omdat de martingaalverschillen in de beloningsagnostische setting een grove deterministische grens toestaan (die schaalt met de tijd) maar een fijnere grens met hoge waarschijnlijkheid. Standaard concentratieongelijkheden leveren in deze context geen niet-vacuue resultaten op.
   • Koppeling voor Markov-Data: De analyse wordt uitgebreid naar single-trajectum data met behulp van een koppeltechniek om de gesubsteekproefde Markov-keten te relateren aan een i.i.d.-reeks.

Resultaten

• Convergentiesnelheden: De voorgestelde algoritmen bereiken bijna-optimale snelheden voor eindige tijd. Specifiek is de foutgrens van de vorm:
  $$\|Q_T - Q^*\|_\infty \leq \tilde{O}\left(\frac{1}{\sqrt{T}}\right) + O(\sqrt{\epsilon})$$
  De term $O(\sqrt{\epsilon})$ hangt af van de corruptiefraction en de ruisvariantie, maar is onafhankelijk van de grootte van de adversariale aanvallen.
• Robuustheid tegen Zware Staarten: De algoritmen functioneren correct zelfs wanneer de ware beloningsverdelingen zware staarten hebben (alleen een eindige tweede moment), een setting waar standaard Q-learning vaak faalt of sub-Gaussische aannames vereist.
• Agnostische Prestaties: De beloningsagnostische variant (Robust Async-RAQ) bereikt dezelfde snelheden als de variant met bekende statistieken, met slechts een lichte polynoominflatie in de afhankelijkheid van de onbekende schaalparameter.
• Simulaties: Empirische resultaten op Grid-world, FrozenLake, CliffWalking en Taxi-omgevingen tonen aan dat standaard Q-learning aanzienlijke fouten lijdt onder corruptie, terwijl de voorgestelde robuuste varianten convergeren naar een omgeving van de optimale waardefunctie.

Betekenis en Claims

Het artikel claimt de eerste principiële en uitgebreide studie te bieden van adversariale robuustheid in de oneindige-horizon, afgekapte RL-setting met asynchrone, Markov-gegevens.

• Theoretische Volledigheid: Door overeenkomende boven- en ondergrenzen te bieden (tot op de corruptieterm), schetst het werk een "vrij volledig beeld" van de fundamentele grenzen van leren in dergelijke adversariale omgevingen.
• Overbrugging van Gaten: Het overbrugt de kloof tussen robuuste statistiek (specifiek het Huber-model en gereduceerde gemiddelden) en de niet-asymptotische analyse van asynchrone stochastische approximatie.
• Praktische Relevantie: Het werk adresseert real-world zorgen waarbij feedbackdata (beloningen) ruisig, bevooroordeeld of kwaadwillig verontreinigd kan zijn, zoals bij menselijke feedback voor grote taalmodellen of sensordata in autonome systemen.
• Methodologische Vooruitgang: De introductie van de gefijnde Azuma-Hoeffding-ongelijkheid voor het hanteren van "grove deterministische maar fijne probabilistische" grenzen wordt geïsoleerd als een instrument met potentieel bredere toepasbaarheid in de studie van RL-algoritmen buiten dit specifieke probleem.

De auteurs merken op dat hoewel hun werk sterke theoretische garanties vaststelt, toekomstige richtingen onder meer het uitbreiden van het kader naar corrupties in de volledige feedbackstroom (transities en beloningen) en naar settings met functiebenadering omvatten.