acceptodds
Under review as a conference paper at ICLR 2027

Non-Asymptotic Last-Iterate Convergence for Scale-Invariant Regret-Matching Algorithms in Matrix Games

Abstract

Regret matching (RM) is a widely used no-regret learning paradigm for computing a Nash Equilibrium (NE) in games, best known for its parameter-free and scale-invariant properties. However, these desirable properties have so far been difficult to reconcile with last-iterate convergence: classical scale-invariant RM variants may exhibit cycling, whereas existing convergent RM methods typically introduce additional step size or smoothing parameters to stabilize the learning dynamics, thereby sacrificing scale invariance. In this work, we take a step toward closing this gap by introducing a scale-invariant RM-type algorithm, termed Radial IREG-PRM, with non-asymptotic last-iterate convergence guarantees in two-player zero-sum matrix games. The key idea is to apply a deterministic radial expansion with exponent to the (pseudo-)cumulative regret vector while leaving the induced strategy unchanged. For arbitrary bounded utility sequences, Radial IREG-PRM achieves the optimal adversarial cumulative regret for every fixed , without prior knowledge of either the horizon or the utility scale. In self-play, a radially weighted RVU-bound analysis further yields an average-iterate convergence rate, which can be made arbitrarily close to the optimal rate. More importantly, we establish an explicit, instance-dependent stretched-exponential last-iterate rate of for some game-dependent constant . We complement this fast instance-dependent guarantee with a uniform worst-case lower bound of over normalized matrix games, together with a matching upper bound for the case in which exactly one player never gets non-zero cumulative regrets. Finally, we extend Radial IREG-PRM to the single-sample bandit-feedback setting by using regularization technique, and establish an in-expectation last-iterate convergence rate of for any . Experiments on four instances of matrix games further validate the competitiveness of Radial IREG-PRM over existing baselines.

Primary area:
optimization
Keywords:
regret matching, scale-invariance, matrix game, last-iterate convergence, Nash equilibrium, bandit

Reviews

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

This paper proposes Radial IREG-PRM+, a scale-invariant regret-matching algorithm designed to achieve non-asymptotic last-iterate convergence in two-player zero-sum matrix games. The main idea is to introduce a deterministic radial expansion of the corrected regret vector while preserving the normalization-based strategy update. The authors establish an optimal-order O(T)\mathcal{O}(\sqrt T) adversarial regret bound, an O(T−1+α)\mathcal{O}(T^{-1+\alpha}) average-iterate convergence rate, and an instance-dependent stretched-exponential last-iterate convergence rate for α∈(0,1/2)\alpha \in (0, 1/2). They also derive a uniform worst-case lower bound and a matching upper bound for a special class of games. Furthermore, the method is extended to the single-sample bandit-feedback setting, with an expected last-iterate convergence rate of O(T−1/10+ϵ)\mathcal{O}(T^{-1/10+\epsilon}). Numerical experiments on several matrix-game instances are presented to evaluate the proposed algorithm against existing methods.

Critical strengths
  1. A meaningful algorithmic contribution that combines scale invariance with last-iterate convergence.

The paper addresses an important limitation of existing regret-matching algorithms: classical scale-invariant methods may fail to converge in the last iterate, whereas existing convergent variants often require additional learning-rate parameters or restarting mechanisms. The proposed radial expansion is a relatively simple modification of IREG-PRM+ that aims to preserve scale invariance while providing explicit last-iterate convergence guarantees without restarting. This combination is conceptually appealing and constitutes the main motivation for considering the paper for acceptance.

  1. A comprehensive theoretical investigation of the proposed algorithm.

The paper goes beyond establishing last-iterate convergence by studying adversarial regret, average-iterate convergence, instance-dependent convergence rates, and uniform worst-case lower bounds. In particular, the distinction between fast instance-dependent convergence and potentially slower uniform worst-case behavior is theoretically meaningful. The extension to bandit feedback further broadens the scope of the analysis. If the main convergence arguments are validated, these results would represent a substantial theoretical contribution to regret-matching methods.

Critical weaknesses
  1. Substantive errors in the proof of the main last-iterate convergence result.

The proof of Lemma 5.3 in Appendix C.4 contains two substantive mathematical issues.

First, Eq. (110) is incorrect as stated. It bounds max⁡pi⟨mit,zit−pi⟩\max_{p_i}\langle m_i^t,z_i^t-p_i\rangle by a constant multiple of ∣∣zit−z~it∣∣2||z_i^t-\tilde z_i^t||_2, whereas Lemma A.1 provides an upper bound involving ⟨mit,pi−z~it⟩\langle m_i^t,p_i-\tilde z_i^t\rangle, with the opposite inner-product direction. Moreover, Eq. (110) admits a counterexample. Taking R=Q=(10,0)R=Q=(10,0), m=(1,0)m=(1,0), and γ=1\gamma=1 yields z=z~=(1,0)z=\tilde z=(1,0). These choices satisfy the algebraic conditions of Lemma A.1, but the left-hand side of Eq. (110) equals 1, while its right-hand side is zero.

