The Equivalence of Dynamic and Strategic Stability under Regularized Learning in Games
Authors: Victor Boone
Panayotis Mertikopoulos
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Regularized learning
dynamic stability
strategic stability
Nash equilibrium

Abstract: In this paper, we examine the long-run behavior of regularized, no-regret learning in finite N-player games. A well-known result in the field states that the empirical frequencies of play under no-regret learning converge to the game’s set of coarse correlated equilibria; however, our understanding of how the players' _actual strategies_ evolve over time is much more limited – and, in many cases, non-existent. This issue is exacerbated further by a series of recent results showing that _only_ strict Nash equilibria are stable and attracting under regularized learning, thus making the relation between learning and _pointwise_ solution concepts particularly elusive. In lieu of this, we take a more general approach and instead seek to characterize the _setwise_ rationality properties of the players' day-to-day trajectory of play. To do so, we focus on one of the most stringent criteria of setwise strategic stability, namely that any unilateral deviation from the set in question incurs a cost to the deviator – a property known as _closedness under better replies_ (club). In so doing, we obtain a remarkable equivalence between strategic and dynamic stability: _a product of pure strategies is closed under better replies if and only if its span is stable and attracting under regularized learning._ In addition, we estimate the rate of convergence to such sets, and we show that methods based on entropic regularization (like the exponential weights algorithm) converge at a geometric rate, while projection-based methods converge within a finite number of iterations, even with bandit, payoff-based feedback.

The Equivalence of Dynamic and Strategic Stability under Regularized Learning in Games
Victor Boone
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France [victor. www.oooooonnnnoeoo panayotis m Qunii muniv-grenobl--e alpes. fr
Abstract
In this paper, we examine the long-run behavior of regularized, no-regret learning in finite games. well-known result in the field states that the empirical frequencies of no-regret play converge to the game's set of coarse correlated equilibria; however, our understanding of how the players' actual strategies evolve over time is much more limited and, in many cases, non-existent. This issue is exacerbated by series of recent results showing that only strict Nash equilibria are stable and attracting under regularized learning, thus making the relation between learning and pointwise solution concepts particularly elusive. lieu of this, we take a more general approach and instead seek to characterize the setwise rationality properties of the players' day-to-day play. To that end, we focus on one of the most stringent criteria of setwise strategic stability, namely that any unilateral deviation from the set question incurs a cost to the deviator property known as closedness under better replies (club). In so doing, we obtain a far- far-reaching equivalence between strategic and dynamic stability: a product of pure sirategies is closed under better replies if and only if its spun is sluble and attracting under regularized learning. addition, we estimate the rate of convergence to such sets, and we show that methods based entropic regularization (like the exponential weights algorithm) converge at geometric rate, while projection-bus based methods converge within a finite number of iterations, even with bandit, payoff-basee baseed feedback.
Introduction
Background. The question of whether players can learn to emulate rational behavior through repeated interactions has been one of the mainstays of non-cooperative game theory, and it has recently gained increased momentum owing to surge of breakthrough applications to machine learning and data science, from online ad auctions to multi-agent reinforcement learning. Informally, this question can be stated as follows:
If each player follows an iterative procedure aiming increase their individual payoff. does the players' long-run behavior converge to rationally admissible state?
natural setting for studying this question is to assume that each player is following a no-regret algorithm, i.e., policy which is asymptotically as good against given sequence of payoff' functions as the best fixed strategy in hindsight. In this framework, the link between learning and rationality provided by folk result which states that, under no-regret learning, the empirical frequency of play converges to the game's 's set of coarse correlated equilibria (CCE) also known as the game's 's Hannan set [26]. This result has been of seminal importance to the field because no-regret play can be achieved via wide class of "regularized learning" policies, as exemplified by the "follow- the-regularize--ledde
(FTRL) family of algorithms [45, 46] and its variants - optimistic methods [15, 28, 41, 42, 47], HEDGE/ EXP3 [4, 6, 10, 11], implicitly normalized forecasters [1, 3], etc.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

All these policies have (at least) one thing in common: they seek to provide the tightest possible guarantees for each player's 's individual regret, thus accelerating convergence to the game's Hannan set. As such, in games where the marginalization of coarse correlated equilibria coincides with the game's Nash equilibria (like two-player zero-sum games), we obtain a positive equilibrium convergence guarantee: the long-run empirical frequency of play evolves "as if" the players were rational to begin with-i.. as if they had full knowledge of the game, common knowledge of rationality, the ability to communicate this knowledge, etc.
On the other hand, in many other contexts, the marginals of connsssttt correlated strategies may fail even the weakest axioms of rational behavior and rationalizability (such as the elimination of strictly dominated strategies). In particular, well-known example of Viossat & Zapechelnyuk [49] (which we discuss in detail in Section 4) shows that it is possible to have negative regret for all time, but still employ only strictly dominated strategies throughout the entire horizon of play.
The reason for this disconnect is that no-regret play has significant predictive power for the empirical frequency of play - that is, the long-run empirical distribution of pure strategy profiles- but much less so for the players' day-to-day sequence of play - i.e., the evolution of the players' actual mixed strategies over time. In particular, even when the marginalization of the Hannan set Nash, the actual trajectory of play may- and, in fact, often does- - diverge away from the game's 's set of equilibria [16, 24, 34-36] or exhibits chaotic, unpredictable oscillations [12, 38]. Thus, especially in the context of regularized learning where players learn independently from one another, with no common correlating device- the blanket guarantee of no-regret play may quickly become irrelevant, and even misleading, providing the veneer of rational behavior but not the substance.
Motivated by the above, our paper seeks to understand the rationality properties of the players' actual sequence of play under regularized learning, as encoded by the following question:
Which sets of mixed strategies are stable and attracting under regularized learning? Are these sets robust to strategic deviations? And, if so, is the converse also true?
Our contributions in the context of related work. This question has attracted significant interest in the literature, especially in its pointwise version, namely: Which mixed strategy profiles are stable and attracting under regularized learning? Are the dynamics' stable states robust to unilateral deviations? And, if so, are these the only stable states of regularized learning?
In the related setting of population games, the answer to this question is sometimes referred to the "folk theorem of cvolutionary game theory" [14, 27, 51]. Somewhat informally, this theorem states that, under the replicator dynamics (the continuous-time analogue of the exponential/ multiplicative weights algorithm, itself an archetypal regularized learning method), the following is true for all games: only Nash equilibria are (Lyapunov) stable, and state is stable and attracting under the replicator dynamics if and only it is a strict Nash equilibrium of the underlying game [27, 51].'
In the context of regularized learning, [13, 20, 33] showed that a similar equivalence holds for the dynamics of FTRL in continuous time: a state is stable and attracting under the FTRI. dynamics if and only if it is strict Nash equilibrium. Subsequently, Giannou et al. [22, 23] extended this cquivalence to an entire class of regularized learning schemes, with different types of feedback and/or update structures from optimistic methods to algorithms run with bandit, payoff-based information.
In all these cases, the same principle emerges: under regularized learning, a state is asymptotically stable and attracting if and only if it is strict Nash equilibrium.
This is an important pointwise prediction but does not cover cases where regularized learning algorithms do not converge to a point, but to sel (such as a limit cycle or other non-trivial attractor). In this case, the very definition of strategic stability is an intricate affair, and there are several definitions that come into play [7, 17, 21, 43]. The first such notion that we consider is that of "resilience to strategic deviations", namely that every unilateral deviation from the set under study is deterred by some other element thereof. Our first contribution in this direction is universal guarantee to the effect that, with probability 1, in any game, and from any initial condition, the long-run limit of any regularized learning algorithm is resilient set.
This result is significant in its universality, but the notion of resilience is not sufficiently strong to disallow irrational behavior and, in fact, it is subject to similar shortcomings as Hannan consistency.
Strictness here means that each player has unique best response at equilibrium.

---

To account for this deficiency, we turn to much more stringent criterion of setwise strategic stability, that of closedness under better replies (club). This notion, originally due to Ritzberger & Weibull [43], states that any deviation from a product of pure strategies is costly, and it is one of the strictest setwise refinements in game theory. particular, it reñines the notion of closedness under rational behavior (curb) [7], and it satisfies all the seminal strategic stability requirements of Kohlberg & Mertens [30], including robustness to strategic payoff perturbations."
In this general context, we show that regularized learning enjoys striking relation with club sets: A product of pure strategies is closed under better replies if and only if its span is stable and attracting under regularized learning. In fact, we show that this equivalence can be refined to sets that are minimally closed under better replies (in the sense that they do not contain strictly smaller closed under better replies (club) set): product of puer strategies is minimally club (m-club) if and only if its span is irreducibly stable and attracting (in that it does not contain a smaller asymptotically stable span of strategies). Finally, we also estimate the rate of convergence to club sets, and we establish convergence at a geometric rate for entropically regularized methods like HEDGE and EXP3 and in a finite number of iterations under projection-based methods.
In light of the above, our results can be seen both as far-reaching setwise generalization of the folk theorem of evolutionary game theory, as well as a bona fide algorithmic analogue of a precursor result for the replicator dynamics, originally due to Ritzberger& Weibull [43]. Importantly, our analysis covers several different update structures "vanilla" regularized methods, but also their optimistic variants as well as wide range of information models from full payoff information bandit, myyoff-based feedback.
2 Preliminaries
We start by recalling some basics from game theory, roughly following the classical treatise of Fudenberg & Tirole [21]. First, finite game in normal form consists of (i) finite of players i E N = (1,.... .N; (ii) a finite set of actions - or pure strategies - -A; per player i E N and (iil) an ensemble of payoff functions u;: [1, Aj R, each determining the reward (a)))) of player i e in a given action profile a = (0)..... .'N). Collectively, we will write A = [T A, for the game's action space and I T(N, A. u) for the game with primitives as above.
During play, each player i E A may randomize their choice of action by playing mixed strategy, ie., a probability distribution X; X, = A(AA) over A, that selects a; AA with probability Xia. To lighten notation, we identify a E A, with the mixed strategy that assigns all weight to aj (thus justifying the terminology "pure strategies"). Then, writing x (x))ee for the players' strategy profile and X' 11; X; for the game's 's strategy space, the players' payoff functions may be extended to all of X by setting
u,(x) = [[))) -..EAA u;(a)
where, in a slight abuse of notation, we write Xa for the joint probability of playing E A under ie., Xa = [l Ma This randomized framework will be referred to as the mixed extension of I and will denote it by A(T).
For concision, we will also write (x;;,-;)) = (x1, Ny......,....................... i plays X; E X; against the strategy profile x-; E [l X, of all other players (and likewise for pure strategies). In this notation, we also define each player's 's mixed payoff vector as
for the strategy profile where player
(x(x) = (1)(a)x)))))a
(2)
so the payoff to player E N under X becomes
(x)x) E,,A,, u;(a;x=)) Xim = (x))
Moving forward, the best-reseonse correspondence of player E N is defined the set-valued mapping bry: X' = Xi given by
bx, = arg max (x/:xx=) for all x X.
(4)
Extending this over all players, we will write br = II br, for the product correspondence br(x) br (x) x ... x br (x), and we will say that x E X' is Nash equilibrium (NE) if x" E br(x").
Roughly speaking, robustness to strategic payoff perturbations means that the set under study remains stable even if the payoff' of the game are subject small but possibly adversarial perturbations.
3

---

