Victor Boone
email: victor.boone@univ-grenoble-alpes.fr

Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr.

THE EQUIVALENCE OF DYNAMIC AND STRATEGIC STABILITY UNDER REGULARIZED LEARNING IN GAMES

Keywords: 2020 Mathematics Subject Classification. Primary 91A10, 91A26, secondary 68Q32, 62L20 Regularized learning, strategic stability, asymptotic stability, closedness under better replies, resilience. 1

In this paper, we examine the long-run behavior of regularized, no-regret learning in finite games. A 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 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 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 in question incurs a cost to the deviator -a property known as closedness under better replies (club). In so doing, we obtain a far-reaching 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.

Introduction

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 a 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 every player follows an iterative procedure aiming to increase their individual payoff, does the players' long-run behavior converge to a rationally admissible state? A natural setting for studying this question is to assume that each player is following a no-regret algorithm, i.e., a policy which is asymptotically as good against a given sequence of payoff functions as the best fixed strategy in hindsight. In this framework, the link between learning and rationality is provided by a folk result which states that, under no-regret learning, the empirical frequency of play converges to the game's set of coarse correlated equilibria (CCE) -also known as the game's Hannan set [START_REF] Hannan | Approximation to Bayes risk in repeated play[END_REF]. This result has been of seminal importance to the field because no-regret play can be achieved via a wide class of "regularized learning" policies, as exemplified by the "follow-the-regularizedleader" (FTRL) family of algorithms [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Shalev-Shwartz | Convex repeated games and Fenchel duality[END_REF] and its variants -optimistic methods [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF][START_REF] Hsieh | On the convergence of single-call stochastic extra-gradient methods[END_REF][START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF][START_REF] Syrgkanis | Fast convergence of regularized learning in games[END_REF], Hedge / EXP3 [START_REF] Auer | Gambling in a rigged casino: The adversarial multi-armed bandit problem[END_REF][START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF], implicitly normalized forecasters [START_REF] Abernethy | Fighting bandits with a new kind of smoothness[END_REF][START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF], etc.

All these policies have (at least) one thing in common: they seek to provide the tightest possible guarantees for each player'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.e., as if they had full knowledge of the game, common knowledge of rationality, the ability to communicate this knowledge, etc. On the other hand, the marginals of Hannan-consistent correlated strategies may fail even the weakest axioms of rationalizability (such as the elimination of strictly dominated strategies). In particular, a well-known example of Viossat & Zapechelnyuk [START_REF] Viossat | No-regret dynamics and fictitious play[END_REF] (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 is Nash, the actual trajectory of play may -and, in fact, often does -diverge away from the game's set of equilibria [START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF][START_REF] Mertikopoulos | Cycles in adversarial regularized learning[END_REF][START_REF] Mertikopoulos | Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile[END_REF] or exhibits chaotic, unpredictable oscillations [START_REF] Chotibut | Family of chaotic maps from game theory[END_REF][START_REF] Palaiopanos | Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos[END_REF]. 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, 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 as the "folk theorem of evolutionary game theory" [START_REF] Cressman | Evolutionary Dynamics and Extensive Form Games[END_REF][START_REF] Hofbauer | Evolutionary game dynamics[END_REF][START_REF] Weibull | Evolutionary Game Theory[END_REF]. Somewhat informally, this theorem states that, under the replicator dynamics (the continuoustime 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 a state is stable and attracting under the replicator dynamics if and only it is a strict Nash equilibrium of the underlying game [START_REF] Hofbauer | Evolutionary game dynamics[END_REF][START_REF] Weibull | Evolutionary Game Theory[END_REF].

In the context of regularized learning, [START_REF] Coucheney | Penalty-regulated dynamics and robust learning procedures in games[END_REF][START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] showed that a similar equivalence holds for the dynamics of FTRL in continuous time: a state is stable and attracting under the FTRL dynamics if and only if it is a strict Nash equilibrium. Subsequently, Giannou et al. [START_REF] Giannou | Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information[END_REF][START_REF] Giannou | The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond[END_REF] extended this equivalence 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 a strict Nash equilibrium.

This is an important pointwise prediction but it does not cover cases where regularized learning algorithms do not converge to a point, but to a set (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 [START_REF] Basu | Strategy subsets closed under rational behavior[END_REF][START_REF] Demichelis | From evolutionary to strategic stability[END_REF][START_REF] Fudenberg | Game Theory[END_REF][START_REF] Ritzberger | Evolutionary selection in normal-form games[END_REF]. 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 a 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 a 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. To account for this deficiency, we turn to a much more stringent criterion of setwise strategic stability, that of closedness under better replies (club). This notion, originally due to Ritzberger & Weibull [START_REF] Ritzberger | Evolutionary selection in normal-form games[END_REF], states that any deviation from a product of pure strategies is costly, and it is one of the strictest setwise refinements in game theory. In particular, it refines the notion of closedness under rational behavior (curb) [START_REF] Basu | Strategy subsets closed under rational behavior[END_REF], and it satisfies all the seminal strategic stability requirements of Kohlberg & Mertens [START_REF] Kohlberg | On the strategic stability of equilibria[END_REF], including robustness to strategic payoff perturbations. 1 In this general context, we show that regularized learning enjoys a 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 a strictly smaller closed under better replies (club) set): a 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 a 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 [START_REF] Ritzberger | Evolutionary selection in normal-form games[END_REF]. Importantly, our analysis covers several different update structures -"vanilla" regularized methods, but also their optimistic variants -as well as a wide range of information models -from full payoff information to bandit, payoff-based feedback.

Preliminaries

We start by recalling some basic facts and definitions from game theory, roughly following the classical textbook of Fudenberg & Tirole [START_REF] Fudenberg | Game Theory[END_REF]. First, a finite game in normal form consists of a) a finite set of players i ∈ N ≡ {1, . . . , N }; b) a finite set of 1 Roughly speaking, robustness to strategic payoff perturbations means that the set under study remains stable even if the payoffs of the game are subject to small -but possibly adversarial -perturbations.

actions -or pure strategies -A i per player i ∈ N ; and c) an ensemble of payoff functions u i : j A j → R, each determining the reward u i (α) of player i ∈ N in a given action profile α = (α 1 , . . . , α N ). Collectively, we will write A = j A j for the game's action space and Γ ≡ Γ(N , A, u) for the game with primitives as above.

During play, each player i ∈ N may randomize their choice of action by playing a mixed strategy, i.e., a probability distribution x i ∈ X i := ∆(A i ) over A i that selects α i ∈ A i with probability x iαi . To lighten notation, we identify α i ∈ A i with the mixed strategy that assigns all weight to α i (thus justifying the terminology "pure strategies"). Then, writing x = (x i ) i∈N for the players' strategy profile and X = i X i for the game's strategy space, the players' payoff functions may be extended to all of X by setting

u i (x) := E α∼x [u i (α)] = α∈A u i (α) x α (1)
where, in a slight abuse of notation, we write x α for the joint probability of playing α ∈ A under x, i.e., x α = i x iαi . This randomized framework will be referred to as the mixed extension of Γ and we will denote it by ∆(Γ).

For concision, we will also write (x i ; x -i ) = (x 1 , . . . , x i , . . . , x N ) for the strategy profile where player i plays x i ∈ X i against the strategy profile x -i ∈ j̸ =i X j of all other players (and likewise for pure strategies). In this notation, we also define each player's mixed payoff vector as

v i (x) = (u i (α i ; x -i )) αi∈Ai (2) so the payoff to player i ∈ N under x ∈ X becomes u i (x) = αi∈Ai u i (α i ; x -i ) x iαi = ⟨v i (x), x i ⟩. (3)
Moving forward, the best-response correspondence of player i ∈ N is defined as the set-valued mapping br i : X ⇒ X i given by

br i (x) = arg max x ′ i ∈Xi u i (x ′ i ; x -i ) for all x ∈ X . (4)
Extending this over all players, we will write br = i br i for the product correspondence br(x) = br 1 (x) × • • • × br N (x), and we will say that x * ∈ X is a Nash equilibrium (NE) if x * ∈ br(x * ). Equivalently, given that u i (x ′ i ; x -i ) is linear in x ′ i , we conclude that x * is a Nash equilibrium if and only if

