Slingshot Perturbation to Learning in Monotone Games

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

Weakness 1

(1) The authors didn't give any impossibility results (lower bounds) on the convergence rate. I would suggest the authors to present some lower bound results to contrast with the upper bound results they give, even if the lower bounds can be from previous work.

Answer

Thank you for your valuable comment regarding the tightness of our derived convergence rates. We agree that establishing lower bounds for our algorithm in both full and noisy feedback settings would be a promising future direction. In fact, to the best of our knowledge, no existing research has derived a lower bound for the noisy feedback setting. We will strive to provide a lower bound for our algorithm in full and noisy feedback settings in future work.

Weakness 2

(2) The $O(T^{-1/10})$ bound for finding exact Nash equilibrium in the noisy feedback case (Theorem 5.2) does not seem to be tight. It would be great if the authors can provide some discussion on the tightness of this result.

Answer

Our convergence rate in the noisy feedback could be improved because we have roughly derived the upper bound on $\langle \nabla_{\pi_i}v_i(\pi^{\mu, \sigma^k}), \pi^{\mu, \sigma^{k-1}} - \sigma^k\rangle$ by using Cauchy–Schwarz inequality in the proof of Lemma F.2. We will mention the potential for improvement in our convergence rate in the subsequent revision.

Weakness 3

(3) While the convergence rates to approximate equilibria (Section 4) are presented for any general $G$ functions, the convergence rates for exact Nash equilibria (Section 5) are only for $G$ being the squared $\ell^2$-distance. The authors say that Theorem G.1 and G.2 are for other $G$ functions, but they are only asymptotic results, with no quantitative convergence rates. Given that the main contribution of this paper is a unified framework, I feel that a quantitative convergence rate for general $G$ function is needed.

Answer

We would like to emphasize that existing studies have only provided asymptotic last-iterate convergence results for special cases of $G$, such as KL divergence [Perolat et al., 2021] or reverse KL divergence [Abe et al., 2023]. Our work significantly contributes to this field by (i) generalizing these results to a wider class of $G$ functions, and (ii) deriving a non-asymptotic last-iterate convergence rate for a specific $G$ function. We acknowledge the importance and challenge of extending Theorems 5.1 and 5.2 to general $G$ functions, which we view as an intriguing open problem for future work.

Question 1

The cited related work [Cai-Luo-Wei-Zheng, 2023, Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games] shows that the Nash equilibria of 2-player zero-sum games can be found by an uncoupled learning algorithm with bandit feedback with $O(T^{-1/8})$ convegence rate.

Answer

As you pointed out, Cai et al. [2023] have analyzed settings that are subtly different from ours, both in terms of the feedback type (bandit feedback vs noisy feedback), and the type of game (two-player zero-sum matrix games or Markov games vs $N$-player monotone games). This distinction makes it challenging to draw a straightforward comparison between the convergence rate of theirs and ours in Theorem 5.2.

Moreover, the algorithm proposed by Cai et al. [2023] involves a decreasing perturbation strength $\mu_t$ over iteration $t$. However, in our method, as indicated in Theorem 4.2, a smaller $\mu$ necessitates a correspondingly smaller learning rate $\eta$. This could potentially slow down the convergence rate and make it difficult to find an appropriate learning rate. Therefore, for the sake of practicality, we have opted to maintain $\mu$ as a constant independent of $t$ in our algorithm.

Many thanks for your encouraging and positive comments on our paper! We appreciate your positive remarks on the writing, the balance of content, and our approach. Your comments greatly encourage our work.

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

Weakness 1

At first glance, the claims about "exact Nash equilibrium" computation can seem misleading.

Answer

Thanks for pointing this out to us. We have replaced the term ‘’exact Nash equilibrium’’ with ‘’Nash equilibrium of the underlying game’’ in our latest version (highlighted in red) to clarify what the term means.

Weakness 2

The algorithm is not fully decentralized. It could be possible to discuss whether the process would converge when the frequency of update of the slingshot strategy and $\mu$ varied across players.

Answer

When each player may have a distinct perturbation strength $\mu_i>0$, convergence results very similar to the theorems in Section 4 are expected to be obtained. This is because strong convexity for every perturbed payoff function is still maintained. Consequently, we expect the behavior to be consistent with these theorems, substituting $\mu$ with the smallest perturbation strength $\min_{i\in [N]}\mu_i$ across all players.

For the scenarios where the frequency of updates of the slingshot strategy, $T_{\sigma}$, varies among players, that is, each player updates the slingshot strategy at his or her own timing, we assume that each player independently adheres to the lower bound on $T_{\sigma}$ as defined in Theorems 5.1 or 5.2. Under this condition, we are expected to obtain similar convergence rates as in these theorems.