Equivalently, given that ui (x/:x-1) is linear in x/C, we conclude that x² is a Nash equilibrium if and only if
u;(x') 2 u;(ag;x1) for all az A; and all i e ..
(NE)
As a final point of note, ifxx is a Nash equilibrium where each player has a unique best response - that is, bx,(x") (x?) for all e - we will say that is strict because, in this case, Ut (xx") > (;(x,;;",,) for all x; * x, N. An immediate consequence of this is that strict equilibria are pure, i.e., each x is a pure strategy. Among Nash equilibria, strict equilibria robust" (in the sense that they remain invariant to small perturbations of the underlying game), so they play a particularly important role in game theory.
the only ones that are "structurally
3 Regularized learning in games
Throughout our paper, we will consider iterative decision processes that unfold as follows:
1. At each stage f 1,2, .... every participating agent selects an action.
Agents receive a reward determined by their chosen actions and their individual payoff functions.
3. Based on this reward (or other feedback), the agents update their strategies and the process repeats.
In this online setting, a crucial requirement is the minimization of the players' regret, i.e., the difference between player's cumulative payoff over time and the player's best possible strategy in hindsight. Formally, if the players' actions at each epoch = 1, ....... are collectively drawn by the probability distribution E E A(A), the regret of each player i E N is defined as
Reg, (T) ma 3(=1_u(00 (2(2)),
(5)
and we will say that player has no regrel if (7) o
One of the most widely used policies to achieve no-regret play is the so-called follow-the-regularie leader" (FTRL) family of algorithms and its variants [45,46]. To motivate the analysis to come, we begin with an archetypal FTRL method, the exponential multiplicaative weights algorithm, also known as HEDGE [4, 11].
3.1. A gentle start. We begin our discussion with a "stimulus-response" approach in the spirit of Erev & Roth [19]: First, at each stage 1 1, 1. every player i e N employs mixed strategy Xx, E X, to select an action at, E A,. Subsequently, to measure the performance of their pure strategies over time, each player further maintains a score variable which is updated recursively as
(6) In words, your. simply tracks the cumulative payoff of the pure strategy 0; E A: up to time I (inclusive). As such, this score can be treated as propensity to play a given pure strategy at any given stage: the strategies a; E A; with the highest propensity scores yia, should be played with higher probability at stage ++1
yla, yta,, u, "aaajaa-,)) for all 0; E A,
The most widely used instantiation of this stimulus-response mechanism is the logit choice rule
A(yy) )
E,,,A, exp(yia,)
which means that each player selects an action with probability that is exponentially proportional to its score. In this way. obtain the exponential/multipiicii
weights HEDGE algorithm (HEdge)
yi.++1 = yi., (a,)
xi,++1 = Ax(.i.+11)
dii,+1 ~ Xi,+1
where y, is the algorithm's "learning rate". For an appetizer to the literature on (HEDGR), see [2, 10, 11, 45] and references therein.
The rest of the methods we discuss below will vary some - or even all - of the components of (HEDGE): the information used to update the players' propensity scores, the way that propensity scores are mapped to mixed strategies, and/or even the way that pure actions are selected. However, all of the methods under study will be characterized by the same "stimulus- responsse reinforcement mechanism: actions that seem to be performing better over time are employed with higher probability, up to some "regularization" that incentivizes exploration of underperforming actions.
of course, updating these scores requires the knowledge of the "what if" pure payoff' (a(ayta11,) at each stage f, but assume for the moment that this information is available (we will relax this assumption later on).

---

3.2. The regularized learning template. In the rest of our paper, we will work with an abstract regularized learning (RL) template which builds on the same responns principle as (HEDGE), while allowing us to simultaneously consider different types of feedback, strategy sampling policies, update structures, etc. To lighten notation below, we will drop the player index E N when the meaning can be inferred from the context; also, to stress the distinction between "strategy-like" and "payotf-like" variables, we will write throughout ) == RA and y = π. J for the game's "payoff space", in direct analogy to X; and X' ΠT; X, for the game's s strategy space.
With all this in hand, consider the following general class of regularized learning methods:
Aggregate payoff information (stimulus):
Y,,++1 Y1, +,
(RL)
Update choice probabilities (response):
X1,++1 2:
In tune with (HEDGE), the various elements of (RI.) are defined as follows:
1. X1, E X denotes the mixed strategy of player i at time 1 = 1,2,...
2. Vú,, E 34 is "score vector" that measures the performance of the player's actions over time.
3. Q:: 3/ - X; is "regularized choice map" that maps score vectors to choice probabilities.
4. 0r is a surrogate// parngaat//appoximmaiion of the mixed payoff vector (X,)) of player i at time I.
5. Y/ > is a step-size sensitivity parameter of the form y, x 1/f5x for some by E [0. 1].
In words, at each stage of the process, every player E N observes or otherwise estimates proxy or of their individual payoff vector; subsequently, players augment their actions' scores based on this information, they select mixed strategy via the regularized choice map Q, and the process repeats. To streamline our presentation, we discuss in detail the precise definition of 0 and Q in Sections 3.3 and 3.4 below, and we present a series of examples of (RL) in Scction 3.5 right after.
3.3. Aggregating payoff information. As noted above, the main idea of regularized learning is to track the players' payoff vector u(x).. Importantly, there are several different modeling choices that can be made here: players may have direct access to their payoff vectors (in the full information setting), or some noisy approximation obtained by an inner randomization of the algorithm (e.g.. when they receive information on their pure actions); they may have recreate their payoff' vectors altogether (as in the bandit setting), or their estimates may be based on a strategy other than the one they actually played (as in the case of optimistic algorithms).
In all cases, we will represent the surrogate payoff vector 0, as
& D( (2) U, + b,
(8)
- where b, Eié, - (X,) and U, = 8, - E 1 respectively denote the offset and the random error of 0, relative to o( X,) To streamline our presentation, will also assume that ||b, O(1 (1/ and ||U,|| | = (r for some l, fo 2 0; we discuss the specifics of these bounds later in the paper.
3.4. From scores to strategies. Regarding the "roorssttosstrateiies" step of (RL), we will follow the classical approach of Shalev-Shwariz [45] and assume that each player is employing regularized choice map of the general form
ei(y:) arg max x (y)..;)) hxx)))
for all y; D/-
In the above, the regularizer : X; + R acts as a penalty that smooths out the "hard" argmax correspondence y arg max x, x;),,)). Accordingly, instead of following the "leader" (i.e., playing the strategy with the highest propensity score), players follow the "regularized leader" - that is, they allow for certain degree of uncertainty in their choice of strategy [10, 33, 45, 46).
max,,xx;
To case notation, we will work with kernelized regularizers of the form h, = Em ((xia)) ) for some continuous function 0: [0, 1] - R with inf (z) O. We will also say that the players' regularizers are steep if lim--o- ('(z) = -o,, and non-steep otherwise.
Example 3.1. A standard family of kernelized regularizers is given by 6(z) = / 1)] for E (0, 1) U (1,2) and 0(z) = log z for p = 1 [10, 31, 33, 53]. This family includes:
For p = 2, the quadratic regularizer 8(z) = z2/2, which yields the Euclidean projection map 2(()) II; (yr) arg min,, xx 11y, - -x1l2-
(10)
5

---

