- 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 adversarial regret bound, an average-iterate convergence rate, and an instance-dependent stretched-exponential last-iterate convergence rate for . 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 . Numerical experiments on several matrix-game instances are presented to evaluate the proposed algorithm against existing methods.
Critical strengths
- 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.
- 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
- 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 by a constant multiple of , whereas Lemma A.1 provides an upper bound involving , with the opposite inner-product direction. Moreover, Eq. (110) admits a counterexample. Taking , , and yields . 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 should involve , whereas the proof uses . These quantities are generally different, and the resulting error is not accounted for. In particular, Eq. (111) only controls a term involving 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.
- 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
- 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 , and gives , 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 using instead of . How can the omitted term 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?
-
Section 5 states that the last-iterate convergence rate becomes when . However, Theorem 5.1 and Theorem C.6 appear to establish only an instance-dependent rate of , where 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 rate or whether this statement should be corrected?
-
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 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?