Angeliki Giannou
email: giannouangeliki@gmail.com

Emmanouil V Vlatakis-Gkaragkounis

Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond

In this paper, we examine the convergence rate of a wide range of regularized methods for learning in games. To that end, we propose a unified algorithmic template that we call "follow the generalized leader" (FTGL), and which includes as special cases the canonical "follow the regularized leader" algorithm, its optimistic variants, extra-gradient schemes, and many others. The proposed framework is also sufficiently flexible to account for several different feedback models -from full information to bandit feedback. In this general setting, we show that FTGL algorithms converge locally to strict Nash equilibria at a rate which does not depend on the level of uncertainty faced by the players, but only on the geometry of the regularizer near the equilibrium. In particular, we show that algorithms based on entropic regularization -like the exponential weights algorithm -enjoy a linear convergence rate, while Euclidean projection methods converge to equilibrium in a finite number of iterations, even with bandit feedback.

Introduction

In the presence of uncertainty, the players of a game may not have full knowledge of its structure, "or the ability and inclination to go through any complex reasoning process to calculate an equilibrium. But the participants are still supposed to adapt by accumulating empirical information on the relative advantages of the various pure strategies at their disposal". This aphorism -originally due to Nash [34, p. 21] -constitutes the driving principle of game-theoretic learning, and highlights one of the field's most central questions: Does learning with empirical observations lead to a Nash equilibrium? And, if so, at what rate?

These questions have been at the forefront of game-theoretic research ever since the early days of the field, and they have recently received renewed attention via their connection to multi-agent reinforcement learning [START_REF] Shoham | Multiagent systems: Algorithmic, game-theoretic, and logical foundations[END_REF], generative adversarial networks [START_REF] Goodfellow | Generative adversarial nets[END_REF], auctions [START_REF] Syrgkanis | Fast convergence of regularized learning in games[END_REF], and many other applications where online decision-making plays a major role. Still, any attempt to provide a positive answer to these questions must wrestle with a major roadblock: the well-known impossibility result of Hart and Mas-Colell [START_REF] Hart | Uncoupled dynamics do not lead to Nash equilibrium[END_REF] shows that there are no uncoupled dynamics that converge to Nash equilibrium in all games, thus shattering any hope of obtaining a universal convergence result.

In view of the above, contemporary research on game-theoretic learning has focused on relaxing the feedback requirements of the players' learning processes, and understanding the stability -and instability -properties of different kinds of equilibria under popular learning algorithms. One property that stands out in this regard is the so-called "folk theorem" of evolutionary game theory [START_REF] Hofbauer | Evolutionary game dynamics[END_REF], which can be stated as follows: Under the replicator dynamics -the continuous-time limit of the multiplicative / exponential weights (EW) algorithm [START_REF] Auer | Gambling in a rigged casino: The adversarial multi-armed bandit problem[END_REF][START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Vladimir | Aggregating strategies[END_REF] a Nash equilibrium is stable and attracting if and only if it is strict (i.e., if and only if each player has a unique best response).

The replicator dynamics are the most widely studied model for evolution in population games, so the above equivalence essentially delineates what is and what isn't achievable in an evolutionary setting. In the context of online learning (our paper's main focus), a similar equivalence was obtained only recently [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF][START_REF] Giannou | Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF], but it extends to the entire family of "follow the regularized leader" (FTRL) dynamics [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Shalev | Convex repeated games and Fenchel duality[END_REF], in both continuous [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF][START_REF] Mertikopoulos | Learning in games via reinforcement and regularization[END_REF] and discrete time [START_REF] Giannou | Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information[END_REF]. In particular, [START_REF] Giannou | Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information[END_REF] studied the convergence of discrete-time FTRL models in the presence of uncertainty, and proved a high-probability, stochastic version of this equivalence that holds for several different types of feedback (full information, bandit, etc.). Thus, coupled with the prominence of FTRL in online and game-theoretic learning, strict Nash equilibria emerge as the only stable limit points of regularized learning under uncertainty.

Our contributions. One important limitation of the above results is that they are qualitative in nature. Indeed, even though asymptotic stability guarantees that a learning process converges locally to a strict equilibrium, it provides no information about the speed of this convergence. In particular, especially for discrete-time models of regularized learning, asymptotic stability does not provide any guidance on how to tune the algorithm's hyperparameters (learning rate, mixing, etc.), and/or what to expect in terms of the number of iterations required to reach a neighborhood of a Nash equilibrium.

Our paper aims to provide quantitative answers to these questions for a wide array of regularized learning methods in the presence of uncertainty and limited information. To do so, we first introduce a flexible algorithmic framework -dubbed "follow the generalized leader" (FTGL) -that incorporates a broad spectrum of action choice mechanisms and feedback models. In more detail (and in analogy to FTRL), the FTGL template maintains a cumulative estimate for the payoff of each action available to the learner, and then selects a mixed strategy via a suitable "regularized" choice map. Specifically:

1. In terms of regularization, the FTGL template includes as special cases the standard logit choice and Euclidean projection methods (as well as all other standard regularizers used in practice).

2. In terms of the information used to update the "aggregate score" of each pure strategy, FTGL includes "vanilla" FTRL, its optimistic variants [START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Denisovich | A modification of the Arrow-Hurwicz method for search of saddle points[END_REF][START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF], extra-gradient and mirror-prox methods [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF][START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF][START_REF] Semen | Prox-method with rate of convergence 𝑂 (1/𝑡) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF], with either full, oracle-based, or bandit feedback.

In this general context, our main result may be summarized as follows. First, we introduce a "rate function" 𝜙 that depends only on the regularizer defining the learning process, and which captures the sensitivity of the induced choice map to external stimuli: for example, 𝜙(𝑥) = exp(𝑥) for entropic / logit choice models, whereas 𝜙(𝑥) = [𝑥] + for methods run with Euclidean projections. We then show that, with probability at least 1 -𝛿, the algorithm's local rate of convergence to a strict equilibrium 𝑥 * is of the form ∥ 𝑋 𝑛 -𝑥 * ∥ ≤ 𝜙(𝑑 -𝑐 𝑛 𝑠=1 𝛾 𝑠 ), where 𝛾 𝑛 is the method's learning rate and 𝑐, 𝑑 are constants with 𝑐 > 0.

This result shows that the convergence speed of FTGL methods depends only on the choice of regularizer and learning rate: for example, EW methods run with a constant step size converge to an equilibrium at an exponential rate, whereas Euclidean regularization attains convergence in a finite number of iterations. From a regret-theoretic point of view, this is somewhat surprising because the regret guarantees of entropic FTRL (the EW algorithm) are far superior to those of FTRL with Euclidean regularization [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF].

Equally surprising is the fact that the type of feedback employed does not affect the method's rate of convergence: ceteris paribus, an FTGL method attains the same rate of convergence to strict Nash equilibria, whether run with full, partial, or bandit / payoff-based feedback. This comes into stark contrast with the corresponding rates of regret minimization, which depend crucially on the type of feedback received [START_REF] Cesa | Prediction, Learning, and Games[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF]; in a certain, precise sense, this robustness in the face of uncertainty shows that regret minimization and convergence to Nash equilibrium are fundamdentally different questions.

Related work. The convergence speed of methods based on the FTRL template -"vanilla", optimistic, or otherwise -have been studied extensively in the context of monotone games and variational inequalities; for a (highly incomplete) list of recent references, see [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF][START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Gauthier Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Golowich | Tight last-iterate convergence rates for no-regret learning in multi-player games[END_REF][START_REF] Hsieh | On the convergence of single-call stochastic extra-gradient methods[END_REF][START_REF] Hsieh | Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium[END_REF][START_REF] Lin | Finite-time last-iterate convergence for multi-agent learning in games[END_REF][START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF][START_REF] Mertikopoulos | Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile[END_REF][START_REF] Mokhtari | Convergence rate of O (1/𝑘) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems[END_REF] and references therein. In this branch of the literature, there are two distinct threads: results concerning the convergence of the "time-average" of the process [START_REF] Gauthier Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF][START_REF] Mokhtari | Convergence rate of O (1/𝑘) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems[END_REF][START_REF] Semen | Prox-method with rate of convergence 𝑂 (1/𝑡) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF], and those focusing on the algorithm's "last-iterate" [START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF][START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Golowich | Tight last-iterate convergence rates for no-regret learning in multi-player games[END_REF][START_REF] Hsieh | On the convergence of single-call stochastic extra-gradient methods[END_REF][START_REF] Hsieh | Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium[END_REF][START_REF] Lin | Finite-time last-iterate convergence for multi-agent learning in games[END_REF]. In the latter case (which is the one closest to our setting), the fastest achievable speed of convergence is exponential when the method is run with a finetuned constant step-size, perfect payoff gradient observations, and the operator defining the problem is strongly monotone and Lipschitz smooth. When run with stochastic gradients, the corresponding min-max optimal rate is O(1/𝑇) under the same assumptions (zeroth-order rates are usually much worse). The apparent gulf between the rates of convergence obtained for monotone games and those obtained herein have to do with two crucial factors: first, we are studying finite games, which are typically not monotone; second, we are examining the algorithm's rate of convergence to strict equilibria, which are corner points of the problem's domain. This means that the geometry of the problem around a strict equilibrium is fundamentally sharper than the geometry around a solution of a generic monotone variational inequality, a fact which in turn explains the qualitatively different nature of the rates we obtain.

In the context of finite games, there have been several works examining the speed of convergence to the game's set of coarse correlated equilibria (CCE) by leveraging the algorithm's regret minimization properties, cf. [START_REF] Blum | Learning, regret minimization, and equilibria[END_REF][START_REF] Blum | Routing without regret: on convergence to Nash equilibria of regretminimizing in routing games[END_REF][START_REF] Foster | Calibrated learning and correlated equilibrium[END_REF][START_REF] Freund | Adaptive game playing using multiplicative weights[END_REF][START_REF] Nisan | Algorithmic Game Theory[END_REF][START_REF] Syrgkanis | Fast convergence of regularized learning in games[END_REF] and references therein. However, in addition to examining the algorithm's empirical average -as opposed to the induced day-to-day sequence of play -these results focus almost exclusively on CCE, which means that it is not possible to draw any conclusions about convergence to the game's Nash set -qualitatively or quantitatively. To the best of our knowledge, the closest work to our own in the literature is the paper of Cohen et al. [START_REF] Cohen | Learning with bandit feedback in potential games[END_REF] who showed that the EXP3 algorithm with explicit exploration converges at a sub-geometric rate in potential games; our analysis allows for a wider range of learning rates, so we are able to obtain faster convergence rates than Cohen et al. [START_REF] Cohen | Learning with bandit feedback in potential games[END_REF]. We are not aware of any other comparable results in the literature.

Preliminaries

Finite games. Throughout this work we consider 𝑁-players finite games in normal form. Formally, each player, indexed by 𝑖 ∈ N = {1, . . . , 𝑁 }, has a finite set of pure strategies 𝛼 𝑖 ∈ A 𝑖 = {1, . . . , 𝐴 𝑖 }, and a payoff function 𝑢 𝑖 : A → ℝ, where A 𝑖 A 𝑖 is the space of all pure strategy profiles. For concision, we will denote such a game as a tuple Γ = Γ(N , A, 𝑢).

During play, players can also play mixed strategies, i.e., probability distributions 𝑥 𝑖 ∈ X 𝑖 Δ(A 𝑖 ) over their pure strategies. In this case, we will write 𝑥 𝑖 𝛼 𝑖 for the probability that player 𝑖 ∈ N selects 𝛼 𝑖 ∈ A 𝑖 under 𝑥 𝑖 , 𝑥 = (𝑥 1 , . . . , 𝑥 𝑁 ) for the players' mixed strategy profile, and X 𝑖 X 𝑖 for the set thereof. Finally, when focusing on the mixed strategy of a particular player 𝑖 ∈ N , we will use the shorthand (𝑥 𝑖 ; 𝑥 -𝑖 ) (𝑥 1 , . . . , 𝑥 𝑖 , . . . , 𝑥 𝑁 ) -and, similarly, (𝛼 𝑖 ; 𝛼 -𝑖 ) for pure strategies. Now, the expected payoff of player 𝑖 in a mixed strategy profile 𝑥 ∈ X is given by

𝑢 𝑖 (𝑥) ≡ 𝑢 𝑖 (𝑥 𝑖 ; 𝑥 -𝑖 ) = ∑ 𝛼 1 ∈A 1 • • • ∑ 𝛼 𝑁 ∈A 𝑁 𝑢 𝑖 (𝛼 1 , . . . , 𝛼 𝑁 ) • 𝑥 1, 𝛼 1 • • • 𝑥 𝑁 , 𝛼 𝑁 (1)
where 𝑢 𝑖 (𝛼 1 , . . . , 𝛼 𝑁 ) is the payoff of player 𝑖 in the action profile 𝛼 = (𝛼 1 , . . . , 𝛼 𝑁 ) ∈ A. For posterity, we will also write 𝑣 𝑖 𝛼 𝑖 (𝑥) = 𝑢 𝑖 (𝛼 𝑖 ; 𝑥 -𝑖 ) for the payoff that player 𝑖 would have gotten by playing 𝛼 𝑖 ∈ A 𝑖 against the mixed strategy profile 𝑥 -𝑖 of all other players. In this way, the mixed payoff vector of the 𝑖-th player can be seen as a vector field 𝑣 𝑖 : X → Y 𝑖 = ℝ A 𝑖 which can be written in components as

𝑣 𝑖 (𝑥) = (𝑣 𝑖 𝛼 𝑖 (𝑥)) 𝛼 𝑖 ∈A 𝑖 . (2)
Again, we will write 𝑣(𝑥) = (𝑣 1 (𝑥), . . . , 𝑣 𝑁 (𝑥)) for the ensemble of payoff vectors of all players and Y = 𝑖 Y 𝑖 for the space of payoff vectors respectively. Finally, in a slight abuse of notation, we will identify 𝛼 𝑖 with the mixed strategy that assigns all probability to 𝛼 𝑖 , and we will write 𝑣 𝑖 (𝛼) = (𝑢 𝑖 (𝛼 𝑖 ; 𝛼 -𝑖 )) 𝛼 𝑖 ∈A 𝑖 . for the corresponding pure payoff vector. Finally, we will also say that a Nash equilibrium 𝑥 * is strict if (NE) holds as a strict inequality whenever 𝑥 𝑖 ≠ 𝑥 * 𝑖 ; obviously, strict equilibria are also pure, but the converse need not hold. Strict Nash equilibria play a key role in game theory because any unilateral deviation incurs a strict loss to the deviating player; put differently, if 𝑥 * is strict, every player has a unique best response. In addition, they are the only equilibria that remain invariant under small generic perturbations of the game [START_REF] Fudenberg | Game Theory[END_REF]; these robustness properties of strict equilibria will play a key role in the sequel.

