Technische Samenvatting: GAE Schiet Tekort in Zelfspel met Imperfecte Informatie

Probleemstelling

Competitieve multi-agent versterkende leer (MARL) in spellen met imperfecte informatie vereist dat agenten opereren onder partiële waarneembaarheid tegenover adversariele tegenstanders, wat stochastische beleidsregels noodzakelijk maakt. Hoewel zelfspel-versterkende leer met behulp van Proximal Policy Optimization (PPO) empirisch succes heeft geboekt, staat het voor een kritieke knelpunt in het leren van evenwichten: variantie in de schatting van het voordeel.

Standaard PPO-implementaties vertrouwen op Generalized Advantage Estimation (GAE) om multi-stap temporal-difference (TD) residuen te aggregeren. In single-agent settings balanceert GAE effectief bias en variantie. Echter, in zelfspel met imperfecte informatie zijn evenwichtsbeleidregels inherent stochastisch. GAE erft willekeur uit het stalen van toekomstige acties binnen zijn multi-stap trace. Omdat evenwichtsbeleidregels verschillende waarden toekennen aan verschillende acties, introduceert het stalen van toekomstige acties intrinsieke ruis. Deze variantie wordt versterkt in zelfspelscenario's en blijft bestaan, zelfs wanneer de state-value critic ($V$-critic) exact is. Bijgevolg produceert standaard GAE hoge-variantie gradiëntschattingen precies in de regimes waar stabiel leren het meest kritiek is, wat de convergentie naar hoogwaardige evenwichten belemmert.

Methodologie

Q-Boosting Schatter

Om de variantie die door actiestalen wordt geïntroduceerd aan te pakken, stellen de auteurs Q-boosting voor, een variantiereductieve voordeelschatter. De kerninnovatie is het vervangen van de gestaalde multi-stap TD-trace die in GAE wordt gebruikt, door een multi-stap Expected SARSA($\lambda$)-trace berekend vanuit een gecentraliseerde action-value critic ($Q$-critic).

• Mechanisme: In plaats van te bootstrappen via gestaalde volgende acties (wat ruis introduceert), berekent Q-boosting beleidsverwachtingen bij elke backup-stap. Het middelt de ruis van stochastische toekomstige acties door de verwachting te nemen over de actieverdeling die wordt gedefinieerd door het huidige beleid.
• Formulering: Gegeven een gecentraliseerde $Q$-critic $Q_i(s, a)$ en een gezamenlijk beleid $\pi$, wordt de state-waarde berekend als $V^\pi_i(s) = \sum_a \pi(a|s) Q_i(s, a)$. De Q-boosting voordeelschatting $\hat{A}^{boost}_{i,\tau}$ wordt gedefinieerd als:
  $$\hat{A}^{boost}_{i,\tau} \triangleq Q_i(s_\tau, a_\tau) - V^\pi_i(s_\tau) + \sum_{\tau' \ge \tau} (\lambda\gamma)^{\tau'-\tau} \cdot \delta^+_{i,\tau'}$$
  waarbij het Expected SARSA TD-residu is $\delta^+_{i,\tau'} \triangleq r_{i}(s_{\tau'}, a_{\tau'}) + \gamma V^\pi_i(s_{\tau'+1}) - Q_i(s_{\tau'}, a_{\tau'})$.
• Theoretische Garantie: De auteurs bewijzen dat voor on-policy trajecten en $\lambda=1$, de Q-boosting-schatter een onbevooroordeelde schatting biedt van de score-functie beleidsgradiënt-term. Bovendien, als de $Q$-critic voldoende nauwkeurig is, is de gemiddelde-kwadratische fout van de Q-boosting-schatter strikt lager dan die van GAE met een exacte $V$-critic, mits toekomstige acties een niet-nul variantie vertonen in hun actiewaarden.

Variantiereductieve Beleidsoptimalisatie (VRPO)

De auteurs integreren Q-boosting in een PPO-achtig algoritme genaamd Variance-Reduced Policy Optimization (VRPO).

• Architectuur: VRPO volgt het paradigma van Centralized Training with Decentralized Execution (CTDE). Het maakt gebruik van gedecentraliseerde acteurs voor uitvoering en een gecentraliseerde $Q$-critic voor training.
• Doel: Het algoritme behoudt PPO's afgeknipte surrogate-doel en trust-region updates, maar wijzigt de voordeelschatting en de procedures voor critic-leren.
• Trainingsprocedure:
  1. Acteur-update: Acteurs worden bijgewerkt met behulp van de Q-boosting voordeelschattingen. Om on-property eigenschappen te behouden, worden de beleidsverwachtingstermen in de voordeelsberekening opnieuw berekend met behulp van huidige acteurkansen terwijl de critic-waarden vast worden gehouden.
  2. Critic-update: De gecentraliseerde $Q$-critics worden getraind door de kwadratische regressieverlies te minimaliseren tegen de Q-boosting-doel (een multi-stap Expected SARSA-trace).
  3. Regularisatie: Een expliciete KL-divergentie-boete ten opzichte van een uniforme verdeling wordt toegevoegd aan het beleidsdoel om exploratie te bevorderen en convergentie van de laatste iteratie te stimuleren.
