Skip to content
Preprint

Why Alternation Speeds Up Counterfactual Regret Minimization?

Oct 2026 · 2 citations · 64 references
Computer Science

Abstract

Solving imperfect-information games at scale rests on counterfactual regret minimization with the regret matching$^{+}$ (RM$^{+}$) update, and a seemingly minor implementation choice accounts for much of its practical speed: alternating the two players'updates, so that the second player responds to the strategy the first player just produced. A widely repeated intuition explains why: seeing the opponent's fresh strategy should act like optimism. We treat this intuition as a testable hypothesis about deterministic two-player zero-sum self-play dynamics and find that its canonical additive form fails an information-matched test. On an analytic witness family we compare alternating RM$^{+}$ against a one-sided predictive RM$^{+}$ that receives the same information channel each round and differs only in where the fresh signal enters, a persistent regret state versus a transient prediction term. Our main result is a dichotomy theorem that reduces trajectory separation to the recurrence of exact-vertex play by the predictive dynamics: under an interior-band assumption on the alternating iterate, either vertex times recur and the profile distance is at least, infinitely often, an explicit constant that our measurements nearly attain, or they terminate. Across the tested self-play regimes, any correct explanation of the alternation speedup must reproduce a staleness cost present at the smallest tested stale fraction, an advantage that persists across seven orders of payoff conditioning, regime crossings of the optimism family, and a measured per-perturbation cost of weakening the injection path that is far steeper for staleness than for partial persistence.

View source

Similar papers

Preprint Oct 2026

Noise Shapes the Surplus: Strategic Play Against No-Regret Learners

Recent work has shown that, in zero-sum games, an optimizer can extract $\Omega(\sqrt{T})$ strategic surplus---cumulative payoff above the minimax benchmark---against noiseless no-regret learners with a constant step size. However, in practice, learners often act on perturbed payoff scores and use decaying learning rat...

Yi-Heng Su, Emmanouil-Vasileios Vlatakis-Gkaragkounis · 0 citations

Constant Swap Regret in General-Sum Games via Two-Scale Higher-Order Optimism

We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret in self-play, independent of the horizon $T$. With $n$ players and at most $m$ actions each, every player's individual swap regret is $O(\sqrt n\,m\...

Tung Mai · 2 citations
Preprint Oct 2026

When Are We Near Nash? Certifying Solutions in General-Sum Games

This work asks what a solver can know about its own iterates from the regret accumulators and the terminal-distribution accumulators its updates already maintain, and produces a portfolio of training-free regret-matching solvers.

Bo-Ning Li, Long-Bo Huang · 0 citations

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with $d$ actions per player, we develop an algorithm achieving a duality gap of $\widetilde{\mathcal{O}}(\sqrt{d/t})$ with high probability, simultaneously at every round $t...

Yu-Heng Zhang · 1 citation
#machine learning Preprint Oct 2026

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

We study causal logistic bandits with counterfactual fairness constraints. The causal structure is given through known factual and counterfactual feature maps that share an unknown logistic reward parameter, but the learner observes only factual rewards. Consequently, the directions determining counterfactual feasibili...

Junhyuk Huh, Seoungbin Bae, Dabeen Lee · 0 citations
Preprint Nov 2026

On the Convergence of Alternating Regret Matching Algorithms

Alternating updates, that is, where each player is updated in turn, tend to typically perform better in regret matching algorithms than simultaneous updates. Alternation within the regret matching family has long been a central ingredient of practical solvers for zero-sum games. Yet our theoretical understanding is lag...

Anh Duc Nguyen, I. Anagnostides, B. Zhang et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.