Towards Learning Representations of Policies in Two-Player Zero-Sum Imperfect-Information Games

Technische Samenvatting: Naar het leren van representaties van beleidsregels in twee-speler zero-sum spellen met imperfecte informatie

Probleemstelling
In twee-speler zero-sum spellen met imperfecte informatie (IIG's) profiteren agenten vaak van het redeneren over hun eigen en de beleidsregels (policies) van hun tegenstanders. Hoewel dieptegelimiteerde lookahead-zoekopdrachten haalbaar zijn in kleine spellen met tabulaire representaties (bijv. Counterfactual Regret Minimization), wordt deze aanpak onuitvoerbaar in spellen met grote publieke geloofstoestanden (belief states), waarbij het enumereren van alle mogelijke beleidsregels onmogelijk is. Bijgevolg is er behoefte aan compacte, nuttige representaties (embeddings) van beleidsregels die agenten in staat stellen te redeneren over strategische intentie zonder toegang te hebben tot volledige beleidstabellen. Bestaand onderzoek naar het leren van dergelijke beleidsrepresentaties in IIG's is echter schaars, en mist zowel systematische methoden voor het genereren van datasets van beleidsregels als gestandaardiseerde downstream-taken voor evaluatie.

Methodologie
De auteurs stellen een systematisch framework voor bestaande uit drie kerncomponenten: datasetgeneratie, embedding-leren en downstream-evaluatie.

1. Datasetgeneratie: Het artikel introduceert drie methoden om diverse datasets van beleidsregels voor een gegeven spel te creëren:

   • Random Initialisatie: Het willekeurig initialiseren van neurale netwerken voor beleidsregels met een aangepast schema om gedragsdiversiteit te waarborgen, om zo de homogeniteit van standaard PyTorch-initialisaties te vermijden.
   • Policy Space Response Oracle (PSRO): Het iteratief trainen van best-responses op mengsels van bestaande beleidsregels om een uitbreidende pool van diverse strategieën te genereren.
   • Neural Population Learning (NeuPL): Het trainen van een enkel conditioneel neuraal netwerk dat gedeeld wordt door alle agenten; nieuwe beleidsregels worden gegenereerd door te samplen uit de latente embedding-ruimte van het netwerk.

2. Embedding-leren: Verschillende methoden worden voorgesteld om beleidsregels te mappen naar vectorrepresentaties:

   • Weight Autoencoder: Een naïef baseline die probeert de afgeplatte gewichtsvector van een beleidsnetwerk te reconstrueren vanuit een bottleneck-laag.
   • Functional Encoder: Vergelijkbaar met de weight autoencoder, maar minimaliseert de KL-divergentie tussen de actieverdelingen van de originele en gereconstrueerde netwerken op gesamplede informatie-toestanden, met de focus op gedragsreconstructie in plaats van gewichtsreconstructie.
   • Trajectory Encoder: Een contrastieve leerbenadering (geïnspireerd door SimCLR) die variabel lengte trajecten (verzameld door beleidsregels uit te rollen tegen willekeurige tegenstanders) mapt naar een vast-dimensionale latente ruimte. Deze methode vereist geen toegang tot de interne werking van het netwerk.
   • NeuPL-stijl Conditionele Embeddings: Een generatieve aanpak waarbij een conditioneel netwerk leert om elke vector uit de latente ruimte te decoderen naar een beleidsregel, waarbij de populatie en de embeddings gezamenlijk worden gegenereerd.
   • Grover et al. Baseline: Een hybride generatief-discriminatief model met een MLP-encoder en een conditioneel beleidsnetwerk getraind met imitatie- en triplet-identificatieverliezen.
   • Baselines: Bevat een Tabulaire Baseline (het concateneren van actieverdelingen bij alle informatie-toestanden) en een Identity Baseline (het direct gebruiken van de ruwe netwerkgewichten).

3. Downstream Evaluatietaken: De effectiviteit van de representaties wordt geëvalueerd met vijf taken:

   • Taak A & B (Payoff Predictie): Het voorspellen van verwachte payoffs tegen een uniforme willekeurige tegenstander (Taak A) of tussen twee specifieke beleidsregels (Taak B) met behulp van een lineaire predictor.
   • Taak C (Exploitability Predictie): Het voorspellen van de payoff van de best-response van een tegenstander op een gegeven beleidsregel.
   • Taak D (Zero-Shot Best-Response): Het trainen van een conditioneel beleidsnetwerk om een best-response te benaderen voor een beleidsregel, gegeven enkel de embedding ervan.
   • Taak E (Agent Identificatie): Het classificeren van welke beleidsregel een gegeven traject heeft gegenereerd met behulp van k-NN of lineaire probes.

Experimentele Resultaten
Experimenten werden uitgevoerd op Kuhn Poker (12 informatie-toestanden) en Leduc Poker (936 informatie-toestanden), met voorlopige resultaten op grotere spellen (Liar's Dice, Phantom Tic-Tac-Toe).

• Payoff Predictie (Taken A & B): In Kuhn Poker domineerde de tabulaire baseline vanwege de kleine omvang van het spel. Echter, in Leduc Poker presteerden geleerde encoders (Trajectory, Grover, NeuPL) beter dan de tabulaire baseline, die leed onder hoge dimensionaliteit (2808 dimensies). De Grover en Trajectory encoders bereikten de hoogste verbeteringen (tot 32,3% reductie in MSE) op Taak A in Leduc. Eenvoudige Weight en Functional autoencoders faalden over het algemeen in het verbeteren ten opzichte van het voorspellen van het gemiddelde.
• Exploitability en Zero-Shot Response (Taken C & D): De NeuPL-methode presteerde significant beter dan de baselines in het voorspellen van best-response payoffs (Taak C) en het trainen van zero-shot responders (Taak D), met name op door NeuPL gegenereerde beleidspopulaties. Identity en Weight baselines presteerden slecht, vaak slechter dan de gemiddelde baseline.
• Agent Identificatie (Taak E): De Trajectory Encoder (gebruikmakend van een lineaire classifier) presteerde aanzienlijk beter dan de Grover baseline, met een top-1 nauwkeurigheid van 47,9% op Kuhn en 57,8% op Leduc, vergeleken met respectievelijk 25,7% en 38,9% voor Grover.
• Visualisatie: t-SNE visualisaties van Kuhn Poker embeddings toonden aan dat de Trajectory Encoder erin slaagde agressieve en passieve strategieën te scheiden, terwijl de Weight Autoencoder embeddings geen dergelijke structuur vertoonden.

Belangrijkste Bijdragen

1. Dataset Creatie: Introductie van drie verschillende methoden (Random, PSRO, NeuPL) voor het genereren van diverse datasets van beleidsregels in IIG's.
2. Representatie-leren: Voorstel en vergelijking van meerdere embeddingtechnieken, variërend van naïeve gewichtsreconstructie tot contrastief traject-leren en conditionele generatieve modellen.
3. Evaluatie Suite: Definitie van een uitgebreide set downstream-taken (payoff predictie, exploitability, zero-shot response, agent identificatie) om beleidsrepresentaties rigoureus te evalueren.
4. Systematische Vergelijking: Naar weten van de auteurs is dit een van de eerste werken die systematisch zelfgesuperviseerde leertechnieken voor beleidsrepresentaties vergelijkt.

Betekenis en Claims
Het artikel claimt een fundamentele stap te zijn richting het leren van compacte, nuttige gedragsrepresentaties in imperfecte informatie-spellen. Hoewel de methoden als "zeer basis" worden beschreven, laten de resultaten zien dat nuttige gedragsmatige semantiek aanwezig is in de geleerde embeddings, vooral bij het gebruik van contrastief traject-leren of NeuPL-stijl conditionering. Dit werk benadrukt dat hoewel tabulaire representaties voldoende zijn voor kleine spellen, geleerde embeddings superieur worden naarmate de complexiteit van het spel toeneemt. De auteurs positioneren dit werk als een open framework (code beschikbaar) om verder onderzoek naar het leren van beleidsrepresentaties te faciliteren, waarbij zij opmerken dat toekomstig werk kan bestaan uit het verfijnen van verliestermen of het integreren van deze representaties met decision-time planning.