Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games

Thank you for the positive review and comments! We address your comments and questions below.

Although this paper considers a different game from [Meng et al., 2023] ... instead explicitly acknowledge that the convergence proof of RM+ of this paper largely depends on [Meng et al., 2023].

A: We have updated the introduction and added a discussion with [Meng et al., 2023] as follows: “[Meng et al., 2023] studies RM+ in strongly-convex-strongly-concave games and proves its asymptotic convergence (without rate) to the unique equilibrium. Theorem 1’s proof largely follows from [Meng et al., 2023] with the key observation that the properties of strict NE suffices to adapt the analysis in [Meng et al., 2023] to zero-sum games (not strongly-convex-strongly-concave games) with a strict NE. ” We also added a remark before the proof of Theorem 1. Thank you for pointing that out!

What is the exact difference between "Convergence of the iterates" and "Convergence in the Duality Gap"? What are the advantages of "Convergence of the iterates" compared to "Convergence in the Duality Gap"?

A: Thank you for the question. We clarify the difference between "Convergence of the iterates" and "Convergence in the Duality Gap" below.

Given a sequence of iterates $\{z^t\}$, convergence of the iterates means $\lim_{t \rightarrow \infty} z^t$ exists and is a Nash equilibrium; convergence of the duality gap means $\lim_{t\rightarrow \infty} \textnormal{DualGap}(z^t) = 0$. If we only focus on asymptotic convergence, the convergence of the iterates is stronger since it implies convergence of the duality gap; but convergence of the duality gap does not imply convergence of the iterates. One example is that the iterates could cycle and become closer and closer to the set of Nash equilibria (so the duality gap goes to 0), but the trajectory does not converge to one point. It also illustrates an advantage of convergence in the iterate over convergence in the duality gap, as convergence in the iterate guarantees the stability of the actual sequence of iterates played. Convergence in the iterate is also called point convergence and is desirable in the optimization community [1].

Why does the first author in prior works use tangent residual to claim "last-iterate convergence," while this paper distinguishes between "Convergence of the iterates" and "Convergence in the Duality Gap"?

A: We note that convergence in the iterate is usually asymptotic unless for strongly-convex-strongly-concave problems. However, we could analyze rate of convergence (convergence rate) for the convergence of the duality gap. We say an algorithm has a convergence rate $f(T)$ in duality gap if $\textnormal{DualGap}(z^T) \le f(T)$ for all $T$. Taking extragradient (EG) as an example, EG is well-known to have convergence in the iterate (see [2]) which also implies convergence in the duality gap. However, its rate of convergence was unclear until [3]. The main contribution of [3] is to provide the convergence rate of EG, showing that $\textnormal{DualGap}(z^T) \le O(1/\sqrt{T})$. In the current paper, for ExRM+ and SPRM+, convergence in the duality gap is relatively standard to prove by classical results. Our main technical contribution is to prove the stronger notion of convergence in the iterate. We leave the convergence rate regarding the duality gap as an interesting open question.

Is the claim in the conclusion about "linear-rate convergence in iterates" correct?

A: Thanks for pointing it out! This phrase is indeed a bit confusing. We have changed it to "linear last-iterate convergence". It means that restarting versions of ExRM+ and SPRM+ have a linear last-iterate convergence rate in the duality gap $\textnormal{DualGap}(z^T) \le O( (1-c)^T)$.

[Meng et al., 2023] Meng, Linjian, Zhenxing Ge, Wenbin Li, Bo An, and Yang Gao. "Efficient last-iterate convergence algorithms in solving games." arXiv preprint arXiv:2308.11256 (2023).

[1] Sedlmayer, Michael, Dang-Khoa Nguyen, and Radu Ioan Bot. "A fast optimistic method for monotone variational inequalities." International Conference on Machine Learning. PMLR, 2023.

[2] Facchinei, Francisco, and Jong-Shi Pang, eds. "Finite-Dimensional Variational Inequalities and Complementarity Problems." 2003

[3] Cai, Yang, Argyris Oikonomou, and Weiqiang Zheng. "Finite-time last-iterate convergence for learning in multi-player games." Advances in Neural Information Processing Systems 35 (2022): 33904-33919.

Thank you for your positive review and comments. We address your questions below.

Can you elaborate on the motivation behind considering RM+ algorithm in NFGs? Why are they important in NFGs, given that there are convergence algorithms like EG/OG.

How can the results be extended to EFGs?

A: This is a great question! EG/OG are popular algorithms for NFGs, and their last-iterate convergence properties have been extensively studied and are now fairly clear. RM+ algorithms are also popular for solving zero-sum games, especially for EFGs. However, little is known about their last-iterate convergence properties. This motivates our study on RM+ algorithms in NFGs (a special case of EFGs). Moreover,

1. Our non-convergence counterexample shows that many RM+ variants, including RM+, alternating RM+, PRM+ do not converge in the last-iterate in some simple NFGs, which implies that this non-convergence persists in EFGs.