Regularized learning

Throughout our paper, we will focus on a wide family of learning schemes that unfold as follows: At each stage 𝑛 = 1, 2, . . . , every player maintains a "score vector" 𝑌 𝑖,𝑛 ∈ Y 𝑖 whose components indicate the player's propensity to play a given pure strategy. More formally, this is captured by a player-specific "regularized choice" map 𝑄 𝑖 : Y 𝑖 → X 𝑖 which outputs the player's mixed strategy 𝑋 𝑖,𝑛 = 𝑄 𝑖 (𝑌 𝑖,𝑛 ) as a function of 𝑌 𝑖,𝑛 (see below for a detailed definition). Then, after selecting their actions and collecting their rewards, players also receive -or otherwise construct -an estimate 𝑉 𝑖,𝑛 of their mixed payoff vectors, which is used to increment their score variables and continue playing.

Formally, this learning process, which we call "follow the generalized leader" (FTGL), can be described via the round-by-round recursive rule

𝑋 𝑖,𝑛 = 𝑄 𝑖 (𝑌 𝑖,𝑛 ) 𝑌 𝑖,𝑛+1 = 𝑌 𝑖,𝑛 + 𝛾 𝑛 𝑉 𝑖,𝑛 (FTGL)
where 𝛾 𝑛 > 0 is a "learning rate" parameter such that 𝑛 𝛾 𝑛 = ∞. The terminology FTGL alludes to the widely known "follow the regularized leader" algorithm, which is, historically speaking, the parent-scheme of FTGL. The link to regularization is provided by the method's choice map, which we detail below; the assumptions for the signal sequence 𝑉 𝑖,𝑛 are provided right after.

3.1. The choice map. The guiding principle behind the definition of the players' choice maps 𝑄 𝑖 : Y 𝑖 → X 𝑖 , 𝑖 ∈ N , as follows: Because the players' score variables 𝑌 𝑖,𝑛 are assumed to represent an estimate of each strategy's cumulative payoff over time, 𝑄 𝑖 is defined as a "regularized" version of the best-response correspondence 𝑦 𝑖 ↦ → arg max 𝑥 𝑖 ∈X 𝑖 ⟨𝑦 𝑖 , 𝑥 𝑖 ⟩. 1 On that account, we will consider regularized best responses of the general form

𝑄 𝑖 (𝑦 𝑖 ) = arg max 𝑥 𝑖 ∈X 𝑖 {⟨𝑦 𝑖 , 𝑥 𝑖 ⟩ -ℎ 𝑖 (𝑥 𝑖 )} (3)
where ℎ 𝑖 : X 𝑖 → ℝ denotes the 𝑖-th player's regularization function.

For concreteness, we will focus on a class of decomposable regularizers of the form ℎ 𝑖 (𝑥 𝑖 ) = 𝛼 𝑖 ∈A 𝑖 𝜃 𝑖 (𝑥 𝑖 ) where the so-called "kernel function" 𝜃 𝑖 : [0, 1] → ℝ is assumed continuous on [0, 1], twice differentiable on (0, 1], and strongly convex, i.e., inf (0,1] 𝜃 ′′ 𝑖 > 0. Of course, different regularizers give rise to different instances of (FTGL); two of the most widely used and cited examples are as follows: Example 3.1 (Entropic regularization and multiplicative/exponential weights). Perhaps the most common representative of regularization functions is given by the entropic kernel 𝜃 (𝑥) = 𝑥 log 𝑥 i.e., ℎ(𝑥 𝑖 ) = 𝛼 𝑖 ∈A 𝑖 𝑥 𝑖 𝛼 𝑖 log 𝑥 𝑖 𝛼 𝑖 . This choice of regularizer is well-known to provide the logit choice map Λ 𝑖 (𝑦 𝑖 ) = (exp(𝑦 𝑖 𝛼 𝑖 )) 𝛼 𝑖 ∈A 𝑖 𝛼 𝑖 ∈A 𝑖 exp(𝑦 𝑖 𝛼 𝑖 ). The resulting algorithm is known in the literature as the multiplicative/exponential weights algorithm [START_REF] Arora | The multiplicative weights update method: A meta-algorithm and applications[END_REF][START_REF] Auer | Gambling in a rigged casino: The adversarial multi-armed bandit problem[END_REF][START_REF] Littlestone | The weighted majority algorithm[END_REF][START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Vladimir | Aggregating strategies[END_REF]. Example 3.2 (Euclidean projection). Another popular regularizer is the quadratic penalty ℎ(𝑥) = 𝑎 𝑥 𝑎 2 /2, which yields the payoff projection map Π(𝑦) = arg min 𝑥 ∈Δ ∥𝑦 -𝑥∥ 2 , cf. [START_REF] Lahkar | The projection dynamic and the geometry of population games[END_REF][START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF].

Remark 3.1. Examples 3.1 and 3.2 are archetypes of a fundamental dichotomy between regularization functions: in the former case, we have 𝜃 ′ (0) = -∞, so ℎ becomes steep at the boundary of the player's strategy space; in the later case, 𝜃 is differentiable at 0, so ℎ is non-steep. We will see that this steep/non-steep dichotomy has a crucial impact on the method's rate of convergence.

The feedback model.

As we mentioned in the beginning of the section, the "payoff signal" 𝑉 𝑛 contains information about the structure of the algorithm as well as the setting under consideration. Thus to account for as broad a range of algorithms as possible, we will assume that the players' signal sequence is of the general form 𝑉 𝑛 = 𝑣(𝑋 𝑛 ) + 𝑍 𝑛 (4) for some abstract error process 𝑍 𝑛 = (𝑍 𝑖,𝑛 ) 𝑖 ∈N . Tp be clear though, we should stress that we do not assume that 𝑉 𝑛 is directly correlated to -or obtained by -the chosen mixed strategy 𝑋 𝑛 ; this will be made clear in the range of models we present below.

To distinguish between random (zero-mean) and systematic (non-zero-mean) errors, we will further decompose 𝑍 𝑛 as 𝑍 𝑛 = 𝑈 𝑛 + 𝑏 𝑛 , where

𝑏 𝑛 = 𝔼[𝑍 𝑛 | F 𝑛 ] and 𝔼[𝑈 𝑛 | F 𝑛 ] = 0 (5)
with F 𝑛 denoting the history of 𝑋 𝑛 up to stage 𝑛 (inclusive). Notice that, since the feedback signal is generated only after the player chooses a strategy, 𝑉 𝑛 is not F 𝑛 -measurable in general. On this account, we will make the following blanket assumptions for the input signal sequence 𝑉 𝑛 :

1. Vanishing bias:

𝑏 𝑛 converges uniformly to 0 as 𝑛 → ∞. (A1) 2. Bounded variance: 𝔼[∥𝑈 𝑛 ∥ 𝑞 * | F 𝑛 ] ≤ 𝜎 𝑞 𝑛 for some 𝑞 > 2. (A2)
In the above 𝜎 𝑛 is assumed to be a deterministic, stage-specific, and possibly increasing bound on the variance of the noise component 𝑈 𝑛 ; our precise assumptions for its growth (relative to 𝑏 𝑛 or otherwise) will be detailed later in this section.

Specific models. So far, the formulation of (FTGL) has been kept intentionally abstract and devoid of any modeling assumptions for how the players' payoff signals are generated or estimated. To illustrate the width and breadth of (FTGL), we present of series of specific models below, including the popular FTRL and optimistic FTRL methods: Model 1 (FTRL with oracle-based feedback). Assume that each player chooses an action based on a given mixed strategy, and once every player has chosen an action, an oracle reveals to each player their corresponding pure payoff vector. Formally, at each round 𝑛 = 1, 2, . . . , each player chooses a pure strategy 𝛼 𝑖,𝑛 ∈ A 𝑖 based on a mixed strategy 𝑋 𝑖,𝑛 ∈ X 𝑖 and subsequently observes the payoff vector 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ) = (𝑢 𝑖 (𝛼 𝑖 ; 𝛼 -𝑖,𝑛 )) 𝛼 𝑖 ∈A 𝑖 . (6) Thus, in this case, (FTGL) boils down to the standard "follow the regularized leader" (FTRL) algorithm of [START_REF] Shalev-Shwartz | Online learning and online convex optimization[END_REF][START_REF] Shalev | Convex repeated games and Fenchel duality[END_REF]. As for our basic feedback assumptions, we readily see that 𝑏 𝑖,𝑛 = 0 and 𝑈 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ); hence:

• (A1) is trivially satisfied since 𝑏 𝑖,𝑛 = 0. • (A2) is again satisfied because ∥𝑈 𝑖,𝑛 ∥ * = ∥𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ) ∥ * ≤ 2 max 𝛼∈A ∥𝑣 𝑖 (𝛼) ∥ * , so 𝑈 𝑛 has uniformly bounded moments for all 𝑞 ∈ [1, ∞]. §
Model 2 (FTRL with bandit feedback). If the players only observe their realized rewards, they have to construct a model for 𝑉 𝑛 based on incomplete information. This is the standard setting for multi-armed bandits [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Cesa | Prediction, Learning, and Games[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF], so it is often referred to as the "bandit feedback" model. In this case, the players' action selection process is as in Model 1 above, but the feedback signal sequence 𝑉 𝑛 is now reconstructed by means of the importance-weighted estimator

𝑉 𝑖 𝛼 𝑖 ,𝑛 = 1{𝛼 𝑖,𝑛 = 𝛼 𝑖 } X𝑖𝛼 𝑖,𝑛 𝑢 𝑖 (𝛼 𝑛 ) (IWE)
where X𝑖,𝑛 = (1 -𝜀 𝑛 ) 𝑋 𝑖,𝑛 + 𝜀 𝑛 /|A 𝑖 | is the mixed strategy of the 𝑖-th player at stage 𝑛. Compared to 𝑋 𝑖,𝑛 the player's actual sampling strategy is now recalibrated by an explicit exploration parameter 𝜀 𝑛 → 0 whose role is to stabilize the learning process. The idea behind this adjustment is that even if a strategy has zero probability to be chosen under 𝑋 𝑛 , it will still be sampled with positive probability thanks to the mixing factor 𝜀 𝑛 .

Feedback FTRL OptFTRL EG / MP Full information 𝑏 𝑛 = 0 𝑀 𝑛 = 0 ∥𝑏 𝑛 ∥ * = O (𝛾 𝑛 ) 𝑀 𝑛 = 0 ∥𝑏 𝑛 ∥ * = O (𝛾 𝑛 ) 𝑀 𝑛 = 0 Oracle-based 𝑏 𝑛 = 0 𝑀 𝑛 = O (1) ∥𝑏 𝑛 ∥ * = O (𝛾 𝑛 ) 𝑀 𝑛 = O (1) ∥𝑏 𝑛 ∥ * = O (𝛾 𝑛 ) 𝑀 𝑛 = O (1) Bandit (payoff-based) ∥𝑏 𝑛 ∥ * = O ( 𝜀 𝑛 ) 𝑀 𝑛 = Θ(1/𝜀 𝑛 ) ∥𝑏 𝑛 ∥ * = O ( 𝜀 𝑛 ) 𝑀 𝑛 = Θ(1/𝜀 𝑛 ) ∥𝑏 𝑛 ∥ * = O ( 𝜀 𝑛 ) 𝑀 𝑛 = Θ(1/𝜀 𝑛 )
Table 1: Recasting different online learning algorithms within the general template of (FTGL).

The importance-weighted estimator (IWE) estimator may be seen as a special case of the model ( 4) with 𝑈 𝑖,𝑛 = 𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) and 𝑏 𝑖,𝑛 = 𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ). Both assumptions (A1),(A2) are again satisfied; indeed:

• For (A1): A standard calculation performed in Appendix D reveals that ∥𝑏 𝑖,𝑛 ∥ * = 𝑂 (𝜀 𝑛 ). Thus our assumption is satisfied since 𝜀 𝑛 → 0. • For (A2): Again a standard calculation presented in Appendix D reveals that ∥𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) ∥ * = 𝑂 (1/𝜀 𝑛 ) and thus the noise has bounded moments,

𝜎 𝑛 = Θ(1/𝜀 𝑛 ) for all 𝑞 ∈ [1, ∞].
Model 3 (OptFTRL with oracle-based feedback). Following Rakhlin and Sridharan [START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF], the so-called "optimistic" variant of FTRL is given by the recursive formula:

Ỹ𝑖,𝑛 = 𝑌 𝑖,𝑛 + 𝛾 𝑛 𝑉 𝑖,𝑛-1 X𝑖,𝑛 = 𝑄 𝑖 ( Ỹ𝑖,𝑛 ) 𝑌 𝑖,𝑛+1 = 𝑌 𝑖,𝑛 + 𝛾 𝑛 𝑉 𝑖,𝑛 (OptFTRL)
In the above the payoff signal 𝑉 𝑖,𝑛 , which depends on the state X𝑛 , is generated as follows: at each round 𝑛 = 1, 2, . . . , every player 𝑖 ∈ N picks an action 𝛼 𝑖,𝑛 ∈ A 𝑖 based on X𝑖,𝑛 ∈ X 𝑖 and observes the pure payoff vector 𝑣 𝑖 (𝛼 𝑛 ) ≡ (𝑢 𝑖 (𝛼 𝑖 ; 𝛼 -𝑖,𝑛 )) 𝛼 𝑖 ∈A 𝑖 . At first glance, it seems difficult to reconcile the above update structure with that of (FTGL); however, it is indeed possible to integrate (OptFTRL) within (FTGL) by considering the auxiliary states 𝑋 𝑛 = 𝑄(𝑌 𝑛 ) (which are never played and are only used here for the analysis).

Indeed, each player's input signal is a special case of (4) with payoff feedback 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ), zeromean noise 𝑈 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 ( X𝑛 ) and bias 𝑏 𝑖,𝑛 = 𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ) that satisfy both the assumptions (A1),(A2). In more detail, we have:

• For (A1): ∥𝑏 𝑖,𝑛 ∥ * = ∥𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ) ∥ * = 𝑂 (𝛾 𝑛 ), which goes uniformly to 0 whenever 𝛾 𝑛 → 0.

• For (A2): ∥𝑈 𝑖,𝑛 ∥ * = ∥𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 ( X𝑛 ) ∥ * ≤ 2 max 𝛼∈A ∥𝑣 𝑖 (𝛼) ∥ * and thus the noise has bounded moments for all 𝑞 ∈ [1, ∞].

Remark 3.2. Based on the structure of the aforementioned algorithms, it is easy to check that we capture a-fortiori the model of a full-information payoff signal; for a more complete account of the different algorithms and feedback models see Table 1.

