⚡ electrical engineering

Robust Asynchronous Q-Learning under Reward and State Corruption via Batching

Dit artikel introduceert BR-Async-Q, een nieuw epoch-gebaseerd robuust Q-leeralgoritme dat effectief omgaat met adversariële corruptie van zowel beloningen als toestanden door gegevens te batchen en robuuste Bellman-operator-schattingen te construeren, waarbij het foutmargen met een hoge waarschijnlijkheid bereikt die overeenkomen met die van vanilla Q-learning tot op een term die schaalt met de corruptiefractie.

Oorspronkelijke auteurs: Sreejeet Maity, Aritra Mitra

Gepubliceerd 2026-07-27

📖 9 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sreejeet Maity, Aritra Mitra

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot leert om door een doolhof te navigeren om de beste schat te vinden. In de perfecte wereld van sciencefiction ziet de robot elke bocht duidelijk, hoort hij elke instructie perfect en leert hij direct van elke fout. Maar in de echte wereld is het rommelig. Sensoren haperen, signalen worden verstoord en soms probeert zelfs een ondeugende hacker de robot te misleiden door hem valse muren te laten zien of te liegen over de locatie van de schat. Dit is de wereld van Reinforcement Learning (RL). Het is een methode waarbij een agent (zoals een robot of een softwareprogramma) leert beslissingen te nemen door dingen uit te proberen en feedback te krijgen. Het doel is om het beste pad te vinden om beloningen te maximaliseren, zoals het winnen van een spel of het veilig besturen van een auto. Echter, als de feedback die de agent ontvangt gecorrumpeerd is — vol ruis, fouten of zelfs bewuste leugens — kan de agent in de war raken, de verkeerde lessen leren en uiteindelijk vreselijke beslissingen nemen. De grote vraag waar wetenschappers aan stellen is: Kunnen we een leersysteem bouoven dat robuust genoeg is om de leugens te negeren en toch de waarheid te achterhalen, zelfs wanneer de data een puinhoop is?

Dit artikel, getiteld "Robust Asynchronous Q-Learning under Reward and State Corruption via Batching", pakt precies dat probleem aan. De auteurs, Sreejeet Maity en Aritra Mitra, maken zich zorgen over een scenario waarin een tegenstander (een kwaadwillende actor) zowel de "beloning" (de score die de robot krijgt) als de "toestand" (het zicht van de robot op de wereld) tegelijkertijd kan verstoren. Ze stellen een nieuw algoritme voor genaamd BR-Async-Q. Zie dit als een nieuwe manier voor de robot om te leren die niet in paniek raakt wanneer hij een leugen ziet. In plaats van zijn brein bij te werken na elke individuele stap — wat het kwetsbaar maakt voor één enkel slecht stukje data — wachten ze eerst en verzamelen ze een hele "batch" aan ervaringen. Vervolgens gebruiken ze een slim statistisch trucje om de leugens te filteren en de gemiddelde waarheid te vinden voordat ze een enkele, sterke update maken. Ze bewijzen wiskundig dat deze methode werkt, waarbij ze laten zien dat de robot zelfs met een bepaald percentage gecorrumpeerde data nog steeds een bijna perfecte strategie kan aanleren. Hun simulaties bevestigen dat terwijl standaard leermethoden onder deze aanvallen instorten, hun nieuwe methode de robot op koers houdt en convergeert naar het juiste antwoord met slechts een kleine, voorspelbare fout veroorzaakt door de resterende leugens.

Het Probleem: Een Robot in een Spiegelpaleis

Om te begrijpen wat de auteurs hebben gedaan, laten we onze robot-leeragent voorstellen als een student die een toets maakt. In een normale Reinforcement Learning-opstelling neemt de student een stap, krijgt een cijfer (beloning) en ziet de volgende vraag (toestand). Ze gebruiken dit om hun studiegids (de "Q-tabel") onmiddellijk bij te werken.