2. Our convergence results for NFGs provide the first step toward understanding last-iterate convergence results in EFGs. The main challenge for establishing last-iterate convergence is the non-monotonicity of the regret operator, which we overcome by using the geometric structure of the limit points of the dynamics (lemma 4 in our paper). We require similar characterizations for EFGs to extend our results. We are hopeful that our techniques could be extended to EFGs, given that it is common to study first the properties of algorithms over NFGs before extending the results to EFGs, e.g. the last-iterate convergence of optimistic OMD was obtained first for NFGs in [1] before being proved in [2] for EFGs.

3. RM+-type algorithms involve non-monotone operators and differ from EG/OG, which concerns monotone operators. Our analysis gives the first convergence in iterate result for an operator with a Minty solution and is of independent interest.

Is it possible to modify EXRM+ to be no regret? Is SPRM+ no regret? ( i believe OG is no regret, so does this extend to SPRM+?)

A: ExRM+ is not no-regret. We study ExRM+ since it has been proposed in previous works and is a natural analog of EG. SPRM+ is indeed no regret. This follows from (1) PRM+is no-regret [3] and (2) SPRM+ is PRM+ where the projection is on the clipped orthant (we chop out the origin).

[1] Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In International Conference on Learning Representations (ICLR), 2021.

[2] Chung-Wei Lee, Christian Kroer, and Haipeng Luo. Last-iterate convergence in extensive-form games. Advances in Neural Information Processing Systems, 34:14293–14305, 2021.

[3] Farina, Gabriele, Christian Kroer, and Tuomas Sandholm. "Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 6. 2021.

Thank you for the very positive review. We address your questions below.

Their paper is restricted to two-player zero-sum games (bimatrix) games. It would be great to get a clarity as to if these techniques can be extended for general convex-concave games? (And also for general convex sets).

A: We would like to clarify that the regret matching-type algorithms that we study in our paper are specifically designed for regret minimization over simplices. As such, studying general convex sets would require different algorithms. It is possible to extend Blackwell approachability in this way, see e.g. [1,2]. Extending our results to this case is an interesting future direction, but most likely a general analysis would be very hard.

Extending our results to convex-concave problems over simplexes does not have this issue: in this case, one can take subgradients to perform regret minimization via regret matching. The results may generalize if subgradients are bounded, but we are not sure whether more conditions are needed for last-iterate convergence.

Is it possible to obtain asymptotic rates of convergence for the last-iterate analysis shown here?

A: We assume that your question is about getting a specific rate of convergence, as opposed to the asymptotic rate-free guarantee. If you had something else in mind, please feel free to ask us to clarify.

Our results only give a rate-free asymptotic last-iterate convergence for RM+ (when strict NE exists), ExRM+, and SPRM+. We also prove concrete rates for the best-iterate convergence of ExRM+ and SPRM+, and linear last-iterate convergence rates for their restarting variants. We acknowledge that we do not have last-iterate convergence rate results for ExRM+ and SPRM+. Proving such results usually requires the operator to be monotone and a sophisticated potential function argument (like the proof for the Extra-Gradient and Optimistic-Gradient methods). These techniques have not been generalized to operators satisfying only the Minty condition, so progress on this front would likely be a challenging result of independent interest. We leave obtaining last-iterate convergence rates for ExRM+ and SPRM+ is an interesting future direction.

[1] Grand-Clément, Julien, and Christian Kroer. "Conic Blackwell algorithm: Parameter-free convex-concave saddle-point solving." Advances in Neural Information Processing Systems 34 (2021): 9587-9599.

[2] D'Orazio, R., & Huang, R.. Optimistic and adaptive Lagrangian hedging. AAAI 2021.

Thank you for the very positive review. We address your questions below.

My only minor concern is that in Theorem 4 and 7 I think that $\eta$ must be constant (not function of t) since $\beta$ must be upper bounded by a constant strictly less than 1 in order to have linear (geometric/inverse exponential) convergence. Thus, I think, if I am correct, that this should be explicitly stated in the Theorems.

A: In algorithms 5 and 6, we set the step size $\eta$ to be constant (independent of $t$). In the updated version, we have restated it (we added ''with constant step size $\eta$") in the theorems for clarity.

Do you have any insight about the rate of convergence of the result of the Theorem 1? I think this will be a good direction for future work.

A: In fact, as we remark at the end of the proof of Theorem 1 in the appendix (page 16, Line 862), our proof gives that RM+ has a $O(1/\sqrt{T})$ best-iterate convergence rate. This rate depends on the constant induced by the strict NE property, which may be very small. We agree that investigating the problem-independent best-iterate convergence rate and last-iterate convergence rate of RM+ in games with strict NE is a very interesting future direction.

I would like to thank Authors for their answer. My questions are completely answered and I will keep my initial score.