Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness

Dear reviewer,

Thank you for your time, constructive input and strong positive evaluation! We reply to your remarks and questions below:

---

Would it be possible to include an actual simulation of the examples? I understand that the character of this paper is theoretical, but an exemplary computational simulation could provide further context.

The way that OpenReview has been set up this year, it is not possible to include any simulations during the rebuttal stage (either through a link to an external image or via an anonymized github / Jupyter notebook). However, we will be happy to present a simulation campaign examining the convergence of FTRL in atomic, non-splittable routing games with data taken from the well-known "TransportationNetworks" dataset of bstabler, which is a standard dataset for routing recommendation problems (we do not provide an external link to avoid violating the rebuttal guidelines).

---

How could the theoretical findings be leveraged to advance practical learning applications?

Some practical learning applications where the theoretical findings can be leveraged are

1. Markov potential games in the context of multi-agent reinforcement learning.
2. Atomic, non-splittable routing games with arbitrary (increasing) cost functions.
3. Cournot competitions for agents with no (or small) price-setting power; etc. The robustness property implies that algorithms like FTRL can enjoy significantly faster convergence in such settings. However, our paper goes beyond simply identifying sufficient conditions for the convergence of FTRL. It also establishes that certain non-robust equilibrium configurations are ruled out as valid asymptotic outcomes of regularized learning. This insight highlights a broader practical concern: it helps explain why some learning problems, such as training GANs, remain inherently unstable and challenging.

---

$^1$ Justification of the existence of robust equilibria in the classes mentioned above:

1. For Markov potential games: Theorem 3.1 of Leonardos et al. (2022) guarantees the existence of a determinstic Nash policy. This is an extreme point of the players' policy polytope, which is thus generically sharp (in the sense of Polyak, 1987), and hence robust.
2. For atomic, non-splittable routing games: see Rosenthal (1973) and note that strict Nash equilibria of finite games are robust.
3. For Cournot competitions: Nash-Cournot equilibria in Cournot games are characterized as solutions to a certain quadratic problem, with the quadratic coefficient determined by the agents' aggregate price-setting power (Monderer & Shapley, 1996). If the agents do not have price-setting power (or their price-setting power is relatively small), the solutions of said quadratic problem that do not exceed the agents' capacity are, by necessity, extreme, and hence generically robust.

---

References

• S. Leonardos, W. Overman, I. Panageas, and G. Piliouras, "Global convergence of multi-agent policy gradient in Markov potential games," ICLR 2022.
• D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, 14(1):124 – 143, 1996.
• B. T. Polyak, Introduction to Optimization. New York, NY, USA: Optimization Software, 1987.
• R. W. Rosenthal, “A class of games possessing pure-strategy Nash equilibria,” International Journal of Game Theory, vol. 2, pp. 65–67, 1973.

I think there is a typo between lines 139 and 140: "for all $x_i$" instead of "for all $x$"

You are right, thanks for the catch!

---

Thank you again for your time, input and positive evaluation—please do not hesitate to reach out if you have any further questions or remarks, we are looking forward to a constructive exchange during the discussion phase!

Kind regards,

The authors

Dear reviewer,

Thank you for your time and input. We reply to your remarks and questions below:

The robust equilibrium assumption is very strong: it restricts the solutions to extreme points with gradients in the interior of the polar cone. As the main theorems assume that the primal iterates stay in a neighborhood of this extreme point, the results are relatively straightforward: in a neighborhood, all gradients are oriented "toward" this extreme point, and the trajectory of the dual iterates is easily characterized.

We would like to clarify two points regarding this comment.

First, in Theorem 2, we do not assume that "the primal iterates stay in a neighborhood of this extreme point". We only assume that FTRL is not initalized too far from said point, and the first important component of the proof is devoted precisely to establishing the stability of FTRL, i.e., that, with high probability, the induced sequence of play does not stray too far from equilibrium. [The key technical elements of this proof is Lemma C.1, which is in turn used to establish the stability bounds of Eqs. (C.25) and (C.26) in the proof of Theorem 2 in Appendix C.]