Analysis & Results

We are now in a position to state our main convergence results for (FTGL). We begin with a precise statement and discussion in Section 4.1; subsequently, we present the main proof techniques in Section 4.2.

4.1.

Statement and discussion of our main results. Our analysis will focus exclusively on strict Nash equilibria. As we discussed in the introduction, the reason for this is that only strict Nash equilibria can be asymptotically stable under FTRL [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF][START_REF] Giannou | Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information[END_REF], so they are the only reasonable candidates to consider when examining the rate of convergence of a regularized learning algorithm. 2To proceed, we will need one technical assumption linking the learning rate of (FTGL) and the bias/variance parameters of the driving feedback sequence 𝑉 𝑛 . This is as follows:

The sequence 𝛿 𝑛 𝑛 𝑘=1 𝛾

1+ 𝑞 2 𝑘 𝜎 𝑞 𝑘 𝑛 𝑘=1 𝛾 𝑘 1+𝛽𝑞/2 is summable for some 𝛽 < 1. (A3)
Assumption (A3) imposes a growth condition on the method's learning rate relative to the bias and variance parameters of the input signal sequence 𝑉 𝑛 , but it is otherwise a technical prerequisite for the analysis to come. What is more important for our purposes is that the concrete models that we discussed in the previous section satisfy it for a wide range of the player-chosen parameters 𝛾 𝑛 (and 𝜀 𝑛 in the case of bandit-based algorithms); to streamline our presentation, we postpone a more precise discussion of this issue until after the statement of our main results.

The last element that we need to introduce concerns the players' choice of regularizer: clearly, since propensities are transformed to strategies via each player's individual choice map 𝑄 𝑖 : Y 𝑖 → X 𝑖 , it stands to reason that the underlying regularization function ℎ plays a major role in the method's rate of convergence. Indeed, given an update of the form 𝑌 𝑛+1 ← 𝑌 𝑛 + 𝛾 𝑛 𝑉 𝑛 , the method's strategy variable will move forward as

𝑋 𝑛+1 ← 𝑋 𝑛 + 𝛾 𝑛 𝐽𝑄(𝑉)𝑉 𝑛 + O(𝛾 2 𝑛 )
, where 𝐽𝑄 denotes the Jacobian matrix of 𝑄. Thus, to leading order in 𝛾 𝑛 , the update 𝑋 𝑛+1 ← 𝑋 𝑛 is dominated by the first derivatives of 𝑄.

By a relatively straightforward application of the Legendre identity from convex analysis (𝑄 = (𝜕ℎ) -1 in our context; see below for a precise statement), this rate of change is related to the inverse mapping of the derivative each 𝜃 𝑖 (the kernel of the underlying regularizer). Motivated by this observation, we introduce below the algorithm's so-called rate function:

𝜙 𝑖 (𝑡) = (𝜃 ′ 𝑖 ) -1 (𝑡) if 𝑡 > 𝜃 ′ 𝑖 (0 + ), 0 otherwise. ( 7
)
The definition of the rate function 𝜙 captures the sensitivity of the choice map 𝑄 in a very precise way: If the score difference corresponding to two pure strategies 𝛼, 𝛽 ∈ A 𝑖 grows as 𝑦 𝛽 -𝑦 𝛼 = 𝑡 for some 𝑡 > 0, then the probability of playing the strategy with the lesser score must be less than the probabiity of playing the strategy with the higher score. The precise amount of this disparity of course depends on the player's choice function 𝑄 and 𝜙 acts as a "transfer" function in this regard. Specifically, as we show in detail later, we have 𝑥 𝛼 = 𝜙(-Θ(𝑡)), i.e., 𝜙 determines the rate at which 𝑥 𝛼 vanishes. For different regularizers we present the corresponding rates in Table 2. With all this in hand, our main result can be stated as follows: Theorem 1. Let 𝑥 * be a strict Nash equilibrium of Γ, and fix some confidence level 𝛿 > 0. If Assumptions (A1)-(A3) hold, there exists an unbounded open set of initial conditions W init ⊆ Y and constants 𝑑 𝑖 , 𝑐 ′ 𝑖 with 𝑐 ′ 𝑖 > 0 such that, if 𝑌 1 ∈ W init , we have: 1. 𝑋 𝑛 converges to 𝑥 * with probability at least 1 -𝛿. 2. Conditioned on the above, the rate of convergence for each player 𝑖 ∈ N is given by

∥ 𝑋 𝑖,𝑛 -𝑥 * 𝑖 ∥ 1 ≤ 2 ∑ 𝛼 𝑖 ∈A 𝑖 \supp( 𝑥 * 𝑖 ) 𝜙 𝑖 𝑑 𝑖 -𝑐 ′ 𝑖 ∑ 𝑛 𝑘=1 𝛾 𝑘 . (8)
Armed with this general result, we readily obtain the following immediate consequences thereof: More generally, we show in the supplement that the conclusion of Theorem 1 holds for all algorithms and feedback models presented in Table 1: in all cases therein, players can employ step-size policies of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1], and a mixing parameter 𝜀 𝑛 ∝ 1/𝑛 𝑟 with 𝑟 ∈ (0, 1/2) for the bandit models. The only case that does not follow as an immediate corollary of Theorem 1 is the case of constant step-sizes for Optimistic FTRL and EG/MP; however, a slightly more refined argument (that we present in the Appendix C) shows that constant step-sizes are also covered by the convergence rate guarantee (8) of Theorem 1.

Corollary 1. If the
ALGORITHM KERNEL 𝜃 (x) RATE 𝜙 (-y) Multiplicative Weight Updates 𝑥 log 𝑥 exp(-𝑦) Projection Gradient Descent 𝑥 2 /2 -𝑦 Inverse Updates -log 𝑥 -1/𝑦 q-Replicator 𝑞>0 [𝑞 (1 -𝑞) ] -1 ( 𝑥 -𝑥 𝑞 ) [𝑞 -1 + (1 -𝑞) 𝑦 ] 1/𝑞-1
4.2. Sketch of proof and main techniques. At a high level, the main idea of the proof of Theorem 1 relies on a tandem application of martingale limit theory and convex analysis in order to exploit the specific structure of (FTGL). While martingale limit theory emerges naturally to control the components of the noise, a delicate analysis of the contribution of ℎ 𝑖 in the solution of the convex constrained optimization problem, that 𝑥 = 𝑄 𝑖 (𝑦) induces, is necessary to derive the aforementioned generic rates. Below we provide a sketch of the main steps in this analysis

Step 1. Our starting point is to explore the geometric properties that are induced by the existence of a strict Nash equilibrium. Indeed, the fact that (NE) holds as a strict inequality for each pure strategy against the equilibrium's strategy, ensures convergence properties for strict Nash equilibria. More precisely, an immediate implication of (NE) is that there exist neighborhood U of 𝑥 * and constants 𝑐 1 , . . . , 𝑐 𝑁 such that

𝑣 𝑖 𝛼 * 𝑖 (𝑥) -𝑣 𝑖 𝛼 𝑖 (𝑥) ≥ 𝑐 𝑖 for all 𝑥 ∈ U and 𝛼 𝑖 ≠ 𝛼 * 𝑖 , 𝛼 𝑖 ∈ A 𝑖 , 𝑖 ∈ N (9)
In other words, in the neighborhood U the payoff of the equilibrium's strategy strictly dominates all other strategies' payoffs for each player. However, since the linchpin of (FTGL) is the interplay between X and Y, for the purpose of our analysis, we need to investigate the variational structure of U in both spaces.

Informal
W 𝑀 𝑖 = {𝑌 𝑖 : 𝑌 𝑖 𝛼 * 𝑖 -𝑌 𝑖 𝛼 𝑖 > 𝑀 𝑖 for all 𝛼 𝑖 ≠ 𝛼 * 𝑖 , 𝛼 𝑖 ∈ A 𝑖 } for 𝑀 𝑖 > 0, 𝑖 ∈ N (10)
Step 2. We now focus on one player 𝑖 ∈ N and drop the index 𝑖 altogether. First we prove that there exists an open set of initializations W init of (FTGL), for which with arbitrary high probability the dual variable (𝑌 𝑘 ) 𝑘 ∈ℕ never exits W 𝑀 and thus its image remains in the desired neighborhood U. We start by writing the score differences between each pure strategy 𝛼 ∈ A and 𝛼 * ∈ supp(𝑥 * )

𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 = 𝑌 𝛼,1 -𝑌 𝛼 * ,1 + 𝑛 ∑ 𝑘=1 𝛾 𝑘 (drift 𝑘 + noise 𝑘 + bias 𝑘 ) (11)
where By substituting the inequality for 𝑀 init in [START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF] we get 𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 ≤ -𝑀 -𝑐 ′ 𝑛 𝑘=1 𝛾 𝑘 and convergence occurs as an immediate consequence; Indeed 𝑋 𝛼 * ,𝑛 → 1, since whenever 𝑌 𝛼 -𝑌 𝛼 * → -∞, it holds that each 𝛼 ∈ A \ supp(𝑥 * ) becomes extinct i.e., 𝑋 𝛼 → 0.

drift 𝑘 = 𝑣 𝛼 (𝑋 𝑘 ) -𝑣 𝛼 * (𝑋 𝑘 ), noise 𝑘 = 𝑈 𝛼,𝑘 -𝑈 𝛼 * ,
Step 3. We now proceed to the delineation of the rates of convergence. Using the KKT conditions (Lemma B.1) combined with Eq. ( 11),Eq. ( 9) and the fact that 𝑌 1 ∈ W init we have

𝜃 ′ (𝑋 𝛼,𝑛+1 ) -𝜃 ′ (𝑋 𝛼 * ,𝑛+1 ) = 𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 ≤ -𝑀 init -𝑐 𝑛 ∑ 𝑘=1 𝛾 𝑘 + 𝑛 ∑ 𝑘=1 𝛾 𝑘 (noise 𝑘 + bias 𝑘 )
Recall that 𝜃 is strong convex, or equivalently 𝜃 ′ is strictly increasing; by rearranging and substituting to the above inequality we get

𝜃 ′ (𝑋 𝛼,𝑛+1 ) ≤ 𝜃 ′ (𝑋 𝛼 * ,𝑛+1 ) -𝑀 -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 ≤ 𝑑 -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 ( 12
)
where 𝑑 = -𝑀 + 𝜃 ′ (1) and 𝛼 ∈ A, 𝛼 ≠ 𝛼 * . By aggregating over all

𝛼 ∈ A, 𝛼 ≠ 𝛼 * ∥𝑥 * -𝑋 𝑛+1 ∥ 1 = 2(1 -𝑋 𝛼 * ,𝑛+1 ) ≤ 2 ∑ 𝛼∈A≠𝛼 * 𝜙(𝑑 -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 ) (13)
which indicates the rate of convergence and completes our proof.

Numerical experiments

In this section we perform a series of numerical experiments to validate our theoretical findings. Specifically we are interested in verifying both the correctness in the computation of the rates via 𝜙 𝑖 for different regularizers and at the same time the fact that convergence speed is invariant to different feedback models and algorithmic variants of (FTGL).

To do this, we start by examining variations of (FTGL) in the archetypal game of Battle of the Sexes, a popular two-player benchmark of the coordination games, which however involves elements of conflict as well. This game exhibits two strict Nash equilibria and one mixed equilibrium (for the exact definition, see Appendix E). We then seek to experimentally study the performance of (FTGL) while the number of the players scales up. To do this we use the atomic version of classical Pigou's congestion game [START_REF] Cecil | The Economics of Welfare[END_REF], where 𝑁 units of traffic (e.g., rush-hour drivers) leave from 𝑂 (origin) to 𝐷 (destination) at the same time and each driver has the same dominant pure strategy/path for this trip. Accordingly to Table 2 the decay rate for the entropic regularization is exponential while for the case of euclidean is linear, which indeed yield linear and constant-time convergence as Fig. 16 illustrates.

We defer a detailed exposition of various configurations with different step-sizes, alternative discretization methods like MirrorProx and ExtraGradient and feedback models with the presence (or not) of extra heavy-tailed/uniform/gaussian noise again to the paper's supplement.

A Martingale limit theory

Our analysis leverages tools from martingale limit theory. Below we present the two main theorems that we utilize in the main body of our proofs.

