acceptodds
Under review as a conference paper at ICLR 2027

Last-Iterate Convergence of Parameter-Free and Scale-Invariant Regret Matching

Abstract

Regret Matching (RM) is widely used as a local regret minimizer in counterfactual regret minimization (CFR) for two-player zero-sum extensive-form games. RM and its predictive variants are parameter-free and invariant to positive rescaling of the payoffs, and existing guarantees control their average or best iterates. Their last-iterate behavior, however, has remained theoretically unresolved even in two-player zero-sum matrix games, where their self-play dynamics can be studied in isolation. We study two predictive RM dynamics in this setting. The first is the Increasing Regret Extra-Gradient Predictive Regret Matching (IREG-PRM) dynamics of zhang2026, and the second is the Increasing-Regret Optimistic PRM (IRO-PRM) dynamics that we introduce. We prove that the played strategy profiles of both dynamics converge to the Nash equilibrium set for every two-player zero-sum matrix game. For IREG-PRM, we further bound the cumulative duality gap by . To the best of our knowledge, these are the first last-iterate convergence guarantees for a parameter-free and payoff-scale-invariant RM-type algorithm. Experiments on structured and random matrix games support the theoretical results.

Primary area:
optimization
Keywords:
learning in games, last-iterate convergence, regret matching

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_jntKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies last-iterate convergence of parameter-free and payoff-scale-invariant RM+-type self-play dynamics in arbitrary two-player zero-sum matrix games. With zero-initialized regret vectors, Theorem 5.1 proves that the played strategy profiles of the existing IREG-PRM+ algorithm approach the Nash equilibrium set and satisfy ∑t=1TGap⁡(xt,yt)=O(T)\sum_{t=1}^{T}\operatorname{Gap}(x^t,y^t)=O(\sqrt{T}). The authors also introduce IRO-PRM+, which uses the previous utility vector for prediction and requires one new gradient evaluation per iteration. Theorem 5.2 establishes its asymptotic last-iterate convergence. The guarantees concern convergence to the equilibrium set, without requiring a unique equilibrium or establishing an explicit last-iterate rate. The analysis combines control of prediction displacements with best-response residual bounds, with an additional argument for the optimistic variant. Experiments on structured and random matrix games support the qualitative convergence claims.

Critical strengths

1. The first general last-iterate convergence guarantees for parameter-free and scale-invariant RM+-type algorithms. Theorems 5.1 and 5.2 establish last-iterate convergence for two-player zero-sum matrix games without requiring additional structural assumptions, such as a unique Nash equilibrium. This is theoretically meaningful because existing last-iterate convergence results for RM+-type methods often rely on explicit step-size choices. The authors instead exploit the increasing-regret construction to establish convergence while preserving the parameter-free and payoff-scale-invariant properties of RM+.

2. A single-call optimistic variant with last-iterate convergence guarantees. The introduction of the parameter-free and scale-invariant IRO-PRM+ is another useful contribution. Compared with IREG-PRM+, which requires two gradient evaluations per iteration, IRO-PRM+ requires only one new gradient evaluation per iteration. Establishing last-iterate convergence for this single-call algorithm is nontrivial, as its prediction errors depend on successive strategy differences rather than extragradient displacements. The corresponding proof provides additional insights into the convergence analysis of optimistic regret-matching algorithms.

Critical weaknesses

Honestly speaking, establishing last-iterate convergence for parameter-free and scale-invariant regret matching type algorithms is important, and I admire the key theoretical results (i.e. the asymptotic last-iterate convergence of IREG-PRM+ and IRO-PRM+) of this paper. However, there are still several weaknesses that could be improved in the revised version:

0. The RVU and scale-invariance property for IREG-PRM+ in Prop 4.1-4.2 has already existed in previous work of IREG-PRM+. Considered the importance of RVU property in demonstrating the last-iterate convergence of IREG-PRM+, the novelty of the theoretical results in Prop 4.1-4.2 is somewhat limited.

