NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibria

1. Probleemstelling

Het paper adresseert de uitdaging om Nash-evenwichten (NE) te vinden in tweespeler zero-sum imperfect-information games (2p0s IIGs) met behulp van Multi-Agent Reinforcement Learning (MARL).

• De Kernmoeilijkheid: Hoewel Deep Reinforcement Learning (DRL) succesvol is geweest in perfect-information games, behelzen 2p0s IIGs (zoals Poker) partiële waarneembaarheid en verborgen informatie.
• Beperkingen van Bestaande Methoden:
  • Populatie-gebaseerde methoden (bijv. PSRO, NFSP): Vereisen vaak dure best-response berekeningen en garanderen alleen convergentie naar een gemiddeld beleid, niet naar de laatste iteratie. Het extraheren van een definitief beleid in DRL-omgevingen is niet triviaal.
  • Counterfactual Regret Minimization (CFR): Vereist volledige enumeratie van de spelboom (model-gebaseerd), wat dit onuitvoerbaar maakt voor grote domeinen.
  • Regularisatie-gebaseerde methoden (bijv. R-NaD): Recentere benaderingen gebruiken regularisatie om convergentie van de laatste iteratie naar een geregulariseerd evenwicht te waarborgen. Deze zijn echter niet noodzakelijk ware Nash-evenwichten (ze blijven uitbuitbaar). Bovendien vertrouwen bestaande praktische implementaties (zoals R-NaD) op Neural Replicator Dynamics (NeuRD), wat in benchmarks inferieure prestaties heeft getoond ten opzichte van standaard policy gradient-methoden.
• De Kloof: Er ontbreekt een schaalbaar, model-vrij, op policy gradient gebaseerd algoritme dat bewezen convergeert naar een exact Nash-evenwicht in grote IIGs.

2. Methodologie

De auteurs stellen een tweestapsbenadering voor: een theoretisch kader (IMMD) en een praktisch algoritme (NASHPG).

A. Theoretisch Kader: Iterative MMD (IMMD)

De auteurs breiden Magnetic Mirror Descent (MMD) uit, een methode die geregulariseerde Variational Inequalities (VI) oplost.

• Geregulariseerde VI: Standaard VI-problemen voor Nash-evenwichten zijn monotoon maar niet sterk monotoon, wat ze moeilijk direct oplosbaar maakt. MMD voegt een sterk convex regularisatieterm (gebaseerd op Bregman-divergentie) toe om een sterk monotoon operator te creëren, wat een unieke oplossing garandeert.
• Iteratieve Verfijning: In plaats van één geregulariseerd probleem op te lossen, lost IMMD een reeks daarvan op.
  1. Start met een initiële strategieprofiel $\rho$.
  2. Los het geregulariseerde VI-probleem $VI(Z, G_\rho)$ op om een nieuwe strategie $z = M(\rho)$ te vinden.
  3. Gebruik deze nieuwe strategie $z$ als referentie $\rho$ voor de volgende ronde.
• Theoretische Garantie: Het paper bewijst dat dit iteratieve proces een strikt monotoon afname oplevert in de Bregman-divergentie naar elk Nash-evenwicht. Bijgevolg convergeert de reeks strategieën naar een ware Nash-evenwicht.

B. Praktisch Algoritme: Nash Policy Gradient (NASHPG)

Om IMMD toepasbaar te maken op grote schaal games waar volledige enumeratie onmogelijk is, leiden de auteurs NASHPG af:

• Van Gemengde naar Gedragsstrategieën: Ze benaderen de gemengde-strategie Bregman-divergentie (gebruikt in IMMD) met een Kullback-Leibler (KL)-divergentie tussen gedragsbeleid (stochastische beleid in RL).
• Doelfunctie: Het algoritme optimaliseert een geregulariseerde beleidsdoelstelling:
  $$\text{Doelstelling} = \mathbb{E}[R] - \alpha \cdot \mathbb{E}_{o} [ D_{KL}(\pi(\cdot|o) \parallel \rho(\cdot|o)) ]$$
  Waarbij $\pi$ het huidige beleid is, $\rho$ het referentiebeleid (van de vorige buitenste lus), en $\alpha$ de regularisatiesterkte.
