Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness
Authors: Kyriakos Lotidis
Panayotis Mertikopoulos
Nicholas Bambos
Jose Blanchet
Venue: NeurIPS 2025 poster ()
Keywords: game theory
Nash equilibrium
robust equilibrium
regularized learning
Primary area: theory

Abstract: In this paper, we examine the robustness of Nash equilibria in continuous games, under both strategic and dynamic uncertainty. Starting with the former, we introduce the notion of a robust equilibrium as those equilibria that remain invariant to small—but otherwise arbitrary—perturbations to the game’s payoff structure, and we provide a crisp geometric characterization thereof. Subsequently, we turn to the question of dynamic robustness, and we examine which equilibria may arise as stable limit points of the dynamics of “follow the regularized leader” (FTRL) in the presence of randomness and uncertainty. Despite their very distinct origins, we establish a structural correspondence between these two notions of robustness: strategic robustness implies dynamic robustness, and, conversely, the requirement of strategic robustness cannot be relaxed if dynamic robustness is to be maintained. Finally, we examine the rate of convergence to robust equilibria as a function of the underlying regularizer, and we show that entropically regularized learning converges at a geometric rate in games with affinely constrained action spaces.

Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness
Kyriakos Lotidis Stanford University settadff
Panayotis Mertikopoulos
Univ. Grenoble A Alpes, CNRS, Inria, Grenoble INP
LIG 38000 Grenoble, France panayotis..m mer mertikopoul os@imag. fr
Nicholas Bambos
Jose Blanchet
Stanford University bambos@stanfordd edu
Stanford University
jose. bww.nchtesttaaoor..ccomm
Abstract
In this paper, we examine the robustness of Nash equilibria in continuous games, under both strategic and dynamic uncertainty. Starting with the former, we intro- duce the notion of a robust equilibrium as those equilibria that remain invariant to small-but otherwise
game's payoff structure, and we provide crisp geometric characterization thereof. Subsequently, turn the question of dynamic robustness, and we examine which equilibria may arise stable limit points of the dynamics of "follow the regularized leader" (FTRL) in the presence randomness and uncertainty. Despite their very distinct origins, establish structural correspondence between these two notions of robustness: strategic robustness implies dynamic robustness, and, conversely, the requirement of strategic robustness cannot be relaxed if dynamic robustness to be maintained. Finally, we examine the rate of convergence to robust equilibria as a function of the underlying regularizer, and show that entropically regularized learning converges at geometric rate in games with affinely constrained action spaces.
1 Introduction
A fundamental requirement in game theory-whice predates even the cornerstone notion of Nash cquilibrium-corte concerss the robustness that should be inherent any axiomatization of rational behavior. To quote famous passage we formulate the guiding principles and the objective justification rational behavior, provisos will have to be made for every possible conduct of "the others." If the superiority of rational behavior over any other kind is to be established, then its description must include rules of conduct for all conceivable situations situations-incldding those where "the others" behaved irrationally in the sense of the standards which the theory will set for them."
Neumann & Morgenstern [53, p. 32]: "In whatever way
As byproduct of this tenet, there has been flurry of activity since the 1970s in proposing refinements of the Nash equilibrium concept, all in an effort to dismiss equilibria that are highly fragile or otherwise implausible (e.g., because they involve threats that are not credible). ! This pursuit of robustness has recently gained increased momentum owing to the applications of game theory to machine learning and data science, two fields where the notion of robustness has been likewise elusive. Here, even though many game-theoretic solutions perform extremely well on specific tasks ausks-such as well-trained generative adversarial network (GAN) equilibrium the resulting models tend to
For a masterful introduction to the topic, see textbook of van Damme [52].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

have a narrow performance envelope, being brittle, and unable to adapt to situations that deviate from their initial configuration.
In game-theoretic terms, this highlights the fact that, even though a Nash equilibrium is resilient to unilateral deviations, it need not be robust to small perturbations in the payoff data of the game (which, in a machine learning context, could represent distributional shifts, incomplete observations, and/or other sources of uncertainty). In view of this, is natural to ask
Which equilibria remain robust in the presence of strategic uncertainty?
This question has been the lodestar of the equilibrium refinement literature, and it has led to wide array of proposals aiming to get rid of "unreasonable" equilibria that may disappear even under the most minute perturbation to the players' payoffs- payoffs-from Selten's 's notion of trembling hand perfection [46]. to Myerson's 's concept of properness [38], and the various criteria of strategic stability introduced by Kohlberg & Mertens [28] (hyperstability, full stability, sequential stability, etc.).
Dually to the above theory of "strategic refinement", an important alternative approach has been based on dynamic considerations: that is, the players of game start offf-euullbrium, and in one sense or another learn (or fail to learn) to play an equilibrium over time. Here, the focus is on the players' learning protocol, the information available during play, and the presence (or absence) of players that may deviate from this protocol. By the so-called "folk theorem of evolutionary game theory" [23], it is well known that only strict equilibria are stable and attracting under the replicator dynamics, result which was extended more recently to a broad class of "regularized learning" schemes, in both continuous [17] and discrete time [18, 19, 36].
These two viewpoints are not always compatible: for instance, in x 2 games with two pure equilibria and one mixed (such the Chicken / Hawk-Dove game), the mixed equilibrium is ruled out by almost all game-theoretic learning algorithms and dynamics, even though it survives broad range of strategic refinement attacks. A point of hope here is the equivalence between (setwise) strategic and dynamic stability proved by Ritzberger Weibull [40], who showed that a span pure strategies in the mixed extension of a finite game is strategically stable in the sense of Kohlberg & Mertens [28] if
and only if it is asymptotically stable under the replicator dynamics see also [10. 13] for an extension to wider class of discrete- timee models for learning, with different information assumptions.
Notably, these considerations all concern finite games in normal (or extensive) form. By contrast, most applications of game theory to machine learning and data science involve continuous games, that is, games with finite number of players and a continuum of actions per player- forr example, GANs, multi-agent reinforcement learning, Kelly auctions, etc. In view of this, our paper seeks to answer the following questions the context of continuous games:
Which equilibria arise as robust predictions of the players' learning dynamics?
We refer to these two types of robustness as strategic and dynamic robustness, respectively. Our paper seeks to quantify the interplay between the two, and the implications that connect them.
Our contributions in the context of related work. Aiming for the strongest possible definition of robustness, we propose the following strategic refinement criterion:
An equilibrium of continuous game is strategically robust if it remains an equilibrium in any slightly perturbed, nearby game.
This requirement is similar in spirit tut considerably stronger than the classical notion of essentiality of Wu & Jiang [55], which posits that any nearby game has a nearby, possibly different cquilibrium. Importantly, our results apply to local Nash equilibria, which are especially relevant in machine learning applications where payoff landscapes crucial, as global Nash equilibria do not always exist in general continuous games, making local equilibrium guarantees both meaningful and necessary in practice.
typically nonconcave. This distinction
An important point here is that, contrast to finite games-whets where the notion of "nearby" fairly unambiguous- caabbiguuss-pertubbatioo to continuous game involve functional variations and, such, the metric that quantifies a "small" perturbation plays crucial role. Importantly, albeit natural, our proposed robustness requirement becomes vacuous if distances measured with respect to the

---

