On the Rate of Convergence of Regularized Learning in Games: From Bandits and Uncertainty to Optimism and Beyond
Authors: Angeliki Giannou
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Panayotis Mertikopoulos
Venue: NeurIPS 2021 Poster (2021)
Keywords: Regularized Learning
Convergence
Rates
Strict Nash Equilibria
Follow the Regularized Leader
Tight bounds
Bandits
Stochastic Optimization

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.

The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond
Angeliki Giannou
Emmanouil V. Vlatakis-Gkaragkounii
Electrical and Computer Engineering National Technical University of Athens
Department of Computer Science
Columbia University
Athens, Greece
New York, NY 10025
gi glammouangelikk@@@aii.... com
emvlatakis@cs. columbia
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG &
Criteo AI Lab
panayotis, htwp:ttissmmrttkkouuossseeeeeeet fr
Abstract
In this paper, examine the convergence rate of wide range of regularized methods for learning in games. To that end, we propose a unified algorithmic tem- plate that call "follow the generalized leader" (FTGL), and which includes 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 bandit feedback. In this general setting, we show that FTGL algorithms converge locally to strict Nash equilibria at 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 linear convergence rate, while Euclidean projection methods converge to equilibrium in 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 go through any complex reasoning process to calculate 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 Nash [34, p. 21] constitutes the driving principle of game-theorete learning, and highlights one of the field's most central questions: Does learning with empirical observations lead Nash equilibrium? And, if so, at what rate?
These questions have been the forefront of game-theoretis 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- decision-making plays a major role. Still, any attempt to provide a positive answer these questions must wrestle with 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 theoretc 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 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 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 It achievable in an evolutionary setting. In the context of online learning (our paper's is main focus), a similar equivalence was obtained only recently [11, 15, 30], but it extends to the entire family of "follow the regularized leader" (FTRI. dynamics [41, 42), in both continuous [11, 30] and discrete time [15]. particular, [15] studied the convergence of discrete-time FTRL models in the presence of uncertainty, and proved a hihh-probaiility, 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 strict equilibrium, it provides no information about the speed of this convergence. 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 neighborhood of a Nash equilibrium.
Our paper aims to provide quantitative answers to these questions for 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 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, gracle-based, or bandit feedback.
In this general context, our main result may be summarized as follows. First, we introduce "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, d(x) = cxp(x) for entropic/ / logit choice models, whereas ((x) [x]+ for methods run with Euclidean projections. We then show that, with probability at least 1 - 8, the algorithm's local rate of convergence to a strict equilibrium x" is of the form ||X,, x'Il &(d d >x Ys), where yn is the method's learning rate and c, d are constants with c > O.
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 Fuclidean regularization attains convergence in finite number of iterations. From a regret-theoretic 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 '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 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", opti- mistic, or otherwise have been studied extensively 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 con- cerning the convergence of the "time-average" of the process [16, 24, 33, 35], and those focusing on the algorithm''s '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 corre- sponding min-max optimal rate is (1/TT) 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 typically not monotone; second, we examining the algorithm's rate of convergence strict equilibria, which are corner points of the problem's domain. This means that the geometry of the problem around strict equilibrium is fundamentally sharper than the geometry around solution of a generic monotone variational inequality, 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 's set of coarse correlated equilibria (CCE) by leveraging the algorithm's 's regret minimization properties, cf. [3, 4. 12, 13, 36, 44] and references therein. However, in addition to examining the algorithm's 's empirical average 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 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 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.
opposed to the induced day-to-day sequence of play these results
sub-geometric rate in potential games; our
2 Preliminaries
Finite games. Throughout this work we consider N N-players finite games in normal form. Formally, each player, indexed by i N = (1..... N). has finite set of pure strategies o; E A; = (1..... A;). and a payoff function u;: AA - I,, where A П1 Ai is the space of all pure strategy profiles. For concision, we will denote such game as a tuple r = A(N,A.
During play, players can also play mixed strategies, i.e., probability distributions x; X; = A(Ar) over their pure strategies. In this case, we will write Xia, for the probability that player i E N selects a; E Ar under xz. x (x1......Xy .NN) ) for the players' mixed strategy profile, and X == ΠI, X, for the set thereof. Finally, when focusing on the mixed strategy of a particular player E N, we will use the shorthand (xy;x-)) = .Y..............................
and, similarly, (a,, a.) for pure strategies.
Now, the expected payoff of player i in a mixed strategy profile x E X' is given by
n (x) (x)xxx))
Σ
[,(a)....,, .N) -1.. '.NN. ON
Σ
where ui(a)...., ONN) is the payoff of player i in the action profile = (a)..... .NN) E A. For posterity, we will also write Vin, (x) ui(a;;x-;) for the payoff that player i would have gotten by playing i E A; against the mixed strategy profile x-, of all other players. In this way, the mixed payoff vector of the i-th player can be seen as vector field v,: X - Y)- Ar which can be written in components as
vi(x) = (x))
Again, we will write v(x) (v) "o.).....((.... (x)) for the ensemble of payoff vectors of all players and y' = 1I; ) for the space of payoff vectors respectively. Finally, in slight abuse of notation, we will identify a; with the mixed strategy that assigns all probability to a;, and we will write vi(a)= (u, (a))aa) for the corresponding pure payoff vector.
Nash equilibrium. The most widely used solution concept in game theory that of a Nash cquilibrium i.c., a (possibly) mixed strategy profile x" e X that discourages unilateral deviations;
3