Maar stel je voor dat er een sluwe surveillant (de tegenstander) meekijkt. Af en toe wisselt de surveillant het echte cijfer van de student in voor een vals cijfer, of verandert de volgende vraag op de pagina in iets totaal anders. Dit is wat het artikel Huber-contaminatie noemt. De surveillant hoeft niet de hele tijd te liegen; slechts een klein percentage leugens (bijvoorbeeld 1% of 5%) is al genoeg om de student van koers te brengen. Als de student zijn studiegids na elke vraag bijwerkt, kan één vals cijfer hem doen denken dat het foute antwoord juist is. Na verloop van tijd stapelen deze kleine fouten zich op, en eindigt de student met een volkomen verkeerde gids.

De situatie wordt nog ingewikkelder omdat de student "asynchroon" leert. Dit betekent dat ze niet alle mogbare vragen en antwoorden in één keer te zien krijgen. Ze dwalen door het doolhof, en sommige paden worden vaak bezocht, terwijl andere zeldzaam zijn. Als de surveillant die zeldzame paden target, merkt de student misschien nooit dat hij is voorgelogen, omdat hij niet genoeg data heeft om het patroon te herkennen.

De Oplossing: De "Batch and Trim" Strategie

De oplossing van de auteurs, BR-Async-Q, verandert het ritme van het leren. In plaats van te reageren op elk stukje feedback, pauzeert de robot en groepeert zijn ervaringen in blokken die epochs of batches worden genoemd.

Stel je voor dat de robot schelpen verzamelt op een strand. Een standaard robot raapt een schelp op, bekijkt hem, en besluit onmiddellijk of het een schat of een steen is. Als er een nepschelp aan hem wordt gegeven (een stuk plastic dat is geschilderd om op goud te lijken), kan de robot erdoor misleid worden.

De BR-Async-Q robot vult echter eerst een emmer met 1.000 schelpen. Zod even de emmer vol is, stort hij ze uit en bekijkt hij de hele stapel. Hij weet dat de surveillant een paar plastic schelpen heeft binnengesmokkeld, maar hij weet ook dat de plastic schelpen waarschijnlijk uitschieters zijn — ofwel te glimmend of te vreemd. Daarom gebruikt de robot een speciaal hulpmiddel genaamd een getrimd gemiddelde (trimmed mean). Hij negeert de meest extreme schelpen (de schelpen die er verdacht nep of onmogelijk perfect uitzien) en berekent de gemiddelde waarde van de overige, normaal ogende schelpen.

Dit "trimmen" is het geheime ingrediënt. Door te wachten tot hij een grote batch aan data heeft, kan de robot het signaal (de waarheid) statistisch scheiden van de ruis (de leugens). Het artikel bewijst dat de robot door dit te doen de werkelijke waarde van zijn acties met hoge precisie kan inschatten, zelfs als een deel van de data gecorrumpeerd is.

Waarom Batching Belangrijk Is: De Variantie-val

De auteurs wijzen op een cruciaal gebrek in eerdere methoden. Oude robuuste algoritmen probeerden sterk te zijn door bij elke stap te updaten, maar gebruikten complexe wiskunde om de waarheid te raden. Het probleem was dat deze updates een hoge variantie hadden. In eenvoudige termen is "variantie" hoe erg de gok van de robot heen en weer springt. Als de robot te vaak updat met ruisachtige data, trilt zijn brein constant, waardoor het voor de surveillant makkelijk is om hem van koers te duwen.

Door de data in batches te verwerken, vermindert BR-Async-Q deze trilling. Het is als het maken van een foto met een lange sluitertijd. Als je een foto maakt van een rijdende auto met een snelle sluitertijd, krijg je een wazig, trillerig beeld. Maar als je wacht en een lange belichting gebruikt, vervaagt de beweging en krijg je een helder, stabiel beeld. De auteurs laten zien dat deze "variantievermindering" ervoor zorgt dat hun algoritme de prestaties van standaard leren (wanneer er geen leugens zijn) kan evenaren, terwijl het immuun is voor de leugens.

De Resultaten: De Leugens Verslaan

Het artikel biedt een wiskundige garantie, wat een chique manier is om te zeggen dat ze met logica hebben bewezen dat de robot zal slagen. Ze toonden aan dat de fout (het verschil tussen wat de robot leert en de perfecte strategie) uit twee delen bestaat:

De Natuurlijke Fout: Dit is de normale fout die je verwacht simpelweg omdat de robot nog niet genoeg data heeft gezien. Dit deel wordt kleiner naarmate de robot meer leert.
De Corruptie-bias: Dit is de extra fout veroorzaakt door de leugens van de surveillant.

Het verbazingwekkende is dat de "Corruptie-bias" in hun nieuwe methode zeer klein is. Het schaalt direct met de hoeveelheid liegen (de corruptiekans), maar wordt niet opgeblazen door de verwarring van de robot. Sterker nog, wanneer alleen de beloningen gecorrumpeerd zijn (en de toestanden schoon zijn), is hun methode minimax optimaal. Dit is een technische manier om te zeggen: "Je kunt het niet beter doen dan dit." Ze bereiken de theoretische limiet van hoe goed een algoritme onder deze omstandigheden zou kunnen presteren.

De auteurs hebben ook simulaties uitgevoerd om te zien hoe dit in de praktijk werkt. Ze creëerden een grid-world omgeving (een simpel doolhof) met 100 toestanden en 40 acties. Ze testten hun algoritme tegen een standaard algoritme terwijl ze verschillende niveaus van corruptie introduceerden.

De Standaard Robot: Wanneer de surveillant begon te liegen, stortte de prestatie van de standaard robot in. Zijn fout werd enorm groot en hij slaagde er niet in om het beste pad te vinden.
De BR-Async-Q Robot: Zelfs toen 20% van de data gecorrumpeerd was (een enorme hoeveelheid liegen), bleef deze robot kalm. Hij convergeerde naar een oplossing die heel dicht bij de perfecte oplossing lag, met slechts een kleine, stabiele fout.

Ze testten ook wat er gebeurt als de robot sommige paden zeer zelden bezoekt. Eerdere methoden worstelden hierbij, omdat ze dachten dat zeldzame paden kwetsbaarder waren voor leugens. Maar omdat BR-Async-Q wacht op een volledige batch aan data, zorgt het ervoor dat zelfs zeldzame paden voldoende aandacht krijgen om de leugens te filteren, waardoor de "versterking" van fouten die oudere methoden teisterde, wordt vermeden.

De Kernboodschap

Uiteindelijk biedt dit artikel een nieuw speelboek voor het onderwijzen van machines in een rommelige, onbetrouwbare wereld. Het suggereert dat geduld een deugd is. Door te vertragen, meer data te verzamelen en slimme statistiek te gebruiken om de ruis te filteren, kunnen we AI-systemen bouwen die niet alleen overleven onder corruptie, maar er juist in floreren. De auteurs hebben niet alleen gegokt dat dit zou werken; ze hebben het wiskundig bewezen en in simulaties aangetoond. Hoewel de huidige methode veel data in het geheugen vereist om op te slaan (zoals het vullen van die grote emmer met schelpen), opent het kernidee — dat batching en robuuste schatting de tegenstander kunnen verslaan — de deur naar veiligere, betrouwbaardere AI in alles van zelfrijdende auto's tot medische diagnoses, waar de prijs van een leugen te hoog is om te negeren.

Technische Samenvatting: Robuuste Asynchrone Q-learning onder Belonings- en Toestandsverontreiniging via Batching

1. Probleemformulering

Het artikel behandelt de uitdaging van het leren van een optimale policy in een gedisconteerde oneindige-horizon Markov Beslissingsproces (MDP) wanneer de feedback van de leerling onderhevig is aan adversariële verontreiniging. De setting betreft een agent die interageert met een omgeving via een gedragspolicy $\mu$ , waarbij staat-actie paren $(s_t, a_t)$ , volgende toestanden $s_{t+1}$ , en beloningen $r_t$ worden waargenomen.

De kern van de moeilijkheid komt voort uit het Huber-verontreinigingsmodel, waarbij een tegenstander zowel de waargenomen beloning als de waargenomen volgende toestand op elke tijdstap willekeurig kan verstoren met een kleine waarschijnlijkheid $\epsilon \in [0, 1/2)$ . Specifiek:

Beloningsverontreiniging: Met een waarschijnlijkheid $\epsilon_R$ wordt de waargenomen beloning $\tilde{r}_t$ vervangen door een willekeurige waarde $z_t$ (potentieel onbegrensd).
Toestandsverontreiniging: Met een waarschijnlijkheid $\epsilon_Y$ wordt de waargenomen volgende toestand $\tilde{s}_{t+1}$ vervangen door een willekeurige toestand $u_t$ .
Heavy-Tailed Beloningen: In tegen tegenstelling tot eerder werk dat sub-Gaussische beloningen vereist, gaat dit framework ervan uit dat de schone beloningsverdelingen slechts een eindige tweede moment hebben, wat ruimte biedt voor heavy-tailed ruis.

Het doel is om een robuuste schatting $\hat{Q}$ te construeren van de optimale staat-actiewaarde functie $Q^*$ en een $\ell_\infty$ -foutberekening met hoge waarschijnlijkheid $\|\hat{Q} - Q^*\|_\infty$ af te leiden die standhoudt ondanks deze gezamenlijke verontreinigingen.

2. Methodologie: BR-Async-Q

De auteurs stellen BR-Async-Q (Batch Robust Asynchronous Q-Learning) voor, een nieuw epoch-gebaseerd algoritme dat is ontworpen om de variantie en bias geïntroduceerd door adversariële feedback te mitigeren. De aanpak wijkt af van standaard Q-learning, dat de Q-tabel bij elke tijdstap bijwerkt, door twee belangrijke mechanismen te introduceren:

A. Online Batching (Epochs)

De interactiehorizon $T$ wordt verdeeld in $K$ epochs (batches), elk met een lengte $H$ . Binnen een epoch $k$ verzamelt het algoritme data, maar werkt het de Q-tabel niet bij. In plaats daarvan aggregeert het observaties voor elk staat-actie paar $(s, a)$ in twee datasets:

$D_k(s, a)$ : De verzameling waargenomen (potentieel verontreinigde) beloningen.
$Y_k(s, a)$ : De verzameling gebootstrapt waarden $\max_{a'} Q_k(\tilde{s}_{t+1}, a')$ gebaseerd op de bevroren Q-tabel aan het begin van de epoch.

B. Robuuste Schatting van de Bellman-operator

Aan het einde van elke epoch berekent het algoritme een robuuste schatting van de Bellman-optimaliteitsoperator $\mathcal{T}$ met behulp van de geaggregeerde batchdata. Dit omvat:

Robuuste Gemiddelde Schatting:
- Voor beloningen ( $D_k$ ) wordt een trimmed mean estimator ( $\text{TRIM}_H$ ) gebruikt om het schone gemiddelde van de beloning $R(s, a)$ te schatten. Dit vangt de heavy-tailed natuur en willekeurige verontreiniging op.
- Voor gebootstrapt waarden ( $Y_k$ ) wordt een clipped mean estimator ( $\text{TRIM}_B$ ) gebruikt. Cruciaal is dat deze estimator bekende grenzen op de Q-waarden gebruikt (afgeleid van de clipping-drempel) om een nauwere afhankelijkheid van de verontreinigingsfractie $\epsilon_Y$ te bereiken.
Clipping voor Stabiliteit: Om te voorkomen dat zeldzame mislukkingen van de robuuste estimators de Q-tabel destabiliseren, wordt de geschatte beloning afgeklemd naar een drempelwaarde $G_k$ die is afgeleid van theoretische grenzen. Dit zorgt ervoor dat de Q-iteraties uniform begrensd blijven.
Synchrone Update: De Q-tabel wordt slechts één keer per epoch bijgewerkt met behulp van de robuust geschatte operator, wat effectief de variantie van de update-richting vermindert vergeleken met single-sample updates.

3. Belangrijkste Bijdragen

Algoritmische Bijdrage