By virtue of Theorem 2, the event $\mathcal{E} = \{\lim_{n\to\infty} x_n = x^\ast\}$ has probability $\geq 1-\delta$. For generality and notational convenience, Theorems 3 and 4 are predicated on this event but, again, the fact that the primal iterates of FTRL stay in a neighborhood of $x^\ast$ with high probability is not an assumption, but something which we rigorously show (and, in fact, one of the main technical challenges that we had to resolve).

Second, the fact that gradients are oriented "toward" an extreme point does not suffice to establish convergence in a straightforward manner—in fact, this is false under different algorithms/setups.

To see this, consider the simple, single-agent problem of maximizing the function $u(x) = x$ over $\mathcal{X} = [0,1]$ with the projected stochastic gradient ascent algorithm

$$x_{n+1} = \Pi(x_n + \gamma \hat v_n) \qquad \textrm{(SGA)}$$

where $\hat v_n$ is a stochastic gradient of $u$ at $x_n$, i.e., $\hat v_n = 1 + U_n$ for some noise process $U_n$. For simplicity, assume further that $U_n$ is a Bernoulli process with $U_n = \pm 1$ with probability $1/2$.

In this toy example, $x^\ast = 1$ is a robust equilibrium. However, even if $x_n = x^\ast$ for some $n$, we would still have $x_{n+1} = 1-\gamma$ with probability $1/2$, so, by a straightforward application of the Borel-Cantelli lemma, we conclude that, with probability $1$, (SGA) does not converge to $x^\ast$.

This shows that it is not straightforward to show that a given learning algorithm converges to a robust equilibrium in the presence of noise and uncertainty—and, in fact, outside the class of FTRL, this intuition is not correct.

Finally, we should point out that many well-studied classes of games admit robust equilibria, for example:

1. Atomic, non-splittable routing games with arbitrary (increasing) cost functions
2. Markov potential games in the context of multi-agent reinforcement learning
3. Cournot competitions for agents with no (or small) price-setting power.

We did not discuss these examples at length in the submitted version, but we will be happy to take advantage of the extra page and include a version of this discussion in the first revision opportunity.$^1$

---

$^1$ Justification of the existence of robust equilibria in the classes mentioned above:

1. For atomic, non-splittable routing games: see Rosenthal (1973) and note that strict Nash equilibria of finite games are robust.
2. For Markov potential games: Theorem 3.1 of Leonardos et al. (2022) guarantees the existence of a determinstic Nash policy. This is an extreme point of the players' policy polytope, which is thus generically sharp (in the sense of Polyak, 1987), and hence robust.
3. For Cournot competitions: Nash-Cournot equilibria in Cournot competitions are characterized as solutions to a certain quadratic problem, with the quadratic coefficient determined by the agents' aggregate price-setting power (Monderer & Shapley, 1996). If the agents do not have price-setting power (or their price-setting power is small), the solutions of said quadratic problem that do not exceed the agents' capacity are, by necessity, extreme, and hence generically robust.

---

Could the assumptions on being a non-equilibrium for the non-convergence in Proposition 1 be relaxed? Proposition 3 shows that being non-robust is not enough, but perhaps a more precise characterization depending on the regularizer is possible? This could justify the very restrictive assumption of robustness.

In the stated context, robustness is much more than an assumption / desideraturm, it is essentially a necessary condition. Specifically, Proposition 2 shows that if the noise affecting FTRL is persistent (in that it has positive covariance throughout), the sequence of play generated by FRTL cannot converge with positive probability to an interior equilibrium—or, more generally, to a non-extreme equilibrium.

Together with Proposition 3, these results imply that only robust equilibria can admit robust convergence guarantees. The proof of Proposition 3 required introducing results from Markov chain theory on the recurrence versus transience of a biased random walk with vanishing bias—tools that, to the best of our knowledge, have not been applied in this context before. This result also highlights the technical difficulty of the problem: even for a simple one-player, one-dimensional examples, establishing non-convergence requires substantial machinery and novel tecnhiques. A complete characterization of convergence behavior based on the choice of regularizer remains an open and highly challenging problem, and our work provides a suggestive first step in that direction.

---

Thank you again for your time and input—we are looking forward to further constructive exchanges during the rebuttal phase.

Kind regards,

The authors

---

References

