Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning

Deze paper introduceert een schaalbaar, generatief reinforcement learning-framework dat Monte-Carlo Tree Search, diepe generatieve modellen en Nash-verhandelingsconcepten combineert om effectieve online en offline tegenstandersmodellen te ontwikkelen voor complexe spelletjes met imperfecte informatie, zoals aangetoond in onderhandelingsexperimenten met mensen.

De kern

Stel je voor dat je in een groot, druk café zit waar iedereen tegelijkertijd onderhandelt over wie wat krijgt. Je hebt geen idee wat de anderen willen, wat ze in hun zak hebben, of hoe ze denken. Je moet een deal sluiten, maar je kunt niet gewoon raden; je moet slimme strategieën bedenken.

Dit is precies het probleem waar deze wetenschappers van DeepMind een oplossing voor hebben bedacht. Ze hebben een nieuwe manier ontwikkeld om kunstmatige intelligentie (AI) te leren omgaan met onbekende tegenstanders in complexe spelletjes, zoals onderhandelen.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. Het Probleem: De "Blinde" Speler

Vroeger waren computerspelletjes slim, maar ze waren vaak "stom" als het ging om het begrijpen van een mens. Ze volgden strakke regels of probeerden alles uit te rekenen, wat in grote, chaotische situaties (waar je niet alles kunt zien) onmogelijk is.

• De analogie: Het is alsof je probeert een spelletje poker te spelen, maar je mag niet naar de kaarten van je tegenstander kijken en je hebt geen idee of hij blufft of echt sterke kaarten heeft. De oude methodes waren als iemand die blindelings gokt op basis van een vast script.

2. De Oplossing: De "Droomende" Speler

De auteurs hebben een nieuwe methode bedacht die ze GenBR noemen. Dit is een combinatie van drie krachtige dingen:

1. Zoeken (Search): Net als een schaker die vooruit denkt: "Als ik dit doe, doet hij dat, en dan doe ik weer dit..."
2. Leren (Reinforcement Learning): Het spel zelf spelen en leren van winst en verlies.
3. Genereren (Generative Models): Dit is het nieuwe en spannende deel. De AI leert een soort "droommachine" of "fantasie-apparaat".

• De analogie: Stel je voor dat je in een donkere kamer zit met een onbekende tegenstander. In plaats van blind te spelen, gebruikt deze AI een magische projectie.
  • De AI zegt: "Oké, ik zie dat mijn tegenstander een boek wil. Laten we eens dromen: wat als hij ook een hoed wil? En wat als hij een basketbal wil?"
  • De AI "droomt" (genereert) duizenden mogelijke scenario's van wat de tegenstander zou kunnen willen.
  • Dan speelt de AI in al die dromen tegelijkertijd om te zien welke strategie het beste werkt.
  • Als de tegenstander een echte zet doet, past de AI haar dromen direct aan. "Oh, hij heeft een hoed gekozen? Dan was mijn droom over de basketbal fout. Laten we opnieuw dromen, maar dan met de hoed als uitgangspunt."

3. De Groepsdynamiek: De "Olympische Spelen"

Om deze AI zo goed mogelijk te maken, hebben ze hem niet alleen tegen zichzelf laten spelen. Ze hebben een systeem gebruikt dat PSRO heet.

• De analogie: Denk aan een trainingskamp voor atleten. Je hebt niet maar één speler. Je hebt een heel team met verschillende stijlen:
  • De "Agressieve" speler (wil alles winnen).
  • De "Vriendelijke" speler (wil een eerlijke deal).
  • De "Slimme" speler (probeert je te bedriegen).
  • De AI speelt tegen al deze verschillende versies van zichzelf. Door te spelen tegen de agressieve, leert hij hoe hij moet verdedigen. Door te spelen tegen de vriendelijke, leert hij hoe hij samenwerkt.
  • Uiteindelijk ontstaat er een "meester-speler" die tegen iedereen goed kan spelen, omdat hij alle stijlen heeft gezien.

4. Het Experiment: Mensen vs. Robots

De echte test kwam toen ze deze AI tegen echte mensen zetten in een spelletje genaamd "Deal or No Deal" (Maak een deal of niet).

