CS Paper Radar

Why Alternation Speeds Up Counterfactual Regret Minimization?

Boning Li, Longbo Huang

cs.GT ·submitted 2026-10-15 14:27 UTC · v1
theory

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.

Comment
34 pages, 8 figures

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.GT cs.AIcs.MA ·2026-10-21 ·Boning Li, Longbo Huang
benchmarkcode/data similarity 0.71
Abstract · 35 pages, 5 figures

Heuristic solvers for general-sum extensive-form games produce a stream of iterates, and practice reports the NashGap of the returned profile. We ask what a solver can know about its own iterates from the regret accumulators and the terminal-distribution accumulators its updates already maintain. In two-player games the NashGap of a weighted average strategy equals, at the maximizing player, the weighted external regret plus a signed value correction. Bounding the regret by the running counterfactual-regret accumulator gives an online certificate whose cost per checkpoint is linear in the number of terminal histories. The certificate stays sound under alternating updates and in games with three or more players. The mismatch between what alternation evaluates and what the averages record enters as one signed comparator term, maximized in a single backward pass per player whose comparator weight is nonzero. The bound is read off the regret state, with no best response against the average. Run a portfolio of training-free regret-matching solvers, output the iterate with the smallest certificate, and verify that iterate once. On the benchmark's biased Leduc family a pool of sixteen training-free solvers, seven original and nine recent variants, solves $89\%$ of the $64$ instances at threshold $10^{-5}$ this way, matching the trajectory-minimum union of the solvers. The same protocol solves $92\%$ of the $64$ pre-registered held-out instances and $89\%$ again on a third set of $64$ instances that no earlier stage used. The zero-best-response certificate certifies all $57$ in-sample solves and all $57$ fresh ones, and $58$ of the $59$ held-out ones. Its exact-comparator refinement certifies every solve in the three sets. The certificate states both and attributes its bound. Code is available at https://github.com/lbn187/CertNE.

0.24

On the Convergence of Alternating Regret Matching Algorithms

cs.GT cs.LG ·2026-11-02 ·Anh Duc Nguyen, Ioannis Anagnostides, Brian Hu Zhang, Tuomas Sandholm
similarity 0.71
Abstract

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 lagging behind. In this paper, we address this gap by developing a systematic way of analyzing such algorithms. Our framework centers on an alternating analog of the RVU property that we introduce, which we use to obtain the optimal $T^{-1}$ average-iterate convergence within this family. In particular, we establish this for two simple variants of predictive regret matching$^+$: i) increasing-regret predictive regret matching$^+$ and ii) half-prediction regret matching$^+$. Interestingly, we find that half prediction is the unique prediction multiplier that satisfies our alternating RVU property, giving it a strong theoretical justification. Going beyond average-iterate convergence, we refine our framework to obtain $T^{-1/2}$ best-iterate convergence and further establish convergence of their strategy profiles to a single Nash equilibrium, without assuming equilibrium uniqueness. We go on to establish separations between alternating and simultaneous updates, including a game in which half-prediction regret matching$^+$ converges under alternating updates but fails to converge in terms of the last iterate under simultaneous updates. This provides theoretical support for the empirical observation that alternation can stabilize learning dynamics. Finally, experiments on 15 game benchmarks demonstrate that the strong theoretical properties of the half-prediction mechanism translate to strong practical performance, being on par with state-of-the-art solvers.

0.13

A Horizon-Independent Regret Bound for Optimistic Hedge in General-Sum Games

cs.GT cs.LG ·2026-09-19 ·Junsoo Ha
theory similarity 0.67
Abstract

Can simple learning rules keep their regret bounded in self-play? Recent work achieves constant regret bounds through modified regularization and higher-order prediction. Yet for Optimistic Hedge, arguably the most canonical method in games, the best known individual regret bound remains logarithmic. In this work, we prove that plain Optimistic Hedge with a constant step size can attain $O_{n,d}(1)$ individual regret in general-sum games with $n$ players and $d=(d_1,\ldots,d_n)$ actions, under expected loss-vector feedback. As a corollary, its time-averaged play enjoys an $O_{n,d}(1/T)$ coarse correlated equilibrium (CCE) gap. Our analysis represents Optimistic Hedge as a real-analytic recurrence on a compact space, which yields an exact finite-order difference relation that eliminates horizon dependence. Our proof hinges on nonconstructive Noetherianity argument of Frisch (1967), so the $(n,d)$-dependence remains implicit.

0.35

Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits

cs.LG ·2026-09-15 ·Zhaojun Peng
benchmarktheory similarity 0.67
Abstract · 90 pages, 18 figures

Decentralized bandit systems often contain heterogeneous agents: rewards can change at individual agents even when the best action for the network stays the same. These local changes may cancel when rewards are averaged across agents, so the number of local changes $\Stloc$ can be much larger than the number of changes in the best common arm $\Stdec$. We introduce Decision-Relevant Fresh Comparison (DRFC), which uses new, balanced samples from all agents to compare arms at the network level and switches only when fresh global evidence indicates that the common best arm has changed. We prove a high-probability dynamic regret bound with no adaptation term depending on $\Stloc$, and show that every algorithm must still pay for identifying genuine decision switches and propagating them through the communication graph. Under a distinct time-average benchmark, an anytime-valid sliding-window extension handles gradual drift; experiments on synthetic, semi-real, and MovieLens-1M replays show that DRFC ignores decision-irrelevant local changes while the extension avoids false switches.