Therefore, we believe that we can fully decentralize our algorithm with ease. We also agree that further analysis of this asymmetric setup would present an intriguing and promising avenue for future research.

Question 1

Do you think that the slingshot perturbation framework achieves no adversarial regret?

Answer

Although a no-regret guarantee is not crucial for ensuring last-iterate convergence, we guess the FTRL-SP would achieve the no-regret property. This is because FTRL-SP updates the slingshot strategy so that it converges to the best response against the current strategy of the opponent. However, this does not always admit an optimal rate. We will mention this issue in the subsequent revision upon your request.

Question 2

What would happen if a fixed number of agents did not update their slingshot strategy every time or every player had their own frequency of updating the slingshot strategy?

Answer

We anticipate that if some agents do not update their slingshot strategy, or if $T_{\sigma}=\infty$ for some agents, it would disrupt the last-iterate convergence property. Specifically, the strategy of the player with $T_{\sigma}=\infty$ at least would not reach a Nash equilibrium strategy.

With regards to the scenario where each player has their own $T_{\sigma}$, we have addressed this in our response to Weakness 2.

Question 3

Would it be possible to tune $\mu$ as well to achieve better convergence rates?

Answer

We appreciate your insightful suggestion regarding the tuning of $\mu$ for better convergence rates. Indeed, setting $\mu$ to a small value that depends on $T$ could potentially lead to improved convergence rates. However, as we have implied in Theorem 4.2, a smaller $\mu$ would necessitate a smaller learning rate $\eta$, which could make the balancing between $\mu$ and $\eta$ quite challenging. For the sake of practicality, we have opted to maintain $\mu$ as a constant independent of $T$.

Question 2

Do you require $G$ to have bounded gradient in section 5? Otherwise I think you cannot use some statements such as theorem 4.2 and 4.9 in section 5.

Answer

No, we do not require the gradient of $G$ to be bounded for Theorems 5.1, 5.2, G.1, and G.2. Therefore, we believe that these theorems hold for a wide range of divergence functions.

Question 3

Way don't you consider dynamic $\mu=\mu_k$ in section 5? Diminishing it every $T_{\sigma}$ turns would help as long as you can bound the distance (with either $G$ of $D$) between $\pi^{\mu_k}$ and $\pi_{\mu_{k+1}}$.

Answer

Thank you for your insightful comment! We would first like to point out that we have already given the non-asymptotic convergence rates to exact Nash equilibria in Theorems 5.1 and 5.2 for our approach (of course, they also mean the asymptotic rates). As in Theorem 4.2, when the perturbation strength $\mu$ is small, a correspondingly small learning rate $\eta$ should be used. Consequently, the convergence speed would slow down if we were to adopt an approach where $\mu_k$ decreases as $k$ increases, and finding a proper learning rate would be difficult. On the contrary, our slingshot update approach does not require a decaying $\mu_k$. Hence, our method does not suffer from the stringent requirement of selecting appropriate $\mu$ and $\eta$ and is more robust than decaying perturbation approaches in terms of hyperparameter settings.

Question 4

Way MWU does not converge in figure 1, without noise?

Answer

Figure 1 shows the exploitability of the last-iterate strategy of each algorithm. As we previously addressed in our response to Weakness 1, MWU’s last-iterate strategy indeed fails to converge even with full feedback. This phenomenon has been widely owhebserved and discussed in several studies [Perolat et al., 2021, Abe et al., 2023, Liu et al., 2023]. Furthermore, it has even been theoretically substantiated by Mertikopoulos et al. [2018] and Bailey and Piliouras [2018].

Thank you for taking the time to review our work and for providing your valuable feedback. We appreciate your insights and understand that you may have some concerns regarding certain aspects of our study. Our responses below address these concerns.

Weakness 1

Usually no-regret algorithm still converge in full feedback, to some sort of equilibria even in the presence of noisy feedback as long as the loss used are unbiased. The authors should discuss better why existing techniques fail, why now they only fail in terms of experimental evaluation.

Answer

Standard no-regret algorithms like MWU converge to a Nash equilibrium only when one averages strategies over iterations to obtain the exact equilibrium strategy, since the dynamics make an orbit around it. While this property is well-known as average-iterate convergence, we focus on last-iterate convergence, where an algorithm converges to an equilibrium without taking the average of the strategies. We hope this clarifies the difference between the concepts of average-iterate and last-iterate.