1. Unclear of the PROOF SKETCH OF THEOREMS 5.1 AND 5.2. I need to admit that i did not check the detailed proofs line by line in the appendix, but I read the proof sketch in detail. A problem is that the proof sketch (e.g. (2) Convergence of IREG-PRM+) in the main text fails to explain how the square-summable prediction displacements ∑t∥zt−z~t∥22<∞\sum _t \lVert z^t - \tilde{z}^t\rVert_2^{2} <\infty leads to the last-iterate convergence lim⁡tGap(xt,yt)=0\lim _t Gap(x^t,y^t)=0. Actually, the square-summable prediction displacements need to be combined with the Lipschitzness of duality gap function (namely, Lemma A.6(Prediction-to-best-response geometry)) to obtain the final result, but such explanation is missed in the proof sketch in section 5.3.

2. What does the sublinear cumulative duality gap bound T\sqrt{T} mean? I am very curious why the authors give the cumulative duality gap T\sqrt{T} in Theorem 5.1. Such result can not give the explicit or asymptotic last-iterate convergence for IREG-PRM+, and in my opinion has no contribution to the topic of this paper.

3. The theoretical last-iterate convergence results for IREG-PRM+ and IRO-PRM+ are different in form. The last-iterate convergence for IRO-PRM+ show that both the limits of the duality gap and the distance to the NE set is zero, but the last-iterate convergence for IREG-PRM+ only contains the limit of the distance to the NE set. Actually, using the Hoffman error bound (in the proof sketch in (2)ConvergenceofIREG-PRM+. ) as well as the metric subregularity condition proposed in [A1] can result in the equivalence between the duality gap of current strategy and its distance to the NE set.

4. Imprecise statement in Introduction. Line 48 says that "Moreover, the existing guarantees for RM+ recover it only by adding explicit regularization and a step size, unlike the parameter-free RM+ updates used in practice (Cai et al., 2025a)." However, existing last-iterate convergence for RM-type algorithm in (Cai et al., 2025a) does not rely on the explicit regularization. More generally, the existing last-iterate convergence for RM-type algorithms does not rely on regularization technique.

5. Imprecise claim in Table 1 and related works. IREG-PRM+ not only enjoys best-iterate convergence, but also admits optimal average-iterate convergence. Besides, the inconsistent use of tense in related works of Last-iterate convergence of RM+ dynamics: Cai et al. (2025a) establish asymptotic last-iterate convergence, but in line 128 Zhang et al. (2025) introduced parameter-free.

6. The experimental evaluation is not extensive enough. This work only conducts experiments on Counterexample and random matrix, but lacks experiments on real-world games, like the NFG representation of Kuhn/Leduc/Goofspiel EFG game as in [A2]. And more empirical comparisons with recent parameter-free and scale-invariant RM algorithm like ExRM+/SPRM+ in [A2] and MI-SPRM+ in [A3] should be added.

Minor Weaknesses

7. The name for Algorithm 1 is not Predictive RM+ self-paly. Algorithm 1 is the template of IREG-PRM+, and describes the whole procedure of two-player zero-sum game (not self play).

8. The equations in Eq 7 can be put in one line. Eq.5 can be put in the main text.

9. There are too many isolated words in the main text.

References

[A1] Linear last-iterate convergence in constrained saddle-point optimization. ICLR 2021

[A2] Last-iterateconvergencepropertiesofregret-matchingalgorithmsingames. ICLR 2025.

[A3] A faster parameter-free regret matching algorithm. ICLR 2026

Questions for authors

See above weaknesses.

1 comment

Thank you for taking the time to review our work and for providing your valuable feedback. Our detailed responses to your comments and questions are provided below.


Existing Properties and Our Contribution (Comment 0)

Since scale invariance is essential to our claims, we state and verify this property explicitly in the main text. We do not regard these results as main contributions. For IREG-PRM$^+,Section4.2explicitlystatesthatthisrestatesZhangetal.(2025).ForIRO−PRM, Section 4.2 explicitly states that this restates Zhang et al. (2025). For IRO-PRM^+$, which we introduce in this work, we verify that the new prediction rule preserves scale invariance. Likewise, we use the RVU bound of Zhang et al. (2025) as a foundation for our convergence analysis and do not claim it as a new contribution.