• (Doob's inequality), also known as Kolmogorov's submartingale inequality gives a bound on the probability that a stochastic process exceeds any given value over a given interval of time. • (Burkholder's inequality), also known the Burkholder-Davis-Gundy inequality is a remarkable result relating the maximum of a local martingale with its quadratic variation.

Theorem A.1 (Doob's inequality). Let 𝑆 𝑛 be a martingale with respect to the filtration F 𝑛 , then for each 𝜀 > 0 and 𝑞 ≥ 1,

ℙ( sup 1≤𝑘 ≤𝑛 |𝑆 𝑘 | ≥ 𝜀) ≤ 𝔼 |𝑆 𝑛 | 𝑞 𝜀 𝑞 (Doob's inequality)
Theorem A.2 (Burkholder's inequality). Let 𝑆 𝑛 be a martingale with respect to the filtration F 𝑛 and 𝑋 𝑛 = 𝑆 𝑛 -𝑆 𝑛-1 . Then for all 1 < 𝑞 < ∞, there exists constant 𝐶 𝑞 depending only on 𝑞 such that

𝔼 |𝑆 𝑛 | 𝑞 ≤ 𝐶 𝑞 𝔼 𝑛 ∑ 𝑘=1 𝑋 2 𝑘 𝑞/2 (Burkholder's inequality)
Proofs for these two theorems can be found in [? ].

B A dichotomy between the regularizers

Our main result (Theorem 1) provides a mechanism to compute the convergence rate to a strict Nash Equilibrium universally for all smooth convex regularizers ℎ 𝑖 (𝑥) = 𝛼 𝑖 ∈A 𝑖 𝜃 𝑖 (𝑥 𝛼 𝑖 ). An important implication of our main theorem (Corollary 1) is that for the case of non-steep kernels (i.e., 𝜃 𝑖 is differentiable at 0), 𝑋 𝑛 converges to 𝑥 * in a finite number of iterations. Below we give some intuition for the interested reader about the differences between the steep and non-steep case.

Steep vs non-steep. In this section we elaborate in detail the dichotomy among the different regularizers mentioned in Sections 3.1 and 4. As we established in Section 3.1, different players may apply different regularizers ℎ 𝑖 in their choice maps 𝑄 𝑖 (𝑦 𝑖 ). Depending on the regularizer chosen, the behavior of (FTGL) could vary significantly. To investigate more this diversity, we start by describing formally the strategy-choice step 𝑥 𝑖 = 𝑄 𝑖 (𝑦 𝑖 ) as a convex constrainted minimization problem.

𝑄 𝑖 (𝑦 𝑖 ) =arg min

𝑥 𝑖 ∈X 𝑖 {ℎ 𝑖 (𝑥 𝑖 ) -⟨𝑥 𝑖 , 𝑦 𝑖 ⟩} . (B.1)
Following also the folklore convention from convex analysis, we express ℎ as an extended-real valued function ℎ : V → ℝ ∪ {∞} with value ∞ outside of the simplex X . Additionally, the subdifferential of ℎ at 𝑥 ∈ V is defined as:

𝜕ℎ(𝑥) = {𝑦 ∈ V * : ℎ(𝑥 ′ ) ≥ ℎ(𝑥) + ⟨𝑦, 𝑥 ′ -𝑥⟩ ∀𝑥 ′ ∈ V } (B.2)
If 𝜕ℎ(𝑥) is nonempty, then ℎ is called subdifferentiable at 𝑥 ∈ X . When 𝑥 ∈ ri(X ) then 𝜕ℎ(𝑥) is always non-empty or more compactly ri(X ) ⊆ dom 𝜕ℎ ≡ {𝑥 ∈ X : 𝜕ℎ(𝑥) ≠ ∅} ⊆ dom ℎ ⊆ X . Notice that when the gradient of ℎ exists, then its subgradient always contains it. Leveraging the property that local and global minima coincides in the case of convex function, Fermat's rule provides a simple characterization of the minimizers of a function as the zeros of its subdifferential:

Fact (Fermat's Rule). For a proper convex function 𝑓 , argmin 𝑓 ≡ zer𝜕 𝑓 = {𝑥 ∈ X | 0 ∈ 𝜕 𝑓 (𝑥)}
With these in mind, we present a typical separation between the different regularizers" focusing on the more simple case of decomposable ones ℎ(𝑥) = 𝛼∈A 𝜃 𝛼 (𝑥). On the one hand, steep regularizers have differentiable kernels on (0, 1] and become infinitely steep as 𝑥 approaches the boundary or infeasible not only as initial conditions but also as part of the sequence of play, while non-steep ones allow completely the sequence of play to transfer between the different faces of the simplex. The qualititative difference in behavior between these cases is illustrated in Fig. 2 (which shows the very different behavior of the derivates of ℎ near the boundary of the state space).

𝜃 ′ (0) = -∞.
𝜃 ′ 𝑖 (𝑥 𝑖 )         steep ℎ 1 (𝑥) = ∑ 𝛼∈A 𝜃 𝑖 (𝑥 𝛼 ) = ∑ 𝛼∈A 𝑥 𝛼 log(𝑥 𝛼 ) non-steep ℎ 2 (𝑥) = ∑ 𝛼∈A 𝜃 𝑖 (𝑥 𝛼 ) = ∑ 𝛼∈A 1 2 𝑥 2 𝛼        
Having discussed the connection between the choice map and the properties of the regularizer, the following lemma quantifies the gulf between the steep and non-steep case and provides the relation between mixed strategies and score vectors and the mirror map (3) that defines the dynamics (FTGL).

More precisely, we focus on the perspective of an arbitrary player, say 𝑖, and for ease of notation we write 𝑄, 𝑥 and 𝑦 instead of 𝑄 𝑖 , 𝑥 𝑖 and 𝑦 𝑖 respectively.

Lemma B.1. 𝑥 = 𝑄(𝑦) if and only if there exist 𝜇 ∈ ℝ and 𝜈 𝛼 ∈ ℝ + such that, for all 𝛼 ∈ A, we have: a) 𝑦 𝛼 = 𝜕ℎ 𝜕𝑥 𝛼 + 𝜇 -𝜈 𝛼 ; and b) 𝑥 𝛼 𝜈 𝛼 = 0 In particular, if ℎ is steep, we have 𝜈 𝛼 = 0 for all 𝛼 ∈ A.

Proof. Recall that

𝑄(𝑦) = arg max 𝑥 ∈K {⟨𝑦|𝑥⟩ -ℎ(𝑥)} = arg max ∑ 𝛼∈A 𝑦 𝛼 𝑥 𝛼 -ℎ(𝑥) : ∑ 𝛼∈A 𝑥 𝛼 = 1 and ∀𝛼 ∈ A : 𝑥 𝛼 ≥ 0
The result follows by applying the Karash-Kuhn Tucker (KKT) conditions to this optimization problem and noting that, since the constraints are affine, the KKT conditions are sufficient for optimality. Our Langragian is

L(𝑥, 𝜇, 𝜈) = ( ∑ 𝛼∈A 𝑦 𝛼 𝑥 𝛼 -ℎ(𝑥)) -𝜇( ∑ 𝛼∈A 𝑥 𝛼 -1) + ∑ 𝛼∈A 𝜈 𝛼 𝑥 𝛼
where the set of constraints (i) of the statement of the lemma are the stationarity constraints, which in our case are ∇L(𝑥, 𝜇, 𝜈) = 0 ⇔ ∇( 𝛼∈A 𝑦 𝛼 𝑥 𝛼ℎ(𝑥)) = 𝜇∇( 𝛼∈A 𝑥 𝛼 -1) -𝛼∈A 𝜈 𝛼 ∇𝑥 𝛼 , while the set of constraints (ii) of the statement of the lemmas are the complementary slackness constraints. Note that complementary slackness implies that whenever 𝜈 𝛼 > 0 whenever 𝛼 ∉ supp(𝑥). Finally, if ℎ is steep, we have |𝜕 𝛼 ℎ(𝑥)| → ∞ as 𝑥 → bd(X ), which implies that the KKT conditions admit a solution with 𝜈 𝛼 = 0. ■

C Proof of Main Theorem

Our lemma shows a property of strict Nash equilibria. More precisely, we prove the existence of a neighborhood U in which each player's payoff corresponding to the strategy of the equilibrium outweighs the payoff of any other pure strategy.

Lemma C.

∥ 𝑋 𝑖,𝑛 -𝑥 * 𝑖 ∥ 1 ≤ 2 ∑ 𝛼 𝑖 ∈A 𝑖 \supp( 𝑥 * 𝑖 ) 𝜙 𝑖 𝑑 𝑖 -𝑐 ′ 𝑖 ∑ 𝑛 𝑘=1 𝛾 𝑘 . ( 8
)
Remark C.3. The probability guarantee is over only the potential randomness that the payoff oracle. i.e., when players have access to a perfect payoff oracle; the results hold with probability 1.

Proof. Fix a confidence level 𝛿 and the parameters of the algorithm respecting (A1)-(A3). We will prove that there exists a "score-dominant" open set of initial conditions W init W init ≡ {𝑌 : 𝑀 init < 𝑌 𝛼 * -𝑌 𝛼 for all 𝛼 ≠ 𝛼 * , 𝛼 ∈ A} ⊆ Y for some 𝑀 init > 0 such that whenever 𝑌 1 ∈ W init then with probability at least 1 -𝛿 the sequence of play generated by (FTGL) converges to 𝑥 * with rate given by the function

𝜙 𝑖 𝜙 𝑖 (𝑡) = (𝜃 ′ 𝑖 ) -1 (𝑡) if 𝑡 > 𝜃 ′ 𝑖 (0 + ), 0 otherwise. (C.8)
which depends on the choice of the kernel 𝜃 𝑖 of each player and the payoff matrix of the game.

For convenience of notation we focus on an arbitrary player in the proof, without loss of generality let it be the 𝑖-th one, and we completely drop the index 𝑖. Since the equilibrium is strict by Lemmas C. We will prove by strong induction that 𝑌 𝑛 ∈ W (𝑀 strict ), for all 𝑛 ≥ 1.

• For the base of the induction, we have that 𝑌 1 ∈ W (𝑀 init ) and by the choice of 𝑀 strict , trivially we get that 𝑌 1 ∈ W (𝑀 strict ). • For the inductive step, let us assume that 𝑌 𝑘 ∈ W (𝑀 strict ) for all 𝑘 = 1, 2, . . . , 𝑛, we will show below that 𝑌 𝑛+1 ∈ W (𝑀 strict ).

Combining (C.12),(C.13),(C. [START_REF] Hart | Uncoupled dynamics do not lead to Nash equilibrium[END_REF]) for the terms 𝑛 𝑘=1 𝛾 𝑘 drift 𝑘 , 𝑛 𝑘=1 𝛾 𝑘 noise 𝑘 , 𝑛 𝑘=1 𝛾 𝑘 bias 𝑘 the claim's assumption 𝑌 1 ∈ W (𝑀 strict ) and the choice of 𝑀 init , (C.11) can be bounded as

𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 = 𝑌 𝛼,1 -𝑌 𝛼 * ,1 + 𝑛 ∑ 𝑘=1 𝛾 𝑘 (drift 𝑘 + noise 𝑘 + bias 𝑘 ) (C.20) 𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 ≤ 𝑌 𝛼,1 -𝑌 𝛼 * ,1 -𝑐 strict 𝑛 ∑ 𝑘=1 𝛾 𝑘 + 𝜉 𝑛 + 2 𝑛 ∑ 𝑘=1 𝛾 𝑘 ∥𝑏 𝑘 ∥ * (C.21) 𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 ≤ -𝑀 init -(𝑐 strict -𝑐 ′ ) 𝑛 ∑ 𝑘=1 𝛾 𝑘 + 𝜉 𝑛 + 2 𝑛 ∑ 𝑘=1 𝛾 𝑘 ∥𝑏 𝑘 ∥ * -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 (C.22) 𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 ≤ -𝑀 strict -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 ≤ -𝑀 strict (C.23)
and thus 𝑌 𝑛+1 ∈ W (𝑀 strict ). ■ above claim immediately implies that 𝑋 𝑛 ∈ U for all 𝑛 = 1, 2, . . .. We will now prove that the sequence of play converges to 𝑥 * . Proof of Convergence. Let's assume that ad absordum that there exists at least one strategy 𝛼 ≠ 𝛼 * , 𝛼 ∈ A such that lim sup 𝑛→∞ 𝑋 𝛼,𝑛 ≥ 𝜀 > 0. for all sufficiently large 𝑛. Recall also that for 𝑋 ∈ U strict , it holds that 𝑋 𝛼 * > 0 by construction in Lemma C.2. Then by Lemma B.1 we have 𝑌 𝛼 = 𝜃 ′ (𝑋 𝛼 ) + 𝜇 -𝑣 𝛼 (C.24) where 𝜇 ∈ ℝ and 𝑣 𝛼 ≥ 0 while 𝑣 𝛼 = 0 whenever 𝑋 𝛼 > 0. Leveraging that i) the sequence of play is contained in U, ii) by descending to a subsequence if necessary 𝑋 𝛼,𝑚 𝑖 > 0 and iii) recall (C.23) for the subsequence we have

𝑌 𝛼,𝑚 𝑖+1 -𝑌 𝛼 * ,𝑚 𝑖+1 = 𝜃 ′ (𝑋 𝛼,𝑚 𝑖+1 ) -𝜃 ′ (𝑋 𝛼 * ,𝑚 𝑖+1 ) ≤ -𝑀 strict -𝑐 ′ 𝑚 𝑖 ∑ 𝑘=1 𝛾 𝑘 (C.25)
However, the RHS of the above inequality goes to -∞ as 𝑚 𝑖 → ∞, while the LHS of the above inequality is bounded by the constant 𝜃 ′ (𝜀) -𝜃 ′ (1) since 𝜃 ′ is strictly increasing, which is a contradiction 6 . ■ Proof of Rate. We now proceed to the delineation of the exact rates achieved. Consider the function

𝜙(𝑡) = (𝜃 ′ ) -1 (𝑡) if 𝑡 > 𝜃 ′ (0 + ), 0 otherwise. (C.26)
where (𝜃 ′ ) -1 (𝑧) is the inverse function of the kernel 𝜃 ′7 . Focusing on (C.25) we can derive that

𝜃 ′ (𝑋 𝛼,𝑛+1 ) ≤ -𝑀 strict + 𝜃 ′ (𝑋 𝛼 * ,𝑛+1 ) -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 (C.27) ≤ -𝑀 strict + 𝜃 ′ (1) -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 (C.28)
for all 𝛼 ∈ A 𝑖 and 𝑛 = 1, 2, . . .. As a result

𝑋 𝛼,𝑛+1 ≤ 𝜙(-𝑀 strict + 𝜃 ′ (1) -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 ) (C.29)
Aggregating over all strategies 𝛼 ∈ A, 𝛼 ≠ 𝛼 * we have

∥𝑥 * -𝑋 𝑛+1 ∥ 1 = 2(1 -𝑋 𝛼 * ,𝑛+1 ) (C.30) ≤ ∑ 𝛼∈A≠𝛼 * 𝜙(-𝑀 strict + 𝜃 ′ (1) -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 ) (C.31) ≤ ∑ 𝛼∈A≠𝛼 * 𝜙(𝑑 -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 ) (C.32)
where 𝑑 = -𝑀 strict + 𝜃 ′ (1). ■ ■ Corollary 1. If the regularizer employed non-steep (i.e., 𝜃 𝑖 is differentiable at 0), 𝑋 𝑛 converges to 𝑥 * in a finite number of iterations.

Proof. Additionally, in the case of non-steep regularizers we can prove that convergence occurs in finite time. More precisely, focusing on (C.28) and bearing in mind that 𝑋 𝛼,𝑛+1 ≥ 0 for all 𝑛 = 1, 2, . . . we have

𝜃 ′ (0) ≤ 𝜃 ′ (𝑋 𝛼,𝑛+1 ) ≤ -𝑀 strict + 𝜃 ′ (1) -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 (C.33)
At the same time for finite 𝑛 it holds

𝑛 ∑ 𝑘=1 𝛾 𝑘 ≥ (-𝑀 strict + 𝜃 ′ (1) -𝜃 ′ (0))/𝑐 ′ (C.34)
since 𝜃 ′ (0) is finite for non-steep regularizers. Rearranging the above inequality we have

-𝑀 strict + 𝜃 ′ (1) -𝑐 ′ 𝑛 ∑ 𝑘=1 𝛾 𝑘 ≤ 𝜃 ′ (0) (C.35)
which inevitably implies that 𝑋 𝛼,𝑛+1 = 0. ■

D Models

We start by presenting the well-known algorithms Follow the Regularized Leader (FTRL), Optimistic Follow the Regularized Leader (OptFTRL) and Mirror Prox (MP), as special cases of our general algorithmic framework.

𝑌 𝑖,𝑛+1 = 𝑌 𝑖,𝑛 + 𝛾 𝑛 𝑉 𝑖,𝑛 𝑋 𝑖,𝑛 = 𝑄 𝑖 (𝑌 𝑖,𝑛 )

(FTRL) Ỹ𝑖,𝑛 = 𝑌 𝑖,𝑛 + 𝛾 𝑛 𝑉 𝑖,𝑛-1 X𝑖,𝑛 = 𝑄 𝑖 ( Ỹ𝑖,𝑛 ) 𝑌 𝑖,𝑛+1 = 𝑌 𝑖,𝑛 + 𝛾 𝑛 𝑉 𝑖,𝑛 (OptFTRL)
Remark D.1. (OptFTRL) requires two initializations and then at each stage the previous payoff signal is stored and is utilized to calculate the auxiliary cumulative payoff Ỹ𝑖,𝑛 .

𝑌 𝑖,𝑛+1/2 = 𝑌 𝑖,𝑛 + 𝛾 𝑛 𝑉 𝑖,𝑛 𝑌 𝑖,𝑛+1 = 𝑌 𝑖,𝑛 + 𝛾 𝑛 𝑉 𝑖,𝑛+1/2 𝑋 𝑖,𝑛+1/2 = 𝑄 𝑖 (𝑌 𝑖,𝑛+1/2 ) 𝑋 𝑖,𝑛+1 = 𝑄 𝑖 (𝑌 𝑖,𝑛+1 ) (MirrorProx)
Remark D.2. (MirrorProx) requires only one initialization, but at each stage the algorithm generates two different states and correspondingly two payoff signals are needed.

For both the algorithms (OptFTRL),(MirrorProx) we can prove that for the cases of full information, oracle based feedback and noisy payoff feedback, the implicit bias for modeling their intermediate steps is ∥𝑏 𝑖,𝑛 ∥ * = O(𝛾 𝑛 ). The bias is the same in all of the three cases and thus we only present the case of full information.

Proof. Full information:

• (OptFTRL): 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝑋 𝑛 ) + (𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 )). Thus ∥𝑏 𝑖,𝑛 ∥ * = ∥𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ) ∥ * ≤ 𝐶 ∥ X𝑛 -𝑋 𝑛 ∥ (D.1) = 𝐶 ∥𝑄 𝑖 ( Ỹ𝑛 ) -𝑄 𝑖 (𝑌 𝑛 ) ∥ ≤ 𝐶 ′ ∥ Ỹ𝑛 -𝑌 𝑛 ∥ * (D.2) = O(𝛾 𝑛 ) (D.3) (MirrorProx): 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝑋 𝑛 ) + (𝑣 𝑖 (𝑋 𝑛+1/2 ) -𝑣 𝑖 (𝑋 𝑛 )).
The proof is similar to the above and ∥𝑏 𝑖,𝑛 ∥ * = O(𝛾 𝑛 ).

■

Below, we explain how the proof of Theorem 1 can be oriented to the specific structure of both (OptFTRL) and (MirrorProx), in order to achieve all the permitted step-sizes. We will not make an exact proof but we will thoroughly describe how the proof of Theorem 1 should be altered for the case of full information; the reader can follow similar steps for the case of oracle based feedback.

• Optimistic Follow the Regularized Leader (OptFTRL) has an extra auxiliary cumulative payoff Ỹ𝑛 . We will first prove that if the two initializations of (OptFTRL) are appropriate then Theorem 1 holds without introducing any bias term.

Step 1: Notice that for the score differences of the auxiliary cumulative payoffs we have

Ỹ𝛼,𝑛+1 -Ỹ𝛼 * ,𝑛+1 = 𝑌 𝛼,𝑛 -𝑌 𝛼 * ,𝑛 + 𝛾 𝑛 𝑣 𝛼 ( X𝑛-1 ) -𝑣 𝛼 * ( X𝑛-1 ) (D.4)
By substituting all the 𝑌 𝑛 terms we have

Ỹ𝛼,𝑛+1 -Ỹ𝛼 * ,𝑛+1 = 𝑌 𝛼,1 -𝑌 𝛼 * ,1 + 𝑛-1 ∑ 𝑘=1 𝛾 𝑘 𝑣 𝛼 ( X𝑘 ) -𝑣 𝛼 * ( X𝑘 ) + 𝛾 𝑛 𝑣 𝛼 ( X𝑛-1 ) -𝑣 𝛼 * ( X𝑛-1 ) (D.5)
Step 2: Assume that Ỹ𝑘 ∈ W 𝑀 as described in Theorem 1 and thus X𝑘 ∈ U for all 𝑘 = 1, . . . , 𝑛. We will prove by induction that Ỹ𝑛+1 ∈ W 𝑀 . Notice that since X𝑘 ∈ U it holds that 𝑣 𝛼 ( X𝑘 ) -𝑣 𝛼 * ( X𝑘 ) ≤ -𝑐 for all 𝑘 = 1, . . . , 𝑛 (D.6) Step 3: From Eq. (D.5) we have

Ỹ𝛼,𝑛+1 -Ỹ𝛼 * ,𝑛+1 ≤ 𝑌 𝛼,1 -𝑌 𝛼 * ,1 -𝑐 𝑛 ∑ 𝑘=1 𝛾 𝑘 (D.7)
By choosing 𝑀 init > 𝑀 our claim follows. We stress here that we have implicitly assumed that for the second initialization of (OptFTRL) it holds Ỹ1 ∈ W.

Step 4: The rest of the proof holds as the one in Theorem 1, as all of the states X𝑛 remain in the desired neighborhood U in which the variational inequality holds.

• Mirror Prox

This algorithm, as we have already mentioned, calculates two different cumulative payoffs and primal states at each round.

Step 1:We will first prove by induction that that the cumulatve payoffs 𝑌 𝑛+1/2 ∈ W 𝑀 for all 𝑛 = 1, 2, . . .. Assume that 𝑌 𝑘+1/2 ∈ W 𝑀 and thus 𝑋 𝑘+1/2 ∈ U for all 𝑘 = 1, . . . , 𝑛 then for the score differences we have

𝑌 𝛼,𝑛+1/2 -𝑌 𝛼 * ,𝑛+1/2 = 𝑌 𝛼,𝑛 -𝑌 𝛼 * ,𝑛 + 𝛾 𝑛 (𝑣 𝛼 (𝑋 𝑛 ) -𝑣 𝛼 * (𝑋 𝑛 )) (D.8) = 𝑌 𝛼,1 -𝑌 𝛼 * ,1 + 𝑛-1 ∑ 𝑘=1 𝛾 𝑘 𝑣 𝛼 (𝑋 𝑘-1/2 ) -𝑣 𝛼 * (𝑋 𝑘-1/2 ) (D.9) + 𝛾 𝑛 (𝑣 𝛼 (𝑋 𝑛 ) -𝑣 𝛼 * (𝑋 𝑛 )) (D.10) ≤ 𝑌 𝛼,1 -𝑌 𝛼 * ,1 -𝑐 𝑛-1 ∑ 𝑘=1 𝛾 𝑘 + 𝛾 𝑛 max 𝛼∈A ∥𝑣(𝛼) ∥ * (D.11)
Step 2: Choose 𝑀 init > 𝑀 + 𝛾 𝑛 max 𝛼∈A {∥𝑣(𝛼) ∥ * } which is feasible for step-size of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1] and our claim follows.

