Technische Samenvatting: GARIP – Een Running-Average Moving Reference voor Last-Iterate Self-Play

1. Probleemstelling

In twee-speler nul-som spellen faalt standaard self-play met naïeve gradiënt-ascent (SGA) in de last-iterate; in plaats daarvan orbiteert het traject rond de Nash-evenwichten op een gesloten conservatief veld. Hoewel tijdgemiddelde policies convergeren, vertrouwt moderne diepe multi-agent reinforcement learning (RL) op de laatste netwerkparameters, waardoor het gedrag van de last-iterate cruciaal wordt.

Bestaande methoden proberen last-iterate convergentie te herstellen door de policy te regulariseren richting een referentie ("magneet") om conservatieve rotaties te doorbreken:

• MMD: Gebruikt een vaste referentie (bijv. uniform). Het convergeert naar een geregulariseerd evenwicht (Quantal Response Equilibrium), wat het verzwakken (annealing) van de regularisatie vereist om het ware Nash-evenwicht te bereiken.
• R-NaD: Gebruikt een periodieke snapshot van de huidige policy (reset elke $K$ stappen). Het bereikt Nash zonder annealing en vormt de basis voor systemen zoals DeepNash.
• Fictitious Play: Reageert optimaal op de gemiddelde tegenstander, maar mist een zelf-anker.

Het artikel identificeert een gat in de ontwerpruimte: een methode die ankeren aan het running average (voortschrijdend gemiddelde) van de eigen policy (continu bijgewerkt) in plaats van aan een vast punt of discrete snapshots, met als doel last-iterate convergentie te bereiken zonder annealing en de robuustheid van hyperparameters te verbeteren.

2. Methodologie: GARIP

GARIP (Generative Adversarial Reciprocal Iterative Play) is een update-regel die een optimistische gradiëntstap combineert met een Halpern-anker gericht naar het running average van de policy.

Update Mechanica

Voor een rij-speler met policy $x$ en tegenstander $y$ in een spel met payoff matrix $A$:

1. Optimistische Stap: De policy voert een optimistische entropische ascent-stap uit (vergelijkbaar met Optimistic Mirror Descent) met behulp van de huidige gradiënt en de vorige gradiënt om de zet van de tegenstander te anticiperen.
2. Halpern Anker: De bijgewerkte policy is een convexe combinatie van de optimistische stap en het running average $\bar{x}$:
   $$x_{t+1} = (1 - \beta) x_{t+1/2} + \beta \bar{x}_t$$
   waarbij $\beta \in (0, 1)$ een constante ankersterkte is (geen annealing).
3. Running Average Update: Het anker $\bar{x}$ wordt continu bijgewerkt (cumulatief gemiddelde in matrix-spellen, of Polyak exponentieel voortschrijdend gemiddelde in diepe RL).

Theoretische Motivatie

De methode wordt gemotiveerd door een "cyclus-consistentie" visie op nul-som spellen als een CycleGAN, waarbij het evenwicht het vaste punt is van de ronde route $F \circ G$. Ankeren aan het running average dwingt consistentie af met dit zelf-referentiële vaste punt. Mechanisch gezien is GARIP echter een optimistische mirror ascent samengesteld met een bewegend Halpern-anker; het optimaliseert niet een cyclus-consistentie verlies.

3. Belangrijkste Bijdragen en Theoretische Resultaten

A. Het "Peak Lag" Mechanisme van Collaps

Het artikel identificeert dat de faalmodus (collaps) van bewegende-referentiemethoden wordt gedreven door de peak lag van de referentie ten opzichte van de huidige policy.

• Staleness (Veroudering): Een referentie loopt achter op de huidige policy met $\ell$ stappen. Onder een regularisatiegewicht $\lambda$ oefent dit een herstellende kracht uit die proportioneel is aan $\lambda \cdot \ell$. Als deze kracht de spel-gradiënt overtreft, stort de policy in naar een exploiteerbare, verouderde staat.
• Sawtooth vs. Flat:
  • R-NaD (Snapshot): Houdt de referentie vast voor $K$ stappen, wat een zaagtand-lag profiel creëert. De peak lag is $K$, terwijl de gemiddelde lag $K/2$ is. Dus: Peak = 2 × Mean.
  • GARIP (Running Average): Het lag profiel is vlak (stationair). De peak lag is gelijk aan de mean lag.
• Propositie 1: Onder alle causale convexe gemiddelden met een vaste mean lag, minimaliseert het running average uniek de peak lag. De peak van een snapshot wordt strikt gedomineerd door een factor 2.

B. Convergentie Eigenschappen

• Lokale Last-Iterate Convergentie (Propositie 3): Het artikel bewijst dat voor een kleine ankersterkte $\beta$, de anker de rotatie-eigenwaarden van de basis-map schaalt met $(1-\beta)$. Dit kruist de stabiliteitsgrens, waardoor een recurrente (orbiterende) basis-map wordt omgezet in een contractie, wat lokale asymptotische stabiliteit bij het Nash-evenwicht garandeert zonder annealing.
• Onbevooroordeelde Vaste Punten (Propositie 2): In tegen tegenstelling tot MMD, dat convergeert naar een magneet-geregulariseerd evenwicht, verdwijnt de zelf-referentiële anker van GARIP bij elk vast punt. Daarom is elk intern vast punt een echt Nash-evenwicht.
• Globale Convergentie: Globale convergentie wordt geconstelleerd voor een kleine $\beta$. Het artikel merkt een "premature consensus" faalmodus op bij een grote $\beta$, waarbij de anker de policy en het gemiddelde te snel dwingt om overeen te stemmen op een suboptimaal punt, wat de progressie stopt.