Proof Sketch and Convergence Statements (Comments 1 and 3)

Regarding the proof sketch, we have revised the IREG-PRM$^+$ argument in Section 5.3 to clarify how square-summable prediction displacements lead to a vanishing duality gap. We first show that square summability of the prediction displacements implies bounded regret-vector norms. With this boundedness, the estimate from Lemma A.6 and Lipschitz continuity of the duality gap imply that the gap converges to zero.

Regarding the theorem statements, we have added lim⁡t→∞Gap(xt,yt)=0\lim_{t\to\infty}\mathrm{Gap}(x^t,y^t)=0 to Theorem 5.1 to match the form of Theorem 5.2. This convergence was already established in the proof in Appendix A.


Cumulative Duality Gap Bound (Comment 2)

The cumulative bound controls self-play dynamic regret against best responses to the opponents' current strategies, as explained after Theorem 5.1. It complements the last-iterate convergence guarantee by quantifying the total duality gap along the played strategy sequence. While this bound does not imply a pointwise rate, we conjecture an O(t−1/2)O(t^{-1/2}) last-iterate gap bound, consistent with the cumulative O(T)O(\sqrt T) guarantee. Proving or disproving this conjecture remains a direction for future work.


Presentation Revisions (Comments 4, 5, 7, and 8)

Thank you for your comments on the presentation. We have made the following revisions.

  • Comment 4: Our intention was to refer to methods that use explicit regularization (Meng et al., 2025) or introduce a step-size parameter (Cai et al., 2025). We have revised the Introduction to make this distinction explicit and added a separate citation for each.

  • Comment 5: We have added the average-iterate convergence guarantee of IREG-PRM$^+$ to Table 1. Each guarantee now has a reference: Zhang et al. (2025) for average-iterate and best-iterate convergence, and this paper for last-iterate convergence. We have also cited Farina et al. (2021) for the average-iterate guarantee of RM$^+$. We have made the tense consistent in the related-work discussion.

  • Comment 7: We have changed the caption of Algorithm 1 to “Self-play with IREG-PRM$^+$ or IRO-PRM$^+$” to clarify that it describes the common self-play procedure for the two methods, with the prediction chosen as specified in Section 4.2.

  • Comment 8: We have combined the four equations in the original Eq. (7) into one line and moved the normalization definition in the original Eq. (5) into the surrounding text.


Experimental Evaluation (Comment 6)

For the camera-ready version, we plan to add experiments on normal-form representations of extensive-form games and comparisons with ExRM$^+/SPRM/SPRM^+$ and MI-SPRM$^+$.


References

  • Cai et al. Last-iterate convergence properties of regret-matching algorithms in games. In ICLR, 2025.
  • Farina et al. Faster game solving via predictive Blackwell approachability: Connecting regret matching and mirror descent. In AAAI, 2021.
  • Meng et al. Efficient last-iterate convergence in solving extensive-form games. In NeurIPS, 2025.
  • Zhang et al. Scale-invariant regret matching and online learning with optimal convergence: Bridging theory and practice in zero-sum games. arXiv:2510.04407, 2025.
Reviewer_QYJwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a new regret matching + (RM+) variant, IRO-PRM+, which removes the extragradient in IREG-PRM+, an existing algorithm proposed in prior work. Moreover, the paper proves that both IREG-PRM+ and IRO-PRM+ enjoy asymptotic last-iterate convergence in two-player zero-sum matrix games and justifies the results empirically.

Critical strengths

The paper is clearly written and easy to read. The paper proposes the first last-iterate guarantee for a parameter-free and payoff-scale-invariant RM+-type. The paper justifies the results empirically, and IRO-PRM+ converges much faster than vanilla RM+ in last-iterate.

Critical weaknesses

The theoretical guarantee is restricted to asymptotic last-iterate convergence. Empirical justifications are limited to vanilla RM variants. A more extensive comparison to algorithms with last-iterate convergence, such as optimistic mirror descent and regularized mirror descent, would strengthen the result. The last-iterate convergence is limited to two-player zero-sum matrix games.

