💻 computer science

GARIP: A Running-Average Moving Reference for Last-Iterate Self-Play in Two-Player Zero-Sum Games

The paper introduces GARIP, a self-play method that anchors policy updates to a running average reference to uniquely minimize reference lag and ensure local last-iterate convergence, demonstrating superior robustness and stability compared to fixed or snapshot-based baselines across various two-player zero-sum games.

Original authors: Can Savcı

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Can Savcı

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine two people playing a high-stakes game of rock-paper-scissors, but they are trying to learn the perfect strategy by playing against themselves over and over again.

In the old way of doing this (called "naive self-play"), the players get stuck in a loop. They keep circling around the perfect answer, never quite landing on it, like a car driving in circles around a roundabout but never exiting.

This paper introduces a new method called GARIP to help these players stop circling and actually reach the perfect strategy. Here is how it works, using simple analogies.

The Problem: The "Stale" Reference

To stop the circling, modern methods tell the player: "Don't just look at your last move; look at a 'reference' move from the past and try to stay close to it." This reference acts like a magnet pulling the player toward a stable spot.

However, there is a catch: How old is that reference?

If the reference is too old (stale), the player gets dragged back to a bad strategy they abandoned long ago.
If the reference is too new, it doesn't help stop the circling.

The Two Competitors: The Snapshot vs. The Running Average

The paper compares two ways of choosing this "reference":

The Snapshot (R-NaD): Imagine a coach who takes a photo of the player's strategy, puts it in a frame, and says, "Stick to this photo for the next 200 moves."
- The Flaw: For the first 199 moves, the player is following a photo that gets older and older. By move 200, the photo is very "stale." Then, the coach takes a new photo and the cycle repeats. This creates a "sawtooth" pattern: the reference is fresh, then gets very old, then gets reset. The paper proves that this "peak staleness" (the oldest the photo gets) is twice as bad as the average age of the photo.
The Running Average (GARIP): Imagine a coach who constantly updates a "mental average" of everything the player has done. Instead of a single photo, the coach says, "Stay close to the average of your entire history so far."
- The Advantage: This average is always "fresh" in a way. It doesn't have those sharp spikes where the reference gets extremely old. It has a "flat" profile. The paper mathematically proves that among all ways to look at the past, this "flat" average is the most efficient at keeping the reference from getting too stale.

The Big Discovery: Why GARIP is the Better Default

The paper claims that both methods can reach the perfect strategy if you tune them perfectly. However, GARIP is much more forgiving.

The Trap: With the "Snapshot" method, if you accidentally choose a reset time that is a little too long (e.g., 200 moves instead of 100), the "stale" reference becomes so old that the player collapses into a bad strategy.
The Safety Net: With GARIP, because the reference is a smooth average, it doesn't have those dangerous "spikes" of staleness. Even if you pick a standard setting, it stays safe.

The Analogy:
Think of the "Snapshot" method like a person holding a heavy weight on a rope. If they let the rope go too long before pulling it back, the weight swings wildly and hits them.
Think of GARIP like a person holding a weight on a spring. The spring absorbs the movement smoothly. Even if they don't pull it perfectly, the spring keeps the weight from swinging out of control.

What the Experiments Showed

The researchers tested this on:

Simple math games (Matrix games).
Card games (Poker).
Board games (Connect Four, Othello).

The Results:

Peak Performance: If you tune both methods perfectly, they perform about the same.
Robustness (The Real Winner): In the real world, where you don't have time to perfectly tune every setting, GARIP wins. It fails much less often.
- On board games like Connect Four, the "Snapshot" method failed 25% of the time with standard settings, while GARIP failed 0% of the time.
- GARIP only fails if you make the "average" update incredibly slow (like looking at a history from 1,000 moves ago), which is a setting nobody would naturally choose.

The Limits

The paper is honest about where GARIP doesn't work:

No Magic: It doesn't make the player unbeatable if the game is too complex for the computer to learn (like the game Hex on a large board).
No Cycles Needed: If a game naturally converges without help (like a small game called Animal Shogi), adding this "magnet" doesn't help and might even slow the player down.
Local Success: The math proves it works well locally (near the solution), but the paper admits it's a conjecture that it works from any starting point, though experiments suggest it does.

