Technische Samenvatting: Het Temmen van de Vloek van Multi-Agents in Robuuste Markov-spellen met Grote Toestandsruimtes via Lineaire Functieapproximatie

1. Probleemformulering

Dit werk adresseert de uitdaging van Distributioneel Robuust Multi-Agent Reinforcement Learning (MARL) in omgevingen met grote of oneindige toestandsruimtes. De auteurs richten zich op Robuuste Lineaire Markov-spellen (R-LMG's), die twee kritieke moeilijkheden combineren:

1. Robuustheid: Agenten moeten optimaliseren voor de slechtst mogelijke prestatie wanneer de omgeving afwijkt van een nominaal model binnen een voorgeschreven onzekerheidsset (specifiek gedefinieerd door de Totale Variatie-afstand).
2. Schaalbaarheid (De Vloek van Multi-Agents): In standaard MARL groeit de gezamenlijke actieruimte exponentieel met het aantal agenten ($n$), wat leidt tot een steekproefcomplexiteit die exponentieel schaalt in $n$. Dit wordt verergerd wanneer toestandsruimtes groot of oneindig zijn, waardoor tabulaire methoden onuitvoerbaar worden.

Hoewel bestaande, bewezen efficiënte algoritmen voor Robuuste Markov-spellen (RMG's) beperkt zijn tot tabulaire settings (eindige toestands-/actieruimtes), en het enige eerdere werk over lineaire functieapproximatie (LFA) voor RMG's berust op restrictieve aannames (verdwijnende minimale waarde) en nog steeds lijdt onder de vloek van multi-agents, stelt dit artikel de vraag: Kan de vloek van multi-agents getemd worden in robuuste Markov-spellen met grootschalige toestandsruimtes?

2. Methodologie

Het artikel stelt bewezen data-efficiënte algoritmen voor R-LMG's voor onder twee verschillende dataverzamelingsmechanismen: een Generatief Model-setting en een nieuw voorgestelde Online Interactieve setting. Beide settings maken gebruik van Onafhankelijke Per-Agent Lineaire Functieapproximatie (LFA), waarbij de overgangs- en beloningsfuncties voor elke agent worden gemodelleerd als lineaire functies van een feature-vector $\phi(s, a_i)$, onafhankelijk van de acties van andere agenten.

2.1 Generatief Model Setting

In deze setting heeft het algoritme toegang tot een simulator die steekproeven kan genereren uit de nominale overgangskern $P^0$ voor elk toestands-actiepaar.

• Algoritme: L-Robust-Q-FTRL.
• Kerninnovatie (Reductie van Oneindig naar Eindig): In tegenstelling tot tabulaire methoden die exhaustieve steekproeven vereisen, construeren de auteurs een eindige ondersteuningsset van toestands-actieparen ($Y_i$) met behulp van een verdeling $\rho_i$ afgeleid uit Lemma 1 (gebaseerd op de geometrie van de feature-ruimte). Dit maakt het mogelijk om alleen te steekproeven uit een eindige deelverzameling van grootte $O(d^2)$, terwijl de dekking van de gehele (potentieel oneindige) toestandsruimte via ridge-regressie wordt gegarandeerd.
• Mechanisme: Het algoritme voert een achterwaartse recursie uit. In elke iteratie steekproeft het uit de geconstrueerde eindige set, schat het het nominale model (beloningen en overgangen) via ridge-regressie, en update het de robuuste Q-functie met behulp van de duale vorm van de robuuste Bellman-vergelijking. Het hanteert een Follow-the-Regularized-Leader (FTRL)-strategie om beleidsplannen te updaten.

2.2 Online Interactieve Setting

Deze setting is praktischer, waarbij agenten interageren met de omgeving om trajecten te verzamelen. Een belangrijke uitdaging is dat de ware slechtst mogelijke overgangskern onbekend is, en dat de kernen van de onzekerheidsset niet noodzakelijkerwijs voldoen aan de lineaire structuur die wordt aangenomen voor de nominale kern.

• Algoritme: Online-L-Robust-Q-FTRL.
• Kerninnovatie (Hybride Steekproeven & Pessimistische Schattingen):
  • Benaderen van de Adversaris: Omdat de grond-waarheid slechtst mogelijke kern onbekend is, kan het algoritme niet direct daaruit steekproeven. In plaats daarvan introduceert het een reeks pessimistische robuuste waardeschattingen. Deze schattingen worden gebruikt om een "benaderende adversariele omgeving" (Definitie 1) binnen de onzekerheidsset te bevragen.
  • Hybride Steekproefstrategie: Om de geldigheid van de lineaire modelschatting te behouden (die alleen van toepassing is op de nominale kern), gebruikt het algoritme een hybride steekproefschema. Voor de eerste $h-1$ stappen van een traject interageren agenten met de benaderende adversariele omgeving (met behulp van de pessimistische schattingen). Bij de laatste stap $h$ schakelen ze over naar het steekproeven uit de nominale kern. Dit behoudt de toestands-actie bezettingsverdeling die wordt geïnduceerd door de slechtst mogelijke dynamica tot stap $h-1$, terwijl ervoor wordt gezorgd dat de laatste overgangsdata afkomstig is uit het lineair benaderbare nominale model.
  • Duale Schattingen: Het algoritme onderhoudt zowel optimistische waardeschattingen (voor beleidsupdates) als pessimistische waardeschattingen (voor het leiden van de adversariele steekproeven), een afwijking van standaard lineaire MG's die doorgaans alleen vertrouwen op optimisme.

3. Kernbijdragen

1. Het Breken van de Vloek van Multi-Agents in Grote Toestandsruimtes: Het artikel levert de eerste bewezen steekproef-efficiënte algoritmen voor R-LMG's met grote (mogelijk oneindige) toestandsruimtes die de vloek van multi-agents doorbreken. De steekproefcomplexiteit en regret-grenzen hangen polynomiëel af van de feature-dimensie $d$ en de maximale individuele actieruimte-grootte $\max_i A_i$, in plaats van de gezamenlijke actieruimte $\prod A_i$.
2. Garanties voor Generatief Model: Onder de setting van het generatieve model bereikt het voorgestelde algoritme een $\epsilon$-benaderende Coarse Correlated Equilibrium (CCE) met een steekproefcomplexiteit van $\tilde{O}(H^9 d^3 / \epsilon^4)$. Dit is de eerste dergelijke garantie voor R-LMG's onder een generatief model, ongeacht de formulering van de onzekerheidsset.
3. Online Interactief Protocol: De auteurs stellen een praktisch betekenisvol online protocol voor waarbij agenten kunnen steekproeven uit overgangskernen binnen de onzekerheidsset (benaderende adversariele omgevingen). Zij bewijzen dat hun algoritme een sublineaire regret van $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$ bereikt.
4. Technische Nieuwheid:
   • Reductie van Oneindig naar Eindig: Een methode om een eindige deelverzameling te steekproeven om te generaliseren naar oneindige toestandsruimtes in robuuste settings.
   • Hybride Steekproeven: Een nieuw mechanisme om het nominale model te schatten terwijl de bezettingsverdeling van de adversariele omgeving wordt behouden, waardoor de niet-lineariteit van de onzekerheidsset wordt overwonnen.
   • Pessimistisch-Optimistische Dualiteit: De introductie van pessimistische waardeschattingen om de adversariele omgeving te benaderen bij gebrek aan grond-waarheid robuuste waarden.

4. Resultaten en Theoretische Garanties

• Generatief Model (Stelling 2): Het algoritme output een $\epsilon$-robuuste CCE met waarschijnlijkheid $1-\delta$ met behulp van $N_{all} \ge O(H^9 d^3 / \epsilon^4)$ steekproeven. In de tabulaire reductie ($d = S \max A_i$) levert dit een complexiteit op van $\tilde{O}(H^9 S^3 (\max A_i)^3 / \epsilon^4)$, wat polynomiëel is in alle parameters, in contrast met de exponentiële afhankelijkheid in eerdere tabulaire robuuste methoden.
• Online Setting (Stelling 3): Het algoritme bereikt een regret-grens van $\tilde{O}(H^2 d \max_i A_i \sqrt{T})$. Als het aantal episodes $T$ voldoet aan $T > H^4 d^2 (\max_i A_i)^2 / \epsilon^2$, is de output een $\epsilon$-robuuste CCE.
• Vergelijking: De resultaten verbeteren aanzienlijk het enige bestaande werk over lineaire RMG's (Zheng en Lin, 2025), dat een restrictieve "verdwijnende minimale waarde"-aanname vereiste en leed onder de vloek van multi-agents ($d_{curse} = S \prod A_i$). De voorgestelde methode verwijdert deze restricties en bereikt een polynomiële afhankelijkheid van het aantal agenten.

5. Betekenis en Claims

De auteurs claimen dat dit werk de eerste bewezen steekproef-efficiënte algoritmen biedt voor robuuste lineaire Markov-spellen met grote (mogelijk oneindige) toestandsruimtes die de vloek van multi-agents succesvol overwinnen.

• Robuustheid: Het werk breidt het toepassingsgebied van robuust MARL uit van kleine, tabulaire domeinen naar grootschalige, continue omgevingen die relevant zijn voor real-world toepassingen zoals autonoom rijden, robotica en financiële markten.
• Data-efficiëntie: Door de exponentiële afhankelijkheid van het aantal agenten te doorbreken, maken de algoritmen robuust leren haalbaar in multi-agent systemen waar de gezamenlijke actieruimte anders onhandelbaar zou zijn.
• Praktijkgerichtheid: De voorgestelde online interactieve setting, die het mogelijk maakt om te steekproeven uit benaderende adversariele omgevingen, sluit aan bij praktische paradigma's die worden gebruikt in veiligheidskritieke toepassingen (bijv. sim-naar-real transfer, adversariele training) en zorgt ervoor dat het probleem goed gesteld blijft voor het bereiken van sublineaire regret.

Het artikel concludeert dat de voorgestelde hybride steekproefstrategie en het gebruik van pessimistische waardeschattingen belangrijke technische bijdragen zijn die van onafhankelijk belang kunnen zijn voor toekomstig onderzoek in robuust reinforcement learning.