• S. Leonardos, W. Overman, I. Panageas, and G. Piliouras, "Global convergence of multi-agent policy gradient in Markov potential games," ICLR 2022.
• D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, 14(1):124 – 143, 1996.
• B. T. Polyak, Introduction to Optimization. New York, NY, USA: Optimization Software, 1987.
• R. W. Rosenthal, “A class of games possessing pure-strategy Nash equilibria,” International Journal of Game Theory, vol. 2, pp. 65–67, 1973.

Dear reviewer,

Thank you for your time and constructive input. We reply to your remarks and questions below:

It is not clear which kinds of games could admit a robust equilibrium. Given that the existence of a robust equilibrium is a precondition for the convergence result in Thm 2, the lack of discussion on the existence of a robust equilibrium makes the value of this result less clear. [...] Can the author provide a characterization of the existence of a robust Nash equilibrium as defined in Definition 1? For example, in which kind of important and interesting games does the robust Nash equilibrium necessarily exist? (This is my main concern. I would be happy to increase my evaluation score if this issue is addressed.)

Certainly! Some widely studied classes of games that always admit robust equilibria (except for a measure zero set of instances) are as follows:

1. Atomic, non-splittable routing games with arbitrary (increasing) cost functions.
2. Markov potential games in the context of multi-agent reinforcement learning.
3. Cournot competitions for agents with no (or small) price-setting power.

We did not discuss these examples at length in the submitted version, but we will be happy to take advantage of the extra page and include a version of this discussion in the first revision opportunity.$^1$

---

$^1$ Justification of the existence of robust equilibria in the classes mentioned above:

1. For atomic, non-splittable routing games: see Rosenthal (1973) and note that strict Nash equilibria of finite games are robust.
2. For Markov potential games: Theorem 3.1 of Leonardos et al. (2022) guarantees the existence of a determinstic Nash policy. This is an extreme point of the players' policy polytope, which is thus generically sharp (in the sense of Polyak, 1987), and hence robust (by the characterization of Theorem 1).
3. For Cournot oligopolies: Nash-Cournot equilibria in Cournot games are characterized as solutions to a certain quadratic problem, with the quadratic coefficient determined by the agents' aggregate price-setting power (Monderer & Shapley, 1996). If the agents do not have price-setting power (or their price-setting power is small), the solutions of said quadratic problem that do not exceed the agents' capacity are, by necessity, extreme, so the resulting equilibria are generically robust.

---

For example, it seems that all the interior equilibria will not be robust according to Thm 1, which implies that a robust equilibrium may not exist in many interesting unconstrained games, such as GANs.

Yes, this is precisely the point! Proposition 2 shows that, under persistent noise, the sequence of play generated by FTRL with a non-vanishing step-size cannot converge with positive probability to an interior equilibrium—or, more generally, to non-extreme equilibria.

Put differently, our paper does not simply provide a sufficient condition for convergence of FTRL, but it also rules out other, non-robust equilibrium configurations as valid limits of regularized learning. This is a cautionary tale which we believe carries important insights for practitioners because it provides a plausible explanation as to why certain machine learning models (including GANs) are notoriously difficult to train.

---

It is not very well-motivated to consider the constant step size FTRL dynamics, given that the vanishing step size is a benchmark in the theoretical analysis of the convergence properties of FTRL.

We should first point out that our results have been stated with a constant step-size only for clarity and simplicity of presentation. In particular, Theorems 2-4 apply verbatim to FTRL with a variable, non-constant step-size schedule $\gamma_n$ with $\gamma:= \sup_n \gamma_n$ and $\liminf_n \gamma_n >0$.

[The required modifications in the proofs are trivial, but we would be happy to detail them if you want, and we will of course be happy to adapt our presentation in the first revision opportunity]

Now, the use of a vanishing step-size schedule—typically satisfying a Robbins-Monro summability condition like $\sum_n \gamma_n^2 < \sum_n \gamma_n =\infty$ or a variant thereof—is indeed common in the stochastic approximation literature. At the same time however, it introduces an inverse recency bias, in that new information enters the algorithm with decreasing weights. This feature of vanishing step-size schedule contradicts "the general principles of iterative schemes, in accordance to which new information is more important than old one" (Nesterov, 2009, p. 224), and is well-known to suffer from important drawbacks, both theoretical and practical:

• From a theory standpoint, it is known that FTRL with a vanishing step-size schedule may lead to superlinear regret, even in simple instances like the exponential weights algorithm (Orabona and Pál, 2018). This is an important part of the reason that FTRL was introduced and analyzed in online learning with a constant step-size, cf. the textbooks of Shalev-Shwartz (2011) and Lattimore & Szepesvári (2020).
• From a practical standpoint, gradient methods with a vanishing step-size suffer from slow warm-up periods, and take a long time to converge to a neighborhood of an equilibrium point. By contrast, in machine learning setups, constant step-size methods reach the vicinity of a solution very fast (often within 0.1% accuracy), cf. Dieuleveut et al. (2020).

For this reason, in many state-of-the-art transformers and LLMs, step-size schedules are often constant over billions (or even trillions) of samples. For example, DeepSeek is trained as follows (DeepSeek v3 technical report, Section 4.2):

We keep a constant learning rate of 2.2 × 10−4 until the model consumes 10T training tokens.
[...]
During the training of the final 500B tokens, we keep a constant learning rate of 2.2 × 10−5 in the first 333B tokens, and switch to another constant learning rate of 7.3 × 10−6 in the remaining 167B tokens.

Of course, there are no silver bullets in optimization: we do not claim that non-vanishing step-size schedules are universally superior to vanishing ones (each has its trade-offs, advantages and disadvantages) but, overall, the use of non-vanishing schedules is very strongly grounded in both theory and practice.

---

It is not clear whether the result of Theorem 2 also applies to the vanishing step size case.

Yes, it actually does! The key observation is that Lemma C.1 continues to hold under a vanishing step-size rule with the RHS of (C.8) replaced by

$$\frac{\sum_{k=1}^n \gamma_k^{q(1-\mu) \sigma_k^q}}{(\sum_{k=1}^n \gamma_k)^{1+q(\mu-1/2)}}$$

If coupled with a Robbins-Monro / Kiefer-Wolfowitz summability condition, this modified version of Lemma C.1 is sufficient for the proof of Theorem 2 to go through essentially verbatim, replacing $\gamma n$ with $\sum_{k=1}^n \gamma_k$.

We did not tackle this case because we wanted to keep the analysis as simple as possible, but we will be happy to include the above.

---

Does the dynamic robustness result still hold when considering the average-iterate behavior of FTRL dynamics?

Theorems 2-4 hold automatically for the time-average of $x_n$ (since $x_n$ converges, so does its time-average). However, the rate for the time-average would be much slower than (16), since time-averages cannot converge at a rate faster than $\mathcal{O}(1/t)$.

---

Is it possible to define robustness for mix Nash equilibrium?

In the context of finite games, mixed Nash equilibria are interior, so they are not robust.

---

Thank you again for your time and input—we look forward to further constructive exchanges during the discussion phase.

Kind regards,

The authors

---

References

• A. Dieuleveut, A. Durmus, and F. Bach, "Bridging the gap between constant step size stochastic gradient descent and Markov chains," The Annals of Statistics, vol. 48, no. 3, 2020.
• T. Lattimore and C. Szepesvári, Bandit Algorithms. Cambridge, UK: Cambridge University Press, 2020.
• S. Leonardos, W. Overman, I. Panageas, and G. Piliouras, "Global convergence of multi-agent policy gradient in Markov potential games," ICLR 2022.
• D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, 14(1):124 – 143, 1996.
• Y. Nesterov, “Primal-dual subgradient methods for convex problems,” Mathematical Programming, vol. 120, no. 1, pp. 221–259, 2009.
• F. Orabona and D. Pál, “Scale-free online learning,” Theoretical Computer Science, vol. 716, pp. 50–69, 2018.
• B. T. Polyak, Introduction to Optimization. New York, NY, USA: Optimization Software, 1987.
• R. W. Rosenthal, “A class of games possessing pure-strategy Nash equilibria,” International Journal of Game Theory, vol. 2, pp. 65–67, 1973.

Dear reviewer,

Thank you for your time, detailed input, and strong positive evaluation! We reply to your remarks and questions below:

---