Het artikel introduceert het eerste robuuste Q-learning algoritme dat in staat is om gezamenlijke staat- en beloningsverontreiniging aan te pakken in een asynchrone online setting. Door data in batches te verdelen en robuuste statistische estimators te gebruiken, overwint BR-Async-Q de beperkingen van standaard Q-learning en eerdere robuuste varianten die bij elke stap een update uitvoeren.

Theoretische Bijdrage

De auteurs bewijzen een high-probability finite-time $\ell_\infty$ -foutberekening voor BR-Async-Q (Theorem 2). De berekening bestaat uit twee componenten:

Statistische Fout: Een dominante term die schaalt als $\tilde{O}\left(\frac{\tilde{\sigma}}{(1-\gamma)^{5/2}\sqrt{\lambda_{\min} T}}\right)$ . Opvallend is dat de afhankelijkheid van de minimale visitatiekans $\lambda_{\min}$ is verbeterd ten opzichte van eerder werk [9], en schaalt als $1/\sqrt{\lambda_{\min} T}$ in plaats van $1/(\lambda_{\min}\sqrt{T})$ .
Verontreinigings-geïnduceerde Bias: Een additieve bias-term $\psi$ $ψ$ die schaalt met de verontreinigingskansen:
$\psi = O\left(\frac{\tilde{\sigma}\epsilon_Y}{(1-\gamma)^2}\right) \vee O\left(\frac{\bar{\sigma}\sqrt{\epsilon_R}}{1-\gamma}\right)$
- Wanneer alleen beloningen verontreinigd zijn ( $\epsilon_Y = 0$ ), schaalt de bias-term als $O(\sqrt{\epsilon_R})$ , wat overeenkomt met de fundamentele minimax lower bound die in eerder werk [6] is vastgesteld.
- Dit resultaat sluit de kloof tussen de upper en lower bounds gevonden in de eerdere literatuur, en demonstreert dat de inverse afhankelijkheid van de visitatiekans gezien in eerdere upper bounds vermijdbaar is via variantiereductie.

4. Resultaten en Betekenis

Simulatie-resultaten

Het artikel valideert BR-Async-Q op een grid-world omgeving ( $|S|=100, |A|=40$ ).

Robuustheid: Vanilla Q-learning faalt onder zelfs kleine verontreinigingsniveaus ( $\epsilon \in \{0.001, 0.005, 0.01\}$ ) of heavy-tailed ruis, terwijl BR-Async-Q convergeert naar een buurt van $Q^*$ .
Asymmetrische Verontreiniging: Het algoritme blijft stabiel, zelfs wanneer de staat- en beloningsverontreinigingspercentages verschillen ( $\epsilon_Y \neq \epsilon_R$ ).
Epoch Lengte: De prestaties blijken robuust over verschillende epoch-lengtes $H$ , mits $H$ voldoende groot is om aan de visitatiekans-vereisten te voldoen.

Betekenis en Claims

Het artikel claimt de eerste bewijsbare robuustheidsgarantie te bieden voor asynchrone Q-learning onder de gezamenlijke verontreiniging van staten en beloningen.

Gap Closure: Het lost een fundamentele kloof op in het begrip van de sample complexiteit van robuuste RL onder beloning-alleen verontreiniging, door aan te tonen dat de suboptimale afhankelijkheid van visitatiekansen in eerdere upper bounds een artefact is van het algoritmeontwerp, en niet van het probleem zelf.
Minimax Optimaliteit: Onder beloning-alleen verontreiniging bereikt het algoritme een bias-term die minimax optimaal is, waarbij exact overeenkomt met de informatie-theoretische lower bound.
Praktische Bruikbaarheid: De methode toont aan dat betrouwbaar leren mogelijk is, zelfs in harde omgevingen met sensorfouten, logging-fouten of bewuste vergiftiging (poisoning), mits de verontreinigingskans klein is en het algoritme gebruikmaakt van batching om variantie te verminderen.

De auteurs merken op dat de huidige implementatie een geheugen vereist dat lineair is in de epoch-lengte $H$ en suggereren toekomstig werk op het gebied van online robuuste gemiddelde estimators en extensies naar functie-approximatie.