Previous studies [Daskalakis and Panageas, 2019, Mertikopoulos et al., 2019, Wei et al., 2021] have shown that optimistic no-regret algorithms, such as OWMU and OGD, enjoy last-iterate convergence only with full feedback, but fail with noisy feedback [Abe et al. 2023]. Roughly speaking, the success with full feedback is due to the proper bound of the variation of the gradient feedback vectors $\sum_{i=1}^N\\|\widehat{\nabla}\_{\pi_i}v_i(\pi^t) -\widehat{\nabla}\_{\pi_i}v_i(\pi^{t-1})\\|^2$ over iterations. More formally, we define the path length of the gradient feedbacks as $\sum_{s=1}^t\sum_{i=1}^N\\|\widehat{\nabla}\_{\pi_i}v_i(\pi^s) -\widehat{\nabla}\_{\pi_i}v_i(\pi^{s-1})\\|^2$. Noisy feedback makes the path length large, leading to the failure of optimistic no-regret algorithms to converge to an equilibrium.

Thus, achieving last-iterate convergence with noisy feedback is still a significantly challenging task. We will explain the intuition in our paper's Introduction or related literature section.

Weakness 2

You give guarantees on the exploitability of the last iterate strategy, but not on the convergence rate to the strategy itself, as you do in theorem 4.2 and 4.10 for approximate nash.

Answer

First, we would like to clarify that the convergence of exploitability means that the last-iterate strategy itself converges to an equilibrium. Therefore, our results (Theorems 5.1 and 5.2) inherently indicate that we have provided the convergence rate of the strategy itself. Exploitability is a standard measure of proximity to a Nash equilibrium, as used in several studies [Cai et al., 2022a,b, Abe et al., 2023, Cai and Zheng, 2023].

Question 1

What are the new techniques introduced here that are designed to help with noisy feedback?

Answer

The techniques devised in this paper are manifold.

• We have developed a subtly different perturbation technique from the existing ones you mentioned so that it enables the FTRL or MD dynamics to converge to an approximate equilibrium in underlying games (an equilibrium in perturbed games).
• The existing studies only show the sort of convergence only with full feedback, and we have been successful with noisy feedback. So, we are the first to establish last-iterate convergence with noisy feedback.
• Our perturbation technique also provides a comprehensive view of payoff-regularized algorithms such as Perorat et al. [2021] and Abe et al. [2022].
• Furthermore, the idea of the slingshot strategy update leads us to find a Nash equilibrium in underlying games (not an approximate one). In other words, it is innovative that we mix the perturbation technique with the slingshot strategy update and exhibit last-iterate convergence with both full and noisy feedback, which has not been achieved so far.

Comment 3

"First, we would like to clarify that the convergence of exploitability means that the last-iterate strategy itself converges to an equilibrium" This is not true. You converge last iterate to an approximate equilibrium, that has comparable exploitability as the true equilibrium, but it could be very far from the actual equilibrium, so last iterate property is less appealing that if the algorithm would converge to the true equilibrium

Answer

As indicated by Theorems 5.1 and 5.2, the exploitability of the last-iterate strategy $\pi^t$ converges $0$. Moreover, according to the definition of exploitability (as we have described in Section 2), the value of exploitability $\mathrm{exploit}(\pi)$ of a given strategy $\pi$ equals $0$ if and only if $\pi$ is an actual Nash equilibrium in the original game. Therefore, Theorems 5.1 and 5.2 mean that the last-iterate strategy $\pi^t$ updated by our FTRL-SP does indeed converge to an actual Nash equilibrium, not an approximate equilibrium.

We will be happy if this clarifies your concerns, although we are still uncertain about why you think last-iterate could be far from the actual equilibrium. Let us know if you think the last iterate property established so far in this literature lacks appeal, please.

Comment 4

In Th 5.1 and 5.2 the assumption on the difference $\pi^{\mu,\sigma^k}-\sigma^{k+1}$ seems to bypass the main difficulty of doing slingshot update, which is that that equilibria can jump from one place to another when the parameter (or losses) are changes, even slightly. It can also be that the assumption are written in a confusing way or that I'm missing something. The authors should definitely discuss if these assumptions are ever met, because they seem pretty strong written as such.

Answer

We would like to emphasize that in our slingshot strategy update framework, the perturbed equilibrium $\pi^{\mu,\sigma^k}$ at $k$-th slingshot update is not far from the next slingshot strategy $\sigma^{k+1}$. Specifically, the assumption that $\|\pi^{\mu,\sigma^k}-\sigma^{k+1}\|\leq \|\pi^{\mu,\sigma^k}-\sigma^k\|\left(\frac{1}{c}\right)^{T_{\sigma}}$ is directly satisfied when Theorem 4.2 holds. This is due to the following reasons:

• Let us set $\sigma=\sigma^k$ and $\pi^0=\sigma^k$ in Theorem 4.2.
• From this theorem, we can immediately deduce that $\|\pi^{\mu,\sigma^k}-\pi^t\| \leq \|\pi^{\mu,\sigma^k} - \sigma^k\|\left(\frac{1}{c}\right)^t$ holds for any $t\geq 1$.
• Therefore, by taking $t=T_{\sigma}$, we obtain $\|\pi^{\mu,\sigma^k}-\pi^{T_{\sigma}}\| \leq \|\pi^{\mu,\sigma^k} - \sigma^k\|\left(\frac{1}{c}\right)^{T_{\sigma}}$.
• Since we use $\pi^{T_{\sigma}}$ as the next slingshot strategy $\sigma^{k+1}$ in our framework, it follows that $\|\pi^{\mu,\sigma^k}-\sigma^{k+1}\|\leq \|\pi^{\mu,\sigma^k}-\sigma^k\|\left(\frac{1}{c}\right)^{T_{\sigma}}$.

Hence, FTRL-SP always satisfies this assumption in the full feedback setting, and we believe that the assumption regarding the difference $\pi^{\mu,\sigma^k}-\sigma^{k+1}$ is not strong. A similar reasoning can be applied to Theorem 5.2 for the noisy feedback setting.

Comment 5

I think it would be more fair to wither consider the average policy in MWU or not to include it at all, when you known that the last iterate convergence would not converge. This is because, the presence of noise could be unknown to the user of the algorithm, but the user would certainly know that it has to take the average strategy for MWU to work. Also it would be fair to include RM, RM+ and equivalent in the experimental evaluations.

Answer

Thank you for your suggestion! We will remove MWU’s results from Figures 1 and 2. Regarding your suggestion to include RM and RM+ in our experimental evaluations, we are currently conducting these experiments. As soon as the results are available, we will update our paper accordingly to provide a more comprehensive analysis.

Thank you for your further comments! Firstly, we would like to summarize the key points of our response to your comments as follows:

• The assumptions of Theorems 5.1 and 5.2 are naturally satisfied by Theorems 4.2 and 4.9, hence they are not strong assumptions.
• Theorems 5.1 and 5.2 guarantee the last-iterate convergence to an actual Nash equilibrium, not a perturbed equilibrium.
• We have also provided the last-iterate convergence results for $G$ other than squared $\ell^2$-distance in Theorems G.1 and G.2.

The details of our responses to each of your comments can be found below.

Comment 1

The algorithm converge last iterate to perturbed equilibrium, not to exact equilibrium. (Convergence to exact eq is given only in section 5 where the authors rely on some strange assumptions about the rate of change of parametric equilibria).

Answer

In Section 5, we have presented Theorems 5.1 and 5.2 that ensure the last-iterate convergence to an actual equilibrium, not to a perturbed one. Your concern might be regarding the assumptions on the difference $\pi^{\mu,\sigma^k}-\sigma^{k+1}$. To clarify, we have addressed this point in our response to Comment 4, where we explain that these assumptions are generally satisfied and thus, are not strong assumptions.

Comment 2

Section 5 (the one in which you actually use slingshot perturbation) only works with $G(a,b)=|a-b|_2^2$. If the authors think that the procedure could also work for other $G$ (see response to review yRC2, weakness 3) they should prove it or tone down the achievements about that part of the paper.

Answer

While our last-iterate convergence rates are indeed provided for the case where $G$ is squared $\ell^2$-distance, we have also established the asymptotic last-iterate convergence results for more general functions $G$ in Theorems G.1 and G.2 (i.e., Bregman divergence, $\alpha$-divergence, Rényi-divergence, and reverse KL divergence). Notably, these results significantly extend the scope of the asymptotic convergence results previously established for KL divergence and reverse KL divergence in existing studies [Perorat et al., 2021, Abe et al., 2022].

Dear Reviewer vVKF,

As you requested, we have included an experimental comparison with the averaged strategies of MWU, RM, and RM+ in Section H.4 of our revised manuscript (highlighted in red). If you're interested, feel free to take a look at these results.

Sincerely,

The Authors

We thank you for your insightful questions. The detailed answers to each of the questions can be found below.

Question 1

I am wondering about the positioning of your results relative to these prior works – especially [1,2]

Answer

