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

Abstract:
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.

text: 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.

heading: 1 Introduction
text: 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 [43], generative adversarial networks [18], auctions [44], 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 [19] 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.
35th Conference on Neural Information Processing Systems (NeurIPS 2021), .
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 [20], which can be stated as follows: Under the replicator dynamics – the continuous-time limit of the multiplicative / exponential weights (EW) algorithm [2, 29, 45] – 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 [11, 15, 30], but it extends to the entire family of “follow the regularized leader” (FTRL) dynamics [41, 42], in both continuous [11, 30] and discrete time [15]. In particular, [15] 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 [10, 38–40], extra-gradient and mirror-prox methods [24, 25, 35], 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” q 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, q(G) = exp(G) for entropic / logit choice models, whereas q(G) = [G]+ for methods run with Euclidean projections. We then show that, with probability at least 1 − X, the algorithm’s local rate of convergence to a strict equilibrium G∗ is of the form ‖-= − G∗‖ ≤ q(3 − 2 ∑= B=1 WB), where W= is the method’s learning rate and 2, 3 are constants with 2 > 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 [5, 41].
Equally surprising is the fact that the type of feedback employed does not affect the method’s rate of convergence: ceteris paribus, the base sequence of states generated by 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 [6, 27]; 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 [9, 10, 16, 17, 21, 23, 28, 31–33] 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 [16, 24, 33, 35], and those focusing on the algorithm’s “last-iterate” [9, 10, 17, 21, 23, 28]. 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. [3, 4, 12, 13, 36, 44] 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. [8] 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. [8]. We are not aware of any other comparable results in the literature.

