Last-Iterate Convergence of Smooth Regret Matching$^+$ Variants in Learning Nash Equilibria

We thank you for your time and for providing feedback that will help us improve our manuscript.

W1: Is the weak MVI condition an interesting setting? Can the authors provide some actual applications that satisfy weak MVI but not MVI, beyond the simple 2 player non-zero sum game from section G.2?

A: Intuitively, as $\rho$ decreases, the number of multi-player general-sum normal-form games that the games satisfying the weak MVI encompasses increases. Multi-player general-sum normal-form games have numerous applications, such as:

• Political science, where they are used to model diplomatic relations and strategies between countries.
• Network and communication systems, where multiple service providers may need to allocate bandwidth or other resources.

W2: I find their version of OMD quite confusing; it is quite heavy notationally, and the authors fail to convince me that this framework is necessary.

A: In fact, we utilize the general adaptive OMD as outlined in Joulani et al. (2017). This form extends the traditional OMD to encompass a broader range of algorithms, which is crucial for transforming RM+ variants into an OMD instance. Only by employing the general adaptive OMD can the RM+ variants be transformed into an OMD instance that updates within the original strategy space of the game. In contrast, using the traditional OMD prevents the RM+ variant from being converted into such an instance.

W3: The paper is not well written. Several sentences are hard to read and to understand.

A: We are deeply sorry for this. Could you provide us with more details, such as the specific point you find unclear? We would be more than happy to address any questions or concerns you may have.

W4: The main methodological tool (RM+ to OMD reduction, in the same space) is the same as Liu et al 2021. The convergence based on tangent residuals follows from the analysis in [0].

A: We acknowledge that our research is built upon these foundational works. However, we wish to clarify that our core novelty lies not in inventing new low-level tools, but in constructing a novel, unifying proof paradigm that uniquely combines and extends these tools to solve a more challenging and general problem that was previously unaddressed.

In addition, our transformation substantially differs from that of Liu et al. (2021). While they convert RM+ to OMD, we transform smooth RM+ variants to OMD, which is fundamentally distinct and significantly more complex, as detailed in Appendix A. Moreover, our transformation establishes both last-iterate and finite-time best-iterate convergence for smooth RM+ variants. In contrast, Liu et al. (2021) do not even achieve average-iterate convergence for RM+ using their transformation, as indicated in the bottom right corner of page 6 of their paper: “be deduced from Lemma 2.2, but not from Theorem 3.5.”

Lastly, the tangent residual, serves solely as a metric for assessing the distance to the set of NEs. This is quite standard practice. For instance, Cai et al. (2024), along with other works [1] and [2], employ the tangent residual in their proofs as a metric for assessing the distance to the set of NEs.

Additional Reference:

[1] Bot, Radu Ioan, Dang-Khoa Nguyen, and Chunxiang Zong. "Fast Forward-Backward splitting for monotone inclusions with a convergence rate of the tangent residual of $o (1/k)$." arXiv preprint arXiv:2312.12175 (2023).

[2] Cai, Yang, Argyris Oikonomou, and Weiqiang Zheng. "Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities." arXiv preprint arXiv:2204.09228 (2022).

W5: The authors mention obtaining the best-iterate convergence rates as one of their contributions. But as they themselves acknowledge in lines 88-100, this follows from the analysis in Cai et al. 25, verbatim.

A:

• Firstly, we would like to clarify that our approach to proving best-iterate convergence is fundamentally different from the approach used by Cai et al. in 2025. We use our novel proof paradigm, while they rely on the definition of the duality gap for two-player zero-sum games (line 85). Therefore, their results are confined to two-player zero-sum games, whereas our results hold in games satisfying the weak MVI.
• Secondly, our statement in lines 99-100 is that when we establish the linear last-iterate convergence for Restarting SExRM+ and Restarting SPRM+ in games that satisfy both monotonicity and metric subregularity via our best-iterate convergence, we can directly use the proofs for Restarting SExRM+ and Restarting SPRM+ from Cai et al. (2025). This is precisely the advantage of our best-iterate convergence. Through it, we extend the linear last-iterate convergence results for Restarting SExRM+ and Restarting SPRM+ in Cai et al. (2025) from two-player zero-sum games to games that satisfy both monotonicity and metric subregularity.