Koshal et al. [2010] have provided last-iterate convergence results for the noisy feedback setting in monotone games. However, their results are limited to asymptotic convergence. Similarly, Tatarenko and Kamgarpour [2019] have also demonstrated asymptotic convergence in a payoff-based setting, where only the exact utility value of sampled actions is observable, which is also referred to as bandit feedback [Bravo et al., 2018]. This setting is fundamentally distinct from our noisy feedback setting.

Regarding Hsieh et al. [2020], it is certain that they establish asymptotic convergence results for general monotone games. However, the concrete convergence rates are derived just under certain stronger assumptions, such as strongly monotone games. In contrast, as we stated in our Theorem 5.2, we have derived the non-asymptotic convergence rates for general monotone games.

From an algorithmic standpoint, both Koshal et al. [2010] and Tatarenko and Kamgarpour [2019] have analyzed an iterative Tikhonov regularization method, where the perturbation strength $\mu$ diminishes as the iteration $t$ progresses. However, as we have implied in Theorem 4.2, a smaller $\mu$ would require a smaller learning rate $\eta$. This could potentially decelerate the convergence rate and complicate the task of finding an appropriate $\eta$. For practicality, we have opted to keep $\mu$ as a constant independent of $t$ in our algorithm.

Question 2

When $G$ is the Bregman divergence induced by $\psi$, is the slingshot strategy different to a Bregman regularization step – like e.g., [2] for the Tikhonov / Euclidean case or [4,5] for general case?

Answer

Our slingshot strategy update technique is fundamentally different from [2,4,5]. Specifically, the learning dynamics proposed by Leslie and Collins [2005] and Coucheney et al. [2015] do not update the slingshot strategy. Indeed, the Boltzmann Q-learning dynamics presented in Example 3.3 of our paper represents one such dynamic they proposed. Hence, a part of their dynamics is contained in our FTRL-SP.

More importantly, while Leslie and Collins [2005] and Coucheney et al. [2015] have demonstrated convergence to an approximate Nash equilibrium, we have achieved convergence to a Nash equilibrium of the original game by introducing a slingshot strategy update. We believe this key distinction underscores the unique contributions of our work.

Question 3

How do the results in Section 4 relate to e.g., [6] who established both convergence and convergence rates, even for more general constraints?

Answer

The study of Drusvyatskiy et al. [2022] is distinguished from ours with regard to both the types of games and feedback. They focus on strongly monotone games, which is a special case of our (non-strictly) monotone games, and the payoff-based setting (a.k.a. bandit feedback), which is inevitably different from our noisy feedback setting where the observed gradient vector is contaminated by additive noise.

Question 4

Did you provide an example that I missed? Even if so, what is the benefit of considering non-divergence $G$ functions?

Answer

We have already provided some examples of $G$ functions that are not Bregman divergence in our paper; $\alpha$-divergence, Rényi-divergence, and reverse KL divergence [Abe et al., 2022, 2023]. Also, the detailed last-iterate convergence results for these functions can be found in Theorems G.1 and G.2.

Our motivation to generalize $G$ functions stems from the observation that while Perolat et al. [2021] utilize the KL divergence, Abe et al. [2022, 2023] employ the reverse KL divergence. A unique characteristic distinguishing these studies is that the dynamics in Abe et al. [2022, 2023] is equivalent to replicator mutator dynamics [Zagorsky et al., 2013], while the FTRL dynamics is known to coincide with replicator dynamics without mutation (or perturbation, as referred to in our paper).

Thus, developing a unified framework for payoff-perturbed algorithms is of significant importance. This generalization would provide us with a more profound understanding of such algorithms, particularly in terms of last-iterate convergence.

Reference

[1] Benjamin M. Zagorsky, Johannes G. Reiter, Krishnendu Chatterjee, and Martin A. Nowak. Forgiver triumphs in alternating prisoner’s dilemma. PLOS ONE, pages 1–8, 2013.

Thanks for your comments regarding the standing of Section 4 and the pointer to the related work.

In Section 4, we will include the relationship between our Theorem 4.9 and the convergence results for the studies on strongly monotone games with noisy and bandit feedback [Hsieh et al., 2020, Drusvyatskiy et al., 2022, Huang and Zhang, 2022].

However, we would like to clarify that Theorem 4.9 represents only a part of our contributions. In addition to this, our work also includes:

• We have proposed a unified framework covering a wide array of existing payoff-regularized algorithms.
• Our algorithm achieves last-iterate convergence with rates in general (non-strictly) monotone games with both full and noisy feedback, by introducing the slingshot strategy update.