💻 computer science

Distributionally Robust Markov Games with Average Reward

Dit artikel stelt het theoretische bestaan vast van stationaire Nash-evenwichten voor distributierobuste Markov-spellen onder zowel irreducibele als zwak communicerende instellingen met gemiddelde beloningscriteria, terwijl het convergerende algoritmen voorstelt en hun benadering via gedisconteerde tegenhangers demonstreert.

Oorspronkelijke auteurs: Zachary Roch, Yue Wang

Gepubliceerd 2026-06-23

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Zachary Roch, Yue Wang

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 een groep vrienden voor die samen een doolhof proberen te navigeren. In een perfecte wereld weten ze precies waar elke muur staat en waar elke deur naartoe leidt. Maar in de echte wereld kan de kaart die ze hebben misschien een beetje fout zijn. Misschien is een muur verschoven, of zit een deur vast. Dit is het probleem van model mismatch: het plan dat ze hebben gemaakt, komt niet overeen met de werkelijkheid waarin ze zich daadwerkelijk bevinden.

Dit artikel introduceert een nieuwe manier voor deze vrienden om beslissingen te nemen die werken, zelfs wanneer hun kaart fout is en wanneer ze heel lang spelen (niet alleen een korte race).

Hier is de uitleg van hun oplossing met behulp van eenvoudige analogieën:

1. Het Probleem: "Wat als de kaart fout is?"