C. Claim van Robuustheid

Het primaire voordeel van GARIP is hyperparameter robuustheid, niet peak performance.

• Omdat de peak lag van R-NaD (snapshot) tweemaal de mean lag is, zet een conventionele reset-periode $K$ (gekozen op basis van mean lag intuïtie) de peak lag onbedoeld op een gevaarlijk niveau.
• Het vlakke profiel van GARIP zorgt ervoor dat bij conventionele parametrisaties de peak lag laag blijft.
• Het artikel claimt dat GARIP de peak performance van R-NaD evenaart wanneer beide zijn afgestemd op hun beste prestaties, maar dat GARIP de superieure default is vanwege de bredere "safe basin".

4. Experimentele Resultaten

Matrix Games en Poker

• Matrix Games: GARIP bereikt bijna-Nash exploitability op willekeurige $10\times10$ en $12\times6$ spellen met standaardinstellingen, terwijl de standaardinstellingen van R-NaD significant achterblijven (vereisen tuning om te matchen). MMD vlakt af op het geregulariseerde evenwicht.
• Poker (Kuhn/Leduc): GARIP presteert beter dan R-NaD en MMD bij standaard tuning, en bereikt een exploitability die dicht bij exacte best-response fictitious play ligt.

Deep RL (Coin Game & Board Games)

• Coin Game: GARIP en R-NaD scoren gelijk in peak performance (beiden superieur aan fixed-magnet en magnet-free baselines).
• Board Games (Connect Four, Othello, Animal Shogi, Hex):
  • Cycling Games (Connect Four, Othello): Bewegende referenties (GARIP/R-NaD) zijn aanzienlijk robuuster dan baselines. GARIP wint licht van R-NaD op Othello.
  • Non-Cycling Game (Animal Shogi): Naïeve self-play convergeert natuurlijk. Hier is regularisatie onnodig en hindert het de prestaties licht, hoewel GARIP de beste regularisator blijft onder de geteste methoden.
  • Unlearnable Game (Hex): Alle methoden falen in het leren van robuuste strategieën door de complexiteit van het $11\times11$ bord, wat de limieten van de search-free learner bevestigt.

Hyperparameter Robuustheid (De Kernbevinding)

Het artikel voert een sweep uit over hyperparameters om de "collapse rates" (falen om te convergeren naar een robuuste policy) te meten.

• Full Grid: Over de gehele parameterruimte hebben GARIP en R-NaD statistisch ononderscheidbare geaggregeerde collapse rates (ongeveer 25% vs 32%). Beiden kunnen falen als ze tot extreme staleness worden gedreven.
• Conventionele Parametrisatie: Het cruciale verschil ligt in de locatie van de collapse boundary relatief aan standaard gebruik:
  • GARIP: Collapseert alleen bij zeer trage averaging rates ($\rho \le 0.005$). Bij de standaard $\rho = 0.01$ is de collapse rate 0/40 seeds.
  • R-NaD: Collapseert bij standaard reset-periodes. Bij $K=200$ is de collapse rate 10/40 seeds.
• Conclusie: De conventionele $K$ van R-NaD onderschat de peak lag met een factor 2, waardoor het in de gevarenzone terechtkomt. GARIP biedt een "safe by default" parametrisatie.

5. Betekenis en Claims

Het artikel positioneert GARIP niet als een methode die een hogere peak performance bereikt dan R-NaD, maar als een structureel superieure default voor niet-geanneleerde self-play.

• Structureel Voordeel: Het running average is de optimale referentievorm voor het minimaliseren van de peak lag onder causale gemiddelden. Dit maakt het inherent robuuster tegen de "staleness" faalmodus die snapshots teistert.
• Praktische Impact: Gebruikers hoeven niet de reset-periode $K$ voor R-NaD te verkorten om collaps te voorkomen; GARIP bereikt deze veiligheid automatisch met standaard parameters.
• Beperkingen:
  • Het artikel stelt expliciet dat het geen claim legt op superieure peak-performance boven getunede R-NaD.
  • Globale convergentie is een conjectuur; grote $\beta$ kan leiden tot premature consensus.
  • Het voordeel manifesteert zich alleen in games waar naïeve self-play cyclust; het biedt geen voordeel (en een lichte kost) in games die van nature convergeren.
  • De methode is niet immuun voor collaps; het verschuift simpelweg de collapse boundary naar minder voorkomende parameterregimes.

Het artikel concludeert dat voor diepe self-play in cycling nul-som spellen, het running average de geprefereerde referentie is, wat een "gratis" veiligheidsmarge biedt ten opzichte van de snapshot-aanpak.