W6: this is the proof of what statement?

A: We sincerely apologize for the missing reference here. This is the proof of Theorem 5.1. As mentioned in line 245, to prove Theorem 5.1, we introduce Theorem 5.2, Theorem 5.3, and Lemma 5.4. We also show that the proofs of Theorems 5.2 and 5.3 can be found in the Appendix, while Lemma 5.4 is derived from Farina et al. 2023.

Q1: Can the idea of the authors be extended beyond smoothness?

A: The answer is yes. This is because our proof paradigm itself is not related to smoothness. Specifically, as shown in Section 4 Our Proof Paradigm, smoothness is only used to prove the specific algorithm convergence of $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$. The proof of $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$ is not part of our proof paradigm as $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$ is the inherent nature of the specific algorithm.

Q2: Cai et al. (2025) also obtain rates using a restarting algorithms, but no last-iterate convergence rates for ExRM+ and SPRM+. You also don’t give rates. Do you think that this is an inherent limitations of your analysis (and the one in Cai et al.) ?

A: You raise a profound question that touches upon the frontier of current research. We argue this is not an inherent limitation of our analytical framework, but rather an open challenge.

To provide a finite-time last-iterate convergence rate, a feasible approach is to construct a potential function as demonstrated by Cai et al. (2022). This involves setting the potential function as an upper bound for the tangent residual and proving the finite-time last-iterate convergence rate of the the potential function. This is not an inherent limitation of us. We just did not find a suitable potential function.

Furthermore, we clarify that the finite-time last-iterate convergence rate in Cai et al. (2025) is restricted to two-player zero-sum games, representing only a subset of the games we consider. Also, as mentioned in our responses to W5, we extend the finite-time last-iterate convergence rate in Cai et al. (2025) from two-player zero-sum games to games that satisfy both monotonicity and metric subregularity.

Thank you for your responses.

We would like to clarify that [1] explicitly characterizes GANs as a nonconvex-nonconcave min-max optimization problem. The weak MVI, serves to quantify the degree of nonconvexity and nonconcavity. This is further detailed in Pethick et al. (2023), which states: "a constant $\rho$, which controls the degree of nonconvexity." (for the max player in a nonconvex-nonconcave min-max optimization problem, the utility function $f$ is nonconcave; equivalently, $-f$ is nonconvex) Therefore, an application of weak MVI is generative adversarial networks (GANs).

In addition, our example of games satisfying the weak MVI (see Appendix G.2) can be mapped to real-world scenarios such as trade wars. Consider a strategic trade game between two players:

• Player A: Weaker countries

• Player B: The USA (stronger economy)

Each player chooses whether to impose a tariff or not. The resulting payoffs reflect the dynamics and consequences of trade policies:

• If the USA imposes no tariff while the weaker countries imposes a tariff, both receive a payoff of 1. This is because the weaker countries protects its domestic industries while still accessing the USA’s open market, and the USA benefits from increased trade volume despite facing competition.
• If neither country imposes a tariff, the USA gains a payoff of 1 due to its stronger industries dominating the market, while the weaker countries gets 0, as its unprotected industries are driven out by US competition.
• If the USA imposes a tariff while the weaker countries does not, the weaker countries obtains a payoff of 1 by accessing the US market, but the USA receives a payoff of 0 as its tariff harms its own industries by reducing trade efficiency.
• If both countries impose tariffs, a trade war results, giving both a payoff of -1, as mutual protectionism stifles economic growth.

We appreciate the your valuable time and constructive suggestions.

W1: the main algorithm proposed (SOGRM+) is left to the appendix.

A: We would like to clarify that while the pseudocode and some proofs related to its convergence are in the appendix for space considerations, the core elements—including the main update rules for SOGRM+ and the associated convergence proofs—are presented in the main body of the paper (Section 6, lines 269-319).

W2: I feel a more comprehensive discussion and comparison of the results of this paper in relation to Cai et al. (2025) would be helpful.

