Regularization is Enough for Last-Iterate Convergence in Zero-Sum Games

Thanks for your comments which are quite helpful to further improve the quality of the paper. We have made some necessary revisions (marked in blue font) in this version. Please refer to the uploaded new version of submission and our point-to-piont responses below.

1. About novelty, and some of those papers are cited, but the discussion is inadequate.

We acknowledge that some of the discussion about related work was inadequate in the original submission, which is also argued by other reviewers. We have carefully addressed this issue and made some necessary modifications in the new version paper (see Section 1.1 on page 2~3). Please also refer to the responses to related comments raised by other reviewers.

2. Regarding the experimental evaluation (Section 5.1), experiments on very small games such as Kuhn or Leduc can be misleading, and it's hard to draw any definite conclusions. I would recommend using larger games.

In Section 5.1, our primary objective was to further validate our theoretical results, with a specific focus on convergence rather than scalability. To ensure a fair comparison with related works and for the sake of consistency with common experimental environments in the literature, we opted for the widely used Kuhn or Leduc game settings. It is true that these games have relatively small sizes, but they still capture the complexity of sequential decision-making, making them suitable for our convergence-focused analysis.

Additionally, we acknowledge the importance of demonstrating the scalability potential of our proposed approach. In Section 5.2, we have included experiments with a larger game, Phantom Tic-Tac-Toe, to showcase the scalability of our approach.

3. What is more concretely the problem of using optimism or extra-gradient in the context of Figure 1? You write that "...can impede convergence, particularly when the real-time policy exhibits chaotic behavior," but I don't think I am following this.

In Figure 1, the primary focus is on illustrating the guidance of second-order information in dynamic settings for different types of games. Specifically:

1. In a Hamiltonian game, second-order information points toward the NE, facilitating convergence. The introduction of second-order information aids in convergence in this context.
2. Conversely, in a potential game, second-order information diverges from the NE. In such cases, introducing second-order information can decelerate convergence or even lead to divergence.

The key reason for this divergence in potential games lies in the fact that the computation of second-order information depends on the gradient flow. In contrast, regularization, which is not dependent on the gradient flow, tends to provide more robust convergence performance.

Furthermore, optimism or extra-gradient can be considered as first-order approximations of second-order information. Therefore, they may inherit similar issues in scenarios where second-order information introduces challenges.

4. I am not sure I see the purpose of Section 2.3. Can the authors explain?

The intention behind Section 2.3 is to illustrate that the introduction of regularization, as discussed in the paper, can be interpreted from the perspective of enhancing the potential component of a game. Specifically, it highlights that the regularization term in the objective function can be viewed as augmenting the potential component, which, in turn, facilitates the achievement of last-iterate convergence.

In the revised version, we have moved Section 2.3 to Appendix C to ensure compliance with page limitations while maintaining the completeness of the content.

Thanks for your comment and we address your questions below.

About the optimistic update

Taking the update formula of OGDA from [1] as an example:

$$\pi_{t}=\text{proj}[x_{t} - \eta F(\pi_{t-1})], x_{t+1}=\text{proj}[x_{t} - \eta F(\pi_t)],$$

where $\text{proj}$ is the projection operator and $F(\pi)=Q_{\pi}$ is the gradient information. It can be observed that, compared to RegFTRL or the vanilla GDA, the optimistic update involves twice the amount of updates. Even in the unconstrained case, where the projection operator is removed, and the update formula can be rewritten as

$$\pi_{t+1} = \pi_{t} - 2\eta F(\pi_{t}) + \eta F(\pi_{t-1}),$$

it still requires twice the storage (i.e., in addition to storing $F(\pi_{t})$, it also needs to store the additional term $F(\pi_{t-1})$).

Nevertheless, the original description may have been somewhat exaggerated, we acknowledge this and have modified it accordingly in the revised manuscript (see Section 1.1 on page 3).

Relation to [2]