Second, the proof of Lemma 5.3 omits the discrepancy between the predicted and actual utility vectors. Specifically, the exploitability gap at z~t\tilde z^t should involve Fi(z~t)F_i(\tilde z^t), whereas the proof uses mit=Fi(zt−1)m_i^t=F_i(z^{t-1}). These quantities are generally different, and the resulting error Fi(z~t)−Fi(zt−1)F_i(\tilde z^t)-F_i(z^{t-1}) is not accounted for. In particular, Eq. (111) only controls a term involving ∣∣zit−z~it∣∣2||z_i^t-\tilde z_i^t||_2 and does not address this missing discrepancy.

These issues are consequential because Lemma 5.3 is directly used in Theorem C.6 to establish the Lyapunov contraction underlying Theorem 5.1. Although the proof may be repairable, the current argument does not establish the claimed stretched-exponential last-iterate convergence rate. Since this is the central theoretical contribution of the paper, the unresolved proof issues substantially affect my assessment of its soundness.

  1. Although Radial IREG-PRM+ provides stronger theoretical last-iterate convergence guarantees, its empirical advantages are not clearly demonstrated in Figure 1. In particular, the proposed method performs comparably to or worse than the original IREG-PRM+ across the tested instances. Moreover, alternating PRM+ converges substantially faster on the 3×3 and random matrix games, while EG performs significantly better on Goofspiel. These results raise concerns about whether the improved theoretical guarantees translate into meaningful practical benefits, as the proposed radial expansion does not appear to offer a consistent empirical advantage over existing methods.
Questions for authors
  1. Could the authors provide a corrected proof of Lemma 5.3 addressing the following two issues?

(i) Eq. (110) is incorrect as stated. For example, taking R=Q=(10,0),m=(1,0)R=Q=(10,0), m=(1,0), and γ=1\gamma=1 gives z=z~=(1,0)z=\tilde z=(1,0), for which the left-hand side of Eq. (110) equals 1 while the right-hand side is zero. What valid estimate can replace Eq. (110), given that Lemma A.1 bounds an inner product with the opposite direction?

(ii) The proof evaluates the exploitability gap at z~t\tilde z^t using mit=Fi(zt−1)m_i^t=F_i(z^{t-1}) instead of Fi(z~t)F_i(\tilde z^t). How can the omitted term Fi(z~t)−Fi(zt−1)F_i(\tilde z^t)-F_i(z^{t-1}) be controlled, and how does this affect the exploitability-gap bound? Could the authors provide a rigorous corrected bound and demonstrate that it is sufficient to recover the Lyapunov contraction in Theorem C.6 and the stretched-exponential last-iterate convergence rate in Theorem 5.1?

  1. Section 5 states that the last-iterate convergence rate becomes O(t−1)\mathcal{O}(t^{-1}) when α=1/2\alpha = 1/2. However, Theorem 5.1 and Theorem C.6 appear to establish only an instance-dependent rate of O(t−μ/2)\mathcal{O}(t^{-\mu/2}), where μ\mu is a positive constant that is not necessarily greater than or equal to 2. Could the authors clarify whether an additional argument establishes the claimed O(t−1)\mathcal{O}(t^{-1}) rate or whether this statement should be corrected?

  2. The paper appears to present Radial IREG-PRM+ as a radial modification of the original IREG-PRM+. However, Algorithm 1 seems to differ from the original algorithm in both the prediction step and the correction step, independently of the radial expansion parameter. In particular, it uses the previous-step utility vector for prediction and applies the correction after truncating the predicted regret vector. Could the authors clarify whether setting α=0\alpha=0 actually recovers the original IREG-PRM+ algorithm? If not, could they explain the roles of these additional modifications and clarify how the original IREG-PRM+ baseline in Figure 1 was implemented?

Reviewer_wzcjOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies a new variant of regret matching called Radial IREG-PRM+, which builds on the scale-free and parameter-free IREG-PRM+ algorithm of Zhang+26. The authors primarily study the last-iterate behavior of this algorithm in two-player zero-sum games. They prove (instance-dependent) quantitative last-iterate convergence rates, near-optimal time-average rates, and also an expected last-iterate rate under bandit feedback.

Critical strengths

The paper presents the first regret-matching variant with quantitative last-iterate convergence guarantees that also maintains the desired parameter-free and scale-free properties. The authors also obtain several complementary and quantitative guarantees for their algorithm in time-average, best-iterate (lower bounds), and under bandit feedback. Thus I believe this is a nice and well-written technical contribution to the learning-in-games field that adds to the frontier of our understanding on the last-iterate behavior of the regret matching family.

Critical weaknesses

