Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games

We are deeply appreciative of your positive feedback and constructive comments, especially your invaluable suggestions on improving our presentation. We will incorporate your feedback into our presentation to make it better. The detailed answers to each of the questions can be found below.

---

Weakness and Question 1

The proposed GABP algorithm does not achieve the optimal $O(1/T)$ last-iterate convergence rate under full gradient feedback. The $O(1/T^{1/7})$ last-iterate convergence rate is also not tight for the noisy feedback.

What is the intuition behind the $O(1/T^{1/7})$ convergence rate in the noisy gradient setting? In your opinion, what is the best possible rate that can be achieved by the current approach?

Answer

As you pointed out, it is still unrevealed whether our convergence rate in the noisy feedback setting is tight or not, given the absence of existing results on lower bounds and faster rates than ours. Nevertheless, we anticipate that the convergence rate we have achieved in the noisy feedback setting may not be optimal. This is largely due to the fact that we have roughly derived the upper bound on $\sum_{l=1}^{k(t)}(l+1)^2\langle \pi^{\mu, \sigma^l} - \sigma^{l+1}, \hat{\sigma}^l - \pi^{\mu, \sigma^l}\rangle$ and $\sum_{l=2}^{k(t)}l(l+1)\langle \pi^{\mu, \sigma^{l-1}} - \sigma^{l}, \pi^{\mu, \sigma^l} - \hat{\sigma}^l\rangle$ by using Cauchy–Schwarz inequality in the proof of Lemma B.2. If we can tighten this upper bound, it could potentially lead to an improved convergence rate of $O(1/T^{1/4})$ in the noisy feedback setting for the same algorithm.

---

Weakness and Question 2

The relationship between the proposed GABP algorithm and the AOG algorithm in [1] and the intuition behind the fast last-iterate convergence rates is not clearly discussed. These two algorithms are different (as shown in Appendix F) but share similar ideas.

Moreover, the potential function and the approximately non-increasing potential analysis are very similar to that used in [1]. If they are inspired by [1] then this should be acknowledged.

Answer

We agree with you that GABP can be viewed as an approximation of Halpern iteration, whereas it has a different update scheme from the AOG algorithm. From the perspective of theoretical guarantee, our potential function (in Eq. (8)) is indeed inspired by the one used in [1] while there are slight variations. We will ensure to elucidate the detailed relationship between our study and [1] in the revised manuscript.

---

Weakness and Question 3

Could you explain Equation (5) and the related discussion? This inequality is not consistent with the text above. In particular, this inequality contains only $k(t-1)$, and the superscript $k(t)-1$ does not appear in the inequality.

Answer

Thank you for pointing out the typo regarding Equation (5)! As you pointed out, the term should be $k(t-1)$, not $k(t)-1$. We will correct this in the revised version of the manuscript.

We thank you for your positive feedback and constructive comments. The detailed answers to each of the questions can be found below.

---

Weakness 1

Experimental Validation: While the paper provides empirical results, the experiments could be expanded to include a broader range of game types and noise levels to further validate the robustness and generalizability of GABP.

Answer

We would like to note that the main contribution of this paper lies in its theoretical aspects, and the experimental validation serves as supportive evidence. Indeed, most existing studies on learning in monotone games either completely lack experimental results or solely focus on experiments with zero-sum games at a single noise level. That being said, if you are still concerned about this, we will be able to conduct some additional experiments.

---

Weakness 2

Comparison with State-of-the-Art: The paper compares GABP with APMD and Optimistic Gradient Ascent (OGA) but could benefit from a more comprehensive comparison with other existing methods in the literature to better situate its contributions.

Answer

We can argue that OGA is a representative baseline that ensures last-iterate convergence under full feedback. Among payoff-perturbed algorithms, there are some highly regarded ones, such as Sokota et al. [2023] and Liu et al. [2023], although they do have no theoretical guarantee under noisy feedback. In contrast, we are the first to provide a theoretical guarantee for last-iterate convergence under noisy feedback.

---

Weakness 3

Practical Considerations: While the paper addresses the theoretical aspects of GABP, it could provide more insights into practical considerations, such as the implementation challenges and potential modifications needed for real-world applications.

Answer

We believe that our technique could be applied to real-world applications, due to its simplicity. While this issue is beyond the scope of this paper, as you are pointing out, our perturbation approach would help us to solve large-scale imperfect information games [Perolat et al. 2022] and minimax optimization for preference learning with LLMs [Munos et al. 2023], especially because our technique is effective for training even with deep neural network architectures. We will extend our algorithm in a follow-up paper.