There could be more intuition provided about the proof for Theorem 2 which is the main theorem showing sufficiency of strategic robustness for dynamic robustness. Namely, describing the main technical ideas/tools to analyze convergence of FTRL and how strategic robustness enters this would be helpful.

Sure thing. The key idea is that, under the conditions of Theorem 2, the auxiliary process $y_n$ (which aggregates the players' individual gradient steps) escapes to infinity along a direction which is "just right" in the sense that it carries the sequence of chosen actions $x_n = Q(y_n)$ toward the equilibrium in qeustion.

A bit more formally, the intuition and key steps for the proof are as follows:

1. From Theorem 1 (and the continuity of the players' payoff functions), strategic robustness of an equilibrium $x^\ast$ implies that the players' individual gradient field points toward $x^\ast$ in a neighborhood thereof.
2. As a result, the "gradient update" component of the FTRL algorithm—that is, the $y_{n+1} = y_n + \gamma \hat v_n$ part of the process—aggregates gradient steps that are, on average, aligned along the interior of the normal cone $\mathrm{NC}(x^\ast)$ to the players' action space $\mathcal{X}$ at $x^\ast$.
3. Because of this alignment, the process $y_n$ exhibits a consistent drift that takes it deeper and deeper toward a "copy" of the normal cone $\mathrm{NC}(x^\ast)$ that lives in the gradient space $\mathcal{Y}$. [The consistency of this drift is not easy to show: this is the subject of Lemma C.1 in Appendix C, and the first part of the proof of Theorem 2, again in Appendix C]
4. In tandem to the above, we show that, with very high probability, the process never strays too far from $x^\ast$. [Again, this is quite technical: it requires a tandem application of Proposition C.1 / Corollary C.1, and the supremum estimation of Eqs. (C.25) and (C.26) in Appendix C.]
5. Combining all of the above, Proposition 1 allows us to show that the sequence of chosen actions $x_n = Q(y_n)$ under (FTRL) converges to $x^\ast$.

Please let us know if this is clear enough! We will be happy to include a version of this discussion in the first revision opportunity—we did not do so in the submitted version of the paper due to lack of space.

---

Do you think this connection will extend to other dynamics, such as gradient descent?

Great question—both yes and no.

To explain what we mean, consider the unconstrained (stochastic) gradient ascent algorithm

$$x_{n+1} = x_n + \gamma \hat v_n \qquad \text{(SGA)}$$

where $\hat v_n$ is some stochastic payoff gradient. The gradient algorithm (SGA) is captured directly from our setup in the case $\mathcal{X} = \mathbb{R}^d$ by taking $h(x) = \|x\|^2/2$ (cf. Example 2.2 in L178 our paper).

Now, in the constrained case, there are two variants of (SGA) to consider. The first interleaves gradient steps and projections as

$$x_{n+1} = \Pi(x_n + \gamma \hat v_n) \qquad \textrm{(P-SGA)}$$

where $\Pi$ denotes the standard Euclidan projection on $\mathcal{X}$. The second is known as "SGA with lazy projections" (Zinkevich, 2003) and proceeds as

$$y_{n+1} = y_n + \gamma \hat v_n, \quad x_{n+1} = \Pi(x_n) \qquad \textrm{(L-SGA)}$$

i.e., the algorithm aggregates gradient steps and then projects the result onto $\mathcal{X}$, cf. Zinkevich (2003), Nesterov (2009), Shalev-Shwartz (2011) and references therein.

The latter version of the stochastic gradient dynamics (L-SGA) is one of the archetypal examples of FTRL. We mentioned this in Example 2.2 (L178), but there was no space to expand upon this in detail—we would be more than happy to include a detailed discussion along the above lines at the first revision opportunity.

---

Thank you again for your constructive input, encouraging words and strong positive evaluation—please do not hesitate to reach out if you have any further questions!

Kind regards,

The authors

---

References

• Y. Nesterov, “Primal-dual subgradient methods for convex problems,” Mathematical Programming, vol. 120, no. 1, pp. 221–259, 2009.
• S. Shalev-Shwartz, “Online learning and online convex optimization,” Foundations and Trends in Machine Learning, vol. 4, no. 2, pp. 107–194, 2011.
• M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in ICML ’03: Proceedings of the 20th International Conference on Machine Learning, pp. 928–936, 2003.