Step 3: Continue with the proof as presented in Theorem 1.

Proposition D.1. In the bandit case, X𝑛 be the state such that X𝑖,𝑛 is the mixed strategy of the 𝑖 𝑡 ℎ player at round 𝑛 i.e., X𝑖,𝑛 = (1 -𝜀 𝑛 ) X𝑖,𝑛 + 𝜀 𝑛 /|A 𝑖 |, based on which the pure strategy 𝛼 𝑖,𝑛 is selected. Then the following properties hold

1. 𝔼[𝑈 𝑖,𝑛 | F 𝑛 ] = 0. 2. ∥𝑈 𝑖,𝑛 ∥ * = O(1/𝜀 𝑛 ). 3. ∥𝑏 𝑖,𝑛 ∥ * = O(𝜀 𝑛 ).
Remark D.3. In the case of (MirrorProx) X𝑖,𝑛 is the state 𝑋 𝑖,𝑛-1/2 .

Proof

≤ 𝐶 ′ 𝑞 𝑛 (1-𝑝) (-1-𝛽𝑞 2 ) 𝑛 1-𝑝 (1+ 𝑞 2 )+𝑟 𝑞 (D.28) ≤ 𝐶 ′ 𝑞 𝑛 -1-𝛽𝑞 2 + 𝑝+ 𝑝𝛽𝑞 2 +1-𝑝-𝑝𝑞 2 +𝑟 𝑞 (D.29) ≤ 𝐶 ′ 𝑞 𝑛 -𝛽𝑞 2 + 𝑝𝛽𝑞 2 -𝑝𝑞 2 +𝑟 𝑞 (D.30)
Thus 𝛿 𝑛 is summable if the exponent of 𝑛 is less than -1:

- 𝛽𝑞 2 + 𝑝𝛽𝑞 2 - 𝑝𝑞 2 + 𝑟𝑞 < -1 (D.31) 2 𝑞 -𝑝 + 2𝑟 < 𝛽(1 -𝑝) (D.32)
The second expression of the proposition can be derived if we only keep the variable 𝑎 in the RHS of the above inequality

2 𝑞 -𝑝 + 2𝑟 < 𝛽(1 -𝑝) (D.33) ( 2
𝑞 -𝑝 + 2𝑟)/(1 -𝑝) < 𝛽 < 1 (D.34) 2 𝑞 -𝑝 + 2𝑟 < 1 -𝑝 (D.

E Experiments

We start this section by explaining in detail the two main games that our experiments are conducted.

E.1. Games.

1. In the archetypal game of Battle of the Sexes, a couple argues over which music to listen over the weekend. Both know that they want to spend the weekend together, but they cannot agree over what to do. The partner (A) prefers to audit a Rock band concert, whereas the partner (B) prefers a Pop music show. This is a classical example of a coordination game, analysed in game theory for its applications in many fields, such as business management or military operations. For the interested reader, check [? ]. Since the couple wants to spend time together, if they go separate ways, they will receive no utility (set of payoffs will be 0, 0). If they go either to a Rock or a Pop musical, both will receive some utility from the fact that they're together, but one of them will actually enjoy the activity. The description of this game in strategic form is therefore as follows:

Figure 1 :

 1 Figure1: For the Battle of the Sexes experiment, we initialize uniformly randomly our executions from𝑌 𝑖𝑛𝑖𝑡 ∈ [-1, 1] × [-1, 1]and examine the instantiations of Model 1-3 using constant-step size and exploration rate 𝜀 𝑛 ∝ 1/3 √ 𝑛. For the Pigou's game, our setup includes two alternative disjoint paths for 𝑁 = 1000 drivers. The first path has linear latency ℓ 1 (𝑥) = 𝑥/𝑁 while the second one has constant unit congestion, ℓ 2 (𝑥) = 1, where 𝑥 denotes the population of the drivers that uses the corresponding path.

Figure 2 :

 2 Figure 2: Steep vs. non-steep regularizers (note in particular the singular behavior of the gradient at the boundary in the case of steep regularizers).

Figure 3 :

 3 Figure 3: Equilibrium Structure: This game has two strict Nash equilibria, one where both go to the Rock concert, and another where both go to the Pop concert.There is also a mixed Nash equilibrium, where the players go to their preferred event more often than the other. For the described payoffs, each player attends their preferred event with probability 3/5.

2 .

 2 In the selfish routing game of Pigou's Congestion Network, we consider the simple network shown in Fig.4. Two disjoint edges/paths connect a source vertex 𝑂 to a destination vertex 𝐷. Each edge is labeled with a cost function, which describes the cost (e.g., travel time) incurred by users of the edge, as a function of the amount of traffic routed on the edge. In the atomic version of the game the population of the drivers that uses a specific edge is an integer 𝑥 ∈ {0, • • • , 𝑁 }. The upper edge has the constant latency function ℓ 1 (𝑥) = 1, and thus it represents a route that is relatively long but immune to congestion. In the linear latency setting, the cost of the lower edge, which is governed by the function ℓ 2 (𝑥) = 𝑥/𝑁, increases as the edge gets more congested. In particular, the lower edge is cheaper than the upper edge if and only if less than 𝑁 drivers uses it.

Figure 11 :100

 11 Figure 11: OptFTRL: oracle-based, bandit; 𝛾 𝑛 ∝ 1/𝑛 1/2

Figure 12 :

 12 Figure 12: OptFTRL: uniform, gaussian; 𝛾 𝑛 ∝ 1/𝑛 1/2

Figure 13 :

 13 Figure 13: MP: oracle-based, bandit;𝛾 𝑛 = 0.05

Figure 14 :

 14 Figure 14: MP: uniform, gaussian; 𝛾 𝑛 = 0.05

Figure 15 :100

 15 Figure 15: mirror-prox (MP): oracle-based, bandit; 𝛾 𝑛 ∝ 1/𝑛 1/2

Figure 16 :

 16 Figure 16: MP: uniform, gaussian; 𝛾 ∝ 1/𝑛 1/2

  𝑢 𝑖 (𝑥 𝑖 ; 𝑥 * -𝑖 ) for all 𝑥 𝑖 ∈ X 𝑖 and all 𝑖 ∈ N .(NE)The set of pure strategies supported at the equilibrium component 𝑥 * 𝑖 ∈ X 𝑖 of each player will be denoted by supp(𝑥 * 𝑖 ) = {𝛼 𝑖 ∈ A 𝑖 : 𝑥 * 𝑖 𝛼 𝑖 > 0}. In turn, the size of the support of 𝑥 * leads to the following dichotomy: 𝑥 * is called pure if supp(𝑥 * 𝑖 ) ≡ 𝑖 ∈𝑁 supp(𝑥 * 𝑖 ) is a singleton and mixed otherwise.

Nash equilibrium. The most widely used solution concept in game theory is that of a Nash equilibrium i.e., a (possibly) mixed strategy profile 𝑥 * ∈ X that discourages unilateral deviations; formally, 𝑥 * ∈ X is said to be a Nash equilibrium of Γ if 𝑢 𝑖 (𝑥 * ) ≥

  regularizer employed is non-steep (i.e., 𝜃 𝑖 is differentiable at 0), 𝑋 𝑛 converges to 𝑥 * in a finite number of iterations. Corollary 2. Suppose that FTRL is run with oracle-based feedback as per Model 1 and a learning rate of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. Then the conclusion of Theorem 1 holds. Corollary 3. Suppose that FTRL is run with bandit feedback as per Model 2, a learning rate of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1] and a mixing parameter 𝜀 𝑛 ∝ 1/𝑛 𝑟 , 𝑟 ∈ (0, 1/2). Then the conclusion of Theorem 1 holds.

