- 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 . 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 leads to the last-iterate convergence . 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 mean? I am very curious why the authors give the cumulative duality gap 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.
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^+$, 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 limt→∞Gap(xt,yt)=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) last-iterate gap bound, consistent with the cumulative O(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^+$ and MI-SPRM$^+$.
References