acceptodds
Under review as a conference paper at ICLR 2027

Norm Saturation Explains Last-Iterate Convergence in Regret Matching

Abstract

Regret matching is the update at the core of counterfactual regret minimization; its guarantees concern the average of all strategies played, and for regret matching the last iterate may not converge at all. Scale-invariant extragradient regret matching (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 -instance testbed, the 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 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.

Primary area:
learning theory
Keywords:
Scale-invariant regret matching, Last-iterate convergence, Extensive-form games, CFR

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_qHScOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studys the last-iterate convergence behavior of IREG-PRM+, a scale-invariant, parameter-free regret-matching algorithm introduced by Zhang et al. (2025a). The paper attributes its observed convergence behavior to norm saturation, namely, the monotonic convergence of the cumulative regret norms to finite limits. The paper first establishes boundedness of the regret norms and asymptotic convergence of the last-iterate Nash gap for arbitrary two-player zero-sum matrix games. When the Nash equilibrium is unique, it further establishes pointwise convergence of the regret states and strategies. Under additional assumptions of a unique, strictly complementary equilibrium and a spectral step-size condition, the authors derive a closed-form Jacobian for the local dynamics and establish a conditional local linear convergence rate. Finally, the paper develops a local relationship between squared regret-norm increments and the squared Nash gap, leading to a ratio-based convergence certificate. The theoretical findings are evaluated on 216 matrix games, with additional empirical studies on Kuhn and Leduc poker.

Critical strengths

The paper provides a technically interesting analysis of the update map near Nash equilibria. The local equivalence between squared regret-norm increments and the squared Nash gap is an interesting observation. Unlike directly evaluating exploitability, norm-increment information is already available from the algorithm's internal updates. This could be useful in extensive-form games, where evaluating best responses is more expensive.

Critical weaknesses

The central norm-saturation property appears to follow largely from the existing analysis of Zhang et al. (2025a), which already establishes monotonicity of the regret norms and bounded second-order path length. The current paper acknowledges that Theorem 1 restates earlier boundedness results with an explicit constant. More importantly, the last-iterate Nash-gap convergence in Theorem 2 also appears derivable from the original paper's results. Specifically, Theorem 5.5 of Zhang et al. establishes summability of the squared differences between the main iterates and pre-iterates. Together with their Assumption 5.6 and Lemma D.2 (the one-step improvement property), this appears to imply that the best-response residual at the pre-iterate tends to zero. Under extragradient self-play in zero-sum matrix games, the sum of the two residuals equals the Nash gap. The difference between the pre-iterates and main iterates also vanishes, yielding last-iterate Nash-gap convergence. This argument directly covers the eventual positive-norm regime; special zero-norm cases may require separate treatment. Nevertheless, it suggests that the main conclusion of Theorem 2 is already a relatively direct consequence of existing results. Once Nash-gap convergence is established, Theorem 3 follows naturally from equilibrium uniqueness, compactness, and convergence of the regret norms. Thus, while these results are explicitly formulated and carefully proved, their independent theoretical novelty appears limited. The paper should more clearly distinguish genuinely new results from consequences of the original IREG-PRM+ analysis.

Questions for authors

Theorem 4 additionally requires η∞σmax(B)<1\eta_\infty \sigma_{\textrm{max}}(B)<1 where η∞\eta_\infty depends on the regret-norm saturation levels selected by the actual trajectory.

Although the paper proves that these saturation levels exist, it does not establish that they necessarily satisfy the spectral condition. Can the authors explain the behavior of IREG-PRM+ on the family Aλ=uu⊤+λvv⊤A_\lambda=uu^\top+\lambda vv^\top, where u=(1,−1,−1)⊤u=(1,-1,-1)^\top and v=(0,1,−1)⊤v=(0,1,-1)^\top? The standard zero-initialized trajectory remains in the invariant subspace r2=r3r_2=r_3 and is independent of λ\lambda, while the maximum singular value grows as 2λ2\lambda. Consequently, for sufficiently large λ\lambda, the trajectory converges to a unique, strictly complementary equilibrium with η∞σmax⁡(B)>1\eta_\infty\sigma_{\max}(B)>1. How does the proposed self-stabilization mechanism account for this behavior?

Reviewer_ZgveOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates the last-iterate convergence of IREG-PRM$^+$, a scale-invariant extra-gradient regret-matching algorithm that does not use restarts, smoothing, or an explicitly prescribed step size. The central insight is that the cumulative regret norms act as state-dependent inverse step sizes and eventually converge to finite limits, a phenomenon the authors call norm saturation. Concretely, this paper makes three main theoretical contributions. First, it establishes that norm saturation occurs on every zero-sum matrix game and proves that the last-iterate Nash gap converges to zero without requiring uniqueness, strict complementarity, or a spectral condition. When the Nash equilibrium is unique, the entire strategy trajectory converges pointwise to that equilibrium. Second, under a unique strictly complementary equilibrium and an additional spectral step-size condition, the authors derive a closed-form local linear last-iterate convergence rate. Third, they establish a ratio certificate relating changes in the squared regret norms to changes in the Nash gap, suggesting that an observable quantity already computed by the algorithm can be used to monitor convergence. The experiments on 216 randomly generated matrix games report close agreement between predicted and measured local convergence rates and support the predicted slope-two relationship between norm increments and the Nash gap.

Critical strengths

1: A meaningful global last-iterate convergence result for the latest parameter-free and scale-invariant regret matching algorithm. The paper establishes that the last-iterate Nash gap converges to Nash Equilibrium for two-player zero-sum matrix games, without requiring a unique equilibrium assumption or the spectral condition used in the local analysis. It further proves pointwise convergence when the equilibrium is unique. This is, to my knowledge, the first global last-iterate convergence guarantee (although is asymptotic) of this kind for a parameter-free, scale-invariant RM algorithm.

2. An explicit local spectral characterization and an explicit last-iterate convergence rate. The derivation of the support-restricted Jacobian and its closed-form spectrum is technically interesting. The resulting explicit last-iterate convergence rate identifies the quantity η∞σmax⁡(B)\eta _\infty \sigma_{\max}(B) as the decisive local stability parameter. The paper also connects squared-norm increments to the squared Nash gap, providing a principled explanation for why these increments can serve as a progress indicator.

3. Extensive empirical evaluations. The reported agreement between theoretical predictions and measured behavior across many matrix-game instances lends support to the proposed mechanism.

Critical weaknesses

My main concerns are centered on the assumptions required to establish the explicit linear last-iterate convergence rate of IREG-PRM+^+, as detailed below.

1. Limited justification for the unique, strictly complementary equilibrium assumption.

Theorem 4 relies heavily on Assumption 1, which requires the existence of a unique, strictly complementary Nash equilibrium (NE). While this is a mathematically meaningful regularity condition, the paper does not sufficiently discuss the class of matrix games for which it holds or its implications for games with non-unique or degenerate equilibria.

In particular, the authors do not provide a concrete payoff matrix AA to illustrate Assumption 1 and its role in the convergence analysis. Such an example would help readers understand the applicability of the theoretical results and the extent to which the assumption restricts the class of games under consideration.

Since the explicit linear last-iterate convergence analysis in Theorem 4 constitutes a substantial portion of the paper's theoretical contributions, I believe a more thorough justification of Assumption 1 and a discussion of its limitations are necessary. Without such clarification, it is difficult to assess how broadly the claimed linear convergence rate applies beyond the regular setting considered in the theorem.

2. Insufficient theoretical justification for the spectral step-size condition in Assumption 2.

Another critical concern is Assumption 2, which requires the limiting step size and the largest singular value of the value-centered payoff matrix to satisfy

$ \eta_\infty \sigma_{\max}(B)<1.$

This condition is essential for establishing the linear last-iterate convergence rate in Theorem 4. However, the paper does not prove that IREG-PRM+^+, when initialized and executed according to its standard implementation, necessarily converges to a limiting state satisfying this condition.

Although the experiments provide encouraging evidence that the condition holds on the tested instances, empirical observations alone cannot establish that it is guaranteed by the algorithm's dynamics. Moreover, the authors do not provide an explicit payoff matrix together with a corresponding convergence trajectory that illustrates how the limiting regret norms lead to the required spectral condition.

I would encourage the authors to provide either a theoretical sufficient condition guaranteeing Assumption 2 for the trajectory generated by IREG-PRM+^+, or a more detailed characterization of the matrix games for which this condition can be expected to hold.

Given that the validity of the claimed linear rate depends critically on Assumptions 1 and 2, I am not fully convinced that the paper establishes a broadly applicable closed-form linear last-iterate convergence guarantee for IREG-PRM+^+. Rather, the current result appears to be a conditional local convergence characterization whose applicability to the algorithm's actual trajectories remains insufficiently understood.

3. Potentially overstated contributions in the Introduction.

The Introduction states:

"We derive a closed-form linear rate for a regret-matching dynamic with no restart, no smoothing and no step-size parameter."

While it is true that the algorithm does not require restarting, smoothing, or a manually specified step-size parameter, the linear convergence guarantee in Theorem 4 still relies on the restrictive conditions imposed by Assumptions 1 and 2.

Although these assumptions are stated elsewhere in the paper, I believe the high-level contribution statement does not sufficiently emphasize the conditional nature of the theoretical result. As currently phrased, it may give readers the impression that the unmodified IREG-PRM+^+ algorithm enjoys an unconditional linear last-iterate convergence guarantee.

I suggest that the authors explicitly qualify this claim by emphasizing that the closed-form linear rate is established only under the unique-equilibrium and spectral stability conditions. This distinction is especially important because the unconditional global convergence result and the conditional linear convergence result are fundamentally different theoretical guarantees.

4. Inaccurate characterization of related work on linear last-iterate convergence.

The Related Work section states:

"For regret-matching-type dynamics the linear last-iterate theorems of Cai et al. (2025); Meng et al. (2025); Perolat et al. (2021); Liu et al. (2023) restart or modify the update."

I believe this characterization is imprecise and potentially misleading, as these studies investigate different algorithmic frameworks and convergence targets.

Specifically, Cai et al. (2025) and Meng et al. (2025) investigate regret-matching-type algorithms and establish linear last-iterate convergence guarantees toward Nash equilibria of the original, unregularized matrix games, under their respective algorithmic conditions.

In contrast, Perolat et al. (2021) employ a regularization-based learning framework involving optimistic follow-the-regularized-leader (OFTRL), which is algorithmically distinct from regret matching. Moreover, their linear convergence results concern equilibria of regularized extensive-form games rather than necessarily the Nash equilibria of the original unregularized games.

Similarly, Liu et al. (2023) establish linear convergence results in regularized game settings, whereas their convergence guarantee for the original unregularized games is sublinear.

Therefore, grouping these studies together as examples of regret-matching-type dynamics achieving linear convergence through restarting or modifying the update obscures important differences in both their algorithmic designs and theoretical objectives.

I recommend that the authors revise this discussion to distinguish between (i) regret-matching-type algorithms and other regularized learning methods, and (ii) convergence to Nash equilibria of the original games and convergence to equilibria of regularized games. Such a distinction would help clarify the precise novelty of the present work relative to existing results.

5. Limited experimental validation on representative extensive-form games.

The empirical evaluation primarily focuses on randomly generated matrix games. Although the paper includes experiments on Kuhn and Leduc poker, these experiments mainly investigate the proposed progress-monitoring mechanism rather than the spectral condition underlying the linear convergence analysis.

While the theoretical results are developed for matrix games, certain extensive-form games can also be represented in normal form, as demonstrated in the experimental setting of Cai et al. (ICLR 2025), Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games.

I therefore encourage the authors to conduct additional experiments on representative game instances derived from extensive-form games, particularly to investigate whether the spectral stability condition

η∞σmax⁡(B)<1\eta_\infty\sigma_{\max}(B)<1

continues to hold for the limiting trajectories of IREG-PRM+^+.

Such experiments would provide stronger evidence for the practical relevance of Assumption 2 and help establish whether the proposed linear convergence characterization extends beyond randomly generated matrix games.

Overall assessment.

Although the paper provides an interesting explanation of norm saturation and establishes valuable global convergence results, I remain concerned about the scope and practical applicability of its explicit linear last-iterate convergence guarantee. In particular, the lack of a theoretical connection between the actual trajectories of IREG-PRM+^+ and the spectral condition required by Theorem 4 substantially limits the strength of the main rate result.

I would be more convinced by the paper if the authors could provide stronger theoretical or empirical evidence supporting the applicability of Assumptions 1 and 2, clarify the distinction between conditional and unconditional convergence guarantees, and more accurately position their contributions relative to existing work.

Questions for authors

Besides the above weaknesses, i have other two questions:

  1. Can the spectral condition for linear convergence be guaranteed for the standard zero initialization? More precisely, can the authors prove that the limiting state of IREG-PRM$^+$ satisfies η∞σmax⁡(B)<1\eta_\infty \sigma_{\max}(B)<1 under additional, clearly stated assumptions? If such a result is not currently possible, could the authors give more experiments to verify the reasonableness of assumption in EFG benchmarks?

Can the ratio certificate be turned into a practically useful, theoretically certified stopping or monitoring rule? The current theoretical constant depends on equilibrium-related quantities and an unknown local regime, while the experimental benchmark is explicitly not certified. Can the authors derive computable bounds on these quantities, or provide a finite-time guarantee that makes the certificate operational without requiring unavailable equilibrium information?

Reviewer_ER2gOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper identify the mechanism of the Last-iterate convergence in regret matching as norm saturation: the regret norm rises to a finite limit and freezes the step size. The authors proved it, and gave a very small experiment.

Critical strengths

The proofs seem to be solid.

Critical weaknesses

The experiment is not sufficient. More experiments, especially those from real applications, should be introduced.

Questions for authors

Could authors ad more experiments, especially those from real applications?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.