# The equivalence of dynamic and strategic stability under regularized learning in games

Victor Boone, Panayotis Mertikopoulos

► To cite this version:

Victor Boone, Panayotis Mertikopoulos. The equivalence of dynamic and strategic stability under regularized learning in games. NeurIPS 2023 - 37th Conference on Neural Information Processing Systems, Dec 2023, New Orleans (LA), United States. pp.1-31. hal-04307883

HAL Id: hal-04307883

https://inria.hal.science/hal-04307883v1

Submitted on 26 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# THE EQUIVALENCE OF DYNAMIC AND STRATEGIC STABILITY
UNDER REGULARIZED LEARNING IN GAMES

VICTOR BOONE* AND PANAYOTIS MERTIKOPOULOS*

**ABSTRACT.** 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.

## 1. 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* [27]. This result has

<footnote>* UNIV. GRENOBLE ALPES, CNRS, INRIA, GRENOBLE INP, LIG, 38000 GRENOBLE, FRANCE.
*E-mail addresses: victor.boone@univ-grenoble-alpes.fr, panayotis.mertikopoulos@imag.fr.
*2020 Mathematics Subject Classification. Primary 91A10, 91A26; secondary 68Q32, 62L20.
*Key words and phrases. Regularized learning; strategic stability; asymptotic stability; closedness under better replies; resilience.</footnote>
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-regularized-
leader” (FTRL) family of algorithms [47, 48] and its variants – optimistic methods
[16, 29, 43, 44, 49], HEDGE / EXP3 [4, 6, 10, 11], implicitly normalized forecasters [1, 3],
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 &
Zaechelnyuk [51] (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 [17, 25, 36–38] or
exhibits chaotic, unpredictable oscillations [13, 40]. 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” [15, 28, 53]. 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 a state is stable and attracting under the replicator dynamics if
and only it is a strict Nash equilibrium of the underlying game [28, 53].

In the context of regularized learning, [14, 21, 35] 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. [23, 24] 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 [7, 18, 22, 45]. 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 [45], 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) [7], and it satisfies all the seminal strategic stability requirements of Kohlberg & Mertens [32], including robustness to strategic payoff perturbations.<fnref n="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 [45]. 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.

## 2. PRELIMINARIES

We start by recalling some basic facts and definitions from game theory, roughly following the classical textbook of Fudenberg & Tirole [22]. First, a *finite game in normal form* consists of a) a finite set of players $i \in \mathcal{N} \equiv \{1, \dots, N\}$; b) a finite set of

<footnote n="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.</footnote>
actions – or pure strategies – $\mathcal{A}_i$ per player $i \in \mathcal{N}$; and c) an ensemble of payoff functions $u_i: \prod_j \mathcal{A}_j \to \mathbb{R}$, each determining the reward $u_i(\alpha)$ of player $i \in \mathcal{N}$ in a given action profile $\alpha = (\alpha_1, \dots, \alpha_N)$. Collectively, we will write $\mathcal{A} = \prod_j \mathcal{A}_j$ for the game's action space and $\Gamma \equiv \Gamma(\mathcal{N}, \mathcal{A}, u)$ for the game with primitives as above.

During play, each player $i \in \mathcal{N}$ may randomize their choice of action by playing a mixed strategy, i.e., a probability distribution $x_i \in \mathcal{X}_i := \Delta(\mathcal{A}_i)$ over $\mathcal{A}_i$ that selects $\alpha_i \in \mathcal{A}_i$ with probability $x_{i\alpha_i}$. To lighten notation, we identify $\alpha_i \in \mathcal{A}_i$ with the mixed strategy that assigns all weight to $\alpha_i$ (thus justifying the terminology “pure strategies”). Then, writing $x = (x_i)_{i \in \mathcal{N}}$ for the players' strategy profile and $\mathcal{X} = \prod_i \mathcal{X}_i$ for the game's strategy space, the players' payoff functions may be extended to all of $\mathcal{X}$ by setting

$$u_i(x) := \mathbb{E}_{\alpha \sim x}[u_i(\alpha)] = \sum_{\alpha \in \mathcal{A}} u_i(\alpha) x_{\alpha} \quad (1)$$

where, in a slight abuse of notation, we write $x_\alpha$ for the joint probability of playing $\alpha \in \mathcal{A}$ under $x$, i.e., $x_\alpha = \prod_i x_{i\alpha_i}$. This randomized framework will be referred to as the mixed extension of $\Gamma$ and we will denote it by $\Delta(\Gamma)$.

For concision, we will also write $(x_i; x_{-i}) = (x_1, \dots, x_i, \dots, x_N)$ for the strategy profile where player $i$ plays $x_i \in \mathcal{X}_i$ against the strategy profile $x_{-i} \in \prod_{j \neq i} \mathcal{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(\alpha_i; x_{-i}))_{\alpha_i \in \mathcal{A}_i} \quad (2)$$

so the payoff to player $i \in \mathcal{N}$ under $x \in \mathcal{X}$ becomes

$$u_i(x) = \sum_{\alpha_i \in \mathcal{A}_i} u_i(\alpha_i; x_{-i}) x_{i\alpha_i} = \langle v_i(x), x_i \rangle. \quad (3)$$

Moving forward, the best-response correspondence of player $i \in \mathcal{N}$ is defined as the set-valued mapping $\mathbf{br}_i: \mathcal{X} \rightrightarrows \mathcal{X}_i$ given by

$$\mathbf{br}_i(x) = \arg \max_{x'_i \in \mathcal{X}_i} u_i(x'_i; x_{-i}) \quad \text{for all } x \in \mathcal{X}. \quad (4)$$

Extending this over all players, we will write $\mathbf{br} = \prod_i \mathbf{br}_i$ for the product correspondence $\mathbf{br}(x) = \mathbf{br}_1(x) \times \dots \times \mathbf{br}_N(x)$, and we will say that $x^* \in \mathcal{X}$ is a Nash equilibrium (NE) if $x^* \in \mathbf{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^*) \ge u_i(\alpha_i; x^*_{-i}) \quad \text{for all } \alpha_i \in \mathcal{A}_i \text{ and all } i \in \mathcal{N}. \quad (NE)$$