[2] primarily explores the relationship between no-regret learning dynamics and time-average convergence to NE in strongly monotone games. While [2] doesn't specifically focus on last-iterate convergence, its Theorem 2 and Theorem 4 indeed establish that first-order and best response algorithms can achieve last-iterate convergence.

• Theorem 2 in [2] shows that the first-order GDA algorithm, with a decreasing learning rate, achieves last-iterate convergence in strongly monotone games. This is equivalent to demonstrating that the GDA algorithm with regularization can converge in monotone games. In contrast, our algorithm provides convergence rates under a constant learning rate setting.
• Theorem 4 in [2] establishes last-iterate convergence for best response algorithms. Although RegFTRL (as well as the optimistic/extra-gradient method) can be seen as aiming to approximate the implicit best-response problem, it remains distinct from explicit best response algorithms. Therefore, the analysis and proof techniques are different from [2].

We acknowledge that [2] is related to our work, and we have added a discussion in the Related Work section (see Section 1.1 on page 3).

[1] Linear Last-iterate Convergence in Constrained Saddle-point Optimization, Wei et al. ICLR 2021.

[2] No-Regret Learning in Strongly Monotone Games Converges to a Nash Equilibrium. Unpublished paper 2022.

Thanks for your comments which are quite helpful to further improve the quality of the paper. We have made some necessary revisions (marked in blue font) in this version. Please refer to the uploaded new version of submission and our point-to-piont responses below.

1. The proposed approach in this paper is very similar to the approach proposed in [1]

We thank the reviewer for pointing out work [1], and acknowledge our work shares some similarities with it. However, we would like to highlight some distinction between these two approaches.

1. Our paper focuses a complementary scenario. While [1] considers a broader class of monotone games beyond NFGs, their analysis could not encompass the behavior-form EFGs considered in our paper.
2. When concentrating on NFGs under full-information feedback, our analyses differ from [1], leading to distinct conclusions. Specifically:
   • Our proposed step size range is larger, especially when $g=D_{\psi}$, where our range is $(0, \frac{1}{\tau}]$ compared to their $(0, \frac{2\tau}{3\tau^2+8})$.
   • The derived convergence rates differ slightly. Our rates are of the form $(1+\eta\tau\lambda)^{-t}$, whereas [1] is $(1-\eta\tau\lambda/2)^{t}$.
3. Additionally, we have strengthened our results by adding sublinear rates to the exact Nash equilibrium, i.e, Theorem 4 in the revised version (see Theorem 4 on page 7). Notably, our results hold for any general-case regularization, whereas [1] specifically considers the l2-norm.

To enhance clarity, we have added a comparison with the relevant literature, especially [1], in the related work (see Section 1.1 on page 3) and the remark following our theorems (see Remark 2 on page 6).

2. “In practical terms, the implementation of the optimistic update approach often necessitates the computation of multiple gradients at each iteration, making it intricate and resource-intensive. " This is not true for OMWU or OGDA (refers to Optimistic Gradient Descent-Ascent) which only requires computation of one gradient in each iteration.

Our original wording was indeed misleading. We have modified "computation of multiple gradients" to "computation of multiple strategies" to accurately convey the idea. In the context of RegFTRL, the computation involves a single strategy sequence $\pi_t$ at each iteration. On the other hand, in the case of OMWU or OGDA, maintenance of two strategy sequences, $\pi_t$ and $\hat\pi_t$, is required. The computation of $\pi_{t+1}$ in each iteration involves both $\pi_t$ and $\hat\pi_{t+1}$. Therefore, the distinction lies in the number of strategy sequences involved in the computation. Furthermore, OGDA has high per-iteration complexity due to the costly projection operations at each iteration, which adds to the computational burden.

3. Some missing references on related works.