For p 1, the entropic regularizer 0(z) = z z, which yields the logit choice map (7).
For p = 1/2, the fractional power regularizer ((z) =4y² that underlies the T
algorithm of [1, 53] (see also Section 3.5 below).
3.5. Specific algorithms. We now proceed to discuss some archetypal examples of (RL).
Algorithm 1 (Follow the regularized leader). The standard heallo--he--rgulaiieeeeeeeee method of Shalev-Shwartz & Singer [46] is obtained when players observe their full payoff vectors, that is, B 0; (X,). In this case, (RL) boils down to the deterministic update rule
(FTRL)
Y1 Y1,5 (X+)
X1,+11 Qi()..41)
or, more explicitly
X1,++1 arg maxx; X
Σ (x; ( (xx))
(FTRL)
For a detailed discussion of (FTRL), see [10, 31, 45]. We only note here that, special case, when (FTRL) is run with the logit choice setup of Eq. (7), a standard calculation yields the exponen- nall/uuliil weights (HEDGE) [4, 32, 45, 50].
Algorithm 2 (Optimistic FTRL). A notable variant of FTRL- originally due to Popov [40] and subsequently popularized by Rakhlin & Sridharan [41, 42] - is the so-called optimistic FTRL method. This scheme employs an "optimistic" correction intended to anticipate future steps, and it updates as
YL Yı,, + yı (2,; D; (X,-1)]
(Opt-FTRL)
with X,, = (Y,r). As a special case. if (Opt-FTRL) is run with the logit choice map (7). we obtain the familiar update rule known as optimistic multiplicative weights (OMW) [15, 41, 42, 47].
Compared to (FTRL), the gain vector 6, 2n( (X) - -1) of (Opt-FTRI) has offset b, = =(X,) v(X,-1) relative to u (())). Thus, even though (Opt-FTRL.) assumes full access to the players' mixed payoff vectors, uses this information differently than (FTRL): in particular, the offset of (Opt-FTRL) is non-zero by design, not because of some systematic error in the payoff measurement process.
Now, up to this point, we have not detailed how players might observe their full, mixed payoff vectors. This assumption simplifies the analysis immensely, but it is not realistic in applications to e.g., online advertising and network science, where players may only be able to observe their realized payoffs, and have no information about the strategies of other players actions they did not play. On that account, we describe below a range of payoff- based policies where players estimate their counterfactual, "what-if" payoffs indirectly.
The most common way to achieve this is via the importance-weighted estimator
1(à; = (,(ā)) for all a E A,i
IWE (x)
(IWE)
Xia;
where x X' is the players' strategy profile, and à e A is drawn according to This estimator is at the heart of the online learning literature [10, 11, 31, 45] and it leads to the following methods:
Algorithm 3 (Bandit FTRL). Plugging (IWE) directly into (RL.) yields the bandit FTRL policy
Yi.++ Yr,, y, (&E) X1.+1 = (Ki.+))
(B-FTRL)
where (IWE) is sampled at the mixed strategy profile
8 = (1- Xi, + +8, unif
(11)
for some "explicit exploration" parameter 6, x 1/f6a, 6g > O, which specifies the mix between Xt,,
and the uniform distribution unif on Ar. As we discuss in the sequel, this combination of (IWE)
with the explicit exploration mechanism (11) means that the surrogate payoff vector é IWE(X,)
used to update (B-FTRL) has offset and noise bounded respectively as b, ((6)) and U, = (116,).
Two special cases of (B- (B-FTRL) that have attracted significant attention in the literature are:
1.
The exponential weights algorithm for exploration and exploitation (EXP3) [6. 11, 31], obtained by running (B-FTRL) with the logit choice map (7).

---

2. The Tsallis implicitly normalized forecaster (TSALLIS-ING [1, 3, 53] that was proposed as more efficient alternative EXP3, and which updates as
1 arg max xx (K.,, + E.,EA, VXia.
(TSALLIS-INE -NNF)
i.e., as (B-FTRI)) with the fractional power regularizer 0(2) = -4 of Example 3.1.
For illustration purposes, we provide some more examples of (RL) in Appendix B.
4 First results: resilience to strategic deviations
We are in position begin our analysis of the rationality properties of the players' long- run behavior under (RL). To that end, we should first note that no-regret play may still lead to counterintuitive and highly non-rationalizable outcomes, e.g., with all players selecting dominated strategies for all time. The example below is adapted from Viossat & Zapecheinyuk [49].
Example 4.1. Consider the 4 symmetric 2- 2-player game with payoff bimatrix
A
B
C
D
A
(I.
(1,2/3)
(0.0)
(0.-1/3)
B
12/
(2/3.2/3)
(-1/3.0)
(-1/3,-1/3)
C
(0,0)
(0.-1/3)
(1,
(1,2/3)
D
(-1/3,0)
(-1/3.-1/3)
(2/3,1)
(2/3.2/3)
In this game, B and D are strictly dominated for both players by their stronger "twins" (A and C respectively). However, it is easy to check that if both players choose between (B, B) and DD, with probability 1/2 each, the resulting distribution of play E A(AA satisfies u;(a;; z-1) - 4;(2) - -1/6 for all 0; (A, B, C, D). 2. As result, the players' regret under 2, negative, even though both players play strietly dominated strategies at all times.
The example above shows unequivocally that
No-regret play does not suffice to exclude non-rationalizable outcomes.
In addition, Example 4.1 also shows that predictions based on correlated play are not always appropriate for describing the players' behavior under (RL): the end-state of any regularized learning algorithm will be a closed connected set of mixed strategies, so it is not possible to play only (B, B) or (D, D) in the long run. We are thus led to the following natural questions: What are the rationality properties of long-run play under (RL)? Is the players' behavior robust to strategic deviations?
To study these questions formally, we will focus on the limit set L(X) of X, under (RL), viz.
((X) = N, cl(X, 2 r) = ($ E X Xx, - X for some subsequence X of X,).
(12)
In words, L(X) is the set of limit points of X, or, equivalently, the smallest subset of X' to which X, converges. Clearly, the simplest instance of limit set is when L(X) is singleton, i.e., when X, converges to a point. This case has attracted significant interest in the literature: for example, L(X) (x') then, for certain special cases of (RL), it is known that x is Nash equilibrium of I' [34]. However, beyond this relatively simple regime, the structure of the limit sets of (RL) could be arbitrarily complicated and their rationality properties
well-understood.
With this in mind, as a first attempt to study whether the long-run behavior of (RL) is "robust to strategic deviations", we will consider the following notion of resilience to strategic deviations:
Definition 1. A closed subset S of X' is resilient to strategic deviations - or simply resilient - if, for every deviation x; X of every player i E N, we have
u7 ux(x") 2 u; xx;"x",, for some x E S.
(13)
Informally, S is resilient if every unilateral deviation from S is deterred by some (possibly different) element thereof. In particular, S a singleton, we immediately recover the definition of a Nash equilibrium; beyond this case however, other examples include the set of undominated strategies of game, the support face of the equílibria of two-player zero-sum games, etc. Importantly, as we show below, the limit sets of (RL) are resilient in all games:
7

---

Theorem 1. Let X, = 1,2...... be the sequence of play generated by (RL) with step-size gain parameters ly or and E > 0. Then, with probability 1, the limit set L(X) of X, resilient.
Proof sketch. The proof of Theorem boils down to two interleaved arguments that we detail in Appendix C. The first hinges on showing that, if IP (X)()) = S) > 0 for some non-random S E X, S must be resilient. This is argued by contradiction: if p: E X; is unilateral deviation violating Definition 1, we must also have lim inf, [u; (pr;) -X; > O with positive probability. However, the existence of a strategy that consistently outperforms X, runs contrary to the fact that strategies that (RL) selects against underperforning strategies. We make this intuition precise via an energy argument that leverages series of results from martingale limit theory (which is where the requirements for yt. b, and U, come in). Then, to get the stronger statement that the random set C(X) is resilient w.p.1, we show that the above remains true if pi is replaced by deviation qi which is close enough to p; and has rational entries. Since there is a countable number of such profiles, we can use union bound on an enumeration of the rationals to isolate a deviation witnessing the negation of Definition 1; our claim then follows by applying our argument for non-random sets.
Theorem 1 is our first universal guarantee for (RI.), some remarks are in order. First, we should point out that the requirements e, > 0 and 26 < by are a priori implicit because they depend on the off'set and magnitude statistics of the feedback sequence 6, However, in most learning algorithms, these quantities are under the explicit control of the players: for example, as we show in Appendix B, Algorithm 2 has l, Ey while, for Algorithm 3, we have 6, = l, C.. In this way, when instantiated to Algorithms 1-3 (and special cases thereof), Theorem 1 yields the following corollary:
Corollary 1. Suppose that Algorithms 1-3 are run with Ey E (0, 1] and, for Algorithm 3, lo (0, 22) Then, with probability 1, the limit set L(X) of X, is resilient.
Now, since Theorem I applies to all games, it would seem to provide a universally positive answer to whether (RL) is robsut to strategic deviations. However, this is not So: a direct calculation shows that the face of X that is spanned by the dominated strategies (B, B) and (D, D) of Example 4. is resilient, so Theorem 1 cannot exclude convergence to a set where dominated strategies survive. Thus, just like no-regret play, the notion of resilience does not suffice by itself to capture the idca of rational behavior. This is because, albeit natural, resilience is too lax to provide a meaningful link between robustness to unilateral deviations a game-theoretic requirement - and stability under regularized learning- dynamic requirement. We address this question in detail in the next section.
5 A characterization of strategic stability under regularized learning
Similar to the set of pure strategies that arise from no-regret play, the main limitation of resilience is that switched to a different strategy; in other words, resilience is not a self-enforcing barrier to deviations. In view of this, we will focus below much more stringent criterion of strategic stability, namely that any deviation from the set in question incurs a cost to the deviating agent.
deviation may be countered by action profile where the deviator also
Club sets. To make all this precise, define the better-reply correspondence of player e N as bxr,(x) = {x/ X, u, (x/:xx))) 2 (x)x))
(14)
and write btr HI btr; for the product correspondence btr(x) btr -.. x btr (x). [In words, btr, assigns to each x E X' those strategies of player that are (weakly) better against x than xy.] In addition, given product of pure strategies C IIE C, with C S Ai for all i E N, let S = ACC) denote the span of C, and let P(X)) denote the collection of all such sets. We then say that S P(X') is closed under better replies- club set for short- - if it closed under btr, i.c.. Str(S) C S; finally, S is said to be minimally club (m-club) if it does not admit proper club subset.
Of course, the entire strategy space X' is closed under better replies so, a priori, club sets could also contain dominated strategies and/ / or other non-rationalizable outcomes. By contrast, minimal club sets are much more rigid in their relation to rational behavior because any unilateral deviation from an m-club set is costly, and m-club sets are minimal in this regard. On that account, m-club sets can be seen as the closest setwise analogue to strict Nash equilibria.
This analogy is accentuated further by the following properties of m-club sets, all due to Ritzberger & Weibull [43] who introduced the concept:
8

---

1. Every game admits an m-club set; and if this set is a singleton, then it is a strict Nash equilibrium.
2. Any m-club set S is fixed under better replies, that is, btr( S (implying in turn that & cannot contain any dominated strategies, including iteratively dominated ones).
3. Any m-club set S contains an exsential equilibrium component, i.e., a component of Nash equilibria such that every small perturbation of the game admits nearby equilibrium; in addition, this component has full support on S, i.c., it employs all pure strategy profiles that lie in S.
Going back online learning setting, the above leads to the following natural set of questions:
Are club sets (minimal or not) stable under the dynamics of regularized learning? Are they attracting? And, if so, are they the only such sets?
Any answer to these questions- - positive or negative - would be an important step in delineating the relation between strategic stability (in the above sense) and dynamic stability under (RL). To that end, we start by formalizing some notions of dynamic stability that will be central in the sequel: Definition 2. Fix some subset S of X' and tolerance level 0. We then say that S is:
1. Stochastically stable if, for every neighborhood 4 of S in X', there exists neighborhood 21 of S such that
.) > e whenever X1 E Un. P(X, E ll for all = 1.2....)
(15)
2. Stochastically attracting if there exists neighborhood 24 of S such that P(lim,-os dist( x, S) = 0) 2 1 - whenever XI E U1.
(16)
Stochastically asymptotically stable if it is stochastically stable and attracting.
Irreducibly stable S is stochastically asymptotically stable and it does not admit strictly smaller stochastically asymptotically subset S' with supp(S') & supp(S).
With all this in hand, our main result below provides sharp characterization of strategic stability in the context of regularized learning:
Theorem 2. Fix some set S E PP(X) and suppose that (RL) is with steep regularizer and step-size/ gain parameters ey E [0. 1], 4 > O, and Ey < 1/2. Then:
stochastically asymptotically stable under (RL) if and only if is a club set. irreducibly stable under (RL) if and only if is an m-club set.
In addition, we also get the following convergence rate estimates for club sets:
Theorem 3. Let S P(X) be club sel, and let X,, 1....... be the sequence of play generated by (RL.) with parameters by E [0. 1], Eb > O, and for < 1/2. Then, for all e > 0, there exists an (open, unbounded) initialization domain D S y such that, with probability at least 1 E, we have
dist( X,, S) s C
whenever Y1 ED
(17)
where C,, C2 are constants (C, > O), and the rate function &p is given by u(z)= (0) if z > lim.-o- (2), and 4(2)= otherwise.
Specifically, if we instantiate Theorem to Algorithms 1-3, we get the explicit estimates:
Corollary 2. Suppose that Algorithms I-3 are with Ey E [0, 1] and, for Algorithm 3, to (0, Then, with notation as in Theorem 3, X, converges to S at a rate of
[1 - 2 1 Ysl+ (). C- exp(-cE, Ys)
if((z) = 22/12
# quadratic regularization
if (())) zlog
# entropic regularization
(18)
1/(c+ [1(c+2,
if(()) = -4VE # fractional regularization
for positive constants C.C > 0. In particular, the projection- based variants of Algorithms 1-3 converge to m-club sets in a finite number of steps.
Formally, component 2 of Nash equilibria of I is essential for all & O, there exists > such that any perturbation the payoff's by most produces Nash equilibrium that e-close X' [48]. This property known as "essentiality" - has a long history as one of the strictest setwise solution refinements in game theory; in particular, it satisfies all the seminal strategic stability requirements of Kohlberg & Mertens [30]. including robustness strategic payoff perturbations. For in in-depth discussion, Damme [48].

---

Pure Coordination
Courdination with Speciater
Matching Pennies with Twist
Manching Pensics with Outsile Option
Figure The long- ong-rrun behavior of EXP3 (Algorithm 3) in four representative 2 2 x games. In all cases, the dynamics converge to m-club sets, either strict equilibria themselves, or spanning an essential component of Nash equilibria. The details of the numerics and the games being played are provided in the appendix.
Proof sketch. The proof of Theorems and 3 is quite involved so we defer it to Appendix D. At high level, it hinges on constructing a family of "primal-dual" energy functions, one per pure deviation from the set S under study. If unilateral deviations from S incur a cost to the deviator (that is, if S is club), these energy functions can be "bundled together" produce a suitable Lyapunov-like function for S. In more detail, the minimization of cach individual energy function implies that the score variable Y, of (RL) diverges along an "astral direction" in the payoff space -i..e. it escapes to infinity along the interior of a certain convex cone of y 118]. Because this minimization occurs at infinity, the aggregation of offiets and random errors in (RL) affords some extra "wiggle room" in our martingale analysis, so we are able to show that X, @(Y,) remains close to S under much wider range of parameters compared to Theorem 1. Then, a series of convex analysis arguments in the spirit of [33] coupled with the definition of Q allows us to show that the escape of Y, along the intersection of all these cones implies convergence to S at the specified rate.
On the converse side, if an asymptotically stable set is not club, we can find a non-costly (and possibly profitable) deviation z from S which is selected against by (RL). However, this extinction runs contrary to the reinforcement of better replies under (RL), an argument which can be made precise by applying the martingale law of large numbers to (Y,, [25]. The irreducible stability of m-club sets then follows by invoking this criterion reductively for any potentially stable subset S of S.
Discussion and remarks. Theorems 2 and 3 are our main results linking dynamic and strategic stability, so we conclude with a series of remarks. First, we should note that Theorem 2 can be summed up as follows: a product of pure strategies is (minimally) closed under better replies if and only if its span is (irreducibly) stable under regularized learning. Importantly, this equivalence is based solely on the game's 's payoff data: it does not depend on the specific choices underlying (RL), including the choice map employed by each player, whether some players are using an optimistic adjustment or not, if they have access to their full payoff vectors, etc. As such, this equivalence provides a crisp operational criterion for identifying which pure strategy combinations ultimately persist under regularized learning and, via Theorem 3, how fast this identification takes place.
In this light, Theorem 2 essentially states that the only robust prediction that can be made for the outcome of a regularized learning process is (minimal) closedness under better replies. This interpretation has significant cutting power for the emergence of rational behavior. To begin, in terms of equilibrium play, it effortlessly implies that pure strategy profile is stochastically asymptotically stable under (RL) if and only if it is strict Nash equilibrium. A version of this equivalence was only recently proved in [20] and [22] (in continuous and discrete time respectively), so Theorem 2 can be seen as a far-reaching generalization of these recent results. More to the point, since every m-club set S contains an essential equilibrium component that is fully supported in S, Theorem 2 also provides an important link between dynamic and structural stability: if an equilibrium - or a component of equilibria - is not robust to perturbations of the underlying game, it cannot be robustly identified by a regularized learning process (and vice versa). This remark is of particular importance for extensive-form games as such games often have non-generie equilibrium components that cannot be treated otherwise by the existing theory.
Finally, we should stress that Theorems 2 and 3 guarantee convergence even with constant step-size. Together with the finite-time convergence guarantees of Corollary 2 for projection- -base methods, this feature is a testament to the robustness of club sets as, in the presence of uncertainty, convergence almost always requires vanishing step-size which can slow convergence down to a crawl. We find this robust convergence landscape particularly intriguing for future research the topic.
10

---

Acknowledgments and Disclosure of Funding
PM is also with the Archimedes Research Unit - Athena RC Department Mathematics, National & Kapodistrian University of Athens. This work has been partially supported by the French National Research Agency (ANR) in the framework of the "Investissements d' avvenr" program (ANR-15-
IDEX-02), the LabEx PERSYVAL (ANR-11 1-LABB-0025-00)) MIAI @ Grenoble Alpes (ANR-19- P3IA-0003), and project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0
funded by the European Union under the NextGeneration Program
References
[1] Ahernethy, J., Lec, C., and Tewari, A. Fighting handits with new kind of smoothness. In NIPS '15: Proceedings of the 29th International Conference Neural Information Processing Systems, 2015.
[2] Arora, S., Hazan, E., and Kale, The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8(1): 164, 2012.
[3] Audibert,J.-Y. J.-Y. and Bubeck, S. Regret bounds and minimax policies under partial monitoring, Journal of Machine Learning Research, 1 11:2635-2686, 2010.
[4] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. F. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings the 36th Annual Symposium Foundations of Computer Science, 1995.
[5] Auer, P., Casa-eC--aaae Bianchi, N., and Fischer, Finite-tims analysis of the multiarmed bandit problem. Machine Learning, 47:235 256, 2002.
[6] Auer, P., Cesa-Bianchi, N., Freund, Y.. and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM Journal Computing. 32(1):48-77, 2002.
[7] Basu, K. Weibull, W. Strategy subsets closed under rational behavior. Economics Letters, 36:
141-146, 1991.
[8] Bauschke, H. H., Borwein, J. M., and Combettes, P. L. Bregman monotone optimization algorithms. SIAM Journal on Control and Optimization, 42(2):596-636, 2003.
[9] Benaïm, M. Dynamics of stochastic approximation algorithms. In Azéma, J., Emery, M., Ledoux, M., and Yor, M. (eds.), Séminaire de Probabilités XXXIII, volume 1709 of Lecture Notes in Mathematics, pp. 1-68. Springer Berlin Heidelherg, 1999.
[10] Bubeck, S. and Cesa- Bianchi, N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[11] Desa-Bianchi. N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University Press, 2006. [12] Chotibut, T., Falniowski, F., Misiurewicz, M., and Piliouras, G. Family of chaotic maps from game theory. Dynamical Systems, 2020.
[13] Coucheney, P., Gaujal, B., and Mertikopoulos, P. Penalty-regulated dynamics and robust learning proce- dures in games. Mathematics of Operations Research, 40(3):61 August 2015.
[14] Cressman, R. Evolutionary Dynamics and Extensive Form Games. The MIT Press, 2003.
[15] Daskalakis, C. and Panageas, I. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In ITCS 19: Proceedings the 10th Conference on Innovations Theoretical Computer Science, 2019.
[16] Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, Training GANs with optimism. ICLR '1: Proceedings of the 2018 International Conference on Learning Representations, 2018.
[17] Demichelis, S. and Ritzberger, K. From evolutionary to strategic stability. Journal of Economic Theory. 113:51-75. 2003.
[18] Dudík, M.. Schapire, R. E., and Telgarsky, M. Convex analysis at infinity: An introduction to astral space. 2022.
https:/aaxiv.orr/ats/255....
[19] Frev, I. and Roth, A. F. Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria. American Economic Review, 88:848-881, 1998.
[20] Flokas, L., Vlatakis Gaaaiiiksaaaaakoiiis... E. V., Lianeas, T., Mertikopoulos, P., and Piliouras, G. No-regret learning and mixed Nash equilibria: They do not mix. In NeurlPS '20: Proceedings the 34th International Conference on Neural Information Processing Systems, 2020.
[21] Fudenberg, D. and Tirole, Game Theory. The MIT Press, 1991.
[22] Giannou, A., Vlatakis-Gkaragkommin Gkaragkounis, 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.

---

[23] Giannou, A., Vlatakis- Gkaragkounis. E. V., and Mertikopoulos, P. The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond. In NeurlPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
[24] Gidel, G., Berard, H., Vignoud, G., Vincent, P., and I Lccoste-Juleen, A variational inequality perspective on generative adversarial networks. In ICLR '19: Proceedings of the 2019 International Conference on Learning Representations, 2019.
[25] Hall, and Heyde, C. C. Martingale Limit Theory and Its Application. Probability and Mathematical Statistics. Academic Press, New York, 1980.
[26] Hannan, J. Approximation to Bayes risk in repeated play. Dresher, M., Tucker, A. W., and Wolfe, P. (cds.), Contributions to the Theory of Games, Volume III, volume 39 of Annals of Mathematics Studies, pp- 97-139. Princeton University Press, Princeton, NJ, 1957.
[27] Hotbauer, J. and Sigmund, K. Evolutionary game dynamics. Bulletin of the American Mathematical Society, 40(4):479- -19. July 2003.
[28] Hsich, Y-G., lutzeler, F., Malick, J., and Mettikopoulos, P. On the convergence of single-call stochastic extra-gradient methods. In NeurlPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Syxtems, pp. 6936-6946, 2019.
[29] Juditsky, A.. Nemirovski, A. S., and Tauvel. C. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 111):17-58, 2011.
[30] Kohlberg, and Mertens, J.-E, On the strategic stability of equilibria. Econometrica, 050
September 1986.
[31] Lattimore. T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, Cambridge, UK, 2020. [32] Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. Information and Computation, 108 (2):212-261, 1994.
[33] Mertikopoulos, and Sandholm. W. H. Learning in games via reinforcement and regularization, Mathe- matics of Operations Reseurch, 41(4):127711324 November 2016.
[34] Mertikopoulos, P. and Zhou, 7. Learning in games with continuous action sets and unknown payoff January 2019.
functions. Mathematical Programmning, 173((-2):4455-33
[35] Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G. Cycles in adversarial regularized learning. In SODA '18: Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms, 2018
[36] 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 Learning Representations, 2019.
[37] Nemirovski, A. S. Prox-methos with rate of convergence (1/rr) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concayy saddle point problems. SIAM Journal on Optimization, 15(1):229 251, 2004.
[38] Palaiopanos, G., Panageas, I., and Piliouras, G. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In NIPS '1: Proceedings of the 31 International Conference on Neural Information Processing Systems, 2017.
[39] Piliouras, G., Sim, R., and Skoulakis, S. Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu. https: / /awxiv..ivvva////// org/ abaa//a/111... 14737, 2021.
[40] Popov, L. D. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5)8455888, 1980.
[41] Rakhlin, A. and Sridharan, K. Online learning with predictable sequences. In COLT '13 Proceedings of the 26th Anmual Conference Learning Theory, 2013.
[42] Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. NIPS '13: Proceedings of the 27th International Conference on Neural Information Processing Systems, 2013.
[43] Ritzberger, K. and Weibull, J. W. Evolutionary selection in normal-form games. Econometricu, 63(6):
1371-99, November 1995.
[44] Rockafellar, T. and Wets, R. J. B. Variational Analysis, volume 317 of A Series of Comprehensive Studies in Mathematics. Springer-Verlas Berlin, 1998.
[45] Shalev-Shwartz, S. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2): 194, 2011.
[46] Shalev-Shward S. and Singer, Y. Convex repeated games and Fenchel duality. In NIPS' 06: Proceedings of the 19th Annual Conference on Neural Information Processing Systems, pp. 1265-1272. MIT Press, 2006.
[47] Syrgkanis. V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. In NIPS '15: Proceedings of the 29th International Conference on Neural Information Processing Systems. pp. 2989 2997, 2015.
12

---

[48] van Damme, E. Stubiiity and perfection of Nash equilibria. Springer- Verlag, Berlin, 1987.
Springer-Verlag, [49] Viossat, Y. and Zapechelnyuk, A. No-regret dynamics and fictitious play. Journal of Economic Theory. 148(2):825 842, March 2013.
[50] Vovk, V. G. Aggregating strategies. In COLT '90: Proceedings of the 3rd Workshop on Computational Learning Theory, pp. 371-383, 1990.
[51] Weibull, J. W. Evolutionary Game Theory. MIT Press, Cambridge, MA, 1995.
[52] Zimmert, J. and Seldin, Y. An optimal algorithm for stochastic and adversarial bandits. In AISTATS '19:
Proceedings of 22nd International Conference on Artificial Intelligence and Statisties, 2019.
[53] Zimmert, J. and Seldin, Y. Tsallis-INF: An optimal algorithm for stochastic adversarial bandits. Journal of Machine Learning Research, 22(28):1-49 2021.
13

---

A Auxiliary results
In this appendix we collect some basic properties of the regularized choice maps and some results from probability theory that will be useful in the sequel.
A.1. Regularized choice maps and their properties. Thoughout this appendix, we will suppress the player index e N, and we will follow standard conventions in convex analysis [44] that treat as an extended-real-valee function I: V - R U {oo} with h(x) co for all x e V X. With this in x E X is defined as
mind, the subdifferential of
@h(x) = fy E y /xxx) 2 lx(x) + (y,x' -x for all x' E X).
(A.1)
where y' denotes here the algebraic dual V" of V. Accordingly, the domain of subdifferentiabiiiy of h is dom 0h (x dom h 0h Ø), and the convex conjugate of is defined
h" (y) max (y.x) h(x)
(A.2)
xEX
for all y Y. We then have the following basic results.
Lemma A.1. Let h be a regularizer on X, and let : y - be the induced choice map. Then:
1. Q is single-valued, and, for all X, y E V, have Q(y) y ah(x).
For all ri X, we have 0h(x) = {[(0 (x0))x=)+ M)EEA : IR.
For all E y, we have @ = (y)
4. Q is (1/K) -))iischiitz continuous with K == inf 6" (z). In particular, as a special case, the logit choice map A is 1 1-Lipschitz continuous in the (L', L²) pair of norms on y and X' respectively. 5. 1f yo' - -co for some a' * ax then (y) - O.
Remark. Some of the properties presented in Lemma A.1 are well known in the literature on regularized learning methods (see e.g.. [33] and references therein), but we provide proof of the entire lemma for completeness.
Proof of Lemma A.I. For the first property of Q, note that the maximum in (9) is attained for all y E y because h is wwwer-semicontinuon (Is.c.) and strongly convex. Furthermore, x solves (9) and only if y @h(x) O, i..., if and only if y 0h(x).
For our second claim, if x ri(2), the first-order stationarity conditions for the convex problem (9) that defines Q become
yu - 0' (xx)) =
for all E A,
(A.3)
because the inequality constraints x,, 2 0 are all inactive (recall that x E ri(2') by assumption). Now, by the first part of the theorem we have x = Q(y) if and only y E @h(x), so we conclude that âh(x) = (xxa) + p) f IR), as claimed.
For the fourth item, the expression @ Vh² is immediate consequence of Danskin's theorem, while the Lipschitz continuity of Q follows from standard results, see e.g., [44, Theorem 12.60(b)..
For our last claim, let y/ be sequence in y such that Yo,t yo'rr by descending to a subsequence if necessary, assume there exists some & > 0 such that Xa. 2 6 for all t. Then, by the defining relation Q(y) arg max (y. h(x)) of Q, we have:
and let = Qvx.). Then,
(yr,x,) h(xx)) (g.,x') h(x')
(A.4)
for all x' X. Therefore, taking x x, E(e,' ea), we readily obtain
E(ya.r - y 2 h(xx) h(x;) 2 min h max h
(A.5)
which contradicts our original assumption that yo. - yer + -o0 With compact, the above shows that x 0 for any limit point x" of i.e. (.(y,) 0.
The second collection of results concerns the Fenchel coupling, an energy function that was first introduced in [33, 34] and is defined follows:
F(p. 8) h(p) ht" (y) (y. p) for all p E X and y E y.
(A.6)
This coupling will play major role the proofs of Theorem 1, so we prove two of its most basic properties below.
14

---

Lemma A.2. For all E X and all y.y E V, we have:
a) F(p.y) 2 1 k (1Q()) - pll?.
(A.7a)
b) F(p.y) - F(p.)) (y' y. Q(y) -p) *2 lly yllco
(A.7b)
In particular, if (() we have
(2 h (y) min (y. (())) (2/K)llyll for all y y.
(A.8)
Proof of Lemma A.2. By the strong convexity of h relative to ||-I1 (cf. Lemma A.I), we have h(x) kly p x) s h(x (p-
1 th(p)) + (1 - ())(x) _ - 0)(xx pll..
(A.9)
leading to the bound
( - 1)|| p11 < h(p) h(x) (y. = F(p.y)
(A.10)
for all E (0, 1]. The bound (A.7a) then follows by letting - 0* in (A.10).
For our second claim, we have
F(p.y) h(p) + +1"())) - (v'.p)
h(p)) + 11 (g) + (y/ - Vn)(
2K 1ly y1l33 (1/.))
F(p.y) y) + (y' y. Q(y) p) 2K
yll
(A.11)
where the inequality in the second line follows from the fact that h² is (1/KK)ssrongg smooth [44, Theorem 12.60(e)].
A.2. Basic results from probability theory. We conclude this appendix with some useful results from probability theory that we will use freely throughout the sequel. For complete treatment, we refer the reader to Hall & Heyde [25].
Lemma A.3 AAzuma-Hoeffding inequality). Let M, E R, 1,2, be a martingale with [|M, - M S of (a.s.). Then, for all 17 > O, we have
1/2 p M (2 (n) In) E. o?) for all 1-1
(A.12)
Lemma A.4 (Kolmogorov's inequality). Let Z, R = 1.2...., be a martingale difference sequence that is bounded in L Then:
P max SSI
ΣE Ze
-
E s=l 2,) for all 0. /
(A.13)
Lemma A.5 (Doob's maximal inequality). Let R, 1,2, .... be martingale difference sequence that is bounded in I.P for some 2 1. Then
1
max
Zal SSt
IE [2, for all > 0. 8P
(A.14)
Lemma A.6 (Burkholder-De Davis Davis-Gundy inequality). Let Z, 1 1,2.... be martingale difference sequence in R". Then, for all p there exist constants Cp. Cp that depend only on p and are such that
Cp Σ 11Z
S
max 851
Σ 2
S
Cp E
Σ 12.1
(A.15)
Lemma A.7 (Robbins Siegmund)). Let F,, 1.2...., be filtration on complete probability space (Q, F.F,P)) P), and suppose that the sequences X,, L, and K, F.-mesurrble,, nonnegative, and such that
S X, L,) K, with probability 1. Then, X, converges to some random variable X with probability on the event
E[X (XX++IFF1 FF)
(A.16)
100 L, < and Eee K, < co).
15