A: Thank you for this valuable suggestion. Here is a more detailed comparison with Cai et al. (2025):

• In terms of proof techniques, our proof paradigm centers on recovering the weak MVI, whereas the methods proposed by Cai et al. (2025) focus on analyzing the limit points of iterates or leveraging the definition of the duality gap in two-player zero-sum games. Notably, our paradigm is applicable to both best-iterate convergence and last-iterate convergence, in contrast to Cai et al. (2025), who require separate proofs for these two types of convergence.

• Regarding best-iterate convergence results, our results apply to games satisfying the weak MVI, whereas those of Cai et al. (2025) are restricted to two-player zero-sum matrix games. The applicability of our best-iterate convergence results is significantly broader than that of Cai et al. (2025).

• Concerning non-finite-time last-iterate convergence results, our findings hold for games satisfying the weak MVI. Cai et al. (2025) divide their results into two sections: the first pertains to two-player zero-sum matrix games, while the second addresses broader games satisfying the MVI. Their results exhibit pointwise convergence for two-player zero-sum matrix games, surpassing our own in strength. However, in games satisfying the MVI, our results align with theirs, yet ours extend further to include games satisfying the weak MVI.

• With respect to finite-time last-iterate convergence results, as mentioned in Section 2 Related Work, our best-iterate convergence results enable us to extend the finite-time last-iterate convergence findings of Cai et al. (2025) from two-player zero-sum matrix games to games that concurrently satisfy monotonicity and metric subregularity. This exemplifies one of the advantages of our best-iterate convergence results.

Q1: In [1], they used the tangent residual not only as a proxy for the distance to NE, but also as a method to create a potential function for the dynamics, thus showing last iterate convergence. Would it be possible to extend similar ideas to the set of games with the MVI/weak MVI property?

A: Extending these ideas is feasible. The primary challenge lies in identifying an appropriate potential function for RM+ variants, a problem that remains unsolved in existing research. It is noteworthy that Cai et al. (2025) and the first author of the work you referenced as [1] are the same individual. However, Cai et al. (2025) also have not succeeded in this endeavor, highlighting the inherent difficulty in discovering a suitable potential function for RM+ variants.

Q2: What properties of the tangent residual can be studied to give more results compared to the standard duality gap?

A: The primary advantage of using the tangent residual over the standard duality gap lies in simplifying the proof process when proving last-iterate convergence for algorithms based on the prox-mapping operator (defined in line 166). Specifically, as shown in Eq. (5), from the update rules of the prox-mapping operator and the definition of the tangent residual, we get that the gap between variables at different iterations (such as the gap between $\ell$ and $\theta$ at different iterations in Eq. (5)) serves as an upper bound for the tangent residual. To establish convergence to the NE, it suffices to demonstrate that this gap converges to zero, simplifying the proof process. In contrast, using the standard duality gap does not achieve this simplification.

Q3: It is stated that all existing works on RM+ variants focus on simultaneous updates. I would be curious to know if your proof technique can be used to study alternating variants SExRM+/SPRM+/SOGRM+ in games with MVI/weak MVI and potentially show last/best iterate convergence.

A: We sincerely apologize for any lack of clarity in our original statement. Our intended statement (lines 783-785) is that current research on last-iterate convergence concentrate on simultaneous update schemes, not that all work on RM+ itself is limited to this setting.

Regarding the extension to alternating updates, our proof paradigm itself would require minimal modification. The main challenge lies in proving $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$ after deriving $r^{tan}(x^{t_2}) \leq \Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2$ using our proof paradigm. Notably, the proof of $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$ is not part of our proof paradigm as $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$ is the inherent nature of the specific algorithm.

Thank you for your positive assessment and helpful suggestions.

Q1: In equation 6, how do you make sure that h is differentiable in $x^{t_2}_i$ and $x^{t_0}_i$?