players' payoff functions: more precisely, it is always possible to find payoff perturbation with arbitrarily small -oom that ends up upsetting any equilibrium.
The underlying issue here is that a small payoff perturbation may exhibit very high local variability, which disrupt the first-order stationarity conditions that characterize equilibria in continuous games, thereby eliminating them altogether. To circumvent this issue, we argue that deviations of continuous games should be measured by comparing their respective gradient fields, which encode all the strategic information in the game. This shift in perspective leads to a crisp geometric characterization of strategically robust equilibria: they are extreme points of the game's 's action space, and they are sharp in the sense that the game's 's individual payoff gradients form a strictly acute angle with any tangent direction (cf. Fig. 1 later in the paper).
From a dynamic standpoint, we focus throughout on the family of algorithms known as "follow the regularized leader" (FTRL) [31, 47-49.. This is arguably one of the most-if not the most-popular class of policies for online learning due to its strong regret minimization and convergence guarantees, and it contains as special cases gradient descent/ascent methods [3, 58], dual averaging [39, 56], the exponential/ / multiplicative weights algorithm [2, 5, 5, 33, 54], implicitly normalized forecasters [1, 4, 57], exponentiated gradient methods [7. 27, 51], and many stochastic approximation schemes, adaptive [24, 25] and non-adaptive alike [26, 34-36].
In this general context, examine which equilibria admit robust convergence guarantees stable limit points of the dynamics of FTRL in the presence of randomness and uncertainty. Our first main result is that strategic robustness implies dynamic robustness, i.e., any strategically robust equilibrium is stable and attracting with high probability under the dynamics of FTRL, for any choice of regularizer. Conversely, we also show that the strategic robustness requirement cannot be lifted, and we provide an example of a game with an extreme, non-robust equilibrium which attracts all FTRL orbits under a certain choice of regularizer, and none under another.
To the best our knowledge, this is the first result of its kind for general continuous games. In the context of finite games, Flokas et al. [17] showed that a point is asymptotically stable under the continuous- time FTRL dynamics if and only if it is a strict Nash equilibrium, while [10] extended this equivalence discrete-tin time models of regularized learning under uncertainty. Striet equilibria are prime examples of strategically robust equilibria, so this part of the analysis of [10] is subsumed
in ours. In the context of concave games-thee is, continuous games with individually concave payoff Deattioss--etiioooouul & Zhou [34] showed that sharp global equilibria enjoy comparable convergence guarantees under FTRL with vanishing step-size. While such step-size schedules effective at suppressing noise in the long run, they do so at the cost of significantly slowing down the algorithm's 's convergence. By contrast, we focus on fast, constant step-size schedules, which are widely used in practice due to their simplicity and often superior empirical performance. In this regime, we show that entropically regularized learning with constant step-size converges to robust equilibria at a geometric rate, compared to distinctly subgeometric rates in the case of vamishing size policies Saaecies-subbumnngg this way a range of previous results for finite [19] and stochastic games [20].
2 Preliminaries
We start by briefly reviewing some basics of game theory and regularized learning, introducing the necessary context for our results.
2.1. The game-theoretic framework. Throughout our paper, we focus on a class of continuous games consisting of finite set of players i E N (I.....N, and defined by the following primitives:
1. Each player E A has access to a compact convex subset X; of some finite dimensional vector space Vj. describing the set of actions available to said player. By x of all ensembles
11; X; we denote the space .X) of actions x; E X; that are independently chosen by each player i E N. We will also write x = (x;:x_,) to emphasize the action of player i e A against the joint action profile x-; (xx) of all other players.
The players' rewards are determined by their individual payoff functions u;: X R, assumed to be continuously differentiable for all E A. Denoting by 3) = V, the dual space of V, we define
3

---

the individual gradient vector by: X - 3/ of player i E N by
(xx) = vx, (x;xxx)))
(I)
and the ensemble o(x) = (v) (x(x) E y [IEE Yi thereof.
................................
continuous game is then defined as a tuple 9 = C(N, X. u) with players, actions and payoff functions above.
Nash equilibrium. (NE), which characterizes the actions x E X' from which no player has incentive to unilaterally deviate. Formally, x² is Nash equilibrium if
The best known solution concept in game theory is that of Nash equilibrium
ui(x") 2 (xxxx()) for all X,
(NE)
A game G = G(N X. always admits a Nash equilibrium if X' is compact and each player's payoff function u, is individually concave in the sense that u (x)xxx_))) is concave in x; for all x-, X_ [14, 44]. In this case, basic arguments from convex analysis [42, 43] show that x is an equilibrium of 9 if and only if it satisfies the (Stampacchia) variational inequality
s 0 for all x E X.
(VI)
If the players' functions are not individually concave, a game may not admit a Nash equilibrium. In that case, it is more meaningful to consider local Nash equilibria, i.c., profiles x² E X such that
uy (xxx)= 2 ux(xxxx), for all x in neighborhood U of x" in X..
(LNE)
In stark contrast to games with individually concave payoff functions, (VT) no longer characterizes local Nash equilibria: specifically, by first-order stationarity, we have (LNH) = (VI) but the converse need not hold; in fact, a solution x² of (VI) may be global payoff maximizer for all i e N. Note. In the sequel, we will work with general continuous games that may not admit a global bquilibrium-but admit local Nash equilibria. To streamline our presentation, we will use the term "equilibrium" without any further qualification to refer to local equilibria, and we will say explicitly "global equilibria" for profiles satisfying (NE).
2.2. Regularized learning in games. The most widely used framework for learning in games, is the so called "follow the regularized leader" (FTRL) template, primarily because it leads to no regret in a wide variety of settings [48, 49]. The corresponding update rule hinges the notion of regularized best response, and proceeds as
yi+1 = y + y0,
X, Q(y))
for r 1,2,...
(FTRL)
where (i) X E X denotes the players' action profile at step r; (ii) yr (yI.)) E 3 is auxiliary process that aggregates historical feedhack into a compact state representation, i.e., a proxy for the players' empirical performance up to time r; (iii é, (Bir) 3' denotes the current gradient-like payoff signal; (iv) > is the learning rate, or step-size parameter of the process; and (v) Q: y - X is mapping between the auxiliary process the dual space Yi and the players' strategy space X. In what follows, we analyze the key components of this framework.
The algorithm's 's step-size. Throughout this work, we adopt a conslant step-size routine. This stands in contrast to the stochastic approximation literature [8, 11, 29], where (FTRL) is typically implemented with a vanishing step-size satisfying the Cobbins-Monro summability conditions E, Y; = 00, Σr x < oo [41], which is known to promote convergence by gradually suppressing the effect of noise [34].
On the other hand, in practical applications, it is common to employ a constant (or non-diminishing) step-size for several reasons. First, constant step-sizes are easier to tune and maintain, making them more suitable for large-scale or production environments. Moreover, methods with vanishing step-sizes often experience long warm-up phases and converge slowly to neighborhood of the equilibrium. comparison, constant step-size methods in machine learning settings typically reach the vicinity of solution much faster-often within 0.1 accuracy [16]. Indeed, many state-of-the-art architectures, including transformers and large language models, use step-size schedules that remain effectively constant over billions even trillions of samples [15].

---

The mirror map. A central ingredient of regularized learning is the mirror map Q = (Qi) with each 2;: 3/ - X2 induced by a strongly convex regularizer h;: X; R that promotes stability during the learning process. To streamline our presentation and letting h(x) = EieN hx(x;), the players' mirror map defined as
Q = arg maxxex (x, h(x))
(2)
In the rest of our paper, we will write X₁, = im Q for the image of y under Q-and, likewise, we Xn, = im Qi for each player W. In particular, if Q is interior-valued that is, X, X-wwe will say that ht is steep because, in this case, the (sub)gradients of h explode to infinity as x - bd (i.e., h becomes "infinitely steep"); instead, im Q X, we will say that h is non-steep. For detailed discussion on this distinction and related concepts, see Appendix A.
Different choices of the regularizer h induce different projection-like operations, adapted to the geometry of the underlying space. We describe two mainstay examples below.
Example 2.1 (Euclidean projection). The quadratic regularizer h(x) = ||x|1//2 gives rise to the Euclidean projection (yy) proj.x (y) = arg min - xl12. In this case, h is non-steep.
Example 2.2 (Exponential weights). For A, a finite set of actions per player i N. and X; = A(A)). the entropic regularizer (x;) A Xia; log,
Xia; gives rise the logit map, defined via Qi(y)) exp(ur)//lexp((t))) where exp(yi) denotes the element-wise exponential of y/-
The feedback process. Throughout this work, we consider two distinct feedback models: (i) stochastic gradients; and (ii) payoff-bused feedback. We describe both frameworks below.
Stochastic gradient feedback. first-order oracle (SFO) that is, noisy version of their individual gradient vector of the form:
At every time step 1, each player i E N has access to a stochastic
i = o(x,) U, with BiU, [J] =
(SFO)
where U, is zero-mean and conditionally sub- Gabssin given the information F, generated up to time I E N. In other words, players observe unbiased estimates of their individual gradient vectors.
Payoff-based feedback. Unlike the (SFO) model where players have access to black-box oracle that provides noisy gradient information, it often more realistic to consider a payoff-based paradigm where players observe only their realized payoffs- that is, a single scalar value and have to reconstruct an estimate of their individual gradient vectors.
The most widely used method in this setting is the single-point stochustic approximation (SPSA) framework of [12, 50], which based on finite differences along randomly sampled directions. Specifically, denoting the set of unit directions & =(= ) that span the affine hull of X; of dimension d,, each player i E N draws a direction Wy, E & uniformly at random in every round t N. Since the perturbed action x1,, W, may lie outside X, for a perturbation radius E, > O, we introduce a pivot element pj E ri(X)) and a radius ri > & such that pi + +ri X for all wy &, Based on these, we define the feasibility-adjuste action x Xi, + (E//r)) xx,,) e X. Finally, each player queries the perturbed action Łi, = xf, + SyWi,r which is an element of X; and observes the realized payoff value (&,). The gradient vector is, then, estimated via the single-point stochastic approximation scheme:
,1, (d./EEE u, wi.r
(SPSA)
Importantly, the feasibility adjustment ensures that the perturbed action 2, remains within the players' action set X, while preserving the direction of the original perturbation Wy. As we show in Appendix A, (SPSA) enjoys the bounds
[[E [i] - v(x,)) = O(e,) and ||0,1l 0(1/s,)
(3)
These statistical properties of (SPSA) will play a crucial role in establishing its convergence guaran- tees; we will revisit them in Section 4.
Since r; > EG, write xf, = (1 /rir) + (e//r))p: which is a convex combination of points in X; Regarding Rt,,, note it can be written as & x1, - e//r)) (p/ + +rw,))). which is also convex combination of points in X2. Thus, both belong to X2.
5

---

3 Strategic robustness: Geometric and variational characterization
We begin in this section by addressing the strategic aspects of the equilibrium robustness question, namely:
Which equilibria remain invariant under small but otherwise arbitrary perturbations of the game?
We take this desideratum the starting point for our definition of strategic robustness, that is, action profiles that remain (local) equilibria under small disturbances in the underlying game. This leads to delicate interplay between the variational and geometric aspects of the underlying game, which detail below.
3.1. A first approach and insights. The first step in our analysis is to quantify the meaning of "small". In this regard, a natural way to measure the distance between two concave games, G = X,) and 9 G(N X. ū)) would be via the uniform distance
(4) Intuitively, if this quantity is small enough, the two games are nearly indistinguishable from a strategic perspective, since for every strategy profile E X, the payoffss in G and & are almost the same. Thus, one might expect that at least some equilibria of G should persist under sufficiently small perturbations, especially given that a Nash equilibrium is defined in terms of the game's payoff functions themselves.
p(g. = maxieN suprexl(:(x)) - (x(x)
Perhaps surprisingly, as we show below, this definition of distance cannot provide a meaningful concept of equilibrium robustness.
Proposition 1. For any game G and any equilibrium x² E X of G, there exists a perturbed game G. arbitrarily close to G in the uniform metric (4) such that x" X is not equilibrium of 9.
To show this, we provide Examples 3.1 and 3.2 which, taken together, cover all possible types of equilibria in continuous games in the sense of (VI).
Example 3.1. Let G be continuous game, and let x* X' be equilibrium of g such that (v,(x"). P: x 0 for some player E N and pl E Ng. For arbitrary & > define ūj : X - R as
=x;
exp(2 (0:("))xx))))))))))))))"")))))
xi))
(5)
which is a continuously differentiable concave function in x,, and let új u for all j # i E W. Since x² E X' is an equilibrium of G, it holds (x"),,, - xf) s 0 for all x E N, which implies that
r(G. 9)
supxe x Il, (x) - (x)x e x exp(2 E (x,)x)),, x, - -x7)) =..
Computing the individual gradient vector of player i N,, we obtain
(x) ez (x) - (x' exp (1,(x")
(x),,,, ), -xx)
and, evaluating it at E X. we get, =,xx')=,;;,+ Therefore, for x = (prix",) E X, we have ((x')x--')== = -(;(x'
x;) 0
(8)
i..,, x² E X is not an equilibrium point of the perturbed game g.
Example 3.2. Let 9 be continuous game, and let x" X' be equilibrium of g such that
(u(x"),x - x²) = 0 for all x E X. Fix a player i E N and p; E X, and let y E V with let a; X R be defined
(yi, Pi x7) O. For arbitrary
(x) = u: (x) + & diam (2) (2) |I. xg
(9)
which is concave function in x,, and ū, ,, for all j # i. E M. Then, readily get that
( sup (x)) e diam X2) - ||_ xx Ky., - x;31
(10)
Computing the individual gradient vector of player i E N, we obtain
(x) = by (x) + diam xx) 11 y
(11)
Therefore, for x= (pxx") X, it holds by the example's 's assumptions that
(i(x'),x x²) = (1, ). x;) e diam X2) |l. II. (y) Pt xx/) > where we used that
(12)
= and (y:- Pi x,) > 0, as per our original assumptions. Thus, x" E X' is not an equilibrium of the perturbed game G.

---

p(x*)
o(x')
NC(x))
NC(x*)
NC(x))
X
X
X
o(x*)
Figure 1: Different equilibrium configurations: interior equilibrium (o(x²) 0); boundary, non-extreme equilibrium (normal cone with empty topological interior); an extreme, non-robust equilibrium (o(x*) the boundary the normal cone); robust equilibrium (o(x") in the interior of normal cone). Only robust equilibrium remains invariant under strategic perturbations the underlying game.
Remark 1. In Examples 3.1 and 3.2, if G is concave, so is G, indicating that this notion of distance is not proper even within the class of concave games.
The preceding examples demonstrate that under the distance (4), even an arbitrarily small perturbation to the payoff function of a single player can destroy any equilibrium. 3 This phenomenon arises because, although an equilibrium defined in terms of payoff functions, the first-order stationarity condition in (VI) shows that it fundamentally depends on the individual gradient vectors. Therefore, any meaningful notion distance between two games must likewise be aware the behavior of the individual gradient vectors.
3.2. Defining strategic robustness. As illustrated in Examples 1.1 and 3.2, small changes in the payoff's, though negligible in the uniform norm, can alter the equilibrium landscape quite significantly, To address this, we refine the notion of distance between games G and & as follows:
dist (g. 9 supxex [|o(x) 0(xx)l
(13)
With this definition in hand, we are now ready to state the concept strategic robustness the class of continuous games.
Definition 1. An equilibrium x² E X' of a game G is called strategically robust if there exists & > such that for any game & with dist(g. 9) E, x also an equilibrium of G.
As we explore next, this definition offers meaningful notion of "closeness" for equilibrium stability, one that grounded not in the payoff values themselves, but in the geometry they induce.
Geometric characterization. To provide a geometric characterization, we zoom in on the varia- tional structure that governs Nash equilibria. Specifically, we show that strategically robust equilibria E X' are precisely those solutions of (VI) for which the inequality is strict for all feasible deviations. Formally, we have the following characterization:
Theorem 1. Let x" E be a joint action profile in 9(N,X,u) Then the following are equivalent:
( x² is a strategically robust equilibrium.
(i) (u(x*),z) 5 =mmllzl for some m > 0 and all E TC(x"), where TC(x") is the closure of all rays emanating from x² and intersecting in at least one other point.
(iii) u(x") E inC()))))),, where PC(x*)=(je y: (y.2) & 0, for all z TC(x")).
Intuitively, Theorem suggests that strategically robust equilibria precisely those points xx X where the associated gradient vector u(x") lies in the topological interior of the polar cone PC(x"), ie.,
(14) We thus conclude that strategic robustness can only occur at boundary points where the tangent cone is pointed; if the feasible set is locally flat xt E X. the corresponding polar cone has empty
(u(x") ). 2) < 0 for all 2 E TC(x").
SSuch variations are not possible in the class of finite games, so, in this much more restrictive class, the sup-norm of the payoff' differences is valid metric measure robustness.
7

---

interior, and robustness is not possible. This phenomenon is illustrated in Fig. 1, and the full proof of Theorem is provided in Appendix B.
Remark 2. Both Examples 3.1 and 3.2 violate the condition in Definition 1, but for different reasons. In the former case, although the perturbed payoft's can be made arbitrarily close to the original, the perturbed gradient vector equilibrium can become arbitrarily large, making the distance dist 9) exceed any > 0. In the latter case, the polar cone PC(x") at the equilibrium has empty interior, so strategic robustness cannot hold atx".
Remark 3. Several important classes of games admit robust equilibria for all but measure-zero set of instances. Examples include nonatomic, non-splittable routing games with arbitrary increasing cost functions [45], Markov potential games arising in multi-agent reinforcement learning [32], Cournot oligopolies in which firms have no or limited price-setting power [37], etc.
In the next section, we examine the dynamic implications of this result by studying the robustness of such equilibria under (FTRL).
4 From strategic to dynamic robustness: Convergence results
So far, we focused on strategic robustness, a static notion determined solely by the underlying game and the local geometry around the equilibrium in question. In this section, we shift to the dynamic perspective of our central question and explore which equilibria admit robust convergence guarantees, namely, equilibria that can emerge as stable outcomes of regularized learning under feedback and initialization uncertainty, regardless of the specific choice of regularizer.
To this end, we first establish that non-equilibrium points cannot arise as limits of (FTRL), even with perfect gradient feedback. Formally, we have the following proposition, whose proof is provided in Appendix C.
Proposition 2. Suppose that (FTRL) is run with perfect gradient feedback of the form 8, v(x,) for all I = 1,2. and assume that x, converges to some 2 E X. Then & is an equilibrium of g.
Having excluded non-equilibrium points as positive probability outcomes of learning process, we now turn identifying equilibria that robust from dynamic standpoint, and more precisely, under that of (FTRL). In this regard, strategically robust equilibria serve as natural candidates, as their stability with respect game perturbations suggests they may also admit robust convergence guarantees. This is further supported by the finding that equilibrium points in the interior of the strategy space X' cannot be limit points: in particular, we show below that, even under i.idd stochastic noise, the iterates of (FTRL) diverge from such equilibria almost surely.
Proposition 3. Xetx" E ri(X)) be Nash equilibrium of GNN, X, u), and (x,)Te be the sequence of play induced by (FTRL) with 0, = v(x,) + Uy. where U, i..dd with E(U,] 0 and cov(U,) > 0 foor all I N. Then:
P lim X, =x)==0 =0
for any X1 Xn.
(15)
1-000
Remark 4. The condition cov(U,) > is not necessary. In fact, it suffices to have cov(U,) non- degenerate in direction p p-x' for X, but we state our result under stronger assumptions for simplicity.
The key idea of the proof, which is deferred to Appendix C, is that, since x" E ri(X', have (u(x"),x xx)) = 0 for all x E X. At the same time, as cov(U,) > O, the quantity (U,x- x x") fluctuates and remains bounded away from zero infinitely often, thereby preventing convergence.
4.1. Learning with gradient- feedback. In view of the impossibility result of Proposition 3. we shift our focus on the convergence of (FTRL) toward strategically robust equilibria. We first consider the gradient feedback model, where each player receives an unbiased estimate of their individual gradient vector via (SFO). Specifically, we analyze the behavior of (FTRL) and we establish local convergence guarantees toward strategically robust equilibria with high probability. This is encoded the following theorem:
Theorem 2. Let x" E X be a strategically robust equilibrium of G(N, N.).. Fix a confidence level 5 0, and let (Xt)ee be the iterates of (FTRL) with feedback provided by (SFO), and step-size > 0 sufficiently small. Then, there exists a neighborhood U of x² in Xn such that:
P lim X, = x²) 2 1 if Ed.
(16)
8

---

Before proceeding, a few remarks are in order. Since continuous games may admit multiple Nash equilibria, global convergence guarantees are in general unattainable. As such, our analysis focuses on the local convergence landscape of (FTRL). As sidenote, it is important to emphasize that the convergence result is robust to the choice of regularizer, relying solely on the general conditions outlined in Section 2 rather than any particular functional form. We outline below the main steps of the proof, with full details provided in Appendix C.
Proof Sketch. The key idea is that the auxiliary process yt, which aggregates the players' gradient updates, diverges to infinity in a direction that steers the induced sequence X, = Q(y,) toward the equilibrium in question. More formally, the proof relies on the following intuition. From Theorem I and the continuity of the players' payoffs, strategic robustness implies that. in a neighborhood of a robust equilibrium x", the players' individual gradient fields point toward x². Consequently, the process yt accumulates gradient steps that, on average, are aligned with the interior of the normal cone NC(x") to the action space X' at xx. As result, y/ exhibits a consistent drift that carries it deeper into a "copy" of the normal cone NC(x*) embedded in the gradient space y. Moreover, we show that, with high probability, once Y/ enters this region, it remains there, provided that the algorithm is not initialized too far from x". Combining the above, Proposition C.1 establishes that the sequence of actions = Qv) generated by (FTRL) converges to x"
While our main focus lies on the qualitative convergence behavior of (FTRL), stronger guarantees can be obtained under additional structural assumptions on the strategy space and the regularizer. In particular, suppose that X' is a polyhedral domain of the form X' =x R Ax = b) for some A E Rd and R"", and h is decomposable with kernel function 0, i.e., h can be written as h(x)= دز O(xy) for some continuous function 0 R+ - IR with locally Lipschitz 0" and 0" O. Under these conditions, we obtain the explicit convergence rates for the (FTRL) dynamics, as follows. Theorem 3. If. in addition, X is polyhedral domain and h is decomposable with kernel I, on the event E (limm X, = >x"} it holds:
1|x 11=x''==0(-000)
(17)
where o is the rate function defined via
(z)
is > (0+) iʃ S (0+)
+ 2
(18)
Remark 5. For the setting of Example 2.2, with X' = A(A), O(z) = z =log z and x" a strict Nash equilibrium, the convergence rate of (FTRL) as per Theorem 3, becomes ||xx, - x-11 exp(-O(r)) Remark 6. For finite games, [19] showed that under step-size schedule of the form y, 1/1P, the Robins-Monro summability conditions require p E (1/2, 1], leading to convergence rates from ((-(((1-P)) to ((-O(log()). Our convergence guarantees remain valid under these step-size schedules, though they yield the slower aforementioned rates.
Remark 7. It is important to highlight the different behavior of (FTRL), often referred to as a "lazy" variant of mirror descent [22], with that of the mirror descent algorithm, defined via the update
Xx+1 (xv((x)) yo,) for / = 1,2,...
(MD)
where Vh(x) denotes continuous selection of âh(x) [12]. To illustrate the difference, consider the single-agent problem of maximizing u(x) = x over X = [0. I], where x' = I is a robust equilibrium. Using the Euclidean regularizer (see Example 2.1), (MD) reduces to the projected gradient algorithm
xy+1 [xx + y0²)
(SGA)
where 0, is stochastic gradient of at x,, i.c.. 0, = 1 U, where Un is a Bernoulli process with U, = +1 with probability 1/2. However, even if x, x for some r, we then have that X,+1 1 with probability 1/2. Thus, by a straightforward application of the Borel-Cantelli lemma, we conclude that, with probability 1, (SGA) does not converge to x". Through this toy example, note that although (MD) and (FTRL) use the same mirror map Q to select actions, they differ fundamentally in how feedback is processed. The "eager" nature of (MD) makes it more sensitive to noise, whereas (FTRL) maintains a cumulative dual variable y, that aggregates all past feedback, effectively smoothing out fluctuations over time. Also, note that for steep regularizers, the iterations (MD) and (FTRL) coincide, as the mirror map Q is essentially injective (see Appendix A for more details). Therefore, differences in their behavior arisc in the case where steepness does not hold.

---

4.2. Learning with payoff-based feedback. We now turn to the payoff-based feedback model, where players observe only their realized payoffs and use them to estimate gradients indirectly via (SPSA). This feedback model introduces higher variance and structural bias due to the diminishing sampling radius and the feasibility corrections. Nevertheless, we show that strategically robust equilibria retain their dynamic robustness: they still locally attract the (FTRL) dynamics with high probability, as the following theorem suggests.
Theorem 4. Let x* & X be strategically robust equilibrium of G. Fix confidence level 5 > O. and let (xx EeN be the iterates of (FTRL) run with (SPSA) with E, oc 1/1P for some p E (0, 1/2) and step-size y > O sufficiently small. Then, there exists a neighborhood U of x such that:
P lim X2 =xx) 1-8
if Eld.
(19)
If. in addition, X is affinely constrained and h is decomposable with kernel then, whenever X converges to x", we have:
- = ((-0(1))
(20)
Despite the scarcity of information inherent in the payoff-based feedback model, strategically robust equilibria retain not only their convergence properties but also their convergence speed, under the additional structural assumptions on the regularizer and domain, matching that of the (SFO) feedback setting. This is further discussed along with the proof of the theorem in Appendix C.
4.3. Convergence landscape beyond strategic robustness. Having established the robust conver- gence properties of strategically robust equilibria, natural question arises: Can expect robust convergence guarantees toward equilibria that lack this structural property? As we show below, the answer is not encouraging: strategic robustness is essentially necessary for robust convergence.
To make this limitation precise, we move beyond the interior of the strategy space, where Proposition rules out equilibria as potential limit points, and shift our focus to non-robust equilibria the boundary. To illustrate the behavior of (FTRL) in this setting, we construct a game with a unique equilibrium that exhibits fundamentally different long-run behavior depending the regularizer.
Proposition 4. Consider the 1-player game G with X = [0. 1]. u(x) x and x* = O. Let (xt)NN be the iterates of (FTRL) with y < and i, v(x,) + U, where U, are i..d. standard normal random variables for all I E N. Then, for any initial condition y1 e R, we have:
(i) For h(x) x x, it holds P(lim X, xx" 0.
(ii) For h(x) = -2/x, it holds P(lim; X, =x) 1.
The core idea of the proof of Proposition 4 (which we present in detail in Appendix C) is to construct process 2, that dominates yn- Importantly, the process 2, can be then viewed random walk with a diminishing drift whose rate of decay depends on the choice of regularizer. Depending on the magnitude of this drift, the process exhibits two sharply contrasting long-term behaviors: if the drift decays sufficiently fast, the process behaves like a zero-mean random walk and returns infinitely often with probability (recurrence); conversely, if the drift diminishes at a slower rate, the process behaves like random walk with constant drift and escapes to infinity with probability (transience).
In view of the above, we conclude that strategic robustness cannot be relaxed without compromising convergence guarantees, even when the equilibrium lies on the boundary of the game's action space.
Concluding remarks
Our aim in this paper was to examine the robustness of Nash equilibria in continuous games, under both strategic and dynamic uncertainty. From a strategic standpoint, the notion of strategic robustness characterizes those (local) equilibria which remain invariant under small perturbations of the underlying game, and we derived tight geometric characterization thereof in terms of the variational geometry of the game. From dynamic standpoint, we focused on the stability of regularized learning under umcertainty, and we established a deep structural connection between the two notions. Strategic robustness guarantees dynamic robustness under (FTRL), and this implication is essentially tight: without strategic robustness, dynamic robustness cannot be ensured. To the best of our knowledge, this is the first study of its kind for continuous games, and we believe that this two-way implication clucidates the delicate interplay between static and dynamic considerations.
10

---

Acknowledgments and Disclosure of Funding
Jose Blanchet gratefully acknowledges support from the Department of Defense through the Air Force Office of Scientific Research (Award FA9550-20-1-0099) and the Office of Naval Research (Grant 1398311), 1), as well as from the National Science Foundation (Grants 2229012, 2312204, and 2403007). Panayotis Mertikopoulos also a member of Archimedes/Athenna RC and acknowledges financial support by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PEIA (XX23--PEIA-0003) 0003), the project IRGA-SPICE (G7H-IRG24F90) and project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0, funded by the European Union under the NextGenerationEUU Program.
References
[1] Abernethy, J., Lee, C., and Tewari, A. Fighting bandits with a new kind of smoothness. In NIPS' '15: Proceedings of the 29th International Conference on Neural Information Processing Systems, 2015.
[2] Arora, S., Hazan, E.,, and Kale, S. The multiplicative weights update method: A meta-algorithm and applications. Theory of Compuring, 8(1):121-144, 2012.
[3] Arrow, K. J., Hurwicz, L.., and Uzawa, Studies linear and non-linear programming. Stanford University Press, 1958.
[4] Audibert, J.-Y., Bubeck, S., and Lugosi, G. Minimax policies for combinatorial prediction games. In COLT 11: Proceedings of the 24th Annual Conference on Learning Theory, 2011.
[5] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995.
[6] Azizian, W., lutzeler, F. Malick, and Mertikopoulos. P. On the rate of convergence of Bregman proximal methods constrained variational inequalities. http://arxis .r org/abs/22111 08843, 2022.
[7] Beck, A. and Teboulle, M. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 11(3):6771155 2003.
[8] Benaim, M. Dynamics of stochastic approximation algorithms. Azéma, J., Émery, M., Ledoux, M., and Yor, M. (eds.). Séminaire de Prububilité' XXXIII, volume 1709 of Lecture Notes in Mathematics, pp. 1-68. Springer Berlin Heidelberg, 1999.
[9] Billingsley, P. Probability and measure. A Wiley- Willy-Innerscienne publication. Wiley, 3. ed edition, 1995.
ISBN 0471007102.
[10] Boone, V. and Mertikopoulos, P. The equivalence of dynamic and strategic stability under regularized lcarning in games. In NeurlPS 23: Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023.
[11] Borkar, S. Stochastic Appreximation: A Dynamical Systems Viewpoins. Cambridge University Press and Hindustan Book Agency, 2008
[12] Bravo, M., Leslic, D. S., and Mertikopoulos, P. Bandit learning in concave N- N-person games. In NeurlPS 18: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2018. [13] Cauvin, P.-L.., Legacci, D., and Mertikopoulos, P. The impact of uncertainty regularized learning in games. In /CMI. 255 Proceedings of the 42nd International Conference on Machine Learning, 2025.
[14] Debreu, G. A social equilibrium existence theorem. Proceedings of the National Academy of Sciences of the USA, October 1952.
[15] DeepSeek-AI, Liu, A., Feng, B., Xue, B., Wang, B., Wu, B., Lu, C., Zhao, C., Deng. C., Zhang. C.,, Ruan,
C.. Dai, D.. Guo, D.,, Yang. D.,, Chen, D., Ji, D., Li, E., Lin. F., Dai. F., Luo, F., Hao. G., Chen, G., Li, G., Zhang, H. Bao. H., Xu, H., Wang, H., Zhang, H., Ding, H., Xin, H., Gao, H., Li, H., Qu, H., Cai, J. L., Liang. J.. Guo, J., Ni, J., Li, J., Wang, J., Chen, J.. Chen, Yuan, J., Qiu. J., J.. Song, J., Dong, K., Hu, K., Gao, K., Guan, K., Huang, K., Yu, K., Wang. L., Zhang, L., Xu, L., Xia, L., Zhao, L., Wang. L., Zhang, L., M., Wang. M., Zhang, M., Zhang, M., Tang, M., Li, M., Tian, N., Huang, P., Wang P., Zhang, P., Wang, Q., Zhu, Q., Chen, Q., Du, Q., Chen, R. J., Jin, R. L., Ge, R., Zhang, R., Pam, R., Wang. R. Xu, R., Zhang, R., Chen, R., Li, S. S., Lu, S., Zhou, S., Chen, S., Wu, S., Ye, S., Ye, S., Ma, S., Wang. S., Zhou, S., Yu, S., Zhou, S., Pan, S., Wang. T., Yun, T., Pei, T., Sun, T., Xiao, W. L., Zeng. W., Zhao W. An, W., Liu, W., Liang, W. Gao, W. Yu, W., Zhang, W., Li, X. Q., Jin, X., Wang. X., Bi, X., Liu, X., Wang, X., Shen, X., Chen, X., Zhang, X., Chen, X., Nie, X., Sun, X., Wang. X., Cheng. X., Liu, X., Xie, X., Liu, X., Yu, X., Song. X., Shan, X., Zhou, X., Yang. X., Li, X., Su. X., Lin, X., Li, Y. K., Wang. Y. Q. Wei, Y. X..
Zha, Y. X., Zhang, Y., Xu, Y. Xu, Y., Huang, Y., Li, Y., Zhao. Y. Sun. Y. Li, Y. Wang. Y. Yu, Y., Zheng.
Y., Zhang, Y., Shi, Y., Xiong, Y. He, Y., Tang, Y., Piao, Y.. Wang. Y., Tan, Y., Ma, Y. Liu, Y., Guo. Y..
11

---

Wu, Y. Ou, Y., Zhu, Y. Wang. Y. Gong, Y.. Zou, Y., He, Y., Zha. Y., Xiong, Y. Ma, Y., Yan. Y., Luo, Y..
You, Y.. Liu, Y. Zhou, Y. Wu, Z. F., Ren, Z. Z., Ren, Z.. Sha, Z.., Fu, Z.., Xu, Z.., Huang, Z., Zhang, Z.. Xie, Z., Zhang, Z., Hao, Z., Gou, Z., Ma, Z... Yan, Z., Shao, Z., Xu, Z., Wu. Z., Zhang, Z., Li, Z., Gu. Z..
Zhu, Z., Liu, Z., Li, Z., Xie, Z., Song, Z., Gao, Z., and Pan, Z. Deepseek-v3 technical report, 2025. URL https://arxiv. hwt..orrgabb//212..2 19437.
[16] Dieuleveut, A., Durmus, A., and Bach, F. Bridging the gap between constant step size stochastic gradient descent and markov chains. The Annals Statistics, 2017. URL https::/app..smmaticcset semanticschollar org/CorppsID:440555
[17] Flokas, I.., Vlatakis- Vlatakis-Gkaragken Gkaragkounis, E. V., Lianeas, T., Mertikopoulos, P., and Piliouras, G. No-regret learning and mixed Nash equilibria: They do not mix. NeurlPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[18] Giannou, A., Vlatakis- SaaakkiiGGGargkouuiii.. E. V., and Mertikopoulos, P. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In COLT '21 Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[19] Giannou, A., Vlatakis- Vlatakis-Gkaragker GearGakkunniii E. V., and Mertikopoulos, P. The convergence rate of regularized lcarning in games: From bandits and uncertainty to optimism and beyond. In NeurlPS '2/: Proceedings of the 35th Internutional Conference Neural Information Processing Systems, 2021.
[20] Giannou, A., Lotidis, K., Mertikopoulos, P., and Vlatakis- Gkaragkounis, E. V. On the convergence of policy gradient methods to Nash equilibria in general stochastic games. In NeurlPS '22: Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
[21] Hall, P. and Heyde, C. C. Martingale Limit Theory and Its Application. Probability and Mathematical Statistics. Academic Press, New York, 1980.
[22] Hazan, E. Introduction to online convex optimization. CoRR, abs/1909.05207, 2019. URL http:
/arxiiv. wwwaaii.org/aaaeeeeeeeeeeoooeeee
oroooog////// hrrg/bbs/1999 05207.
[23] Hofbauer, and Sigmund, K. Evolutionary game dynamics. Bulletin of the American Mathematical Society, 40(4), July 2003.
[24] Hsich, Y.G., Antonakopoulos, K., and Mertikopoulos, P. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In COLT '21: Proceedings of the 34th Annual
Conference on Learning Theory, 2021.
[25] Hsieh, Y.-G., Antonakopoulos, K., Cevher, V., and Mertikopoulos, P. No-regret learning in games with noisy feodback: Faster rates and adaptivity via learning rate separation. In NeurlPS '22: Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
[26] Hsieh, Y.-P., Mertikopoulos, P., and Cevher, V. The limits of min- max optimization algorithmss Conver- gence to spurious non coi-cciiical sets. In ICML '1:: Proceedings of the 38th International Conference on Machine Learning. 2021.
[27] Kivinen, J. and Warmuth, M. K. Exponentiated gradient versus gradient descent for linear predictors. Information and Computation, 132(1):1-63, 1997.
[28] Kohlberg, E. and Mertens, J.-F. On the strategic stability of equilibria. Econometrica, 550 September 1986.
[29] Kushner, H. J. and Clark, D. S. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer, 1978.
[30] Lamperti, Criteria for the recurrence transience of stochastic process. i. Journal Mathematical Anal- yais and Applications, 1(3)314-330, 1960. ISSN 0022-247X. doi:
90005-6. URL https: //wp:. sciencedeeee rect. com/ http://cennc//rrceeee wtt.c//iien//aaaiiee/eeeeeee///e att.cc///pp//100222140095555555
[31] Lattimore. T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, Cambridge, UK, 2020.
[32] Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. Global convergence of multi-agent policy gradient in Markov potential games. In ICLR '22: Proceedings of the 2022 International Conference on Learning Representations, 2022.
[33] Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. Information and Computation, 108 (2):212-261) 1994,
[34] Mertikopoulos. P. and Zhou, Z. Learning in games with continuous action sets and unknown payoff' functions. Mathematical Programming. 173(1-2):465-33 10-4655-77.00 January 2019.
[35] Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chandrasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR '19 Proceedings of the 2019 International Conference on Learning Representations, 2019.
[36] Mertikopoulos, P., Hsich, Y.-P., and Cevher, V. A unified stochastic approximation framework for lcarning in games. Math. Program., 203( (0:55))):559- (009,960,,6600 August 2023. ISSN 0025-5610, doi: 10. 1001/ $10107-023-02001-y URL htttps:///oi org/10.
[37] Monderer, D. and Shapley. L. S. Potential games. Games and Economic Behavior, 14(1):124 143, 1996.
12

---

[38] Myerson, R. B. Refinements of the Nash equilibrium concept. International Journal of Game Theory, 7
(2):73-80, 1978.
[39]
Nesterov, Primal-dual subgradient methods convex problems. Mathematical Programming, 120(1):
221-259. 2009.
[40]
Ritzberger, K. and Weibull, J. W. Evolutionary selection in normal-form games. Econometrica, 63(6):
1371-99, November 1995.
[41] Robbins, H. and Monro, A stochastic approximation method. Annals of Mathematical Statistics, 22:
400-407, 1951.
[42] Rockafellar, R. T. Convex Analysis. Princeton University Press, Princeton, NJ, 1970.
[43] Rockafellar, R. T. and Wets, R. J. B. Variational Analysis, volume 317 of A Series of Comprehensive Peringer-Verlagg Berlin, 1998.
Studies in Mathematics.
[44] Rosen, B. Existence and uniqueness of equilibrium points for concave N-person games. Econometrica, 33(3):520-534, 1965.
[45] Rosenthal, R. W. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65-67, 1973.
[46] Selten, R. Re-examination of the perfectness concept for equilibrium points in extensive games. Interna- tional Journal of Game Theory, 4:25-55, 1975.
[47] Shalev-Shwartz, Online learning: Theory, algorithms, and applications. PhD thesis, Hebrew University of Jerusalem, 2007.
[48]
S. Online learning and online convex optimization. Foundations and Trends in Machine
Learning, 4(2), 2011.
[49] Shalev-Shwarzz, and Singer, Convex repeated games and Fenchel duality. In NIPS 06: Proceedings of the 19th Annual Conference on Neural Information Processing Systems. MIT Press, 2006.
[50] Spall. J. C. Multivariate stochastic approximation using simultaneous perturbation gradient approximation. IEEE Trans. Autom. Control, 57(3):332-344 March 1992.
[51] Tsuda, K., Rätsch, G., and Warmuth, M. K. Matrix exponentiated gradient updates for on-line Bregman projection. Journal of Machine Learning Research, [52] van Damme, F. Stability and perfection of Nash equilibria. Springer-Verlag, Verlag, Berlin, 1987.
2005.
[53] von Neumann, J. and Morgenstern, O. Theory of Games and Economic Behavior. Princeton University Press, 1944.
[54] Vovk, V. G. Aggregating strategies. In COLT '90: Proceedings of the 3rd Workshop Computational Learning Theory, pp. 371-383, 1990.
[55] Wu, W.-T. and Jiang. J.H. Essential equilibrium points N-person non-cooperative games. Scientia Sinica, 11 11(10):1077-132, 1962.
[56] Xiao, L. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543-2596, October 2010.
[57] Zimmert, J. and Seldin, Y. Tsallis-INF: An optimal algorithm for stochastic adversarial bandits. Journal of Machine Learning Research, 22(28): 2021.
[58] Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In ICML '03: P Proceedings of the 20th International Conference Machine Learning, pp. 928-936, 2003.
A Auxiliary results
As preamble to our analysis, we provide some basic properties of the regularizers and the mirror maps. and present some auxiliary results from martingale theory and Markov processes that will use throughout the sequel.
A.I. Mirror maps and results from convex analysis. this section, we provide a more detailed discussion of key notions from convex analysis, including mirror maps and regularizers.
To begin, let (V, II-II) be knite-dimensions normed vector space. Its dual space denoted by (V*, II:ll.), where the dual norm is defined as
|lll- = myx : |||||| < 1),
(A.1)
and (y.x) denotes the canonical pairing between y E 1/" and x E V. maintain consistency with the notation used throughout the paper, will refer to V as y from this point onward.
13