• Munos, Rémi, et al. “Nash learning from human feedback.” 2023.
• Perolat, Julien, et al. "Mastering the game of Stratego with model-free multiagent reinforcement learning." 2022.

We thank you for your positive feedback and constructive comments. The detailed answers to each of the questions can be found below.

---

Weakness 1

The game considered in this paper is motivated by real-life examples. But the authors only give one example motivating monotone games.

Answer

As we have elaborated in the introduction section, monotone games include a wide range of applications other than concave-convex games, such as Cournot competition, two-player zero-sum imperfect information games, and zero-sum polymatrix games. For instance, Munos et al. [2023] and Perolat et al. [2022] have demonstrated the perturbation of the payoff function is effective for equilibrium learning in large-scale imperfect information games, as well as minimax optimization for preference learning with large language models. We believe these examples highlight the adaptability and practicality of our technique in real-world applications.

• Rémi Munos, et al. “Nash learning from human feedback.” 2023.
• Julien Perolat, et al. "Mastering the game of Stratego with model-free multiagent reinforcement learning." 2022.

---

Weakness 2

Part of contributions of the paper is claimed to be the study of two feedback models: full feedback and noisy feedback, but there is not specific examples and applications illustrating the importance of these settings. For sure readers can always find related works even just by googling the keywords, but providing concrete application scenes where the gradient of payoff can be achieved perfectly or only partially achievable gradients can be obtained is important, especially "noisy feedback" can be just a model of many cases.

Answer

The full feedback setting serves as an ideal and significant benchmark for evaluating algorithms. We can argue that the noisy feedback setting is more practical, as feedback or observations in real-world scenarios often fluctuate. For instance, when training neural networks or learning in large-scale imperfect information games, it becomes necessary to estimate the gradient from sampled data. This process inevitably prevents the observation of a perfect gradient vector.

---

Question 1

Noisy feedback has been studied in some previous works e.g. Mertikopoulos and Zhou, 2019, Hsieh et al. 2019. What is technical difference/challenge of this paper comparing to aforementioned ones?

Answer

While Hsieh et al. [2019] and Mertikopoulos and Zhou [2019] have assumed strictly variational stability or strong monotonicity, our study has achieved last-iterate convergence in (not necessarily strongly) monotone games. Last-iterate convergence in non-strongly monotone games with noisy feedback has been largely unexplored, with only asymptotic convergence being provided, except for the work by Abe et al. [2024]. Contrarily, we have derived a faster last-iterate convergence rate in the noisy feedback setting by introducing a novel perturbation payoff function.

We thank you for your positive feedback and constructive comments. The detailed answers to each of the questions can be found below.

---

Weakness 1

The authors should include a table which compares their paper with others in the literature. This would make it easier for the reader to place the results in context and see where improvements are made more easily. (for example comparison to [Yoon and Ryu, 2021, Cai and Zheng, 2023] including constants)

Answer

Thank you for your insightful suggestion. We agree that a comparative table would indeed provide a clearer context for the readers. Please find below a table that compares our work with the existing literature, including Yoon and Ryu [2021] and Cai and Zheng [2023]. In summary, our GABP enjoys a nearly optimal convergence rate under full feedback and a much faster rate under noisy feedback, compared to existing studies. We will include this table in the updated manuscript.

---

Weakness 2

The idea of changing the anchoring slowly seems very interesting. How different is this approach from the two-scale GDA type algorithms that have been studies recently (For example, see Lin, Tianyi, Chi Jin, and Michael Jordan. "On gradient descent ascent for nonconvex-concave minimax problems." International Conference on Machine Learning. PMLR, 2020. and follow up papers). Can a similar algorithm be derived from the updates of the algorithms proposed by the authors of this paper?

Answer

GABP and two-timescale GDA are fundamentally different from both the algorithmic and convergence guarantee perspectives. From an algorithmic viewpoint, two-timescale GDA uses different learning rates for each player, whereas our GABP employs identical learning rates for all players. Furthermore, GABP introduces the payoff perturbation technique, which is not utilized in two-timescale GDA. This perturbation technique is an essential element for our GABP to achieve last-iterate convergence even under noisy feedback.

From the perspective of convergence guarantee, our GABP achieves last-iterate convergence, whereas two-timescale GDA has only been shown to converge in an average-iterate sense. However, it is indeed an intriguing direction to improve the convergence results of two-timescale GDA by incorporating our payoff perturbation technique.