A: To begin with, the function $h_i(x_i)$ is defined as $h_i(x_i)=\frac{\Vert \theta^{t_0}_i \Vert^2_2}{\eta}\psi(x_i)$, where $\frac{\Vert \theta^{t_0}_i \Vert^2_2}{\eta}$ is a constant. The term $\psi(x_i)$ is the quadratic regularizer $\Vert x_i \Vert^2_2$ that is differentiable for any $x_i \in \mathbb{R}^n$. Consequently, $h$ is differentiable with respect to both $x^{t_2}_i$ and $x^{t_0}_i$.

Q2: It would be useful to include a table with other existing results in particular to compare the range of $\rho$?

A: Thank you very much for your suggestion. We think adding this table will greatly improve the clarity of our paper. This table is provided below. Given that we focus on the constrained setting, we only present the comparison within this context. Although we acknowledge that other algorithms tolerate a broader range of $\rho$, existing work primarily focuses on OMD algorithms. We are the first to investigate the last-iterate convergence of RM+ variants in games that satisfy the weak MVI.

Additional References:

1. Ahmet Alacaoglu, Donghwan Kim, and Stephen J Wright. Extending the reach of firstorder algorithms for nonconvex min-max problems with cohypomonotonicity. arXiv preprint arXiv:2402.05071, 2024.
2. Pethick, Thomas, Ioannis Mavrothalassitis, and Volkan Cevher. "Efficient Interpolation between Extragradient and Proximal Methods for Weak MVIs." The Thirteenth International Conference on Learning Representations, 2025.

Thank you for your positive and encouraging feedback on our work.

Q1: Can you provide some intuition behind the equivalence between (4) and (5)?

A: The intuitive explanation is straightforward—both update rules in Eq. (4) and Eq. (5) can be expressed as a $[\cdot]^+ = \max(\cdot, 0)$ operation. Specifically, Eq. (4) is represented as Eq. (18) in Appendix A, while Eq. (5) corresponds to Eq. (20) in Appendix A. The update rules in Eq. (18) and Eq. (20) feature the $[\cdot]^+$ operation, even encompassing terms such as ${\theta}_i^{t_0}$ and $-\eta \ell^{t_1}_i$ within the square brackets.

Q2: Why does the current proof paradigm not directly extend to the Reflected Gradient or the composite Fast Extra-Gradient algorithm? Is it possible to use the equivalence between (4) and (5) to give RM variants of these two algorithms? If not, what might be the obstacles?

A: There are no obstacles. By using our proof paradigm, we can get $r^{tan}(x^{t_2}) \leq \Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2$ for RM variants of these two algorithms.

The main challenge lies in proving $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$ after deriving $r^{tan}(x^{t_2}) \leq \Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2$. The proof of $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$ is not part of our proof paradigm as $\Vert \ell^{t_2} - \ell^{t_1} + \frac{\theta^{t_0} - \theta^{t_2}}{\eta}\Vert_2 \to 0$ is the inherent nature of the specific algorithm.

L1: The authors provide the assumptions of their theoretical results, but do not give an explicit discussion on the limitations of their approach.

A: In addition to the limitations mentioned in in our paper, the most significant limitation lies in the absence of proof regarding the convergence of RM+ variants within extensive-form games. Typically, RM+ variants are integrated with the counterfactual regret minimization (CFR) framework to address extensive-form games. This constitutes one of our future research directions. Moreover, it should be clarified that proving convergence within extensive-form games presents considerable difficulty.

To Reviewer fkfR

We sincerely thank you for your feedback and insightful comments.

Q1: Why not work with OMD in the first place then?

A: The primary reason is that there is no OMD instance capable of updating in the same manner as RM+ variants. Specifically, as mentioned in Q2.3, there exists a transition from $(4) \to (5)$, but not from $(5) \to (4)$. In other words, to obtain the strategy for the next iteration, we must use the update rules of RM+ variants instead of those of OMD.

Q2.1: what can you say about RM+ variants under other regularizers than the quadratic one?

A: This is a interesting idea. However, we have not yet tested the algorithm under these conditions. We will consider this as one of our future research directions.

Q2.2: Is the time-dependence of $f_i$ and $h_i$ crucial in establishing the equivalence with RM+?