Questions for authors

Is the only distinction between IREG-PRM+ and IRO-PRM+ the definition of m^xt,m^yt\hat m_x^t, \hat m_y^t? What are the main technical challenges to extending the last-iterate result to counterfactual regret minimization (CFR) with the corresponding RM+ variant in extensive-form games? Following the question above, does CFR with IRO-PRM+ exhibit last-iterate convergence empirically in extensive-form games?

1 comment

Thank you for taking the time to review our work and for providing your valuable feedback. Our detailed responses to your comments and questions are provided below.


On the Difference Between IREG-PRM$^+$ and IRO-PRM$^+$

Yes. Both dynamics use the same learner and differ only in their predictions. IRO-PRM$^+$ reuses the previous observed utilities and requires only one new payoff evaluation per iteration, compared with two for IREG-PRM$^+$.

However, reusing the previous utilities makes the convergence analysis more difficult. Both analyses need to bound the sum of squared prediction errors. Once both regret vectors are nonzero, the prediction error for Player xx under IREG-PRM$^+$ is A(yt−y~t)A(y^t-\widetilde y^t). Its squared norm is bounded by ∥A∥22∥yt−y~t∥22\|A\|_2^2\|y^t-\widetilde y^t\|_2^2, and the latter strategy difference is directly controlled by the negative term in the RVU inequality. For IRO-PRM$^+$, the prediction error is instead A(yt−yt−1)A(y^t-y^{t-1}). Decomposing yt−yt−1y^t-y^{t-1} into (yt−y~t)+(y~t−yt−1)(y^t-\widetilde y^t)+(\widetilde y^t-y^{t-1}) introduces an additional term that the same argument does not directly control. Appendix B bounds this additional term using the growth of the regret-vector norms and thereby establishes convergence. We have revised the proof sketch in Section 5.3 to clarify this additional term and its control.


On the Extension to Extensive-Form Games

As a first step, this paper studies last-iterate convergence in two-player zero-sum matrix games. We agree that extending these results to extensive-form games through CFR is an important direction.

The main difficulty is that the counterfactual utility at each information set depends on strategies at other information sets, including the player's own subsequent decisions. Thus, we would need to jointly control the prediction errors across information sets and combine the RVU inequalities for their local regret minimizers. Our matrix-game analysis does not directly provide these bounds. The last-iterate convergence results for CFR-type methods of Liu et al. (2023) and Meng et al. (2025) rely on solving regularized games. Establishing convergence directly in the original game with our local regret minimizers remains an open direction.


On the Asymptotic Last-Iterate Convergence Guarantee

Our contribution is to establish last-iterate convergence while retaining both the parameter-free and payoff-scale-invariant properties of the dynamics, as summarized in Table 1. For comparison, as discussed in Section 2, Cai et al. (2025) establish asymptotic last-iterate convergence for ExRM$^+$ and SPRM$^+$, and linear convergence after adding restarts. However, these methods require a step size chosen according to the payoff scale and do not retain both properties. We have clarified after Theorem 5.2 that neither theorem establishes an explicit pointwise rate for the last-iterate gap. Establishing such a rate remains an important direction for future work.


On Experimental Coverage and Comparisons with Other Methods

Our current experiments are limited to matrix games and comparisons among RM$^+$ variants. We agree that evaluating CFR with IRO-PRM$^+$ in extensive-form games and comparing our methods with optimistic mirror descent and regularized mirror descent would strengthen the empirical evaluation. We plan to add these experiments in the camera-ready version.


References

  • Cai et al. Last-iterate convergence properties of regret-matching algorithms in games. In ICLR, 2025.
  • Liu et al. The power of regularization in solving extensive-form games. In ICLR, 2023.
  • Meng et al. Efficient last-iterate convergence in solving extensive-form games. In NeurIPS, 2025.