In my view, the main (minor) weakness of the paper's results is that the new Radial IREG-PRM+ algorithm is slighty more complicated than the original IREG-PRM+ algorithm of Zhang+26, while the latter still empircally seems to converge in last-iterate and also has provably better time-average convergence guarantees. Thus, there is still some theory/practice tradeoff.

Questions for authors

I have several high-level questions:

  1. What are the roadblocks in deriving similar guarantees for the optimistic variant of radial IR-RM+, and not the current extra-gradient variant? (note: I am aware that the Zhang+26 paper similarly has guarantees only for the extragradient variant).

  2. For Theorem 5.1, can you give some intuition and discussion on what structural properties of the game (e.g., location of the NE?) and/or what properties of the initialization make the constants C and \mu degrade? and what can make the threshold T_\star large? I just want to understand more intuitively what properties of the instance make the last-iterate rate become very slow.

  3. Same as question 2, but now for the constants C_{x, y} and t_\star in Theorem 4.2. Also, do these constants depend on \alpha at all?

  4. Experimentally (Figure 1) we see that the (non-radial) IREG-PRM+ algorithm of Zhang+26 converging in last-iterate at similar rates as your radial variant (this was shown also in the Zhang+26 paper experimentally). Given your new analysis of the radial variant, do you have any intuition as to how to analyze the last-iterate behavior the original, non-radial version?

  5. Can you provide any brief additional intuition for the potential in (8) (and in particular, on the constituent quantities P and \calV?)

Minor typos:

  • line 458: "best stepsizs" --> "best stepsizes"
Reviewer_rHBBOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses the problem of reconciling scale invariance with last-iterate convergence in regret-matching algorithms. The proposed radial expansion is conceptually simple and avoids explicit payoff-dependent learning-rate tuning and restarting. If the theoretical guarantee is established, it would provide an interesting complement to existing RM-based and extragradient methods.

Critical strengths

The paper addresses the meaningful problem of reconciling scale invariance with last-iterate convergence in regret-matching algorithms. The proposed radial expansion is conceptually simple. If the theoretical guarantee is established, it would provide an interesting complement to existing RM-based and extragradient methods.

Critical weaknesses

The proof of Lemma 5.3 on page 24 appears incorrect. Specifically, Equation (110) attempts to upper-bound

max⁡pi⟨mit,zit−pi⟩\max_{p_i}\langle m_i^t,z_i^t-p_i\rangle

by a constant times ∣zit−z~it∣2|z_i^t-\widetilde z_i^t|_2, citing Lemma A.1. However, Lemma A.1 bounds the expression with the opposite sign.

For example, let R=(1,0))and(m=(1,0)R=(1,0)) and (m=(1,0). The prediction step can yield Q=RQ=R, hence z=z~=(1,0)z=\widetilde z=(1,0). The right-hand side of Equation (110) is zero, while the left-hand side equals one.

Moreover, the proof of Lemma 5.3 uses the lagged utility prediction mit=Ui(zt−1)m_i^t=U_i(z^{t-1}) to express the exploitability at $ \widetilde z^t $, rather than using Ui(z~t)U_i(\widetilde z^t). This discrepancy requires an additional correction term.

These issues are consequential because Lemma 5.3 is used to derive the Lyapunov contraction underpinning the main stretched-exponential last-iterate guarantee.

There is also a related sign inconsistency in the variational characterization of the exploitability gap on page 3. Additionally, the claimed $ O(T^{-1}) $ boundary rate at $ \alpha=1/2 $ does not follow from the exponent in Theorem C.6.

  1. Although the stretched-exponential result appears attractive, it is instance-dependent and requires a potentially very large burn-in time. The stabilization threshold scales as $ M_A^{1/(2\alpha)} $, which can deteriorate dramatically as $ \alpha $ approaches zero. This is especially relevant because the main experiments use $\alpha=10^{-3} $.

The paper does not establish an instance-independent last-iterate upper bound when both players activate, and its uniform lower bound is specific to the proposed algorithm.

Furthermore, the bandit-feedback convergence rate is substantially slower than the best existing results, and Algorithm 2 is not experimentally evaluated. A consolidated comparison of rates, assumptions, gradient-oracle costs, and the effects of hyperparameter selection would help establish the practical advantages of the method.

  1. The related-work discussion should also consider Fiegel et al. (2026), Optimal Last-Iterate Convergence in Matrix Games with Bandit Feedback Using the Log-Barrier, and the recent work of Li and Huang (2026) on last-iterate convergence of unmodified IREG-PRM+.
Questions for authors

Could the authors provide explicit estimates of the stabilization time $ T_0 $ and contraction constant $ c_A $ for representative game instances, especially when $ \alpha=10^{-3} $?

How do these constants compare with those of existing restarted RM or extragradient methods? The apparent improvement in the asymptotic exponent may be offset by a very large burn-in time.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.