---

formally, x² E A' is said to be a Nash equilibrium of T if
u;(x') 2 (xxxx=4) for all x; 2; and all i N.
(NE)
The set of pure strategies supported at the equilibrium component x² E X; of each player will be denoted by supp(x;) = {ar Ai xia, > 0}. In turn, the size of the support of x" leads to the following dichotomy: x' is called pure if supp(x;) IlieN supp(x;) is singleton and mixed otherwise.
Finally, we will also say that a Nash equilibrium x² is strict if (NE) holds as strict inequality whenever Xi * x;; obviously, strict equilibria are also pure, but the converse need not hold. Striet Nash equilibria play key role in game theory because any unilateral deviation incurs strict loss to the deviating player; put differently, if xx 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 striet equilibria will play key role in the sequel.
3 Regularized learning
Throughout our paper, we will focus on a wide family of learning schemes that unfold as follows: At each stage n = 1,2..... every player maintains a "score vector" Yi,, E 3/ whose components indicate the player's propensity to play a given pure strategy. More formally, this is captured by player-specific "regularized choice" map Q1 )1- - X2 which outputs the player's s mixed strategy XI,, (Y,..) as function of Yr, (see below for detailed definition). Then, after selecting their actions and collecting their rewards, players also receive or otherwise construct an estimate Vi.n 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-roumt recursive rule
Xi, = (Yim,))
(FTGL)
Yi,++1 = Vi, + Yn Vin
where Yn 0 is a "learning rate" parameter such that Σn Yu = co. The terminology FTGL alludes to the widely known "follow the regularized leader" algorithm, which is, historically speaking, the parent-scheme of FTGL. The link regularization is provided by the method's choice map, which we detail below; the assumptions for the signal sequence Vi,, are provided right after.
3.1. The choice map. The guiding principle behind the definition of the players' choice maps 2: )1- - X,. i E N, as follows: Because the players' score variables Y., are assumed to represent an estimate of each strategy's s cumulative payoff over time, Qi is defined as a "regularized" version of the best-response correspondence y; H arg e x,). On that account, we will consider regularized best responses of the general form
Q,(y:) = arg max h;(x;)) xxEX
(3)
where h;: X - IR denotes the i-th player's regularization function.
For concreteness, we will focus on a class of decomposable regularizers of the form (x;x;) E,,EA, (x;x) where the so-called "kernel function" 8; [0. I] - R is assumed continuous on [0, IJ, twice differentiable on (0, 1], and strongly convex, i.e., inf in 6" > 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 multiplicativeeexpoeette weights). Perhaps the most common representative of regularization functions is given by the entropic kernel 6(x) = =x log i.., h(x;)) E,,,,A, Xia, log lig- This choice of regularizer is well-known to provide the logit choice map Aạ(y;) (exp(yia,)) en Eo exp(yia,). The resulting algorithm is known in the weights algorithm [1, 2, 29, 41, 45].
literature as the multiplicativelexpneeni
Example 3.2 (Fuclidean projection). Another popular regularizer is the quadratic penalty h(x)
Σa Xa /2, which yields the payoff projection map IT(y) = arg min lly - xx1 cf. [26, 46).
IIn this context, regularization be seen as means to reinforce exploration avoid committing prematurely given strategy.

---

Remark 3.1. Examples 3.1 and 3.2 are archetypes of fundamental dichotomy between regularization functions: in the former case, we have (0) -00, so becomes steep at the boundary of the player's s strategy space; in the later case, A is differentiable at O, so h 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" Vn contains information about the structure of the algorithm as well 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
Vn = r(x,) + Zn
(4)
for abstract error process Z, (Zi.) Tp be clear though, should stress that do not assume that Vn is directly correlated to or obtained by the chosen mixed strategy X 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 Zn Zn = Un + bns where
b B[ 1F.l and 1,
(5)
with Fn denoting the history of X, up to stage (inclusive). Notice that, since the feedback signal generated only after the player chooses a strategy, V, is not Fn-measurable in general. On this account, we will make the following blanket assumptions for the input signal sequence Vn;
1. Vanishing bias:
on converges uniformly to 0
co.
(A1)
2. Bounded variance: E || [F.) of for some q 2.
(A2)
In the above on is assumed to be a deterministic, stage-specific, and possibly increasing bound on the variance of the noise component Un; our precise assumptions for its growth (relative to bn 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 action based 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 n 1, 2, 2...... each player chooses pure strategy 0g,n E A, based on a mixed strategy XI.x E X, and subsequently observes the payoff vector
Vn. = (a = (.in;))ii))))a.... A
(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 bin 0) and Ui, v;(a,) - vi X,); hence:
.(A1) is trivially satisfied since bi,== = 0.
(A2) is again satisfied because || ||v;((n)) - (X,)ll s max max so Un has uniformly bounded moments for all 4 [1,
Model 2 (FTRL with bandit feedback). If the players only observe their realized rewards, they have construct model for V, based incomplete information. This 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 in Model 1 above, but the feedback signal sequence V, is now reconstructed by means of the importance-weighted weighted estimator
1 1 az) (a((a,)
Vian,
(IWE)
8iann
where &,,, = (.,),,),.. + + is the mixed strategy of the i-th player at stage Compared to X the player's actual sampling strategy now recalibrated by an explicit exploration parameter En - 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 X,, it will still be sampled with positive probability thanks to the mixing factor En-
5

---

Feedback
FTRI.
OpIFTRI.
EG/MP
Full information
bn =0
[|bn ll = O(ya)
[ball. O(ya)
Mn =0
Mn =0
Mn =0
bn
I |l O(yn)
b -(yn)
Oracle-based
Mn O(1)
M₁ = O(1)
M, O(1)
Bandit (payoff-based)
[|b,, ((6a)
I|b I|- O(En)
bbb (EEn)
M, ((1/En)
Mn = ((1/sn)
M, ((1/En)
Table 1: Recasting different online learning algorithms within the general template of (FTGL).
The importance-weighhee estimator (IWE) estimator may be seen as a special case of the model (4) with Ui,n Vi.n (8.)) and b vz( - vi (X)). Both assumptions (A1),AA2) are again satisfied; indeed:
For (Al): A standard calculation performed in ?? reveals that [|b = O(.n). Thus our assumption is satisfied since E, - 0.
For (A2): Again standard calculation presented in ?? reveals that [[V vy = O(1/sn) and thus the noise has bounded moments, on = (1/Ea) for all E [1,o0].
Model 3 (OptFTRL with oracle-based feedback). Following Rakhlin and Sridharan [40], the so- called "optimistic" variant FTRL given by the recursive formula:
Pr.m = Vi. + Yn Vin-1
X.,, (Prmn) Yint1
Vin + Yn Vi..
(OptFTRL)
In the above the payoff signal Vi.., which depends the state Xn is generated follows: at each round 1, 2. every player i E N picks an action ai,n A, based on Xi., E X and observes the pure payoff vector (a,,) (u,(aa;-t,)))a
At first glance. seems difficult reconcile the above update structure with that of (FTGL); however, it is indeed possible to integrate (OptFTRL) within (FTGL. by considering the auxiliary states X,, Q(Y,) (which are never played and are only used here for the analysis).
Indeed, each player's 's input signal is a special case of (4) with payoff feedback Vi,, (a)),, zero- mean noise U₁,, v:(ax) vi (x,) and bias bi, v; (x(X)) v; (X,) that satisfy both the assumptions (A1),(A)). more detail, we have:
For (A1): ||ا = (X,) (x.)l 0ly)), which goes uniformly to 0 whenever 7n - 0. For (A2): ||U, = I|v;(a,)) (X,)ll S 2 (l) and thus the noise has bounded moments for all E [o]
Remark 3.2. Based on the structure of the aforementioned algorithms, it is easy to check that we capture a-fortiori the model of full-information payoff signal; for more complete account of the different algorithms and feedback models see Table 1.
4 Analysis & Results
We are now in position to state 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 equi- libria can be asymptotically stable under FTRL [11, 15], so they are the only reasonable candidates to consider when examining the rate of convergence of regularized learning algorithm." 2
As sidenote, we should remark here that FTGL. also contains the optimistic FTRI. algorithm, which does converge to mixed Nash equilibria in bilinear zero-sum games with perfect, determinivtic feedback [16, 25, 32). At first glance, this would seem to contradict the results of [11, 15J. but one needs to bear in mind that the convergenee of (OptFTRL) to mixed equilibria only occurs in settings with perfect information (i.c., V,, v ((X)) for all 1, 2, In the presence of uncertainty, this convergence is destroyed| [7, 22], there is contradiction with the results of [15]. Because are primarily interested in Jearning with limited information and/or under uncertainty. will not this somewhat fragile

---

To proceed, we will need one technical assumption linking the learning rate of (FTGL) and the bias/variance parameters the driving feedback sequence V,, This is as follows:
The sequence on == Σk= V oK
is summable for some B < 1.
(A3)
[Σ yx] 1+8g/2
Assumption (A3) imposes a growth condition on the method's learning rate relative to the bias and variance parameters of the input signal sequence Vn, 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 wide range of the player-chosen parameters Yn (and en 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 introduce concerns the players' choice of regularizer: clearly, since propensities are transformed to strategies via each player's 's individual choice map Qr: 3 - X; it stands to reason that the underlying regularization function h plays major role in the method's rate of convergence. Indeed, given an update of the form Yn < Yy +n Vn, the method's strategy variable will move forward as Xn+1 Xn + yn (VVVV, ((r)), where JQ denotes the Jacobian matrix of Q. Thus, to leading order in Yn, the update Xn+1 < Xn is dominated by the first derivatives of Q.
By a relatively straightforward application of the Legendre identity from convex analysis (Q =(hh in our context; below for a precise statement), this rate of change is related to the inverse mapping of the derivative each 0; (the kernel of the underlying regularizer). Motivated by this observation, we introduce below the algorithm's so-called rate function:
(1))) (0))'(1) (r)
if 0,(0',
otherwise.
The definition of the rate function & captures the sensitivity of the choice map Q in a very precise way: If the score difference corresponding to two pure strategies a, E Ai grows yB YYo for some > O, 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 's choice function Q and & acts as a "transfer" function in this regard. Specifically,
show in detail later, we have xa o( (1)) i.e., & determines the rate which Xa 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 x* be a strict Nash equilibrium of I, and fix some confidence level ō > 0. If Assumptions (A1)-(A3) hold, there exists unbounded open set of initial conditions Wmit y and constants di, of with c/ > 0 such that, if Y1 E Wina. we have:
1. Xn converges to x" with probability at least 1- Conditioned on the above, the rate of convergence for each player i E N is given by
| - x1,11 2 E.,,AA $1 $1(4:
c E 7k).
n
(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., 0; is differentiable at 0), Xn converges to x" in a finite number of iterations.
Corollary 2. Suppose that FTRL is run with oracle- based feedback per Model I and a learning rate of the form Yn x 1/nP, p E [0. 1]. Then the conclusion of Theorem holds.
Corollary 3. Suppose that FTRL is with bandit feedback per Model 2, a learning rate of the form Yn x 1/nP, E [0, and a mixing parameter En oe 1/n", r E (0. 1/2). Then the conclusion of Theorem holds.
Remark 4.1. We stress out here that for all the bandit-feedback derived results, the convergence rates refer to Xi, instead of the explicit exporation term & whose rate is always dominated by the mixing parameter En.
Corollary 4. Suppose that Optimistic FTRL is run with oracle-based feedback as per Model 3 and learning rate of the form Yn 1/nP, p (0. 1]. Then the conclusion of Theorem I holds.
7

---

ALGORITHM
KERNEL. 0(x)
RATE ((-y)
Multiplicative Weight Updates Projection Gradient Deseent
x logx
exp(-y)
x²/2
-y
Inverse Updates q g-Replicator,ps0
log
-1/y 14 +1 (1-))))))
[1 q)1 ((x (xxxx)
Table 2: Regularizers & correppiniigg rates.
More generally, we show in the supplement that the conclusion of Theorem holds for all algorithms and feedback models presented in Table 1: in all cases therein, players can employ step-size policies of the form Yn < 1/n², E [O. 1], and a mixing parameter ε, < 1/n" with r E (0, 1/2) for the bandit models. The only case that does not follow as an immediate corollary of Theorem I 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 The- orem I relies 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 h; in the solution of the convex constrained optimization problem, that x = Qi(y) induces, is necessary to derive the aforementioned generic rates. Below we provide 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 's strategy, ensures convergence properties for strict Nash equilibria. More precisely, an immediate implication of (NE) that there exist neighborhood of xx and constants CN....,CN such that
Via; Vior (x) 2 c, for all x E U and or # 07, E A
In other words, in the neighborhood U the payoff of the equilibrium's 's strategy strictly dominates all other strategies' payoft's 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 C1....,CN CN and MI...., MN for which (9) holds such that IIEN (.WM S U, where WM, are open sets of the form"
WM, (Y; : Yio; Yin, M; for all a; # a,,a; a; E for M, 0, E Step 2. We now focus on one player A and drop the index altogether. First we prove that there exists an open set of initializations Wmi of (FTGL), for which with arbitrary high probability the dual variable (Yx)eeN never exits WM and thus its image remains in the desired neighborhood U. We start by writing the score differences between each pure strategy a E A and a' supp(x')
(10)
Y Ya.n+1 - Yor,n n+1 = Yaa. - Yor, Σ
Yk (drifty + noise + biask)
(11)
k=1
where drift,- = Va - Vor (Xx), noise; = =Ua,k - UU &.. bias; = bb.k ba
R. We will prove by induction our forward-invariant statement; let Yx E WM and thus Xx E l for all k I.....n then
By (9) we have Σx=1 drift, I cc -x=1 7& for all k == I.....n. n.
By the triangle inequality and (A1), the term Σx=1 yy biasy dominated by the term ΣT=1 Ya drift, for all π = 1, 2,
Subsequently, by leveraging the machinery of martingale's maximal inequalities and assumption (A2), which we present ?? and using learning rates that respect (A3), we prove that with probability at least - 6, for any fixed confidence level 6, >x yonoise,, which is a martingale, is also dominated by the term Σ dædrift for all 1,2....
We now define the open set of initial conditions Winits which is of the form described in (10), with constant Minit By choosing* Mini Z M + Σカ= Yt (noise + bias;) - (c - c') Σt=1 Yk. for any << and any n 1, since Y1 Winh we have that Y Ya, v+1 S MM for all 2
It is worth mentioning that the images of these open sets belong neighborhoods of x", which are nested as M, increases. such Miit exists since both the bias and the noise terms dominated by the term ((c c') Σi_ Yk.
8

---

By substituting the inequality for Mun in (11) we Ya.+1 Yar I -M -M c' Et= and convergence occurs as an immediate consequence; Indeed X - 1, since whenever Ya Yo- -co, it holds that each Step We now proceed the delineation of the rates convergence. Using the KKT conditions (??) combined with Eq. (1 (11).qq. (9) and the fact that Y1 E Wint we have
A supp(x") becomes extinct i.e., X O.
('( - (Xaa = Ya, - Yar.n+ S Miit
Σ Yk +
Σ Yk (noisex biask)
Recall that is strong convex, or equivalently 6' is strictly increasing: by rearranging and substituting to the above inequality we get
a
0' da(aan++1) S (X M Σ S d - Σn
(12)
where d -M + + (1) and a E a, a a", By aggregating over all a A, a #
||x - X 11 2(1 m+1) 2
Σ s(d c'
Σ
(13)
acAAO
k=1
which indicates the rate of convergence and completes our proof. Remark 4.2. The bounds we provide are indeed sharp. To see this, consider single-player game with two actions "O" and "1", and payoffs u(0) 0, u(1) 1. Then, if e.g., FTRL is run with "full
information" feedback, the probability that the player plays "1 time is exactly equal
=1 ΣT.(() =1 d(c Σnd
where & is the rate function of Eq. (7) and is an initialization constant. This simple derivation shows that MWU converges to the game's 's (strict) equilibrium at rate of exactly exp(-0(2,, Ys)), whereas Euclidean methods achieve equilibrium after finite number of iterations in particular, as soon as Σ Ys exceeds c. thus follows that the rates provided by Theorem are, in general, unimprovable.
5 Numerical experiments
In this section perform series of numerical experiments validate 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 different feedback models and algorithmic variants of (FTGL).
To do this, 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 well. This game exhibits two striet Nash equilibria and mixed equilibrium (for the exact definition, see ??). We then seek to experimentally study the performance (FTGL) while the number of the players scales up. To do this game [37], where N units of traffic (e.g., rush-hour drivers) leave from O (origin) to D (destination) the same time and each driver has the same dominant pure strategy/path for this trip. Accordingly
the atomic version of classical Pigou's 's congestion
to Table 2 the decay rate for the entropic regularization is exponential while for the case of euclidean linear, which indeed yield linear and constant-ting convergence Fig. illustrates.
We defer a detailed exposition of various configurations with different step-sizes, alternative dis- cretization methods like MirrorProx and Exarinrr and feedback models with the presence (or not) of extra wtlatytaaled//iooomggauusss
noise again to the paper's supplement.
It is worth mentioning that the sharpness of the provided rates of Theorem can clearly be observed the list the extensive numerical experiments we present in Fig. and ??. In particular, the faster convergence rate of Euclidean algorithms is somewhat surprising since 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 analysis shows that Euclidean

---

Xdh.
Netoore I
FIR-MAUU crade
ITEL MELLMMM bands
FTRL-MAU-tedd
ITBL-- ands
FTRL- kands
10-
F188-1200de
MVLloads
GTTTL maile
OniFTRLMWUlanek
QyeTTaL kynid
O (oodR
931
12:01
300
(a) Battle of the Sexes
(b) Pigou Network
Figure 1: For the Battle of the Sexes experiment, we initialize uniformly randomly our executions from
Yinir E [-1, x [-1. and examine the instantiations of Model 1-3 using constant-step size and exploration rate En In. For the Pigou's 's game, our setup includes two alternative disjoint paths for N 1000 drivers. The first path has linear latency & (x) x/N while the second one has constant unit congestion, (x where denotes the population the drivers that uses the corresponding path.
regularizer is much more suitable for achieving convergence to equilibrium in a game -hee-theo setting. 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.)
Concluding remarks
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 sgreetminimizztionn strategies (such as which regularizer to use, with what learning rate, etc.) ceases apply when the figure of merit is convergence to equilibrium. Because the only states that are stable under leader-following policies are the game's 's strict Nash equilibria, the agents be significantly more firm and confident in their choices, without compromising their final limit state; as a result, this extra degree "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-theoretie learning, and charting out its ramifications for multi-agent learning is 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 100-1/2017-2013 P. Mertikopoulos also grateful for financial support by the French National Research Ageney (ANR) in the framework of the "Investissements d' avenir" program 1ANR-15-IDEX--
the LabEx PERSYVAL (ANR- ABX-0002--01, MAAI@Grenole Alpes (ANR-194 (ANR-19-P3IA--- 19-P31A-0003), and the grant ALIAS (ANR-19-CE48-00) 8-00). E.V. Vlatakis- Gkaragkounis is grateful be supported by NSF grants CCF-1703923 CCF1763970, CCF- CCF-181455 1814873, CCF. 1563155, and by the Simons Collaboration on Algorithms and Geometry.
References
[1] Sanjecv Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta-algorithm and applications. Theory of Computing. 8(1::121-144, 2012.
[2] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposison on Foundations of Computer Science, 1995.
[3] Avrim Blum and Yishay Mansour. Learning, regret minimization, and equilibria. In Noam Nisan, Tim Roughgarden, Éva Tardos, and Vaziruni, editors, Algorithmic Game Theory, chapter Cambridge University Press, 2007.
10

---

[4] Avrim Blum. Eyal Even-Dar, and Katrina Ligett. Routing without regret: convergence to Nash equilibria of regret- minimizing in routing games. In PODC '06: Proceedings of the 25th annual ACM SIGACT-SIGOPS symposium on Principles Distributed Computing, pages 45-52, 2006.
[5] Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret unalysis stochastic and noustochastic multi-armes bandit problems. Foundations and Trends Machine Learning. 5(1):1-122, 2012.
[6] Nicold Besa-Biacchi and Gáhor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[7] Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacuste-Julien, Reducing noise in GAN training with variance reduced extragradient. In NewrlPS 19; Proceedings of the 33rd International Conference on Neural
Information Processing Systems, 2019.
[8] Johamne Cohen, Amélie Héliou, and Panayotis Mertikupoulos. Learning with bandit feedback in potential games. In NIS '17: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
[9] Constantinos Daskalakis and Toannis Panageas. Last-iterate convergence: 7ero-sum games and constrained min-max optimization. In ITCS '9: Proceedings of the 10th Conference on Innovations in Theoretical Computer Science, 2019.
[10] Constantinos Duskalakis. Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR 18: Proceedings of the 2018 International Conference Learning Repre Representattons, 2018
[11] Lampros Flokas, Emmanouil Vasileios Vlatakis- Viatakis-Gkaragkoumm Gkaragkounis, Thanasis Liancas, Panayotis Mertikopoulos, and Georgios Piliouras. No-regret learning and mixed Nash equilibria: They do not mix. In NeurlPS '20: Proceedings of the 34th International Conference Neural Information Processing Systems, 2020.
[12) Dcan Foster and Rakesh V. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21
(1):40-55, October 1997.
[13] Yoav Freund and Robert E. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79-103, 1999.
[14] Drew Fudenherg and Jean Timole. Game Theory. The MIT Press, 1991.
[15] Angeliki Giannou, Emumanouil Vasileios Vlatakis-Gkaragkkon Gkaragkounis, and Panayotis Mertikopoulus. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In COLT '21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[16] Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. In ICLR '1: Proceedings of the 2019 International Conference on Learning Representations, 2019.
[17] Noah Golowich, Sarath Pattathil, and Constantinos Duskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In NeurlPS '20: Proceedings the 34th International Conference Neural Information
Processing Systems, 2020.
[18] Ian J. Goodfellow, Jean Pouget-Abadie, Mchdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Auron Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS '14: Priceedings of the 28th International Conference on Neural Information Processing Systems, 2014.
[19] Sergiu Hart and Andreu Mus-Colell. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review, 1835)11830-1866 2003.
[20] Josef Hofbauer and Karl Sigmund. Evolutionary game dynamics. Bulletin of the American Mathemattical Society, 40(4):
479-519, July 2003.
[21] Yu-Guan Hsich, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradicnt methods. In NeurlPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 6936-6946 2019.
[22] Yu-Guan Hsich, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conser- vatively: Stochastic extragradient methods with variable stepsize scaling. In NewrlPS '20; Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[23] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In COLT '21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[24] Anatoli Juditsky, Arkadi Semen Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochostic Systems, 1(1)11-58, 2011.
[25] M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonom. Mat. Metody, 12: 747-756, 1976.
[26] Ratul Lahkar and William II, Sandholm. The projection dynamic and the geometry of pupulation games. Games and Economic Behavior, 64:565-590, 2008.
[27] Tor Lattimore and Csaba Szcpesvári. Bandit Algoritlums. Cambridge University Press, Cambridge, UK, 2020.
[28] Tianyi Lin, Zhengyuan Zhou, Panayntis Mertikopoulos, and Michael Jordan. Finite-time last-iterate convergence for multi-agent learning in games. In JCML '20: Proceedings of the 37th International Conference on Machine Learning, 2020.
[29] Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108(2);
212-261, 1994.
11

---

[30] Panayotis Mertikopoulos and William H. Sandholm. Learning in games via reinforcement and regularization. Mathemar- ics of Operations Research, 114421297-1324, November 2016.
[31] Panayotis Mertikopoulos and Zhengyuan 7hou. Learning games with continuous action sets and unknown payoff' functions. Mathematical Programming, 173(1 (731-)):45--001 January 2019.
[32] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mitror descent saddle point problems: Going the extra (gradient) mile. In ICLR '19: Proceedings of 2019 International Conference Learning Representations, 2019.
[33] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) optimistic gradient and extra-gr gradient methods smooth convex-concave saddle point problems. https://arxiv.orgg /1906. 011..5.11p.. 2019.
[34] John Nash. Non-cooperative gumes. PhD thesis, Princeton University. 1950.
[35] Arkadi Semen Nemirovski. Prox-method with rate convergence ((1/r) for variational incqualities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15 (1):229-251, 251, 2004.
[36] Noam Nisan, Tim Roughgarden, Eva Tardos, and V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, 2007.
[37] Arthur Cocil Pigou. The Economics of Welfäre. Macmillan, London, U'K, 1920.
[38] Leonid Denisovich Popov. A modification of the Arrow-Hurwicz method for scarch of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):445848, 1980.
[39] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In COLT 11: Proceedings of the
26th Annual Conference on Learning Theory, 2013.
[40] A Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In NIPS '13: Proceedings of the 27th International Conference on Neural Information Processing Systems, 2013.
[41] Shai Shalev-Shwarta. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4 (2:107-114,, 2011.
[42] Shai Shalev-Shwartz and Yoram Singer. Convex repeated games and Fenchel duality. In NIPS' 06: Proceedings of the 19th Annual Conference on Neural Information Processing Systems, pages 1275-1272. MIT Press, 2006.
[43] Yoav Shoham and Kevin Leyton-Brown Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.
[44] Vasilis Syrgkanis, Alckh Agarwal, Haipeng and Robert E. Schapire. Fast convergence of regularized learning games. NIPS 11: Proceedings of the 29th International Conference Neural Information Processing Systems, pages 2989-2997, 2015.
[45] Vladimir Vovk. Aggregating strategies, COLT '90: Proceedings of the 3rd Workshop on Computational Learning Theory, pages 371-383, 1990.
[46] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. ICML '03; Proceedings of 20th International Conference on Machine Learning, pages 928-936, 2003.
12


Reviews:
[{"review_id": "yumGhPrnlhS", "reviewer": "Reviewer_mbqJ", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This submission was an interesting read given its somewhat surprising conclusions. It is clearly written and easy to follow. However, it seems like the authors aim to claim two contributions (this might not be true): (i) abstracting FTRL into FTGL and giving convergence analysis on a specific problem; (ii) new convergence results for the specific problem of strict Nash equilibria in finite games. I believe (i) is unnecessarily abstract and confusing for two reasons: first, we know how to do FTRL with different regularization functions (Bregman divergences as potential functions), so the fact that the regularization function is written more generally is not a contribution; second, it is not quite clear what the exact assumptions are w.r.t. different feedback models when they are all lumped in together into one.\n\nMore importantly, if the main contribution of this paper is showing new convergence results for finding strict Nash equilibria in finite games, then the authors should pick the specific algorithm(s) they use, prove and provide their convergence results, and draw conclusions. The unified framework might be appealing and seem elegant, but in this case, in my opinion, it doesn't contribute anything and obfuscates from the main problem at hand. In particular, the studied problem seems amenable to the Euclidean $l_2$ norm regularization given the geometry around the strict equilibria. The result suggests convergence to the desired points in a finite number of steps -- since the problem is solved in finite number of steps, for comparison one must look at the exact number of steps then instead of bringing in MW as another method to compare to. Now given $l_2$ regularization, is there any convergence rate difference between various feedback models, e.g. full information and bandit? I would be very surprised if not. And note that even if in your analysis you get identical rates, you cannot make any claims about these rates without any lower bounds -- maybe with your analysis they have the same rate but it's possible to do things much faster with full information. This same logic should apply to experiments, get rid of MW experiments, make the claim that there is convergence in finite number of steps, and compare the exact number for different methods with $l_2$ regularization.\n\nOverall, the paper has interesting ideas, insights, and results, but, as presented, I don't think it's ready for publication. Weak reject.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The societal impact was adequately addressed. I would like to see more discussion around the limitations of this work. The authors could answer questions such as how much this exact problem has been studied, what results were known for it, and what can be done for future work (or what should be investigated).", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "j0Sr0RWGHs", "reviewer": "Reviewer_4S9g", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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. In particular, the FTGL method updates a score vector with the payoff observed in every iteration and the strategy is induced by the score vector via a choice map function. This include well-known MWU method as a special case.\n\nThe main result states that as long as the score vector lies in a proper initialization zone, FTGL methods are guaranteed to converge. The convergence rate depends on the choice of step size as well as the choice map. In particular, MWU with constant step size converges linearly and Euclidean projection methods converges within finite steps.\n\nWhile the results appear to be new, the fast convergence does not seem to be surprising under the assumption of strict Nash equilibrium and initialization condition. Actually the assumptions may have revealed extra information: as long as $\\\\|X_i - x_i^*\\\\|_\\{1} < 1$, one can immediately recover $x_i^\\*$ by simply picking the action with largest probability in $X_i$. Therefore, providing some discussion on how large  $W_\\{init}$ is would make the result more solid. Showing $W_\\{init}$ is unbounded alone doesn't necessarily leads to larger $\\\\{X_\\{i, 1} = Q_i(Y_\\{i,1}), Y_1 \\in Q_\\{init}\\\\}$, as scaling (or shifting, depending on the choice map) the score vector leads to exactly the same strategy. \n\nTypos:\n\nline 246, \"thatthat\";\n\nline 248, \"consdier\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "LMfXN8OIlw", "reviewer": "Reviewer_FAhb", "summary": "# Summary\n\nThe paper investigates the important issue of convergence in games. \nA local convergence result is shown in N player general sum games, where local \nmeans within a neighborhood of a strict Nash equilibria. \nConvergence is attained with the proposed follow the generalized leader (FTGL) \nframework, resembling the classical follow the regularized leader method\nfrom online learning. Futhermore convergence is shown under a set of assumptions \nthat includes various forms of feedback, from deterministic to bandit feedback.\nConnections with FTGL and other well-known algorithms are also made. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n# Main Review\n\n## Summary of Review\n\nOverall the paper is well written with significant contributions to the field of learning in games. \nIn particular, although only local convergence to a strict Nash equilibrium is considered, \na convergence result for a large family of algorithms such as FTGL in general sum games is likely to be impactful. \nFurthermore, having a unified framework for studying various forms feedback (from deterministic to unbiased to bandit) and showing convergence is of great value. \nI would expect that similar techniques might be useful for examining stronger convergence results if more assumptions are made on the game such as two-player zero-sum.\n\nI do however have some issues regarding the discussion of related work and the claimed connections of FTGL with other well-known algorithms (see clarity section below).\n\n\n## Originality\n\nI believe the results to be novel see summary above.\n\n## Quality\n\nThe paper is complete in its investigation of local convergence for the FTGL method\nand results are supported with extensive proofs, using well-known tools from probability theory and convex analysis. \nI would like to see more clarification of the fixed stepsize result referred to in lines 295-298. It is difficult to see where this result is located in Appendix C, it would be better to include a more exact pointer.\nThis result is important because other related works show convergence for a fixed stepsize [2]. \n\n## Clarity\nI believe the paper to be well-written overall, however, improvements can be made with respect to discussion of related work, and connections between FTGL and other methods.\n\n### Discussion of related work\n\nComparisons of related work are made in the related work section and throughout the paper.\nThere is an emphasis on stohcastic vs determinstic (See footnote 2 for example). It is claimed that a lot the related works depend on deterministic feedback for convergence as opposed to this paper studying a more general feedback model for which results from the related work do not apply (expect the works of [1] for example). \nI too believe this statement to be true, however, I believe an important main driver of convergence in a lot of the works cited in these cases like those in footnote 2 or like [2], is not just the fact that it is determinstic but also because the games are monotone and Lipschitz smooth (don't need strongly monotone in the most general settings). But it should be mentioned that there is a significant important distinction in the quality of the results attained in these works, that they are global convergence guarantees. \nTake the original extra gradient method from [3] for example, it is shown that the procedure will converge to an equilibrium without assuming starting in a neighbourhood of an equilibrium. \nOr take for example an even closer related work [2], where convergence of the optimistic multiplicative weights algorithm (an example of optimistic follow the regularized leader) is shown to converge in zero-sum matrix games with unique equilibrium if a sufficiently small constant stepsize is used.\nTherefore, I would suggest to emphasize that tho the paper investigates convergence in general sum games with possibly stochastic feedback the convergence results are local while a lot of the related works focus on global convergence with determistic feedback; except perhaps for the mentioned related work [1] where I believe global convergence is shown in potential games even with bandit feedback.\n\n### Connections between FTGL and other methods\n\n#### FTGL vs FTRL\nAlthough FTGL resembles FTRL I believe it is different in a fundamental way by how the stepsizes are used. FTRL with a sequence stepsizes is generally understood to mean that at a each round when a stepsize is selected it is applied to all the past feedback vectors in the same way (see for example [4]). This is different that FTGL unless constant stepsizes are used.\n\n#### FTGL and Mirror Prox or Mirror Descent\n\nI believe that FTGL is more closely related to FTRL than mirror descent since it maintains an average in the dual space $Y_{i,n}$ and then projects back to the primal space when needed. This setup can sometimes be equivalent to mirror descent  (for example see [4]), but without further assumptions this approach is different \nthan mirror descent (projected gradient descent as an example) which maps the primal iterate to the dual space before taking\na gradient step. For example in the case of example 3.1 they are equivalent but in the case of example 3.2 they are not. Therefore, I do not see how the FTGL framework can capture mirror prox in general (which can be written as optimistic mirror descent [5]). I see there are discussions in the appendix to justify this connection, however, I do not believe mirror prox or extra gradient can be recovered if one averages in the dual space like FTGL. \n\n\n\n## Significance\nSee summary above.\n\n## Other minor suggested improvements\n\n* I think there is a typo on line 134 $supp(x_i^\\ast)$ should be $supp(x^\\ast)$ ?\n* What is the value of $q$ in assumption A3? is it the same $q$ as in A2?\n* Why is it assumed that $h_i$ is decomposable? For example do you expect $h_i(x_i) = <x_i, M x_i>$ the matrix norm for an arbitrary positive definite matrix (hence $h_i$ is strongly convex) to also work? what is the difficulty when we cannot decompose $h_i$? A discussion would be nice.\n* On remarkk 3.1. This remark seems to be closely related to the Legendre assumption that is commonly used when defining mirror descent in online learning, see for example [4]. This might be interesting to mention or investigate.\n* On model 3 for OptFTRL. This perspective suggests that optimism is a nuissance to deal with since it contributes to bias. However, in online learning optimism improves regret bounds for predicatble problems and so helps with convergence [5,6].\nA comment on these two different perspectives would be interesting.\n\n\nReferences\n\n1. Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In\nNIPS ’17: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.\n\n2. Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max\noptimization. In ITCS ’19: Proceedings of the 10th Conference on Innovations in Theoretical Computer Science, 2019.\n\n3. G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Èkonom. i Mat. Metody, 12:\n747–756, 1976.\n\n4. Orabona, F., 2019. A modern introduction to online learning. arXiv preprint arXiv:1912.13213.\n\n5. Rakhlin, S. and Sridharan, K., 2013. Optimization, Learning, and Games with Predictable Sequences. Advances in Neural Information Processing Systems, 26, pp.3066-3074.\n\n6. Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in\ngames. In NIPS ’15: Proceedings of the 29th International Conference on Neural Information Processing Systems, pages\n2989–2997, 2015.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed throughout the paper. There is not discussion of potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After discussions, reviewers agree that this paper makes solid contribution for 
advancing the understanding of the convergence rate for regularized learning in games.
Please do incorporate all the suggestions/discussions from the reviews into the final version.
Decision: Accept (Poster)