Reviewer_E3eHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the last-iterate behavior of parameter-free, payoff-scale-invariant predictive regret matching+ in two-player zero-sum matrix games. It analyzes IREG-PRM+, an extragradient method introduced by Zhang et al. (2025), and IRO-PRM+, a single-call variant obtained by supplying the previous utility vector as the prediction to the existing increasing-regret learner. Theorem 5.1 proves convergence of the played profiles of IREG-PRM+ to the Nash equilibrium set and an O(T)\mathcal{O}(\sqrt T) bound on the cumulative last-iterate duality gaps. Theorem 5.2 establishes asymptotic convergence to the equilibrium set for IRO-PRM+. The proofs use nondecreasing regret-vector norms, an RVU inequality, displacement/residual estimates, and, for the optimistic variant, a bootstrap argument involving successive strategy increments. Numerical experiments on three structured and three families of random matrix games compare the methods with vanilla RM+ and PRM+.

Critical strengths
  1. The theoretical question is meaningful. The results concern the actual played strategies, not merely averages or a best iterate, while retaining positive payoff-scale invariance and avoiding a matrix-dependent stepsize. Theorems 5.1 and 5.2 cover arbitrary finite two-player zero-sum matrix games, including games with nonunique equilibria. The appendices explicitly consider zero-regret states, which are important because both learners start with zero regret. This makes the guarantee potentially useful beyond settings where smoothing or step-size tuning is acceptable.

  2. The optimistic result is a substantive theoretical extension, even though the underlying prediction rule is standard. Zhang et al. (2025) introduced the increasing-regret learner and explicitly left the corresponding optimistic setup open. Proving last-iterate convergence with only one new payoff evaluation per iteration is therefore of interest. In particular, the analysis of the carried-strategy displacement and regret-norm growth in Appendix B is more than a direct restatement of the extragradient proof.

Critical weaknesses
  1. The incremental novelty of the IREG-PRM+ analysis appears limited and is not fully distinguished from Zhang et al. (2025). The algorithm, equal-norm shift, RVU framework, and important squared-path-length estimates were already available in that work. Furthermore, a short, support-independent bound for the predicted best-response residual seems possible, suggesting that some of the lengthy analysis in Lemma A.6 may be avoidable. This does not establish that Theorem 5.1 is an immediate corollary of prior results, particularly given the different treatments of zero-regret states. Nevertheless, the paper should identify more precisely which new arguments are indispensable. The main independent contribution seems to lie in the analysis of IRO-PRM+, although its previous-utility prediction rule is itself standard.

  2. The strength of the stated guarantees and the evidence for practical advantages are somewhat limited. Neither theorem establishes an explicit pointwise convergence rate for the last-iterate gap: the O(T)\mathcal{O}(\sqrt T) bound in Theorem 5.1 is on cumulative gaps, not on Gap(xT,yT)Gap(x^T,y^T), while Theorem 5.2 does not state a corresponding cumulative bound (although Appendix B may already imply one). These are limitations of the stated results, not errors in the convergence proofs. The experiments already compare methods by gradient evaluations, but do not provide wall-clock or time-to-accuracy comparisons against representative methods with last-iterate guarantees. Moreover, Appendix F reports lower final-budget gaps for alternating PRM+ than for alternating IRO-PRM+ on all three random-game dimensions. This finite-horizon observation does not contradict the simultaneous-update theorem, but leaves the practical benefit of the single-call variant less clear. Given the paper's theoretical focus, I regard the experimental limitations as secondary.

