Technische Samenvatting: Paralleliseren van Counterfactual Regret Minimization

Probleemstelling

Hoewel parallelisering een hoeksteen is geweest van kunstmatige intelligentie, met als gevolg een drastische verkorting van de trainingtijden voor grote modellen, blijft de toepassing ervan op computationeel oplossen van spellen relatief onontgonnen terrein. Ondanks mijlpalen in het oplossen van grote imperfecte-informatiespellen (bijvoorbeeld Cepheus, Libratus, Pluribus) die vertrouwen op een vorm van parallelisme, zijn de specifieke mechanismen voor het paralleliseren van Counterfactual Regret Minimization (CFR)-algoritmen niet gegeneraliseerd. Bestaande pogingen, zoals die van Reis en Rudolf, lijden vaak aan reproduceerbaarheidsproblemen, vereisen complexe besturingsflow per thread, of resulteren in suboptimale kwadratische werkcomplexiteit. Bovendien ontbreekt het aan generaliteit bij eerdere domeinspecifieke benaderingen (bijvoorbeeld in Cepheus). De auteurs identificeren de behoefte aan een gegeneraliseerd, domeinonafhankelijk raamwerk dat CFR en zijn tabulaire varianten kan versnellen zonder de algoritmische eigenschappen die ze effectief maken, te offeren.

Methodologie