Corollary 4

. Suppose that Optimistic FTRL is run with oracle-based feedback as per Model 3 and a learning rate of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ (0, 1]. Then the conclusion of Theorem 1 holds.

Table 2 :

 2 Regularizers & correspinding rates.

  𝑘 , bias 𝑘 = 𝑏 𝛼,𝑘 -𝑏 𝛼 * ,𝑘 . We will prove by induction our forward-invariant statement; let 𝑌 𝑘 ∈ W 𝑀 and thus 𝑋 𝑘 ∈ U for all 𝑘 = 1, . . . , 𝑛 then • By[START_REF] Daskalakis | Last-iterate convergence: Zero-sum games and constrained min-max optimization[END_REF] we have 𝑛 𝑘=1 𝛾 𝑘 drift 𝑘 ≤ -𝑐 𝑛 𝑘=1 𝛾 𝑘 for all 𝑘 = 1, . . . , 𝑛. • By the triangle inequality and (A1), the term 𝑛 𝑘=1 𝛾 𝑘 bias 𝑘 is dominated by the term 𝑛 𝑘=1 𝛾 𝑘 drift 𝑘 for all 𝑛 = 1, 2, . . .. • Subsequently, by leveraging the machinery of martingale's maximal inequalities and assumption (A2), which we present in Appendix A and using learning rates that respect (A3), we prove that with probability at least 1 -𝛿, for any fixed confidence level 𝛿, 𝑛 𝑘=1 𝛾 𝑘 noise 𝑘 , which is a martingale, is also dominated by the term 𝑛 𝑘=1 𝛾 𝑘 drift 𝑘 for all 𝑛 = 1, 2, . . . • We now define the open set of initial conditions W init , which is of the form described in[START_REF] Daskalakis | Training GANs with optimism[END_REF], with constant 𝑀 init . By choosing4 𝑀 init ≥ 𝑀 + 𝑛 𝑘=1 𝛾 𝑘 (noise 𝑘 + bias 𝑘 ) -(𝑐 -𝑐 ′ ) 𝑛 𝑘=1 𝛾 𝑘 , for any 𝑐 ′ < 𝑐 and any 𝑛 ≥ 1, since 𝑌 1 ∈ W init we have that 𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 ≤ -𝑀 for all 𝑛 ≥ 1.

	10 0				Battle of the Sexes-x * -Xk 1				10 0			Pigou's Network-x * -Xk 1
								FTRL-MWU-oracle							FTRL-MWU-oracle
	10 -2							FTRL-MWU-bandit FTRL-2-oracle FTRL-2-bandit OptFTRL-MWU-oracle	10 -2					FTRL-MWU-bandit FTRL-2-oracle FTRL-2-bandit
	10 -4							OptFTRL-MWU-bandit OptFTRL-2-oracle	10 -4					OptFTRL-MWU-oracle OptFTRL-MWU-bandit
								OptFTRL-2-bandit							OptFTRL-2-oracle
	10 -6										10 -6					OptFTRL-2-bandit
	10 -8	0	250	500	750	1000 rounds	1250	1500	1750	2000	0	250	500	750	1000 rounds	1250	1500	1750	2000
				(a) Battle of the Sexes					(b) Pigou Network

  1. Let 𝑥 * = (𝛼 * 1 , . . . , 𝛼 * 𝑁 ) ∈ A be a strict Nash equilibrium. Then there exists a neighborhood U of 𝑥 * and constants 𝑐 𝑖 such that for each player 𝑖 ∈ N : 𝑣 𝑖 𝛼 * 𝑖 (𝑥) -𝑣 𝑖 𝛼 𝑖 (𝑥) ≥ 𝑐 𝑖 for all 𝑥 ∈ U and 𝛼 𝑖 ≠ 𝛼 * 𝑖 , 𝛼 𝑖 ∈ A 𝑖 . Proof. Our claim is a consequence of the definition of strict Nash equilibria. Specifically, from (NE) for each player 𝑖 ∈ N we have that 𝑣 𝑖 𝛼 * 𝑖 (𝑥 * ) > 𝑣 𝑖 𝛼 𝑖 (𝑥 * ) for all 𝛼 𝑖 ∈ A 𝑖 , 𝛼 𝑖 ≠ 𝛼 * By continuity there exists a neighborhood U ⊆ X and 𝑐 𝑖 > 0 for each player 𝑖 ∈ N such that 𝑣 𝑖 𝛼 * 𝑖 (𝑥) -𝑣 𝑖 𝛼 𝑖 (𝑥) ≥ 𝑐 𝑖 for all 𝑥 ∈ U (C.3) Then a collection is said to be "(𝛼 * 𝑖 , 𝑀 𝑖 ) 𝑖 ∈N -score-dominant" if there exist positive constants 𝑀 𝑖 > 0 corresponding open sets W 𝑖 (𝑀 𝑖 ) of the form W 𝑖 (𝑀 𝑖 ) = {𝑌 𝑖 : 𝑌 𝑖 𝛼 * 𝑖 -𝑌 𝑖 𝛼 𝑖 > 𝑀 𝑖 for all 𝛼 𝑖 ≠ 𝛼 there exist constants 𝑀 𝑖, 𝜀 and the corresponding score-dominant open sets for each player 𝑖 ∈ N such that: 𝑖 ∈N 𝑄 𝑖 (W 𝑖 (𝑀 𝑖, 𝜀 )) ⊆ U 𝜀 , where U 𝜀 = {𝑥 ∈ X : 𝑥 𝑖 𝛼 𝑌 𝑖 ∈ W 𝑖 (𝑀 𝑖, 𝜀 ) with 𝑥 𝑖 = 𝑄 𝑖 (𝑌 𝑖 ) we have that 𝑌 𝑖 𝛼 * 𝑖 -𝑌 𝑖 𝛼 𝑖 > 𝑀 𝑖, 𝜀 (C.5) 𝜃 ′ (𝑥 𝑖 𝛼 * 𝑖 ) -𝜃 ′ 𝑖 (𝑥 𝑖 𝛼 𝑖 ) -(𝜈 𝛼 * 𝑖 -𝜈 𝛼 𝑖 ) > 𝑀 𝑖, 𝜀 . (C.6) with 𝜈 𝛼 𝑖 ≥ 0 and 𝑥 𝑖 𝛼 𝑖 = 0 whenever 𝑥 𝑖 𝛼 𝑖 > 0. Notice that since 𝑀 𝑖, 𝜀 > 0 and 𝜃 ′ 𝑖 is strictly increasing, it holds that 𝑥 𝑖 𝛼 𝑖 < 𝑥 𝑖 𝛼 * 𝑖 . Indeed, assume by contradiction that 𝑥 𝑖 𝛼 𝑖 ≥ 𝑥 𝑖 𝛼 * 𝑖 for some 𝛼 𝑖 , then we examine two different cases: (i) If 𝑥 𝑖 𝛼 * 𝑖 = 0, then 𝑥 𝑖 𝛼 𝑖 ≥ 𝑥 𝑖 𝛼 * 𝑖 for all 𝛼 𝑖 ∈ A 𝑖 with 𝑥 𝑖 𝛼 𝑖 > 0 for at least one 𝛼 𝑖 ∈ A 𝑖 , 𝛼 𝑖 ≠ 𝛼 * It is easy to check that as 𝑀 ′ 𝑖 increases the score-dominant sets and their corresponding images are nested. Indeed if 𝑀 ′ ≥ 𝑀 𝜀 ⇒ W (𝑀) ⊆ W (𝑀 ′ ) ⇒ 𝑄(W (𝑀)) ⊆ 𝑄(W (𝑀 ′ )), since 𝑌 𝑖 𝛼 * 𝑖 -𝑌 𝑖 𝛼 𝑖 > 𝑀 > 𝑀 𝜀 for all 𝛼 𝑖 ≠ 𝛼 * 𝑖 , 𝛼 𝑖 ∈ A 𝑖 . Remark C.2. Notice that since the above analysis is for each strategy 𝛼 𝑖 ∈ A 𝑖 of player 𝑖, it implies that not only the images 𝑄 𝑖 (W 𝑀 𝑖 ) are nested, but also that if 𝑥 𝑖 = 𝑄 𝑖 (𝑌 𝑖 ), 𝑌 𝑖 ∈ W 𝑀 𝑖 all 𝑥 𝑖 𝛼 𝑖 → 0 for 𝛼 𝑖 ≠ 𝛼 * 𝑖 as 𝑀 𝑖 → ∞. Theorem 1. Let 𝑥 * be a strict Nash equilibrium of Γ, and fix some confidence level 𝛿 > 0. If Assumptions (A1)-(A3) hold, there exists an unbounded open set of initial conditions W init ⊆ Y and constants 𝑑 𝑖 , 𝑐 ′ 𝑖 with 𝑐 ′ 𝑖 > 0 such that, if 𝑌 1 ∈ W init , we have: 1. 𝑋 𝑛 converges to 𝑥 * with probability at least 1 -𝛿. 2. Conditioned on the above, the rate of convergence for each player 𝑖 ∈ N is given by

		(C.1)
	𝑖	(C.2)
		𝑖
	which is a contradiction to (C.6).
	(ii) if 𝑥 𝑖 𝛼 * 𝑖 > 0, then (C.6) implies that 𝑀 𝑖, 𝜀 ≤ 𝜃 ′ (𝑥 𝑖 𝛼 * 𝑖 ) -𝜃 ′ 𝑖 (𝑥 𝑖 𝛼 𝑖 ) < 0 which is again a contradic-
	tion.
	Therefore 𝜈 𝛼 * 𝑖 = 0 and (C.6) can be rewritten for all 𝛼 𝑖 ≠ 𝛼

■ 𝑀 𝑖 < 𝑌 𝑖, 𝛼 * 𝑖 -𝑌 𝑖, 𝛼 𝑖 Y 𝑥 * = ( 𝛼 * 1 , . . . , 𝛼 * 𝑁 ) U X

The following lemma plays a central role in the proof of our main theorem (Theorem 1). More precisely, Lemma C.2 provides a detailed analysis of the topology of a neighborhood U where variational inequality (C.1) holds both in primal space X and dual space Y. In order to achieve that we introduce the notion of "(𝛼 * 𝑖 , 𝑀 𝑖 )-score-dominant" open set for a player 𝑖 ∈ N , which we denote W 𝑖 (𝑀 𝑖 ). Definition (Score-Dominant Collection). Let 𝑥 * = (𝛼 * 1 , . . . , 𝛼 * 𝑁 ) ∈ A be a strict Nash equilibrium of a finite game Γ. * 𝑖 , 𝛼 𝑖 ∈ A 𝑖 } for each player 𝑖 ∈ N (C.4) Lemma C.2. Let 𝑥 * = (𝛼 * 1 , . . . , 𝛼 * 𝑁 ) ∈ A be a strict Nash equilibrium. Then for every 𝜀 ∈ (0, 1), * 𝑖 > 1 -𝜀 for every player 𝑖 ∈ N } Proof. For an arbitrary player 𝑖 ∈ N let W 𝑖 (𝑀 𝑖, 𝜀 ) be a score-dominant open set. We will show that any 𝑀 𝑖, 𝜀 > 𝜃 ′ 𝑖 (1) -𝜃 ′ 𝑖 ( 𝜀 |A 𝑖 | ) > 0 satisfies the desideratum. Indeed, again by using Lemma B.1 for a * 𝑖 with 𝑥 𝑖 𝛼 𝑖 > 0 as 𝜃 ′ 𝑖 (𝑥 𝑖 𝛼 𝑖 ) < -𝑀 𝑖, 𝜀 + 𝜃 ′ (𝑥 𝑖 𝛼 * 𝑖 ) < -𝑀 𝑖, 𝜀 + 𝜃 ′ (1) < 𝜃 ′ 𝑖 ( 𝜀 |A 𝑖 | ) (C.7) where last inequality holds by the choice of 𝑀 𝑖, 𝜀 > 𝜃 ′ 𝑖 (1) -𝜃 ′ 𝑖 ( 𝜀 |A 𝑖 | ) > 0. Again, since 𝜃 ′ is strictly increasing, this implies that for all 𝛼 𝑖 ≠ 𝛼 * 𝑖 either 𝑥 𝑖 𝛼 𝑖 = 0 or 0 < 𝑥 𝑖 𝛼 𝑖 < 𝜀 |A 𝑖 | . By union bound, this implies that 𝑥 𝑖 𝛼 * 𝑖 > 1 -𝜀 and equivalently that 𝑥 ∈ U 𝜀 . ■ C.1.

  𝑣 𝛼 (𝑋 𝑘 ) -𝑣 𝛼 * (𝑋 𝑘 ), noise 𝑘 = 𝑈 𝛼,𝑘 -𝑈 𝛼 * ,𝑘 , bias 𝑘 = 𝑏 𝛼,𝑘 -𝑏 𝛼 𝑛 𝑘=1 𝛾 𝑘 bias 𝑘 ≤ 2 𝑛 𝑘=1 𝛾 𝑘 ∥𝑏 𝑘 ∥ * = 𝑜( For the remaining term, 𝑅 𝑛 = 𝑛 𝑘=1 𝛾 𝑘 noise 𝑘 , firstly notice that it is trivially a martingale. We will prove that with probability at least 1 -𝛿 this martingale is bounded above by a term 𝜉 𝑛 which is dominated by the term 𝑛 𝑘=1 𝛾 𝑘 . Consider the event 𝐷 𝑛, 𝜉 𝑛 = {sup 1≤𝑘 ≤𝑛 |𝑅 𝑘 | ≥ 𝜉 𝑛 }; we will show that the union of these events E = ∞ 𝑛=1 𝐷 𝑛, 𝜉 𝑛 occurs with probability at most 𝛿 when 𝜉 𝑛 = 𝜉 ( 𝑛 𝑛 𝑘=1 𝛾 𝑘 ] 1+𝛽𝑞/2 for some 𝛽 < 1. By assumption (A3), 𝛿 𝑛 is summable and by controlling the parameter 𝜉 we can ensure that

	Fact (Generalized Hölder's Inequality). We will consider a variation of the
	Hölder'sinequality
	𝑛			𝑟			𝑛				𝑟-1 𝑛
	∑	𝑎 𝑘 𝑏 𝑘	≤	∑	𝑎	𝜇𝑟 𝑟-1 𝑘		∑	𝑎	(1-𝜇)𝑟 𝑘	𝑏 𝑟 𝑘 for all 𝑟 > 1, 𝜇 ∈ (0, 1)	(GH)
	𝑘=1					𝑘=1				𝑘=1
	Applying (GH) for 𝑎 𝑘 = 𝛾 2 𝑘 , 𝑏 𝑘 = ∥𝑈 𝑘 ∥ 2 * , 𝑟 = 𝑞/2 and 𝜇 = (𝑟 -1)/2𝑟 = (𝑞 -2)/2𝑞, we get
	ℙ(𝐷 𝑛, 𝜉 𝑛 ) ≤	𝑐 𝑞 ( 𝑛 𝑘=1 𝛾 𝑘 )	𝑞-2 2	𝑛 𝑘=1 𝛾 1+𝑞/2 𝑘 𝑛 𝜉 𝑞	𝔼[∥𝑈 𝑘 ∥ 𝑞 * ]	(C.15)
				≤	𝑐 𝑞 ( 𝑛 𝑘=1 𝛾 𝑘 )	𝑞-2 2	𝑛 𝑘=1 𝛾 1+𝑞/2 𝑘 𝑛 𝜉 𝑞	𝔼[𝔼[∥𝑈 𝑘 ∥ 𝑞 * | F 𝑘 ]]	(C.16)
				≤	𝑐 𝑞 ( 𝑛 𝑘=1 𝛾 𝑘 )	𝑞-2 2 𝜉 𝑞 𝑛	𝑛 𝑘=1 𝛾 1+𝑞/2 𝑘	𝜎 𝑞 𝑘	(C.17)
	Recall that 𝜉 𝑛 = 𝜉 𝑛 𝑘=1 𝛾 𝑘	𝑎 with 𝑎 < 1 and let us denote 𝛿 𝑛 =	𝑐 𝑞 𝜉 𝑞	𝑛 𝑘=1 𝛾 𝑘=1 𝛾 𝑘 ] 1+(2𝑎-1) 𝑞/2 or 𝑞 1+ 𝑞 2 𝑘 𝜎 𝑘 [ 𝑛
	equivalently 𝛿 𝑛 =	𝑐 𝑞 𝜉 𝑞	[	𝑛 𝑘=1 𝛾	1+ 𝑘	𝑞 2	𝜎	𝑞 𝑘
												𝑛 𝑘=1 𝛾 𝑘 )	(C.12)
	• (Payoff ) By Lemma C.1: 𝑛 𝑘=1 𝛾 𝑘 drift 𝑘 ≤ -𝑐 𝑛 𝑘=1 𝛾 𝑘	(C.13)
	• (Zero-mean Noise) 𝜉 𝑛	𝑞	≤	𝑐 𝑞 𝔼[( 𝑛 𝑘=1 𝛾 2 𝑘 ∥𝑈 𝑘 ∥ 2 * ) 𝑞/2 ] 𝑛 𝜉 𝑞	(C.14)

1 and C.2 there exist a neighborhood U strict , 𝑐 strict > 0 and 𝑀 strict > 0 such that 𝑣 𝛼 * (𝑥) -𝑣 𝛼 (𝑥) ≥ 𝑐 strict for all 𝛼 ≠ 𝛼 * , 𝛼 ∈ A and 𝑥 ∈ U strict (C.9) 𝑌 * 𝛼 -𝑌 𝛼 > 𝑀 strict for all 𝛼 ≠ 𝛼 * , 𝛼 ∈ A and 𝑥 = 𝑄(𝑌 ) ∈ U strict (C.10) We start by proving the following claim: Claim 1. Let W (𝑀) be a "score-dominant" open set for the strict Nash equilibrium 𝑥 * . Then there exists 𝑀 init > 0 such that if 𝑌 1 ∈ W (𝑀 init ) = W init then with probability at least 1 -𝛿 the sequence of play (𝑌 𝑛 ) 𝑛∈ℕ stays in W (𝑀 strict ). Proof of Claim. By definition of (FTGL) for the score differences we have 𝑌 𝛼,𝑛+1 -𝑌 𝛼 * ,𝑛+1 = 𝑌 𝛼,1 -𝑌 𝛼 * ,1 + 𝑛 ∑ 𝑘=1 𝛾 𝑘 (drift 𝑘 + noise 𝑘 + bias 𝑘 ) (C.11) where drift 𝑘 = * ,𝑘 . Notice that • (Bias) By (A1): 𝑘=1 𝛾 𝑘 ) 𝑎 with 𝑎 < 1. Using Theorem A.1 and Theorem A.2 we have ℙ(𝐷 𝑛, 𝜉 𝑛 ) ≤ 𝔼[|𝑅 𝑛 | 𝑞 ] ∞ ∑ 𝑛=1 𝛿 𝑛 = 𝛿 (C.18) Applying union bound to all the events 𝐷 𝑛, 𝜉 𝑛 we have that with probability at least 1 -𝛿 it is 𝑛 ∑ 𝑘=1 𝛾 𝑘 noise 𝑘 ≤ 𝜉 𝑛 for all 𝑛 = 1, 2, . . . (C.19) For the rest of the proof we condition to the event E 𝑐 . Let us define a constant 𝑀 init , such that 𝑀 init ≥ max{𝑀 strict , 𝑀 strict + sup 𝑛 ≥1 { 𝑛 𝑘=1 𝛾 𝑘 (noise 𝑘 + bias 𝑘 ) -(𝑐 -𝑐 ′ ) 𝑛 𝑘=1 𝛾 𝑘 }, for any arbitray choice of 0 < 𝑐 ′ < 𝑐 strict 5 . Let us recall the definition of a "score-dominant" open set W (𝑀) = {𝑌 : 𝑌 * 𝛼 -𝑌 𝛼 > 𝑀 for all 𝛼 ≠ 𝛼 * , 𝛼 ∈ A}.

  . The payoff signal which is estimated through the (IWE) can be rewritten as 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝑋 𝑛 ) + 𝑈 𝑖,𝑛 + 𝑏 𝑖,𝑛 , where 𝑈 𝑖,𝑛 = 𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) and 𝑏 𝑖,𝑛 = 𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ).1. LetA 𝑖 = {𝛼 1 , . . . , 𝛼 |A 𝑖 | } be the pure strategies of player 𝑖 ∈ N ; then 𝔼[𝑉 𝑖,𝑛 ] = ∑ 𝛼 -𝑖 ∈A -𝑖 (𝑢 𝑖 (𝛼 1 ; 𝛼 -𝑖 ), . . . , 𝑢 𝑖 (𝛼 |A 𝑖 | )) X-𝑖,𝑛 = 𝑣 𝑖 ( X𝑛 ) (D.12)where with X-𝑖,𝑛 we symbolize the joint probability distribution for all players except for the 𝑖 𝑡 ℎ player. 2. We move on to the second part of this proposition.∥𝑈 𝑖,𝑛 ∥ * = ∥𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) ∥ * (D.13) ≤ ∥𝑉 𝑖,𝑛 ∥ * + ∥𝑣 𝑖 ( X𝑛 ) ∥ * (D.14) ≤ max 𝛼∈A |𝑢 𝑖 (𝛼)||A 𝑖 |/𝜀 𝑛 + max Finally for the norm of the bias term, let again A 𝑖 = {𝛼 1 , . . . , 𝛼 |A 𝑖 | } be the pure strategies of player 𝑖 ∈ N ; then ∥𝑏 𝑖,𝑛 ∥ * = ∥𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ) ∥ * (D.17) = ∥ (𝑢 𝑖 (𝛼 1 ; X-𝑖,𝑛 ) -𝑢 𝑖 (𝛼 1 ; 𝑋 -𝑖,𝑛 ), . . . , 𝑢 𝑖 (𝛼 |A 𝑖 | ; X-𝑖;𝑛 ) -𝑢 𝑖 (𝛼 |A 𝑖 | ; 𝑋 -𝑖;𝑛 )) ∥ * (D.18) It is sufficient to examine one of the elements of the vector 𝑏 𝑖,𝑛 : ,𝑛 . . . X𝑁 𝛼 𝑁 ,𝑛 -𝑋 2𝛼 2 ,𝑛 . . . 𝑋 𝑁 𝛼 𝑁 ,𝑛 )𝑢 𝑖 (𝛼 1 , . . . , 𝛼 𝑁 )| ,𝑛 . . . X𝑁 𝛼 𝑁 ,𝑛 -𝑋 2𝛼 2 ,𝑛 . . . 𝑋 𝑁 𝛼 𝑁 ,𝑛 ||𝑢 𝑖 (𝛼 1 , . . . , 𝛼 𝑁 )|In this section we provide different algorithms and feedback models which connect to our general algorithm (FTGL) and model described in Section 3.2. We first present a useful proposition in order to calculate the permitted parameters of the algorithm in order for assumption A3 to be satisfied. Proposition D.2. 1. For all step sizes of the form 𝛾 𝑛 = 𝛾/𝑛 𝑝 , with 𝑝 < 1 and noise bounds 𝜎 𝑛 = 𝜎𝑛 𝑟 For all step-sizes of the form 𝛾 𝑛 = 𝛾/𝑛 and 𝜎 𝑛 = 𝜎𝑛 𝑟 , assumption A3 holds as long as Since 𝛾 𝑛 = 𝛾/𝑛 𝑝 and 𝜎 𝑛 = 𝜎𝑛 𝑟 , assumption A3 is restated as

	1. 𝛿 𝑛 =	𝑛 𝑘=1 𝛾 1+𝑞/2 𝑘 [ 𝑛 𝑘=1 𝛾 𝑘 ] 1+𝛽𝑞/2 𝜎 𝑞 𝑘	(D.26)
							𝑛	𝑛
					= 𝐶 𝑞 (	∑	1/𝑘 𝑝 ) -1-𝛽𝑞/2	∑	1/𝑘 𝑝 (1+ 𝑞 2 ) 𝑘 𝑟 𝑞	(D.27)
							𝑘=1	𝑘=1
							|𝑢 𝑖 (𝛼)|	(D.15)
							𝛼∈A
						= O(1/𝜀 𝑛 )	(D.16)
	3. |𝑢 𝑖 (𝛼 1 ; X-𝑖,𝑛 ) -𝑢 𝑖 (𝛼 1 ; 𝑋 -𝑖,𝑛 )|	(D.19)
	= |	∑	• • •	∑	( X2𝛼 2 (D.20)
		𝛼 2 ∈A 2		𝛼 𝑁 ∈A 𝑁
	≤	∑	• • •	∑	| X2𝛼 2 (D.21)
	𝛼 2 ∈A 2		𝛼 𝑁 ∈A 𝑁
	= O(𝜀 𝑛 )				(D.22)
							■
	assumption A3 is satisfied if
					2	-𝑝 + 2𝑟 < 𝛽(1 -𝑝) for some 𝛽 < 1	(D.23)
					𝑞
	Furthermore, it holds that
							1/𝑞 + 𝑟 < 1/2	(D.24)
	2. 1/𝑞 + 𝑟 < 1/2	(D.25)

  𝛾 𝑛 = 𝛾/𝑛 and 𝜎 𝑛 = 𝜎𝑛 𝑟 , then for assumption A3 we have Full information). In this case players have access to their full payoff vector 𝑣(𝑋 𝑛 ) for each round 𝑛 = 1, 2, . . . and thus 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝑋 𝑛 ) for all 𝑖 ∈ N . From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. § Model D.2 ((FTRL) & Noisy payoff feedback). In this setting at each round 𝑛 = 1, 2, . . . players have access to a perturbed version of their full payoff vector 𝑣(𝑋 𝑛 ) with a zero-mean noise 𝑈 𝑛 . Two examples of such noises that we consider in the experimental section are a zero-mean guassian noise and a uniform noise at [-1.1]. Both these noises satisfy (A2) with deterministic constant bounds for all 𝑞 ∈ [1, ∞]. Thus • (A1): Trivially satisfied since 𝑏 = 0. • (A2): Satisfied for all 𝑞 ∈ [1, ∞]. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. § Model D.3 ((FTRL) & Oracle-based feedback). Assume that each player chooses an action based on a given mixed strategy, and once every player has chosen an action, an oracle reveals to each player their corresponding pure payoff vector. Formally, at each round 𝑛 = 1, 2, . .. , each player chooses a pure strategy 𝛼 𝑖,𝑛 ∈ A 𝑖 based on a mixed strategy 𝑋 𝑖,𝑛 ∈ X 𝑖 and subsequently observes the payoff vector 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ) = (𝑢 𝑖 (𝛼 𝑖 ; 𝛼 -𝑖,𝑛 )) 𝛼 𝑖 ∈A 𝑖 . (D.42) Regarding our basic assumptions, we readily have 𝑏 𝑖,𝑛 = 0 and 𝑈 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ); hence: • (A1): Trivially satisfied since 𝑏 𝑖,𝑛 = 0. • (A2): Satisfied because ∥𝑈 𝑖,𝑛 ∥ * = ∥𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ) ∥ * ≤ 2 max 𝛼∈A ∥𝑣 𝑖 (𝛼) ∥ * , so 𝑈 𝑛 has uniformly bounded moments for all 𝑞 ∈ [1, ∞]. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. § Model D.4 ((FTRL) & Payoff-based feedback).If the players only observe their realized rewards, they have to construct a model for 𝑉 𝑛 based on incomplete information. This is the standard setting for multi-armed bandits, so it is often referred to as the "bandit feedback" model. In this case, the players' action selection process is as in Model D.3 above, but the feedback signal sequence 𝑉 𝑛 is now reconstructed by means of the importance-weighted estimator𝑉 𝑖 𝛼 𝑖 ,𝑛 = 1{𝛼 𝑖,𝑛 = 𝛼 𝑖 } X𝑖𝛼 𝑖,𝑛 𝑢 𝑖 (𝛼 𝑛 ) (IWE)where X𝑖,𝑛 = (1 -𝜀 𝑛 ) 𝑋 𝑖,𝑛 + 𝜀 𝑛 /|A 𝑖 | is the mixed strategy of the 𝑖-th player at stage 𝑛. Compared to 𝑋 𝑖,𝑛 the player's actual sampling strategy is now recalibrated by an explicit exploration parameter 𝜀 𝑛 → 0 whose role is to stabilize the learning process. The idea behind this adjustment is that even if a strategy has zero probability to be chosen under 𝑋 𝑛 , it will still be sampled with positive probability thanks to the mixing factor 𝜀 𝑛 . • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1] and 𝜀 In this case the full payoff vector of each player is 𝑉 𝑖,𝑛 = 𝑣 𝑖 ( X𝑛 ) for all 𝑖 ∈ N . As we proved above the state X𝑛 can be treated separately and thus • (A1): Trivially satisfied since 𝑏 𝑖,𝑛 = 0. • (A2): Trivially satisfied since 𝑈 𝑖,𝑛 = 0. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. § Model D.6 ((OptFTRL) & Noisy payoff feedback). Again in this setting at each round 𝑛 = 1, 2, . . . players have access to a perturbed version of their full payoff vector 𝑣( X𝑛 ) with a zero-mean noise 𝑈 𝑛 . Two examples of such noises that we consider in the experimental section are a zero-mean guassian noise and a uniform noise at [-1.1]. 𝛼 𝑖 ∈A 𝑖 .player's input signal is a special case of (4) with payoff feedback 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ), zero-mean noise 𝑈 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 ( X𝑛 ) and bias 𝑏 𝑖,𝑛 = 0 that satisfy all of the assumptions A1 -A3. In more detail, we have: • (A1): trivially satisfied since 𝑏 𝑖,𝑛 = 0. • (A2): ∥𝑈 𝑖,𝑛 ∥ * = ∥𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 ( X𝑛 ) ∥ * ≤ 2 max 𝛼∈A ∥𝑣 𝑖 (𝛼) ∥ * and thus the noise has bounded moments for all 𝑞 ∈ [1, ∞]. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. § Model D.8 ((OptFTRL) & Payoff-based feedback). As we mentioned in Model D.4, in this case players only observe their realized rewards; thus they have to construct a model for 𝑉 𝑛 based on incomplete information. The players' action selection process is as in Model D.7 above, but the feedback signal sequence 𝑉 𝑛 is now reconstructed by means of the importance-weighted estimator 𝑉 𝑖 𝛼 𝑖 ,𝑛 = 1{𝛼 𝑖,𝑛 = 𝛼 𝑖 } X𝑖𝛼 𝑖,𝑛 𝑢 𝑖 (𝛼 𝑛 ) (IWE) where X𝑖,𝑛 = (1 -𝜀 𝑛 ) X𝑖,𝑛 + 𝜀 𝑛 /|A 𝑖 | is the mixed strategy of the 𝑖-th player at stage 𝑛. Compared to X𝑖,𝑛 the player's actual sampling strategy is now recalibrated by an explicit exploration parameter 𝜀 𝑛 → 0. This type of feedback may be seen as a special case of the model (4) with 𝑈 𝑖,𝑛 = 𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) and 𝑏 𝑖,𝑛 = 𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ). All of the assumptions (A1)-(A3) are again satisfied; indeed: • (A1): From Proposition D.1 ∥𝑏 𝑖,𝑛 ∥ * = 𝑂 (𝜀 𝑛 ). Thus our assumption is satisfied since 𝜀 𝑛 → 0. • (A2): Again from Proposition D.1 ∥𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) ∥ * = 𝑂 (1/𝜀 𝑛 ) and thus the noise has bounded moments, 𝜎 𝑛 = Θ(1/𝜀 𝑛 ) for all 𝑞 ∈ [1, ∞]. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1] and 𝜀 From Proposition D.2 and our specific analysis for (MirrorProx) is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. § We simply mention here that in the exact same way all of the assumptions (A1)-(A3) are satisfied for the second "intermediate" state of (MirrorProx). Model D.11 ((MirrorProx) & Oracle-based feedback). In this case, at each round 𝑛 each player 𝑖 ∈ N chooses two pure strategies 𝛼 𝑖,𝑛 and 𝛼 𝑖,𝑛+1/2 successively based on the mixed strategies 𝑋 𝑖,𝑛 , 𝑋 𝑖,𝑛+1/2 equivalently. Thus, the first payoff signal is 𝑉 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ) with 𝑏 𝑖,𝑛 = 0 and 𝑈 𝑖,𝑛 = 𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ). Satisfied because ∥𝑈 𝑖,𝑛 ∥ * = ∥𝑣 𝑖 (𝛼 𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ) ∥ * ≤ 2 max 𝛼∈A ∥𝑣 𝑖 (𝛼) ∥ * , so 𝑈 𝑛 has uniformly bounded moments for all 𝑞 ∈ [1, ∞]. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1], by also taking into account our specific analysis for (MirrorProx) presented above. Trivially satisfied since 𝑏 = 0. • (A2): Satisfied because ∥𝑈 𝑖,𝑛+1/2 ∥ * = ∥𝑣 𝑖 (𝛼 𝑛+1/2 ) -𝑣 𝑖 (𝑋 𝑛+1/2 ) ∥ * ≤ 2 max 𝛼∈A ∥𝑣 𝑖 (𝛼) ∥ * , so 𝑈 𝑛 has uniformly bounded moments for all 𝑞 ∈ [1, ∞]. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1], by also taking into account our specific analysis for (MirrorProx) presented above. § Model D.12 ((MirrorProx) & Payoff-based feedback). In this case, as we have already mentioned, players only observe their realized rewards and the feedback signal sequence 𝑉 𝑛 is now reconstructed by means of the importance-weighted estimator 𝑉 𝑖 𝛼 𝑖 ,𝑛 = 1{𝛼 𝑖,𝑛 = 𝛼 𝑖 } X𝑖𝛼 𝑖,𝑛 𝑢 𝑖 (𝛼 𝑛 ) (IWE) where X𝑖,𝑛 = (1 -𝜀 𝑛 ) 𝑋 𝑖,𝑛+1/2 + 𝜀 𝑛 /|A 𝑖 | is the mixed strategy of the 𝑖-th player at stage 𝑛, with 𝜀 𝑛 → 0. The IWE estimator may be seen as a special case of the model (4) with 𝑈 𝑖,𝑛 = 𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) and 𝑏 𝑖,𝑛 = 𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ). All of the assumptions (A1)-(A3) are again satisfied; indeed: • (A1): From Proposition D.1 ∥𝑏 𝑖,𝑛 ∥ * = 𝑂 (𝜀 𝑛 ). Thus our assumption is satisfied since 𝜀 𝑛 → 0. • (A2): Again from Proposition D.1 ∥𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) ∥ * = 𝑂 (1/𝜀 𝑛 ) and thus the noise has bounded moments, 𝜎 𝑛 = Θ(1/𝜀 𝑛 ) for all 𝑞 ∈ [1, ∞]. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1] and 𝜀 𝑛 ∝ 1/𝑛 𝑟 , 𝑟 ∈ (0, 1/2).

					35)
	1/𝑞 + 𝑟 < 1/2	(D.36)
	2. Let 𝛿 𝑛 =	𝑛 𝑘=1 𝛾 1+𝑞/2 𝑘 [ 𝑛 𝑘=1 𝛾 𝑘 ] 1+𝛽𝑞/2 𝜎 𝑞 𝑘	(D.37)
	= 𝐶 𝑞	𝑛 𝑘=1 [ 𝑛 𝑘=1	1 𝑘 1+𝑞/2 𝑘 𝑟 𝑞 1 𝑘 ] 1+𝛽𝑞/2	(D.38)
	≤ 𝐶 ′ 𝑞 (log(𝑛 + 1)) -1-𝛽𝑞/2 𝑛 1-1-𝑞/2+𝑟 𝑞	(D.39)
	≤ 𝐶 ′ 𝑞 (log(𝑛 + 1)) -1-𝛽𝑞/2 𝑛 -𝑞/2+𝑟 𝑞	(D.40)
	Since the sum ∞ 𝑛=1 1/(log 1+𝜀 (𝑛)𝑛 1+𝜀 ′ ) is finite for all 𝜀, 𝜀 ′ > 0; assumption A3 is satisfied as
	long as
	-𝑞/2 + 𝑟𝑞 < -1 ⇒ 1/𝑞 + 𝑟 < 1/2	(D.41)
					■
	Model D.1 ((FTRL) & All of the assumptions
	A1-A3 are satisfied; indeed • (A1): Trivially satisfied since 𝑏 𝑖,𝑛 = 0. • (A2): Trivially satisfied since 𝑈 𝑖,𝑛 = 0. constant bounds for all 𝑞 ∈ [1, ∞]. Thus • (A1): Trivially satisfied since 𝑏 𝑖,𝑛 = 0. Hence: • (A1): Trivially satisfied since 𝑏 𝑖,𝑛 = 0. • (A3): Both these noises satisfy (A2) with deterministic • (A2): Satisfied for all 𝑞 ∈ [1, ∞]. • (A2):

The IWE estimator may be seen as a special case of the model

[START_REF] Blum | Routing without regret: on convergence to Nash equilibria of regretminimizing in routing games[END_REF]

with 𝑈 𝑖,𝑛 = 𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) and 𝑏 𝑖,𝑛 = 𝑣 𝑖 ( X𝑛 ) -𝑣 𝑖 (𝑋 𝑛 ). All of the assumptions (A1)-(A3) are again satisfied; indeed: • (A1): From Proposition D.1 ∥𝑏 𝑖,𝑛 ∥ * = 𝑂 (𝜀 𝑛 ). Thus our assumption is satisfied since 𝜀 𝑛 → 0. • (A2): Again from Proposition D.1 ∥𝑉 𝑖,𝑛 -𝑣 𝑖 ( X𝑛 ) ∥ * = 𝑂 (1/𝜀 𝑛 ) and thus the noise has bounded moments, 𝜎 𝑛 = Θ(1/𝜀 𝑛 ) for all 𝑞 ∈ [1, ∞]. 𝑛 ∝ 1/𝑛 𝑟 , 𝑟 ∈ (0, 1/2). § Model D.5 ((OptFTRL) & Full information). • (A3): From Proposition D.2 and our specific analysis for (OptFTRL) is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. § Model D.7 ((OptFTRL) & Oracle-based feedback). In this case the payoff signal 𝑉 𝑖,𝑛 , which depends on the state X𝑛 , is generated as follows: at each round 𝑛 = 1, 2, . . . , every player 𝑖 ∈ N picks an action 𝛼 𝑖,𝑛 ∈ A 𝑖 based on X𝑖,𝑛 ∈ X 𝑖 and observes the pure payoff vector 𝑣 𝑖 (𝛼 𝑛 ) ≡ (𝑢 𝑖 (𝛼 𝑖 ; 𝛼 -𝑖,𝑛 )) 𝑛 ∝ 1/𝑛 𝑟 , 𝑟 ∈ (0, 1/2). § Model D.9 ((MirrorProx) & Full information). In this case players have access to their full payoff vector 𝑣(𝑋 𝑛 ) for each round 𝑛 = 1, 2, . . .; for the algorithm (MirrorProx) we observe two payoff vectors at each round and as stated in the specific analysis above, for each one of 𝑣 𝑖 (𝑋 𝑛+1/2 ) and 𝑣 𝑖 (𝑋 𝑛 ), we have • Assumption A1: Trivially satisfied since 𝑏 𝑖,𝑛 = 0. • (A2): Trivially satisfied since 𝑈 𝑖,𝑛 = 0. • (A3): From Proposition D.2 is satisfied for all the step-sizes of the form 𝛾 𝑛 ∝ 1/𝑛 𝑝 , 𝑝 ∈ [0, 1]. § Model D.10 ((MirrorProx) & Noisy payoff feedback). As before at each round 𝑛 = 1, 2, . . . players have access to a perturbed version of their full payoff vector 𝑣(𝑋 𝑛 ) with a zero-mean noise 𝑈 𝑛 . Two examples of such noises that we consider in the experimental section are a zero-mean guassian noise and a uniform noise at [-1.1]. Both these noises satisfy (A2) with deterministic constant bounds for all 𝑞 ∈ [1, ∞]. Thus • (A1): Trivially satisfied since 𝑏 𝑖,𝑛 = 0. • (A2): Satisfied for all 𝑞 ∈ [1, ∞]. • (A3): § The second payoff signal is 𝑉 𝑖,𝑛+1/2 = 𝑣 𝑖 (𝛼 𝑛+1/2 ) with 𝑏 𝑖,𝑛+1/2 = 0 and 𝑈 𝑖,𝑛+1/2 = 𝑣 𝑖 (𝛼 𝑛+1/2 ) -𝑣 𝑖 (𝑋 𝑛+1/2 ) • (A1):