Questions for authors
  1. Zhang et al. (2025, revised version, Theorem 5.5) already establish uniform bounds on the cumulative squared prediction displacements and prediction errors. Moreover, their Assumption 5.6, verified for IR-PRM+ in Lemma D.2, appears to provide a one-step improvement bound relating the predicted best-response residual to the played-to-carried displacement. If this bound holds with a time-uniform constant, the preceding estimates, together with a Lipschitz transfer to the actual utilities, seem sufficient to establish square summability of the last-iterate duality gap. This would imply both last-iterate convergence and the O(T)\mathcal{O}(\sqrt T) cumulative-gap bound. Could the authors clarify whether any step in this argument fails for the precise IREG-PRM+ dynamics, particularly in the treatment of zero-regret states or the one-step improvement estimate? If so, which new argument or lemma, such as Lemma A.6, resolves the difficulty? This distinction is important for assessing the novelty of Theorem 5.1 relative to the prior work.

  2. Appendix B, Lemma B.1 establishes square summability of both ∣∣zit−z~it∣∣||z_i^t - \tilde z_i^t|| and ∣∣zit−zit−1∣∣||z_i^t - z_i^{t-1}|| in the two-active-player case. Lemmas A.6 and B.2 appear to give, after regret norms are bounded, an estimate of the form R(zit;uit)≤Ci∣∣zit−z~it∣∣+2∣∣uit−mit∣∣∞R(z_i^t; u_i^t) \leq C_i ||z_i^t-\tilde z_i^t|| + 2||u_i^t-m_i^t||_ \infty. For IRO-PRM+, the last term is controlled by the opponent's successive-strategy increment. The one-active-player case seems similarly manageable using the proof of Theorem 5.2. Would these estimates imply ∑tGap(xt,yt)2<∞\sum_t Gap(x^t,y^t)^2 < \infty; and thus ∑t=1TGap(xt,yt)=O(T)\sum_{t=1}^T Gap(x^t,y^t) = \mathcal{O}(\sqrt T) for IRO-PRM+ as well? If not, which implication fails? If valid, these estimates would strengthen Theorem 5.2 and suggest that the existing analysis already establishes square summability of the duality gap, contrary to the explanation immediately following the theorem.

  3. Lemma A.6 seems to admit a shorter argument that may avoid the detailed support-case analysis. Let q≥0q \geq 0, q≠0q \neq 0, p=[q+m−γ1]+p = [q + m - \gamma\mathbf{1}]_+, ∣∣p∣∣2=∣∣q∣∣2=ρ>0||p||_2 = ||q||_2 = \rho > 0, z=N(p)z = N(p), and s=N(q)s = N(q). The equal-norm identity gives δ=⟨m,z⟩−γ=∣∣p−q∣∣22(2∣∣p∣∣1)≥0\delta = \langle m,z\rangle - \gamma = \frac{||p-q||_2^2}{(2||p||_1)} \geq 0. Writing M=max⁡jmjM = \max_j m_j and choosing jj with mj=Mm_j = M, we have M−γ≥δ≥0M-\gamma \geq \delta \geq 0 and hence pj−qj=M−γp_j-q_j = M-\gamma. It follows that R(z;m)≤∣∣p−q∣∣2≤2ρd∣∣z−s∣∣2R(z;m) \leq ||p-q||_2 \leq 2 \rho \sqrt{d} ||z-s||_2. This also seems to imply R(s;m)≤[2ρd+d2osc⁡(m)]∣∣z−s∣∣2R(s;m) \leq [2\rho\sqrt{d} + \frac{\sqrt{d}}{2}\operatorname{osc}(m)]||z-s||_2, which would suffice for Lemma A.6. Could the authors confirm whether this support-independent reasoning is valid, or explain which clipping or support configuration it misses?

3 comments

Thank you for your positive assessment and detailed comments, including the suggested simplification of Lemma A.6. Our detailed responses to your comments and questions are provided below.


On the Novelty Relative to Zhang et al. (2025)

Thank you for pointing out this connection. We agree that the estimates in the proof of Theorem 5.5 of Zhang et al. (2025), combined with the one-step improvement property asserted in their Lemma D.2, can be used to derive last-iterate convergence for IREG-PRM$^+$. We have clarified this relationship to the prior analysis in the Introduction and Section 2. We view our contributions as twofold.

First, we identify and prove a stronger consequence of the existing analysis: last-iterate convergence and a cumulative O(T)O(\sqrt T) duality-gap bound for IREG-PRM$^+$. Although these guarantees can be obtained by combining existing estimates, this implication was not explicitly established in the prior work. Recognizing and proving it provides a theoretical explanation for the last-iterate convergence observed in their experiments.