1. We acknowledge that references [3, 4] are relevant works utilizing optimistic/extra gradient techniques. In the revised version, we have included these references in the related works section to provide a more comprehensive overview of the literature (see Section 1.1 on page 2~3).
2. Regarding reference [5], we recognize the relevance of this work, especially in the context of entropy regularization. However, we want to emphasize the distinction between our work and the scenario considered in [5]:
   • In stateless NFGs, while [5] focuses on bandit feedback in the context of entropy regularization, our work addresses full feedback scenarios under general-case regularization.
   • In sequential decision making settings, the scope of analysis differs, with [5] exploring infinite-horizon discounted Markov games and path convergence, whereas our work concentrates on undiscounted behavior-form EFGs and last-iterate convergence. These differences in emphasis and setting make direct comparisons difficult, and the conclusions are not easily transferable between the two analyses.

[1] Slingshot Perturbation to Learning in Monotone Games. Abe et al., ArXiv 2023

[2] Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games. Abe et al. AISTATS 2023

[3] Finite-Time Last-Iterate Convergence for Learning in Multi-Player Games. Cai et al., NeurIPS 2022

[4] Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities, Gorbunov et al. NeurIPS 2022

[5] Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games. Cai et al. NeurIPS 2023

Thanks for your comments which are quite helpful to further improve the quality of the paper. We have made some necessary revisions (marked in blue font) in this version. Please refer to the uploaded new version of submission and our point-to-piont responses below.

1. The paper requires significant proofreading. There are many typos and missing articles (e.g., "continue-time" and "continues-time" should be "continuous-time" on page 5) and quantities aren't necessarily always clearly defined (e.g., $r^h$ should be either explicitly given a name or otherwise introduced at the bottom of page 3 since the way it is currently written it is assume that the reader should know what $r^h$ is/that it already has been introduced).

We have proofread the paper several times again in order to eliminate any possible typos.

2. The preliminaries could be made more substantial. A discussion of FTRL (at least explicitly mentioning the FTRL update) would be appropriate in the preliminaries (or earlier in the introduction).

Following your advice, in the main text, we have added an explicit but brief mention of the FTRL update in the preliminaries (see Section 2.2 on page 4), and provide a detailed explanation in the Appendix C to adhere to page limitations.

3. Perhaps you can note once after the preliminaries all proofs are included in the appendix instead of explicitly creating a proof environment for each theorem statement to state that the proof can be found in the appendix.

Thanks for the advice, and we have adopted your recommendation in the revised version.

4. Have you considered mentioning the last-iterate analysis of OGDA that has been done by Wei et al. 2021 in the related work section?

While OGDA is indeed an important related work, we initially did not consider mentioning it in the related work section as its connection to our paper may not be as close as that of OMWU. Nevertheless, following your advice, we have included a reference to OGDA by Wei et al. 2021 in the revised version to provide a more comprehensive overview of the relevant literature (see Section 1.1 on page 2).

5. Why do the plots in Figures 3 and 4 start at $10^2$ and $10^3$? It seems important to note the performance early on as well.

In the early iterations, the exploitability of various algorithms experiences rapid declines, and the distinction among them is not apparent. By focusing on later iterations, where the differences among these algorithms become more evident, we aimed to provide a clearer and more meaningful comparison. However, we acknowledge the importance of presenting a complete picture. In response to your feedback, we have added figures in the revised paper to include all iterations (see Figure 3 and 4 on page 8), ensuring a more comprehensive view of the algorithms' performance over the entire range.

6. Is there a reason you are not comparing to SOTA CFR variants (e.g. CFR+ [a], DCFR [b], PCFR+ [c]) in your EFG experiments in Figure 4?

We have added CFR+ as a baseline in the revised version (see Figure 4 on page 8).

Thanks for your comments which are quite helpful to further improve the quality of the paper. We have made some necessary revisions (marked in blue font) in this version. Please refer to the uploaded new version of submission and our point-to-piont responses below.

1. Novelty

We acknowledge that there are existing works, such as [Wei et al., 2021], that explore the last-iterate convergence problem. However, it's worth noting that many of these works employ optimistic techniques or a combination of optimistic and regularization techniques. In contrast, our work emphasizes achieving last-iterate convergence solely through regularization techniques, providing a more straightforward and conceptually distinct approach.