Summary

GARIP is a new way for AI to learn games by constantly averaging its own past moves. It is mathematically proven to be the most stable way to do this because it avoids the "spikes" of staleness that plague other methods. It is the "safe default" choice: it performs just as well as the best existing methods when tuned perfectly, but it is much harder to mess up.

Technical Summary: GARIP – A Running-Average Moving Reference for Last-Iterate Self-Play

1. Problem Statement

In two-player zero-sum games, standard self-play using naive gradient ascent (SGA) fails to converge in the last iterate; instead, the trajectory orbits the Nash equilibrium on a closed conservative field. While time-averaged policies converge, modern deep multi-agent reinforcement learning (RL) relies on the final network parameters, making last-iterate behavior critical.

Existing methods attempt to restore last-iterate convergence by regularizing the policy toward a reference ("magnet") to break conservative rotations:

MMD: Uses a fixed reference (e.g., uniform). It converges to a regularized equilibrium (Quantal Response Equilibrium), requiring annealing of the regularization to reach the true Nash.
R-NaD: Uses a periodic snapshot of the current policy (reset every $K$ steps). It reaches Nash without annealing and powers systems like DeepNash.
Fictitious Play: Best-responds to the average opponent but lacks a self-anchor.

The paper identifies a gap in the design space: a method that anchors to the policy's own running average (continuously updated) rather than a fixed point or discrete snapshots, aiming to achieve last-iterate convergence without annealing while improving hyperparameter robustness.

2. Methodology: GARIP

GARIP (Generative Adversarial Reciprocal Iterative Play) is an update rule that combines an optimistic gradient step with a Halpern anchor directed toward the policy's running average.

Update Mechanics

For a row player with policy $x$ and opponent $y$ in a game with payoff matrix $A$ :

Optimistic Step: The policy takes an optimistic entropic ascent step (similar to Optimistic Mirror Descent) using the current gradient and the previous gradient to anticipate the opponent's move.
Halpern Anchor: The updated policy is a convex combination of the optimistic step and the running average $\bar{x}$ :
$x_{t+1} = (1 - \beta) x_{t+1/2} + \beta \bar{x}_t$
where $\beta \in (0, 1)$ is a constant anchor strength (no annealing).
Running Average Update: The anchor $\bar{x}$ is updated continuously (cumulative mean in matrix games, or Polyak exponential moving average in deep RL).

Theoretical Motivation

The method is motivated by a "cycle-consistency" view of zero-sum games as a CycleGAN, where the equilibrium is the fixed point of the round trip $F \circ G$ . Anchoring to the running average enforces consistency with this self-referential fixed point. Mechanically, however, GARIP is an optimistic mirror ascent composed with a moving Halpern anchor; it does not optimize a cycle-consistency loss.

3. Key Contributions and Theoretical Results

A. The "Peak Lag" Mechanism of Collapse

The paper identifies that the failure mode (collapse) of moving-reference methods is driven by the peak lag of the reference relative to the current policy.

Staleness: A reference lags the current policy by $\ell$ steps. Under a regularization weight $\lambda$ , this exerts a restoring force proportional to $\lambda \cdot \ell$ . If this force overwhelms the game gradient, the policy collapses to an exploitable, stale state.
Sawtooth vs. Flat:
- R-NaD (Snapshot): Holds the reference fixed for $K$ steps, creating a sawtooth lag profile. The peak lag is $K$ , while the mean lag is $K/2$ . Thus, Peak = 2 × Mean.
- GARIP (Running Average): The lag profile is flat (stationary). The peak lag equals the mean lag.
Proposition 1: Among all causal convex averages with a fixed mean lag, the running average uniquely minimizes the peak lag. A snapshot's peak is strictly dominated by a factor of 2.

B. Convergence Properties