• Het spel: Twee mensen moeten een pot met spullen (boeken, hoeden, ballen) verdelen. Ze weten niet wat de ander waardeert. Ze moeten onderhandelen.
• Het resultaat: De AI's waren verrassend goed.
  • Sommige AI's waren zo slim dat ze de mensen bijna evenveel winst gaven als twee mensen onder elkaar.
  • Een specifieke AI (de "Fair" agent) was zo goed in onderhandelen dat hij vaak een deal vond die voor beide partijen het beste was. Hij was niet alleen slim, hij was ook eerlijk.
  • De AI kon zelfs "lezen" in de dromen van de mens: als een mens een bepaalde keuze maakte, begreep de AI snel wat die mens wilde, zelfs zonder dat de mens het hardop zei.

Conclusie: Waarom is dit belangrijk?

Deze technologie is niet alleen voor spelletjes. Het is een grote stap vooruit voor de toekomst van AI in de echte wereld.

• Vergelijking: Stel je voor dat een AI helpt bij het onderhandelen over salarissen, of bij het verdelen van hulpgoederen in een rampgebied, of bij het regelen van verkeerslichten in een stad.
• In al die situaties zijn er veel mensen met verschillende wensen, en niemand weet precies wat de ander wil. Deze nieuwe methode laat computers leren om niet alleen "te winnen", maar om samen te werken en begrip te tonen, zelfs als ze de situatie niet volledig kunnen zien.

Kortom: Ze hebben een computer gemaakt die niet alleen rekent, maar ook fantaseert en leert van de dromen van anderen, zodat hij een betere onderhandelaar wordt dan ooit tevoren.

Technische samenvatting

Probleemstelling

Bestaande methoden voor tegenstandermodellering (opponent modeling) in multi-agent systemen kampen met twee fundamentele beperkingen:

1. Afhankelijkheid van domeinspecifieke heuristieken: Traditionele methoden vereisen vaak handmatig ontworpen kennis over de regels of het gedrag van tegenstanders, wat de overdraagbaarheid naar nieuwe domeinen beperkt.
2. Schaalbaarheid in imperfecte informatie: Het berekenen van een optimale respons (best response) in grote games met imperfecte informatie (waarbij agents niet alle toestanden van de wereld zien) is computationeel onhaalbaar. Bestaande zoekalgoritmen zoals Monte-Carlo Tree Search (MCTS) hebben moeite met het schatten van de posterior-verdeling over wereldtoestanden wanneer de zoekruimte enorm groot is.

Het doel van dit werk is het ontwikkelen van een schaalbaar, generiek trainingsregime dat agents in staat stelt om tegenstanders te modelleren en daarop te reageren zonder voorafgaande domeinkennis, specifiek in general-sum games met imperfecte informatie.

Methodologie

De auteurs introduceren een geïntegreerde aanpak die diepe versterkende leer (Deep RL), zoekalgoritmen en generatieve modellen combineert binnen het Policy Space Response Oracles (PSRO) framework.

1. Generative Best Response (GenBR)

De kern van de innovatie is GenBR, een verbeterde versie van AlphaZero-stijl zoekalgoritmen voor imperfecte informatie.

• Architectuur: GenBR gebruikt drie diepe neurale netwerken: een beleidsnetwerk ($p$), een waardenetwerk ($v$) en een generatief netwerk ($g$).
• Werking: In tegenstelling tot traditionele IS-MCTS (Information Set MCTS), die de posterior-verdeling over wereldtoestanden expliciet moet berekenen (wat vaak onmogelijk is), gebruikt GenBR het generatieve netwerk $g$ om wereldtoestanden te stalen (sample) op basis van de huidige informatiestaat.
• Bayesiaans leren: Tijdens het zoeken (search) update het agent continu een online model van de tegenstander door Bayesiaanse redenering toe te passen op de gegenereerde wereldtoestanden. Dit stelt het agent in staat om zowel de omgevingstoestand als de strategie van de tegenstander te infereren tijdens het spel.
• Training: GenBR wordt getraind via een zelfspeel-loop (self-play) waarbij de netwerken worden geüpdatet met data uit zoektrajecten.

2. PSRO Framework met Bargaining Theory