Besides, works such as [Sokota et al., 2023; Abe et al., 2022; Perolat et al., 2021], similar to ours, specifically focus on investigating the impact of regularization on last-iterate convergence. However, these works either focus on matrix games [Sokota et al., 2023; Abe et al., 2022] and only guarantee asymptotic convergence to the NE of the original game [Abe et al., 2022], or assume continuous-time feedback [Perolat et al., 2021].

Our contribution lies in the exploration of the effects of general-case regularization on last-iterate convergence, providing further insights into discrete-time convergence rate to NE. Additionally, we extend our study to sequential decision-making settings, offering a comprehensive analysis.

Although last-iterate convergence and average-iterate convergence only focus on the algorithm's output, their implications for algorithm performance are significant. For algorithms with only average-iterate convergence guarantees, theoretical considerations suggest that their last-iterate strategy may deviate from the optimal strategy or even diverge. In terms of implementation, dealing with average-iterate strategies poses challenges related to memory consumption and computational overhead.

2. Presentation

We appreciate your keen observation, and in response to your comment, we have made some revisions. Specifically, we have unified the notation to avoid ambiguity, addressing the inconsistency pointed out with $V^{h,\tau}$ and $V^i$. Additionally, we have expanded the discussion in the remarks following the theoretical results, providing a comparative analysis with relevant existing results (see Remark 2 on page 6).

3. Rigor

1. Regarding the annealing approach, it is indeed inspired by the insights provided by Theorems 2 and 3: larger values of $\tau$ lead to faster convergence but introduce higher bias. While our experiments support its effectiveness, we recognize the current description may appear too absolute, and we have fixed it in the revised version (see Section 3.3 on page 6).
2. In the adaption approach, we appreciate your suggestion to provide a more detailed analysis of the convergence speed for different choices of $\tau$. In the revised version, we have introduced a strengthened Theorem 4 to illustrate the comparative convergence rates for various $\tau$ (see Theorem 4 on page 7). This theorem shows that both excessively large and small values of $\tau$ can slightly hinder the convergence rate. The explanation for this phenomenon can be derived from Theorems 2 and 3. Larger $\tau$ values result in faster convergence when the reference strategy $\mu_k$ is fixed, but at the cost of a larger bias, requiring more iterations to reduce it. On the other hand, smaller $\tau$ values, while having a smaller bias, lead to slower convergence, necessitating more iterations to converge. Thus, an optimal choice for $\tau$ lies in a moderate range.

4. While the value function Q is approximated using an actor-critic approach in equation (3), is it correct to assume that the Q function in equation (2) is known?

Yes, the assumption that the Q function in equation (2) is known corresponds to a full-information setting. This is a foundational assumption shared by many works in the literature, including [Sokota et al., 2023; Perolat et al., 2021; Abe et al., 2022].

[Wei et al., 2021] Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games.

[Sokota et al., 2023] A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games.

[Perolat et al., 2021] From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization.

[Abe et al., 2022] Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games.

Thanks for your comments which are quite helpful to further improve the quality of the paper. We have made some necessary revisions (marked in blue font) in this version. Please refer to the uploaded new version of submission and our point-to-piont responses below.

1. Do you request uniqueness of NE in zero-sum game?

No, we do not request the uniqueness of NE. The uniqueness of the equilibrium is ensured by Theorem 1 in our paper, and therefore, we do not rely on the uniqueness assumption.

2. In NFGs (0-sum), your algorithm converge always to an \eps-NE?

Yes, our algorithm converges to an $\epsilon$-NE in NFGs without the use of annealing or adaption approaches. However, as indicated by experiments and theorems in our paper, the proposed algorithm can also converge to an NE through the adaption approach.

3. What is the reason that you pass to FollowMu in the experimental section?

In the experimental section, we employed FollowMu as part of a two-fold evaluation. The first evaluation assesses RegFTRL to substantiate our theoretical findings, while the second one evaluates the neural-based algorithm, FollowMu, which is derived from RegFTRL, in order to validate the effectiveness and practical performance of RegFTRL with neural network function approximation.