Local Last-Iterate Convergence (Proposition 3): The paper proves that for small anchor strength $\beta$ , the anchor scales the base map's rotation eigenvalues by $(1-\beta)$ . This crosses the stability boundary, turning a recurrent (orbiting) base map into a contraction, ensuring local asymptotic stability at the Nash equilibrium without annealing.
Unbiased Fixed Points (Proposition 2): Unlike MMD, which converges to a magnet-regularized equilibrium, GARIP's self-referential anchor vanishes at any fixed point. Thus, every interior fixed point is a true Nash equilibrium.
Global Convergence: Global convergence is conjectured for small $\beta$ . The paper notes a "premature consensus" failure mode at large $\beta$ , where the anchor forces the policy and average to agree too quickly on a suboptimal point, stalling progress.

C. Robustness Claim

The primary advantage of GARIP is hyperparameter robustness, not peak performance.

Because R-NaD's peak lag is twice its mean lag, a conventional reset period $K$ (chosen based on mean lag intuition) inadvertently sets the peak lag to a dangerous level.
GARIP's flat profile ensures that at conventional parameterizations, the peak lag remains low.
The paper claims GARIP matches R-NaD's peak performance when both are tuned to their best, but GARIP is the superior default because its "safe basin" is wider.

4. Experimental Results

Matrix Games and Poker

Matrix Games: GARIP achieves near-Nash exploitability on random $10\times10$ and $12\times6$ games at default settings, whereas R-NaD's default settings trail significantly (requiring tuning to match). MMD plateaus at the regularized equilibrium.
Poker (Kuhn/Leduc): GARIP outperforms R-NaD and MMD at default tuning, reaching exploitability close to exact best-response fictitious play.

Deep RL (Coin Game & Board Games)

Coin Game: GARIP and R-NaD tie in peak performance (both far superior to fixed-magnet and magnet-free baselines).
Board Games (Connect Four, Othello, Animal Shogi, Hex):
- Cycling Games (Connect Four, Othello): Moving references (GARIP/R-NaD) are significantly more robust than baselines. GARIP edges out R-NaD slightly on Othello.
- Non-Cycling Game (Animal Shogi): Naive self-play converges naturally. Here, regularization is unnecessary and slightly handicaps performance, though GARIP remains the best regularizer among the tested methods.
- Unlearnable Game (Hex): All methods fail to learn robust strategies due to the complexity of the $11\times11$ board, confirming the limits of the search-free learner.

Hyperparameter Robustness (The Core Finding)

The paper conducts a sweep over hyperparameters to measure "collapse rates" (failure to converge to a robust policy).

Full Grid: Over the entire parameter space, GARIP and R-NaD have statistically indistinguishable aggregate collapse rates (approx. 25% vs 32%). Both can fail if pushed to extreme staleness.
Conventional Parameterization: The critical difference lies in the location of the collapse boundary relative to standard usage.
- GARIP: Collapses only at very slow averaging rates ( $\rho \le 0.005$ ). At the standard $\rho = 0.01$ , collapse rate is 0/40 seeds.
- R-NaD: Collapses at standard reset periods. At $K=200$ , collapse rate is 10/40 seeds.
Conclusion: R-NaD's conventional $K$ under-counts its peak lag by a factor of 2, placing it in the danger zone. GARIP provides a "safe by default" parameterization.

5. Significance and Claims

The paper positions GARIP not as a method that achieves higher peak performance than R-NaD, but as a structurally superior default for non-annealed self-play.

Structural Advantage: The running average is the optimal reference shape for minimizing peak lag among causal averages. This makes it inherently more robust to the "staleness" failure mode that plagues periodic snapshots.
Practical Impact: Users do not need to know to shorten the reset period $K$ for R-NaD to avoid collapse; GARIP achieves this safety automatically with standard parameters.
Limitations:
- The paper explicitly states it does not claim peak-performance superiority over tuned R-NaD.
- Global convergence is a conjecture; large $\beta$ can cause premature consensus.
- The advantage only manifests in games where naive self-play cycles; it offers no benefit (and slight cost) in games that naturally converge.
- The method is not immune to collapse; it simply shifts the collapse boundary to less common parameter regimes.

The paper concludes that for deep self-play in cycling zero-sum games, the running average is the preferred reference, offering a "free" safety margin over the snapshot approach.