GenBR fungeert als de "Oracle" (de zoekfunctie) binnen het PSRO-algoritme:

• Iteratief proces: PSRO bouwt een populatie van strategieën op door iteratief beste antwoorden te vinden op een gemengde strategie van de tegenstanders.
• Meta-Strategy Solvers (MSS): Een cruciale bijdrage is het gebruik van concepten uit de onderhandelings-theorie (bargaining theory) als MSS. In plaats van alleen naar Nash-evenwichten te zoeken, gebruiken de auteurs de Nash Bargaining Solution (NBS).
  • Ze lossen het optimalisatieprobleem van de Nash-product (maximalisatie van het product van de nutswinsten boven een dis-agreement punt) op via geprojecteerde gradiëntstijging.
  • Dit leidt tot strategieën die dichter bij de Pareto-grens liggen, wat betekent dat ze sociale welvaart maximaliseren en eerlijke uitkomsten bevorderen.

Belangrijkste Bijdragen

1. GenBR Algoritme: Een nieuwe zoekmethode die MCTS combineert met een diep generatief model. Dit maakt het mogelijk om in grote ruimtes met imperfecte informatie te plannen en te infereren, zonder de posterior exact te hoeven berekenen.
2. NBS-gebaseerde Meta-Strategy Solvers: Het introduceren van nieuwe MSS's binnen PSRO die gebaseerd zijn op de Nash Bargaining Solution. Dit automatiseert het vinden van evenwichten die zowel efficiënt als eerlijk zijn, wat essentieel is voor onderhandelingsgames.
3. Empirische Validatie met Mensen: Een uitgebreide studie waarin agents getraind met deze methode onderhandelen met echte mensen in het spel "Deal or No Deal".

Resultaten

De auteurs testen hun methode op twee gebieden:

• Colored Trails (Benchmark):

  • Agents getraind met NBS-based MSS's presteerden significant beter in het minimaliseren van de "Pareto Gap" (afstand tot de optimale uitkomsten) dan agents die gebruikmaakten van traditionele solvers.
  • De NBS-methoden leidden sneller naar strategieën die sociale welvaart maximaliseerden.

• Deal or No Deal (Menselijke Studie):

  • Schaalbaarheid: GenBR met generatieve modellen presteerde aanzienlijk beter dan standaard Deep Q-Networks (DQN), vooral tegen sterkere tegenstanders. De zoekmethode bereikte hoge waarden in minder trainingsepisodes.
  • Mens-Agent Interactie: In een experiment met 346 deelnemers werden verschillende agenten getest (competitief, coöperatief, eerlijk).
    • De "Fair" agent (gebaseerd op NBS en ongelijkheidsaversie) behaalde een sociale welvaart en een Nash-bargaining score die vergelijkbaar was met mens-mens interacties.
    • Deze agent was in staat om zich aan te passen aan verschillende menselijke stijlen en behaalde eerlijke uitkomsten zonder de mens te exploiteren.
    • Competitieve agents (zoals DQN) haalden soms hogere individuele scores, maar ten koste van de totale sociale welvaart en door minder menselijke uitkomsten te accepteren.

Betekenis en Impact

Dit werk is significant omdat het een brug slaat tussen game-theoretische optimalisatie en praktische multi-agent leer in complexe, onvolledige informatiesituaties.

• Generalisatie: Het bewijst dat agents zonder handmatige regels (domain-specific heuristics) kunnen leren om effectief te onderhandelen en samen te werken met mensen.
• Toepassingsgebied: De methode is toepasbaar op diverse domeinen zoals geautomatiseerde veilingen, onderhandelingssystemen, cyberveiligheid en autonome voertuigen, waar agents moeten opereren in general-sum omgevingen met imperfecte informatie.
• Ethische Implicatie: De studie benadrukt het belang van het ontwerpen van agents die niet alleen winstgevend zijn, maar ook sociale normen en eerlijkheid respecteren, wat essentieel is voor de acceptatie van AI in menselijke interacties.

Kortom, het artikel presenteert een robuust raamwerk waarbij zoekalgoritmen en generatieve modellen worden gecombineerd om agents te creëren die niet alleen slimme tegenstanders zijn, maar ook effectieve en eerlijke partners in dynamische multi-agent omgevingen.