35th Conference on Neural Information Processing Systems (NeurIPS 2021), Sydney, Australia.

In this context, regularization can be seen as a means to reinforce exploration so as to avoid committing prematurely to a given strategy.

As a sidenote, we should remark here that FTGL also contains the optimistic FTRL algorithm, which does converge to mixed Nash equilibria in bilinear zero-sum games with perfect, deterministic feedback[16, 25,

[START_REF] Mertikopoulos | Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile[END_REF]. At first glance, this would seem to contradict the results of[START_REF] Flokas | No-regret learning and mixed Nash equilibria: They do not mix[END_REF][START_REF] Giannou | Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information[END_REF], but one needs to bear in mind that the convergence of (OptFTRL) to mixed equilibria only occurs in settings with perfect information (i.e., 𝑉 𝑛 = 𝑣 (𝑋 𝑛 ) for all 𝑛 = 1, 2, . . . ). In the presence of uncertainty, this convergence is destroyed[START_REF] Chavdarova | Reducing noise in GAN training with variance reduced extragradient[END_REF][START_REF] Hsieh | Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling[END_REF], so there is no contradiction with the results of[START_REF] Giannou | Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information[END_REF]. Because we are primarily interested in learning with limited information and/or under uncertainty, we will not treat this somewhat fragile case.

It is worth mentioning that the images of these open sets belong to neighborhoods of 𝑥 * , which are nested as 𝑀 𝑖 increases.

such a 𝑀 init exists since both the bias and the noise terms are dominated by the term -(𝑐 -𝑐 ′ ) 𝑛 𝑘=1 𝛾 𝑘 .

such a 𝑀 init > 0 exists since both the bias and the noise terms are dominated by the term the terms 2 𝑛 𝑘=1 𝛾 𝑘 ∥𝑏 𝑘 ∥ * , 𝜉 𝑛 and consequently by -(𝑐 -𝑐 ′ ) 𝑛 𝑘=1 𝛾 𝑘 .

The aforementioned by contradiction argument also provides a short proof of Remark C.2.

𝜃 ′ is strictly increasing and so does its inverse.

Below we prove some properties concerning the case of payoff oracle/bandit feedback.

4: Pigou's Network E.2. Experimental setup and methodology. Below, we will present separately the three archetypal instantiations of (FTGL) that we discussed in Appendix D, namely (FTRL),(OptFTRL) and (MirrorProx). All algorithms were run on a) a game of the Battle of the Sexes; and b) Pigou's linear version with 𝑁 = 1000 atomic drivers. For each algorithm and each model we will present the performance of two well-studied regularizers: • entropic :

𝛼 /2. We will group our models with the following way: The first collection of figures for each algorithmic subsection will include the {oracle-based,payoff based/bandit} feedback model for the two aforementioned games for constant step-size and inverse-polynomial 𝛾 𝑛 ∝ 1/𝑛 1/2 . The latter one will present the {perfect,uniform-noise,gaussian-noise} feedback. Finally, the shaded areas around the curves represent the error bars in the execution for different random initializations.