u i (x * ) ≥ u i (α i ; x * -i ) for all α i ∈ A i and all i ∈ N . (NE)
As a final point of note, if x * is a Nash equilibrium where each player has a unique best response -that is, br i (x * ) = {x * i } for all i ∈ N -we will say that x * is strict because, in this case,

u i (x * ) > u i (x i ; x * -i ) for all x i ̸ = x * i , i ∈ N .
An immediate consequence of this is that strict equilibria are pure, i.e., each x * i is a pure strategy. Among Nash equilibria, strict equilibria are the only ones that are "structurally 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.

Regularized learning in games

Throughout our paper, we will consider iterative decision processes that unfold as follows:

(1) At each stage n = 1, 2, . . . , every participating agent selects an action.

(2) 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 a player's cumulative payoff over time and the player's best possible strategy in hindsight. Formally, if the players' actions at each epoch n = 1, 2, . . . are collectively drawn by the probability distribution z n ∈ ∆(A), the regret of each player i ∈ N is defined as

Reg i (T ) = max αi∈Ai T n=1 [u i (α i ; z -i,n ) -u i (z n )], (5)
and we will say that player i has no regret if Reg i (T ) = o(T ).

One of the most widely used policies to achieve no-regret play is the so-called "followthe-regularized-leader" (FTRL) family of algorithms and its variants [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Shalev-Shwartz | Convex repeated games and Fenchel duality[END_REF]. To motivate the analysis to come, we begin with an archetypal FTRL method, the exponential / multiplicative weights algorithm, also known as Hedge [START_REF] Auer | Gambling in a rigged casino: The adversarial multi-armed bandit problem[END_REF][START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF].

3.1.

A gentle start. We begin our discussion with a "stimulus-response" approach in the spirit of Erev & Roth [START_REF] Erev | Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria[END_REF]: First, at each stage n = 1, 2, . . . , every player i ∈ N employs a mixed strategy x i,n ∈ X i to select an action α i,n ∈ A i . Subsequently, to measure the performance of their pure strategies over time, each player further maintains a score variable which is updated recursively as

y iαi,n+1 = y iαi,n + u i (α i ; α -i,n ) for all α i ∈ A i . (6)
In words, y iαi,n simply tracks the cumulative payoff of the pure strategy α i ∈ A i up to time n (inclusive). 2 As such, this score can be treated as a propensity to play a given pure strategy at any given stage: the strategies α i ∈ A i with the highest propensity scores y iαi,n+1 should be played with higher probability at stage n + 1.

The most widely used instantiation of this stimulus-response mechanism is the logit choice rule

Λ i (y i ) ≡ (exp(y iαi )) αi∈Ai αi∈Ai exp(y iαi ) (7)
which means that each player selects an action with probability that is exponentially proportional to its score. In this way, we obtain the exponential / multiplicative weightsor Hedge -algorithm

y i,n+1 = y i,n + γ n v i (α n ) x i,n+1 = Λ i (y i,n+1 ) α i,n+1 ∼ x i,n+1 (Hedge)
where γ n is the algorithm's "learning rate". For an introduction to the literature on (Hedge), see [START_REF] Arora | The multiplicative weights update method: A meta-algorithm and applications[END_REF][START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] 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-response" 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.

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 stimulus-response 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 i ∈ N when the meaning can be inferred from the context; also, to stress the distinction between "strategy-like" and "payoff-like" variables, we will write throughout Y i := R Ai and Y := i Y i for the game's "payoff space", in direct analogy to X i and X = i X i for the game's strategy space.

With all this in hand, consider the following general class of regularized learning methods:

Aggregate payoff information (stimulus):

Y i,n+1 = Y i,n + γ n vi,n
Update choice probabilities (response):

X i,n+1 = Q i (Y i,n+1 ) (RL)
In tune with (Hedge), the various elements of (RL) are defined as follows:

(1) X i,n ∈ X i denotes the mixed strategy of player i at time n = 1, 2, . . .

(2) Y i,n ∈ Y i is a "score vector" that measures the performance of the player's actions over time. (3) Q i : Y i → X i is a "regularized choice map" that maps score vectors to choice probabilities. (4) vi,n is a surrogate / approximation of the mixed payoff vector v i (X n ) of player i at time n. (5) γ n > 0 is a step-size / sensitivity parameter of the form γ n ∝ 1/n ℓγ for some ℓ γ ∈ [0, 1]. In words, at each stage of the process, every player i ∈ N observes -or otherwise estimates -a proxy vi,n of their individual payoff vector; subsequently, players augment their actions' scores based on this information, they select a mixed strategy via the regularized choice map Q i , and the process repeats. To streamline our presentation, we discuss in detail the precise definition of v and Q in Sections 3.3 and 3.4 below, and we present a series of examples of (RL) in Section 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 v(X n ). 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 to 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 vn as

vn = v(X n ) + U n + b n (8)
where

b n = E[v n | F n ] -v(X n ) and U n = vn -E[v n | F n ] (9)
respectively denote the offset and the random error of vn relative to v(X n ). To streamline our presentation, we will also assume that ∥b n ∥ = O(1/n ℓ b ) and ∥U n ∥ = O(n ℓσ ) for some ℓ b , ℓ σ ≥ 0; we discuss the specifics of these bounds later in the paper.

3.4.

From scores to strategies. Regarding the "scores-to-strategies" step of (RL), we will follow the classical approach of Shalev-Shwartz [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] and assume that each player is employing a regularized choice map of the general form

Q i (y i ) = arg max xi∈Xi {⟨y i , x i ⟩ -h i (x i )} for all y i ∈ Y i . (10)
In the above, the regularizer h i : X i → R acts as a penalty that smooths out the "hard" argmax correspondence y i → arg max xi∈Xi ⟨y i , x i ⟩. 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 a certain degree of uncertainty in their choice of strategy [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Shalev-Shwartz | Convex repeated games and Fenchel duality[END_REF].

To ease notation, we will work with kernelized regularizers of the form

h i (x i ) = αi∈Ai θ(x iαi ) (11)
for some continuous function θ : [0, 1] → R with inf z∈(0,1] θ ′′ (z) > 0. We will also say that the players' regularizers are steep if lim z→0 + θ ′ (z) = -∞, and non-steep otherwise.

Example 3.1. A standard family of kernelized regularizers is given by

θ(z) = z ρ /[ρ(ρ -1)] for ρ ∈ (0, 2], (12)
for ρ ∈ (0, 1) ∪ (1, 2] and θ(z) = z log z for ρ = 1 [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF][START_REF] Zimmert | Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits[END_REF]. This family includes:

• For ρ = 2, Eq. ( 12) boils down to the quadratic regularizer θ(z) = z 2 /2, which in turn yields the Euclidean projection map

Q i (y i ) = Π Xi (y i ) ≡ arg min xi∈Xi ∥y i -x i ∥ 2 . (13)
• For ρ = 1, Eq. ( 12) yields the entropic regularizer θ(z) = z log z, which in turn leads the logit choice map [START_REF] Basu | Strategy subsets closed under rational behavior[END_REF]. • For ρ = 1/2, we obtain the fractional power regularizer θ(z) = -4 √ z that underlies the Tsallis-INF algorithm of [START_REF] Abernethy | Fighting bandits with a new kind of smoothness[END_REF][START_REF] Zimmert | Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits[END_REF] (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 "follow-the-regularized-leader" (FTRL) method of Shalev-Shwartz & Singer [START_REF] Shalev-Shwartz | Convex repeated games and Fenchel duality[END_REF] is obtained when players observe their full payoff vectors, that is, vi,n = v i (X n ). In this case, (RL) boils down to the deterministic update rule

Y i,n+1 = Y i,n + γ n v i (X n ) X i,n+1 = Q i (Y i,n+1 )
or, more explicitly

X i,n+1 = arg max xi∈Xi n k=1 γ k u i (x i ; X -i,k ) -h i (x i ) (FTRL)
For a detailed discussion of (FTRL), see [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF]. We only note here that, as a special case, when (FTRL) is run with the logit choice setup of Eq. ( 7), a standard calculation yields the exponential / multiplicative weights (Hedge) [START_REF] Auer | Gambling in a rigged casino: The adversarial multi-armed bandit problem[END_REF][START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Vovk | Aggregating strategies[END_REF].

♢ Algorithm 2 (Optimistic FTRL). A notable variant of FTRL -originally due to Popov [START_REF] Popov | A modification of the Arrow-Hurwicz method for search of saddle points[END_REF] and subsequently popularized by Rakhlin & Sridharan [START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF] -is the so-called optimistic FTRL method. This scheme employs an "optimistic" correction intended to anticipate future steps, and it updates as

Y i,n+1 = Y i,n + γ n [2v i (X n ) -v i (X n-1 )] (Opt-FTRL) with X i,n = Q i (Y i,n
). As a special case, if (Opt-FTRL) is run with the logit choice map [START_REF] Basu | Strategy subsets closed under rational behavior[END_REF], we obtain the familiar update rule known as optimistic multiplicative weights (OMW) [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF][START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF][START_REF] Syrgkanis | Fast convergence of regularized learning in games[END_REF].

Compared to (FTRL), the gain vector

vn = 2v(X n ) -v(X n-1 ) of (Opt-FTRL) has offset b n = v(X n ) -v(X n-1 ) relative to v(X n ).
Thus, even though (Opt-FTRL) assumes full access to the players' mixed payoff vectors, it 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 or 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

IWE iαi (x) = 1{α i = α i } x iαi u i (α) for all α i ∈ A i , i ∈ N , (IWE)
where x ∈ X is the players' strategy profile, and α ∈ A is drawn according to x. This estimator is at the heart of the online learning literature [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF] and it leads to the following methods:

Algorithm 3 (Bandit FTRL). Plugging (IWE) directly into (RL) yields the bandit FTRL policy

Y i,n+1 = Y i,n + γ n IWE i ( Xn ) X i,n+1 = Q i (Y i,n+1 ) (B-FTRL)
where (IWE) is sampled at the mixed strategy profile

Xi,n = (1 -δ n )X i,n + δ n unif Ai (14)
for some "explicit exploration" parameter δ n ∝ 1/n ℓ δ , ℓ δ > 0, which specifies the mix between X i,n and the uniform distribution unif Ai on A i . As we discuss in the sequel, this combination of (IWE) with the explicit exploration mechanism [START_REF] Coucheney | Penalty-regulated dynamics and robust learning procedures in games[END_REF] means that the surrogate payoff vector vn = IWE( Xn ) used to update (B-FTRL) has offset and noise bounded respectively as

b n = O(δ n ) and U n = O(1/δ n ).
Two special cases of (B-FTRL) that have attracted significant attention in the literature are:

(1) The exponential weights algorithm for exploration and exploitation (EXP3) [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Cesa-Bianchi | Prediction, Learning, and Games[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF], obtained by running (B-FTRL) with the logit choice map ( 7). (2) The Tsallis implicitly normalized forecaster (Tsallis-INF) [START_REF] Abernethy | Fighting bandits with a new kind of smoothness[END_REF][START_REF] Audibert | Regret bounds and minimax policies under partial monitoring[END_REF][START_REF] Zimmert | An optimal algorithm for stochastic and adversarial bandits[END_REF][START_REF] Zimmert | Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits[END_REF] that was proposed as a more efficient alternative to EXP3, and which updates as

X i,n = arg max xi∈Xi ⟨Y i,n , x i ⟩ + 4 αi∈Ai √ x iαi (Tsallis-INF)
i.e., as (B-FTRL) with the fractional power regularizer θ(z) = -4 √ z of Example 3.1.

♢

For illustration purposes, we provide some more examples of (RL) in Appendix B.

First results: resilience to strategic deviations

We are now in a position to 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 & Zapechelnyuk [START_REF] Viossat | No-regret dynamics and fictitious play[END_REF].

A B C D A (1, 1) (1, 2/3) (0, 0) (0, -1/3) B (2/3, 1) (2/3, 2/3) (-1/3, 0) (-1/3, -1/3) C (0, 0) (0, -1/3) (1, 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 (D, D) with probability 1/2 each, the resulting distribution of play z ∈ ∆(A)

satisfies u i (α i ; z -i ) -u i (z) ≤ -1/6 for all α i ∈ {A, B, C, D}, i = 1, 2.
As a result, the players' regret under z n ≡ z is negative, even though both players play strictly 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 n under (RL), viz.

L(X) := n cl{X k : k ≥ n} ≡ {x ∈ X : X n k → x for some subsequence X n k of X n }.
(15) In words, L(X) is the set of limit points of X n or, equivalently, the smallest subset of X to which X n converges. Clearly, the simplest instance of a limit set is when L(X) is a singleton, i.e., when X n converges to a point. This case has attracted significant interest in the literature: for example, if L(X) = {x * } then, for certain special cases of (RL), it is known that x * is a Nash equilibrium of Γ [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF]. However, beyond this relatively simple regime, the structure of the limit sets of (RL) could be arbitrarily complicated and their rationality properties are not 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 said to be resilient to strategic deviations -or simply resilient -if, for every deviation x i ∈ X i of every player i ∈ N , we have

u i (x * ) ≥ u i (x i , x * -i ) for some x * ∈ S. (16)
Informally, S is resilient if every unilateral deviation from S is deterred by some (possibly different) element thereof. In particular, if S is a singleton, we immediately recover the definition of a Nash equilibrium; beyond this case however, other examples include the set of undominated strategies of a game, the support face of the equilibria of two-player zero-sum games, etc. Importantly, as we show below, the limit sets of (RL) are resilient in all games: Theorem 1. Let X n , n = 1, 2, . . . , be the sequence of play generated by (RL) with stepsize / gain parameters ℓ γ > 2ℓ σ and ℓ b > 0. Then, with probability 1, the limit set L(X) of X n is resilient.

Corollary 1. With assumptions as above, if L(X) = {x * }, x * is a Nash equilibrium w.p.1.
Proof sketch. The proof of Theorem 1 boils down to two interleaved arguments that we detail in Appendix C. The first hinges on showing that, if P(L(X) = S) > 0 for some non-random S ⊆ X , S must be resilient. This is argued by contradiction: if p i ∈ X i is a unilateral deviation violating Definition 1, we must also have

lim inf n→∞ [u i (p i ; X -i,n ) -u i (X n )]
> 0 with positive probability. However, the existence of a strategy that consistently outperforms X n runs contrary to the fact that strategies that (RL) selects against underperforming strategies. We make this intuition precise via an energy argument that leverages a series of results from martingale limit theory (which is where the requirements for γ n , b n and U n come in). Then, to get the stronger statement that the random set L(X) is resilient w.p.1, we show that the above remains true if p i is replaced by a deviation q i which is close enough to p i and has rational entries. Since there is a countable number of such profiles, we can use a 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 (RL), so some remarks are in order. First, we should point out that the requirements ℓ b > 0 and 2ℓ σ < ℓ γ are a priori implicit because they depend on the offset and magnitude statistics of the feedback sequence vn . 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 ℓ b = ℓ γ while, for Algorithm 3, we have ℓ b = ℓ σ = ℓ δ . In this way, when instantiated to Algorithms 1-3 (and special cases thereof), Theorem 1 yields the following corollary: Corollary 2. Suppose that Algorithms 1-3 are run with ℓ γ ∈ (0, 1] and, for Algorithm 3, ℓ δ ∈ (0, ℓ γ /2). Then, with probability 1, the limit set L(X) of X n is resilient. Now, since Theorem 1 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.1 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 idea 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 -a dynamic requirement. We address this question in detail in the next section.

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 a payoff-improving deviation may be countered by an action profile where the deviator also 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 on a much more stringent criterion of strategic stability, namely that any deviation from the set in question incurs a cost to the deviating agent.

Club sets. To make all this precise, define the better-reply correspondence of player i ∈ N

as btr i (x) = {x ′ i ∈ X i : u i (x ′ i ; x -i ) ≥ u i (x)} (17)
and write btr = i btr i for the product correspondence btr(

x) = btr 1 (x)ו • •×btr N (x).
[In words, btr i assigns to each x ∈ X those strategies of player i that are (weakly) better against x than x i .] In addition, given a product of pure strategies C = i∈N C i with C i ⊆ A i for all i ∈ N , let S = ∆(C) 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 repliesa club set for short -if it is closed under btr, i.e., btr(S) ⊆ S; finally, S is said to be minimally club (m-club) if it does not admit a proper club subset. 3 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 [START_REF] Ritzberger | Evolutionary selection in normal-form games[END_REF], who introduced the concept:

(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) = S (implying in turn that S cannot contain any dominated strategies, including iteratively dominated ones). (3) Any m-club set S contains an essential equilibrium component, i.e., a component of Nash equilibria such that every small perturbation of the game admits a nearby equilibrium; in addition, this component has full support on S, i.e., it employs all pure strategy profiles that lie in S. 4 3 Analogously to club sets, S ∈ P(X ) is said to be closed under rational behavior (curb) if it is closed under best replies, i.e., br(S) ⊆ S [START_REF] Basu | Strategy subsets closed under rational behavior[END_REF]. Clearly, club sets are also curb, but the converse does not hold, cf. [START_REF] Ritzberger | Evolutionary selection in normal-form games[END_REF]. 4 Formally, a component X * of Nash equilibria of Γ is essential if, for all ε > 0, there exists δ > 0 such that any perturbation of the payoffs of Γ by at most δ produces a Nash equilibrium that is ε-close to X * [START_REF] Van Damme | Stability and perfection of Nash equilibria[END_REF]. 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 [START_REF] Kohlberg | On the strategic stability of equilibria[END_REF], including robustness to strategic payoff perturbations. For an in-depth discussion, see van Damme [START_REF] Van Damme | Stability and perfection of Nash equilibria[END_REF].

Going back to our 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 a tolerance level ε > 0. We then say that S is:

(1) Stochastically stable if, for every neighborhood U of S in X , there exists a neighborhood U 1 of S such that

P(X n ∈ U for all n = 1, 2, . . . ) ≥ 1 -ε whenever X 1 ∈ U 1 . (18)
(2) Stochastically attracting if there exists a neighborhood U 1 of S such that

P(lim n→∞ dist(X n , S) = 0) ≥ 1 -ε whenever X 1 ∈ U 1 . (19)
(3) Stochastically asymptotically stable if it is stochastically stable and attracting.

(4) Irreducibly stable if S is stochastically asymptotically stable and it does not admit a strictly smaller stochastically asymptotically subset S ′ with supp(S ′ ) ⊊ supp(S).

With all this in hand, our main result below provides a sharp characterization of strategic stability in the context of regularized learning: Theorem 2. Fix some set S ∈ P(X ) and suppose that (RL) is run with a steep regularizer and step-size / gain parameters ℓ γ ∈ [0, 1], ℓ b > 0, and ℓ σ < 1/2. Then:

(1) S is stochastically asymptotically stable under (RL) if and only if it is a club set.

(2) S is irreducibly stable under (RL) if and only if it 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 a club set, and let X n , n = 1, 2, . . . , be the sequence of play generated by (RL) with parameters ℓ γ ∈ [0, 1], ℓ b > 0, and ℓ σ < 1/2. Then, for all ε > 0, there exists an (open, unbounded ) initialization domain D ⊆ Y such that, with probability at least 1 -ε, we have

dist(X n , S) ≤ Cφ(c 1 -c 2 n k=1 γ k ) whenever Y 1 ∈ D (20)
where C, c 1 , c 2 are constants (C, c 2 > 0), and the rate function φ is given by φ

(z) = (θ ′ ) -1 (z) if z > lim z→0 + θ ′ (z)
, and φ(z) = 0 otherwise.

Specifically, if we instantiate Theorem 3 to Algorithms 1-3, we get the explicit estimates:

Corollary 3. Suppose that Algorithms 1-3 are run with ℓ γ ∈ [0, 1] and, for Algorithm 3, ℓ δ ∈ (0, 1/2). Then, with notation as in Theorem 3, X n converges to S at a rate of

dist(X n , S) ≤ C •      [1 -c n k=1 γ k ] + if θ(z) = z 2 /2 # Euclid. proj. exp -c n k=1 γ k if θ(z) = z log z # logit choice 1 c + n k=1 γ k 2 if θ(z) = -4 √ z # Tsallis maps (21)
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. Proof sketch. The proof of Theorems 2 and 3 is quite involved so we defer it to Appendix D. At a 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" to produce a suitable Lyapunov-like function for S. In more detail, the minimization of each individual energy function implies that the score variable Y n of (RL) diverges along an "astral direction" in the payoff space Y -i.e., it escapes to infinity along the interior of a certain convex cone of Y [START_REF] Dudík | Convex analysis at infinity: An introduction to astral space[END_REF]. Because this minimization occurs at infinity, the aggregation of offsets and random errors in (RL) affords some extra "wiggle room" in our martingale analysis, so we are able to show that X n = Q(Y n ) remains close to S under a much wider range of parameters compared to Theorem 1. Then, a series of convex analysis arguments in the spirit of [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] coupled with the definition of Q allows us to show that the escape of Y n 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 noncostly (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 n , z⟩ [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF]. The irreducible stability of m-club sets then follows by invoking this criterion reductively for any potentially stable subset S ′ of S. ■

Discussion and concluding 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 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 readily implies that a pure strategy profile is stochastically asymptotically stable under (RL) if and only if it is a strict Nash equilibrium. A version of this equivalence was only recently proved in [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF] and [START_REF] Giannou | Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information[END_REF] (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-generic equilibrium components that cannot be treated otherwise by the existing theory.

The above also places severe restrictions on which components of Nash equilibria can be stable and attracting under (RL): if an equilibrium component does not span a club set, it cannot be asymptotically stable (a fact which explains the behavior seen in the Entry Deterrence game in Fig. 1). This observation goes a long way toward explaining why regularized learning correctly identifies the support of Nash equilibria in 2-player zero-sum games (but cannot go further), and also serves to illustrate why the convergence of optimistic methods is destroyed in the presence of randomness and uncertainty [START_REF] Chavdarova | Reducing noise in GAN training with variance reduced extragradient[END_REF][START_REF] Hsieh | Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling[END_REF]. By this token, Theorem 2 can be seen as a trade-off between how robust versus how informative a learning prediction is from a strategic perspective. We find this interpretation of Theorem 2 particularly appealing as it opens the door to several fruitful research directions.

Finally, we should stress that Theorems 2 and 3 guarantee convergence even with a constant step-size. Together with the finite-time convergence guarantees of Corollary 3 for projection-based methods, this feature is a testament to the robustness of club sets as, in the presence of uncertainty, convergence invariably requires a vanishing step-size which can slow things down to a crawl. We find this robust convergence landscape particularly intriguing for future research on the topic.

Lemma A.4 (Kolmogorov's inequality). Let Z n ∈ R, n = 1, 2, . . . , be a martingale difference sequence that is bounded in L 2 . Then:

P max k≤n k ℓ=1 Z ℓ ≥ ε ≤ 1 ε 2 E n k=1 Z k 2 for all ε > 0. (A.14)
Lemma A.5 (Doob's maximal inequality). Let Z n ∈ R, n = 1, 2, . . . , be a martingale difference sequence that is bounded in L p for some p ≥ 1. Then

P max k≤n |Z k | > ε ≤ 1 ε p E |Z n | p for all ε > 0. (A.15)
Lemma A.6 (Burkholder-Davis-Gundy inequality). Let Z n , n = 1, 2, . . . , be a martingale difference sequence in R n . Then, for all p > 1, there exist constants c p , C p that depend only on p and are such that

c p E n k=1 ∥Z k ∥ 2 2 p/2 ≤ E max k≤n k ℓ=1 Z ℓ p 2 ≤ C p E n k=1 ∥Z k ∥ 2 2 p/2 . (A.16)
Lemma A.7 (Robbins-Siegmund). Let F n , n = 1, 2, . . . , be a filtration on a complete probability space (Ω, F, P), and suppose that the sequences X n , L n and K n F n -measurable, nonnegative, and such that

E[X n+1 | F n ] ≤ X n (1 + L n ) + K n with probability 1. (A.17)
Then, X n converges to some random variable X ∞ with probability 1 on the event

∞ n=1 L n < ∞ and ∞ n=1 K n < ∞ . (A.18)
Appendix 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 in the general framework of (RL). To lighten notation, we will assume that b n , U n and vn are respectively bounded as

∥b n ∥ ∞ ≤ B n ∥U n ∥ ∞ ≤ σ n and ∥v n ∥ ∞ ≤ M n (B.1)
and we will set

G := max i∈N max α∈A |v i (α)| (B.2) so we can take M n = G + B n + σ n in (B.1
). We will also make free use of the fact that v is Lipschitz continuous on X , and we will write L for its Lipschitz modulus in the (L 1 , L ∞ ) pair of norms on X and Y respectively, viz.

∥v(x ′ ) -v(x)∥ ∞ ≤ L∥x ′ -x∥ 1 for all x, x ′ ∈ X . (B.3)
We now proceed to establish the required bounds for Algorithms 1-3:

Algorithm 1. Since vn = v(X n ), we readily get b n = U n = 0 by definition, so Algorithm 1 fits the scheme (RL) for free with ℓ b = ∞, ℓ σ = 0. ♢ Algorithm 2. For the case of (Opt-FTRL), we have

vn = 2v(X n ) -v(X n-1 ) so b n = v(X n ) -v(X n-1
), which is F n -measurable. We thus get

∥b n ∥ ∞ = ∥E[v n | F n ] -v(X n )∥ ∞ ≤ E[∥v(X n ) -v(X n-1 )∥ ∞ | F n ] ≤ L E[∥X n -X n-1 ∥ | F n ] # by (B.3) = L E[∥Q(Y n ) -Q(Y n-1 )∥ ∞ | F n ] # by (Opt-FTRL) ≤ (L/K) E[∥Y n -Y n-1 ∥ ∞ | F n ] # by Lemma A.1 ≤ γ n (L/K) E[2v(X n ) -v(X n-1 ) | F n ] # by (Opt-FTRL) ≤ 3LG/K • γ n # by (B.2) = O(γ n ) = O(1/n ℓγ ) (B.4)
Moreover, given that v is F n -measurable, we readily get U n = 0. ♢ Algorithm 3. Since αn is sampled according to Xn = (1-δ n )X i,n +δ n unif Ai (cf. Eq. ( 14) in Section 3), we readily obtain

E[v i,n | F n ] = v i ( Xn )
, and hence, by (B.3), we get

B n = O(∥ Xn -X n ∥) = O(δ n ) = O(1/n ℓ δ ). (B.5) Moreover, since Xiαi,n ≥ δ n /A i , it follows that ∥v n ∥ ∞ = O(1/δ n ) = O(n ℓ δ ).

♢

For comparison purposes, we illustrate the algorithms' behavior in a simple 2 × 2 × 2 game in Fig. 2 in Appendix E.

B.2. Further algorithms and illustrations.

To demonstrate the breadth of (RL) as an algorithmic template, we provide below some more examples of algorithms from the game-theoretic literature that can be recast as special cases thereof (see also Table 1 for a recap).

Algorithm 4 (Mirror-prox). A progenitor of (Opt-FTRL) is the so-called mirror-prox (MP) algorithm [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF][START_REF] Nemirovski | Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF], which updates as:

Ỹn = Y n + γ n v(X n ) Y n+1 = Y n + γ n v( Xn ) Xn = Q( Ỹn ) X n+1 = Q(Y n+1 ). (MP)
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 Xn is generated with payoff information from X n , not Xn-1 . This method has been used extensively in the literature for solving variational inequalities and two-player, zero-sum games, cf. Juditsky et al. [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF] and references therein.

A calculation similar to that for (Opt-FTRL) shows that Algorithm 4 has B n = O(1/n ℓγ ) and σ n = 0 because the algorithm has no further randomization. ♢ Algorithm 5 (Clairvoyant multiplicative weights). A recent variant of (Hedge) is the so-called clairvoyant multiplicative weights (CMW) algorithm [START_REF] Piliouras | Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu[END_REF]

Y i,n+1 = Y i,n + γ n v i (X n+1 ) X i,n+1 = Λ i (Y i,n+1 ). (CMW)
The main difference between (CMW) and (Hedge) is that the proxy payoff vector vn in (CMW) is based on the future state X n+1 and not the current state X n . To perform this "clairvoyant" update, the players of the game must coordinate to solve an implicit fixed

Representative Regularizer (θ) Feedback Bias (Bn) Variance (σn)

Algorithm 1 Hedge z log z full info 0 0 Algorithm 2 OMW z log z full info O(1/n ℓγ ) 0 Algorithm 3 EXP3 z log z payoff O(1/n ℓ δ ) O(n ℓ δ ) Algorithm 3 Tsallis-INF -4 √ z payoff O(1/n ℓ δ ) O(n ℓ δ ) Algorithm 4 MP general full info O(1/n ℓγ ) 0 Algorithm 5 CMW z log z full info O(1/n ℓ δ ) 0
Table 1: A range of algorithms adhering to the general template (RL) and their bias and variance characteristics when run with a step-size sequence of the form γn = γ/n ℓγ , ℓγ ∈ (0, 1], and, where applicable, a sampling parameter δn = δ/n ℓ δ .

point problem, so (CMW) is only meaningful when one has access to the payoff function v(•). In this regard, (CMW) can be seen as a Bregman proximal point method in the general spirit of Bauschke et al. [START_REF] Bauschke | Bregman monotone optimization algorithms[END_REF].

To cast (CMW) as an instance of the generalized template (RL), simply note that the sequence of input signals is given by vn = v(X n+1 ), so

U n = 0 and b n = v(X n+1 )-v(X n ) = O(γ n ) = O(1/n ℓγ ). ♢ Appendix C. Proof of Theorem 1
Our main goal in this appendix will be to prove Theorem 1 on the resilience properties of (RL). For convenience, we restate below the relevant result for ease of reference: Theorem 1. Let X n , n = 1, 2, . . . , be the sequence of play generated by (RL) with stepsize / gain parameters ℓ γ > 2ℓ σ and ℓ b > 0. Then, with probability 1, the limit set L(X) of X n is resilient.

Proof. Our proof that L(X) is resilient hinges on an energy-based technique that we will employ repeatedly in other parts of our analysis. To begin, introduce a player-strategy deviation pair (i, z i ), and say that a set is resilient to (i, z i ) if there exists an element of the set, say x * , which counters said deviation, i.e., such that u i (x * ) ≥ u i (z i ; x * -i ). In this specific case, our proof proceeds by contradiction, namely by assuming that, with positive probability, L(X) is not resilient to (i, z i ). The main steps of our proof unfold as follows:

Step 1. Assume that L(X) is not resilient to (i, z i ) with positive probability. Then there exists c, ϵ, n 0 > 0 such that

P(u i (z i ; X n,-i ) ≥ u i (X n ) + c for all n ≥ n 0 ) ≥ ϵ. (C.1) Proof of Step 1. The function f : x ∈ X → u i (z i ; x -i ) -u i (x) is continuous and X is compact, so there is a definite function η ≡ η(δ) such that if ∥x -x ′ ∥ ≤ η(δ), then |f (x) -f (x ′ )| ≤ δ. Now, by assumption, {∀x * ∈ L(X), u i (z i ; x * -i ) > u i (x *
)} is of positive probability. We thus get

0 < P ∀x * ∈ L(X), u i (z i ; x * -i ) > u i (x * ) = P inf x * ∈L(X) u i (z i ; x * -i ) -u i (x * ) > 0 (C.2a) = P m>0 inf x * ∈L(X) u i (z i ; x * -i ) -u i (x * ) > 2 -m (C.2b) ≤ 1 2 P ∀x * ∈ L(X), u i (z i ; x * -i ) -u i (x * ) > 2c (C.2c)
for some c > 0 in (C.2c), and where (C.2a) is because L(X) is closed -hence compactalmost surely. Therefore, by definition of η(•),

0 < P ∀x * ∈ X , dist(x * , L(X)) ≤ η(c) ⇒ u i (z i ; x * -i ) -u i (x * ) > c = 2ϵ (C.2d) Now, let n 0 such that P{∀n ≥ n 0 , dist(X n , L(X)) ≤ η(c)} > 1 -ϵ 2 .
Then by construction, we get

P{∀n ≥ n 0 , u i (z i ; X n,-i ) > u i (X n ) + c} > ϵ. (C.
3) and our proof is complete.

■

Intuitively, the existence of an action that consistently outperforms X n 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

F i,n = h i (z i ) + h * i (Y i,n ) -⟨Y i,n , z i ⟩ (C.4)
Then, by Lemma A.2 in Appendix A, we readily get that

F i,n+1 ≤ F i,n -γ n ⟨v i,n , z i -X i,n ⟩ + γ 2 n 2κ h ∥v i,n ∥ 2 ∞ . (C.5)
where, in obvious notation, we are identifying z i ∈ A i with the corresponding vertex e zi of X i = ∆(A i ). To proceed, the main idea will be to relate γ n ⟨v i,n , z i -X i,n ⟩ to its "perfect" counterpart γ n ⟨v i (X n ), z i -X i,n ⟩. We formalize this below.

Step 2. If L(X) is not resilient to (i, z i ), there exists n 1 ≥ n 0 such that, with probability ε ′ /2 > 0, and for all n ≥ n 1 , we have

F i,n ≤ F i,n0 - c 2 n k=n0 γ k . (C.6)
Proof of Step 2. With probability ε ′ and for all n ≥ n 0 , we have

γ n ⟨v i,n , z i -X i,n ⟩ = γ n ⟨v i (X n ), z i -X i,n ⟩ + γ n ⟨U i,n , z i -X i,n ⟩ + γ n ⟨b i,n , z i -X i,n ⟩ ≥ c + ⟨U i,n , z i -X i,n ⟩ + ⟨b i,n , z i -X i,n ⟩ γ n . (C.7)
The combination of Eqs. (C.5) and (C.7) then provides the following upper bound of F i,n+1 :

F i,n+1 ≤ F i,n -cγ n + γ n ⟨U i,n , z i -X i,n ⟩ + γ n ⟨b i,n , z i -X i,n ⟩ + γ 2 n 2κ h ∥v i,n ∥ 2 ∞ ≤ F i,n0 -c n k=n0 γ k + n k=n0 ∥v k,i ∥ 2 ∞ 2κ h γ 2 k + n k=n0 γ k ⟨U k,i , z i -X k,i ⟩ E U,n + n k=n0 γ k ⟨b k,i , z i -X k,i ⟩ E b,n . (C.8)
We are thus left to show is that c n k=n0 γ k is the dominant term above. To do so, we proceed to examine each term individually:

• Second-order term: We first deal with the second-order term

n k=n0 ∥v k,i ∥ 2 ∞ 2κ h γ 2 k . By expanding the ∥v k,i ∥ 2 ∞ , we readily get n k=n0 ∥v k,i ∥ 2 ∞ γ 2 k τ n = O n k=1 γ 2 k (1 + B 2 k + σ 2 k ) n k=1 γ k . (C.9)
However, by our assumptions on the parameters of (RL), we readily get

lim n→∞ γ 2 n (1 + B 2 n + σ 2 n ) γ n = 0 (C.10)
so we conclude that

lim n→∞ n k=1 γ 2 k (1 + B 2 k + σ 2 k ) n k=1 γ k = 0 (C.11)
by the Stolz-Cesàro theorem.

• Bias term: By far the most immediate, the bias term E b,n is bounded as

E b,n ≤ 2 n k=n0 ∥b i,n ∥ ∞ γ k ≤ 2 n k=n0 B k γ k = o n k=n0 γ k as n → ∞. (C.12)
• Noise term: Finally, the noise term E U,n is bounded by means of the Azuma-Hoeffding inequality, cf. Lemma A.3 in Appendix A. Specifically, with probability at least 1 -ε ′ /2, we have

E U,n := n k=n0 γ k ⟨U k,i , z i -X k,i ⟩ ≤ 2 n k=n0 ∥U k,i ∥ 2 ∞ γ 2 k 1/2 2 log 4n 2 ε ′ ≤ 2 n k=n0 σ 2 k γ 2 k 1/2 2 log 4n 2 ε ′ . (C.13)
for all n ≥ n 0 . To proceed, note that a second application of the Stolz-Cesàro theorem yields

n k=n0 σ 2 k γ 2 k = o( n k=n0 γ k ) and, moreover, note that log(4n 2 /ε ′ ) = O( n k=n0 γ k ).
Taking square roots and multiplying then yields that

E U,n = o n k=n0 γ k (C.14)
with probability at least 1 -ε ′ /2. We are now in a position to establish the bound Eq. (C.6). Indeed, putting Eqs. (C.11), (C.12) and (C.14) together, we readily infer that there exists n 1 ≥ n 0 such that, with probability at least 1 -ε ′ /2, we have

n k=n0 γ k ⟨U k,i , z i -X k,i ⟩ + n k=n0 γ k ⟨b k,i , z i -X k,i ⟩ + n k=n0 ∥v k,i ∥ 2 ∞ 2κ h γ 2 k ≤ c 2 n k=n0 γ k (C.15)
for all n ≥ n 1 . This proves Eq. (C.6) and concludes our proof.

■

Summarizing the above, we have shown that, with probability at least 1 -ε ′ /2, we have

F i,n+1 ≤ F n0 - c 2 n k=n0 γ k → -∞ as n → ∞. (C.16)
Since F is nonnegative (by Lemma A.2), we have established that the event where L(X) is not resilient to (i, z i ) 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 3. L(X) is almost-surely resilient.

Proof of Step 3. The key point of the proof is the observation that a closed set is resilient if and only if it is rationally resilient, i.e., it nullifies all rational deviations z i ∈ X i ∩ Q Ai (which are countably many). Indeed, if L(X) is not resilient with positive probability, then, likewise, L(X) will not be rationally resilient with positive probability either. Because there are countably many rational deviations, there must be a rational strategic deviation (i, z i ) (with z i ∈ X i ∩ Q Ai ) to which L(X) is not resilient. This comes in contradiction with the conclusions of Step 2.

■

This concludes the last required step, so the proof of Theorem 1 is now complete. ■ Appendix D. Proof of Theorems 2 and 3

In this last appendix, our goal is to prove our characterization of club sets, namely:

Theorem 2. Fix some set S ∈ P(X ) and suppose that (RL) is run with a steep regularizer and step-size / gain parameters ℓ γ ∈ [0, 1], ℓ b > 0, and ℓ σ < 1/2. Then:

(1) S is stochastically asymptotically stable under (RL) if and only if it is a club set.

(2) S is irreducibly stable under (RL) if and only if it is an m-club set.

Theorem 3. Let S ∈ P(X ) be a club set, and let X n , n = 1, 2, . . . , be the sequence of play generated by (RL) with parameters ℓ γ ∈ [0, 1], ℓ b > 0, and ℓ σ < 1/2. Then, for all ε > 0, there exists an (open, unbounded ) initialization domain D ⊆ Y such that, with probability at least 1 -ε, we have

dist(X n , S) ≤ Cφ(c 1 -c 2 n k=1 γ k ) whenever Y 1 ∈ D (20)
where C, c 1 , c 2 are constants (C, c 2 > 0), and the rate function φ is given by φ(z) = (θ ′ ) -1 (z) if z > lim z→0 + θ ′ (z), and φ(z) = 0 otherwise.

Our proof strategy will be to construct a sheaf of "linearized" energy functions which, when bundled together, yield a suitable Lyapunov-like function for S. To do so, let C = i C i denote the support of S (cf. the definition of club sets), and let

Z i = {e iα ′ i -e iαi : α i ∈ C i , α ′ i ∈ A i \ C i } (D.1) and Z = i∈N Z i (D.2)
denote the set of all pure strategic deviations from S. Then, our ensemble of candidate energy functions will be given by

E z (y) = ⟨y, z⟩ for z ∈ Z, y ∈ V * . (D.3)
The motivation for this definition is given by the following lemma.

Lemma D.1. Suppose that the sequence y n ∈ V * , n = 1, 2, . . . , has E z (y n ) → -∞ for all z ∈ Z as n → ∞. Then the sequence x n = Q(y n ) converges to S as n → ∞.

Proof. Let z = e iα ′ i -e iαi for some i ∈ N , α i ∈ C i , and α ′ i ∈ A i \ C i . Since E z (y n ) → -∞ by assumption, we get y iα ′ i ,n -y iαi,n → -∞ and hence, by Lemma A.1, we conclude that

Q iα ′ i (x n ) → 0 as n → ∞.
In turn, given that this holds for all i ∈ N and all α ′ i ∈ A i \ C i , we conclude that x n = Q(y n ) converges to S.

■

In view of the above, we will focus on showing that E z (Y n ) → -∞ for all z ∈ Z. As a first step, we establish a basic template inequality for the evolution of E z under (RL).

Lemma D.2. Fix some z ∈ Z and let E n := E z (Y n ). Then, for all n = 1, 2, . . . , we have

E n+1 ≤ E n + γ n ⟨v(X n ), z⟩ + γ n ξ n + γ n ψ n (D.4)
where the error terms ξ n and ψ n are given by

ξ n = ⟨U n ,

■

The key take-away from (D.4) is that, if X n is close to S and α

i ∈ C i , α ′ i ∈ A i \ C i , we will have ⟨v(X n ), z⟩ = v iα ′ i (X n ) -v iαi (X n ) = u i (α ′ i ; X -i,n ) -u i (α i ; X -i,n ) < 0 (D.6)
by the continuity of u i and the assumption that S is a club set. More concretely, by the definition of the better-reply correspondence, we have ⟨v(x * ), z⟩ < 0 for all x * ∈ S and all z ∈ Z (D.7)

and hence, by continuity, there exists a neighborhood B of S such that ⟨v(x), z⟩ < 0 for all x ∈ B and all z ∈ Z. (D.8)

In other words, as long as X n is sufficiently close to S, (D.4) exhibits a consistent negative drift pushing E n towards -∞.

To exploit this "dynamic consistency" property of S, it will be convenient to introduce the family of sets D(ε) = {y ∈ V * : ⟨y, z⟩ < -ε for all z ∈ Z} (D.9)

As we show below, these sets are mapped under Q to neighborhoods of S, so they are particularly well-suited to serve as initialization domains for (RL). This is encoded in the following properties:

Lemma D.3. Let x = Q(y) for some y ∈ V * . Then, for all α i , α ′ i , i ∈ N , we have x iαi ≤ φ θ(1 -) + y iα ′ i -y iαi (D.10)
with φ defined as per Theorem 3, i.e.,

φ(z) =      0 if z ≤ θ ′ (0 + ), (θ ′ ) -1 (z) if θ ′ (0 + ) < z < θ ′ (1 -), 1 if z ≥ θ ′ (1 -).
(D.11)

Corollary D.1. For all δ > 0 there exists some ε δ ∈ R such that, for all ε > ε δ and all y ∈ D ε , we have

Q iα ′ i (y i ) < δ for all α ′ i ∈ A i \ C i and all i ∈ N . (D.12)
Proof of Lemma D.3. Suppressing the player index for simplicity, the first-order stationarity conditions for the convex problem (10) readily give

y α -θ ′ (x α ) = µ -ν α , (D.13)
where µ is the Lagrange multiplier for the equality constraint α x α = 1, and ν α is the complementary slackness multiplier of the inquality constraint x α ≥ 0 (so ν α = 0 whenever x α > 0). Thus, rewriting (D.13) for some α ∈ A, we get

y α ′ -y α = θ ′ (x α ′ ) -θ ′ (x α ) + ν α -ν α ′ (D.14)
and hence

θ ′ (x α ′ ) = θ ′ (x α ) + ν α ′ -ν α + y α ′ -y α ≤ θ ′ (1 -) + ν α ′ + y α ′ -y α , (D.15)
where we used the fact that ν α ≥ 0. Now, if θ ′ (1 -) + y α ′ -y α < θ ′ (0 + ) and x α ′ > 0 (so ν α ′ = 0), we will have θ ′ (x α ′ ) < θ ′ (0 + ), a contradiction. This shows that x α ′ = 0 if θ ′ (1 -) + y α ′ -y α < θ ′ (0 + ), so (D.10) is satisfied in this case. Otherwise, if x α ′ > 0, we must have ν α ′ = 0 by complementary slackness, so (D.10) follows by applying the second branch of (D.11) to (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 n may fail to be decreasing and X n may drift away from S. On that account, it will be convenient to introduce the aggregate error processes

I n = n k=1 γ k ξ k and II n = n k=1 γ k ψ k . (D.16)
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 n→∞ I n /τ n = 0 (Sub.I) lim n→∞ II n /τ n = 0 (Sub.II)
where τ n = n k=1 γ k and both limits are to be interpreted in the almost sure sense. (2) Drift dominance:

P(I n ≤ Cτ α n /2 for all n) ≥ 1 -η (Dom.I) P(II n ≤ Cτ α n /2 for all n) ≥ 1 -η (Dom.II)
for some C > 0 and α ∈ [0, 1). In a nutshell, (Sub) posits that the aggregate error processes I n and II n 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: to establish (Dom.I). To that end, let I * n = sup 1≤k≤n |I n | and set P n := P(I * n > Cτ α n /2) so

P n ≤ E[|I n | q ] (C/2) q τ αq n ≤ c q E[ n k=1 γ 2 k ∥U k ∥ 2 ∞ q/2 ] τ αq n (D.25)
where c q is a positive constant depending only on C and q, and we used Kolmogorov's inequality (Lemma A.4) in the first step and the Burkholder-Davis-Gundy inequality (Lemma A.6) in the second.

To proceed, we will require the following variant of Hölder's inequality [9, p. 15]:

n k=1 a k b k ρ ≤ n k=1 a λρ ρ-1 k ρ-1 n k=1 a (1-λ)ρ k b ρ k (D.26) valid for all a k , b k ≥ 0 and all ρ > 1, λ ∈ [0, 1). Then, substituting a k ← γ 2 k , b k ← ∥U k ∥ 2 ∞ , ρ ← q/2 and λ ← 1/2 -1/q, (D.25) gives P n ≤ c q ( n k=1 γ k ) q/2-1 n k=1 γ 1+q/2 k E[∥U k ∥ q ∞ ] τ αq n ≤ c q n k=1 γ 1+q/2 k σ q k τ 1+(α-1/2)q n (D.27)
We now consider two cases, depending on whether the numerator of (D.27) is summable or not.

Case 1: ℓ γ (1 + q/2) ≥ 1 + qℓ σ . In this case, the numerator of (D.27) is summable under the theorem's assumptions, so the fraction in (D.27) behaves as O(1/n (1-ℓγ )(1+(α-1/2)q) ).

Case 2: ℓ γ (1 + q/2) < 1 + qℓ σ . In this case, the numerator of (D.27) is not summable under the theorem's assumptions, so the fraction in (D.27) behaves as O n 1-ℓγ (1+q/2)+qℓσ n (1-ℓγ )(1+(α-1/2)q) . Thus, working out the various exponents, a tedious -but otherwise straightforwardcalculation shows that there exists some α ∈ (0, 1) such that P n is summable as long as ℓ σ < 1/2 -1/q and 0 ≤ ℓ γ < q/(2 + q). Hence, if γ is sufficiently small relative to η, we conclude that P(I n ≤ Cτ α n /2 for all n) ≥ 1n P n ≥ 1 -η/2. (D.28)

Finally, if ℓ γ > 1/2 + ℓ σ , (Dom.I) is a straightforward consequence of (D.25) for q = 2. With all this in hand, the final steps of our proof proceed as follows:

Closedness =⇒ Stability. Our assertion follows by invoking Proposition D.1.

Stability =⇒ Closedness. Suppose that S is not club. Then there exists some pure strategy α ∈ C and some deviation α ′ ̸ ∈ C such that the deviation from α to α ′ is not costly to the deviating player. Thus, if we consider the restriction of the game to the face spanned by α and α ′ (a single-player game with two strategies), the corresponding score difference will be y α ′ ,n -y α,n ≥ k=1

γ k b k + k=1 γ k U k (D.29)
By our standing assumptions for b n and U n (and Doob's martingale convergence theorem for the latter), both k=1 γ k b k and k=1 γ k U k will be bounded from below by some (a.s.) finite random variable A 0 . Since θ is steep, it follows that, with probability 1, lim inf n→∞ (y α,n ) > 0, so C cannot be stable.

Minimality =⇒ Irreducible Stability. Suppose that S is m-club. Then, by our previous claim, S is stochastically asymptotically stable. If S contains a proper subface S ′ ⊊ 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, S 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 implies that S is club. Then, if it so happens that S is not m-club, it would contain a proper club subface 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 our proof.

■

We are only left to establish the convergence rate estimate of Theorem 3.

Proof of Theorem 3. Going back to (D.21) and invoking Lemma D.3 shows that there exist constants c 1 > 0 and c 2 ∈ R such that, for all α i ∈ A i \ C i , i ∈ N , we have

X iαi,n ≤ φ θ(1 -) + E n ≤ φ(c 2 -c 1 τ n ) (D.30)
with probability 1 on the events of (Dom). We thus get In all our experiments, we ran the EXP3 variant of bandit FTRL (B-FTRL) (cf. Algorithm 3) with step-size and sampling radius parameters γ n = 0.2 × n -1/2 and δ n = 0.1 × n -0.15 respectively. The algorithm was run for T = 10 4 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 y 1 ∈ {-1, 0, 1} 3 and perturbed by a uniform random number in [-0.1, -0.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 our experiments, we conclude that 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, 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). We illustrate these findings in Fig. 2.

Regarding Fig. 1, the payoffs of the chosen games were normalized to [-1, 1] and players are assumed to choose between two actions labeled "O" and "1". The specific tableaus are shown in the table below, next to the respective portrait (all taken from Fig. 1.

-1 1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1

Example 4 . 1 .

 41 Consider the 4 × 4 symmetric 2-player game with payoff bimatrix

Figure 1 :

 1 Figure 1: The long-run behavior of EXP3 (Algorithm 3) in four representative 2 × 2 × 2 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.

dist 1 (

 1 X n , S) ≤ i∈N αi∈Ai\Ci φ(c 2 -c 1 τ n ), (D.31)and our proof is complete.■As for the rate estimates of Corollary 3, the proof boils down to a simple derivation of the corresponding rate functions:Proof of Corollary 3. By a straightforward calculation, we have:(1) If θ(z) = z log z then φ(z) = exp(1 + z).(2) If θ(z) = -4 √ z then φ(z) = 4/z 2 . (3) If θ(z) = z 2 /2 then φ(z) = [z]1 0 . Our claims then follow immediatly from the rate estimate (20) of Theorem 2. ■ Appendix E. Numerical experiments

Figure 2 :

 2 Figure 2: The long-run behavior of Algorithms 1-3 in a 2 × 2 × 2 game. Algorithms 1 and 2 were run with a logit choice map as per (Hedge); Algorithm 3 was run with both variants, EXP3 and Tsallis-INF. All algorithms were run for 5 × 10 5 iterations with γn = 1/n 0.4 and δn = 0.1/n 0.15 ; color indicates time, with darker hues indicating later iterations. The face to the left is closed under better replies, so Xn converges quickly to said face (as per Theorems 2 and 3).

  Proof. Simply set y ← Y n+1 in E z (y), invoke the definition of the update Y n ← Y n+1 in (RL), and note that |⟨b n , z⟩| ≤ ∥z∥∥b n ∥ ∞ ≤ 2B n by the definition of Z.

	z⟩	and	ψ n = 2B n .	(D.5)

Of course, updating these scores requires the knowledge of the "what if" pure payoffs u i (α i ; α -i,n ) at each stage n, but we assume for the moment that this information is available (we will relax this assumption later on).

Acknowledgments

This work has been partially supported by the French National Research Agency (ANR) in the framework of the "Investissements d'avenir" program (ANR-15-IDEX-02), the LabEx PERSYVAL (ANR-11-LABX-0025-01), MIAI@Grenoble Alpes (ANR-19-P3IA-0003). PM is also a member of the Archimedes Unit, Athena RC, Department of Mathematics, University of Athens, and is grateful for financial support by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationEU Program.

Appendix 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 i ∈ N , and we will follow standard conventions in convex analysis [START_REF] Rockafellar | of A Series of Comprehensive Studies in Mathematics[END_REF] that treat h as an extended-real-valued function h : V → R ∪ {∞} with h(x) = ∞ for all x ∈ V \ X . With this in mind, the subdifferential of a h at x ∈ X is defined as ∂h(x) := {y ∈ Y : h(x ′ ) ≥ h(x) + ⟨y, x ′ -x⟩ for all x ′ ∈ X }, (A. [START_REF] Abernethy | Fighting bandits with a new kind of smoothness[END_REF] where Y denotes here the algebraic dual V * of V. Accordingly, the domain of subdifferentiability of h is dom ∂h := {x ∈ dom h : ∂h ̸ = ∅}, and the convex conjugate of h is defined as

for all y ∈ Y. We then have the following basic results.

Lemma A.1. Let h be a regularizer on X , and let Q : Y → X be the induced choice map. Then:

(1) Q is single-valued, and, for all x ∈ X , y ∈ Y, we have x = Q(y) ⇐⇒ y ∈ ∂h(x).

(2) For all x ∈ ri X , we have

In particular, as a special case, the logit choice map Λ is 1-Lipschitz continuous in the (L 1 , L ∞ ) pair of norms on Y and X respectively. (5) If y α -y α ′ → -∞ for some α ′ ̸ = α, then Q α (y) → 0.

Remark. Some of the properties presented in Lemma A.1 are well known in the literature on regularized learning methods (see e.g., [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] and references therein), but we provide a proof of the entire lemma for completeness.

♢

Proof of Lemma A.1. For the first property of Q, note that the maximum in [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF] is attained for all y ∈ Y because h is lower-semicontinuous (l.s.c.) and strongly convex. Furthermore, x solves [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF] if and only if y -∂h(x) ∋ 0, i.e., if and only if y ∈ ∂h(x).

For our second claim, if x ∈ ri(X ), the first-order stationarity conditions for the convex problem [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF]

because the inequality constraints x α ≥ 0 are all inactive (recall that x ∈ ri(X ) by assumption). Now, by the first part of the theorem we have x = Q(y) if and only if y ∈ ∂h(x), so we conclude that ∂h

For the fourth item, the expression Q = ∇h * is an immediate consequence of Danskin's theorem, while the Lipschitz continuity of Q follows from standard results, see e.g., [START_REF] Rockafellar | of A Series of Comprehensive Studies in Mathematics[END_REF]Theorem 12.60(b)].

For our last claim, let y n be a sequence in Y such that y α,n -y α ′ ,n → -∞ and let x n = Q(y n ). Then, by descending to a subsequence if necessary, assume there exists some ε > 0 such that x α,n ≥ ε > 0 for all n. Then, by the defining relation Q(y) = arg max{⟨y, x⟩ -h(x)} of Q, we have:

which contradicts our original assumption that y α,n -y α ′ ,n → -∞. With X compact, the above shows that x * α = 0 for any limit point x * of x n , i.e. Q α (y n ) → 0.

■

The second collection of results concerns the Fenchel coupling, an energy function that was first introduced in [START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF][START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF] and is defined as follows:

This coupling will play a major role in the proofs of Theorem 1, so we prove two of its most basic properties below.

Lemma A.2. For all p ∈ X and all y, y ′ ∈ Y, we have:

In particular, if h(0) = 0, we have

Proof of Lemma A.2. By the strong convexity of h relative to ∥•∥ (cf. Lemma A.1), we have

leading to the bound

for all t ∈ (0, 1]. The bound (A.8a) then follows by letting t → 0 + in (A.11).

For our second claim, we have

where the inequality in the second line follows from the fact that h * is (1/K)-strongly smooth [46, 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 a complete treatment, we refer the reader to Hall & Heyde [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF].

Then, for all η > 0, we have

for all n ≥ 1 -η. (A.13) Proposition D.1. Let S be a club set, fix some confidence threshold η > 0, and let X n = Q(Y n ) be the sequence of play generated by (RL). If (Sub) and (Dom) hold, there exists an unbounded initialization domain D ⊆ V * such that

Proof of Proposition D.1. Fix some z ∈ Z, let E n = E z (Y n ), and pick α ∈ [0, 1) so that (Dom) holds for some C > 0. In addition, set c = -sup x∈B ⟨v(x), z⟩ > 0, let n 0 = inf{n : cτ n > Cτ α n }, and write

where ε is such that D(ε) ⊆ B, we will have Y n ∈ D(ε) for all n. Indeed, this being trivially the case for n = 1, assume it to be the case for all k = 1, 2, . . . , n. Then, by (D.4) and our inductive hypothesis, we get

i.e., E n+1 ∈ D(ε), as claimed. Now, since E n ∈ D(ε) for all n, we conclude that

Thus, if (Sub) holds, we readily get E n → -∞ with probability 1 on the event that (Dom.I) and (Dom.II) both hold. This implies that E n → -∞, and since z ∈ Z above is arbitrary, we conclude that X n → S with probability at least 1 -2η, as claimed.

■

We are now in 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 a direct application of Proposition D.1 and a reduction to a suitable subface of X . First, regarding (Sub), the law of large numbers for martingale difference sequences [START_REF] Hall | Martingale Limit Theory and Its Application[END_REF]Theorem 2.18] shows that I n /τ n → 0 with probability 1 on the event