De auteurs stellen een gegeneraliseerd paralleliseringsraamwerk voor dat de sequentie-vormversie van CFR herformuleert als een reeks lineair-algebraïsche bewerkingen. Deze transformatie maakt het toepassen van standaard, sterk geoptimaliseerde technieken voor het paralleliseren van lineaire algebra (specifiek op GPU's) op het oplossen van spellen mogelijk.

Kern Technische Aanpak

1. Herformulering van CFR als Lineaire Algebra:
   Het papier converteert de boomtraversiestappen die inherent zijn aan CFR (top-down voor strategie-updates, bottom-up voor nutobservatie) naar matrix-vectorbewerkingen. Dit wordt bereikt met behulp van logische matrices (matrices met waarden in $\{0, 1\}$) om verschillende data-representaties met elkaar in overeenstemming te brengen:

   • Sequentie versus Knooprepresentatie: Logische matrix $A \in \mathbb{R}^{P \times \Sigma}$ converteert tussen per-knoop vectoren ($\mathbb{R}^P$) en per-sequentie vectoren ($\mathbb{R}^\Sigma$).
   • Gedragsrepresentatie: Logische matrix $B$ behandelt de conversie naar de gedragsrepresentatie ($\mathbb{R}^{\Sigma^+}$), die de lege sequentie uitsluit.
   • Actieaggregatie: Logische matrix $C$ aggregeert waarden over beschikbare acties op beslispunten, waardoor L1-normalisatie en verwachtingsberekeningen via matrixvermenigvuldiging mogelijk worden.

2. Geparalleliseerde Boomtraversie:
   In plaats van recursieve boomtraversie, decomposeert het algoritme het Boomvormige Sequentiële Beslissingsproces (TFSDP) in niveaustructuren. Adjacentiematrices $L^{(d)}$ vertegenwoordigen randen op elke diepte $d$.

   • Top-down traversie (voor strategievergroeiing) wordt uitgevoerd door sequentieel $L^{(1)}, L^{(2)}, \dots, L^{(k)}$ toe te passen.
   • Bottom-up traversie (voor nutaccumulatie) wordt uitgevoerd door deze matrices in omgekeerde volgorde toe te passen.
   • Deze bewerkingen worden geïmplementeerd met behulp van Compressed Sparse Row (CSR) sparse matrix-vector vermenigvuldiging, wat zeer efficiënt is op parallelle hardware.

3. Algoritmische Aanpassing:
   Het raamwerk is ontworpen om modulair te zijn. De kern geparalleliseerde bewerkingen (NEXTSTRATEGY en OBSERVEUTILITY) worden gedefinieerd, en specifieke CFR-varianten worden geïmplementeerd door eenvoudige bewerkingen aan deze kernfuncties toe te voegen:

   • CFR+: Voegt een vloeroperatie toe aan regrets.
   • Gediscouteerde CFR (DCFR): Past tijdsafhankelijke schalingsfactoren toe op positieve en negatieve regrets.
   • Voorspellende CFR (PCFR): Integreert een voorspellingsvector voor instantane regrets.

Belangrijkste Bijdragen

• Gegeneraliseerd Raamwerk: Het papier presenteert een domeinonafhankelijk raamwerk dat CFR behandelt als lineaire algebra, waardoor het toepasbaar is op elke tabulaire CFR-variant (CFR, CFR+, DCFR, PCFR, PCFR+).
• Theoretische Analyse: Met behulp van het werk-diepte model bewijzen de auteurs dat het geparalleliseerde algoritme dezelfde totale werkcomplexiteit behoudt ($W = \Theta(|P|)$) als de sequentiële sequentie-vorm CFR, waardoor geen efficiëntieverlies optreedt bij afwezigheid van parallelisme. De diepte blijkt $D = \Theta(k \log B)$ te zijn, waarbij $k$ de boomhoogte is en $B$ de vertakkingsfactor.
• Open-Source Implementatie: In tegenstelling tot eerdere GPU-pogingen biedt dit werk een open-source implementatie die compatibel is met de OpenSpiel-bibliotheek, wat reproduceerbaarheid en integratie faciliteert.
• Schaalbaarheid: De aanpak splitst het spel effectief op elke diepte, in plaats van alleen op subspeldrempels, wat potentieel meer parallelisme oplevert dan eerdere architecturen zoals Cepheus.

Experimentele Resultaten

De auteurs evalueerden hun GPU-versnelde implementatie tegenover de implementaties van Google DeepMind's OpenSpiel (Python en C++) die draaien op CPU's over zeven benchmarkspellen van variërende grootte (van Kuhn poker met 58 knopen tot Large Battleship met $5.2 \times 10^7$ knopen).

• Kleine Spellen: Voor kleine spellen (bijvoorbeeld Kuhn poker, Leduc poker) resulteert de GPU-overhead in een vertraging ten opzichte van CPU-implementaties.
• Grote Spellen: Naarmate de spelgrootte toeneemt, presteert de geparalleliseerde implementatie aanzienlijk beter dan de CPU-baselines.
  • Voor Small Battleship is de snelheidswinst ongeveer $2.1 \times 10^2$ keer sneller dan de C++-implementatie van OpenSpiel.
  • Voor Medium Battleship bereikt de snelheidswinst $1.2 \times 10^3$.
  • Voor Large Battleship is de snelheidswinst $4.1 \times 10^3$.
  • Over het geheel genomen is de GPU-implementatie tot 18.889 keer sneller dan de Python-implementatie van OpenSpiel en 3.413 keer sneller dan de C++-implementatie.
• Convergentie: De experimenten tonen aan dat de geparalleliseerde implementatie dezelfde vermindering van exploitabiliteit over de wandkloktijd bereikt, maar in een fractie van de tijd, waarbij de snelheidswinst duidelijker wordt naarmate de spelgrootte toeneemt.

Betekenis en Beweringen

Het papier beweert dat deze paralleliseringstechniek niet noodzakelijk de grootte van het spel dat opgelost kan worden vergroot (in termen van geheugencapaciteit), maar wel de tijd die nodig is om een optimale oplossing te vinden drastisch reduceert.

• Versnelling van Onderzoek: De primaire waardepropositie is het mogelijk maken voor onderzoekers om hypothesen, nieuwe CFR-varianten en hyperparameterregimes te testen met veel snellere doorlooptijden.
• Herhalende Instellingen: Het raamwerk is bijzonder nuttig voor spellen die in herhalende settings worden gespeeld (bijvoorbeeld poker met variërende stackgroottes) waarbij individuele spelbomen vergelijkbaar zijn, wat snelle heroplossing mogelijk maakt.
• Compatibiliteit: De auteurs benadrukken dat hun methode volledige compatibiliteit behoudt met OpenSpiel, waardoor het kan worden gebruikt als een 'drop-in'-versneller voor bestaand speltheoretisch onderzoek zonder dat een herschrijving van speldefinities nodig is.
• Bescheidenheid: De auteurs stellen expliciet dat hun bijdrage niet wederzijds uitsluitend is ten opzichte van eerdere architecturen (zoals de subspelsplitsing van Cepheus); integendeel, hun techniek kan worden aangevuld met dergelijke architecturen voor verder parallelisme. Zij erkennen ook dat hoewel zij GPU vergelijken met CPU, de resultaten het potentieel van parallelisme benadrukken, zelfs in reguliere gebruiksscenario's, hoewel zij niet beweren spellen op te lossen die eerder onoplosbaar waren vanwege geheugenbeperkingen.