• Omgaan met Grote Actieruimtes: Voor spellen met enorme actiestelsels (bijv. Dou Dizhu) ontleden de auteurs complexe beslissingen in meerdere tijdstappen. Dit vermindert het aantal beschikbare acties per stap tot een hanteerbare grootte, waardoor de enumeratie die nodig is voor de beleidsverwachting in de Q-boosting-trace mogelijk wordt.

Belangrijkste Bijdragen

1. Identificatie van Variantiebron: Het paper identificeert dat het stalen van toekomstige acties in GAE extra variantie introduceert in stochastisch zelfspel, wat blijft bestaan zelfs met exacte waardenfuncties.
2. Q-Boosting Schatter: De auteurs leiden Q-boosting af, een PPO-compatibele schatter die een Expected SARSA($\lambda$)-trace toepast op een gecentraliseerde $Q$-critic om ruis van toekomstige actiestalen te middelen.
3. VRPO Algoritme: Het voorstellen van VRPO, een PPO-achtig algoritme dat Q-boosting benut om verbeterde stabiliteit en prestaties te bereiken.
4. Empirische Validatie: Demonstratie dat het verminderen van variantie in voordeelschatting aanzienlijke winsten oplevert in de kwaliteit van evenwichten over spellen van verschillende schalen.

Experimentele Resultaten

Middelgrote Spellen (Exacte Exploitability)

De auteurs hebben VRPO getoetst aan middelgrote spellen waarbij exacte exploitability kan worden berekend: Abrupt Phantom Tic-Tac-Toe (APTTT), Abrupt Dark Hex 3 (ADH3) en Liar's Dice met 2 dobbelstenen en 5 vlakken (LiDi 2D5F).

• Prestaties: VRPO behaalde consistent meer dan 15% lagere exploitability vergeleken met diverse PPO-gebaseerde baselines (IPPO, MAPPO, MMD, PPG) onder een gedeelde trainingsschema.
• Ablatie: Experimenten bevestigden dat de prestatiewinsten robuust zijn over verschillende trace-parameters ($\lambda$), regularisatiecoëfficiënten ($\alpha$) en PPO-afkniptcoëfficiënten ($\epsilon$).

Groot-schalige Spellen

De auteurs evalueerden VRPO in groot-schalige domeinen waar exacte exploitability onberekenbaar is.

• Dou Dizhu: VRPO werd getraind tegen de vorige state-of-the-art agent, PerfectDou. Onder een overeenkomend trainingbudget ($\approx 2.65 \times 10^9$ tijdstappen) overtrof VRPO PerfectDou na slechts 40% van de trainingsstappen. In head-to-head evaluaties over 100.000 deals behaalde VRPO positieve winsten tegen PerfectDou, DouZero en zichzelf (in rol-gewisselde matchups), waarmee een nieuwe state of the art werd gevestigd.
• Heads-Up No-Limit Texas Hold'em (HUNL): VRPO werd getraind op HUNL met een stack van 200 big blinds. In vergelijking met IPPO en MAPPO verminderde VRPO significant de standaardafwijking van de voordeelschattingen tijdens training. Tegen de sterke baseline Slumbot behaalde de VRPO-agent een gemiddelde winst van $33 \pm 19$ mBB/hand over 1.000.000 handen. Opmerkelijk is dat deze prestatie werd bereikt zonder online zoekopdrachten, subspeloplossing of op blauwdruk gebaseerde verhogingsgrootte.

Betekenis en Scope

Het paper claimt dat de primaire bijdrage ligt in de identificatie van variantie in voordeelschatting als een knelpunt in evenwichts-zelfspel en de demonstratie dat Q-boosting dit probleem effectief mitigeert. De resultaten suggereren dat het verminderen van variantie in voordeelschatting aanzienlijke winsten kan opleveren in de kwaliteit van geleerde evenwichten.

De auteurs handhaven een bescheiden scope met betrekking tot hun claims:

• De aanpak is gevalideerd voor spellen met grote discrete actiestelsels (via ontleding) maar adresseert geen hoog-dimensionale continue actieruimtes.
• De empirische focus ligt op stochastisch zelfspel met gecentraliseerde critics; de auteurs claimen geen brede verbeteringen boven GAE in standaard single-agent RL-benchmarks.
• De methode is afhankelijk van de mogelijkheid om beleidsverwachtingen over acties te berekenen, wat haalbaar is in de geteste domeinen maar specifieke architecturale overwegingen kan vereisen voor extreem grote actieruimtes.

Concluderend vertegenwoordigt VRPO een significante stap voorwaarts in het toepassen van beleidsgradiëntmethoden op spellen met imperfecte informatie door een specifieke, eerder onder-geïdentificeerde bron van variantie inherent aan stochastisch evenwichtsleren aan te pakken.