0.23

Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation

cs.LG cs.GT ·2026-11-04 ·Yuval Dagan, Nadav Eisen, Liad Erez, Tomer Koren
theory similarity 0.67
Abstract

Optimistic Hedge, a multiplicative weight update with one step of extrapolation, is one of the most natural regret-minimizing dynamics for games, and characterizing its regret has been a longstanding open question. Daskalakis, Fishelson and Golowich proved that if all $m$ players in a finite general-sum game follow Optimistic Hedge with a fixed learning rate, each player's regret is polylogarithmic in the horizon $T$. Subsequently, Ha showed that an appropriate choice of learning rate makes each player's regret bounded independently of $T$. This bound, however, is non-constructive and its dependence on the number of actions $n$ is not explicit, leaving open whether Optimistic Hedge can achieve a constant regret bound which is polynomial in the size of the game. We show that the answer hinges on the number of players. In two-player games, there is a learning rate for which Optimistic Hedge guarantees $O(n\log n)$ regret independent of the horizon. In three-player games, however, no such bound is possible: for any learning rate up to an absolute constant and for sufficiently large horizon $T$, there is a game with $n$ actions per player in which some player's regret is $2^{Ω(n)}$, and more generally, for every $m\ge3$ we construct $m$-player games in which some player's regret is $2^{Ω(mn)}$; for learning rates above $2^{-Ω(mn)}$, that player's regret even grows linearly in $T$. Our upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge. Starting from the variance-based RVU bound of Daskalakis et al., we approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance. In $m$-player games, the same framework gives a significantly simplified proof of the recent $O(\sqrt{m}\log n\log T)$ regret bound due to Ha.

0.16

Logarithmic Regret for Alternating Mirror Descent

cs.LG cs.GTmath.OCstat.ML ·2026-11-03 ·Tianlong Nan, Christian Kroer
similarity 0.66
Abstract

Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained $O(T^{1/3})$ and $O(T^{1/5})$ regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether AltOMD achieves near-constant regret has remained an open question. In this paper we resolve the question of whether AltOMD achieves near-constant regret in the affirmative. In particular, we show an $O(log(T))$ regret bound on the sum of the players' external regrets for any two-player zero-sum bilinear game with compact convex strategy sets, under mild regularity assumptions on the regularizers. We verify that our assumptions hold for the negative entropy regularizer, thereby obtaining logarithmic regret for the alternating multiplicative weights updates algorithm. The regret bound also yields an $O(log(T)/T)$ duality gap bound for the averaged strategies.

0.14

Why Last-Iterate Scale-Invariant Regret Matching Converges Linearly?

cs.GT ·2026-09-29 ·Boning Li, Longbo Huang
theorycode/data similarity 0.65
Abstract · 50 pages, 2 figures

IREG-PRM+ normalizes the cumulative regret vector by its own norm and attains optimal regret without knowledge of the payoff scale. Run unmodified on zero-sum matrix games, it converges linearly in the last iterate, and no analysis explains why. The obstacle is that the algorithm has no fixed step size to analyze: the step size is a state variable, the inverse of a regret norm that the trajectory itself moves. Every proved linear rate for regret-matching dynamics comes from restarting or modifying the update. We identify the mechanism as norm saturation: the regret norm rises to a finite limit and freezes the step size. We prove that it always does, with an explicit bound, and that saturation forces the last-iterate Nash gap to vanish on every matrix game; pointwise convergence follows whenever the equilibrium is unique. Near a unique strictly complementary equilibrium the active support freezes in one step, and the one-round Jacobian on that support has a closed form. The last-iterate then converges linearly at a closed-form rate, provided one scale-invariant quantity stays below one: the saturated step size times the largest singular value of the value-centered payoff submatrix on the support. On the $216$-instance testbed, the $184$ instances with a resolvable limit all satisfy it. The same analysis gives a ratio certificate: observable norm-increment ratios bound the unobservable Nash-gap ratio up to a constant that enters once and does not accumulate with the iteration count. Its slope-two law holds on $96.1\%$ of the instances where the slope is measurable, and the same increment monitors progress in extensive-form games, where best-response passes can be scheduled sparsely. The code is available at https://github.com/lbn187/NormCert.

0.63

Multiplicative Optimism for Constant Regret in Games

cs.GT cs.LGmath.OC ·2026-09-18 ·Ashkan Soleymani, Georgios Piliouras
similarity 0.65
Abstract

We introduce Multiplicatively Optimistic Regret Matching (MORM), an uncoupled learning rule for finite general-sum games. Under simultaneous full-information self-play, every player achieves external regret $O(\sqrt n\log d)$ uniformly over all horizons, using only one-step optimism. The analysis combines a potential-based regret-matching argument with multiplicative stability and Hellinger control of strategy movement. A learning-rate safeguard additionally gives $O(\sqrt{T\log d})$ regret in the face of adversarial utilities.

0.40