• Algoritme Structuur:
  1. Binnenste Lus: Voer $K$ stappen uit van standaard policy gradient updates (bijv. met PPO) om de geregulariseerde doelstelling te optimaliseren tegen het huidige referentie $\rho$.
  2. Buitenste Lus: Na $K$ stappen, update het referentiebeleid $\rho$ naar het huidige beleid $\pi$, en herhaal.
• Modulariteit: NASHPG is agnostisch ten opzichte van de specifieke policy gradient schatter. Het kan naadloos integreren met geavanceerde single-agent RL-algoritmen zoals PPO (Proximal Policy Optimization).

3. Belangrijkste Bijdragen

1. Theoretische Convergentie: Introductie van IMMD, een meer-ronde regularisatiekader dat een strikt monotoon afname in Bregman-divergentie en convergentie naar een exact Nash-evenwicht garandeert in 2p0s extensive-form games.
2. Praktisch Algoritme (NASHPG): Ontwikkeling van een schaalbaar, model-vrij algoritme dat het IMMD-kader implementeert met behulp van standaard policy gradient-methoden (zoals PPO) en KL-regularisatie.
3. Hypothese Validatie: Verschafte empirisch bewijs dat de slechte prestaties van eerdere regularisatiemethoden (zoals R-NaD) te wijten waren aan het gebruik van NeuRD als innerlijke solver, en niet aan het regularisatiekader zelf. Het vervangen van NeuRD door PPO in een vergelijkbaar kader verbeterde de prestaties aanzienlijk.
4. Schaalbaarheid: Demonstreerde het vermogen om grote domeinen op te lossen (bijv. Battleship, Heads-Up No-Limit Texas Hold'em) waar exacte enumeratie onmogelijk is.

4. Experimentele Resultaten

De auteurs evalueerden NASHPG op zeven games variërend van klein (Kuhn Poker) tot massaal (Heads-Up No-Limit Texas Hold'em).

• Convergentie & Stabiliteit: NASHPG toonde stabiele convergentie zonder divergentie, zelfs met hoge regularisatiesterktes, in tegenstelling tot sommige baselines.
• Prestaties vs. Baselines:
  • Kleine Games: NASHPG bereikte vergelijkbare of lagere uitbuitbaarheid dan NFSP, PSRO, MMD en R-NaD op Kuhn Poker, Leduc Poker, Dark Hex en Phantom Tic-Tac-Toe.
  • Grote Games: In Battleship en Heads-Up No-Limit Texas Hold'em (waar exacte uitbuitbaarheid onuitvoerbaar is), behaalde NASHPG hogere gemiddelde uitbetalingen in head-to-head wedstrijden tegen alle baselines (NFSP, PSRO, R-NaD, MMD).
• Ablatie Studie (R-NaD vs. PPO): Een gecontroleerd experiment verving NeuRD door PPO in het R-NaD-kader (creërend RNaD-PPO).
  • In kleine games maakte de update-regel minder uit.
  • In grote games overtrof RNaD-PPO standaard R-NaD dramatisch, waardoor de kloof met NASHPG werd verkleind. Dit bevestigde dat de innerlijke optimalisatieregel (PPO vs. NeuRD) de primaire bottleneck is in steekproef-gebaseerde meer-ronde regularisatie.
• Efficiëntie: De implementatie vereiste slechts ~20 regels code-aanpassing bovenop standaard Independent PPO, wat de toegankelijkheid benadrukt.

5. Betekenis

• Kloof tussen Theorie en Praktijk Overbruggen: Het paper slaagt erin de kloof te overbruggen tussen theoretische convergentiegaranties (vaak beperkt tot kleine, geënumereerde games) en praktische, schaalbare MARL-algoritmen.
• Nieuw Paradigma voor MARL: Het vestigt dat iteratief verfijnen van een regularisatiereferentie gecombineerd met standaard policy gradients een superieure aanpak is voor het vinden van Nash-evenwichten in vergelijking met populatie-gebaseerde methoden of oudere regularisatietechnieken.
• Toegankelijkheid: Door te vertrouwen op standaard PPO en eenvoudige KL-regularisatie, verlaagt NASHPG de instapdrempel voor practitioners, waardoor ze geavanceerde speltheoretische convergentiegaranties kunnen toepassen zonder complexe aangepaste solvers of volledige spelboom-enumeratie nodig te hebben.
• State-of-the-Art Prestaties: Het zet een nieuwe benchmark voor model-vrije methoden in imperfect-information games, en presteert beter dan gevestigde baselines in zowel kleine als grote domeinen.