heading: 2 Preliminaries
text: Finite games. Throughout this work we consider #-players finite games in normal form. Formally, each player, indexed by 8 ∈ N = {1, . . . , #}, has a finite set of pure strategies U8 ∈ A8 = {1, . . . , 8}, and a payoff function D8 : A→ ℝ, where A B ∏ 8 A8 is the space of all pure strategy profiles. For concision, we will denote such a game as a tuple Γ = Γ(N ,A, D). During play, players can also play mixed strategies, i.e., probability distributions G8 ∈ X8 B Δ(A8) over their pure strategies. In this case, we will write G8U8 for the probability that player 8 ∈ N selects U8 ∈ A8 under G8 , G = (G1, . . . , G# ) for the players’ mixed strategy profile, and X B ∏ 8 X8 for the set thereof. Finally, when focusing on the mixed strategy of a particular player 8 ∈ N , we will use the shorthand (G8; G−8) B (G1, . . . , G8 , . . . , G# ) – and, similarly, (U8;U−8) for pure strategies. Now, the expected payoff of player 8 in a mixed strategy profile G ∈ X is given by
D8 (G) ≡ D8 (G8; G−8) = ∑
U1∈A1 · · · ∑ U# ∈A# D8 (U1, . . . , U# ) · G1,U1 · · · G# ,U# (1)
where D8 (U1, . . . , U# ) is the payoff of player 8 in the action profile U = (U1, . . . , U# ) ∈ A. For posterity, we will also write E8U8 (G) = D8 (U8; G−8) for the payoff that player 8 would have gotten by playing U8 ∈ A8 against the mixed strategy profile G−8 of all other players. In this way, the mixed payoff vector of the 8-th player can be seen as a vector field E8 : X → Y8 = ℝA8 which can be written in components as E8 (G) = (E8U8 (G))U8 ∈A8 . (2) Again, we will write E(G) = (E1 (G), . . . , E# (G)) for the ensemble of payoff vectors of all players and Y = ∏8 Y8 for the space of payoff vectors respectively. Finally, in a slight abuse of notation, we will identify U8 with the mixed strategy that assigns all probability to U8 , and we will write E8 (U) = (D8 (U8;U−8))U8 ∈A8 . for the corresponding pure payoff vector.
Nash equilibrium. The most widely used solution concept in game theory is that of a Nash equilibrium i.e., a (possibly) mixed strategy profile G∗ ∈ X that discourages unilateral deviations;
formally, G∗ ∈ X is said to be a Nash equilibrium of Γ if D8 (G∗) ≥ D8 (G8; G∗−8) for all G8 ∈ X8 and all 8 ∈ N . (NE) The set of pure strategies supported at the equilibrium component G∗ 8 ∈ X8 of each player will be denoted by supp(G∗ 8 ) = {U8 ∈ A8 : G∗8U8 > 0}. In turn, the size of the support of G
∗ leads to the following dichotomy: G∗ is called pure if supp(G∗ 8 ) ≡ ∏8∈# supp(G∗8 ) is a singleton and mixed otherwise.
Finally, we will also say that a Nash equilibrium G∗ is strict if (NE) holds as a strict inequality whenever G8 ≠ G∗8 ; 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 G∗ 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 [14]; these robustness properties of strict equilibria will play a key role in the sequel.

heading: 3 Regularized learning
text: 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” .8,= ∈ Y8 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 &8 : Y8 → X8 which outputs the player’s mixed strategy -8,= = &8 (.8,=) as a function of .8,= (see below for a detailed definition). Then, after selecting their actions and collecting their rewards, players also receive – or otherwise construct – an estimate +8,= 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
-8,= = &8 (.8,=) .8,=+1 = .8,= + W=+8,=
(FTGL) where W= > 0 is a “learning rate” parameter such that ∑
= W= = ∞. 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 +8,= are provided right after.
3.1. The choice map. The guiding principle behind the definition of the players’ choice maps &8 : Y8 → X8 , 8 ∈ N , as follows: Because the players’ score variables .8,= are assumed to represent an estimate of each strategy’s cumulative payoff over time, &8 is defined as a “regularized” version of the best-response correspondence H8 ↦→ arg maxG8 ∈X8 〈H8 , G8〉.
1 On that account, we will consider regularized best responses of the general form
&8 (H8) = arg max G8 ∈X8 {〈H8 , G8〉 − ℎ8 (G8)} (3)
where ℎ8 : X8 → ℝ denotes the 8-th player’s regularization function. For concreteness, we will focus on a class of decomposable regularizers of the form ℎ8 (G8) =∑
U8 ∈A8 \8 (G8) where the so-called “kernel function” \8 : [0, 1] → ℝ is assumed continuous on [0, 1], twice differentiable on (0, 1], and strongly convex, i.e., inf (0,1] \ ′′8 > 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 \ (G) = G log G i.e., ℎ(G8) = ∑ U8 ∈A8 G8U8 log G8U8 . This choice of regularizer is well-known to provide the logit
choice map Λ8 (H8) = (exp(H8U8 ))U8 ∈A8 / ∑
U8 ∈A8 exp(H8U8 ). The resulting algorithm is known in the literature as the multiplicative/exponential weights algorithm [1, 2, 29, 41, 45]. Example 3.2 (Euclidean projection). Another popular regularizer is the quadratic penalty ℎ(G) =∑
0 G0 2/2, which yields the payoff projection map Π(H) = arg minG∈Δ‖H − G‖2, cf. [26, 46].
1In this context, regularization can be seen as a means to reinforce exploration so as to avoid committing prematurely to a given strategy.
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.
3.2. 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 += = E(-=) + /= (4) for some abstract error process /= = (/8,=)8∈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 /= = *= + 1=, where
1= = [/= |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: 1= converges uniformly to 0 as =→∞. (A1) 2. Bounded variance: [‖*=‖@∗ |F=] ≤ f@= for some @ > 2. (A2)
In the above f= 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 1= 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 U8,= ∈ A8 based on a mixed strategy -8,= ∈ X8 and subsequently observes the payoff vector +8,= = E8 (U=) = (D8 (U8;U−8,=))U8 ∈A8 . (6) Thus, in this case, (FTGL) boils down to the standard “follow the regularized leader” (FTRL) algorithm of [41, 42]. As for our basic feedback assumptions, we readily see that 18,= = 0 and *8,= = E8 (U=) − E8 (-=); hence: • (A1) is trivially satisfied since 18,= = 0. • (A2) is again satisfied because ‖*8,=‖∗ = ‖E8 (U=) − E8 (-=)‖∗ ≤ 2 maxU∈A‖E8 (U)‖∗, 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 [5, 6, 27], 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
+8U8 ,= = 1{U8,= = U8}
-̂8U8,= D8 (U=) (IWE)
where -̂8,= = (1 − Y=)-8,= + Y=/|A8 | is the mixed strategy of the 8-th player at stage =. Compared to -8,= the player’s actual sampling strategy is now recalibrated by an explicit exploration parameter Y= → 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 Y=.
The importance-weighted estimator (IWE) estimator may be seen as a special case of the model (4) with *8,= = +8,= − E8 ( -̂=) and 18,= = E8 ( -̂=) − E8 (-=). Both assumptions (A1),(A2) are again satisfied; indeed:
• For (A1): A standard calculation performed in ?? reveals that ‖18,=‖∗ = $ (Y=). Thus our assumption is satisfied since Y= → 0. • For (A2): Again a standard calculation presented in ?? reveals that ‖+8,= − E8 ( -̂=)‖∗ = $ (1/Y=) and thus the noise has bounded moments, f= = Θ(1/Y=) for all @ ∈ [1,∞].
Model 3 (OptFTRL with oracle-based feedback). Following Rakhlin and Sridharan [40], the socalled “optimistic” variant of FTRL is given by the recursive formula:
.̃8,= = .8,= + W=+8,=−1 -̃8,= = &8 (.̃8,=) .8,=+1 = .8,= + W=+8,= (OptFTRL)
In the above the payoff signal +8,=, which depends on the state -̃=, is generated as follows: at each round = = 1, 2, . . . , every player 8 ∈ N picks an action U8,= ∈ A8 based on -̃8,= ∈ X8 and observes the pure payoff vector E8 (U=) ≡ (D8 (U8;U−8,=))U8 ∈A8 . 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 +8,= = E8 (U=), zeromean noise*8,= = E8 (U=) − E8 ( -̃=) and bias 18,= = E8 ( -̃=) − E8 (-=) that satisfy both the assumptions (A1),(A2). In more detail, we have:
• For (A1): ‖18,=‖∗ = ‖E8 ( -̃=) − E8 (-=)‖∗ = $ (W=), which goes uniformly to 0 whenever W= → 0. • For (A2): ‖*8,=‖∗ = ‖E8 (U=) − E8 ( -̃=)‖∗ ≤ 2 maxU∈A‖E8 (U)‖∗ 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.

heading: 4 Analysis & Results
text: 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 [11, 15], so they are the only reasonable candidates to consider when examining the rate of convergence of a regularized learning algorithm.2
2As 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, 32]. At first glance, this would seem to contradict the results of [11, 15], but one needs to bear in mind that the convergence of (OptFTRL) to mixed equilibria only occurs in settings with perfect information (i.e., += = E (-=) for all = = 1, 2, . . . ). In the presence of uncertainty, this convergence is destroyed [7, 22], so there is no contradiction with the results of [15]. Because we are primarily interested in learning with limited information and/or under uncertainty, we will not treat this somewhat fragile case.
To 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 X= B
∑= :=1 W 1+ @2 : f @
:[∑= :=1 W: ]1+V@/2 is summable for some V < 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 W= (and Y= 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 &8 : Y8 → X8 , 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 ← .= + W=+=, the method’s strategy variable will move forward as -=+1 ← -= + W= &(+)+= +O(W2=), where & denotes the Jacobian matrix of &. Thus, to leading order in W=, the update -=+1 ← -= is dominated by the first derivatives of &.
By a relatively straightforward application of the Legendre identity from convex analysis (& = (mℎ)−1 in our context; see below for a precise statement), this rate of change is related to the inverse mapping of the derivative each \8 (the kernel of the underlying regularizer). Motivated by this observation, we introduce below the algorithm’s so-called rate function:
q8 (C) = { (\ ′ 8 )−1 (C) if C > \ ′ 8 (0+),
0 otherwise. (7)
The definition of the rate function q captures the sensitivity of the choice map & in a very precise way: If the score difference corresponding to two pure strategies U, V ∈ A8 grows as HV − HU = C for some C > 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 q acts as a “transfer” function in this regard. Specifically, as we show in detail later, we have GU = q(−Θ(C)), i.e., q determines the rate at which GU 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 G∗ be a strict Nash equilibrium of Γ, and fix some confidence level X > 0. If Assumptions (A1)–(A3) hold, there exists an unbounded open set of initial conditions Winit ⊆ Y and constants 38 , 2′8 with 2 ′ 8 > 0 such that, if .1 ∈ Winit, we have: 1. -= converges to G∗ with probability at least 1 − X. 2. Conditioned on the above, the rate of convergence for each player 8 ∈ N is given by
‖-8,= − G∗8 ‖1 ≤ 2 ∑
U8 ∈A8\supp(G∗8 ) q8
( 38 − 2′8 ∑= :=1 W: ) . (8)
Armed with this general result, we readily obtain the following immediate consequences thereof: Corollary 1. If the regularizer employed is non-steep (i.e., \8 is differentiable at 0), -= converges to G∗ 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 W= ∝ 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 W= ∝ 1/=? , ? ∈ [0, 1] and a mixing parameter Y= ∝ 1/=A , A ∈ (0, 1/2). Then the conclusion of Theorem 1 holds. Remark 4.1. We stress out here that for all the bandit-feedback derived results, the convergence rates refer to -8,= instead of the explicit exporation term -̂8,= whose rate is always dominated by the mixing parameter Y=. Corollary 4. Suppose that Optimistic FTRL is run with oracle-based feedback as per Model 3 and a learning rate of the form W= ∝ 1/=? , ? ∈ (0, 1]. Then the conclusion of Theorem 1 holds.
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 W= ∝ 1/=?, ? ∈ [0, 1], and a mixing parameter Y= ∝ 1/=A with A ∈ (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 ??) shows that constant step-sizes are also covered by the convergence rate guarantee (8) of Theorem 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 ℎ8 in the solution of the convex constrained optimization problem, that G = &8 (H) 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 G∗ and constants 21, . . . , 2# such that
E8U∗ 8 (G) − E8U8 (G) ≥ 28 for all G ∈ U and U8 ≠ U∗8 , U8 ∈ A8 , 8 ∈ 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 Lemma 1. There exists a neighborhood U , constants 21, . . . , 2# and "1, . . . , "# for which (9) holds such that ∏ 8∈N &8 (W"8 ) ⊆ U , where W"8 are open sets of the form 3
W"8 = {.8 : .8U∗8 − .8U8 > "8 for all U8 ≠ U ∗ 8 , U8 ∈ A8} for "8 > 0, 8 ∈ N (10)
Step 2. We now focus on one player 8 ∈ N and drop the index 8 altogether. First we prove that there exists an open set of initializations Winit 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 U ∈ A and U∗ ∈ supp(G∗)
.U,=+1 − .U∗ ,=+1 = .U,1 − .U∗ ,1 + =∑
:=1 W: (drift: + noise: + bias: ) (11)
where drift: = EU (-: ) − EU∗ (-: ), noise: = *U,: −*U∗ ,: , bias: = 1U,: − 1U∗ ,: . We will prove by induction our forward-invariant statement; let .: ∈ W" and thus -: ∈ U for all : = 1, . . . , = then • By (9) we have ∑= :=1 W:drift: ≤ −2 ∑= :=1 W: for all : = 1, . . . , =.
• By the triangle inequality and (A1), the term ∑= :=1 W:bias: is dominated by the term ∑=
:=1 W:drift: for all = = 1, 2, . . .. • Subsequently, by leveraging the machinery of martingale’s maximal inequalities and assumption (A2), which we present in ?? and using learning rates that respect (A3), we prove that with probability at least 1 − X, for any fixed confidence level X, ∑=:=1 W:noise: , which is a martingale, is also dominated by the term ∑= :=1 W:drift: for all = = 1, 2, . . . • We now define the open set of initial conditions Winit, which is of the form described in (10), with constant "init. By choosing4 "init ≥ " + ∑= :=1 W: (noise: + bias: ) − (2 − 2′) ∑= :=1 W: , for any
2′ < 2 and any = ≥ 1, since .1 ∈ Winit we have that .U,=+1 − .U∗ ,=+1 ≤ −" for all = ≥ 1. 3It is worth mentioning that the images of these open sets belong to neighborhoods of G∗, which are nested as "8 increases. 4such a "init exists since both the bias and the noise terms are dominated by the term −(2 − 2′) ∑= :=1 W: .
By substituting the inequality for "init in (11) we get .U,=+1 − .U∗ ,=+1 ≤ −" − 2′ ∑=
:=1 W: and convergence occurs as an immediate consequence; Indeed -U∗ ,= → 1, since whenever .U − .U∗ → −∞, it holds that each U ∈ A \ supp(G∗) becomes extinct i.e., -U → 0. Step 3. We now proceed to the delineation of the rates of convergence. Using the KKT conditions (??) combined with Eq. (11),Eq. (9) and the fact that .1 ∈ Winit we have
\ ′(-U,=+1) − \ ′(-U∗ ,=+1) = .U,=+1 − .U∗ ,=+1 ≤ −"init − 2 =∑
:=1 W: + =∑ :=1 W: (noise: + bias: )
Recall that \ is strong convex, or equivalently \ ′ is strictly increasing; by rearranging and substituting to the above inequality we get
\ ′(-U,=+1) ≤ \ ′(-U∗ ,=+1) − " − 2′ =∑
:=1 W: ≤ 3 − 2′ =∑ :=1 W: (12)
where 3 = −" + \ ′(1) and U ∈ A, U ≠ U∗. By aggregating over all U ∈ A, U ≠ U∗
‖G∗ − -=+1‖1 = 2(1 − -U∗ ,=+1) ≤ 2 ∑
U∈A≠U∗ q(3 − 2′ =∑ :=1 W: ) (13)
which indicates the rate of convergence and completes our proof. Remark 4.2. The bounds we provide are indeed sharp. To see this, consider a single-player game with two actions “0” and “1”, and payoffs D(0) = 0, D(1) = 1. Then, if e.g., FTRL is run with “full information” feedback, the probability that the player plays “1” at time C is exactly equal to
-C = 1 − q(2 − C∑
B=1 WBD(1)) = 1 − q(2 − C∑ B=1 WB)
where q is the rate function of Eq. (7) and 2 is an initialization constant. This simple derivation shows that MWU converges to the game’s (strict) equilibrium at a rate of exactly exp(−Θ(∑CB=1 WB)), whereas Euclidean methods achieve an equilibrium after a finite number of iterations – in particular, as soon as ∑C B=1 WB exceeds 2. It thus follows that the rates provided by Theorem 1 are, in general, unimprovable.

heading: 5 Numerical experiments
text: 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 q8 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 ??). 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 [37], 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. 1 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.
It is worth mentioning that the sharpness of the provided rates of Theorem 1 can clearly be observed in the list of the extensive numerical experiments we present in Fig. 1 and ??. In particular, the faster convergence rate of Euclidean algorithms is somewhat surprising since a regret-based viewpoint would suggest the use of entropic regularization (which, ceteris paribus, has much better regret guarantees) as optimal in this regard. Interestingly, however our analysis shows that a Euclidean
regularizer is much more suitable for achieving convergence to equilibrium in a game-theoretic setting. It is for this reason that we insisted on the comparison between entropic and Euclidean regularization in the simulations. (The Pigou network example of Fig. 1b is especially telling in this regard.)

heading: 6 Concluding remarks
text: A key take-away from this study is that the questions of regret minimization and convergence to Nash equilibrium are fundamentally different. In particular, much of the conventional wisdom that has been accrued for regret-minimization strategies (such as which regularizer to use, with what learning rate, etc.) ceases to apply when the figure of merit is convergence to an equilibrium. Because the only states that are stable under leader-following policies are the game’s strict Nash equilibria, the agents can be significantly more firm and confident in their choices, without compromising their final limit state; as a result, this extra degree of "confidence" allows for rates of convergence that are well beyond the operational envelope of regret minimization problems. We believe that this polar shift in perspective constitutes an important - and under-explored - issue in game-theoretic learning, and charting out its ramifications for multi-agent learning is a particularly fruitful direction for future research.
Acknowledgments and Disclosure of Funding
This research was partially supported by the COST Action CA16228 “European Network for Game Theory” (GAMENET) and the Onassis Foundation under Scholarship ID: F ZN 010-1/2017-2018. P. Mertikopoulos is also grateful for financial support 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), and the grant ALIAS (ANR-19-CE48-0018-01). E.V. VlatakisGkaragkounis is grateful to be supported by NSF grants CCF-1703925, CCF1763970, CCF-1814873, CCF1563155, and by the Simons Collaboration on Algorithms and Geometry.

Review summaries:
This paper proposes an abstraction of the online Follow-the-(Blank)-Leader type of methods they call Follow-the-Generalized-Leader (FTGL) that not only incorporates various regularization functions but also different feedback models. The authors provide a general convergence analysis for the family of methods over the problem of finding *strict* Nash equilibria in *finite* games. The main insight of the work is to claim that the convergence rate in this problem only depends on the regularization function used and *not* on the different feedback models, e.g. full information feedback vs bandit feedback.

This paper focused on normal-form games and proposed an algorithm framework called "follow the generalized leader" (FTGL). The framework covers the well-known "follow the regularized leader" methods as well as many other variants. The authors established FTGL's local convergence to strict Nash equilibria and further demonstrated that MWU converged linearly, while Euclidean projection methods converge within finite steps.

# Summary  The paper investigates the important issue of convergence in games.  A local convergence result is shown in N player general sum games, where local  means within a neighborhood of a strict Nash equilibria.  Convergence is attained with the proposed follow the generalized leader (FTGL)  framework, resembling the classical follow the regularized leader method from online learning. Futhermore convergence is shown under a set of assumptions  that includes various forms of feedback, from deterministic to bandit feedback. Connections with FTGL and other well-known algorithms are also made.