Second, we introduce IRO-PRM$^+$ and establish the same guarantees with only one new payoff evaluation per iteration. Establishing these guarantees requires additional technical arguments beyond the IREG analysis. In particular, the optimistic prediction introduces an additional term, ∥z~t−zt−1∥22\|\widetilde z^t-z^{t-1}\|_2^2, in the prediction-error bound that is not directly controlled by the existing RVU argument. We have revised the proof sketch in Section 5.3 to clarify how the growth of the regret-vector norms controls this term. This answers, for two-player zero-sum matrix games, the open question posed by Zhang et al. (2025) in Section 5.1 of whether similar convergence guarantees can be established for the optimistic learning setup.


On the Last-Iterate Convergence Rate

Our contribution is to establish last-iterate convergence while retaining both the parameter-free and payoff-scale-invariant properties of the dynamics. We view this asymptotic guarantee as a first step toward understanding their last-iterate behavior. For comparison, Cai et al. (2025) also establish asymptotic last-iterate convergence for ExRM$^+$ and SPRM$^+$, with linear convergence obtained after adding restarts; these methods require a step size chosen according to the payoff scale. We have clarified after Theorem 5.2 that neither theorem establishes an explicit pointwise rate for the last-iterate gap. Establishing such a rate while retaining both properties remains an important direction for future work.


On the Experimental Evaluation

Cai et al. (2025) also observe fast last-iterate convergence for alternating PRM$^+,whosegeneraltheoreticalguaranteeremainsopen.∗∗Ourcontributionistoestablishlast−iterateconvergenceforaparameter−free,payoff−scale−invariantmethodthatalsoexhibitscompetitiveempiricalperformance.∗∗SincethecomparedRM, whose general theoretical guarantee remains open. **Our contribution is to establish last-iterate convergence for a parameter-free, payoff-scale-invariant method that also exhibits competitive empirical performance.** Since the compared RM^+$ variants have similar computational costs per payoff evaluation, we expect broadly similar trends in wall-clock comparisons. For the camera-ready version, we plan to verify this with wall-clock and time-to-accuracy measurements and add comparisons against representative methods with last-iterate convergence guarantees.


On the Cumulative Duality Gap for IRO-PRM$^+$

Thank you for pointing this out. You are correct that the existing estimates imply square summability of the duality gap and hence a cumulative O(T)O(\sqrt T) bound for IRO-PRM$^+$. We have added this bound to Theorem 5.2, included the derivation covering all cases in Appendix B, and corrected the accompanying discussion.


On the Proof of Lemma A.6

Thank you for suggesting this simpler proof. Your argument is valid and avoids the case analysis in our original proof. We have replaced the proof of Lemma A.6 in Appendix A accordingly, keeping the lemma statement and constants unchanged.


References

  • Cai et al. Last-iterate convergence properties of regret-matching algorithms in games. In ICLR, 2025.
  • Zhang et al. Scale-invariant regret matching and online learning with optimal convergence: Bridging theory and practice in zero-sum games. arXiv:2510.04407, 2025.
Reviewer_E3eHOpenReview ↗

Follow-up on the author response

Thank you for the detailed response and revisions. I appreciate the clarification that the IREG-PRM+ convergence guarantee can be obtained by combining the estimates in Zhang et al. (2025). This resolves the ambiguity in how that result should be positioned; I continue to regard the IRO-PRM+ analysis as the principal new technical contribution.

The added cumulative O(T)O(\sqrt{T}) bound in Theorem 5.2 and Appendix B, and the support-independent proof of Lemma A.6, directly address my corresponding questions. I consider those clarification requests addressed.

The remaining limitations are the absence of an explicit pointwise last-iterate rate and the limited evidence for a practical advantage of the single-call variant. Wall-clock and time-to-accuracy comparisons would help substantiate the practical benefit, but I continue to regard this as a secondary limitation given the paper's theoretical focus.

Overall, the last-iterate convergence analysis for the parameter-free, payoff-scale-invariant single-call variant remains a meaningful theoretical contribution. I maintain my original rating of 3 (Weak acceptance).

Thank you for your constructive feedback and continued positive evaluation of our work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.