---

B Specific algorithms and their properties
B.1. Known algorithms as special cases of (RL). To complement our analysis in the main part of our paper, we detail below how Algorithms 1-3 can be recast the general framework of (RL). To lighten notation, we will assume that b,, U, and 0, are respectively bounded as
||b, 1lee - B,
1l 0%
and 1| S M,
(B.1)
and we will set
G = max max (ax)
(B.2)
KeY acA
so we can take = B, in (B.1). We will also make free use of the fact that v is Lipschitz continuous on N, and we will write L for its Lipschitz modulus in the (L', _ pair of norms on X' and Y' respectively, viz.
[[(x')) o(x) L|Ix' - -xlli
for all x,x' X.
(B.3)
We now proceed to establish the required bounds for Algorithms 1-3:
Since 8, = =xx),, we readily get b, U, 0 by definition, so Algorithm I fits scheme (RL) for free with lo co, Co =0
Algorithm 1.
Algorithm 2. which is F-mmeauurabl.. We thus get
For the case of (Opt-FTRL), we have 8, -2( - so b, =o(X,) - -()
||b |[E[0, [Fi v(X,)) ao
(X)] v(X,-1))ls Fi]
s B[|] X, - X,- Fr
# by (B.3)
L E(IlQ(Y)) 1Y, Fi]
# #by (Opt-FTRL) by Lemma A. # by (Opt-FTRL)
$ (L/K) H[IlY, Y, | F1
$ (L(KK) E[2o(X,) ((X,-))
$ 3LG/K
# by (B.2)
= =0(y) = =(1/1/>
(B.4)
Moreover, given that 0 is meaeaauurall,, we readily get U, =0.
Algorithm 3. Since &, is sampled according 8, (1 8,, + 8, unif (ef. Eq. (11) in Section 3), we readily obtain E[ F.] 0, X,), and hence, by (B.3), we get
B, 011 - x,1I) = = = Moreover, since & 8,/A, follows that ||0, O(1/8,) (1
(1/1fo).
(B.5)
For comparison purposes, we illustrate the algorithms' behavior in simple 2 2 2 x game in Fig. in Appendix E.
B.2. Further algorithms and illustrations. To demonstrate the breadth of (RL. as an algorithmic template, provide below some examples of algorithms from the game-theoretic literature that can be recast as special cases thereof (see also Table for a recap).
Algorithm 4 (Mirror-prox). A progenitor of (Opt-FTRL) the so-called mirror-prox (MP) algorithm [29, 37], which updates as:
Y, Y, + (X,( X, 2(,)
Y.1 +,, +,,x)
(MP)
X,+1 Q(Y..).
The main difference between (MP) and (Opt-FTRL) is that the former utilizes two surrogate gain vectors per iteration meaning in particular that the interim, leading state X, is generated with payoff information from X,, not X,-1- -- This method has been used extensively in the literature for solving variational inequalities and two-player, zero-sum games, cf. Juditsky et al. [29] and references therein.
calculation similar that for (Opt-FTRL) shows that Algorithm 4 has B, = O(1/(77) and 0, = because the algorithm has no further randomization.
16

---

Representative
Regularizer (0) Feedback
Bias (B,)
Variance (o,)
Algorithm
HEDGE
2 log
full info
0
0
Algorithm 2
OMW
z zlogz
full info
O(1/f>>)
0
Algorithm 3
EXP3
zlog
payoff'
O(1/166)
Oafs))
Algorithm
TSALLIS-INF
-4
payoff
O(1/166)
Oa1
Algorithm
MP
general
full info
O(1/16)
0
Algorithm
CMW
z zlog
info O(1/1f0)
0
Table I: A range of algorithms adhering to the general template (RL) and their bias and variance characteristics when with step-size sequence of the form yr y/tfy, by (0, 1J, and, where applicable, sampling parameter 6, 8//f5.
Algorithm 5 (Clairvoyant multiplicative weights), recent variant of the exponential / multiplicative weights (HEDGE) algorithm is the so-called clairvoyant multiplicative weights (CMW) algorithm [39]
Y1,+ Yi,, 7;4(((++)) X(+1)
X1,++ (V
(CMW)
The main difference between (CMW) and (HEDGE) is that the proxy payoff vector & in (CMW) is based on the future state X,+1 and nor the current state X,. To perform this "clairvoyant" update, the players of the game must coordinate to solve an implicit fixed point problem, so (CMW) is only meaningful when one has access to the payoff function v(-). this regard, (CMW) can be seen as Bregman proximal point method in the general spirit of Bauschke et al. [8].
To cast (CMW) as an instance of the generalized template (RL), simply note that the sequence of input signals is given by i = v(X++)), so U, and b, = o(X,+1) e(X,) O(y,) = 0(1/17).
C Proof of Theorem 1
Our main goal in this appendix will be to prove Theorem on the resilience properties of (RL). For convenience, we restate below the relevant result for ease of reference:
Theorem 1. Let X,, == 1, ..... be the sequence of play generated by (RL) with step-size / gain parameters by 26 and ly > O. Then, with probability 1, the limit L(X) of X₁ resilient.
Proof. Our proof that L(X) is resilient hinges on energy-based technique that we will employ repeatedly in other parts of our analysis. To begin, introduce player-strategy deviation pair (i. 2i), and say that a set is resilient to (i, if there exists an element of the set, say x', which counters said deviation, i.e., such that ui(x") 2 u; u;(z)x²,)) In this specific case, our proof proceeds by contradiction, namely by assuming that, with positive probability, L(X) is not resilient to (i, zi). The main steps of our proof unfold as follows:
Step 1. Assume that L(X) is not resilient to (i,zi) with positive probability. Then there exists
c, 6, to such that
(1, ui (X,) + for all t to) 2.
(C.I)
Proof of Step The function f:x E X' + uy (z(xxx-=)) - ux(x) continuous and is compact, so there is definite function 17 1706) such that if ||x x'Il n6)), then lf(x) - f(x')l s S. Now, by assumption, (Vx* E L(X), u, (z,x",) > (x())) ) is of positive probability. We thus get
< P P(Vx* L(X), u (x(xx()) > ux(x))
= P inf (ur(zxx()) - -,,(x))) > 0f
(C.2a)
(E)((
U inf (4(4xx2)) - m/(x') > 2-m
= P
(C.2b)
m= (EC()
$ P(vx' e L(X), ((xx))) -x(xx)) 20}
(C.2c)
17

---

for some > 0 in (C.2c), and where (C.2a) is because L(X) is closed hence compact almost surely. Therefore, by definition of 17()).
0 < P(Vx' E X, dist(x", " (X)) $ 17(c) = (,((zxx(), - - c) 2 Now, let to such that P(Vr 2 fo, dist X, ())) & s > 1 5. Then by construction, we get
(C.2d)
P(V 2 lo. (2); -i) (;(),) + >E
(C.3)
and our proof is complete.
Intuitively, the existence of an action that consistently outperforms X, runs contrary to the behavior that one would expect from any regularized learning algorithm. We will proceed to make this intuition precise below by means of an energy argument. To that end, consider the Fenchel coupling
Fr h4 (zi) (X,r) - (Y1,,z)
(C.4)
Then, by Lemma A.2 in Appendix A, we readily get that
Fie S F, Yr (i - Xi,) +
110;,
(C.5)
2kh
where, obvious notation, we are identifying ž E Ai with the corresponding vertex ez of X; A(AA). To proceed, the main idea will be to relate y (8 X1,)) to its "perfect" counterpart (X)),. X1,). We formalize this below.
Step 2. If L(X) is not resilient to (i, zi), there exists 11 2 to such that, with probability s'/2 O, and for all 2 t1, we have
Σ Ys.
F, Fb
(C.6)
y=1n
Proof of Step 2. With probability and for all f 2 to, we have
Y: 2i Xi.) (e()) Xt,) + + - X1,) y (bia, - Xi,)
(C.7)
2 c (Ul,,, X,,) + (bi,,, =i - -x,,))
(C.8)
The combination of Eqs. (C.5) and (C.8) then provides the following upper bound of Fi+t:
x?
Fi+ S Fj - cy, + (1 Xi,)) + 7 (bi,s, Xi.) + 110
(C.9)
2kh
$ Fi - Σ Ys
1
Ys (U Xz.i) Σ
Σ s=fo
ys (bs.i - Xs.a) +
Σ
110
ys-
(C.10)
2kg
5=1o
Ev.r
Es,t
We are thus left to show is that Ex Ys is the dominant term above. To do so, proceed to examine each term individually:
1 y??
Second-order term: We first deal with the second-order term Σ || readily get
By expanding the
2nm
11s o Σ's1 x2 1 B² of))
(C.11)
T
Σ s=1
However, by our assumptions on the parameters of (RL), we readily get
y2 + B² + of)
lim
(C.12)
f 400
Y1
so we conclude that
Σ x2(1 + B² o²
lim
(C.13)
Σ1 7/s
by the Stolz-Cesåro theorem.
18

---

Bias term: By far the most immediate, the bias term Eb.r is bounded as
Eb. S
lbb.lllo 2 Bs $=10
Σ s=
Ys
as r - oo.
(C.14)
$=
Noise term: Finally, the noise term Eu.r is bounded by means of the Azuma-Hooffdiin inequality, cf. Lemma A.3 in Appendix A. Specifically, with probability least 1 /2, we have
EU.
Σ s=lo
Ys (U,,, 5,1, Xs.i)
2
Σ SUs
4 2
1/2
$ 2
Σ 3=10
y
2
4r¹ E
(C.15)
for all / 2 fo. To proceed, note that a second application of the Stolz-Cesàro theorem yields Ei= o,y? = of (i ys) and, moreover, note that (gg(4//e') = O(E; Ys). Taking square roots and multiplying then yields that
Ev. = Ens
(C.16)
with probability least 1- /2.
We are now in a position to establish the bound Eq. (C.6). Indeed, putting Eqs. (C.13), (C.14) and (C.16) together, we readily infer that there exists / 2 to such that, with probability at least 1 8 /2, we have
Σ - X,,)
1 2kh
Yb
X,,i)
y,
Σ Ys
(C.17)
5=10
5=
for all This proves Eq. (C.6) and concludes our proof.
Summarizing the above, have shown that, with probability at least - 8'/2 /2, we have
FI F
y,
00
(C.18)
s=1p
Since F nonnegative (by Lemma A.2), we have established that the event where L(X) is not resilient to (i, zi) is an event of probability zero. However, since there are uncountably many strategic deviations, the proof is not yet complete; the last step involves an approximation by deviations with rational entries.
Step L(X) sunostt-urely resilient.
Proof of Step 3. The key point of the proof is the observation that a closed set is resilient and only if it is rationally resilient, i.e., it nullifies all rational deviations X; n Q (which are countably many). Indeed, if C(X) is not resilient with positive probability, then, likewise, L(X) will not be rationally resilient with positive probability either. Because there countably many rational deviations, there must be a rational strategic deviation (i, 21) (with z E X, n Ar) to which L(X) is not resilient. This comes in contradiction with the conclusions of Step 2.
This concludes the last required step, the proof of Theorem 1 is now complete.
19

---

D Proof of Theorems 2 and 3
In this last appendix, our goal to prove our characterization of club sets, namely:
Theorem 2. Fix some set S E P(()) and suppose that (RL) is run with a steep regularizer and step-size/ gain parameters by [0, 11, l O, and Eo < 1/2. Then:
stochastically asymptotically stable under (RL) if and only if is a club set.
2. is irreducibly stable under (RL) if and only if it is an m-club set.
Theorem 3. Let S E P(X) be a club set, and let X,, == 1.2...., be the sequence of play generated by (RL) with parameters by [0. 1]. lb O, and for < 1//2. Then, for all > O, there exists (open, unbounded) initialization domain D S y such that, with probability at least 1 1-6 e, we have
dist(X,,,5, S) - Cu(cc -c2
whenever Y1 ED
(17)
where C,c1, C2 constants c2 0), and the rate function yp is given by p(2) (2) if 2 > limz-or 6' (z), and ((z) = 0 otherwise.
Our proof strategy will he construct sheaf of "linearized" energy functions which, when bundled together, yield a suitable Lyapunov- function for S. To do so, let C = IT: C denote the support of S (cf. the definition of club sets), and let
Zi {eia; lia. : ai E C,, E Ai (C)
(D.1)
and
z= Zi
(D.2)
denote the of all pure strategic deviations from S. Then, our ensemble of candidate energy functions will be given by
Ey(y) = (y.z) for ZE E Z, y.ye..
(D.3)
The motivation for this definition is given by the following lemma. Lemma D.I. Suppose that the sequence yt V", 1,2,..., has Ez(y)) -00 for all 2 as I - co. Then the sequence x, = ((y,) converges to as - oo.
Proof. Let z Cta: - Cta, for some N, a, C,, and af Ai \ C. Since Ey by assumption, we get y y - -co and hence, by Lemma A.I, we conclude that Qia; (x,) In turn, given that this holds for all i E N and all aj A; C, conclude x, ( converges to S.
In view of the above, we will focus on showing that EY, - for all E Z. As first step, we establish a basic template inequality for the evolution of E, under (RL).
Lemma D.2. Fix some 2 and let E, = Ey(Y,). Then, for all r = 1,2,... we have
E1+1 S E, + (x(,)), 2) + YiEi 4eth
(D.4)
where the error terms & and v, are given by
&, 2U, and
v, 2B,
(D.5)
Proof. Simply set y + Y,41 in (y). invoke the definition of the update Y, < Y,+1 in (RL), and note that 2)1 $ b, $ 2B, by the definition of Z.
The key take-away from (D.4) is that, if X, is close to S and a, E C, aj E A, \ C,, we will have
(o(X,).2) Dio; (1)) - Dia, (X,) = u, X-1,) (; X-1.) <
(D.6)
by the continuity of u; and the assumption that S is a club set. More concretely, by the definition of the better-reply correspondence, have
(u(x"),z) < for x" E S and all E Z
(D.7)
20

---

and hence, by continuity, there exists neighborhood B of S such that
(u(x), 2) <0 for all x E B and all 2 E 2.
(D.8)
In other words, as long X, sufficiently close S, (D.4) exhibits consistent negative drift pushing E, towards -o0.
To exploit this "dynamic consistency" property of S. it will be convenient to introduce the family of sets
D(e) ty E V": (y.z)
for all E 2)
(D.9)
As we show below, these sets are mapped under @ to neighborhoods of S. so they are particularly well-suited serve initialization domains for (RL). This is encoded in the following properties:
Lemma D.3. Lef Q(y) for some y V* Then, for all az d/,, N, we have
Xian $ =((0(11) + "Yia ytur
(D.10)
with yp defined as per Theorem i.e.,
0
i (0*),
((2)
(8') (z)
(0*) <=<0((1),
(D.11)
ifz (17).
Corollary D.1. For all 8 > O there exists some 68 E RR such that, for all e > 68 and all E De, we have
Quo;(ii <
for all of E Ai C. and all e N.
(D.12)
Proof of Lemma D.3. Suppressing the player index for simplicity, the first-order stationarity condi- tions for the convex problem (9) readily give
Ya 0' 0' = H- Va- Va.
(D.13)
where μ is the Lagrange multiplier for the equality constraint E. and Ya is the complementary slackness multiplier of the inquality constraint Xa 2 0 (so Va = whenever Xa > 0). Thus, rewriting (D.13) for some A, get
Yu - Ya =0 - 0 (x.) + +V
(D.14)
and hence
0'(xx') 0' (xa) +Va Y Va ya S (1 Va + Ya' ya- where we used the fact that va 2 O. Now, if (17() yer - Y/ < 6 (0*) and x > 0 (so V = 0), we will have 0' (xxr) < 0' (0*). contradiction. This shows that x., if (1(17) )+ Ya' Ya 00').. so (D.10) is satisfied in this case. Otherwise, xf > O, we must have Va 0 by complementary slackness, so (D.10) follows by applying the second branch of (D.11) (D.15).
(D.15)
The above provides us with a fairly good handle on the local geometric and dynamic properties of S. On the flip side however, the various error terms in (D.5) may be positive, so E, may fail to be decreasing and X, may drift away from S. On that account, it will be convenient to introduce the aggregate error processes
I = Σ EvEx
and
11,= Σ Ysh..
(D.
Intuitively, the aggregates (D.16) measure the total effect of each error term in (D.4), so we will establish a first series of results under the following general requirements:
1. Subleading error growth:
lim I,/T, 0 10000
(Sub.I)
lim 11,/T, = 1-00
(Sub.II)
where T, Et_ Ys and both limits are to be interpreted in the almost sure sense.
21

---

2. Drift dominance:
P(L, CT for all r) 2 1 1-1 17
(Dom.I) (Dom.Il)
P(I,, s /2,"/2 for all r) 2 1 - 1
for some C 0 and a [0, 1).
In a nutshell, (Sub) posits that the aggregate error processes I, and II, of (D.16) are subleading relative to the long-run drift of (D.4), while (Dom) goes a step further and asks that said errors are asymptotically dominated by the drift in (D.4). Accordingly, under these implicit error control conditions, we obtain the interim convergence result below:
Proposition D.1. Let S be club set, fix some confidence threshold ll O, and let X, 2(Y) be the sequence of play generated by (RL). If (Sub) and (Dom) hold, there exists an unbounded initialization domain D S V such that
P(X, converges to S S E D) 2 2n
(D.19)
Proof of Proposition D.I. Fix some ? 2, let F, EY;),, and pick [0. 1) that (Dom) holds for some C > 0. In addition, set c = - - (v(x)) z) > O, let to inf CT, > CT,"", and write AE max, (CT," -.T). Then, Y initialized in + (=D(++A)) where is such that D(e) S B, we will have Y, E D()) for all t. Indeed, this being trivially the case for / = 1, assume it to be the case for all s 1,2,....Z. Then, by (D.4) and our inductive hypothesis, we get
E
E1
Σ ys (x 2) + I, +1+ II S - AE CT + Cr - x=1
12
AE+ AE -
(D.20)
i.e. Eit1 D(c), as claimed.
Now, since E, E D(e) for all 1, we conclude that
E,+1 F1 CT, + II, for all 1,2,...
(D.21)
Thus, if (Sub) holds, we readily get E, - -oo with probability 1 on the event that (Dom.l) and (Dom.II II) both hold. This implies that E, - -co, and since E Z above is arbitrary, we conclude that X, - S with probability at least - 2n, as claimed.
We are now a position to prove Theorem 2.
Proof of Theorem 2. Our proof will hinge on showing that (Sub) and (Dom) hold under the stated step-size and sampling parameter schedules. Our claim will then follow by direct application of Proposition D.1 and a reduction to suitable subface of X.
First, regarding (Sub), the law of large numbers for martingale difference sequences [25, Theorem 2.18] shows that T,/T, + with probability on the event [Σ, x? ElE? 1 F.1/ < oo However
E Fi1 = 2 EI FA s =f ((2
(D.22)
so, in turn, we get
Σ >?
Σ 10222 =
Σ
2f, 2(1- = 0
[
1
<0
(D.23)
+7
2-
given that for < 1/2.. This establishes (Sub.I); the remaining requirement (Sub.II) follows trivially by noting that Σ YsB,/ Σ Yss - if and only if B, - O, which is immediate from the theorem's 's assumptions.
Second, regarding (Dom), since B, is deterministic and B, = (11/r for some 4, > 0. it is always possible to find and a E (0, 1) so that (Dom. II) holds. We are thus left to establish (Dom.l). To that end, let I, supisssi [Tr] and set P, := P(1; > Cr,¹ /2) so
v2 11.. 9/2
E| Σ
E E
P <
Cg
(D.24)
(C/2)
aq
T
44
22

---

where Eq is a positive constant depending only on C and and we used Kolmogorov's 's inequality
(Lemma A.4) in the first step and the Burkholder-Diue Sonddy inequality (Lemma A.6) in the second.
To proceed, we will require the following variant of Hölder's inequality (9, p. 15]:
Σ a,hs
Σ
(1-2)p by a5
(D.25)
valid for all as,
as,bs bs and all p 1, a (). Then, substituting as yz. bs - ||,,1
- q/2 and d = 1/2 - 1/q. (D.24) gives
Ex 9/2-1
Σ s=1 7
1+//2
E s=1 Ys
14q/2
P, cq
Cq
(D.26)
I+(a-111 1/2)g
We now consider two cases, depending on whether the numerator of (D.26) is summable or not.
Case 1: fy(14/22) 2 ltqla. this case, the numerator of (D.26) is summable under the theorem's assumptions, so the fraction in (D.26) behaves as O O(1/r() ((1))(11,,,0((0a11,,,
Case 2: ly(1 + q/2) < + glo. In this case, the numerator of (D.26) is not summable under the theorem's assumptions, so the fraction in (D.26) behaves as 011)-1,(14//))4g /r(1-(,)(11 110-11)111(0-11211111
Thus, working out the various exponents, a tedious but otherwise straightforward - calculation shows that there exists some a E (0. 1) such that P, is summable as long as Crr 1/2 1/q and 0 s ly < g2 q). Hence, if y is sufficiently small relative to we conclude that
P(L S CT² /2 for all r) 2 1 Σ, P, 2 - 1/2..
(D.27)
Finally, fy 1/2 + Lo, (Dom.I) is a straightforward consequence of (D.24) for q =
With all this in hand, the final steps of our proof proceed as follows:
Closedness = Stability.
Our assertion follows by invoking Proposition D.1.
Closedness. Suppose that S is not club. Then there exists some pure strategy E C and some deviation a' & C such that the deviation from a to a' is not costly the deviating player. Thus, if we consider the restriction of the game to the face spanned by and a' (a single-player game with two strategies), the corresponding score difference will be
Stability =
9ee. - ya. 2 Σ Yr,,
Σ Y,
(D.28)
s=1
By our standing assumptions for b, and U, (and Doob's martingale convergence theorem for the latter), both Σ==1 b, and Σx=1 YsU, will be bounded from below by some (a.s.) finite random variable Ag. Since 0 is steep, it follows that, with probability 1, lim inf, > O, so C cannot be stable.
Minimality = Irreducible Stability. Suppose that S is m-club. Then, by our previous claim, S stochastically asymptotically stable. If contains a proper subface S' that is also stochastically asymptotically stable, S' must be club by the converse implication of the first part of the theorem. However, in that case, would not be m-club, a contradiction which proves our claim.
Irreducible Stability
Minimality. For our last claim, assume that S is irreducibly stable. By the first part of our theorem, this implics that S is club. Then, it so happens that S is not m-club, would contain a proper club subface S' S S; by the first part of our theorem, this set would be itself stochastically asymptotically stable, in contradiction to the irreducibility assumption. This shows that S is m-club and concludes proof.
We are only left to establish the convergence rate estimate of Theorem 3.
23

---

Long-run behavriar of
Long-ran
Lung-run EXPs
Long-run behaviir
The long-run behavior of Algorithms 1-3 in a 2 x 2 x 2 game. Algorithms and were run with a logit choice map per (HEDGB); Algorithm 3 was run with both variants, EXP3 and TSALLIS-ING All algorithms were run for 5 x 10y iterations with y, 1//0.4 and 6, = 0.1/1 color indicates time, with darker hues indicating later iterations. The face to the left is clased under better replies, so X, converges quickly to said face (as per Theorems and 3).
Figure 2:
Proof of Theorem 3. Going back to (D.21) and invoking Lemma D.3 shows that there exist constants C1 0 and C2 E IR such that, for all oj Ai C., N, we have
Xia, ((((17)+ + E p(c2 c17,)
(D.29)
with probability on the events of (Dom). We thus get
dist, S) S Σ Σ iEN a.EAAC
p
(D.30)
and our proof is complete.
As for the rate estimates of Corollary 2, the proof boils down to a simple derivation of the correspond- ing rate functions:
Proof of Corollary 2. By straightforward calculation, we have:
1. If (()) = = zlogz z then (()) = cxp( z). 2. If ((z) = =4 then p(z) = 4/22.
If ((2) =22/2 then <=z) [=]]-
Our claims then follow immediatly from the rate estimate (17) of Theorem 2.
E Numerical experiments
In all our experiments, we the EXP3 variant of bandit FTRL (B-FTRL) (cf. Algorithm 3) with step-size and sampling radius parameters yr 0.2 1 and 6, = 0.1 x r 0015 respectively. The algorithm was run for 7 = 10 iterations and, to reduce graphical clutter, we plotted only every third point of each trajectory. Trajectories have been colored throughout with darker hues indicating later times (e.g.. light blue indicates that the trajectory is closer in time to its starting point, darker shades of blue indicate proximity to the termination time). The algorithm' 's initial conditions were taken from a uniform initialization grid of the form E (-1, O, 1}3 and perturbed by uniform random number in [-0.1, 1) to avoid non-generic initializations.
In general, the two defining elements of (RL) are a) the regularizer of the method; and b) the feedback available to the players. From experiments, conclude that methods with Euclidean regularization tend have faster identification rates (i.e., converge to the support of an equilibrium / club set faster), but they are more "extreme" than methods with an "entropy-like" regularizer (in the sense that players tend to play pure strategies more often). As for the feedback available to the players, payoff- payoff-based based methods tend to have higher variance (and hence slower rate of convergence) relative to methods with full information; otherwise, from a qualitative viewpoint, there are no perceptible differences in their limiting behavior.
Finally, optimistic/ extra-oracle methods with full information exhibit better convergence properties in two-player zero-sum games (relative to standard FTRL policies); however, this is a fragile advantage
24

---

that evaporates in the presence of noise and/or uncertainty (in which case "vanilla" and "optimistic" methods are essentially indistinguishable). We illustrate these findings in Fig. 2.
Regarding Fig. 1, the payoffs of the chosen games were normalized to [-1, I] and players are assumed choose between two actions labeled "O" and "1". The specific tableaus shown in the table below, next to the respective portrait (all taken from Fig. 1.
Caechnation
I.I.IIII
(0.0,0)
(0.0,
(0,1.0)
(0.1.
(1.0.0)
(1,0,1)
(1,1,0)
(1,1,1)
DYNAMICS
UTILITIES
Player
1
0
0
Player II
1
Player
1
0
0
0
0
Gerlindaas Spataee
I.
(0.0,0)
(0.0.1)
(0.1.0)
1.
(1..0)
(1.0.1)
(1.1.))
(1
DYNAMICS
UTILITIES
Player
1
0
1
Player
1
0
1
1
Player III
0
0
0
0
0
I.
(0.0,0)
(0.0.
(0.1.0)
O..1.
(1.0.0)
(1.0.1)
(1.1,0)
(1.1.1)
DYNAMICS
UTILITIES
Player
0
0
0.1
0.1
0.1
0.1
Player II
1
0
1
Player
0
1
0
0
Matdiig Chanade Option
I.1.1II
(0.0.0)
(0.0.1)
(0.1.0)
(0.1.1)
(1.0.0)
(1,0.1)
(.1.0)
(1,1.))
DYNAMICS
UTILITIES
Player -1
Player
1
1
-1
Player III
-1
25


Reviews:
[{"review_id": "HYjIDlNXnU", "reviewer": "Reviewer_nBFX", "summary": "The paper deals with a fundamental question about long-term behavior of regularized learning algorithms in finite player finite action static games. They prove an interesting equivalence between the set of strategies which are closed under better replies with that of stochastically stable and attracting fixed points of wide class of regularized learning algorithm popularly studied in literature. Furthermore, they also study the rate of convergence of regularized learning algorithms to this set. \n\n", "questions": "-- Is there any characterization on size of m-club set given certain regularity structure of game. This will provide more predictive power about the asymptotic behavior of common learning dynamics", "limitations": "Some typographical errors \n\n1. In supplementary material, line 267 has ?? \n2. In equation C.13 the right hand side is missing. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies a very fundamental equivalence relation between payoff structure of a static game with that of limit sets of regularized learning algorithms. This result is very strong result which enhances our understanding of learning in static games. Particuarly, this paper brings the notion of better replies from economic literature and presents a deep connection with asymptotic properties of learning algorithm.  \n\nThe clarity of presentation of this paper is very good. \n\nThe literature survey is also up to the mark to the best of my knowledge. \n\n", "weaknesses": "The paper has no major weakness in my view. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you again for your encouraging input and positive evaluation. We reply to your questions below and we will revise our manuscript accordingly at the next revision opportunity:\n\n\n1. \"*Is there any characterization on size of m-club set given certain regularity structure of game. This will provide more predictive power about the asymptotic behavior of common learning dynamics.*\"  \n\n   **Reply.** To the best of our knowledge, a complete characterization of (the size of) the support of an m-club set is an open question in the literature. However, under certain structural hypotheses, it is indeed possible to predict what these sets will look like: for example, in (generic) congestion games, the support of any mixed Nash equilibrium contains that of a strict equilibrium, so only strict Nash equilibria can be m-club (a fact which, coupled with Theorem 1, implies that the only irreducibly stable sets of regularized learning in congestion games are strict equilibria). We conjecture that the class of $(\\lambda,\\mu)$-smooth games introduced by Roughgarden may enjoy similar structural properties, but we are not aware of a specific characterization along these lines.\n\n---\n\n2. **Typographical errors**  \n   - \"*Line 267 has ??*\": apologies, this was a broken reference to Appendix C.  \n   - \"*In equation C.13 the right hand side is missing.*\": indeed, (C.13) should read  \n   $$\n  \\lim_{t\\to\\infty} \\frac{\\sum_{s=1}^{t} \\gamma_s^2 (1+B_s^2+\\sigma_s^2)}{\\sum_{s=1}^{t} \\gamma_s} = 0\n   $$\nThanks for spotting these two typos, consider them fixed!\n\n---\n\nPlease let us know if you have any further questions - and thank you again for your input and positive evaluation!\n\nKind regards,\n\nThe authors"}, {"review_id": "sQDUYLlHNp", "reviewer": "Reviewer_7Hjy", "summary": "The paper shows the convergence of regularized learning in games to sets satisfying a property called closeness under better replies. Moreover, convergence rates are derived even with bandit feedback. ", "questions": "While the questions (line 59-60) are important and the results are mathematically sound, what do they imply to regularized learning, in particular, for practitioners? For example, from prior works, we already know that a day-to-day strategy can be arbitrarily bad so it is probably better to do some averaging. Does this paper extend our understanding in this direction?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The pointwise behavior of regularized learning in games has gained lots of attention recently, and the paper considers a fundamental question in this field. The authors provide complete and general answers to the questions. ", "weaknesses": "The paper is super notation-heavy and considers a very general setting in terms of both algorithms and feedback models. It would be much easier to follow if the authors could first provide some basic or toy examples and then generalize. Minor: a corrupted reference at the beginning of Line 267.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed input and positive evaluation. We reply to your questions below and we will revise our manuscript accordingly at the next revision opportunity:\n\n1. \"*The paper is [notation-heavy and considers a very general setting] It would be much easier to follow if the authors could first provide some basic or toy examples and then generalize.*\"  \n\n   **Reply.** We understand your concern but, at the same time, we were constrained by the NeurIPS page limitations, and we had to do some tough choices in terms of presentation along the way. In this regard, we intend to take full advantage of the extra page allowed in the revision phase to implement the following restructuring changes:\n   - Include a quick \"warm-up\" section before the current Section 3, intended to discuss some basic algorithms and feedback models that are standard in the field (exponential weights, optimistic exponential weights, and bandit exponential weights).\n   - Proceed to state the \"umbrella\" FTRL template and quickly explain how it includes these algorithms as special cases (without any technical details that could distract the reader).\n   - Relegate the remaining technical elements and definitions to the appendix (in order to streamline the flow of the discussion), as per your suggestion.\n   \n   This will provide the necessary examples and anchor points to motivate the general analysis and ease notation, so we trust and hope it addresses your notation concerns.\n\n---\n\n2. \"*Minor: a corrupted reference at the beginning of Line 267.*\"  \n\n   **Reply.** Apologies, this was a broken reference to Appendix C - thanks for catching it.\n\n---\n\n3. \"*From prior works, we already know that a day-to-day strategy can be arbitrarily bad so it is probably better to do some averaging. Does this paper extend our understanding in this direction?*\"  \n\n   **Reply.** There are several remarks to be made here, so we proceed point-by-point:\n   - First, from a practical point of view, when agents are involved in a real-time, online learning process (e.g., commuting from home to work each day), the payoff they obtain at each epoch is determined by the action they actually *played* at said epoch. In this context, an \"averaged\" sequence of strategies (either time-averages or empirical frequencies) is not as meaningful, because it is never actually *played* by the agents. As such, the day-to-day sequence of play becomes the de facto figure of merit for the problem, as it describes what the agents actually play and determines their in-game rewards.\n   - Second, if the game is not monotone (in the sense of operator theory and variational inequalities), the time-averaged sequence $\\bar x_{i,t} = (1/t) \\sum_{s=1}^t x_{i,s}$ has no convergence guarantees in general. The only general class of finite games which *is* monotone is two-player, zero-sum games: in this case, time-averaging can be beneficial as a technique for the **offline** computation of Nash equilibria but, even then, since $\\bar x_{i,t}$ is never actually played by the players, it is not as meaningful from an **online** viewpoint.\n   - Finally, concerning the empirical frequency of play $\\bar z_{\\alpha,t} = (1/t)\\sum_{s=1}^t \\mathbb{I}(\\alpha_t = \\alpha)$ (which is not the same as the time-averaged sequence $\\bar x_t$ above), it is indeed well known that, under no-regret learning, $\\bar z_{t}$ converges to the Hannan set of the game (its set of CCE). However, as we discuss in Section 4, the Hannan set could contain highly non-rationalizable outcomes, e.g., with players selecting dominated strategies for all time (the counterexample of Viossat and Zapechelnyuk). Our result serves to exclude such outcomes by showing that the *only* part of the Hannan set which is stable and attracting under regularized learning is its intersection with the set of correlated actions that are supported on a **club** set - i.e., which is closed under better replies, and hence strategically stable.\n\n   We did not include a detailed discussion along those lines because, as we explained above, averaging in an online context is less relevant than in the offline case. However, we will be happy to take advantage of the extra page provided in the camera-ready phase to include the above discussion.\n\n---\n\nWe hope and trust that these points address your questions - thank you again for your input and positive evaluation!\n\nKind regards,\n\nThe authors"}, {"review_id": "aV8s3SxQ1b", "reviewer": "Reviewer_vfB1", "summary": "This paper studies the long run behavior of no-regret learning, and introduces the notion of resilience to strategic deviations as a metric with which to characterize no-regret learning algorithms. Moreover, to further strengthen their results the paper utilizes the idea of setwise strategic stability (m-club). In particular, the paper shows a nice connection between regularized learning and club sets. Finally, they estimate convergence rates to club sets, showing geometric rate for entropic regularizers and finite iterations for projection-based methods. ", "questions": "A question regarding the actual convergence properties of regularized learners to club sets in comparison to classical solution concepts:  how do the payoffs of these points compare to the Nash equilibrium values? Do you see any interesting behaviors of note between standard FTRL dynamics and other RL dynamics that are significantly different in your experiments?\n\nAlso, is there any connection between club sets and the chain recurrent set of the dynamics? Of course the paper is focused on discrete time regularized learning, but do you have any intuition as to whether club sets could be useful to construct/converge to chain recurrent sets in the continuous-time setting? ", "limitations": "The limitations and scope of the proposed ideas are discussed adequately.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think this paper is a conceptual step forward in the area of regularized learning dynamics. A major point of contention in many prior works in learning in games has been the disconnect between desirable equilibria and equilibria that are actually converged to by regularized learning. The results given in the paper are fairly broad, and the characterization of club sets as an alternative solution concept for regularized learning is (as far as I can tell) quite watertight and intuitive.", "weaknesses": "I only have very minor complaints with the paper, namely the section on regularized learning that introduces a few different algorithms under the RL umbrella. I feel this section is quite long and the notation is unnecessarily heavy, most of these could be in the appendix. I would have preferred to see more space allocated to either an extended proof sketch for Thms 2 & 3, or more experimental details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are sincerely grateful for your detailed input and positive evaluation. We reply to your questions below and we will revise our manuscript accordingly at the next revision opportunity:\n\n1. \"*I feel Section 3 is quite long and the notation is unnecessarily heavy, most of these could be in the appendix. I would have preferred to see more space allocated to either an extended proof sketch for Thms 2 & 3, or more experimental details.*\"  \n\n   **Reply.** We understand your concern but, at the same time, we were constrained by the NeurIPS page limitations, and we had to do some tough choices in terms of presentation along the way. In this regard, we intend to take full advantage of the extra page allowed in the revision phase to implement the following restructuring changes:\n   - Include a quick \"warm-up\" section before the current Section 3, intended to discuss some basic algorithms and feedback models that are standard in the field (exponential weights, optimistic exponential weights, and bandit exponential weights).\n   - Proceed to state the \"umbrella\" FTRL template and quickly explain how it includes these algorithms as special cases (without any details).\n   - Relegate the remaining technical elements, definitions and examples to the appendix (in order to streamline the flow of the discussion), as per your suggestion.\n\n   This will provide the necessary examples and anchor points to motivate the general analysis and ease notation, and it will also leave us sufficient space to expand on the proof sketches of Theorems 1-3 (by bringing forward the step-by-step skeleton from the paper's current appendices).\n\n---\n\n2. \"*How do the payoffs of these points compare to the Nash equilibrium values?*\"  \n\n   **Reply.** Each club set contains an essential component of Nash equilibria so, by the multilinearity of the players' payoff functions, the payoff values of the latter will be contained in the convex hull of the former (and, in the case of m-club sets, it cannot be contained in a smaller subset thereof). Without further structural assumptions on the underlying game, we are not aware of a finer relation between them.\n\n---\n\n3. \"*Do you see any interesting behaviors of note between standard FTRL dynamics and other RL dynamics that are significantly different in your experiments?*\"  \n\n   **Reply.** In general, the two driving factors are (*a*) the regularizer of the method; and (*b*) the feedback available to the players. Methods with Euclidean regularization tend to have faster identification rates (i.e., converge to the support of an equilibrium / club set faster), but they are more \"extreme\" than methods with an \"entropy-like\" regularizer (in the sense that players tend to play pure strategies more often). As for the feedback available to the players, payoff-based methods tend to have higher variance (and hence a slower rate of convergence) relative to methods with full information; otherwise however, from a qualitative viewpoint, there are no perceptible differences in their limiting behavior. Finally, optimistic / extra-oracle methods with **full** information exhibit better convergence properties in two-player zero-sum games (relative to standard FTRL policies); however, this is a fragile advantage that evaporates in the presence of noise and/or uncertainty (in which case \"vanilla\" and \"optimistic\" methods are essentially indistinguishable).\n   \n   Figure 2 in Appendix B was intended to illustrate a part of these findings, and we would be happy to expand on it and bring it to the main text if you think it would make things clearer for the reader.\n\n---\n\n4. \"*Is there any connection between club sets and the chain recurrent set of the dynamics? Of course the paper is focused on discrete time regularized learning, but do you have any intuition as to whether club sets could be useful to construct/converge to chain recurrent sets in the continuous-time setting?*\"  \n\n   **Reply.** Excellent question! Due to space limitations, we could not expand on the continuous-time implications of our work but, indeed, there is an important relation between sets that are *minimally* closed under better replies (m-club) and sets that are internally chain recurrent.\n   \n   First, in continuous time, the dynamics of regularized learning are described by the system $\\dot y(t) = v(x(t))$ with $x(t) = Q(y(t))$, as per reference [28] of our paper. In this context, the analogue of Theorem 2 would state that a set is m-club if and only if it is irreducibly stable under the above dynamics: we do not prove this result, but our techniques can be used to show that this statement holds.\n   \n   Given this equivalence, it follows that m-club sets are compact, invariant, and do not admit any asymptotically stable subsets with smaller support. This is not exactly the same as not admitting any proper *attractors*, but it is close - and since a set is internally chain recurrent if and only if it is compact, invariant, and does not admit any proper attractors, this would suggest that m-club sets are, in many cases, internally chain recurrent.\n   \n   We conjecture that this relation is actually true in general, but we do not have a proof for this fact, and we believe it is a very fruitful direction for future research.\n\n---\n\nWe hope and trust that the above points address your questions - thank you again for your detailed input and positive evaluation!\n\nKind regards,\n\nThe authors"}]

Author rebuttal:
Dear AC, dear reviewers,

We are sincerely grateful for your time, input and positive evaluation. To streamline the discussion phase, we reply to each reviewer's questions in a separate point-by-point thread below.

Thank you again for your time and positive input. Kind regards,

The authors

Meta-review: This paper studies the long-term behavior of regularized, no-regret learning in multiplayer games. Concretely, the paper considers a more stringent criteria---closedness under better replies (CLUB), and shows that a product of pure strategies is CLUB if and only if its span is stable and attracting under regularized learning. Additionally, the rates of convergence of several algorithms are given.

The paper considers a new interesting setting, and achieves novel results. The reviewers are satisfied with author feedback. We thus recommend acceptance.
Decision: Accept (spotlight)