A: Yes, you are correct. To establish the equivalence between OMD and RM+ variants, $f_i$ and $h_i$ must vary with time.

Q2.3: In which sense are exactly the updates given by Eqs. 4 and 5 equivalent? It seems reasonable that $(4) \to (5)$. However, I do not see how it can be $(5) \to (4)$?

A: You are correct that the transformation is unidirectional: $(4) \to (5)$ holds, while $(5) \to (4)$ does not. In fact, the term "equivalence" used in Liu et al. 2022 is not entirely precise. Therefore, in Section 1 Introduction, we use the term "transformation" instead of "equivalence."

Q3: Can you provide further motivation / intuition / discussion around the design of the main update step of your algorithm (second line of eq 12)?

A: The intuition for the update step in Eq. (12) is: our proposed algorithm, SOGRM+, can be viewed as a momentum-based method, conceptually similar to Adam. Specifically, the update in Eq. (12) is equivalent to

${{\theta}}^{t+\frac{3}{2}}\_i \in \arg min\_{{{\theta}}\_i \in \mathbb{R}^{|A\_i|}\_{\geq 1}} \{ \eta \langle -{{F}}\_i({{\theta}}^{t+\frac{1}{2}}) - ({{F}}\_i({{\theta}}^{t+\frac{1}{2}}) - {{F}}\_i({\theta}^{t-\frac{1}{2}}), {{{{\theta}}}}\_i\rangle + D\_{\psi} ({{{{\theta}}}}\_i, {{{{\theta}}}}^{t+\frac{1}{2}}\_i) \}$

In this context, ${{F}}_i({{\theta}}^{t+\frac{1}{2}}) - {{F}}_i({\theta}^{t-\frac{1}{2}})$ acts as a momentum term. More precisely, it represents the trend of change in ${{F}}_i$ over the two most recent iterations, analogous to the "acceleration" of ${{F}}_i$. This can be likened to a ball rolling down a hill; as acceleration accumulates, its velocity increases, allowing it to reach the bottom more swiftly.

The formulation in Eq. (12) is primarily to reserve the structural similarity with the update rules of SExRM+ and SPRM+ in Eq. (2) and (3).

Q4: Can you see a generalization of your framework to smooth games played on generic convex compact sets (as opposed to the particular case of the simplex)?

A: To extend to generic convex compact sets, we can modify Phase 1 of our proof paradigm. We can utilize the definition of the cone (line 178) rather than the equivalence (or transformation) used in this paper. Specifically, we do not prove whether $(4) \to (5)$ holds, while obtain the third line of Eq. (6) using the cone's definition.

Q5: Can you provide a counter-example of a game not fulfilling the w-MVI, in which your algorithm does not converge?

A: We can provide examples of games not fulfilling the $\rho$-weak MVI in Theorem 6.2, where our algorithm does not converge. Specifically, in some randomly generated two-player general-sum normal-form games, our algorithm does not converge. According to Theorem 6.2, our algorithm is guaranteed to converge if $\rho > -\frac{1}{12\sqrt{3}D\sqrt{2P^2+4L^2}}$. Therefore, these multi-player normal-form games inherently do not meet the $\rho$-weak MVI criteria stipulated by Theorem 6.2.

Specifically, for such a randomly generated two-player general-sum normal-form game, each player has 20 actions. The payoff matrix for each player is generated using the following python code:

import numpy as np
import random

np.random.seed(3)
random.seed(3)
Player_0_payoff_matrix = np.random.random(size=(20,20))*2-1
Player_1_payoff_matrix = np.random.random(size=(20,20))*2-1

L1: The authors are encouraged to highlight further limitations of their work.

A: We agree with you that a more explicit discussion of limitations would strengthen the paper. From our perspective, beyond the limitations discussed in our paper, the most significant limitation lies in the absence of proof regarding the convergence of RM+ variants within extensive-form games. Typically, RM+ variants are integrated with the counterfactual regret minimization (CFR) framework to address extensive-form games. This constitutes one of our future research directions. Moreover, it should be clarified that proving convergence within extensive-form games presents considerable difficulty.