Meestal, wanneer mensen computers leren om spelletjes te spelen of beslissingen te nemen (zoals robots in een magazijn of auto's op een snelweg), gaan ze ervan uit dat de regels vaststaan. Maar in de werkelijkheid veranderen de dingen.

De Oude Manier: De meeste eerdere methoden richtten zich op kortetermijndoelen (zoals "bereik de uitgang in 10 stappen") of gebruikten een "korting" (waarbij een beloning vandaag meer waarde heeft dan een beloning morgen). Dit is als een sprinter die een korte race loopt; hij geeft niet om de slijtage aan zijn schoenen op de lange termijn.
De Nieuwe Uitdaging: De auteurs wilden het Average Reward-probleem oplossen. Dit is als een marathonloper die een constant, duurzaam tempo moet aanhouden. Hij geeft om de gemiddelde snelheid over de hele race, niet alleen over de eerste mijl.
De Twist: Ze wilden ook Distributionally Robust zijn. Dit betekent dat de spelers uitgaan van het "worst-case scenario" voor de kaart. Ze hopen niet alleen dat de kaart klopt; ze plannen alsof een ondeugende "gremlin" constant probeert de muren te veranderen om hun leven zo moeilijk mogelijk te maken.

2. De Grote Hindernis: "Het doolhof is te ingewikkeld"

De auteurs leggen uit dat het combineren van "lange-termijn gemiddelde doelen" met "planning voor het slechtste scenario" ongelooflijk moeilijk is.

De Analogie: Stel je voor dat je probeert het beste pad te vinden in een doolhof waar de muren elke keer dat je een stap zet veranderen, en je moet voor eeuwig blijven lopen. In simpelere spelletjes (korte races) kun je terugwerken vanaf de finishlijn. Maar in een eindeloze marathon is er geen finishlijn om vanaf terug te werken.
De Ontdekking: Ze bewezen dat zonder bepaalde regels (zoals het feit dat het doolhof "verbonden" is, zodat je van elke kamer naar elke andere kamer kunt komen), een perfecte, stabiele strategie misschien niet eens bestaat. Het is alsof je probeert een enkele "beste zet" te vinden in een spel waarbij de regels zo wild veranderen dat geen enkele zet ooit echt veilig is.

3. De Oplossing: Het vinden van een "Stabiele Overeenstemming"

Het artikel bewijst dat als de omgeving "goed verbonden" is (je kunt uiteindelijk overal komen), er wel degelijk een Nash-evenwicht bestaat.

Wat is een Nash-evenwicht? Denk aan een "stabiele wapenstilstand". Het is een reeks strategieën waarbij geen enkele individuele speler zijn gemiddelde score kan verbeteren door zijn eigen plan te veranderen, ervan uitgaande dat iedereen zich aan zijn eigen plan houdt. Zelfs met de slechtst denkbare veranderingen in de kaart, spreken alle spelers af over een strategie die het beste is wat zij kunnen doen, gezien de chaos.
De Doorbraak: De auteurs lieten zien hoe je wiskundig kunt bewijzen dat deze overeenstemming bestaat, zelfs wanneer de "gremlin" probeert het spel te breken. Ze deden dit door een speciale vergelijking (een "Bellman-vergelijking") te creëren die de directe beloning afweegt tegen het gemiddelde op de lange termijn, rekening houdend met de slechtst mogelijke kaartveranderingen.

4. De Hulpmiddelen: Twee Nieuwe Algoritmen

Om deze "stabiele wapenstilstand" daadwerkelijk te vinden, hebben de auteurs twee nieuwe hulpmiddelen (algoritmen) gebouwd:

Hulpmiddel A: Robust Nash-Iteration (De "Iteratieve Onderhandeling")
- Hoe het werkt: Stel je de spelers voor die rond een tafel zitten. Ze wisselen beurten af door te zeggen: "Als jullie je allemaal aan jullie huidige plan houden, dan is dit de beste zet voor mij." Ze blijven hun plannen bijwerken op basis van wat anderen doen.
- Het Nadeel: Deze methode werkt perfect, maar vereist een "supercomputer" om bij elke stap een complex wiskundig puzzelstuk op te lossen. Het is alsof je een genie nodig hebt dat een Sudoku-puzzel oplost telkens wanneer je een stap zet in het doolhof.
Hulpmiddel B: Robust TD Descent (De "Gladde Klim")
- Hoe het werkt: Dit is een slimmere, meer praktische methode. In plaats van elke keer een moeilijke puzzel op te lossen, nemen de spelers kleine stapjes bergafwaarts op een "geluksheuvel". Ze meten hoe "fout" hun huidige plan is (de fout) en duwen hun strategie voorzichtig bij om deze fout te verkleinen.
- De Truc: Omdat de wiskunde grillig en hobbelig is (door de planning voor het slechtste scenario), hebben ze de heuvel eerst "gladgestreken", zoals het schuren van een ruw stuk hout. Hierdoor kunnen ze naar de beste oplossing glijden zonder vast te komen zitten op een hobbel. Deze methode is veel sneller en heeft geen supercomputer nodig.

5. De Brug: Het Verbinden van Kort en Lang

Ten slotte toonden de auteurs een slimme afkorting aan.

De Analogie: Ze bewezen dat als je het spel speelt met een "korting" (waarbij je het heden iets meer waardeert dan de toekomst), maar die kortingsfactor extreem dicht bij 1 maakt (wat betekent dat je bijna evenveel om de toekomst geeft als om het heden), je bijna hetzelfde resultaat krijgt als een perfect langetermijn-gemiddelde plan.
Waarom dit ertoe doet: Dit betekent dat we bestaande, goed begrepen tools die ontworpen zijn voor kortetermijnspellen kunnen gebruiken om de oplossing voor deze complexe, langetermijn, worst-case scenario's te benaderen. Het is alsof je een standaard kompas gebruikt om te navigeren tijdens een marathon, als je de naald maar een klein beetje aanpast.

Samenvatting

Kortom, dit artikel biedt een wiskundige garantie en een praktische toolkit voor groepen agenten (zoals robots of AI) om effectief samen te werken of te concurreren op de lange termijn, zelfs wanneer ze niet de exacte regels van het spel kennen en verwachten dat de omgeving hen probeert te misleiden. Ze bewezen dat er een stabiele oplossing bestaat en gaven twee manieren om deze te vinden: één die precies maar zwaar is, en één die praktisch en vloeiend is.

Technische Samenvatting: Distributionally Robust Markov Games met Gemiddelde Beloning

Probleemformulering

Dit artikel behandelt de uitdaging van besluitvorming door meerdere agenten in omgevingen die worden gekenmerkt door modelonzekerheid en uitgebreide operationele horizonten. Hoewel Markov Games (MG's) een kader bieden voor competitieve multi-agent systemen, schieten standaardformuleringen vaak tekort omdat ze geen rekening houden met de "Sim-to-Real"-kloof, waarbij het veronderstelde transitiemodel afwijkt van de werkelijke omgeving door niet-stationariteit, modelleringsfouten of adversariële verstoringen.

Om dit te mitigeren, bestuderen de auteurs Distributionally Robust Markov Games (DR-MG's), waarbij agenten optimaliseren voor de slechtst denkbare prestaties over een vooraf gedefinieerde onzekerheidsverzameling van transitiekernen. Cruciaal is dat dit werk zich richt op het gemiddelde beloningscriterium (average-reward criterion) in plaats van de meer algemeen bestudeerde eindige-horizon of verdisconteerde beloningsinstellingen. Het gemiddelde beloningscriterium is essentieel voor systemen die opereren over onbepaalde tijdsintervallen (bijv. robotica in magazijnen, communicatienetwerken), maar het brengt aanzienlijke theoretische hindernissen met zich mee:

Falen van Min-Max Dualiteit: In robuuste instellingen kan de slechtst denkbare transitiekern voor de ene agent verschillen van die van een andere, wat de zadelpuntstructuur doorbreekt, zelfs in zero-sum games.
Structurele Complexiteit: In tegen tegenover de verdisconteerde instellingen, verbreekt de correspondentie tussen stationaire beleidsregels en staat-actie frequenties in gemiddelde beloningsinstellingen zonder restrictieve structurele aannames.
Gebrek aan Bestaande Oplossingen: Eerdere methoden voor verdisconteerde DR-MG's of niet-robuuste gemiddelde belonings MG's kunnen niet direct worden uitgebreid naar de robuuste gemiddelde beloningsinstelling vanwege de niet-contractie van Bellman-operatoren en de niet-uniciteit van oplossingen.

Het artikel toont aan dat zonder structurele aannames, gemiddelde belonings DR-MG's mogelijk geen stationair Nash-evenwicht (NE) toelaten, zoals aangetoond door een geconstrueerd tegenvoorbeeld van een tweespeler zero-sum game.

Methodologie

1. Theoretische Fundamenten: Bestaan van Evenwicht

De auteurs stellen het bestaan van een stationair robuust Nash-evenwicht vast onder twee verschillende structurele aannames:

Irreducibele Instelling: Er wordt aangenomen dat voor elke stationaire gezamenlijke beleidsregel en elke toelaatbare kern, de geïnduceerde Markov-keten irreducibel is (alle staten behoren tot één enkele recurrente klasse).
- De auteurs leiden een correspondentie af tussen optimale beleidsregels en de oplossingen van de robuuste Bellman-vergelijking.
- Zij bewijzen dat de robuuste Bellman-vergelijking een unieke oplossing heeft (op een constante vector na) voor de gain en de bias.
- Met behulp van deze resultaten tonen zij aan dat de best-response mapping niet-leeg, convex en bovengesteld halfcontinu is. Door het Kakutani-vastpunttheorema toe te passen, bewijzen zij het bestaan van een stationair robuust NE.
Zwak Communicerende Instelling (Weakly Communicating Setting): Een algemenere instelling waarbij de toestandsruimte kan worden gedecomposeerd in transiënte staten en een unie van recurrente klassen.
- In deze instelling faalt de directe correspondentie tussen beleidsregels en Bellman-oplossingen.
- De auteurs construeren een proxy set-valued map gebaseerd op de constant-gain optimale robuuste Bellman-operator.
- Zij bewijzen dat deze proxy-map een deelverzameling is van de ware best-response mapping en voldoet aan de voorwaarden voor het Kakutani-vastpunttheorema, waarmee zij het bestaan van een stationair robuust NE aantonen, zelfs in deze bredere context.

2. Algoritmische Oplossingen

Het artikel stelt twee algoritmen voor om het robuste NE te berekenen:

Robust Nash-Iteration: Een uitbreiding van de standaard Nash waarde-iteratie. Het houdt bias-schattingen bij en lost een Nash-evenwicht op voor een stage-game die gedefinieerd wordt door robuuste Q-waarden in elke stap.
- Convergentie: Bewezen te convergeren naar een robuust NE onder de irreducibele aanname en een aanvullende aanname met betrekking tot de selectie van stage-game evenwichten (bijv. globale optimaliteit of zadelpuntselectie).
- Beperking: Vereist een oracle om het NE van de stage-game te berekenen, wat in het algemeen PPAD-compleet is in general-sum settings.
Robust TD Descent: Een two-time-scale actor-critic algoritme ontworpen om de noodzaak van een NE-oracle te omzeilen.
- Mechanisme: Het karakteriseert het robuste NE via de minimalisatie van een globale robuuste Temporal Difference (TD) gap. Het algoritme minimaliseert een gesmoothde versie van deze gap (met behulp van een Moreau-envelope) om niet-gladheid te behandelen.
- Convergentie: Er is bewezen dat het algoritme zwak convergeert naar een stationair punt van de gesmoothde doelfunctie. Hoewel het geen convergentie naar het exacte NE garandeert zonder verdere aannames (zoals lokale gradiënt-dominantie), biedt het de eerste bewijsbaar convergerende methode voor average-reward DR-MG's die niet afhankelijk is van een NE-oracle.

3. Connectie met Verdisconteerde Evenwichten

De auteurs vestigen een theoretische brug tussen average-reward en verdisconteerde DR-MG's. Zij bewijzen dat wanneer de verdisconteringsfactor $\gamma \to 1$ , het robuste NE van de verdisconteerde game convergeert naar het robuste NE van de average-reward game. Dit maakt het mogelijk om het uitdagende average-reward probleem te benaderen met de meer hanteerbare verdisconteerde formuleringen.

Belangrijkste Resultaten

Bestaan van NE: Het artikel bewijst het bestaan van een stationair robuust Nash-evenwicht voor average-reward DR-MG's onder zowel irreducibele als zwak communicerende aannames, waarmee een fundamentele vraag over oplosbaarheid wordt beantwoord die in eerdere literatuur open bleef.
Oplosbaarheid van Robuuste Bellman-vergelijkingen: De auteurs bieden fundamentele resultaten over de oplosbaarheid en uniciteit (op constanten na) van de robuuste Bellman-vergelijking voor average-reward MDP's, waarmee zij eerdere hiaten in de literatuur corrigeren.
Convergerende Algoritmen: Twee algoritmen worden geïntroduceerd. De Robust Nash-Iteration biedt convergentie onder specifieke structurele aannames, terwijl de Robust TD Descent een praktische, oracle-vrije aanpak biedt met bewezen convergentie naar stationaire punten.
Benadering via Verdiscontering: Het artikel valideert dat average-reward evenwichten effectief benaderd kunnen worden door verdisconteerde evenwichten met voldoende grote verdisconteringsfactoren, wat een praktische computationele route biedt.

Betekenis en Claims

Het artikel claimt een omvattend theoretisch en algoritmisch fundament te bieden voor besluitvorming in complexe, onzekere en langlopende multi-player omgevingen. Specifiek:

Het lost de fundamentele vraag op of robuuste evenwichten bestaan in average-reward multi-agent settings, een probleem waarbij standaardtechnieken falen.
Het introduceert de eerste algoritmen met bewijsbare convergentiegaranties voor het oplossen van average-reward DR-MG's, waarmee de beperkingen van verdisconteerde of eindige-horizon benaderingen worden overstegen.
Het benadrukt de noodzaak van structurele aannames (irreducibiliteit of zwakke communicatie) voor het bestaan van stationaire evenwichten, waarbij via tegenvoorbeelden wordt aangetoond dat dergelijke aannames niet louter technisch zijn maar essentieel.

De auteurs merken op dat hoewel hun kader een sterk fundament biedt, het vinden van exacte evenwichten in general-sum games uitdagend blijft, en dat hun TD-gebaseerde algoritme convergeert naar stationaire punten die dienen als een noodzakelijke eerste stap naar het vinden van exacte robuuste NE's. Toekomstig werk wordt gesuggereerd om lokale gradiënt-dominantie te verkennen voor sterkere convergentiegaranties en om het kader uit te breiden voorbij $(s, a)$ -rechthoekige onzekerheidssets.