---

Given closed convex set X' S V and point E A, we define the tangent cone TC(p) and the polar cone PC(p) as follows:
TC(p) c e V: + 12 X' for some / 0}
(A.2)
and
PC(p) = (y y: (y.2) O, for all e TC(p))
(A.3)
For strongly convex regularizer h R, the suhdifferential of at e X is defined as
ah(x) = y h(x') 2 h(x) (y,x' xx) for all X} and we denote the domain of subdifferentiabilin of h as
(A.4)
Xx = [x X ah(x) 2).
(A.5)
In addition, the mirror map Q, defined via
Q(y) arg max (y,,x) h(x))
(A.6)
x
is single-valued on y, since the maximization problem admits unique solution, as h is strongly convex. Finally, by the optimality conditions of (A.6), we get that
Q(y) if and only if E dh(x). since 0 E - 0xxx.. This readily implies that 2₁ = im Q. In general, we have
(A.7)
ri(X) Xr2 S X
(A.8)
where the first inclusion follows from standard results on the subdifferentiability of convex functions [42, Chap. 26], whereas the second immediate from the definition of Xg. This leads to two contrasting regimes: (i) Xn = ri(X), in which case h is called steep; and (ii) X₁ = X' in which case is called non-steep.
Finally, we include here for future reference an elementary result concerning solid (convex) cones.
Lemma A.1. Let K. be a convex cone in Rd with nonempty topological interior, and let z e int((C). Then there exists finitely generated cone K'' such that E int K'' int...
Remark. We stress here that, by int we mean the topological interior XC (which is nonempty by assumption), not the relative interior ri IC thereof (whis is always nonempty).
Proof. Since closed and 2 int K,, there exists a closed ball centered at z, which entirely contained in int K. (an immediate consequence of the fact that is well-separated from the boundary bd of K.). Since is not contained in any lower-dimensional subspace Rd it is possible to find inductively d linearly independent vectors Z1.-... . Zd E B on the boundary bd B of B such that is contained in the convex hull A(z1....,Z.) =a) (and, in particular, in the relative interior thereof). Thus, letting K' K(zz...., 2d) be the polyhedral cone generated by ZI...., Zd, have K' S and z E KC' by construction, and our proof is complete.
A.2. Statistical bounds and results from probability theory. In this section, we provide some basic statistical bounds for (SPSA), and present some results that will use freely in the sequel. We start with our bounds for (SPSA), specifically:
Proposition A.1. The estimator (SPSA) enjoys the following bounds:
[ Fi] v(x,) ||- = O(e,) and ||θ,ll- = O(1/8))
(A.9)
Proof.
Letting 2, = =, (w, (p - xr) we write 2 =x, + br, and we have for player N:
(,(&)) = ux(x)),,,r + (Vu, (x,,, w.) w + L.'' (Vu((x + T&2) (u,( (A.10)
Now, the middle term can be unfolded as
(Xu;Xx), G),,, = (X,,,(x,,, St.)).. [(V
(A.11)
3d1
14

---

and, noting that E[w,, [FF. = 0, we take conditional expectation, and we get:
(((V [F.] E; ([ (V, w FF) (=,/d))o;(x)
(A.12)
and
(l,;(x,)wr, [F] =0
(A.13)
Therefore, we have:
| [.'''' (Vu((x; r&) Vu;(x,), (.)
| [F) (x+)ll
E
Fr
O(s))
(A.14)
Now, for the second bound, since u; continuous compact domain, is bounded, and readily get that:
=01/e;)
(A.15)
Moving forward, we provide some useful results from probability theory. The first statements below are adapted from the classical textbook of Hall & Heyde [21], while the third one is simplified version of [30, Theorem 3.2] on the recurrence of nonnegative Markov process with diminishing drift. Namely, we have:
Theorem A.1. (Doob's maximal incquality, [21, Corollary 2.1J) Sf is a martingale, we have:
E[|,
P Sup Sst
for all 1 0.
(A.16)
Theorem A.2. (Burkholder's inequality, [21, Theorem 2.10)) Let S, E5= Ds. where (D (Ds)sen is martingale difference sequence, and let q (1, Then, there exists constant C that depends only on such that:
9/2
B|] s CIBE
D
(A.17)
s=1
Theorem A.3. (Lamperti [30, Theorem 3.2]) Let the non-negative stochastic process (xt)ren be defined as
Xx41 = (x, f(x)) +E,*
(A.18)
for some x f(x) bounded measurable function, and & i.i.d. with E(E, = V(G) 0² # and finite 2 + moment for some & > 0. Then:
(i) (x) s /2 for all large enough, the process is recurrent in the sense there exists oo such that
lim I <c)=1
(A.19)
T-000
(i) if f(x) 2 2o2/2xx for some 0 and all x large enough, the process is transient in the sense that
lim X, = 00 =0)==
(A.20)
Analysis and results for strategic robustness
Our aim in this appendix is to provide a detailed proof for Theorem 1, which we restate below for convenience.
Theorem 1. Let x E be a joint action profile in 9(N, Then the following are equivalent:
( xx is a strategically robust equilibrium.
(i) (u(x*),z) s -m]|zll for some m > 0 and all E TC(x"), where TC(x") is the closure of all rays emanating from x* and intersecting in least one other point.
(ii) u(x") e int()))))), where PC(x") =[y E y: (y, z) s 0, for all z TC(x")).
Proof. We will go full-cirele by showing
(ii)
(ii (
15

---

(i) (i). Suppose that x E A' is a strategically robust equilibrium, and let 0 be such that x" is equilibrium of any & with dist(G, 9) E.
For the sake of contradiction, suppose that there exists 2 0, z E TC(x") such that
(u(x'),z) =0.
(B.1)
which readily implies that there exists player E N and 2; # 0, E (x;(;,) such that
(u,(x"), = 0.
(B.2)
Fix some yi 3/ such that (yr, zi) > O, and let y (y) ........ ........).......... E y with yj for j i. N. Using (B.1) and the definition of y, we get that (u(x*) + E el|y|l. y. 2) > O, and therefore, there exists E X' such that:
(u(x') + Elylll. y, x > 0
(B.3)
Now, define the game & with payoff functions
(x) (x) + +lyy|l. (y), -1))
(B.4)
and ū = 4j for all j e N. # Then, the individual gradient vector of player e W is given by
(x) (x) + +lly|1,' y/
(B.5)
and the distance between and & is equal to
dist(G..) = sup [xp]l((x) - 8(x) = s =|lv|l" -1yll= = E.
(B.6)
xeX
Finally, conclude that x X is not an equilibrium of 9, since for p X' as above, we have (8(x"), -x)x (u(x") + 8 :llylll" voll"'aa y. - xx)
(B.7)
where the last inequality holds by (B.3). Thus, we arrive at contradiction, i.e., (o(x*), 2) 0 for all z # O, E TC(x"). Finally, since {z E V TC(x"), ||/|| = 1} is compact, we readily obtain
sup( : TC(x"), ||||| 13 m
(B.8)
for some > 0. Therefore, for all z TC(x"), have:
(u(x"), 2) s -m||=ll
(B.9)
as was to shown.
(ii) = (ii).. First, note that the ||-11-- ball of radius & > O centered at o(x*) can be written as:
B (xxx)))) = v(x") + IB, (0)
(B.10)
where (y) =/y eV: 11y - yll. r) for E y. Now, take any E (0) and TC(x"). Then, for & we have
(u(x") + ey. 2) (u(x"), + e(y,
I =l|| + e||g|1.1lz||
S -m - ||]|
(B.11)
Setting = m/2, we have for all TC(x")
(u(x") + (m/2)y,2) z) < (mm/)]]lz
(B.12)
which implics that u(x*) (m/2)y e PC(x*). Thus, we readily get that (m,((v(x")) C PC(x*),i.. i... v(x") E int(PC(x*)).
(ii) (i). Suppose that v(x") int(PC(x')). First, directly implies that (o(x*), for all 7 E TC(x"), i.c., x² is an equilibrium of G. In addition, there exists & > 0 such that B (u(x") PC(x*). Therefore, for any game I with dist(g, 9) < E, we immediately get that T(x") e PC(x"), which implies that x e X' an equilibrium of G. Thus, is strategically robust, and our proof is complete.
16

---

C Analysis and results for dynamic robustness
In this appendix, we provide detailed proofs of the statements presented in Section 4, along with several intermediate results that will serve as key building blocks.
C.1. Intermediate results. We begin this section with two results establishing sufficient conditions for convergence, followed by a proobbbbbbbiltty deviation bound for martingales. We conclude with a variant of Farkas' Lemma, which will be instrumental in deriving convergence rates.
Proposition C.1. Let x" X and 2 [= ..... 2m) - V be set of unil vectors, such that any z TC(xx) can written as 2 = Σド=1 2zz for some d3 2 If lim; (tt: 24) -0o for all 2j 2, then lim (()))= =x'
Proof. Denote Q(yr) by X,, and suppose that lim sup, x''l > 0. Then, there exists a subsequence (xt, seN such that ||x,, -x'll stays bounded away from zero, i.e., ||x; -x'll c for some c 0 and all s E IN. Since yr, E dh(x,,) ) we readily get for 2r, (Xe, - xx') x')// x ||:
h(x') 2 h(xi,) (yeg, - -xe,)
h(x,) - (e,,, 11xe, - x"1l
2 min h - (1,,,22,1 (1,,) - x²11
(C.1)
Now, we have 2n TC(x"), and by assumption 2zZ 2n Ajzzzj for some coefficients 4j,5 0. Therefore, the above inequality can be written as:
m
h(x") 2 min h - ||xe, - x1 Σ
d (11er
(C.2)
2 min h maxx(1n 2pr) || -x"ll
(C.3)
j=l
Now, note that by the definition of Zr,- we have || and, thus:
m
m
m
1 = || |l =
Σ
1
jzzz
$
> ال = Σ
(C.4)
j=1
f=l
where we used that ||zy|| for all j. Now, since (y), 2z) = for all 2 Z, readily implies that
lim max (yr, 2p) -c0
(C.5)
Therefore, for all large enough, we have -max, (yt, 2pr) > and, using that Σ Aj.s 2 1 and I|xe, -x"ll 2 for all E N. we obtain:
h(x') 2 min (- max 23r) |l,e, - xx
j
(C.6)
min h max(yr, 2
(C.7)
Finally, letting oo, we get that h(x*) 2 co, which a contradiction. Thus, the result follows.
Finally, using the above proposition, we establish the following corollary.
Corollary C.1. Let W(M) =yy e y: ze (y. 2) -M)
MMMof for M Then, for any & 0, there exists M > O such that for all E W(M)) it holds I|x" @(y) || < <.
Proof. Suppose it does not hold. Then, there exists 0 such that for any E I, one can find
yt E y such that max (gr, 2) < <- and I|x" ( E. Taking - co leads to a contradiction with Proposition C.I.
17

---

Lemma C.1. Let y 35=1 1 Es be martingale with respect to filtration (Fi)re such that Bl1 of for all N and some q 2 2. Then, for any (0. 1) and 0, it holds:
yol1-u) Σ 03S
P
sup TS
|+1 > c(yr))) S Cy
(C.8)
(1
where Cq is a constant that depends only on e and q.
Proof. To bound the maximum absolute deviation of St, we apply Doob's maximal inequality (see Theorem A.1), and obtain:
EUS,
P sup |t1 > c(rr)")
(C.9)
c² (yr)en
Now, we invoke Burkholder's inequality (see Theorem A.2), from which we get:
9/2
9/2
B||S, C.
B
Σ
S ,g E
ΣEEP 1E,
(C.10)
s=1
where Cy is a constant that depends only on Since 2 2, applying Jensen's inequality, we obtain:
4/2
-
S
Σ
15.19
(C.11)
and, therefore,
9/2
1
E
Σ
Es
?
1/211
E
Σ
1
(C.12)
//21-
07
(C.13)
Thus, combining the above with (C.9) and (C.10), we obtain:
1/ Σ T
P sup
Sr c(ys)
(C.14)
09 c9(1))9
TS1
y9(1-H) E1 E/= 03 11t9(x-1/2)
Cg
(C.15)
for C. CG and the proof is complete.
We finally provide a separation result in the spirit of Farkas' lemma, that we will need for establishing the convergence rates.
Lemma C.2. Ler X (x = b. 0} for A RRxdd b E Rd. Then, for all x" E X with act(x") =(B E (1...., d} x = 0}, there exists P(x") 2 1 such that for all I S act(x") ) at least
one of the the following is Irue:
(i) I # 0 and there exists B E act(xx) such that xB s P max(xa a I) for all x e X.
(ii) There exists ker(A) such that ||ж|| s P. 2p ffr B I and S up P for E act(x") II. Then, there exists
Proof. For the proof, see Azizian al. [6, Lemma 6].
18

---

C.2. Main results of Section 4. With the necessary tools in place, we proceed to prove the main results stated in Section 4. We start with the first result, establishing that a -oneiuiiiir point cannot arise as a limit point of the sequence of play induced by (FTRI..
Proposition 2. Suppose that (FTRL) is run with perfect gradient feedback of the form 8, = v(x,) for all 1 1,2, ..... and assume that X, converges some & E X. Then & is an equilibrium of G.
Proof. Since i is not an equilibrium, there exists p E X with (o(8), p p- -8) > 0. Therefore, by continuity of the function = (u(x),p->) x), there exists neighborhood U of & and 0 such that (u(x), 1- x) 2 c for x E U.
Moreover, since cl(()) compact, we have supredizz)lo(3)) suppose that - Å. Then, X2 E un n (c/4 eventually, i.c., there exists no such that x, E ll and ||x, - -l| Finally, since y E @h(x,), we have for > to:
(lx())) Il. = B < co. For the sake of contradiction,
c/4B for all r no.
hp)) 2 hxx) + (y:, P xx)
2 h(x,)) + (yhu x1) + Σ (oxx)),-xx)
[-] (o(xx), pxx, +Xx xi)
h(xx)) + (ylm p 1-xp) x1) +
Σ
x=b
[-]
2 h(xx)) + (Ulm P - -xx)+ Σ
+
((u(x;). pouxxs).-xx. x,) (0(x,), - xx))
[-]
h(xx,) + (ytn. P p-xx) x1) +
Σ ((v(s))
11lx,))l
s=bo
2 h(xx)) + (ymm P -- xx) + Σ (c - Bl|xs - xx
x=1o
[-]
2 h(xx)) - 11 - x +
Σ (c c/2)
x=
2 min h 11y ll. diam X²) + yc(t - 1o) 12
(C.16)
Taking: - oo, we obtain h(p) 2 0o, which is a contradiction. Therefore, the result follows.
Moving forward, we show that equilibrium points in the relative interior cannot be limit points of (FTRL), either. Formally, we have:
Proposition 3. Let x" E ri(X)) be a Nash equilibrium of CGN,, X, X.u), and (xz)TeN be the sequence of play induced by (FTRL) with 0 v(x,) + U., where U, i...d. with E[U,] 0 and cov(U,) > 0 for all t N. Then:
P lim X = =x=) xx====== = 1000
for any x1 E Xn.
(15)
Proof. Since x" an equilibrium point ri()', we readily get that (u(x*),x 00 for all x e X, and x Xr. In view of this, there exists y" E y such that E @h(x"), ie., = Q(y)). Our goal is to show that the auxiliary process yr does not converge to @h(x"). However, there are infinitely many points in y' that belong to dh(x"), so this attempt is insufficient, in the sense that, showing that o is not a limit point of the yt dynamics, does not preclude that some other E 0h(x") is not.
To tackle this issue, we will show that the space y can be decomposed as y = 5 e 5 where all the "essential" deviations of the problem is in V. For this, we define the set
x = {y E y (y. P - x) 0, for all x, E X) which is subspace of Yr and as the following lemma suggests, is equal to the polar cone at any point in the relative interior.
(C.17)
Lemma C.3. Let xo ri(X)) and 5 ty E y: (y.P x) 0. for all x, p X}. Then 5 = PC(x)).
19

---

To preserve the clarity of the argument, we defer the proof of Lemma C.3 until the end of this proposition. Letting J be the orthocomplement of y, readily get that y Ye V, and any point in y' can be uniquely written as y = - + with f 5 and y D. Defining the linear map y y as Hy = D. and more importantly, under all points in åh(x") under II are essentially unique.
This is formalized in the following lemma, whose proof is relegated after this proposition.
Lemma C.4. Let X E ri(X) and y.y' 0h(xa)- Then Hy a and Nl Ily'.
In view of the above, are now ready to prove the result. Namely, fix some p E R, p # x² and let & (IWU, p -- xx).
Then, setting x² = (p-x') such that P > E) à for all r N. Therefore, by the second Borel-Cantelli lemma [9], we get P(A) for A = (5, > & infinitely often). For the sake of contradiction, suppose that P > 0 for = (lim Xy = }x). Fix some w E Then, for all large enough, we readily get that (w) E ri(X), and, denoting 2, nl, and z' = Illy,, we readily get that
O, we have &, ~ (0, o²) i.i.d., and, so, there exists ô > 0
lim Zt (w) = 1-00
(C.18)
Thus, setting a, (z, z', x') we conclude by the above equality that lim, a, = 0, and therefore it holds
lim (at, (21-1)
1-00
lim (II,, / x²)
1-00
lim (Ilu(x;), - x²) + (IIU, p -x))
1-100
(Ilu(x'., + lim &
1000
lim &
(C.19)
1-000
Therefore, & A, which implies that B S AS, with P(A9) = 0. Thus, P(B) 0. which is contradiction, and the result follows.
We now prove the two auxiliary lemmas presented in the proof of Proposition 3.
Lemma C.3. Let xo E ri(X)) and 5 ty E y (y. p xx) = 0, for all x, X}. Then ÿ = PC(x)).
Proof. First, we will show that
PC(xo) = ty y: (y.p - xo) 0 for all p E X)
(C.20)
For this, suppose that there exist y E PC(xp) and p' X such -') 0. Then, since xo E ri(A), there exists a > 0 such that xo a(p'' - xo) E X. By the definition of the polar cone, xy, - ap' xo) xo) 0, or equivalently, Ky. xo) 2 which is a contradiction. Therefore, (C.20) holds, which implies that y c PC(x).
Now, for the inverse inclusion, let E PC(xo) and p,x E X. Then, we have:
(y. p - x)
(y. p - Xg + Xip -
(y. p xo) (y.x0- xx x)
0
(C.21)
where the last equality follows by (C.20). Thus, E 5, and we conclude the result.
Lemma C.4. Let x ri(2)) and y. Ōh(xa). Then Ny @h(xa), and Nl Tly.
Proof. For the first part, note that
(y. p xo) =( (Ū+ū.p xo) = (g. P xo) (ū. x
20

---

= (g. p -x0
(Iy. (-y.p-xo)
(C.22)
which directly implies that Ny E (h())). For the second part, since xo ri(X), and y. e ah(x)). we have that
yy xx) 0 for all p t
(C.23)
Thus y - o e PC(x)), and invoking Lemma C.3 we obtain that y y' D. Therefore, applying the linear projection operator II, we readily get that Πy y') = 0, and, using linearity, the result follows.
We now turn to main convergence theorems, showing that the iterates of (FTRL) converge with high probability under both gradient-based and payoff- based feedback
Theorem 2. Let x" E X be a strategically robust equilibrium of 9 X,,,,,,, Fix a confidence level
5 > 0, and let (x))ee be the iterates of (FTRL) with feedback provided by (SFO), and step-size
y > 0 sufficiently small. Then, there exists a neighborhood U of x" in Xn such that:
P liim (0-00 X, =x) 2 6 ifxi EM.
(16)
Proof. Since x² strategically robust, o(x") lies in the interior of the PC(x'). By Lemma A.I, this implies in turn that there exists a polyhedral cone K. generated by Z = (z1,..., Ir for r N, such that TC(x*) S K and (v(x"). < <0 for all z Z.* Therefore, for all 2 Z, we have (u(x*), and by continuity of the vector field v, there exists neighborhood U of x* and c > 0 such that (u(x), 2) - for all z e 2 and x U.
-m.
Fixing some z 2, we obtain:
(y++1, 2) (y),,) y(0,.2)
= =y1, y(v(x,), 2) + (())2))
(y),,) + Σ (1(xs) 2) + Σ (U,
(C.24)
s=l
Now, we define the stochastic process (S:)ee via S₁ =y Ex (U.. which is martingale, since 2), Fs] = O.
Therefore, by Lemma C.1 for o, = o, q > 2 and E (0. 1), whose value is determined later, we get:
ST1 > c(yr)# Cy y9(1=4)0
6, = sup T
(C.25)
19(1-1/2)
where Cg is a constant that depends only on and q. Thus, we readily have that:
= - P U
P
sup rsr
| s c(rr)²
sup Tst
|S,1 > c(ri)a
/21
2 1 Σ
P
sup rss
|S+| c(yr)
[=1
2
1
Σ 6
(C.26)
where the second inequality comes from the union bound. Now, we need ensure that Σ 6, 6/r. For this, we need the sequence to be summable, which, using (C.25), is guaranteed for q(u-1/2) > I, or equivalently, μ (1/2 + 1/q. 1). Therefore, for y small enough, we obtain that Σ 6, 6/r.
Therefore, with probability at least - 6/r, the template inequality becomes:
(y/+1, 2) s (v). z) +y Σ (x(x))) clyr)"
(C.27)
"To resolve any ambiguities, the cone in question here is the polar of the provided by Lemma A.I.
21

---

If we initialize such that (y1, z²) < <-M- - for all z' E 2, we get that (yr, z) < -M for all e N with probability at least - ö/r. To see this, suppose that (Us, -M for all 1, I,...,t. Then
(Ur+1.2) = (y). + Σ (o(x)) + Σ (U,
- c cyt c- clyt)"
(C.28)
For N with yr I, we have -c c(yr)" O, while for yr 1, it holds -cyt + clyr)" < 0. In both cases, we conclude that (U1+1, z) < -,M, and by induction, we get the inequality. Therefore, with probability at least 6/r, we have:
(y++1. 2) M - eyt+
(C.29)
and sending / - co, we get (y., - -00
Finally, repeating the same argument for all 2 and applying union bound, we readily get that (yr.)) z) - -o with probability at least 6, and invoking Proposition C.I, the result follows.
Having established the local convergence to x with high probability, we proceed to the convergence rate in the case of affinely constrained X' and decomposable regularizer h.
Theorem 3. If. in addition, X is polyhedral domain and h is decomposable with kernel 6, on the event E (lim, X4 =x" holds:
-
(17)
where b is the rate function defined via
s 2 (00)
if > (0+)
(18)
if S 0' (0*)
Proof. By the definition of the iterates of (FTRL), we have:
@ = arg min (((x) (y...) Ax = b, 2 0}
(C.30)
x
Introducing the Lagrangian
C(x, h(x) - -(),x)+ Σ
A bbi Σ MĄai
(C.31)
1=1
with d; and Hj 2 0, by the KKT conditions, we readily obtain:
m y1 Vh(x,) + > Aaa;
(C.32)
where Vh(x) = E3 0' (xg,)))B, since 0 is continuously differentiable.
For the sequel, we define the set of active constraints at x" act(x") (l.....d) x = 0). Note that the event of (lim, X, = xx), ), the iterates x, lie in neighborhood of x*, shown in Theorem 2. Thus, all non-active indices or & act(x") stay bounded away from zero, and so (0(x..)l remains bounded for all r.
We treat the two cases separately: (i) the steep case, where h is steep - equivalently 8(0+) -o0, and (ii) the non-steep case, where is h not steep, i.e.. 0' 8'(0)) -00
The steep case. We define the of "good" indices I at step as: B e I of (xp.)) -0()). Our goal is to show that all indices act(x") of x, are "good". . Fix some i E N.
Suppose that act(x") \ I 0, and let P 1, per Lemma C.2. Then,
condition (i) of Lemma C.2 holds, there exists B' such that xØ. S P max(xaa, a I}, and thus, I + IU (
22

---

If condition (ii) of Lemma C.2 holds, there exists z' E ker(A) such that || & P. 2B = 8 and 1 1 2p s P if / act(x*) I. By (C.32), and noting that z' ker(A) and μ = 0, since all constraints are non-active due to steepness of h. have:
(Vh(x,), = (y1.2))
(C.33)
Moreover, it holds:
(Vh(s,),z)= Σ e (xp.)) Σ el (xp.))z BeI
Σ ('(xx))+++ (eacu(s))
Σ
(xp,,)
G=1
(Eac((x))
e' (xpx,)) (
Σ
+C
(C.34)
for constant C, since non-active indices remain bounded away from zero, as explained in the beginning. Now, note that z' E TC(x*), and thus, by Lemma A.I, we can write z' as z' E 4zz with & 2 O, such that (yr, 2i) $ (r( for all I....,r r as in the proof of Theorem So, combining it with (C.39), (C.34), we obtain:
Σ Beact(x*)
('(x,.) s (
(C.35)
and therefore, there exists at least one B³ E act((x)) I such that
8' (xpx,)) s 0
(C.36)
Thus, I (B')
Therefore, as act(x*) is finite, we conclude inductively that 6' (x(x..) s -O(1) for all B e act(x"). Finally, we have that Rd row(A) spante fp= B act(x")), and thus, for all we can write the standard basis vector as Epean(x) Ai, + a; for some a; E row(A)
Ni, x =xx xx,x,;,))
X4
Σ Beact((²)
di. +
diBB
BEact(x*)
Ai,B....
(C.37)
BEact(x*)
where we used that (x, xxx,"ae equivalence of norms and the above, we conclude that
xx'aa) a,) = O. Thus, since 8' (x(x,,) S -1()) for all B act(x"), by the
||x, - x''=x
(C.38)
The non-steep case. For the stn-steep case, follow a similar approach, but with some modifi- cations since the iterates of (FTRL) are not always the interior of X.
Specifically, let the set of "good" indices I be defined as: B I if xp. 0 0' (x(x.) N -0(). Our goal is to show that all indices act(x") of x, are "good". We construct sequentially, as before.
Suppose that act(x") ) \I # 0, and let P 2 1, as per Lemma C.2. Then,
If condition (i) of Lemma C.2 holds, there exists B' such that xpr P Pmax(Xa. I], and thus, I + IU (8').
If condition (ii) of Lemma C.2 holds, there exists z' e ker(A) such that || s P, = =f and s z/g P if B act(x") I.. Therefore, we have
(Vh(x)) = (g.,z') (,,z²) (yr,z') + Σ upzi
up2z
Σ
BeI
Beaci(x))
-yr,
(C.39)
23

---

where, in this case, we used that (i) 0z 2/= for B I, (ii) H3 0 by complementary slackness for B & act(x") since these constraints remain non-active for the whole process, and (iii) Mg 0, again by complementary slackness for ß E act(x") \ I since they were active, we would have B E I. This, with the same argument before, conclude that
Σ BEaCT MI
0' (xp,,) & (1))
(C.40)
and therefore, there exists at least one B' act(x") \ such that
0' ('(x $ (r)
(C.41)
This holds until 8 vanishes, which can lead μp 0. In either case, have I I (B').
Finally, since act(x") is finite, we conclude inductively that all for all B e act(x"), we have either 8' (xp,) (1)) or Xp,r = O. As in the steep case, we conclude
||,, - x = =
(C.42)
We now shift the payoff-based setting. The relevant result is restated below.
Theorem 4. Let x* E X be strategically robust equilibrium of G. Fix confidence level ō > 0. and let (x be the iterates of (FTRL) run with (SPSA) with E, o 1/t" for some p E (0, 1/2) and step-size y 0 sufficiently small. Then, there exists a neighborhood U of x² such that:
P lim x, =x²) 1-8
if ElU.
(19)
If. in addition, X is affinely constrained and h is decomposable with kernel then, whenever X₁ converges to x", we have:
||x, -
(20)
Proof.
First of all, we write 8, in the following convenient form:
i = v(x,) + U, b,
(C.43)
with
U, 0, B[ [J
and
= 1[0, v(x,)
(C.44)
which, by Proposition A.1, satisfy the bounds ||U, (1/8;) and ||b, ||- O(e)). Now, as in the proof of Theorem 2, v(x') lies in the interior of the PC(x*). By Lemma A.1 this in turn implies that there exists a polyhedral cone IC generated by 2 = {21,..., 2r) for E N, such that TC(x") IC and (u(x"),z) < 0 for all E 2. Therefore, for all E 2, we have (u(x"),z) I -m, and by continuity of the vector field u, there exists a neighborhood xf and c > such that (v(x), z) s - for all Z and x E U. Fix some Z. Then, unfolding the evolution of yr. have:
(y++1. 2) = (yr, =) + (0r,
(y,, z) y (o(xx) (U,, (b,,))
= (y), z) Σ (o(xs). + Σ (Us, 2) + Σ (b,
(C.45)
Now, we define the stochastic process (S))en via y Di (Us, 2), which is martingale, since El 2) F.] = 0, and [[]K,,, 2) F.) & E[I [Fs = ((11/,))))
Therefore, by Lemma C.1 for o,, @(1e,,), 2 and (0, 1), whose value is determined later, we get:
y0(1-w) E o
8, : P sup TS1
S (c/2)<r1)*) Cq 100011111 (1=g(a-112)
(C.46)
5 As before, to resolve any ambiguities, the cone in question here is the polar of the cone provided by Lemma A.I.
24

---

where Cq is a constant that depends only on and Thus, for = E/t", there exist B > 0 such that:
Σ
0
BE
9
Σ
pa
z B' 8'85-114pp 1
(C.47)
s=l
s=1
where we used that ش sP9 ( (p)). So, using the above bound, (C.48) becomes:
C y9(1-))
8, Cy (1t9(1-112)
(C.48)
19(H-112-p)
Thus, we readily have that:
n sup r21 TSA
|Sr| sup
s c(yr)")
P
U
sup /r1 c(vo)()
121
2 1 Σ
sup |S+| c(yr)
[=1
2 1
Σ 1=1
(C.49)
Now, we need to show that there exists μ E (0, 1) and q > such that " 6, s 6/r. order for the sum to be finite, we need q(μ 1/2-p) p) which readily implies that p < p 1/2 1/q.
For the bias term, since ||b,ll- = ((s), we have:
Σ (bs 2) s Σ 11&11 s Σ b.ll. S
D E5 S D
s/sP= s D'grl-P
(C.50)
8=1
for some D' > O, where in the last inequality we used that Σ 1/sP = 0( Therefore, for 1 P p. and y L, readily get that
Σ y
(b,, D'yer" D'e(yt)"
(C.51)
s=1
Therefore, we need to satisfy
-- 1/2- 1/q
(C.52)
from which obtain μ E (3/4, 1). Thus, for p (0, 1/2), there exist μ (3/4, 1) and & 2 that satisfy (C.51). So, for e, y sufficiently small we can guarantee that
Σ (b., 2) (c)2) and
Σ
S 5/r
(C.53)
Therefore, with probability at least 6/r, , the template inequality becomes:
(1++1.2) s ()),2) + Σ (o(x)) +
$ (1), z) + Σ (o(x)),)) c(y))"
(C.54)
Initializing yn such that (y1, z²) - for all z 2, have (),,z) -M for all N with probability at least 1 - 6fr. To see this, we proceed by induction, and suppose that (ys, z) < - M for
all I.....f. Then
1 2V., +y 2b) (y++1. = ()) + Σ (o(xs). 2) +y
s=1
s=1
s=1
S S-M- cyt c((y))
(C.55)
For N with yr < 1, we have -c c while for yt 1, it holds -cyl c(yr)" 0. In both cases, conclude that 2))+1. -M, and by induction, get the inequality.
25

---

Therefore, with probability at least 1 6/r, we have:
(1++1. -M c-cy clys)"
(C.56)
and sending 1 - oo, we get (yr. + -00
As final step, using the same argument for all E Z and applying a union bound, we have that (y,, 2) - with probability at least ō, and by Proposition C.I, we get that
P lim =x) 2 11
(C.57)
If, in addition, X' affinely constrained and h is decomposable with kernel 0, then the argument in the proof of Theorem applies verbatim, yielding:
||x; x'll ((-0(1))
(C.58)
whenever x, converges to xo.x".
We conclude this appendix with Proposition 4, which illustrates that an extreme, non-strategically robust equilibrium may exhibit fundamentally different behavior depending on the choice of regular- izer.
Proposition 4. Consider the 1-player game G with X = [0. 1J. u(x) - and x" = O. Let (xt)aaN be the iterates of (FTRL) with y < and i, o(x,) + U,. where U, are i.i.d standard normal random variables for all N. Then, for any initial condition y1 E R, we have:
(i) For h(x) x logx, it holds P(lim, X, =x") ) 0.
(i) For h(x) = -2NX, it holds P(lim X, = xx) = 1.
Proof. We show each case separately.
(i) Writing down the (FTRL) dynamics, we have
Ur+1 yr y(=x, 1/3 U,) = sup (yr x x log x [0.1)
(C.59)
Solving the maximization problem in the definition of x,, we obtain:
x; = [xxp(y: - 1), yt 1 1. if y/ >
or, equivalently, X (y, > 11 (yr $ 1) exp(y, 1) and the dual process can be written as:
yr+1 = yt y 1y > 1) - 1 - 1) exp ((yr 1)/3) +yU,
(C.60)
It is clear that X, 0 if and only if yr
goes infinity. For notational convenience, set Zn = -tr. Then, the evolution of the dual process becomes:
2+4 2 1(2, + 11 - exp ((-z, - 1)/3) yU,
(C.61)
Now, define the process
</1 y 1 (11) 1 ex- (1-2) 1)/3) - -u,)" 21
(C.62)
where is the same random variable in (C.61).
The rest of our proof relies on series claims, which we state and prove one-by-one.
Claim 1. The process (z))en dominates (Z.)Ie, iee, 2ς for all i N.
The proof of Claim 1 lies at the end. Now, invoking Theorem A.3 with
f(z) = y (z < -1) +y (2 2 -1) exp ((-z - 1)/3)
(C.63)
bounded and u===²² it holds that
x² f(z) -
for all z large enough
(C.64)
2z
26

---

Thus, (EN is recurrent, which implies that Finally, since
P lim 24 = 00) 1-00
(C.65)
ENN dominates
(EI) by Claim 1, we obtain
lim 21 00
lim 2 o
(C.66)
which implies that and the result follows.
P lim = =xx) P lim oo) s P 1--000
lim zi 00) = 1-000
(C.67)
10-00
Proof of Claim 1. Consider the function
= (z < -1) +y (z -1) exp ((-2- 1)/3)
(C.68)
Then:
For z <1: (z) =
For > -1: gz)) = y/3 exp ((-z- 1)/3) > 1 1- - 0
Thus, is strictly increasing for all E R. Now, for the sake of contradiction, suppose that there exists w E Q and a first time k + E N where the dominance does not hold, i.e.,
[x(w) (w) and <k(i(w) < (()
(C.69)
By the monotonicity property of g. we get that
g(xx(w)) S g(z((w))) and, therefore, adding (w) in both sides
(C.70)
(w) , + 1(2 < - +y 1(4 2 -1) exp (1-2) -yU,
+ < -1) +y 1(2 -1) exp ((-2) 1)/3) -U,)*
$ (w)
(C.71)
which is contradiction. Thus, the proof of Claim is complete.
(ii) In this setup, the (FTRL) dynamics are described by the system
yr+1 = U/ 7 xx- 1/3 U²) x; = supx= [0.1] (yr x 2v
(C.72)
Solving the maximization problem in the definition of x,, we obtain:
(-1)) y: -1 x; 1. if > -1
(C.73)
or, equivalently, x, (y, > -1) [1 1 -1)
2 and the dual process can be written as:
Ur+1 y/r - y 1 > -1 1 S --))(-y;) 2/3 yU, For notational convenience, set Σn 1/t Then, the evolution of the dual process becomes:
(C.74)
2++1 = + 1 (2, 1) + 1 (z, 2 1)z, 2/3 yU,
(C.75)
It is clear that x, + 0 if and only if
as goes to infinity. Now, define the process
<ạ,1 = 2 y ( 1y 2 11:2213yUj -yU:). 2 =1
(C.76)
where U, is the same randomness in (C.75).
27

---

Claim 2. The process (Z dominates (zi)IeN, i.e., 2, 2 2, for all r e N.
The proof of Claim 2 lies at the end. Now, invoking Theorem A.3 with
y < + [ 1)23
(C.77)
bounded, o² == and 1, we have
f(z) 2 0²0
for all large enough
(C.78)
2z
Thus, ENN is transient, which implies that P(A) for {w Q: lim 2,(w)) o0).
Now, fix some E A. Since lim (w) = co, there exists nu E IN such that 2/ > for all n 2 Ba and therefore
-/+1 ž yz₁ 22/3 - yU,
p + y Σ
125-1/3 Us)
(C.79)
s-+
from which we conclude that
2
2/3
Uss
+ 00 as 1 - 00
(C.80)
s=m
Finally, we have that
21+1 Zno +y
Σ
((2 < 1) 1l (2, 2 1)z,
U.) -Us]
(C.81)
x
and, since (ZJ)EN dominates (Zi)reN. and 2 for all 2 tw we readily get that
(11(s 11)+ 2 1)zs 2//3 Us z
(1(z,
Σ
2
2 Us)
(C.82)
x
x=n +1
Thus, by (C.80), we conclude that
Σ (1(2, < 1) 112+ 2 1)2, 2/13 - -U,) 4
as 1 - 00
(C.83)
which implies that lim, - 2, (w) and since (PA)) = 1, it follows that
Therefore, we obtain that lim, (w) oo for all A.
P lim x, =xx) P lim &, 00) 1-000
(C.84)
and the proof is complete.
Proof of Claim 2. Consider the function
g [t)== 1)2-
(C.85)
Then:
For z < 1: (1))g(())++>>>>>>
Zorz 1: gz))==
5/33333 1- 2y/3
Thus, g is strictly increasing for all E R. Now, for the sake of contradiction, suppose that there exists @ E Q and a first time & 1 E N where the dominance does not hold, i.c.,
(w) Z (w) and
< (())
(C.86)
By the monotonicity property of g, we get that
g(z((w)) (()((w))
(C.87)
and therefore, adding (wU in both sides
1)+1(w) (w) < t 1)+ 1(2, 2 1)/3- yUs
$ + < 1) +y 1(24 2 1)z4 -2/3 - -UUs)
$ (w)
(C.88)
which is a contradiction. Thus, the proof of Claim 2 is complete.
28

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
It can found in Section 3, Section and the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: It can be found in Section 1.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specificationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: It can be found in Section 3, Section 4 and the appendix.
29

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility can also provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
example, if the contribution
While NeurIPS does not require releasing code, the conference does require all submissions provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be way access this model for reproducing the results or way reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
30

---

The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips (tttps///nips.cc/ubblic/ cc/public/ guides/CodeSubmn www.Ssumiissosoliioooooooooooooe ssionPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code. unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips////ppp.// cc/ cc/public/ guides guides/CooeeSumissee www.iiisssiiiooooooooooooii for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reprodueible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
No statistical significance applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap. etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
31

---

If eтrог bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
Experiments compute resources
Question: For each experiment, does the puper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics https://neur .ss..ppssss........e ctt..cccpuuueeee cccppbicc/tthhicsuieeeliiii
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
32

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e-g. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There are such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. wttccooe.coo/aaaaeeeeoeeeeeeo com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
33

---

The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable), You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy hettss///eerrissscc///ooeeeee//s for what should or should not be described.
34


Reviews:
[{"review_id": "nlrlQTfYnF", "reviewer": "Reviewer_D3Vd", "summary": "The paper shows connections between two notions of robustness in games. The first is strategic robustness which requires that an equilibrium of a game continues to be an equilibrium even if the payoffs of the game are perturbed by a small amount. The second is dynamic robustness, which requires that learning dynamics converge to this equilibrium even if the initial point is perturbed by a small amount. \n\nThe second notion of robustness is interesting in dynamics where the step-sizes don’t decay. So the paper considers dynamic robustness with FTRL as learning dynamics and show that their results apply to FTRL with any choice of regularizer. \n\nThe paper provides a geometric interpretation of strategic robust equilibria. The paper shows that strategic robustness is a sufficient condition for dynamic robustness relative to FTRL for two feedback structures: unbiased estimate of loss gradients and simply the loss received. \n\nToward arguing that strategic robustness is also necessary, they show that strategic robustness is necessary for some regularizer in an example they construct.", "questions": "Do you think this connection will extend to other dynamics, such as gradient descent?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: The paper makes a nice connection between two forms of robustness of equilibria. This also seems to be a connection between two forms of equilibrium selection --- based on payoffs and based on convergence of dynamics. The paper is well-written and the main arguments are easy to follow.\n\nWeaknesses: 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.", "was_revised": true, "final_justification": "The work contained interesting results and was presented well. They also provided helpful clarifications and addressed concerns during the rebuttal phase. Hence I would like to keep my positive score.", "rebuttal": "Dear reviewer,\n\nThank you for your time, detailed input, and strong positive evaluation! We reply to your remarks and questions below:\n\n---\n> 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.\n\nSure 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.\n\nA bit more formally, the intuition and key steps for the proof are as follows:\n\n1. 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.\n1. 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$.\n1. 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]\n1. 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.]\n1. 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$.\n\nPlease 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.\n\n---\n> Do you think this connection will extend to other dynamics, such as gradient descent?\n\nGreat question—both yes and no.\n\nTo explain what we mean, consider the unconstrained (stochastic) gradient ascent algorithm\n$$\nx_{n+1} = x_n + \\gamma \\hat v_n\n\\qquad\n\\text{(SGA)}\n$$\nwhere $\\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).\n\nNow, in the constrained case, there are two variants of (SGA) to consider. The first interleaves gradient steps and projections as\n$$\nx_{n+1} = \\Pi(x_n + \\gamma \\hat v_n)\n\\qquad\n\\textrm{(P-SGA)}\n$$\nwhere $\\Pi$ denotes the standard Euclidan projection on $\\mathcal{X}$. The second is known as \"SGA with lazy projections\" (Zinkevich, 2003) and proceeds as\n$$\ny_{n+1} = y_n + \\gamma \\hat v_n,\n\\quad\nx_{n+1} = \\Pi(x_n)\n\\qquad\n\\textrm{(L-SGA)}\n$$\ni.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.\n\n**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.\n\n---\nThank 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!\n\nKind regards,\n\nThe authors \n\n---\n### References\n\n- Y. Nesterov, “*Primal-dual subgradient methods for convex problems*,” Mathematical Programming, vol. 120, no. 1, pp. 221–259, 2009.\n- S. Shalev-Shwartz, “*Online learning and online convex optimization*,” Foundations and Trends in Machine Learning, vol. 4, no. 2, pp. 107–194, 2011.\n- 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."}, {"review_id": "HmjgiA73ES", "reviewer": "Reviewer_5rLL", "summary": "This paper defines two notions of stability for local Nash equilibrium in continuous games: strategic robustness and dynamic robustness. For strategic robustness, the author refers to a Nash equilibrium that remains unchanged under perturbation in the underlying game's payoff structure in terms of the vector fields. For dynamic robustness, the authors refer to an equilibrium that attracts the FTRL dynamics with initial conditions in a neighborhood. \n\nThe main results include a characterization of the strategic robustness equilibrium (Thm 1) and a proof that FTRL converges to the strategic robustness equilibrium (Thm 2).", "questions": "* 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? \n\n  **(This is my main concern. I would be happy to increase my evaluation score if this issue is addressed.)**\n\n* Does the dynamic robustness result still hold when considering the average-iterate behavior of FTRL dynamics?\n\n* Is it possible to define robustness for mix Nash equilibrium?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n* The problem studied in this paper is interesting, and the writting is clear and easy to follow.\n* The observation that small perturbation on the payoff value of games will destroy all the equilibrium (Example 3.1 & 3.2) is interesting.\n* Theorem 1 provides an interesting characterization of the geometry of robust equilibrium in terms of TC and PC.\n\nWeaknesses:\n\n* 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. 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.\n\n* 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. Especially, it is not clear whether the result of Theorem 2 also applies to the vanishing step size case.", "was_revised": true, "final_justification": "My main concern regarding the existence of a robust equilibrium defined in this paper has been addressed.", "rebuttal": "Dear reviewer,\n\nThank you for your time and constructive input. We reply to your remarks and questions below:\n\n> 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.\n[...]\n> 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.)\n\nCertainly! Some widely studied classes of games that always admit robust equilibria (except for a measure zero set of instances) are as follows:\n1. **Atomic, non-splittable routing games** with arbitrary (increasing) cost functions.\n2. **Markov potential games** in the context of multi-agent reinforcement learning.\n3. **Cournot competitions** for agents with no (or small) price-setting power.\n\nWe 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$\n\n---\n#### $^1$ *Justification of the existence of robust equilibria in the classes mentioned above:*\n\n1. *For atomic, non-splittable routing games:* see Rosenthal (1973) and note that strict Nash equilibria of finite games are robust.\n1. *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).\n1. *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.\n\n---\n> 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.\n\nYes, 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.\n\nPut 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.\n\n---\n> 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.\n\nWe 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$.**\n\n[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]\n\nNow, 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:\n\n- 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).\n- 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).\n\nFor 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):\n\n```\nWe keep a constant learning rate of 2.2 × 10−4 until the model consumes 10T training tokens.\n[...]\nDuring 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.\n```\n\nOf 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.\n\n---\n> It is not clear whether the result of Theorem 2 also applies to the vanishing step size case.\n\nYes, 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\n$$\n\\frac{\\sum_{k=1}^n \\gamma_k^{q(1-\\mu) \\sigma_k^q}}{(\\sum_{k=1}^n \\gamma_k)^{1+q(\\mu-1/2)}}\n$$\nIf 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$.\n\nWe 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.\n\n---\n> Does the dynamic robustness result still hold when considering the average-iterate behavior of FTRL dynamics?\n\nTheorems 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)$.\n\n---\n> Is it possible to define robustness for mix Nash equilibrium?\n\nIn the context of finite games, mixed Nash equilibria are interior, so they are not robust.\n\n\n---\nThank you again for your time and input—we look forward to further constructive exchanges during the discussion phase.\n\nKind regards,\n\nThe authors\n\n---\n### References\n- 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.\n- T. Lattimore and C. Szepesvári, *Bandit Algorithms*. Cambridge, UK: Cambridge University Press, 2020.\n- S. Leonardos, W. Overman, I. Panageas, and G. Piliouras, \"Global convergence of multi-agent policy gradient in Markov potential games,\" ICLR 2022.\n- D. Monderer and L. S. Shapley, “*Potential games*,” Games and Economic Behavior, 14(1):124 – 143, 1996.\n- Y. Nesterov, “Primal-dual subgradient methods for convex problems,” Mathematical Programming, vol. 120, no. 1, pp. 221–259, 2009.\n- F. Orabona and D. Pál, “*Scale-free online learning*,” Theoretical Computer Science, vol. 716, pp. 50–69, 2018.\n- B. T. Polyak, *Introduction to Optimization*. New York, NY, USA: Optimization Software, 1987.\n- R. W. Rosenthal, “*A class of games possessing pure-strategy Nash equilibria*,” International Journal of Game Theory, vol. 2, pp. 65–67, 1973."}, {"review_id": "X5926fHLU9", "reviewer": "Reviewer_HTpi", "summary": "This paper looks at the dynamics of the Follow The Regularized Leader (FTRL) algorithm in continuous games of finite dimension, in both deterministic and stochastic settings. It relies on an assumption of a robust equilibrium in order to ensure convergence under any regularizer. Especially, the rate is characterized depending on the regularizer, and FTRL is shown not to converge to non-equilibrium. The paper is purely theoretical.", "questions": "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.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The paper is well written and very clear.\n\n- The statements are precise and rigorous. All properties are proven properly.\n\nWeakness:\n\n- 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.\n\nTo support the idea of the restrictiveness of the assumption, in the specific case of mixed policies of a finite games, robustness is (if I'm not mistaken) equivalent to being a strict pure Nash equilibrium.", "was_revised": true, "final_justification": "While I still think the assumption of robustness is quite strong, the authors argued it is a common occurence in many games, and I may have misunderstood some techinicalities of the paper that made results appear simpler than they are.", "rebuttal": "Dear reviewer,\n\nThank you for your time and input. We reply to your remarks and questions below:\n\n> 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.\n\nWe would like to clarify two points regarding this comment.\n\nFirst, 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.]\n\nBy 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).\n\nSecond, 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.\n\nTo 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\n$$\nx_{n+1} = \\Pi(x_n + \\gamma \\hat v_n)\n\\qquad\n\\textrm{(SGA)}\n$$\nwhere $\\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$.\n\nIn 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$.\n\nThis 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.\n\nFinally, we should point out that many well-studied classes of games admit robust equilibria, for example:\n1. **Atomic, non-splittable routing games** with arbitrary (increasing) cost functions\n2. **Markov potential games** in the context of multi-agent reinforcement learning\n3. **Cournot competitions** for agents with no (or small) price-setting power.\n\nWe 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$\n\n---\n#### $^1$ *Justification of the existence of robust equilibria in the classes mentioned above:*\n\n1. *For atomic, non-splittable routing games:* see Rosenthal (1973) and note that strict Nash equilibria of finite games are robust.\n2. *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.\n3. *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.\n\n---\n> 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.\n\nIn 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.\n\nTogether 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.\n\n---\nThank you again for your time and input—we are looking forward to further constructive exchanges during the rebuttal phase.\n\nKind regards,\n\nThe authors \n\n---\n### References\n- S. Leonardos, W. Overman, I. Panageas, and G. Piliouras, \"Global convergence of multi-agent policy gradient in Markov potential games,\" ICLR 2022.\n- D. Monderer and L. S. Shapley, “*Potential games*,” Games and Economic Behavior, 14(1):124 – 143, 1996.\n- B. T. Polyak, *Introduction to Optimization.* New York, NY, USA: Optimization Software, 1987.\n- R. W. Rosenthal, “*A class of games possessing pure-strategy Nash equilibria*,” International Journal of Game Theory, vol. 2, pp. 65–67, 1973."}, {"review_id": "KR4MCUbcdX", "reviewer": "Reviewer_ezQj", "summary": "This paper focuses on continuous games which exhibit some level of uncertainty and the stability of equilibria in these games. The authors provide the concept of a robust equilibrium to define and describe equilibria that remain valid under sufficiently small perturbations of the payoff structure. The paper provides several theoretical results, such as a geometric characterization of robust equilibria and the relation of strategic and dynamic robustness with respect to FTRL dynamics.", "questions": "1. Would it be possible to include an actual simulation of the examples?\n2. How could the theoretical findings be leveraged to advance practical learning applications?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Overall, I enjoyed reading the paper and did not spot any major weaknesses. Here are the details:\n\nStrengths:\n- The paper has a clear structure and extensively discusses related work which enables readers to access the contributions of the present work\n- The authors consistently discuss limitations and provide context for their theoretical results\n- The results seem to close a gap in the existing literature\n- The theoretical results appear rigorous and assumptions are clearly stated\n- Examples complement the theory\n\nSuggestions:\n- 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\n- I think there is a typo between lines 139 and 140: \"for all $x_i$\" instead of \"for all $x$\"", "was_revised": true, "final_justification": "The authors did address my remaining questions adequately. Since my initial review and the evaluation of the other reviewers is mostly positive, I remain confident that the paper should be accepted for publication.", "rebuttal": "Dear reviewer,\n\nThank you for your time, constructive input and strong positive evaluation! We reply to your remarks and questions below:\n\n---\n> 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.\n\nThe 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).\n\n---\n> How could the theoretical findings be leveraged to advance practical learning applications?\n\nSome practical learning applications where the theoretical findings can be leveraged are\n1. **Markov potential games** in the context of multi-agent reinforcement learning.\n2. **Atomic, non-splittable routing games** with arbitrary (increasing) cost functions.\n3. **Cournot competitions** for agents with no (or small) price-setting power; etc.\nThe 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.\n\n---\n#### $^1$ *Justification of the existence of robust equilibria in the classes mentioned above:*\n\n1. *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.\n2. *For atomic, non-splittable routing games:* see Rosenthal (1973) and note that strict Nash equilibria of finite games are robust.\n3. *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.\n\n---\n### References\n- S. Leonardos, W. Overman, I. Panageas, and G. Piliouras, \"Global convergence of multi-agent policy gradient in Markov potential games,\" ICLR 2022.\n- D. Monderer and L. S. Shapley, “*Potential games*,” Games and Economic Behavior, 14(1):124 – 143, 1996.\n- B. T. Polyak, *Introduction to Optimization.* New York, NY, USA: Optimization Software, 1987.\n- R. W. Rosenthal, “*A class of games possessing pure-strategy Nash equilibria*,” International Journal of Game Theory, vol. 2, pp. 65–67, 1973.\n\n> I think there is a typo between lines 139 and 140: \"for all $x_i$\" instead of \"for all $x$\"\n\nYou are right, thanks for the catch!\n\n---\nThank 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!\n\nKind regards,\n\nThe authors"}]

Author rebuttal:

Meta-review: This paper studies the robustness of Nash equilibrium in continuous games, under both strategic and dynamic uncertainty. A robust Nash equilibrium of a game is the one that remains an equilibrium even the payoff functions of the game changes arbitrarily by a small amount. The paper carefully justifies the distance notion of closeness between two games when they quantify changes in the payoff functions. They provide a geometric interpretation of the robust equilibrium. They then establish the results for dynamic robustness -- aiming at answering the question: Which equilibria remains attracting the dynamics of FTRL under small perturbations to the initialization of the dynamic's initial points. They establish that any strategically robust equilibrium has the property of robust dynamics. 

Strengths. A very well written paper with a good trace of history about the quest for defining meaningful equilibrium, making the studied problem significant, a fairly complete characterization of robustness and the relationship between strategic robustness and dynamic robustness. 

Weaknesses. No major concerns from the reviews as they are well addressed by the authors. For me, the only concern is that, for dynamic robustness, it requires that the initial point is initialized within a neighborhood of the convergent point, which makes the dynamic robustness less appealing, as my first impression is that the perturbation to the initial point is within a neighborhood centered at any point, though technically I am not sure if that result is possible. 

Reasons for accept. See Strengths 

During the rebuttal and discussion, the paper received positive evaluations. This is evident by that two reviewers have increased their scores after the discussion.
Decision: Accept (poster)