As a final point of note, if $x^*$ is a Nash equilibrium where each player has a unique best response – that is, $\mathbf{br}_i(x^*) = \{x_i^*\}$ for all $i \in \mathcal{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 \neq x_i^*$, $i \in \mathcal{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.

### 3. REGULARIZED LEARNING IN GAMES

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

(1) At each stage $n = 1, 2, \dots$, 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, \dots$ are collectively drawn by the probability distribution $z_n \in \Delta(\mathcal{A})$, the regret of each player $i \in \mathcal{N}$ is defined as

$$ \mathrm{Reg}_i(T) = \max_{\alpha_i \in \mathcal{A}_i} \sum_{n=1}^{T} [u_i(\alpha_i; z_{-i,n}) - u_i(z_n)], \quad (5) $$

and we will say that player $i$ has no regret if $\mathrm{Reg}_i(T) = o(T)$.

One of the most widely used policies to achieve no-regret play is the so-called “follow-the-regularized-leader” (FTRL) family of algorithms and its variants [47, 48]. To motivate the analysis to come, we begin with an archetypal FTRL method, the exponential/multiplicative weights algorithm, also known as HEDGE [4, 5, 11].

**3.1. A gentle start.** We begin our discussion with a “stimulus-response” approach in the spirit of Erev & Roth [20]: First, at each stage $n = 1, 2, \dots$, every player $i \in \mathcal{N}$ employs a mixed strategy $x_{i,n} \in \mathcal{X}_i$ to select an action $\alpha_{i,n} \in \mathcal{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\alpha_i, n+1} = y_{i\alpha_i, n} + u_i(\alpha_i; \alpha_{-i,n}) \quad \text{for all } \alpha_i \in \mathcal{A}_i. \quad (6) $$

In words, $y_{i\alpha_i, n}$ simply tracks the cumulative payoff of the pure strategy $\alpha_i \in \mathcal{A}_i$ up to time $n$ (inclusive).<fnref n="2" /> As such, this score can be treated as a *propensity* to play a given pure strategy at any given stage: the strategies $\alpha_i \in \mathcal{A}_i$ with the highest propensity scores $y_{i\alpha_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

$$ \Lambda_i(y_i) = \frac{(\exp(y_{i\alpha_i}))_{\alpha_i \in \mathcal{A}_i}}{\sum_{\alpha_i \in \mathcal{A}_i} \exp(y_{i\alpha_i})} \quad (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 weights – or HEDGE – algorithm

$$ y_{i,n+1} = y_{i,n} + \gamma_n v_i(\alpha_n) \quad x_{i,n+1} = \Lambda_i(y_{i,n+1}) \quad \alpha_{i,n+1} \sim x_{i,n+1} \quad (\text{HEDGE}) $$

where $\gamma_n$ is the algorithm's “learning rate”. For an introduction to the literature on (HEDGE), see [2, 10, 11, 33, 47] 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.

<footnote n="2">²Of course, updating these scores requires the knowledge of the “what if” pure payoffs $u_i(\alpha_i; \alpha_{-i,n})$ at each stage $n$, but we assume for the moment that this information is available (we will relax this assumption later on).</footnote>
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 \in \mathcal{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 $\mathcal{Y}_i := \mathbb{R}^{A_i}$ and $\mathcal{Y} := \prod_i \mathcal{Y}_i$ for the game’s “payoff space”, in direct analogy to $\mathcal{X}_i$ and $\mathcal{X} = \prod_i \mathcal{X}_i$ for the game’s strategy space.

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

$$ \begin{array}{ll} \text{Aggregate payoff information (stimulus):} & Y_{i,n+1} = Y_{i,n} + \gamma_n \hat{v}_{i,n} \\ \text{Update choice probabilities (response):} & X_{i,n+1} = Q_i(Y_{i,n+1}) \end{array} \qquad (\text{RL}) $$

In tune with (HEDGE), the various elements of (RL) are defined as follows:

(1) $X_{i,n} \in \mathcal{X}_i$ denotes the mixed strategy of player $i$ at time $n = 1, 2, \dots$

(2) $Y_{i,n} \in \mathcal{Y}_i$ is a “score vector” that measures the performance of the player’s actions over time.

(3) $Q_i: \mathcal{Y}_i \to \mathcal{X}_i$ is a “regularized choice map” that maps score vectors to choice probabilities.

(4) $\hat{v}_{i,n}$ is a surrogate / approximation of the mixed payoff vector $v_i(X_n)$ of player $i$ at time $n$.

(5) $\gamma_n > 0$ is a step-size / sensitivity parameter of the form $\gamma_n \propto 1/n^{\ell_\gamma}$ for some $\ell_\gamma \in [0, 1]$.

In words, at each stage of the process, every player $i \in \mathcal{N}$ observes – or otherwise estimates – a proxy $\hat{v}_{i,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 $\hat{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 $\hat{v}_n$ as

$$ \hat{v}_n = v(X_n) + U_n + b_n \qquad (8) $$

where

$$ b_n = \mathbb{E}[\hat{v}_n | \mathcal{F}_n] - v(X_n) \quad \text{and} \quad U_n = \hat{v}_n - \mathbb{E}[\hat{v}_n | \mathcal{F}_n] \qquad (9) $$

respectively denote the offset and the random error of $\hat{v}_n$ relative to $v(X_n)$. To streamline our presentation, we will also assume that $\|b_n\| = \mathcal{O}(1/n^{\ell_b})$ and $\|U_n\| = \mathcal{O}(n^{\ell_\sigma})$ for some $\ell_b, \ell_\sigma \ge 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 [47] and assume that each player is employing a *regularized choice map* of the general form

$$Q_i(y_i) = \arg \max_{x_i \in \mathcal{X}_i} \{\langle y_i, x_i \rangle - h_i(x_i)\} \quad \text{for all } y_i \in \mathcal{Y}_i. \quad (10)$$

In the above, the *regularizer* $h_i: \mathcal{X}_i \to \mathbb{R}$ acts as a penalty that smooths out the “hard” argmax correspondence $y_i \mapsto \arg\max_{x_i \in \mathcal{X}_i} \langle y_i, x_i \rangle$. 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 [10, 35, 47, 48].

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

$$h_i(x_i) = \sum_{\alpha_i \in \mathcal{A}_i} \theta(x_i \alpha_i) \quad (11)$$

for some continuous function $\theta: [0, 1] \to \mathbb{R}$ with $\inf_{z \in (0,1]} \theta''(z) > 0$. We will also say that the players’ regularizers are *steep* if $\lim_{z \to 0^+} \theta'(z) = -\infty$, and *non-steep* otherwise.

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

$$\theta(z) = z^\rho / [\rho(\rho - 1)] \quad \text{for } \rho \in (0, 2], \quad (12)$$

for $\rho \in (0, 1) \cup (1, 2]$ and $\theta(z) = z \log z$ for $\rho = 1$ [10, 33, 35, 55]. This family includes:

* For $\rho = 2$, Eq. (12) boils down to the quadratic regularizer $\theta(z) = z^2/2$, which in turn yields the Euclidean projection map

$$Q_i(y_i) = \Pi_{\mathcal{X}_i}(y_i) \equiv \arg \min_{x_i \in \mathcal{X}_i} \|y_i - x_i\|_2. \quad (13)$$

* For $\rho = 1$, Eq. (12) yields the *entropic regularizer* $\theta(z) = z \log z$, which in turn leads the logit choice map (7).

* For $\rho = 1/2$, we obtain the *fractional power regularizer* $\theta(z) = -4\sqrt{z}$ that underlies the *TSALLIS-INF* algorithm of [1, 55] (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 [48] is obtained when players observe their full payoff vectors, that is, $\hat{v}_{i,n} = v_i(X_n)$. In this case, (RL) boils down to the deterministic update rule

$$Y_{i,n+1} = Y_{i,n} + \gamma_n v_i(X_n) \quad X_{i,n+1} = Q_i(Y_{i,n+1})$$

or, more explicitly

$$X_{i,n+1} = \arg \max_{x_i \in \mathcal{X}_i} \left\{ \sum_{k=1}^{n} \gamma_k u_i(x_i; X_{-i,k}) - h_i(x_i) \right\} \quad (\text{FTRL})$$

For a detailed discussion of (FTRL), see [10, 33, 47]. 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) [4, 34, 47, 52]. ◇

**Algorithm 2 (Optimistic FTRL).** A notable variant of FTRL – originally due to Popov [42] and subsequently popularized by Rakhlin & Sridharan [43, 44] – 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} + \gamma_n [2v_i(X_n) - v_i(X_{n-1})] \quad (\text{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 (7), we obtain the familiar update rule known as *optimistic multiplicative weights* (OMW) [16, 43, 44, 49].

Compared to (FTRL), the gain vector $\hat{v}_n = 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*

$$ \text{IWE}_{i\alpha_i}(x) = \frac{1\{\hat{\alpha}_i = \alpha_i\}}{x_{i\alpha_i}} u_i(\hat{\alpha}) \quad \text{for all } \alpha_i \in \mathcal{A}_i, i \in \mathcal{N}, \qquad (\text{IWE}) $$

where $x \in \mathcal{X}$ is the players' strategy profile, and $\hat{\alpha} \in \mathcal{A}$ is drawn according to $x$. This estimator is at the heart of the online learning literature [10, 11, 33, 47] 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} + \gamma_n \text{IWE}_i(\hat{X}_n) \quad X_{i,n+1} = Q_i(Y_{i,n+1}) \qquad (\text{B-FTRL}) $$

where (IWE) is sampled at the mixed strategy profile

$$ \hat{X}_{i,n} = (1 - \delta_n)X_{i,n} + \delta_n \text{unif}_{\mathcal{A}_i} \qquad (14) $$

for some “explicit exploration” parameter $\delta_n \propto 1/n^{\ell_\delta}$, $\ell_\delta > 0$, which specifies the mix between $X_{i,n}$ and the uniform distribution $\text{unif}_{\mathcal{A}_i}$ on $\mathcal{A}_i$. As we discuss in the sequel, this combination of (IWE) with the explicit exploration mechanism (14) means that the surrogate payoff vector $\hat{v}_n = \text{IWE}(\hat{X}_n)$ used to update (B-FTRL) has offset and noise bounded respectively as $b_n = \mathcal{O}(\delta_n)$ and $U_n = \mathcal{O}(1/\delta_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) [6, 11, 33], obtained by running (B-FTRL) with the logit choice map (7).

(2) The Tsallis implicitly normalized forecaster (TSALLIS-INF) [1, 3, 54, 55] that was proposed as a more efficient alternative to EXP3, and which updates as

$$ X_{i,n} = \arg\max_{x_i \in \mathcal{X}_i} \left\{ \langle Y_{i,n}, x_i \rangle + 4 \sum_{\alpha_i \in \mathcal{A}_i} \sqrt{x_{i\alpha_i}} \right\} \qquad (\text{TSALLIS-INF}) $$

i.e., as (B-FTRL) with the fractional power regularizer $\theta(z) = -4\sqrt{z}$ 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 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 [51].

**Example 4.1.** Consider the 4 × 4 symmetric 2-player game with payoff bimatrix

<table><thead><tr><th></th><th>A</th><th>B</th><th>C</th><th>D</th></tr></thead><tbody><tr><th>A</th><td>(1, 1)</td><td>(1, 2/3)</td><td>(0, 0)</td><td>(0, -1/3)</td></tr><tr><th>B</th><td>(2/3, 1)</td><td>(2/3, 2/3)</td><td>(-1/3, 0)</td><td>(-1/3, -1/3)</td></tr><tr><th>C</th><td>(0, 0)</td><td>(0, -1/3)</td><td>(1, 1)</td><td>(1, 2/3)</td></tr><tr><th>D</th><td>(-1/3, 0)</td><td>(-1/3, -1/3)</td><td>(2/3, 1)</td><td>(2/3, 2/3)</td></tr></tbody></table>

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 \in \Delta(A)$ satisfies $u_i(\alpha_i; z_{-i}) - u_i(z) \le -1/6$ for all $\alpha_i \in \{A, B, C, D\}$, $i = 1, 2$. As a result, the players' regret under $z_n \equiv 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 $\mathcal{L}(X)$ of $X_n$ under (RL), viz.

$$ \mathcal{L}(X) := \bigcap_n \text{cl}\{X_k : k \ge n\} \equiv \{\hat{x} \in \mathcal{X} : X_{n_k} \to \hat{x} \text{ for some subsequence } X_{n_k} \text{ of } X_n\}. \quad (15) $$

In words, $\mathcal{L}(X)$ is the set of limit points of $X_n$ or, equivalently, the smallest subset of $\mathcal{X}$ to which $X_n$ converges. Clearly, the simplest instance of a limit set is when $\mathcal{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 $\mathcal{L}(X) = \{x^*\}$ then, for certain special cases of (RL), it is known that $x^*$ is a Nash equilibrium of $\Gamma$ [36]. 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 $\mathcal{S}$ of $\mathcal{X}$ is said to be *resilient to strategic deviations* – or simply *resilient* – if, for every deviation $x_i \in \mathcal{X}_i$ of every player $i \in \mathcal{N}$, we have

$$u_i(x^*) \geq u_i(x_i, x_{-i}^*) \quad \text{for some } x^* \in \mathcal{S}. \qquad (16)$$

Informally, $\mathcal{S}$ is resilient if every unilateral deviation from $\mathcal{S}$ is deterred by some (possibly different) element thereof. In particular, if $\mathcal{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, \dots$, be the sequence of play generated by (RL) with step-size/gain parameters $\ell_\gamma > 2\ell_\sigma$ and $\ell_b > 0$. Then, with probability 1, the limit set $\mathcal{L}(X)$ of $X_n$ is resilient.

**Corollary 1.** With assumptions as above, if $\mathcal{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 $\mathbb{P}(\mathcal{L}(X) = \mathcal{S}) > 0$ for some non-random $\mathcal{S} \subseteq \mathcal{X}$, $\mathcal{S}$ must be resilient. This is argued by contradiction: if $p_i \in \mathcal{X}_i$ is a unilateral deviation violating Definition 1, we must also have $\liminf_{n \to \infty} [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 $\gamma_n$, $b_n$ and $U_n$ come in). Then, to get the stronger statement that the random set $\mathcal{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 $\ell_b > 0$ and $2\ell_\sigma < \ell_\gamma$ are a priori *implicit* because they depend on the offset and magnitude statistics of the feedback sequence $\hat{v}_n$. 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 $\ell_b = \ell_\gamma$ while, for Algorithm 3, we have $\ell_b = \ell_\sigma = \ell_\delta$. 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 $\ell_\gamma \in (0, 1]$ and, for Algorithm 3, $\ell_\delta \in (0, \ell_\gamma/2)$. Then, with probability 1, the limit set $\mathcal{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 robust to strategic deviations. However, this is not so: a direct calculation shows that the face of $\mathcal{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.

## 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 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 \in \mathcal{N}$ as

$$ \mathbf{btr}_i(x) = \{x'_i \in \mathcal{X}_i : u_i(x'_i; x_{-i}) \ge u_i(x)\} \quad (17) $$

and write $\mathbf{btr} = \prod_i \mathbf{btr}_i$ for the product correspondence $\mathbf{btr}(x) = \mathbf{btr}_1(x) \times \dots \times \mathbf{btr}_N(x)$. [In words, $\mathbf{btr}_i$ assigns to each $x \in \mathcal{X}$ those strategies of player $i$ that are (weakly) better against $x$ than $x_i$.] In addition, given a product of pure strategies $C = \prod_{i \in \mathcal{N}} C_i$ with $C_i \subseteq A_i$ for all $i \in \mathcal{N}$, let $S = \Delta(C)$ denote the span of $C$, and let $\mathcal{P}(\mathcal{X})$ denote the collection of all such sets. We then say that $S \in \mathcal{P}(\mathcal{X})$ is *closed under better replies* – a *club set* for short – if it is closed under $\mathbf{btr}$, i.e., $\mathbf{btr}(S) \subseteq S$; finally, $S$ is said to be *minimally club* (m-club) if it does not admit a proper club subset.<fnref n="3" />

Of course, the entire strategy space $\mathcal{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 [45], 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, $\mathbf{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$.<fnref n="4" />

<footnote n="3">³Analogously to club sets, $S \in \mathcal{P}(\mathcal{X})$ is said to be *closed under rational behavior* (curb) if it is closed under *best replies*, i.e., $\mathbf{br}(S) \subseteq S$ [7]. Clearly, club sets are also curb, but the converse does not hold, cf. [45].</footnote>

<footnote n="4">⁴Formally, a component $\mathcal{X}^*$ of Nash equilibria of $\Gamma$ is *essential* if, for all $\varepsilon > 0$, there exists $\delta > 0$ such that any perturbation of the payoffs of $\Gamma$ by at most $\delta$ produces a Nash equilibrium that is $\varepsilon$-close to $\mathcal{X}^*$ [50]. 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 [32], including robustness to strategic payoff perturbations. For an in-depth discussion, see van Damme [50].</footnote>
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 $\mathcal{S}$ of $\mathcal{X}$ and a tolerance level $\varepsilon > 0$. We then say that $\mathcal{S}$ is:

(1) *Stochastically stable* if, for every neighborhood $\mathcal{U}$ of $\mathcal{S}$ in $\mathcal{X}$, there exists a neighborhood $\mathcal{U}_1$ of $\mathcal{S}$ such that

$$ \mathbb{P}(X_n \in \mathcal{U} \text{ for all } n = 1, 2, \dots) \geq 1 - \varepsilon \quad \text{whenever } X_1 \in \mathcal{U}_1. \qquad (18) $$

(2) *Stochastically attracting* if there exists a neighborhood $\mathcal{U}_1$ of $\mathcal{S}$ such that

$$ \mathbb{P}(\lim_{n \to \infty} \text{dist}(X_n, \mathcal{S}) = 0) \geq 1 - \varepsilon \quad \text{whenever } X_1 \in \mathcal{U}_1. \qquad (19) $$

(3) *Stochastically asymptotically stable* if it is stochastically stable and attracting.

(4) *Irreducibly stable* if $\mathcal{S}$ is stochastically asymptotically stable and it does not admit a strictly smaller stochastically asymptotically stable $\mathcal{S}'$ with $\text{supp}(\mathcal{S}') \subsetneq \text{supp}(\mathcal{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 $\mathcal{S} \in \mathcal{P}(\mathcal{X})$ and suppose that (RL) is run with a steep regularizer and step-size / gain parameters $\ell_\gamma \in [0, 1]$, $\ell_b > 0$, and $\ell_\sigma < 1/2$. Then:

(1) $\mathcal{S}$ is stochastically asymptotically stable under (RL) if and only if it is a club set.

(2) $\mathcal{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 $\mathcal{S} \in \mathcal{P}(\mathcal{X})$ be a club set, and let $X_n$, $n = 1, 2, \dots$, be the sequence of play generated by (RL) with parameters $\ell_\gamma \in [0, 1]$, $\ell_b > 0$, and $\ell_\sigma < 1/2$. Then, for all $\varepsilon > 0$, there exists an (open, unbounded) initialization domain $\mathcal{D} \subset \mathcal{Y}$ such that, with probability at least $1 - \varepsilon$, we have

$$ \text{dist}(X_n, \mathcal{S}) \leq C\varphi(c_1 - c_2 \sum_{k=1}^{n} \gamma_k) \quad \text{whenever } Y_1 \in \mathcal{D} \qquad (20) $$

where $C, c_1, c_2$ are constants ($C, c_2 > 0$), and the rate function $\varphi$ is given by $\varphi(z) = (\theta')^{-1}(z)$ if $z > \lim_{z \to 0^+} \theta'(z)$, and $\varphi(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 $\ell_\gamma \in [0, 1]$ and, for Algorithm 3, $\ell_\delta \in (0, 1/2)$. Then, with notation as in Theorem 3, $X_n$ converges to $\mathcal{S}$ at a rate of

$$ \text{dist}(X_n, \mathcal{S}) \leq C \cdot \begin{cases} [1 - c \sum_{k=1}^{n} \gamma_k]_{+} & \text{if } \theta(z) = z^2/2 \quad \# \text{Euclid. proj.} \\ \exp(-c \sum_{k=1}^{n} \gamma_k) & \text{if } \theta(z) = z \log z \quad \# \text{logit choice} \\ 1/(c + \sum_{k=1}^{n} \gamma_k)^2 & \text{if } \theta(z) = -4\sqrt{z} \quad \# \text{Tsallis maps} \end{cases} \qquad (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.
<figure><img src="image_2.png" /><figcaption>**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.</figcaption></figure>

*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'$ [19]. 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 [35] 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 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 $\langle Y_n, z \rangle$ [26]. The irreducible stability of m-club sets then follows by invoking this criterion reductively for any potentially stable subset $S'$ of $S$. $\blacksquare$

## 6. 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 [21] and [23] (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 [12, 30]. 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.

## 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. Throughout this appendix, we will suppress the player index $i \in \mathcal{N}$, and we will follow standard conventions in convex analysis [46] that treat $h$ as an extended-real-valued function $h: \mathcal{V} \to \mathbb{R} \cup \{\infty\}$ with $h(x) = \infty$ for all $x \in \mathcal{V} \setminus \mathcal{X}$. With this in mind, the subdifferential of a $h$ at $x \in \mathcal{X}$ is defined as

$$ \partial h(x) := \{y \in \mathcal{Y} : h(x') \geq h(x) + \langle y, x' - x \rangle \text{ for all } x' \in \mathcal{X}\}, \quad (A.1) $$

where $\mathcal{Y}$ denotes here the algebraic dual $\mathcal{V}^*$ of $\mathcal{V}$. Accordingly, the domain of subdiffer-entiability of $h$ is $\text{dom} \partial h := \{x \in \text{dom} h : \partial h \neq \emptyset\}$, and the convex conjugate of $h$ is defined as

$$ h^*(y) = \max_{x \in \mathcal{X}} \{\langle y, x \rangle - h(x)\} \quad (A.2) $$

for all $y \in \mathcal{Y}$. We then have the following basic results.

**Lemma A.1.** Let $h$ be a regularizer on $\mathcal{X}$, and let $Q: \mathcal{Y} \to \mathcal{X}$ be the induced choice map. Then:

(1) $Q$ is single-valued, and, for all $x \in \mathcal{X}$, $y \in \mathcal{Y}$, we have $x = Q(y) \iff y \in \partial h(x)$.

(2) For all $x \in \text{ri} \mathcal{X}$, we have

$$ \partial h(x) = \{(\theta'(x_\alpha) + \mu)_{\alpha \in \mathcal{A}} : \mu \in \mathbb{R}\}. \quad (A.3) $$

(3) The prox-domain $\mathcal{X}_h := \text{im} Q$ of $h$ satisfies $\text{ri} \mathcal{X} \subseteq \mathcal{X}_h \subseteq \mathcal{X}$.

(4) For all $y \in \mathcal{Y}$, we have $Q(y) = \nabla h^*(y)$. and $Q$ is $(1/K)$-Lipschitz continuous with $K := \inf_{(0,1]} \theta''(z)$. In particular, as a special case, the logit choice map $\Lambda$ is 1-Lipschitz continuous in the $(L^1, L^\infty)$ pair of norms on $\mathcal{Y}$ and $\mathcal{X}$ respectively.

(5) If $y_\alpha - y_{\alpha'} \to -\infty$ for some $\alpha' \neq \alpha$, then $Q_\alpha(y) \to 0$.

**Remark.** Some of the properties presented in Lemma A.1 are well known in the literature on regularized learning methods (see e.g., [35] and references therein), but we provide a proof of the entire lemma for completeness. $\diamond$

**Proof of Lemma A.1.** For the first property of $Q$, note that the maximum in (10) is attained for all $y \in \mathcal{Y}$ because $h$ is lower-semicontinuous (l.s.c.) and strongly convex. Furthermore, $x$ solves (10) if and only if $y - \partial h(x) \ni 0$, i.e., if and only if $y \in \partial h(x)$.

For our second claim, if $x \in \text{ri}(\mathcal{X})$, the first-order stationarity conditions for the convex problem (10) that defines $Q$ become

$$ y_{\alpha} - \theta'(x_{\alpha}) = \mu \quad \text{for all } \alpha \in \mathcal{A}, \quad (A.4) $$

because the inequality constraints $x_\alpha \geq 0$ are all inactive (recall that $x \in \text{ri}(\mathcal{X})$ by assumption). Now, by the first part of the theorem we have $x = Q(y)$ if and only if $y \in \partial h(x)$, so we conclude that $\partial h(x) = \{(\theta'(x_\alpha) + \mu)_{\alpha \in \mathcal{A}} : \mu \in \mathbb{R}\}$, as claimed.

For the fourth item, the expression $Q = \nabla h^*$ is an immediate consequence of Danskin's theorem, while the Lipschitz continuity of $Q$ follows from standard results, see e.g., [46, Theorem 12.60(b)].

For our last claim, let $y_n$ be a sequence in $\mathcal{Y}$ such that $y_{\alpha,n} - y_{\alpha',n} \to -\infty$ and let $x_n = Q(y_n)$. Then, by descending to a subsequence if necessary, assume there exists some $\varepsilon > 0$ such that $x_{\alpha,n} \geq \varepsilon > 0$ for all $n$. Then, by the defining relation $Q(y) = \arg \max\{\langle y, x \rangle - h(x)\}$ of $Q$, we have:

$$ \langle y_n, x_n \rangle - h(x_n) \geq \langle y_n, x' \rangle - h(x') \quad (A.5) $$
for all $x' \in \mathcal{X}$. Therefore, taking $x'_n = x_n + \varepsilon(e_{\alpha'} - e_{\alpha})$, we readily obtain

$$ \varepsilon(y_{\alpha,n} - y_{\alpha',n}) \geq h(x_n) - h(x'_n) \geq \min h - \max h \quad (A.6) $$

which contradicts our original assumption that $y_{\alpha,n} - y_{\alpha',n} \to -\infty$. With $\mathcal{X}$ compact, the above shows that $x^*_\alpha = 0$ for any limit point $x^*$ of $x_n$, i.e. $Q_\alpha(y_n) \to 0$. ■

The second collection of results concerns the *Fenchel coupling*, an energy function that was first introduced in [35, 36] and is defined as follows:

$$ F(p, y) = h(p) + h^*(y) - \langle y, p \rangle \quad \text{for all } p \in \mathcal{X} \text{ and } y \in \mathcal{Y}. \quad (A.7) $$

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 \in \mathcal{X}$ and all $y, y' \in \mathcal{Y}$, we have:

$$ a) \quad F(p, y) \geq \frac{1}{2} K \|Q(y) - p\|^2. \quad (A.8a) $$

$$ b) \quad F(p, y') \leq F(p, y) + \langle y' - y, Q(y) - p \rangle + \frac{1}{2K} \|y' - y\|_{\infty}^2. \quad (A.8b) $$

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

$$ (K/2)\|Q(y)\|^2 \leq h^*(y) \leq -\min h + \langle y, Q(y) \rangle + (2/K)\|y\|_{\infty}^2 \quad \text{for all } y \in \mathcal{Y}. \quad (A.9) $$

*Proof of Lemma A.2.* By the strong convexity of $h$ relative to $\|\cdot\|$ (cf. Lemma A.1), we have

$$ \begin{aligned} h(x) + t\langle y, p - x \rangle &\leq h(x + t(p - x)) \\ &\leq th(p) + (1-t)h(x) - \frac{1}{2}Kt(1-t)\|x-p\|^2, \end{aligned} \quad (A.10) $$

leading to the bound

$$ \frac{1}{2} K(1-t)\|x-p\|^2 \leq h(p) - h(x) - \langle y, p-x \rangle = F(p, y) \quad (A.11) $$

for all $t \in (0, 1]$. The bound (A.8a) then follows by letting $t \to 0^+$ in (A.11).

For our second claim, we have

$$ \begin{aligned} F(p, y') &= h(p) + h^*(y') - \langle y', p \rangle \\ &\leq h(p) + h^*(y) + \langle y' - y, \nabla h^*(y) \rangle + \frac{1}{2K} \|y' - y\|_{\infty}^2 - \langle y', p \rangle \\ &= F(p, y) + \langle y' - y, Q(y) - p \rangle + \frac{1}{2K} \|y' - y\|_{\infty}^2, \end{aligned} \quad (A.12) $$

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 [26].

**Lemma A.3 (Azuma-Hoeffding inequality).** Let $M_n \in \mathbb{R}$, $n = 1, 2, \dots$, be a martingale with $\|M_n - M_{n-1}\|_{\infty} \leq \sigma_n$ (a.s.). Then, for all $\eta > 0$, we have

$$ \mathbb{P}\left( |M_n| \leq \left( 2 \log(2n^2/\eta) \sum_{k=1}^{n} \sigma_k^2 \right)^{1/2} \text{ for all } n \right) \geq 1 - \eta. \quad (A.13) $$
**Lemma A.4** (Kolmogorov's inequality). Let $Z_n \in \mathbb{R}$, $n = 1, 2, \dots$, be a martingale difference sequence that is bounded in $L^2$. Then:

$$ \mathbb{P}\left(\max_{k \le n} \sum_{\ell=1}^{k} Z_{\ell} \ge \varepsilon\right) \le \frac{1}{\varepsilon^2} \mathbb{E}\left[\left(\sum_{k=1}^{n} Z_k\right)^2\right] \quad \text{for all } \varepsilon > 0. \quad (A.14) $$

**Lemma A.5** (Doob's maximal inequality). Let $Z_n \in \mathbb{R}$, $n = 1, 2, \dots$, be a martingale difference sequence that is bounded in $L^p$ for some $p \ge 1$. Then

$$ \mathbb{P}\left(\max_{k \le n} |Z_k| > \varepsilon\right) \le \frac{1}{\varepsilon^p} \mathbb{E}[|Z_n|^p] \quad \text{for all } \varepsilon > 0. \quad (A.15) $$

**Lemma A.6** (Burkholder-Davis-Gundy inequality). Let $Z_n$, $n = 1, 2, \dots$, be a martingale difference sequence in $\mathbb{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 \mathbb{E}\left[\sum_{k=1}^{n} \|Z_k\|_2^2\right]^{p/2} \le \mathbb{E}\left[\max_{k \le n} \left\|\sum_{\ell=1}^{k} Z_\ell\right\|_2^p\right] \le C_p \mathbb{E}\left[\sum_{k=1}^{n} \|Z_k\|_2^2\right]^{p/2}. \quad (A.16) $$

**Lemma A.7** (Robbins-Siegmund). Let $\mathcal{F}_n$, $n = 1, 2, \dots$, be a filtration on a complete probability space $(\Omega, \mathcal{F}, \mathbb{P})$, and suppose that the sequences $X_n$, $L_n$ and $K_n$ $\mathcal{F}_n$-measurable, nonnegative, and such that

$$ \mathbb{E}[X_{n+1} | \mathcal{F}_n] \le X_n(1 + L_n) + K_n \quad \text{with probability 1.} \quad (A.17) $$

Then, $X_n$ converges to some random variable $X_\infty$ with probability 1 on the event

$$ \left\{ \sum_{n=1}^{\infty} L_n < \infty \quad \text{and} \quad \sum_{n=1}^{\infty} K_n < \infty \right\}. \quad (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 $\hat{v}_n$ are respectively bounded as

$$ \|b_n\|_{\infty} \le B_n \quad \|U_n\|_{\infty} \le \sigma_n \quad \text{and} \quad \|\hat{v}_n\|_{\infty} \le M_n \quad (B.1) $$

and we will set

$$ G := \max_{i \in \mathcal{N}} \max_{\alpha \in \mathcal{A}} |v_i(\alpha)| \quad (B.2) $$

so we can take $M_n = G + B_n + \sigma_n$ in (B.1). We will also make free use of the fact that $v$ is Lipschitz continuous on $\mathcal{X}$, and we will write $L$ for its Lipschitz modulus in the $(L^1, L^\infty)$ pair of norms on $\mathcal{X}$ and $\mathcal{Y}$ respectively, viz.

$$ \|v(x') - v(x)\|_{\infty} \le L \|x' - x\|_{1} \quad \text{for all } x, x' \in \mathcal{X}. \quad (B.3) $$

We now proceed to establish the required bounds for Algorithms 1–3:

**Algorithm 1.** Since $\hat{v}_n = v(X_n)$, we readily get $b_n = U_n = 0$ by definition, so Algorithm 1 fits the scheme (RL) for free with $\ell_b = \infty$, $\ell_\sigma = 0$. $\diamond$
**Algorithm 2.** For the case of (Opt-FTRL), we have $\hat{v}_n = 2v(X_n) - v(X_{n-1})$ so $b_n = v(X_n) - v(X_{n-1})$, which is $\mathcal{F}_n$-measurable. We thus get

$$ 
\begin{aligned}
\|b_n\|_{\infty} &= \|\mathbb{E}[\hat{v}_n | \mathcal{F}_n] - v(X_n)\|_{\infty} \\
&\le \mathbb{E}[\|v(X_n) - v(X_{n-1})\|_{\infty} | \mathcal{F}_n] \\
&\le L \mathbb{E}[\|X_n - X_{n-1}\| | \mathcal{F}_n] \quad \# \text{by (B.3)} \\
&= L \mathbb{E}[\|Q(Y_n) - Q(Y_{n-1})\|_{\infty} | \mathcal{F}_n] \quad \# \text{by (Opt-FTRL)} \\
&\le (L/K) \mathbb{E}[\|Y_n - Y_{n-1}\|_{\infty} | \mathcal{F}_n] \quad \# \text{by Lemma A.1} \\
&\le \gamma_n (L/K) \mathbb{E}[2v(X_n) - v(X_{n-1}) | \mathcal{F}_n] \quad \# \text{by (Opt-FTRL)} \\
&\le 3LG/K \cdot \gamma_n \quad \# \text{by (B.2)} \\
&= \mathcal{O}(\gamma_n) = \mathcal{O}(1/n^{\ell_{\gamma}}) \quad (B.4)
\end{aligned}
$$

Moreover, given that $\hat{v}$ is $\mathcal{F}_n$-measurable, we readily get $U_n = 0$. ◇

**Algorithm 3.** Since $\hat{\alpha}_n$ is sampled according to $\hat{X}_n = (1 - \delta_n)X_{i,n} + \delta_n \text{unif}_{A_i}$ (cf. Eq. (14) in Section 3), we readily obtain $\mathbb{E}[\hat{v}_{i,n} | \mathcal{F}_n] = v_i(\hat{X}_n)$, and hence, by (B.3), we get

$$ B_n = \mathcal{O}(\|\hat{X}_n - X_n\|) = \mathcal{O}(\delta_n) = \mathcal{O}(1/n^{\ell_{\delta}}). \quad (B.5) $$

Moreover, since $\hat{X}_{i\alpha_{i,n}} \ge \delta_n/A_i$, it follows that $\|\hat{v}_n\|_{\infty} = \mathcal{O}(1/\delta_n) = \mathcal{O}(n^{\ell_{\delta}})$. ◇

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 [31, 39], which updates as:

$$ 
\begin{aligned}
\tilde{Y}_n &= Y_n + \gamma_n v(X_n) & Y_{n+1} &= Y_n + \gamma_n v(\tilde{X}_n) \\
\tilde{X}_n &= Q(\tilde{Y}_n) & X_{n+1} &= Q(Y_{n+1}).
\end{aligned}
\quad (\text{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 $\tilde{X}_n$ is generated with payoff information from $X_n$, not $\tilde{X}_{n-1}$. This method has been used extensively in the literature for solving variational inequalities and two-player, zero-sum games, cf. Juditsky et al. [31] and references therein.

A calculation similar to that for (Opt-FTRL) shows that Algorithm 4 has $B_n = \mathcal{O}(1/n^{\ell_{\gamma}})$ and $\sigma_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 [41]

$$ Y_{i,n+1} = Y_{i,n} + \gamma_n v_i(X_{n+1}) \quad X_{i,n+1} = \Lambda_i(Y_{i,n+1}). \quad (\text{CMW}) $$

The main difference between (CMW) and (HEDGE) is that the proxy payoff vector $\hat{v}_n$ 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
<table><caption>**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 $\gamma_n = \gamma/n^{l_\gamma}$, $l_\gamma \in (0, 1]$, and, where applicable, a sampling parameter $\delta_n = \delta/n^{l_\delta}$.</caption><thead><tr><th></th><th>Representative</th><th>Regularizer (θ)</th><th>Feedback</th><th>Bias (B<sub>n</sub>)</th><th>Variance (σ<sub>n</sub>)</th></tr></thead><tbody><tr><td>Algorithm 1</td><td>HEDGE</td><td>z log z</td><td>full info</td><td>0</td><td>0</td></tr><tr><td>Algorithm 2</td><td>OMW</td><td>z log z</td><td>full info</td><td>O(1/n<sup>l<sub>γ</sub></sup>)</td><td>0</td></tr><tr><td>Algorithm 3</td><td>EXP3</td><td>z log z</td><td>payoff</td><td>O(1/n<sup>l<sub>δ</sub></sup>)</td><td>O(n<sup>l<sub>δ</sub></sup>)</td></tr><tr><td>Algorithm 3</td><td>TSALLIS-INF</td><td>-4√z</td><td>payoff</td><td>O(1/n<sup>l<sub>δ</sub></sup>)</td><td>O(n<sup>l<sub>δ</sub></sup>)</td></tr><tr><td>Algorithm 4</td><td>MP</td><td>general</td><td>full info</td><td>O(1/n<sup>l<sub>γ</sub></sup>)</td><td>0</td></tr><tr><td>Algorithm 5</td><td>CMW</td><td>z log z</td><td>full info</td><td>O(1/n<sup>l<sub>δ</sub></sup>)</td><td>0</td></tr></tbody></table>

point problem, so (CMW) is only meaningful when one has access to the payoff function $v(\cdot)$. In this regard, (CMW) can be seen as a 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 $\hat{v}_n = v(X_{n+1})$, so $U_n = 0$ and $b_n = v(X_{n+1}) - v(X_n) = O(\gamma_n) = O(1/n^{l_\gamma})$. ◇

## 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, \dots$, be the sequence of play generated by (RL) with step-size/gain parameters $l_\gamma > 2l_\sigma$ and $l_b > 0$. Then, with probability 1, the limit set $\mathcal{L}(X)$ of $X_n$ is resilient.

*Proof.* Our proof that $\mathcal{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^*) \ge u_i(z_i; x^*_{-i})$. In this specific case, our proof proceeds by contradiction, namely by assuming that, with positive probability, $\mathcal{L}(X)$ is not resilient to $(i, z_i)$. The main steps of our proof unfold as follows:

**Step 1.** Assume that $\mathcal{L}(X)$ is not resilient to $(i, z_i)$ with positive probability. Then there exists $c, \epsilon, n_0 > 0$ such that

$$ \mathbb{P}(u_i(z_i; X_{n,-i}) \ge u_i(X_n) + c \text{ for all } n \ge n_0) \ge \epsilon. \quad (C.1) $$

*Proof of Step 1.* The function $f: x \in \mathcal{X} \mapsto u_i(z_i; x_{-i}) - u_i(x)$ is continuous and $\mathcal{X}$ is compact, so there is a definite function $\eta \equiv \eta(\delta)$ such that if $\|x - x'\| \le \eta(\delta)$, then $|f(x) - f(x')| \le \delta$. Now, by assumption, $\{\forall x^* \in \mathcal{L}(X), u_i(z_i; x^*_{-i}) > u_i(x^*)\}$ is of positive probability. We thus get

$$ \begin{aligned} & 0 < \mathbb{P}\{\forall x^* \in \mathcal{L}(X), u_i(z_i; x^*_{-i}) > u_i(x^*)\} \\ & = \mathbb{P}\left\{\inf_{x^* \in \mathcal{L}(X)} (u_i(z_i; x^*_{-i}) - u_i(x^*)) > 0\right\} \end{aligned} \quad (C.2a) $$
$$= \mathbb{P}\left(\bigcup_{m>0} \left\{ \inf_{x^* \in \mathcal{L}(X)} (u_i(z_i; x_{-i}^*) - u_i(x^*)) > 2^{-m} \right\} \right) \quad (C.2b)$$

$$\leq \frac{1}{2} \mathbb{P}\{\forall x^* \in \mathcal{L}(X), u_i(z_i; x_{-i}^*) - u_i(x^*) > 2c\} \quad (C.2c)$$

for some $c > 0$ in (C.2c), and where (C.2a) is because $\mathcal{L}(X)$ is closed – hence compact – almost surely. Therefore, by definition of $\eta(\cdot)$,

$$0 < \mathbb{P}\{\forall x^* \in \mathcal{X}, \mathrm{dist}(x^*, \mathcal{L}(X)) \leq \eta(c) \Rightarrow u_i(z_i; x_{-i}^*) - u_i(x^*) > c\} = 2\epsilon \quad (C.2d)$$

Now, let $n_0$ such that $\mathbb{P}\{\forall n \geq n_0, \mathrm{dist}(X_n, \mathcal{L}(X)) \leq \eta(c)\} > 1 - \frac{\epsilon}{2}$. Then by construction, we get

$$\mathbb{P}\{\forall n \geq n_0, u_i(z_i; X_{n,-i}) > u_i(X_n) + c\} > \epsilon. \quad (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}) - \langle Y_{i,n}, z_i \rangle \quad (C.4)$$

Then, by Lemma A.2 in Appendix A, we readily get that

$$F_{i,n+1} \leq F_{i,n} - \gamma_n \langle \hat{v}_{i,n}, z_i - X_{i,n} \rangle + \frac{\gamma_n^2}{2\kappa_h} \|\hat{v}_{i,n}\|_{\infty}^2. \quad (C.5)$$

where, in obvious notation, we are identifying $z_i \in \mathcal{A}_i$ with the corresponding vertex $e_{z_i}$ of $\mathcal{X}_i = \Delta(\mathcal{A}_i)$. To proceed, the main idea will be to relate $\gamma_n \langle \hat{v}_{i,n}, z_i - X_{i,n} \rangle$ to its “perfect” counterpart $\gamma_n \langle v_i(X_n), z_i - X_{i,n} \rangle$. We formalize this below.

**Step 2.** If $\mathcal{L}(X)$ is not resilient to $(i, z_i)$, there exists $n_1 \geq n_0$ such that, with probability $\varepsilon'/2 > 0$, and for all $n \geq n_1$, we have

$$F_{i,n} \leq F_{i,n_0} - \frac{c}{2} \sum_{k=n_0}^{n} \gamma_k. \quad (C.6)$$

*Proof of Step 2.* With probability $\varepsilon'$ and for all $n \geq n_0$, we have

$$\gamma_n \langle \hat{v}_{i,n}, z_i - X_{i,n} \rangle = \gamma_n \langle v_i(X_n), z_i - X_{i,n} \rangle + \gamma_n \langle U_{i,n}, z_i - X_{i,n} \rangle + \gamma_n \langle b_{i,n}, z_i - X_{i,n} \rangle \\ \geq [c + \langle U_{i,n}, z_i - X_{i,n} \rangle + \langle b_{i,n}, z_i - X_{i,n} \rangle] \gamma_n. \quad (C.7)$$

The combination of Eqs. (C.5) and (C.7) then provides the following upper bound of $F_{i,n+1}$:

$$\begin{aligned} F_{i,n+1} &\leq F_{i,n} - c\gamma_n + \gamma_n \langle U_{i,n}, z_i - X_{i,n} \rangle + \gamma_n \langle b_{i,n}, z_i - X_{i,n} \rangle + \frac{\gamma_n^2}{2\kappa_h} \|\hat{v}_{i,n}\|_{\infty}^2 \\ &\leq F_{i,n_0} - c \sum_{k=n_0}^{n} \gamma_k + \sum_{k=n_0}^{n} \frac{\|\hat{v}_{k,i}\|_{\infty}^2}{2\kappa_h} \gamma_k^2 \\ &\quad + \underbrace{\sum_{k=n_0}^{n} \gamma_k \langle U_{k,i}, z_i - X_{k,i} \rangle}_{E_{U,n}} + \underbrace{\sum_{k=n_0}^{n} \gamma_k \langle b_{k,i}, z_i - X_{k,i} \rangle}_{E_{b,n}}. \end{aligned} \quad (C.8)$$
We are thus left to show is that $c \sum_{k=n_0}^{n} \gamma_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 $\sum_{k=n_0}^{n} \frac{\|\hat{v}_{k,i}\|_{\infty}^2}{2\kappa_h} \gamma_k^2$. By expanding the $\|\hat{v}_{k,i}\|_{\infty}^2$, we readily get

$$ \frac{\sum_{k=n_0}^{n} \|\hat{v}_{k,i}\|_{\infty}^2 \gamma_k^2}{\tau_n} = O\left( \frac{\sum_{k=1}^{n} \gamma_k^2 (1 + B_k^2 + \sigma_k^2)}{\sum_{k=1}^{n} \gamma_k} \right). \quad (C.9) $$

However, by our assumptions on the parameters of (RL), we readily get

$$ \lim_{n \to \infty} \frac{\gamma_n^2 (1 + B_n^2 + \sigma_n^2)}{\gamma_n} = 0 \quad (C.10) $$

so we conclude that

$$ \lim_{n \to \infty} \frac{\sum_{k=1}^{n} \gamma_k^2 (1 + B_k^2 + \sigma_k^2)}{\sum_{k=1}^{n} \gamma_k} = 0 \quad (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} \le 2 \sum_{k=n_0}^{n} \|b_{i,n}\|_{\infty} \gamma_k \le 2 \sum_{k=n_0}^{n} B_k \gamma_k = o\left(\sum_{k=n_0}^{n} \gamma_k\right) \quad \text{as } n \to \infty. \quad (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 - \varepsilon'/2$, we have

$$ \begin{aligned} E_{U,n} &:= \sum_{k=n_0}^{n} \gamma_k \langle U_{k,i}, z_i - X_{k,i} \rangle \\ &\le 2 \left( \sum_{k=n_0}^{n} \|U_{k,i}\|_{\infty}^2 \gamma_k^2 \right)^{1/2} \sqrt{2 \log \left( \frac{4n^2}{\varepsilon'} \right)} \\ &\le 2 \left( \sum_{k=n_0}^{n} \sigma_k^2 \gamma_k^2 \right)^{1/2} \sqrt{2 \log \left( \frac{4n^2}{\varepsilon'} \right)}. \end{aligned} \quad (C.13) $$

for all $n \ge n_0$. To proceed, note that a second application of the Stolz-Cesàro theorem yields $\sum_{k=n_0}^{n} \sigma_k^2 \gamma_k^2 = o(\sum_{k=n_0}^{n} \gamma_k)$ and, moreover, note that $\log(4n^2/\varepsilon') = O(\sum_{k=n_0}^{n} \gamma_k)$. Taking square roots and multiplying then yields that

$$ E_{U,n} = o\left(\sum_{k=n_0}^{n} \gamma_k\right) \quad (C.14) $$

with probability at least $1 - \varepsilon'/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 \ge n_0$ such that, with probability at least $1 - \varepsilon'/2$, we have

$$ \sum_{k=n_0}^{n} \gamma_k \langle U_{k,i}, z_i - X_{k,i} \rangle + \sum_{k=n_0}^{n} \gamma_k \langle b_{k,i}, z_i - X_{k,i} \rangle + \sum_{k=n_0}^{n} \frac{\|\hat{v}_{k,i}\|_{\infty}^2}{2\kappa_h} \gamma_k^2 \le \frac{c}{2} \sum_{k=n_0}^{n} \gamma_k \quad (C.15) $$
for all $n \ge n_1$. This proves Eq. (C.6) and concludes our proof.

Summarizing the above, we have shown that, with probability at least $1 - \varepsilon'/2$, we have

$$F_{i,n+1} \le F_{n_0} - \frac{c}{2} \sum_{k=n_0}^{n} \gamma_k \to -\infty \quad \text{as } n \to \infty. \quad (C.16)$$

Since $F$ is nonnegative (by Lemma A.2), we have established that the event where $\mathcal{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.** $\mathcal{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 \in \mathcal{X}_i \cap \mathbb{Q}^{A_i}$ (which are countably many). Indeed, if $\mathcal{L}(X)$ is not resilient with positive probability, then, likewise, $\mathcal{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 \in \mathcal{X}_i \cap \mathbb{Q}^{A_i}$) to which $\mathcal{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 \in \mathcal{P}(\mathcal{X})$ and suppose that (RL) is run with a steep regularizer and step-size/gain parameters $\ell_\gamma \in [0, 1]$, $\ell_b > 0$, and $\ell_\sigma < 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 \in \mathcal{P}(\mathcal{X})$ be a club set, and let $X_n$, $n = 1, 2, \dots$, be the sequence of play generated by (RL) with parameters $\ell_\gamma \in [0, 1]$, $\ell_b > 0$, and $\ell_\sigma < 1/2$. Then, for all $\varepsilon > 0$, there exists an (open, unbounded) initialization domain $\mathcal{D} \subseteq \mathcal{Y}$ such that, with probability at least $1 - \varepsilon$, we have

$$\mathrm{dist}(X_n, S) \le C\varphi(c_1 - c_2 \sum_{k=1}^n \gamma_k) \quad \text{whenever } Y_1 \in \mathcal{D} \quad (20)$$

where $C, c_1, c_2$ are constants ($C, c_2 > 0$), and the rate function $\varphi$ is given by $\varphi(z) = (\theta')^{-1}(z)$ if $z > \lim_{z \to 0^+} \theta'(z)$, and $\varphi(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 = \prod_i C_i$ denote the support of $S$ (cf. the definition of club sets), and let

$$\mathcal{Z}_i = \{e_{i\alpha'_i} - e_{i\alpha_i} : \alpha_i \in C_i, \alpha'_i \in A_i \setminus C_i\} \quad (D.1)$$

and

$$\mathcal{Z} = \bigcup_{i \in \mathcal{N}} \mathcal{Z}_i \quad (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) = \langle y, z \rangle \quad \text{for } z \in \mathcal{Z}, y \in \mathcal{V}^*. \quad (D.3)$$
The motivation for this definition is given by the following lemma.

**Lemma D.1.** Suppose that the sequence $y_n \in \mathcal{V}^*$, $n = 1, 2, \dots$, has $E_z(y_n) \to -\infty$ for all $z \in \mathcal{Z}$ as $n \to \infty$. Then the sequence $x_n = Q(y_n)$ converges to $\mathcal{S}$ as $n \to \infty$.

*Proof.* Let $z = e_{i\alpha'_i} - e_{i\alpha_i}$ for some $i \in \mathcal{N}$, $\alpha_i \in \mathcal{C}_i$, and $\alpha'_i \in \mathcal{A}_i \setminus \mathcal{C}_i$. Since $E_z(y_n) \to -\infty$ by assumption, we get $y_{i\alpha'_i, n} - y_{i\alpha_i, n} \to -\infty$ and hence, by Lemma A.1, we conclude that $Q_{i\alpha'_i}(x_n) \to 0$ as $n \to \infty$. In turn, given that this holds for all $i \in \mathcal{N}$ and all $\alpha'_i \in \mathcal{A}_i \setminus \mathcal{C}_i$, we conclude that $x_n = Q(y_n)$ converges to $\mathcal{S}$.

In view of the above, we will focus on showing that $E_z(Y_n) \to -\infty$ for all $z \in \mathcal{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 \in \mathcal{Z}$ and let $E_n := E_z(Y_n)$. Then, for all $n = 1, 2, \dots$, we have

$$E_{n+1} \le E_n + \gamma_n \langle v(X_n), z \rangle + \gamma_n \xi_n + \gamma_n \psi_n \quad (D.4)$$

where the error terms $\xi_n$ and $\psi_n$ are given by

$$\xi_n = \langle U_n, z \rangle \quad \text{and} \quad \psi_n = 2B_n. \quad (D.5)$$

*Proof.* Simply set $y \leftarrow Y_{n+1}$ in $E_z(y)$, invoke the definition of the update $Y_n \leftarrow Y_{n+1}$ in (RL), and note that $|\langle b_n, z \rangle| \le \|z\| \|b_n\|_{\infty} \le 2B_n$ by the definition of $\mathcal{Z}$.

The key take-away from (D.4) is that, if $X_n$ is close to $\mathcal{S}$ and $\alpha_i \in \mathcal{C}_i$, $\alpha'_i \in \mathcal{A}_i \setminus \mathcal{C}_i$, we will have

$$\langle v(X_n), z \rangle = v_{i\alpha'_i}(X_n) - v_{i\alpha_i}(X_n) = u_i(\alpha'_i; X_{-i,n}) - u_i(\alpha_i; X_{-i,n}) < 0 \quad (D.6)$$

by the continuity of $u_i$ and the assumption that $\mathcal{S}$ is a club set. More concretely, by the definition of the better-reply correspondence, we have

$$\langle v(x^*), z \rangle < 0 \quad \text{for all } x^* \in \mathcal{S} \text{ and all } z \in \mathcal{Z} \quad (D.7)$$

and hence, by continuity, there exists a neighborhood $\mathcal{B}$ of $\mathcal{S}$ such that

$$\langle v(x), z \rangle < 0 \quad \text{for all } x \in \mathcal{B} \text{ and all } z \in \mathcal{Z}. \quad (D.8)$$

In other words, as long as $X_n$ is sufficiently close to $\mathcal{S}$, (D.4) exhibits a consistent negative drift pushing $E_n$ towards $-\infty$.

To exploit this “dynamic consistency” property of $\mathcal{S}$, it will be convenient to introduce the family of sets

$$\mathcal{D}(\varepsilon) = \{y \in \mathcal{V}^* : \langle y, z \rangle < -\varepsilon \text{ for all } z \in \mathcal{Z}\} \quad (D.9)$$

As we show below, these sets are mapped under $\mathcal{Q}$ to neighborhoods of $\mathcal{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 = \mathcal{Q}(y)$ for some $y \in \mathcal{V}^*$. Then, for all $\alpha_i, \alpha'_i, i \in \mathcal{N}$, we have

$$x_{i\alpha_i} \le \varphi(\theta(1^-) + y_{i\alpha'_i} - y_{i\alpha_i}) \quad (D.10)$$

with $\varphi$ defined as per Theorem 3, i.e.,

$$\varphi(z) = \begin{cases} 0 & \text{if } z \le \theta'(0^+), \\ (\theta')^{-1}(z) & \text{if } \theta'(0^+) < z < \theta'(1^-), \\ 1 & \text{if } z \ge \theta'(1^-). \end{cases} \quad (D.11)$$
**Corollary D.1.** For all $\delta > 0$ there exists some $\varepsilon_\delta \in \mathbb{R}$ such that, for all $\varepsilon > \varepsilon_\delta$ and all $y \in D_\varepsilon$, we have

$$Q_{i\alpha_i'}(y_i) < \delta \quad \text{for all } \alpha_i' \in A_i \setminus C_i \text{ and all } i \in \mathcal{N}. \qquad (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_{\alpha} - \theta'(x_{\alpha}) = \mu - \nu_{\alpha}, \qquad (D.13)$$

where $\mu$ is the Lagrange multiplier for the equality constraint $\sum_{\alpha} x_{\alpha} = 1$, and $\nu_{\alpha}$ is the complementary slackness multiplier of the inequality constraint $x_{\alpha} \ge 0$ (so $\nu_{\alpha} = 0$ whenever $x_{\alpha} > 0$). Thus, rewriting (D.13) for some $\alpha \in A$, we get

$$y_{\alpha'} - y_{\alpha} = \theta'(x_{\alpha'}) - \theta'(x_{\alpha}) + \nu_{\alpha} - \nu_{\alpha'} \qquad (D.14)$$

and hence

$$\theta'(x_{\alpha'}) = \theta'(x_{\alpha}) + \nu_{\alpha'} - \nu_{\alpha} + y_{\alpha'} - y_{\alpha} \le \theta'(1^{-}) + \nu_{\alpha'} + y_{\alpha'} - y_{\alpha}, \qquad (D.15)$$

where we used the fact that $\nu_{\alpha} \ge 0$. Now, if $\theta'(1^{-}) + y_{\alpha'} - y_{\alpha} < \theta'(0^{+})$ and $x_{\alpha'} > 0$ (so $\nu_{\alpha'} = 0$), we will have $\theta'(x_{\alpha'}) < \theta'(0^{+})$, a contradiction. This shows that $x_{\alpha'} = 0$ if $\theta'(1^{-}) + y_{\alpha'} - y_{\alpha} < \theta'(0^{+})$, so (D.10) is satisfied in this case. Otherwise, if $x_{\alpha'} > 0$, we must have $\nu_{\alpha'} = 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 = \sum_{k=1}^{n} \gamma_k \xi_k \quad \text{and} \quad \Pi_n = \sum_{k=1}^{n} \gamma_k \psi_k. \qquad (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 \to \infty} I_n / \tau_n = 0 \qquad (\text{Sub.I})$$

$$\lim_{n \to \infty} \Pi_n / \tau_n = 0 \qquad (\text{Sub.II})$$

where $\tau_n = \sum_{k=1}^n \gamma_k$ and both limits are to be interpreted in the almost sure sense.

(2) *Drift dominance:*

$$\mathbb{P}(I_n \le C \tau_n^\alpha / 2 \text{ for all } n) \ge 1 - \eta \qquad (\text{Dom.I})$$

$$\mathbb{P}(\Pi_n \le C \tau_n^\alpha / 2 \text{ for all } n) \ge 1 - \eta \qquad (\text{Dom.II})$$

for some $C > 0$ and $\alpha \in [0, 1)$.

In a nutshell, (Sub) posits that the aggregate error processes $I_n$ and $\Pi_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:
**Proposition D.1.** Let $\mathcal{S}$ be a club set, fix some confidence threshold $\eta > 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 $\mathcal{D} \subseteq \mathcal{V}^*$ such that

$$ \mathbb{P}(X_n \text{ converges to } \mathcal{S} | Y_1 \in \mathcal{D}) \geq 1 - 2\eta. \qquad (\text{D.19}) $$

*Proof of Proposition D.1.* Fix some $z \in \mathcal{Z}$, let $E_n = E_z(Y_n)$, and pick $\alpha \in [0, 1)$ so that (Dom) holds for some $C > 0$. In addition, set $c = -\sup_{x \in \mathcal{B}} \langle v(x), z \rangle > 0$, let $n_0 = \inf\{n : c\tau_n > C\tau_n^\alpha\}$, and write $\Delta E = \max_n\{C\tau_n^\alpha - c\tau_n\}$. Then, if $Y_1$ is initialized in $\mathcal{D} \leftarrow \mathcal{D}(\varepsilon + \Delta E)$ where $\varepsilon$ is such that $\mathcal{D}(\varepsilon) \subseteq \mathcal{B}$, we will have $Y_n \in \mathcal{D}(\varepsilon)$ for all $n$. Indeed, this being trivially the case for $n = 1$, assume it to be the case for all $k = 1, 2, \dots, n$. Then, by (D.4) and our inductive hypothesis, we get

$$ \begin{aligned} E_{n+1} &\le E_1 - \sum_{k=1}^n \gamma_k \langle v(X_k), z \rangle + I_n + \Pi_n \\ &\le -\varepsilon - \Delta E - c\tau_n + C\tau_n^\alpha/2 + C\tau_n^\alpha/2 \\ &\le -\varepsilon - \Delta E + \Delta E = -\varepsilon \end{aligned} \qquad (\text{D.20}) $$

i.e., $E_{n+1} \in \mathcal{D}(\varepsilon)$, as claimed.

Now, since $E_n \in \mathcal{D}(\varepsilon)$ for all $n$, we conclude that

$$ E_{n+1} \le E_1 - c\tau_n + I_n + \Pi_n \quad \text{for all } n = 1, 2, \dots \qquad (\text{D.21}) $$

Thus, if (Sub) holds, we readily get $E_n \to -\infty$ with probability 1 on the event that (Dom.I) and (Dom.II) both hold. This implies that $E_n \to -\infty$, and since $z \in \mathcal{Z}$ above is arbitrary, we conclude that $X_n \in \mathcal{S}$ with probability at least $1 - 2\eta$, 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 $\mathcal{X}$.

First, regarding (Sub), the law of large numbers for martingale difference sequences [26, Theorem 2.18] shows that $I_n/\tau_n \to 0$ with probability 1 on the event

$$ \left\{ \sum_n \gamma_n^2 \mathbb{E}[\xi_n^2 | \mathcal{F}_n] / \tau_n^2 < \infty \right\}. \qquad (\text{D.22}) $$

However

$$ \mathbb{E}[\xi_n^2 | \mathcal{F}_n] \le 2^2 \mathbb{E}[\|U_n\|_{\infty}^2 | \mathcal{F}_n] \le 2^2 \sigma_n^2 = \mathcal{O}(n^{2\ell_{\sigma}}) \qquad (\text{D.23}) $$

so, in turn, we get

$$ \sum_n \frac{\gamma_n^2 \mathbb{E}[\xi_n^2 | \mathcal{F}_n]}{\tau_n^2} = \mathcal{O}\left(\sum_n \frac{\gamma_n^2 \sigma_n^2}{\tau_n^2}\right) = \mathcal{O}\left(\sum_n \frac{n^{-2\ell_{\gamma}} n^{2\ell_{\sigma}}}{n^{2(1-\ell_{\gamma})}}\right) = \mathcal{O}\left(\sum_n \frac{1}{n^{2-2\ell_{\sigma}}}\right) < \infty \qquad (\text{D.24}) $$

given that $\ell_{\sigma} < 1/2$. This establishes (Sub.I); the remaining requirement (Sub.II) follows trivially by noting that $\sum_{k=1}^n \gamma_k B_k / \sum_{k=1}^n \gamma_k \to 0$ if and only if $B_n \to 0$, which is immediate from the theorem's assumptions.

Second, regarding (Dom), since $B_n$ is deterministic and $B_n = \mathcal{O}(1/n^{\ell_b})$ for some $\ell_b > 0$, it is always possible to find $C > 0$ and $\alpha \in (0, 1)$ so that (Dom.II) holds. We are thus left
to establish (Dom.I). To that end, let $I_n^* = \sup_{1 \le k \le n} |I_n|$ and set $P_n := \mathbb{P}(I_n^* > C \tau_n^\alpha/2)$ so

$$P_n \le \frac{\mathbb{E}[|I_n|^q]}{(C/2)^q \tau_n^{\alpha q}} \le c_q \frac{\mathbb{E}[(\sum_{k=1}^n \gamma_k^2 \|U_k\|_\infty^2)^{q/2}]}{\tau_n^{\alpha q}} \quad (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]:

$$\left(\sum_{k=1}^{n} a_k b_k\right)^{\rho} \le \left(\sum_{k=1}^{n} a_k^{\frac{\lambda\rho}{\rho-1}}\right)^{\rho-1} \sum_{k=1}^{n} a_k^{(1-\lambda)\rho} b_k^{\rho} \quad (D.26)$$

valid for all $a_k, b_k \ge 0$ and all $\rho > 1$, $\lambda \in [0, 1)$. Then, substituting $a_k \leftarrow \gamma_k^2$, $b_k \leftarrow \|U_k\|_\infty^2$, $\rho \leftarrow q/2$ and $\lambda \leftarrow 1/2 - 1/q$, (D.25) gives

$$P_n \le c_q \frac{(\sum_{k=1}^n \gamma_k)^{q/2-1} \sum_{k=1}^n \gamma_k^{1+q/2} \mathbb{E}[\|U_k\|_\infty^q]}{\tau_n^{\alpha q}} \le c_q \frac{\sum_{k=1}^n \gamma_k^{1+q/2} \sigma_k^q}{\tau_n^{1+(\alpha-1/2)q}} \quad (D.27)$$

We now consider two cases, depending on whether the numerator of (D.27) is summable or not.

**Case 1:** $\ell_\gamma(1 + q/2) \ge 1 + q\ell_\sigma$. 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-\ell_\gamma)(1+(\alpha-1/2)q)})$.

**Case 2:** $\ell_\gamma(1 + q/2) < 1 + q\ell_\sigma$. 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-\ell_\gamma(1+q/2)+q\ell_\sigma}/n^{1-\ell_\gamma(1+(\alpha-1/2)q)})$.

Thus, working out the various exponents, a tedious but otherwise straightforward calculation shows that there exists some $\alpha \in (0, 1)$ such that $P_n$ is summable as long as $\ell_\sigma < 1/2 - 1/q$ and $0 \le \ell_\gamma < q/(2+q)$. Hence, if $\gamma$ is sufficiently small relative to $\eta$, we conclude that

$$\mathbb{P}(I_n \le C \tau_n^\alpha/2 \text{ for all } n) \ge 1 - \sum_n P_n \ge 1 - \eta/2. \quad (D.28)$$

Finally, if $\ell_\gamma > 1/2 + \ell_\sigma$, (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** $\Rightarrow$ **Stability.** Our assertion follows by invoking Proposition D.1.

**Stability** $\Rightarrow$ **Closedness.** Suppose that $S$ is not club. Then there exists some pure strategy $\alpha \in S$ and some deviation $\alpha' \notin S$ such that the deviation from $\alpha$ to $\alpha'$ is not costly to the deviating player. Thus, if we consider the restriction of the game to the face spanned by $\alpha$ and $\alpha'$ (a single-player game with two strategies), the corresponding score difference will be

$$y_{\alpha',n} - y_{\alpha,n} \ge \sum_{k=1} \gamma_k b_k + \sum_{k=1} \gamma_k U_k \quad (D.29)$$

By our standing assumptions for $b_n$ and $U_n$ (and Doob's martingale convergence theorem for the latter), both $\sum_{k=1} \gamma_k b_k$ and $\sum_{k=1} \gamma_k U_k$ will be bounded from below by some (a.s.) finite random variable $A_0$. Since $\theta$ is steep, it follows that, with probability 1, $\liminf_{n \to \infty} (y_{\alpha,n}) > 0$, so $C$ cannot be stable.
**Minimality** $\Rightarrow$ **Irreducible Stability.** Suppose that $\mathcal{S}$ is m-club. Then, by our previous claim, $\mathcal{S}$ is stochastically asymptotically stable. If $\mathcal{S}$ contains a proper subface $S' \subsetneq \mathcal{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, $\mathcal{S}$ would not be m-club, a contradiction which proves our claim.

**Irreducible Stability** $\Rightarrow$ **Minimality.** For our last claim, assume that $\mathcal{S}$ is irreducibly stable. By the first part of our theorem, this implies that $\mathcal{S}$ is club. Then, if it so happens that $\mathcal{S}$ is not m-club, it would contain a proper club subface $S' \subsetneq \mathcal{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 $\mathcal{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 \in \mathbb{R}$ such that, for all $\alpha_i \in A_i \setminus C_i$, $i \in \mathcal{N}$, we have

$$X_{i\alpha_i, n} \leq \varphi(\theta(1^{-}) + E_n) \leq \varphi(c_2 - c_1\tau_n) \quad (D.30)$$

with probability 1 on the events of (Dom). We thus get

$$\mathrm{dist}_1(X_n, \mathcal{S}) \leq \sum_{i \in \mathcal{N}} \sum_{\alpha_i \in A_i \setminus C_i} \varphi(c_2 - c_1 \tau_n), \quad (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 $\theta(z) = z \log z$ then $\varphi(z) = \exp(1 + z)$.

(2) If $\theta(z) = -4\sqrt{z}$ then $\varphi(z) = 4/z^2$.

(3) If $\theta(z) = z^2/2$ then $\varphi(z) = [z]_0^1$.

Our claims then follow immediately from the rate estimate (20) of Theorem 2. ■

## APPENDIX E. NUMERICAL EXPERIMENTS

In all our experiments, we ran the EXP3 variant of bandit FTRL (B-FTRL) (cf. Algorithm 3) with step-size and sampling radius parameters $\gamma_n = 0.2 \times n^{-1/2}$ and $\delta_n = 0.1 \times 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 \in \{-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
<figure><img src="image_3.png" /><figcaption>**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⁵ iterations with γn = 1/n⁰.⁴ and δn = 0.1/n⁰.¹⁵; 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).</figcaption></figure>

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.

<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /></figure>

REFERENCES

[1] Abernethy, J., Lee, C., and Tewari, A. Fighting bandits with a new kind of smoothness. In NIPS '15: Proceedings of the 29th International Conference on Neural Information Processing Systems, 2015.

[2] Arora, S., Hazan, E., and Kale, S. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8(1):121–164, 2012.

[3] Audibert, J.-Y. and Bubeck, S. Regret bounds and minimax policies under partial monitoring. Journal of Machine Learning Research, 11:2635–2686, 2010.

[4] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995.

[5] Auer, P., Cesa-Bianchi, N., and Fischer, P. Finite-time 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 on Computing, 32(1):48–77, 2002.

[7] Basu, K. and Weibull, J. 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., Émery, 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 Heidelberg, 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] Cesa-Bianchi, N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University Press, 2006.

[12] Chavdarova, T., Gidel, G., Fleuret, F., and Lacoste-Julien, S. Reducing noise in GAN training with variance reduced extragradient. In NeurIPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.

[13] Chotibut, T., Falniowski, F., Misiurewicz, M., and Piliouras, G. Family of chaotic maps from game theory. Dynamical Systems, 2020.

[14] Coucheney, P., Gaujal, B., and Mertikopoulos, P. Penalty-regulated dynamics and robust learning procedures in games. Mathematics of Operations Research, 40(3):611–633, August 2015.

[15] Cressman, R. Evolutionary Dynamics and Extensive Form Games. The MIT Press, 2003.
[16] Daskalakis, C. and Panageas, I. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In *ITCS '19: Proceedings of the 10th Conference on Innovations in Theoretical Computer Science*, 2019.

[17] Daskalakis, C., Ilyas, A., Syrgkanis, V., and Zeng, H. Training GANs with optimism. In *ICLR '18: Proceedings of the 2018 International Conference on Learning Representations*, 2018.

[18] Demichelis, S. and Ritzberger, K. From evolutionary to strategic stability. *Journal of Economic Theory*, 113:51–75, 2003.

[19] Dudík, M., Schapire, R. E., and Telgarsky, M. Convex analysis at infinity: An introduction to astral space. https://arxiv.org/abs/2205.03260, 2022.

[20] Erev, I. and Roth, A. E. Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria. *American Economic Review*, 88:848–881, 1998.

[21] Flokas, L., Vlatakis-Gkaragkounis, E. V., Lianeas, T., Mertikopoulos, P., and Piliouras, G. No-regret learning and mixed Nash equilibria: They do not mix. In *NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems*, 2020.

[22] Fudenberg, D. and Tirole, J. *Game Theory*. The MIT Press, 1991.

[23] Giannou, A., Vlatakis-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.

[24] 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 *NeurIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems*, 2021.

[25] Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S. A variational inequality perspective on generative adversarial networks. In *ICLR '19: Proceedings of the 2019 International Conference on Learning Representations*, 2019.

[26] Hall, P. and Heyde, C. C. *Martingale Limit Theory and Its Application*. Probability and Mathematical Statistics. Academic Press, New York, 1980.

[27] Hannan, J. Approximation to Bayes risk in repeated play. In Dresher, M., Tucker, A. W., and Wolfe, P. (eds.), *Contributions to the Theory of Games, Volume III*, volume 39 of *Annals of Mathematics Studies*, pp. 97–139. Princeton University Press, Princeton, NJ, 1957.

[28] Hofbauer, J. and Sigmund, K. Evolutionary game dynamics. *Bulletin of the American Mathematical Society*, 40(4):479–519, July 2003.

[29] Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P. On the convergence of single-call stochastic extra-gradient methods. In *NeurIPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Systems*, pp. 6936–6946, 2019.

[30] Hsieh, Y.-G., Iutzeler, F., Malick, J., and Mertikopoulos, P. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In *NeurIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems*, 2020.

[31] Juditsky, A., Nemirovski, A. S., and Tauvel, C. Solving variational inequalities with stochastic mirror-prox algorithm. *Stochastic Systems*, 1(1):17–58, 2011.

[32] Kohlberg, E. and Mertens, J.-F. On the strategic stability of equilibria. *Econometrica*, 54(5): 1003–1037, September 1986.

[33] Lattimore, T. and Szepesvári, C. *Bandit Algorithms*. Cambridge University Press, Cambridge, UK, 2020.

[34] Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. *Information and Computation*, 108(2):212–261, 1994.

[35] Mertikopoulos, P. and Sandholm, W. H. Learning in games via reinforcement and regularization. *Mathematics of Operations Research*, 41(4):1297–1324, November 2016.

[36] Mertikopoulos, P. and Zhou, Z. Learning in games with continuous action sets and unknown payoff functions. *Mathematical Programming*, 173(1-2):465–507, January 2019.

[37] 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.
[38] Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chandrasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In *ICLR '19: Proceedings of the 2019 International Conference on Learning Representations*, 2019.

[39] Nemirovski, A. S. Prox-method with rate of convergence $O(1/t)$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. *SIAM Journal on Optimization*, 15(1):229–251, 2004.

[40] Palaiopanos, G., Panageas, I., and Piliouras, G. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. In *NIPS '17: Proceedings of the 31st International Conference on Neural Information Processing Systems*, 2017.

[41] Piliouras, G., Sim, R., and Skoulakis, S. Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu. https://arxiv.org/abs/2111.14737, 2021.

[42] 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):845–848, 1980.

[43] Rakhlin, A. and Sridharan, K. Online learning with predictable sequences. In *COLT '13: Proceedings of the 26th Annual Conference on Learning Theory*, 2013.

[44] Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. In *NIPS '13: Proceedings of the 27th International Conference on Neural Information Processing Systems*, 2013.

[45] Ritzberger, K. and Weibull, J. W. Evolutionary selection in normal-form games. *Econometrica*, 63 (6):1371–99, November 1995.

[46] Rockafellar, R. T. and Wets, R. J. B. *Variational Analysis*, volume 317 of *A Series of Comprehensive Studies in Mathematics*. Springer-Verlag, Berlin, 1998.

[47] Shalev-Shwartz, S. Online learning and online convex optimization. *Foundations and Trends in Machine Learning*, 4(2):107–194, 2011.

[48] Shalev-Shwartz, 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.

[49] 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.

[50] van Damme, E. *Stability and perfection of Nash equilibria*. Springer-Verlag, Berlin, 1987.

[51] Viossat, Y. and Zapechelnyuk, A. No-regret dynamics and fictitious play. *Journal of Economic Theory*, 148(2):825–842, March 2013.

[52] Vovk, V. G. Aggregating strategies. In *COLT '90: Proceedings of the 3rd Workshop on Computational Learning Theory*, pp. 371–383, 1990.

[53] Weibull, J. W. *Evolutionary Game Theory*. MIT Press, Cambridge, MA, 1995.

[54] Zimmert, J. and Seldin, Y. An optimal algorithm for stochastic and adversarial bandits. In *AISTATS '19: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics*, 2019.

[55] Zimmert, J. and Seldin, Y. Tsallis-INF: An optimal algorithm for stochastic and adversarial bandits. *Journal of Machine Learning Research*, 22(28):1–49, 2021.