On the Convergence of Alternating Regret Matching Algorithms

Anh Duc Nguyen; Ioannis Anagnostides; Brian Hu Zhang; Tuomas Sandholm

cs.GTNov 2, 2026

On the Convergence of Alternating Regret Matching Algorithms

Authors: Anh Duc Nguyen, Ioannis Anagnostides, Brian Hu Zhang, Tuomas Sandholm

Organizations: Carnegie Mellon University, Computer Science Department · Massachusetts Institute of Technology · Additional affiliations: Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc.

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.

Figures & tables

Figure 1:

\texttt{Alt-PRM}^{+}

on the normal-form game ( 20 ).

Figure 2:

\texttt{Alt-HPRM}^{+}

on the normal-form game ( 20 ).

Figure 3: The construction of Proposition 6.1 with 2 actions.

Figure 4: Average-iterate and last-iterate gaps under alternating self-play. Half prediction is compared with

\lambda=10^{-4}

on the

3\times 3

game of Cai et al. (2025) (with the payoff matrix negated to match our maximizing-row convention),

\lambda=10^{-2}

on a

11,002\times 11,002

block game, and

\lambda=1/3

on a

177,702\times 177,702

block game. The gray lines indicate the reference slopes

T^{-1/2}

and

T^{-1}

Figure 5: Runtime and iteration ratios ( $\texttt{Alt-PCFR}^{+}/\texttt{Alt-HPCFR}^{+}$ ) to reach target exploitability. Values larger than $1$ mean that $\texttt{Alt-HPCFR}^{+}$ outperforms $\texttt{Alt-PCFR}^{+}$ .

	Recorded runtime		Iteration count
Algorithm	Top 1	Top 3	Top 1	Top 3
$\texttt{Alt-HPCFR}^{+}$	14 (11 sole, 3 ties)	30	10 (9 sole, 1 tie)	28
$\texttt{Alt-SAPCFR}^{+}$	10 (7 sole, 3 ties)	24	10 (6 sole, 4 ties)	22
$\texttt{Alt-PCFR}^{+}$	5 (4 sole, 1 tie)	21	3 (3 sole, 0 ties)	19
$\texttt{Alt-PDCFR}^{+}$	3 (3 sole, 0 ties)	11	6 (6 sole, 0 ties)	19
$\texttt{Alt-IR-PCFR}^{+}$	0 (0 sole, 0 ties)	9	2 (0 sole, 2 ties)	17

Table 1: Top-one and top-three placements across the 33 game-threshold comparisons.

Figure 6: Last-iterate convergence against iteration count.

Figure 7: HS30 average convergence against iteration count.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 8: Last-iterate gap for

\lambda=1/3

on the

177{,}702\times 177{,}702

block game over three late windows of

200{,}000

iterations, with identical axis scales. Circles mark the minimum gap within each complete cycle, defined by consecutive upward crossings of gap

10

. Incomplete cycles at the window boundaries are displayed but excluded from cycle averages.

Figure 9: Half prediction under simultaneous and alternating updates (stars mark the equilibrium, and open markers denote iteration 2). (a) Simultaneous strategy trajectories. (b) Alternating trajectories, enlarging the dashed triangular region in (a). (c) Joint Euclidean distance to equilibrium.

Game	Histories	Information sets	Terminal histories	No. of iterations
Kuhn poker	58	12	30	200
GoofspielImp (4 cards)	1,077	162	576	500
Liar’s Dice (4 sides)	8,181	1,024	4,080	1000
Leduc poker	9,457	936	5,520	50000
GoofspielImp (5 cards)	26,931	2,124	14,400	50000
Liar’s Dice (5 sides)	51,181	5,120	25,575	50000

Appendix

Table 2: Benchmark games (the number of information sets counts those of both players).

Figure 10: Average-iterate convergence against iteration count.

Figure 11: Last-iterate convergence against learner wall time.

Figure 12: HS30 average convergence against learner wall time.

Figure 13: Average-iterate convergence against learner wall time.

Regret Minimization

Regret minimization studies how to make sequential decisions whose cumulative loss or reward approaches the best available comparator in hindsight.

See all 119 papers

IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence
Oct 13, 2026Michael Sullins, Ian A. KashCounterfactual Regret Minimization Regret Minimization
University of Illinois Chicago, Chicago, Illinois, USA
Logarithmic Regret for Alternating Mirror Descent
Nov 3, 2026Tianlong Nan, Christian KroerRegret Minimization Online Mirror Descent
Columbia University, Department of Industrial Engineering and Operations Research.
Optimal Alternating Regret for Online Learning and Games
Aug 25, 2026Yixin Tao, Weiqiang ZhengOnline LP Online Convex Optimization
ITCS, Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics · Yale University

Oct 13, 2026J/K move · Enter open · S save

IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

Michael Sullins, Ian A. Kash

University of Illinois Chicago, Chicago, Illinois, USA

Counterfactual Regret Minimization Regret Minimization Nash Equilibrium Computation Zero-Sum Games Imperfect-Information Games

Open paper AskPDF arXiv

Regret matching (and its variants) and counterfactual regret minimization are central algorithms in practice for normal-form and extensive-form game solving. Yet these have historically lacked the stronger theoretical convergence guarantees available to optimistic and extra-gradient methods. Recent work introduced IREG-PRM+, a regret matching variant which does have strong theoretical convergence guarantees. However, it relies on a simultaneous, extra-gradient update. IREG-PRM+ is an instance of the more general IR-PRM framework, where empirically optimistic and alternating updates often have better performance. However, the prior extra-gradient analysis does not extend to these cases. We introduce a new approach that covers both settings. For simultaneous and alternating IR-PRM+ in finite two-player zero-sum matrix games, previous-utility prediction recovers the constant-regret and convergence-rate guarantees previously obtained with extra-gradient prediction: external regret bounded independently of T, an O(T^{-1}) average duality gap, and an O(T^{-1/2}) best-current-iterate gap. Moreover, the current duality gap vanishes and the current profile converges to the Nash equilibrium set. The key step bounds the component of consecutive strategy movement not controlled by the existing IR-PRM+ regret inequality using the relative growth of the nondecreasing regret-vector norm rho_t. Coupling this bound across the two players yields recurrences whose effective coefficient scales as 1/(rho_t^X rho_t^Y), preventing unbounded norm growth. We extend the analysis to finitely many simplex learners under a weighted Minty condition and, through the corresponding CFR variant IR-PCFR+, recover analogous guarantees for finite two-player zero-sum perfect-recall extensive-form games under the same full-reach condition as prior work.

Abstract

Regret Minimization

Explore similar work

IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

Logarithmic Regret for Alternating Mirror Descent

Optimal Alternating Regret for Online Learning and Games