Accelerated Regularized Learning in Finite N-Person Games
Authors: Kyriakos Lotidis
Angeliki Giannou
Panayotis Mertikopoulos
Nicholas Bambos
Venue: NeurIPS 2024 poster (2024)
Keywords: game theory
Nash equilibrium
Nesterov's acceleration
regularized learning
Primary area: algorithmic_game_theory

Abstract: Motivated by the success of Nesterov's accelerated gradient algorithm for convex minimization problems, we examine whether it is possible to achieve similar performance gains in the context of online learning in games.
To that end, we introduce a family of accelerated learning methods, which we call “follow the accelerated leader” (FTXL), and which incorporates the use of momentum within the general framework of regularized learning - and, in particular, the exponential / multiplicative weights algorithm and its variants.
Drawing inspiration and techniques from the continuous-time analysis of Nesterov's algorithm, we show that FTXL converges locally to strict Nash equilibria at a superlinear rate, achieving in this way an exponential speed-up over vanilla regularized learning methods (which, by comparison, converge to strict equilibria at a geometric, linear rate).
Importantly, the FTXL maintains its superlinear convergence rate in a broad range of feedback structures, from deterministic, full information models to stochastic, realization-based ones, and even bandit, payoff-based information, where players are only able to observe their individual realized payoffs.

Accelerated Regularized Learning in Finite N-Person Games
Kyriakos Lotidis
Angeliki Giannou University of Wisconsin- Madison giannou@wis sc. edu
Stanford University kloti tidii a@stanford..ccmmmm edu
Panayotis Mertikopoulos
Nicholas Bambos Stanford University
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP
LIG 38000 Grenoble, France
bambos@stanford edu
panayotis. wwttsssiooooooooolsiioooo. fr
Abstract
Motivated by the success of Nesterov's accelerated gradient algorithm for con- vex minimization problems, we examine whether it possible to achieve similar performance gains in the context of online learning in games. To that end, we introduce a family of accelerated learning methods, which we call "follow the accelerated leader" (FTXL), and which incorporates the use of momentum within the general framework of regularized learning- and, in particular, the exponen- tial/ / multiplicative weights algorithm and its variants. Drawing inspiration and techniques from the continuous time analysis of Nesterov's s algorithm, we show that FTXL converges locally to strict Nash equilibria superlinear rate, achiev- ing in this way an exponential speed-up over vanilla regularized learning methods (which, by comparison, converge to strict equilibria at geometric, linear rate). Importantly, FTXL maintains its superlinear convergence rate in a broad range of feedback structures, from deterministic, full information models stochastic, realization-based ones, and even when run with bandit, payoff- information, where players are only able observe their individual realized payoffs.
1 Introduction
One of the most important milestones in convex optimization was Nesterov's accelerated gradient (NAG) algorithm, as proposed by Nesterov [38] in 1983. The groundbreaking achievement of Nesterov's 's algorithm was that it attained an (1//T²) rate of convergence in Lipschitz smooth convex minimization problems, thus bridging decades-old gap between the (1ITT) convergence rate of ordinary gradient descent and the corresponding (21/7)) lower bound for said class [37]. In this way. Nesterov's accelerated gradient algorithm opened the door acceleration in optimization, leading in turn to wide range of other, likewise influential schemes such as FISTA and its variants [3] and jumpstarting a vigorous field of research that remains extremely active to this day.
Somewhat peculiarly, despite the great success that NAG has enjoyed in all fields where optimization plays major role -and, and, in particular, machine learning and data science its use has percolated to the adjoining field of game theory as suitable algorithm for learning Nash equilibria. Historically, the reasons for this are easy to explain: despite intense scrutiny by the community and an extensive corpus of literature dedicated to deconstructing the algorithm's guarantees, NAG's update structure remains quite opaque and, to certain extent, mysterious. Because of this, Nesterov's 's algorithm could not be considered as plausible learning scheme that could be employed by boundedly rational human agents involved in repeated game. Given that this was the predominant tenet in economic thought
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

at the time, the use of Nesterov's 's algorithm in a game game-the context has not been extensively explored, the best of our knowledge.
On the other hand, as far as applications to machine learning and artificial intelligence are concerned, the focus on human agents is no longer a limiting factor. In most current and emerging applications of game-theoretic learning from multi-agent reinforcement learning to adversarial models in machine learning the learning agents are algorithms whose computational capacity only limited by the device on which they are deployed. In view of this, our paper seeks to answer the following question:
Can Nesterov's 's accelerated gradient scheme be deployed in a game-theoretie setting? And, if so, is it possible to achieve similar performance gains as in convex optimization?
Our contributions in the context of related work. The answer to the above questions is not easy to guess. On the one hand, given that game theory and convex optimization are fundamentally different fields, a reasonable guess would be "no" after all, finding Nash equilibrium is PPAD-complet problem [9], whereas convex minimization problems are solvable in polynomial time [7]. On the other, since in the context of online learning each player would have every incentive to use the most efficient unilateral optimization algorithm at their disposal, the use of NAG methods cannot be easily discarded from an algorithmic viewpoint.
Our paper examines it is possible to obtain even a partially positive answer to the above question concerning the application of Nesterov's 's accelerated gradients techniques to learning in games. We focus throughout on the class of finite N-person games where, due to the individual concavity of the players' payoff functions, the convergence landscape of online learning in games is relatively well-understood at least, compared to non-concave games. particular, it is known that regularized learning algorithms- such as "follow the regularized leader" (FTRL) and its variants converge locally to strict Nash equilibria at a geometric rate [18], and striet equilibria are the only locally stable and attracting limit points of regularized learning in the presence of randomness and/or uncertainty [11, 17, 23). In this regard, we pose the question of (i) whether regularized learning schemes like FTRL can be accelerated; and (ii) whether the above properties are enhanced by this upgrade.
We answer both questions in the positive. First, we introduce an accelerated regularized scheme. in both continuous and discrete time, which we call "follow the accelerated leader" " (FTXL). In continuous time, our scheme can be seen as fusion of the continuous-time analogue of NAG proposed by Su, Boyd, and Candès [41] and the dynamics of regularized learning studied by Mertikopoulos & Sandholm [31] - see also [5, 6, 19, 24, 29, 32-36, 42] and references therein. We show that the resulting dynamics exhibit the same qualitative equilibrium convergence properties as the replicator dynamics of Taylor & Jonker [43] (the most widely studied instance of FTRL in continuous time). However, whereas the replicator dynamics converge to strict Nash equilibria at linear rate, the FTXL dynamics converge superlinearly.
In discrete time, we likewise propose an algorithmic implementation of FTXL which can be applied in various information context: (i) full information, that is, when players observe their entire mixed payoff vector; (ii) realization- based feedback, i.c., when players get to learn the "what-if" payoff of actions that they did not choose; and (iii) bandit, payoff- shafef-aaedddee feedback, where players only observe their realized, in- on-game payoff, and must rely on statistical estimation techniques to reconstruct their payoff vectors. In all cases, we show that FTXL maintains the exponential speedup described above, and converges to strict Nash equilibria at superlinear rate (though the subleading term in the algorithm's 's convergence rate becomes increasingly worse as less information is available). We find this feature of FTXL particularly intriguing as superlinear convergence rates are often associated to methods that are second-order in space, not time; the fact that this is achieved even with bandit feedback is quite surprising in this context.
Closest our work the continuous-time, second-order replicator equation studied by Laraki & Mertikopoulos [25] in the context of evolutionary game theory, and derived through model of pairwise proportional imitation of "long-term success". The dynamics of [25] correspond to the undamped, continuous citttuuuuus--teeeeee version of FTXL with entropic regularization, and the equilibrium convergence rate obtained by [25] agrees with our analysis. Other than that, the dynamics of Flåm & Morgan [12] also attempted to exploit Newtonian structure, but they do not yield favorable convergence properties a general setting. The inertial dynamics proposed [26) likewise sought to leverage an inertial structure combined with the
underpinnings of the replicator
2

---

dynamics, but the resulting replicator equation was not even well-posed (in the sense that its solutions exploded in finite time).
More recently, Gao & Pavel [15, 16] considered a second-order, inertial version of the dynamics of mirror descent in continuous games, and examined their convergence in the context of variational stability [34]. Albeit related at high level to our work (given the link between mirror descent and regularized learning), the dynamics of Gao & Pavel [15, 16] are actually incomparable to our own, and there is no overlap in our techniques or results. Other than that, second-order dynamics in games have also been studied continuous time within the context of control-theorene passivity, yielding promising results in circumventing the impossibility results of Hart & Mas- Mas-CColell [21], cf. Gao & Pavel [13, 14]. Mabrok& Shamma [30], Toonsi & Shamma [44], and references therein. However, the resulting dynamics are also different, and we do not see a way of obtaining comparable rates in our setting.
Preliminaries
In this section, we outline some notions and definitions required for our analysis. Specifically, we introduce the framework of finite N-player games, we discuss the solution concept of a Nash equilibrium, and we present the main ideas of regularized learning in games.
2.1. Finite games. In this work, we focus exclusively with finite games in normal form. Such games consist of finite set of players N .I....,N,, .)), each of whom has finite set of actions strategies 0; E A, and a payoff function u;: A - R, where A t= Nie A, denotes the set of all possible action profiles
pure
(0),....0 aN). To keep track of all this, finite game with the above primitives will be denoted as T(W.
In addition to pure strategies, players may also randomize their choices by employing mixed strategies, that is, by choosing probability distributions X, X; A(A)) over their pure strategies, where A(A)) denotes the probability simplex over Ai. Now, given a strategy profile x .N. X == ITe Ng we will use the standard shorthand x = (xy;x-4) +) to highlight the mixed strategy x; of player against the mixed strategy profile x-; X_; j Xj of all other players. We also define:
1. The mixed payoff of player i under as
(x(x) (xxx)xx
Σ a)EA
Σ
Xia ... IN. (e
(1)
aN ANEAN
2. The mixed payoff vector of player under x as
(x(x) (x) (u,(orix-))aaae
(2)
In words, ex) collects the expected rewards Bia, (x) == u;(a;x-ii of each action a; E Ai of player i N against the mixed strategy profile x-, of all other players. Finally, we write v(x) (x),....., (x)) for the concatenation of the players' mixed payoff vectors.
In terms of solution concepts, we will say that is Nash equilibrium (NE) if player can benefit by unilaterally deviating from their strategy, that is
U7 (xx) 2 (; for all x; E X and all i E N.
(NE)
Moreover, we say that x" a strict Nash equilibrium if (NE) holds as a strict inequality for all x; # x i e N, i.e., if any deviation from x results in strictly worse payoff for the deviating player i e N. is straightforward to verify that a strict equilibrium x² e X is also pure in the sense that each player assigns positive probability only to single pure strategy of E A,. Finally, we denote the support of a strategy x as the set of actions with non-zero probability mass, i.e., supp(x) (a E A Xa > 0}.
2.2. Regularized learning in games. In the general context of finite games, the most widely used learning scheme is the family of algorithms and dynamics known as "follow the regularized leader" (FTRL). In a nutshell, the main idea behind FTRL is that each player i e N plays a "regularized" best response to their cumulative payoff over time, leading to the continuous time dynamics
(1) (x(())
(1 ())
(FTRL-D)
3

---

where
Qi(y) arg max x, xx (y), xi) (x
(3)
denotes the regularized best response mirror map of player E N, and hy: X R is strongly convex function known as the method's 's regularizer. Accordingly, in discrete time, this leads to the algorithm
yl,++1 = Vt yēi,
Xt, Q((y.n)
(FTRL)
where y > O is a hyperparameter known as the algorithm's 's learning rate (or step-size) and 8 is black-box "payoff signal" that carries information about (x,). In the simplest case, when players have full information about the game being played and the actions taken by their opponents, we have Di.n = 0: (x,); ; in more information-deplett environments (such as learning with payoff- bandit feedback), Bg., is a reconstruction of 0; (Xn) based on whatever information
hand.
For concreteness, we close this section with the prototypical example of FTRL methods, the exponen- tial mial/uulillicaaive weights (EW) algorithm. Going back to [2, 28, 45], this method is generated by the negentropy regularizer h (xx) = E Ea Xia, log which yields the EW update rule
exp(Ui.n)
yt.++ Vt yog,
X1,x (y(.)) ||ex(().n))
(EW)
and, in the continuous-timg limit y 0, the exponential weights dynamics
ia v;(x(r))
x1(1) -
(EWD)
In the above, A, denotes the regularized best response induced by the method's entropic regularizer, which is known colloquially as a logit best response - or, even more simply, as the logit map. To make the notation more compact in the sequel, we will write Q (Qi)ieN and A (Ar)ee for the ensemble of the players' regularized logit best response maps.
Remark 1. To streamline our presentation, in the main part of the paper, quantitative results will be stated for the special case of the EW setup above. In Appendix A, we discuss more general decomposable regularizers of the form (x,),) = E, (x;), where 0; [0, 1] - RR is continuous on [0. I]. and has 8" (x) 0 for all x E (0, 1] and lim,-o- 6' ('(x) -cn, Although this set of assumptions can be relaxed, it leads to the clearest presentation of our results, so it will suffice for us.
Remark 2. Throughout the paper, we will interchangeably use ÿ()) and dg/ ds denote the time derivative of g()). This dual notation allows us to adopt whichever form is most convenient in the given context. Moreover, for a process g, we will use the notation g(t) for 2 if it evolves in continuous time, and In for π E IN if it evolves in discrete time steps, omitting the time-index when it clear from context.
3 Combining acceleration with regularization: First insights and results
In this section, we proceed to illustrate how Nesterov's 's accelerated gradient (NAG) method can be combined with FTRL. To keep things as simple as possible, we focus on the continuous- time limit, so we do not have to worry about the choice of hyperparameters, the construction of black-box box models for the players' payoff vectors, etc.
3.1. Nesterov's accelerated gradient algorithm. We begin by discussing Nesterov's 's accelerated gradient algorithm as presented in Nesterov's 's seminal paper [38] in the context of unconstrained smooth convex minimization. Specifically, given a Lipschitz smooth convex function f: IRd - R, the algorithm unfolds iteratively as
Xn+1 Un (V)()
(NAG)
Wn+1 Xn+1 n (Nu+1 X,,
where Wi X1 is initialized arbitrarily and y 0 is a step-size parameter (typically chosen as < 1/L where I. is the Lipschitz smoothness modulus of f). The specific iterative structure of (NAG) - and, in particular the "3" in the denominator - can appear quite mysterious; nevertheless, (NAG) otherwise offers remarkable perfomance gains, improving in particular the rate of convergence

---

of gradient methods from (I/T)) to O(1/T9) [38], and matching in this way the corresponding 22 (1/T") lower bound for the minimization of smooth convex functions [37].'
This groundbreaking result has since become the comnrstone of a vast and diverse literature expanding on the properties of (NAG) and trying to gain deeper understanding of the "how" and "why" of its update structure. One perspective that has gained significant traction in this regard is the continuous- time approach of Su al. [40, 41]; combining the two equations in (NAG) into
xn+1
2 Xn In-1 VV
3 Xn Xn-1
VY
n
VY
they modeled (NAG) as a heavy ball with vanishing friction system of the form
dx di =V((()
3 dx
(HBVF)
1 dt
The choice of terminology alludes to the fact that (HBVF) describes the dynamics of a heavy ball descending the landscape of f under the potential field F(x) fx) with vanishing kinetic friction coefficient (the 3/r factor in front of the momentum term dx/dr). In this interpretation, the mass of the ball accelerates the system, the friction term dissipates energy to enable convergence, and the vanishing friction coefficient quenches the impact of friction over time in order to avoid decelerating the system too much (so the system is, in sense, "critically underdamped").
As was shown by Su al. [41], an explicit Fuler discretization of (HBVF) yields (NAG) with exactly the right momentum coefficient n/ (n 3); moreover, the rate of convergence of the continuous- time dynamics VFB is the same as that of the discrete-time algorithm (NAG), and the energy function and Lyapunov analysis used to derive the former can also be used to derive the latter. For all these reasons, (HBVF) is universally considered as the de facto continuous time analogue of (NAG), and we will treat it as such in the sequel.
3.2. NAG meets FTRL. To move from unconstrained convex minimization problems to finite N N-person games- a constrained, non-convex, multi-agent, multi-objective setting - will be more transparent to start with the continuous-time formulation (HBVF). Indeed, applying the logic behind (HBVF) to the (unconstrained) state variables y of (FTRL-D), we obtain the "follow the accelerated leader" dynamics
d' = v(e(g)) - dy di2
(FTXL-D)
i dr
where the dynamics' driving force Fly) 0 (()) is now given by the payoff field of the game, and the factor r/t, r 2 0. plays again the role of a vanishing friction coefficient. To avoid confusion, we highlight that in the case of regularized learning. the algorithm's 's variable that determines the evolution of the system in an autonomous way the "score variable" y. not the "strategy variable", (which is an ancillary variable obtained from y via the regularized choice map Q).
In contrast to (EWD). the accelerated dynamies (FTXL-D) are second-order in time, fact with fundamental ramifications, not only from a conceptual, but also from an operational viewpoint. Focusing on the latter, we first note that (FTXL-D) requires two sets of initial conditions, y(O) and ((O), the latter having no analogue in the first-order setting of (FTRL-D). In general, the evolution of the system depends on both y() and (()), but since this would introduce an artificial bias toward certain direction, we will take (0) = O, in tune with standard practice for (NAG) [41].
We also note that (FTXL-D) can be mapped to equivalent autonomous first-order system with double the variables: specifically, letting p = I denote the players' (payoff) momentum, (FTXL-D) can be rewritten
dy
di = dp = =((())) -
r
(5)
di
with y(0) initialized arbitrarily and p(0) = (()). In turn, (5) yields (())=r" "'""""rro@@@ ('(((((T)) dr, so pt) can be seen as weighted aggregate of the players' payoffs up to time r: if r = (the undamped regime), all information enters p(t) with the same weight; if > O, past information is discounted relative to more recent observations; and, in the overdamped limit co, all weight is assigned to the current point in time, emulating in this way the first-order system (FTRL-D).
There are, of course, many other approaches to acceleration, that we cannot cover here; for a discussion of the popular "linear coupling" approach of Allen-Zhe & Orecchia [1], see Appendix F.
5

---

3.3. First insights and results. From an operational standpoint, the main question of interest is to specify the equilibrium convergence properties of (FTXL-D) - and, later in the paper, its discrete-time analogue. To establish a baseline, the principal equilibrium properties of its first-order counterpart can be summarized as follows: (i) striet Nash equilibria are locally stable and attracting under (FTRL-D) [23, 311;2 (ii) the dynamics do not admit any other such points (that is, stable and attracting) [11]; and (ti) quantitively, in the case of (EWD), the dynamics converge locally to strict Nash equilibria at geometric rate of the form (1x - x = O(exp(-ct) for some 0 [31].
Our first result below shows that the accelerated dynamies (FTXL-D) exhibit an exponential speed-up relative to (FTRL-D), and the players' orbits converge to strict Nash equilibria at a superlinear rate:
Theorem 1. Let x" be a strict Nash equilibrium ofT, and let x(1) = Qgy(t) be a solution orbit of (FTXL-D). (O) is sufficiently close to x", then x(t) converges x', in particular. if (FTXL-D) is
run with logit best responses (that is, Q t- N), we have
[|x(1) - - 1o s exp(c- 2(r
ot
(6)
where C > O is constant that depends only on the initialization of (FTXL--D) and
1 min min [L (x]xxxx))) =,(Br:x=,) > icN Bessuppix))
c= 2
is the minimum payoff difference equilibrium.
Theorem 1 (which we prove in Appendix B) is representative of the analysis to come, so some remarks are in order. First, we should note that the explicit rate estimate (6) is derived for the special case of logit best responses, which underlie all exponential coanential/multtin multiplicatiie weights algorithms. To the best of our knowledge, the only comparable result in the literature is the similar rate provided in [25] for the case r = O. In the case of a general regularizer, an analogous speed-up is observed, but the exact expressions are more involved, so we defer them to Appendix A second important point concerns whether the rate estimate (6) is tight or not. Finally, the neighborhood of initial conditions around x is determined by the minimum payoff difference at equilibrium and is roughly O(c) in diameter; we defer the relevant details of this discussion to Appendix B.
To answer this question and, at the same time get glimpse of the proof strategy for Theorem 1 - it will be instructive to consider a ainle-player game with two actions. Albeit simple, this toy example is not simplistic, it provides an incisive look into the problem, and will be used to motivate design choices in the sequel.
Example 3.1. Consider single-player game with actions A and B such that u(A) u(B) so the (dominant) strategy x = (1,0) is strict Nash equilibrium. Then, letting yA yB. (FTXL-DD) readily yields
d²
d'ys
d d'yn
dy u(A) u(B) 1 dt dt
dys
dz dt
(8)
dt2
di2
di2
As we show in Appendix B, this non-autonomous differential equation can be solved exactly to yield z(r) z(0) + 12(( + 1)], and hence
2
(1x - x011 I exp(z(()) exp -z(0)- 2(r
1)
Since e = ((A) (B) = 1, the rate (9) coincides with that of Theorem I up to a factor of 1/2. This factor is an artifact of the analysis and, in fact, it can be tightened to (1 8) for arbitrarily small > 0; we did not provide this more precise expression to lighten notation. By contrast, the factor 2(r 1) in (6) cannot be lifted: this has important ramifications which we diseuss below.
The first conclusion that can be drawn from Example 3.1 is that the rate estimate of Theorem is tight and cannot be improved in general. In addition, and in stark contrast to (NAG), Example 3.1
RRcall here that e X is said to be (i) Lyapunov stable (or simply stable) if every orbit x(1 of the dynamics that starts close enough to x" remains close enough to x" for all I 2 O: (ii) attracting if lim x(1) = x" for every orbit x(r) that starts close enough to x"; and (ii) asymptotically stable if it is both stable and attracting. For introduction to the theory of dynamical systems, cf. Shub [39] and Hirsch et al. [22].

---

shows that the optimal value for the friction parameter is 0 (at least from a min-man max viewpoint, as this value yields the best possible lower bound for the rate). Of course, this raises the question as to whether this is due to the continuous-tima character of the policy; however, as we show in detail in Appendix C, this is not the case: the direct handover of (NAG) to Example 3.1 yields the exact same rate (though the proof relies on significantly more opaque generating function calculation).
In view of all this, it becomes apparent that friction only hinders the equilibrium convergence properties of accelerated FTRL schemes in our game-theoretic setting. On that account, we will continue our analysis in the undamped regime r = 0.
Accelerated learning: Analysis and results
4.1. The algorithm. To obtain a bona fide, algorithmic implementation of the continuous time dynamics (FTXI.-D), will proceed with the same explicit, finiteddifference scheme leading to the discrete-time algorithm (NAG) from the continuous-
dynamics (HBVF) of Su et al. [41]. Specifically, taking discretization step y > 0 in (FTXL-D) and setting the scheme's friction parameter to zero (which, as we discussed at length in the previous section, is the optimal choice in our setting), straightforward derivation yields the basic update rule
yyt,+I 2 + 1iln=11/y² 0j.m for all E A and all n = 1,2....
(10)
In the above, just as in the case of (FTRL), ij.n E RA denotes black-box "payoff signal" that carries information about the mixed payoff vector 8; (xx,) of player at the current strategy profile X (we provide more details on this below).
Alternatively, to obtain an equivalent first-order iterative rule (which is easier to handle and discuss), it will be convenient to introduce the momentum variables pn (yn yn-1)/y. Doing just that, simple rearrangement of (10) yields the "follow the accelerated leader" scheme
Vi,++1 Bi.n YPi,n+1
Pin+1 Pi,n + y0i,
Ni,n (.(y)n))
(FTXL)
The algorithm (FTXL) will be our main object of study in the sequel, and we will examine its convergence properties under three differerent models for i,
1. Full information, i.c., players get to access their full, mixed payoff vectors:
ig_n (xxx)
for all i E N, 1,
(1
2. Realization- based feedback, i.e., after choosing an action profile a ~ Xn. each player e / observes (or otherwise calculates) the vector of their counterfactual, "what-if" rewards, namely
ii (;((n))
for all e N, 1,2,...
(11b)
Bandit/ / (Payoff-buul based feedback, i.e., each player only observes their current reward, and must rely on statistical estimation techniques to reconstruct an estimate of ny (x,). For concreteness, we will consider the case where players employ version of the so-called importance estimator
üj IWE(Xi, oi for all i N, 1,2....
(11c)
which we describe in detail later in this section.
Of course, this list of information models is not exhaustive, but it is a faithful representation of most scenarios that arise in practice, so will suffice for our purposes.
Now before moving forward with the analysis, it will be usefull to keep some high-level remarks in mind. The first that (FTXL) shares many similarities with (FTRL), but also several notable differences. At the most basic level, (FTRL) and (FTXL) are both "stimulus-response" the spirit of Erev & Roth [10], that is, players "respond" with strategy N;,, = Qi(Yi... a "stimulus" It.n generated by the observed payoff signals Di.n. In this regard, both methods adhere to the online learning setting (and, in particular, to the regularized learning paradigm).
schemes in
'The reader might also wonder the use of non-vanishing friction coefficient ry instead of (r/1g- could be beneficial to the convergence rate of (FTXL-D). As we show in Appendices B and C, this leads to significantly worse convergence rates of the form [|x(t)) llo exp(-O(() for all > 0.
7

---

However, unlike (FTRL), where players respond to the aggregate of their payoff signals the process yn (FTRL) - the accelerated algorithm (FTXL) introduces an additional aggregation layer, which expresses how players "build momentum" based on the same payoff signals the process Pn in (FTXL.). Intuitively, we can think of these two processes as the "position" and "momentum" variables of classical inertial system, not unlike the heavy-ball dynamics of Su et al. [41]. The only conceptual difference is that, instead of rolling along the landscape of a (convex) function, the players now track the "mirrored" payoff field b(y) (v))))
In the rest of this section, we proceed to examine in detail the equilibrium convergence properties of (FTXL) under each of the three models detailed in Eqs. (11a)-(11c) in order.
4.2. Accelerated learning with full information. We begin with the full information model (1 (l)).. This is the most straightforward model (due to the absence of randomness and uncertainty) but, admittedly, also the least realistic one. Nevertheless, it will serve as a useful benchmark for the rest, and it will allow to introduce several important notions.
Before we state our result, it is important to note that a finite game can have multiple strict Nash equilibria, global convergence results are, in general, unattainable; for this reason, analyze the algorithm's 's local convergence landscape. In this regard, Theorem 2 below shows that (FTXL) with full information achieves superlinear local convergence rate strict Nash equilibria:
Theorem 2. Let x" be strict Nash equilibrium of T, and let Xn = Q(m) be the sequence of play generated by (FTXL) with full information feedback of the form (lla). If is initialized sufficiently close to x", then Xn converges to x"; in particular, if (FTXL) is run with logit best responses (that is, Q A), we have
| - x' 1oc s exp C cy²
T(T exp(-O((2))
(12)
2
where C > O a constant that depends only on the initialization of (FTXL) and
1
c= min min (x((x(x>>) - 14; (;;Bxxx"))]
(13)
2 IEN Bexupp(x))
the minimum payoff difference at equilibrium.
To maintain the flow of our discussion, we defer the proof of Theorem 2 to Appendix C. Instead, we only note here that, just as in the case of (HBVF) and (NAG), Theorem 2 provides essentially the same rate of convergence its continuous-time counterpart, Theorem I, modulo subleading term which has an exponentially small impact on the rate of convergence. In particular, we should stress that the superlinear convergence rate of (FTXL) exhibits an exponential speedup relative to (FTRL), which is known to converge at a geometric rate ||xy - x" ll = exp(-O(TT). This is in direct correspondence to what we observe in continuous time, showing in particular that the continuous time dynamics (FTXL-D) are a faithful representation of (FTXL).
We should also stress here that superlinear convergence rates are typically associated with methods that are second-order in space, in the sense that they employ Hessian-like information like Newton's algorithm not second-order in time - like (NAG) and (FTXL). We find this observation particularly intriguing as it suggests that accelerated rates can be observed in the context of learning in games without having to pay the excessively high compute cost of second-order methods in optimization.
4.3. Accelerated learning with realization- based feedback. We now turn to the realization-baser model (1Ib), where players can only assess the rewards of their pure actions in response to the realized actions of all other players. In words, 0z 1;(a,) collects the payoffs that player i E N would have obtained by playing each of their pure actions 0; E A, against the action profile Q-i.n adopted by the rest of the players.
In contrast to the full information model (1 (a),, the realization- model is stochastic in nature, so our convergence results will likewise be stochastic. Nevertheless, despite the added layer of uncer- tainty, we show that (FTXL) with realization- based feedback maintains a superlinear convergence rate with high probability:
Theorem Let x" be a strict Nash equilibrium of I, fix some confidence level > O, and let Xn ((ym) be the sequence of play generated by (FTXL) with realization- based feedback per
8

---

16-1
01711
(a) Zero-sum game: Realization- based feedhack
(b) Zero-sum game: Bandit feedback
Feetbark Modil: Bellossss bood
Fewdbokk Model Baads
FTA
167
FTA
147
12.4
18.7
(c) Congestion game: Sealization-basee feedback
(d) Congestion game: Bandit feedback
Figure Performance evaluation of (FTXL) a zero-sum and congestion game under realization- and bandit feedback. Solid lines represent average values, while shaded regions enclose +1 standard deviation. The plots are in logarithmic scale.
(11b) and sufficiently small step-size > O. Then there exists a neighborhood of such that P(xn + x" as - oo) 6 if E U.
(14)
In particular, if (FTXL) is run with logit best responses (that is, Q - A), there exist positive constants C, c 0 as in Theorem 2 such that on the event (xn + x" as n - oo):
||x - x b1 s exp cCp T(T T 1)
2 5 3CySB3TS13 = exp(-o(T3))
(15)
What is particularly surprising in Theorem 3 is that, (FTXL) maintains the accelerated superlinear rate of Theorem 2 and, likewise, the exponential speedup relative to (FTRL) despite the randomness and uncertainty involved in the realization- based model (11.). The salient point enabling this feature of (FTXL) is that 0, can be expressed as
D, v(x,) U,
(16)
where Un E Tl R is an almost surely bounded conditionally zero-mean stochastic perturbation,
that is, E[U,, [F,] = O, where F, := Ox))... x,,) denotes the history of play up to (and including) time n. Thanks to the boundedness of (16), we are able to derive a series of probabilistic estimates showing that, with high probability (and, in particular, greater than - 6), the contribution of the noise in the algorithm's is rate becomes subleading, thus allowing the superlinear rate of Theorem 2 to emerge. As in the case of Theorem 2, we defer the proof of Theorem 3 to the appendix.
4.4. Bandit feedback. The last framework we consider is the bandit model where players only observe their realized rewards, scalar from which they must reconstruct their entire payoff vector. To do so, a standard technique from the multi-armed bandit literature is the so-called importance weighted estimator (IWE) [8, 27], defined in our setting
1 [arn ar
Dia.n
Ui (ay a.1.)
(IWE)
Riarn
9

---

where 8t, (1- En),i,n + En unif is a mixture of xt,n and the uniform distribution on A, (a mechanism known in the literature as explicit exploration). Importandly this estimator is unbiased relative to the perturbed strategy x, which thus incurs an (E5,) non-zero-sum error to the estimation of (x,)) This error can be made arbitrarily small by taking 6n - but, in doing so, the variance of ii,n diverges, leading to bias-variance trade-off that is difficult to tame.
Despite these added difficulties, show below that (FTXL) maintains its superlinear convergence rate even with bandit, payoff- feedback:
Theorem 4. Let x" be a strict Nash equilibrium of T, fix some confidence level ö > O, and let Xn Q(yn) be the sequence of play generated by (FTXL) with bandit feedback of the form (11c), an IWE exploration parameter En x 1/n's for some la E (0, 1/2), and a sufficiently small step-size
y 0. Then there exists neighborhood U of in X such that
P(xn - xx as oo) 2 6
if E U
(17)
In particular, if (FTXL) is run with logit best responses (that is, Q t A), there exist positive constants C. O as in Theorem 2 such that on the event (In + x' as n + 00)
|xx 10 I exp ( ccy T(T T(T-T)) 11) 5 cy ( exp(-o(r3))
(18)
2
Theorem 4 (which we prove in Appendix D shows that, despite the degradation of the sublcading term, (FTXL) retains its superlinear convergence rate even with bandit, payoff-based feedback (for numerical demonstration, see Fig. I above). We find this feature of (FTXL) particularly important as it shows that the algorithm remains exceptionally robust in the face of randomness and uncertainty, even we move toward increasingly information-stare starved environments from full information, to realization- based observations and, ultimately, to bandit feedback. This has important ramifications from an operational standpoint, which we intend to examine further in future work.
4.5. Numerical Experiments. We conclude this section with a series of numerical simulations to validate the performance of (FTXL). To this end, we consider two game paradigms, (i) a 2-player zero-sum game, and (ii) a congestion game.
Zero-sum Games. First, we consider a 2-player zero-sum game with actions {a), 02, [3) and B2,B3, and payoff matrix
(2) (1,-1)
(2
P (-2,2) (-1,1)
(-2. 2)
(-1,1) (-2,2)
(-2,2)
Here, the rows of P correspond to the actions of player A and the columns to the actions of player B, while the first item of each entry of P corresponds to the payoff of A, and the second one to the payoff of Clearly, the action profile (2)) is strict Nash equilibrium.
Congestion Games. As a second example, we consider a congestion game with N 100 and 2 roads, ri and 72, with costs e 1.1 and c2 d/N where is the number of drivers on r2. In words, has fixed delay equal to 1.1, while has delay proportional to the drivers using it. Note, that the strategy profile where all players are using 72 is a strict Nash equilibrium.
In Fig. 1. we assess the convergence of (FTXL) with logit best responses, under realization- and bandit feedback, and compare it to the standard (EW) with the same level of information. The figures verify that (FTXL) outperforms (EW) regarding the convergence to strict Nash equilibrium both for the realization-based and the bandit feedback, as expected from the theoretical findings. Specifically, they validate the faster convergence rate of (FTXL) compared to that of the (EW) algorithm. Moreover, we observe that both algorithms perform worse under bandit feedback than under realization-basse feedback. This behavior is expected as less information becomes available. More details can be found in Appendix E.
10

---

Acknowledgments and Disclosure of Funding
This research was supported in part by the French National Research Agency (ANR) in the frame- work of the PEPR IA FOUNDRY project AANR-3--PEIA-KA program" (ANR-I5-IDEX Alpes SEIR-19-P31A-0000
the "Investissements d' d'avenir the LabEx PERSYVAL (ANR- 11--111-L----OE 01). MIAI@ Grenoble the project IRGA2024- SPICE- G-LE-GGH--IEE 677--RGG44990 PM is also with the Archimedes Research Unit Athena RC Department of Mathematics, National & Kapodistrian University of Athens, and his research was partially funded by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGenerationFU Program.
References
[1] Allen-Zhe Zhu, Z. and Orecchia, L. Lincar coupling: An ultimate unification of gradicnt and mitror descent. In ITCS '17: Proceedings of the 8th Conference on Innovations in Theoretical Computer Science, 2017.
[2] Auer, P., Cesa- BiaaaBBaachh, N., Freund. Y.. and Schapire. R. E. Gambling in a rigged casino: The adversarial multi-armed bandit problem. Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995.
[3] Beck, A. and Teboulle, M. A fast iterative shrinkage-thresholddee thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183 202, March 2009.
[4] Benaim, M. Dynamics of stochastic approximation algorithms. Azéma, J., Émery, M., Ledoux. M., and Yor, M. (cds.), Séminaire Probabilités XXXIII, volume 1709 of Lecture Notes in Mathematics, pp. 1-68. Springer Berlin Hcidelberg, 1999.
[5] Boone, V. and Mertikopoulos, P. The equivalence of dynamic and strategic stability under regularized learning in games. In NeurlPS '23: Proceedings of the 37th International Conference Neural Information Processing Systems, 2023.
[6] Bravo, M. and Mertikopoulos, P. On the robustness of learning in games with stochastically perturbed payoff observations. Games and Economic Behuvior, 103(John Nash Memorial issue):41-66, May 2017.
Bubeck, S. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 833-4): 2015.
[8] Bubeck, S. and Cesa- Bianchi, N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning. 111): 2012.
Daskalakis, C., Goldherg, W., and Papadimitriou, C. H. The complexity of computing Nash equilibrium. Communications of the ACM, 52(())89-97, 2009.
[10] Erev, I. and Roth, A. E. Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria. American Economic Review, 88:848-881, 1998.
[11] Flokas, I.., Vlatakis- Saaakiis-Gaaagkouuni... F. V., Lianeas, T., Mertikopoulos, P., and Piliouras, G. No-regret learning and mixed Nash equilibria: They do not mix. In NeurlPS '20: Proceedings the 34th International Conference on Neural Information Processing Systems, 2020.
[12] Flåm, S. D. and Morgan, J. Newtonian mechanics and Nash play. International Game Theory Review, 6 (2):181-194, 2004.
[13] Gao, B. and Pavel, T... On passivity and reinforcement learning in finite games. In 2018 IEFE Conference on Decision and Control (CDC), pp. 340-345, 2018. doi: 10. (09/CDC.201..6199111
[14] Gao, B. and Pavel, L. On passivity, reinforcement learning, and higher order learning in multiagent finite games. IEEE Transactions Automatic Control, 66(1):121-136, 2021. doi: 10.1
[15] Gao, B. and Pavel, I.. Second-order mirror descent: exact convergence beyond strictly stable equilibria in concave games. In 2021 60th IEEE Conference on Decision and Control (CDC), pp. 948-953, 2021. doi: N0.1109/CDC45484.2200 211.844.2221.988222.
[16] Gao, B. and Pavel, Second-order mirror descent: Convergence in games beyond averaging and discounting. IEEE Transactions on Automatic Control, 6944)221432 2024, doi: 10.1 109// 3291953.
[17] Giannou, A., Vlatakis- Gkaragkounis, E. V., and Mertikopoulos, P. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In COLT '21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[18] Giannou, A., Vlatakis Gkaragkounis, E. V., and Mertikopoulos, P. The convergence rate of regularized learning in games: From bandits and uncertainty to optimism and beyond. In NeurIPS '21: Proceedings of the 35th International Conference Neural Information Processing Systems, 2021.
11

---

[19] Hadikhanloo. S., Laraki, R., Mertikopoulos. P., and Sorin, S. Learning in nonatomic games, Part I: Finite action spaces and population games. Journal of Dynamicx and Games, 944 William H. Sandholm memorial
1ssu October 2022.
[20] Hall, and Heyde, C. C. Martingale Limit Theory and Its Application. Prohability and Mathematical Statistics. Academic Press, New York, 1980.
[21] Hart, S. and Mas-Colell, A. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review, 93(5): 1830-11011100 836, 2003.
[22] Hirsch, M. W., Smale, S., and Devaney, R. L. Differential Equations, Dynamical Systems, and on Introduction to Chaos. Elsevier, London, UK, edition, 2004.
[23] Hofbauer, and Sigmund, K. Evolutionary game dynamics. Bulletin of the American Mathematical Society, 40(4). July 2003.
[24] Hsieh, Y.GG., Antonakopoulos, K., and Mertikopoulos, P. 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.
[25] Laraki, and Mertikopoulos, P. Higher order game dynamics. Journal of Economic Theory, 148(6): 2666-2695, November 2013.
[26] Laraki, R. and Mertikopoulos, P. Inertial game dynamics and applications to constrained optimization. SIAM Journal on Control and Optimization, 33655)33 53(5):3141-3170 October 2015.
[27]
Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, Cambridge, UK, 2020.
[28] Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. Information and Computation, 108
(2):212-261, 1994.
[29] Lotidis, K., Mertikkppollss, P., and Bambos, N. Learning in games with quantized payoff observations. In CDC '22 Proceedings of the 6t IEEE Anmual Conference on Decision and Control, 2022.
[30] Mabrok, M. A. and Shamma, J. S. Passivity analysis higher order evolutionary dynamics and population
games. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 6129-6134, 2016. doi: 10. 00.10999DCC2211.799221..
[31] Mertikopoulos. P. and Sandholm. W. H. Learning in games via reinforcement and regularization. Mathe- matics of Operations Research, 4 4144):1297-1324 November 2016.
[32] Mertikopoulos, and Sandholm, W. H. Riemannian game dynamics. Journal of Economic Theory, 177:
315-364, September 2018.
[33] Mertikopoulos, P. and Staudigl. M. Equilibrium tracking and convergence in dynamic games. In CDC '21: Proceedings of the 60th IEEE Annual Conference Decision and Control, 2021.
[34] Mertikopoulos, P. and Zhou, 7. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programminng 173((12))465-507, January 2019.
[35] Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G. Cycles in adversarial regularized learning. In Symposium on Discrete Algorithums, 2018.
SODA '8: Proceedings of the 29th annual
[36] Mertikopoulos, P., Hsieh, Y.-P., and Cevher, V. A unified stochastic approximation framework for learning in games. Mathematical P Programming, 203:559-600 January 2024.
[37] Nemirovski, A. S. and Yudin, D. B. Problem Complexity and Method Efficiency in Optimization. Wiley, New York, NY, 1983.
[38] Nesterov, Y. A method for unconstrained convex minimization problem with the rate of convergence O(1/k2), Proceedings of the USSR Academy of Sciences, 269(543-547). 1983.
[39] Shub, M. Global Stability of Dynamical Systems. Springer- Berlin, 1987.
[40] Su, W.. Boyd, S. P., and Candès, E. J. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. In NIPS '1: Proceedings of the 28th International Conference on Neural 2014.
Information Processing Systems, pp.
[41] Su, W., Boyd, S., and Candès, E. J. A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights. Journal of Machine Learning Research. (7(153):1443 2016.
[42] Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. F. Fast convergence of regularized learning in games.
In NIPS 115: Proceedings of the 29th International Conference on Neural Information Processing Systems, pp. 2989-29977 2015.
[43] Taylor, P. D. and Jonker, L. B. Evolutionary stable strategies and game dynamics. Mathematical Biosciences. 40(1-2), 1978.
[44] Toonsi, S. and Shamma, J. S. Higher-order uncoupled dynamics do not lead Nash equilibrium except when they do. NewrlPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023.
[45] Vovk, V. G. Aggregating strategies. In COLT '90: Proceedings of the 3rd Workshop on Computational Learning Theory, pp. 371-383, 1990.
12

---

Appendix
In Appendix A, we discuss how our findings can be extended to general regularizers. Subsequently, Appendices and contain the technical proofs for continuous and discrete time algorithms, respectively. Following this, Appendix D provides the convergence results of (FTXL) under partial information, specifically under realization based and bandit feedback. conclude this section with Appendix E, which presents the details of the numerical experiments.
A Auxiliary results for general regularizers
In this appendix, we briefly discuss how to obtain the convergence of (FTXL) for mirror maps Q beyond the logit map A. Namely, we consider regularizers that are decomposable, i.e., hx,x;, Ea (xa,) such that 0 [0, 1] - R is continuous on [0, 1], twice differentiable on (0, 1] and strongly convex with 07(0+)= 00.
Lemma A.1. Suppose that Xn Qyyn) and for all E A, a', holds that ya.n Ya as - Then, Xu converges to x", where x" is point mass at a². Moreover, it holds that:
||,, 1o 20' ya. yar.a)
(A.1)
ata
Proof. First, note that for Q(y), have that x is the solution of the following optimization problem
Q(y) arg max
Σ acd
YaNa h(x)
Σ Xa a&A
and Va E :A:xa 20}
By solving the Karush-KuhnTTuun
(KKT) conditions to this optimization problem readily get that x lies in the interior of X, since ((0*) = -00, and thus we obtain that at the solution, holds Ya 0' (xx)) + for 1 R. Therefore, have:
ya.n ya a 0' (Naa.)) O (xar.))
(A.2)
or equivalently:
(xx,,) = 6 (Xo' n) + yann ya,, n S (1) + ya.n Ya*
(A.3)
Now, assume that there exists A such that Xa.. does not converge to 0, that is, lim sup, Xa. for some > Then, since / strongly convex, is strictly increasing, and thus 6' (Naa,n) 0/ (e) infinitely often. However, by taking contradiction. Therefore, we conclude that for all a # a", it holds that lim convergence result follows.
co in (A.3), it implies that 6' (Na,n) -o0, which is and the
Finally, note that since is strictly increasing, it is invertible and its inverse is strictly increasing as well. Thus, for each a & a we have:
Xa. s (0')-1(0 (1) + yan yn)..))
(A.4)
Therefore,
||x, - x' = No Σ xa. S (8)- yo ya
(A.5)
ata
aza
and our proof is complete.
B Proofs for Continuous Time Algorithms
In this appendix, we provide the proof of Theorem and discuss the convergence of (FTXL-D) under a non-vanishing friction coefficient that is, rý instead of (r/1)g. First, we provide lemma that necessary for analysis.
13

---

Lemma B.1. Letx" (ai....., ,n)) E X be strict Nash equilibrium of T, and let d denote the minimum payoff difference at equilibrium, i.e.,
= min min ieN Bresupp(x))
(B.1)
Then, for any c (0, d), there exists > 0 such that if yio yio: > for all at * of e A, and i N, then
Bio; (2(u)) - Via, (O(y)) for all a; # aj E Ai, EN.
(B.2)
Proof. Since x" is a strict Nash equilibrium, the minimum payoff difference d at is bounded away from zero. Then, by continuity the function x + o(x), there exists a neighborhood U. of x" such that for any U. it holds
Dia; (x) - Via, (x) > for all # aj E and i N
(B.3)
Finally, by Giannou et al. [18, Lemma C.2.], there exists M > 0, such that Q(y) E U. for all e V with
yiu; yia, > M for all a; aj Ai. and e N Therefore, readily get that if y V satisfies the above relation, then Via; Bia (Q())) Via, (Q()))
(B.4)
for all # of e Ai, and i e N.
We are now a position to prove Theorem I, which we restate below for convenience.
Theorem 1. Let x" be strict Nash equilibrium o, and let x(1) = =Qy(()) be solution orbit of (FTXL-D). (f)) is sufficiently close to x", then x(t) converges to x"; ; in particular, if (FTXL-D) is run with logit best responses (that is, Q - A), we have
|xx(1) - 1l exp(cc
ot2
(6)
2(r +(r+1)
where C > O a constant that depends only on the initialization of (FTXL--D) and
1 min min (u<(x]xxL)) u,(Bxxx(,)) >
(7)
2 ieN (xsppp()))
the minimum payoff difference equilibrium.
Proof. First of all, since x" is strict Nash equilibrium, by Lemma B.1 for
c = min min [x;(x/xx",) -:,(Bxx(())))))
2 iEN Bresupp(x))
there exists M > such that if yta; yia > M for all a; # of E Ai and i e N, then
Uio (Q())) Uia, (e())) for all a; # af and i N.
(B.5)
From now on, for notational convenience, focus on player i N and drop the player-specific indices altogether. Then, for a a² E A, we let (t) yo (1) y (t), which evolves as:
( = =x( - Uor (x(1) -
(B.6)
Let (0) such that z. (0) - E, a # E A, where > 0 small. We will, first, show that z(1) -M for all / 2 O. For the sake of contradiction, and denoting To = inf 2 0: z(1) 2 -M), suppose that To < so. Then, we readily get that for < To, holds
vx(x(1) uer (x(1)
(B.7)
and therefore, for all To:
2 (t) + 17- (1 1 (x) vx)( -ct"
(B.8)
14

---

which can be rewritten as:
dt (ta(1)))) S -ot
(B.9)
Integrating over To, we obtain 2a(1) s -otrt| /(r + 1), which readily implies:
(I) (0) 2(r + 1) 2 c <-M 2(r
(B.10)
By sending/ / - To, we arrive at a contradiction. Therefor (1) < -M for all 2 O, and the previous equation implies that for all 0:
Za (r) (0) 2(r 1) f
(B.11)
and invoking Lemma A. we get the convergence result. Finally, translating the score-differences to the primal space X, get:
|xx(1) -x' max {1 Niuu (t) rcN
(B.12)
For the of logit best responses, i.e., when Q and assuming that the maximum above is attained for player N, we obtain
Earsat exp(zar(1) (1)
[xx(t) x'slss
1 Mantte exp(za, (1))
x Σ exp(Zan (r))
s | exp Zai (0) 2(r P)
eesp/c- C- 2(r+ p)
(B.13)
for C loglAA1 Zen (0).
Now, moving to the case where constant friction coefficient instead of (r/r)g. (FTXL-D) becomes:
di v( - dy di Under, (B.14), we obtain the following convergence result.
d'
(B.14)
Theorem B.1. Let x" be strict Nash equilibrium of and let x(1) = Qy((t) be solution orbit of (4. x0) is sufficiently close to x", then x(1) converges to x*: in particular, if (B.14) is run with logit best responses (that is. t- A). we have
(xx xllooo -xp(c--1-- fe
(B.15)
where C > 0 is constant that depends on the initialization of (B.14) and
1
min min (u((x)xx",) -., (x:xxx,,)) leN Brssupp(())
(B.16)
2
is the minimum payoff difference equilibrium.
Proof. The initial steps of proof of Theorem B. are similar to the proof of Theorem 1, which we include for the sake of completeness.
Specifically, by Lemma B.I there exists M such that if yia; - Via, M for all a, # az A, and E N,, then
Uio , (Q())) Via (Q()) for all # aj and i N.
(B.17)
15

---

Now, for notational convenience, we focus on player i E . and drop the player-specific indices altogether. Then, for a' A, we let 2a (1) (t) - yu (r). which evolves as:
2(1) (x(()) - Un- (x(()) - (()
(B.18)
Let y(0) such that (0) -M &, for all a * a" E ... where & > small. As in the proof of Theorem 1, we will, first, show that z(r) < - for all r 2 O. For the sake of contradiction, and
denoting To inf 2 0 z(r) 2 -M}, suppose that To co. Then, we readily get that for all To- it holds
(xx(0)) < -c
(B.19)
and therefore, for all To:
(1)e + rre rre" = ('(((( vo (x) & -ce
(B.20)
which can be rewritten as:
d
di 2 (1)e)) s -ce
(B.21)
Integrating over f To, and using that ča (0) = 0, we obtain ia (a( S -c/r ce ce /r, which implies:
c
c
(1) s za (0)
-1
- =e-
p x2
p2
= z.) - C
< (0)
< <-M
(B.22)
where we used the fact that + e 1 for x e R with equality and only if 0. By sending / - To, we arrive at contradiction. Therefore zu (f) < -M for all 0, and the previous equation implies that for all : 2 0:
(1) - za (0)
-1 p2
(B.23)
and invoking Lemma A.1 for ((x) x logxx, we get the convergence result.
C Proofs for discrete-time algorithms with full information
In this section, we provide the results for the (FTXL) algorithm with full- full-informatio feedback. First, we discuss the rates obtained by the direct discretization of (FTXL--) with both vanishing and non- vanishing friction, and then provide the proof of Theorem 2, our main result, for the full-information case.
C.1. FTXL with vanishing friction. First, we provide the rate of convergence for the discrete version of (FTXL-D) with vanishing friction:
Pin+1 = Pi. 1- yr y0i.
(C.1)
yi,++1 = Yi.n + YPi.n+1
To streamline our presentation, we consider the setup of Example 3.1 that provides a lower bound for the algorithm.
Proposition C.1. Consider the single-player game I with actions and such that u(A) - u(B) of Example 3.1, and let Xn A(yn) be the sequence of play generated by (C.1). Then, denoting by (1,0) the strict Nash equilibrium, we have:
-'llss ~ exp/c- C- 2(yr + +1)
2212
(C.2)
where C > O is constant that depends only the initialization of the algorithm.
16

---

Proof. We first define the score-difference
Wn = PB.n
Ps
(C.3)
with initial condition
0. Then, unfolding according to the sequence of play, we obtain:
yr
Wn+1
= Wn
+ (( -
n
Yr
w/
k-1
yr
-Y
(C.44
k=
We next define for N the difference
yB,n yn Thus, unfolding it, we obtain:
Zn+1 = Zn yW
k-1 Z=D
yr n1 x>//)) )
In y²
k=
21
2
Σ
yr m - e)
(C.5)
m-1
8-
Now, using Lemma C.I, which we provide after this proof, we obtain that
yr 1 +
yr m)
Zn+1 = 21 y
1+ 1 yr
1 yr
m==
t=l
=1 - y² 11(111 1)
yr
yr i
2(1 yr)
1 yr
1
[=l
n2n²
21 2(1 yr)
+ (n)
(C.6)
and invoking Lemma A.1 for 0(x) logx, get the result.
The following lemma a necessary tool for obtaining the exact convergence rate in Proposition C.2. Lemma C.1. For any m e N and we have that
Σ1
1-1
m +
M ++
a
(C.7)
E-
m
1
[-]
Proof. First, by expanding the inner product, we can rewrite the expression
c C-a
m
m
m... (m k + 1)
m-1 (m - a) a) - k)!
(m k am!!!
(m a)!
m-1
(m - k)!
(C.8)
m! (m-k-a)
where with slight abuse of notation we use the factorial notation (m a)! denote the Gamma function evaluated at m a i.e., ['m a 1).
Now, defining the quantity
(m k)! (m a)! m
Fm =
m!
(m k a)!

---

the difference of two consecutive terms evolves as:
(m +
a)! m+]
m + k)!
(m - a)!
m
(m k)!
Fm+1= Fmm
(m 1)!
(m + - k a)!
m!
(m k - a)!
k=1
+ 1 -
(m + a)!
m+1
(m + - k)
(m- a)!
m
(m - k)!
+
(m 1)!
(m - a
m!
(m aa!
(m a)!
(m 1 k)!
(m a)!
(m + 1)!
m #+1
(m + 1)!
(m + 1--k a)!
m!
(m 1
k=2
k=2
m
(m 1 am (m++ -k)! (m + 1) a)! k 1)!
I1 + 1
(m + 1)!(m a- k)!
l=2
m 1
m++
(m
+ 1
(m + 1)!(m 1-
m 1
m+1
(m (m-(mmmmm)))))))
1
(m 1)!(m + 1 -
k=2
m 1
a
m+l
(m + 1- k)) a)!
i + 1
+ 1
(m 1)!(m aa k)!
m +
a
Fm+l
(C.9)
111 +
Thus, we readily obtain the recurrence relation
m +
Fm+1 Fm + 1.
(C.10)
We continue the proof by induction.
To this end, will show that
Fm m a
m l-a
(C.11)
1+a
1
For the base case, note that For the inductive step, suppose that (C.11) holds for m N. Then, we have:
1
F1 = (1-
Ita + 1 (1 (1-a)
(C.12)
m
a
F Fm+1=
+
m +
1 a
1+
t=1
m m+1
a
{ f-a
(C.13)
I+a
1 (=1 8
which implies the inductive step
Fm+1 m + 1 a
m+1 (- I+a a 1+a
(C.14)
a
t=l t
and thus (C.11) holds for all m N. Finally, to complete the proof notice that
m-
(m a)!
m-1
(m- k)! a)!
))
m!!
m-1
F
(=0
m
m
a
M
L a
m
a
1
1 +
7
m
a
M
a
7
(C.15)
1
1 1
[-]
to be shown.
18

---

Next, we discuss the cases of non-vaniln ton-vanishing and zero friction.
C.2. FTXL with non-vanishing friction. We continue this section by considering the case of non-vanishing friction in analogy to the continuous time case, per Appendix B. Specifically, consider the discrete version of (FTXL-D) with non-vanishing friction, as follows:
Pin+1 Pi.n yr) + y0i.
(C.
yl,++ Mi.n PPi.++1
with yr 1. Below, we provide the rate of convergence for the setup of Example 3.1, as we did before. Namely, we obtain a linear convergence rate, the following proposition suggests.
Proposition C.2. Consider the single-player game I with actions and such that u(A) - u(B) = of Example 3.1, and let Xn A(yn) be the sequence of play generated by (C.16). Then, denoting by x (1, 0y the strict Nash equilibrium, we have:
||x - x" oo exp(c-2n))
(C.17)
where C > O a constant that depends on the initialization of the algorithm.
Proof. We first define the score-difference
Wn = PB.n PA,n
(C.18)
with initial condition w1 Then, unfolding according to the sequence of play, we obtain:
Wn+1
Wn yr) y(u(B) u(A))
Wn (1 yr-
n-1 Σ (1 yr)
k=0
(1 yr)
(C.19)
We next define for N the difference lB.n Ya.n Thus, unfolding it, obtain:
In+1 = yWn+11
= zn - (1 yr)
n
1 (1- yr)
Σ
1 yr)"
= 21
n (1 - yrr)
= 21 - + O(1)
(C.20)
and invoking Lemma A.I for (xx) x log.x, we get the result.
presented in Section C.3. FTXL with friction. Moving forward the case of provide the proof of Theorem 2, which we restate below for convenience.
Theorem 2. Let x² be strict Nash equilibrium of T, and let X, Q be the sequence of play generated by (FTXL) with full information feedback of the form (lla). x is initialized sufficiently close to x", then Xn converges x"; particular, if (FTXL) is run with logit best responses (that is, Q < A), we have
- - S cxp T( exp(-0(T2))
(12)
2
where C > 0 constant that depends only on the initialization of (FTXL) and
1
min min [m<({]sx()) u;(Bix"",) > 0 ieN Bresup((;))
(13)
2
is the minimum payoff difference equilibrium.
19

---

First of all, since x² is a strict Nash equilibrium, by Lemma B.1 for Proof.
c= min min [m;(xf:x",) ux(Bax2i)]
2 ieN Brisupp()))
there exists M > O such that if yiu; yia, > M for all * af E A; and e N, then
Dia; Via; (2(g)) - Via, (Q(v)) > for all a; * oj A, and N.
(C.21)
For notational convenience, focus player and drop the player-specific indices altogether. Let a + a E A, and define for n E N the quantities Wan and Za.n as
Wa.n == (Pn. fu ea), Za. == (yn ca - eer)
(C.22)
where ca e are the standard basis vectors corresponding to a, a' E A.
Let initial conditions y1 such that ya,1 Yor.1 = -M - for all a # o² E A. where & > 0 small, and Pı = O. We will first show by induction that Zar. for all n N. To this end, unfolding the recursion, we obtain:
Wan++ Wa.n + ((0ns ea - e'g)
Wa.n + 7(((xn) la e'a)
= - (o(x)) E()
(C.23)
where we used that = 0. Now, for the sake of induction, suppose that
Za.k < -M for all k = I,...,
(C.24)
which implies that (u(xx). ca e'r) cc With this in hand, we will prove that zan+1 < <M,, as well. Specifically, we have:
Za,+11 Za.n + yWa.++ = Za.n + x²
Σ
(xxx))ee-ee
k=l
$ Ea,n cy²n
$ ca.1 - cy
Σ
[=1
< <-M
(C.25)
where we used the inductive hypothesis and the initial condition. Therefore, we conclude by induction that Za.n <-M for all I. Thus, we readily obtain that after T time-step:
T-1 Ees cy T(I
2τ S 2a.1 cc²
(C.26)
2
2=1
and invoking Lemma A.1 for 0(x) x log.x, we get the result.
D Proofs for discrete-time algorithms with partial information
In this appendix, provide the proofs of Theorem 3 and Theorem 4 that correspond to the con- vergence of (FTXL) with realization based and bandit feedback, respectively. For this, we need the following lemma, which provides maximal bound martingale process. Namely, have:
Lemma D.1. Let M, == Σk=n Y&εR be martingale with respect to (Fn)nen with [[]] o for some q > 2. Then, for μ E (0, 1) and n
n
9/2+1 Yk
of 1+9
P supl supl ksn
>
Σ
S Aq
(D.1)
(1/21)
7k)
where Ag is constant depending only on and q.
20

---

Proof. Fix some e (0, 1). By Doob's maximal inequality [20, Corollary 2.1], we have:
El 19] <9
P
Mup|
c
Σ
Yk
(E )
(D.2)
Asn
k=1
Now, applying the Markholder-Davise Gundy inequality [20, Theorem 2.10], we get that
9/2
B[|M,| & Aq E
Σ r 1
(D.3)
where Ag is constant depending only on c and q. Now, we will invoke the generalized Hölder's inequality [4], have:
p-1
Σ k=1
aabb
Σ k=1
(1-A)P
be
(D.4)
k
k
k=l
for ak. by 2 20, p0 p >
and E [0, 1). Thus, setting ag = xz by = 11 = 9/2 and 1/2 1/4.
(D.2), combined with (D.3), becomes:
n
1
[ik=l yk.
72) 9/2-1
2 72
9/2+1
E [1]
supl > kmn
Σ
Yk
S Aq
(Σ 7k)
Σ 7k
9/2+1
ok
$ Aq
(D.5)
119(/-1122)
(>%==1 7k)
and our proof is complete.
With this tool in hand, proceed prove the convergence of (FTXI.) under realization-basee feedback. For convenience, we restate the relevant result below.
Theorem Let x² be a strict Nash equilibrium of r, fix some confidence level > and let Xn Qyy be the sequence of play generated by (FTXL) with realization-based feedback per (11b) and sufficiently small step-size y > Then there exists a neighhorhood of x" such that
P(xn +x x as - 0o) 2 1-
if E U.
(14)
In particular, (FTXL) is run with logit best responses (that is, Q A), there exist positive constants C, c > O as in Theorem 2 such that on the event (Xn - xxx" as n - oo);
||x--x - 1b S exp(ccoy> T(T- 3 2 exp(-o(T3)).
(15)
First of all, since x" is strict Nash equilibrium, by Lemma B.1 for Proof.
1 min min (x;(x/xx",) =x(Bxxx2,] c= 2 ieN Bresupp(x))
there exists M > O such that if yoa; yia M for all # oz e Ai and i e A, then
Dia (Q())) Dia, (0())) > for all a; # af e A,, and i e N.
(D.6)
For notational convenience, focus player and drop the player-specific indices altogether. Let a # a' E A, and define for n E N the quantities Wa.n and Za,n as
Wa,n (pn. ea e'a) Za,n (yn, ear -ea)
(D.7)
where ca cx, are the standard basis vectors corresponding to a. E A. Then, unfolding the recursion, we obtain:
W Wo, Wa,n + ((n, ear eaa)= wann y(0((a), + ecd)
-x))))
(.) + > (Uk.ea Eir)
(D.8)
k=1
k=
21

---

where we used that = 0. Now, define the stochastic process (Mn as
" M, = Σ
(k. ea)
(D.9)
k=1
which is martingale, since EiU, [in] 0. Moreover, note that
||,, [Ib(a,) - u(xx)ll S maxl]
(D.10)
aeA
and, thus, readily obtain that E| Fi. s 04 for 2 allaael and all q E [1,00].
By Lemma D.1 for Yn y. On = o, e (Un, la ea), in Theorem 2, and μ (0, 1). > 2 whose values will be determined next, there exists Aq 0 such that:
nyd/2+1
8, == P M c(yn)
Ano
(yn) (-90(11111
ksn
y²(1==)
S Ago n9(1-1122
(D.11)
Now, we need to guarantee that there exist (0, 1), > 2, such that
Σ 6n < 00
(D.12)
For this, simply need q(u 1/2) 1. equivalently, μ 1/2 1/q. which implies that μ E (1/2, l).
Therefore, for small enough, we get M 6n < 6, and therefore:
P
8
MaI
c(yn)u
=1 - P
supl Mel > c(m))
kin
Akn
8n
==1 2 6
(D.13)
From now on, we denote the good event Of (sup S c(yn)") by E. Then, with probability at least 1 6:
Wa.n+1 s (o(x)), e'a) + clyn)" for all N.
(D.14)
Furthermore, we have that for No = [1/y], we readily get that yn (yn)". Therefore, setting
R = cy
(D.15)
we obtain:
cy (yk (yk (yk)²)
(D.16)
for all n N. Then, initializing y1 such that 2a.1 <-M we will show that Za.n <- for all E IN with probability at least - 6. For this, suppose that E is realized, and assume that
Za.k <- for all 1....,n
(D.17)
We will show that 2a. -M, well. For this, we have:
Ean+t1 = Za.n + yWa.tt
$ zan + y Σ
(u(x)),e - - ) + c(yn)"
k=l
22

---

Proof. First of all, since x" is a strict Nash equilibrium, by Lemma B.1 for $ Stan Cocyn-e (yn)4)
2zal - cy Σ (yk (yk)*)
$ -M - R cy Σ (yk - (yk)")
k=1
< M
(D.18)
Therefore, we conclude by induction that Za,n < -M for n IN Thus, we readily obtain that with probability least 1 6 holds:
Za.7 S 2a.1
cy
(yk (yk)
k=1
T(T 1)
+ ey 1p ("" dd
2n,1 cy
2
$ 2a.1 cy² T(T 11)
+ cyylH lt Tu+1
(D.19)
2
H
for all T N. Setting μ = =233 and invoking Lemma A.I for ((x) x log x, we get the result.
Finally, we prove the convergence of (FTXL) with bandit feedback. Again, for convenience, we restate the relevant result below.
Theorem 4. Let x' be strict Nash equilibrium of T, fix some confidence level 8 > O, and let Xn (yn) be the sequence of play generated by (FTXL) with bandit feedback of the form (11c), an IWE exploration parameter En x 1/n for some le E (0, 1/2), and a sufficiently small step-size
y > O. Then there exists a neighborhood of X such that
P(xn xx
2 6
if E U.
(17)
In particular, if (FTXL) is run with logit best responses (that is, Q + A), there exist positive constants C, 0 in Theorem 2 such that on the event (In +xx' as n co)
||xy x010 S exp/ c- T(T-TT--)) -1) 5 ( exp(-O(Tt))
(18)
2
1 min min (x/(x)=>))) u;(Bxx2;)
c= 2 ieN Bresupp(x))
there exists M such that if y/a; yi M for all a; # oj A, and i e N, then
Dio; Via; (Q())) Via, (Q(v)) > for all a; # aj e A,, and M.
(D.20)
For notational convenience, focus player and drop the player-specific indices altogether. Let a a" A, and define for n N the quantities wann and Za,n as
Wann (pn.e. e',), Za,n (yn,ea -
(D.21)
where ca eú, are the standard basis vectors corresponding to a, a E A. For notational convenience, we focus on player i and drop the ppayer-specific indices altogether. Now, decomposing the IWE ön we obtain
0, v(xx) + Un + bn
(D.22)
where U, := in 0z (f,)) is zero-mean noise, and b == (& (z(xx).
Then, unfolding the recursion, we obtain:
Wan+t1 = Wa,n Kineea-ce
= Wan + y(o(xn), Ca - e')) + (Unn - + (bbn
S Wan y(((x)).ea ca)) + (U c')) + 2yl|bnll.
23

---

y (u(xk),er ea -6a) + + Σ
(Uk, ca - -ea) -a)++ + +2y Σ lbbxll
k-1
k-1
$ y
Σ (u(xe),eo ea e + (Ukie - + B Σ
&k
(D.23)
k=1
Rml
R=1
where we used that [|b,||. (&x) for all n E N. Now, define the process {Mn]nen as
M, =
eu -ea)
(D.24)
k=1
which is a martingale, since ElU, F = Moreover, note that
n ||O, - =(,,) |1+ - ||0, + [I0(
(D.25)
i.e. ||,, = ((1/8,) Thus, we readily obtain that [[[ 7n FFl Σ 0 for on (((/e,) and all E co]. So, by Lemma D.1 for yn = y, n = as in Theorem 2, and μr e (0, 1). > 2 whose values will be determined next, there exists Ag 0 such that:
Ag /a/241 2 k=1 kk (yn)l+q(u111))
6n P Mup| ken
2 (yn)"
ya(1-H) H)) k= o
Ag
(D.26)
n1tg(011/2)
Now, note that for 6n = g/n'e, and since on = ((1/En) we get that there exists M > 0 such that
a k96
9 s Ma
(D.27)
with -x=1 k0Cz = (al)) Therefore,
5n A y4 1) 8 nn -
n 11t4(11112)
y9(1-H) 8-
I A n9(m-1/2-(e)
(D.28)
Now, we need to guarantee that there exist (0, 1), > 2, such that
Σ 8n < 00
(D.29)
For this, need to ensure that q(H 1/2 (g) or, equivalently,
l f 1/2 1/4
(D.30)
which we will do later. Then, we will get for y small enough:
P supl
C Mxl
2 (ym))
= - P
U
supl SuplM2l>> > {(mn)()
n=1
Usnn
Iknn
60 Σ 5n
>
(D.31)
Regarding the term 2yB Σm= &t in (D.23), we have that:
By
Σ
6k
28ys
Σ k le
BD B'y I-c
(D.32)
k=1
k=
where we used that ΣØ -fc ((n)-c)) Thus, for
- le
(D.33)
24

---

we have for e, > 0 small enough:
B Σ Ek S B' yen' s B'nn
$ (yn)*
(D.34)
2
k=1
for all n N. Hence, by (D.30), (D.33) we need the following two conditions to be satisfied:
1 1 1 l. and le <
(D.35)
2 4
for which get that for le E (0, 1/2), there exists always μ (3/4, 1) and q large that satisfy (D.35). Thus, combining (D.34) and (D.31), we get by (D.23) that with probability at least - 6:
Wa,n+1 S Σ re(loss).e-- - en) c(yn)" for all E
(D.36)
Thus, following similar steps as in the proof Theorem after (D.14), we readily obtain that with probability at least 1 6, we have:
T-1 (yk (yk)
Za. Zu.1 cy Σ
k-1
Zu.1 - cy T(T 1)
+ cyl ("
d'
(D.37)
2
j0
Ea,1 cy² T(T 1)
2 cy 1t TH+1
#+1
(D.38)
for all T N. Setting μ 4/5 and invoking Lemma A.I for ((x) x log x, our claim follows.
E Numerical experiments
In this section, we provide numerical simulations to validate and explore the performance of (FTXL). To this end, we consider two game paradigms, (i) zero-sum game, and (ii) a congestion game.
Zero-sum Game First, we consider 2-player zero-sum game with actions {ar, 02 0rz) and (Bi, B2, Bs}, and payoff matrix
(2 (1,-1) (2.-2)
P (-2,2)
(-1.1)
(-2,
(-2,2)
(-1,1)
(-2,2)
Here, the rows of P correspond the actions of player A and the columns to the actions of player B, while the first item of each entry of P corresponds to the payoff of A, and the second one to the payoff of B. Clearly, the action profile (a1,8)) B2) is strict Nash equilibrium.
Congestion Game, As second example, we consider congestion game with N 100 and roads, ri and r2, with costs C₁ 1.1 and C2 d/N where d is the number of drivers on 72. In words, TI has fixed delay equal 1.1, while r2 has delay proportional to the drivers using it. Note, that the strategy profile where all players are using 12 is strict Nash equilibrium.
In Fig. 1. assess the convergence of (FTXL) with logit best responses, under realization- based and bandit feedback, and compare it to the standard (EW) with the same level of information. For each feedback mode, the average norm ||x, - x'Ili as a function of the iteration counter n = 1, T. The solid lines represent the average distance from equilibrium for each method, while the shaded areas enclose the range of +1 standard deviation from the mean across the different trials. All the plots are displayed in logarithmic scale. For the zero-sum game, all runs were initialized with y1 O. and we used constant step-size y = 10-2, and exploration parameter & 10-1, where applicable. For the congestion game, the initial state Y/ for each run was drawn uniformly random in [-1, 1 and we used constant step-size y 10-2, and exploration parameter 8, 1/4 where applicable.
conducted 100 separate trials, each with T = 10 steps, and calculated
The experiments have been implemented using Python 3.5 on a M1 MacBook Air with 16GB of RAM.
25

---

F Connection with other acceleration mechanisms
In this appendix, we discuss the connection between (FTXL) and the "linear coupling" method of Allen-Zhu & Orecchia [1]. Because [1] is not taking momentum-based approach, it is difficult to accurately translate the coupling approach of [1] to our setting and provide a direct comparison between the two methods. One of the main reasons for this is that [1] is essentially using two step-sizes: the first is taken equal to the inverse Lipschitz modulus of the function being minimized and is used to take a gradient step; the second step-size sequence is much more aggressive, and is used to generate an ancillary, exploration sequence which "scouts ahead". These two sequences are then "coupled" with mixing coefficient which plays role "similar" but not equivalent the friction coefficient in the (HBVF) VF) formulation of (NAG) by Su et al. [40].
The above is the best high-level description and analogy we make between the coupling approach of [1] and the momentum-driver analysis of Su et al. [40] and/or momentum analysis Nesterov's 2004 textbook. At low level (and omitting certain technical details and distinctions that central to this discussion), the linear coupling approach of [1] applied to our setting would correspond the update scheme:
Xn = ((yn
Wn = Zn + (1 2n
Un+1 = yn (1 An)mnnn
Zn+1 = Anān + (1 -1- An))x=1
with én obtained by querying a first-order oracle at Wn that is. én an estimate, possibly imperfect, of v(w)). The first and third lines of this update scheme are similar to the corresponding update structure of (FTXL). However, whereas (FTXL) builds momentum by the aggregation of gradient information via the momentum variables pu. the linear coupling method above achieves acceleration through the coupling of the sequences Wn. 2n and X,, and by taking an increasing step-size sequence Ta that grows roughly (n), and a mixing coefficient An that evolves as A, = (L))), where is the Lipschitz modulus of v(.). Beyond this comparison, we cannot provide a term-by-term correspondence between the momentum-based and coupling-based approaches, because the two methods are not equivalent (even though they give the same value convergence rates in convex minimization problems). In particular, we do not see way of linking the parameters 7/n and A, of the coupling approach to the friction and step-size parameters of the momentum approach.
In the context of convex minimization problems, the coupling- based approach of [1] is more amenable to a regret-based analysis this is the "unification" aspect of [1] - while the momentum-bies based approach of Su et al. [40] facilitates Lyapunov- baaedd analysis. From game-theoretic standpoint, the momentum- based approach seems be more fruitful and easier to implement, but studying the linear coupling approach of [1] could also be very relevant.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: It can be found in Section 3, Section 4 and the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
It can be found in Section 1.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-speeification, asymptotic approximations only holding locally). 'he authors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-tee seecchtt-ttett system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best judgment and recognize
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: It can be found in Section 2, Section 3, Section 4 and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
27

---

All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely. any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: It can be found in Appendix E, and the code is included in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e-g.. in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code. the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g., a large language model), then there should either be a way to access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which authors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code included the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc/publ) gui Tites/CCoeSubblee www.ooosssoooooooooooooooo aeiiionoolyyy for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for open-source benchmark).
28

---

The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://nips.
gui quides/CCoeSubmi ssi sssssssooooooo onPoliiie cy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: It can be found in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: No statistical significance applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eтrоrs not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If eтror bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
Justification: It can be found in Appendix E.
Guidelines:
29

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact. Guidelines:
The answer NA means that there is no societal impact of the work performed. If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
There are such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
30

---

Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, possible, include a URL..
The name of the license (e.g., CC-BY 4.0) should included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ com/datasets datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information not available online, the authors are encouraged reach out the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should included in the main paper.
31

---

According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
32


Reviews:
[{"review_id": "eSWrId8iuI", "reviewer": "Reviewer_yttq", "summary": "This paper primarily focuses on introducing a Nesterov's accelerated gradient (NAG) algorithm for online learning in games.\nInitially, the author shows that a continuous-time version of NAG converges to a strict Nash equilibrium at a rate that is quadratic.\nThis rate of convergence is notably faster than that of standard FTRL algorithms.\nFollowing this, the paper demonstrates that the convergence rate of NAG is preserved even in a bandit feedback setting.\nThe experimental results confirm that the proposed algorithm converges to an equilibrium more quickly than a FTRL algorithm.", "questions": "My major concerns and questions are stated in Weaknesses.\nI also have the following additional questions:\n* Why is the update rule of $y_{i,n+1}=y_{i,n}+\\gamma p_{i,n+1}$ in (FTXL) derived? Looking at the original NAG's update rule in (NAG), it seems more natural that $y_{i,n+1}=y_{i,n}+\\gamma (p_{i,n+1}-p_{i,n})$.\n* Is it possible to recover FTRL algorithms by setting $r$ appropriately in FTXL?", "limitations": "I see no negative societal impacts that need to be addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Despite the significant importance of introducing Nesterov's accelerated gradient, a method highly esteemed in convex optimization problems, into the context of learning in games, such an approach has not been pursued until now.\n* The intuition behind the proposed method is thoroughly explained. Furthermore, the proposed algorithm appears to be straightforward to implement.\n* The derived convergence rates are confirmed to be tight by deriving the exact convergence rate in a simple instance.", "weaknesses": "My primary concern is that the theoretical results are only applicable to games with a strict Nash equilibrium.\nThis is somewhat problematic as even in a simple game like rock-paper-scissors, a strict Nash equilibrium does not exist.\nMoreover, the convergence in games that do not have a strict equilibrium has been the subject of extensive research.\nTherefore, I'm wondering how efficient NAG algorithms are in two-player zero-sum games and monotone games.\n\nFurthermore, Theorems 1, 2, 3, and 4 hinge on the presumption that the initial strategy is in close proximity to an equilibrium.\nCould you provide some insight into how close the initial point needs to be to the equilibrium?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer yttq,\n\nThank you for your input. For your convenience (and that of the committee), we reproduce and reply to your comments below one-by-one.  \n\n[**Note:** all bibliography reference numbers are as in our paper]\n\n> Results are only applicable to games with a strict Nash equilibrium. [...] Therefore, I'm wondering how efficient NAG algorithms are in two-player zero-sum games and monotone games.\n\nThere are several points here – related, but distinct:  \n1. *On the lack of strict equilibria.* We should begin here by stating that, by the impossibility theorem of Hart & Mas-Colell [17], there are no uncoupled learning dynamics that converge to Nash equilibrium in *all* games. In this regard, at least *some* assumption needs to be made in order to have a hope of converging to a Nash equilibrium.  \n\n    Our focus on games with strict Nash equilibria is motivated by the results of [14] which state that, in the presence of uncertainty – i.e., with anything other than full, perfect information – ***only*** strict Nash equilibria can be stable and attracting with high probability. In particular, if a game does not possess a strict equilibrium, the sequence of play generated by regularized learning schemes provably fails to converge with positive probability. Thus, given that we are interested in robust convergence results that continue to hold in the presence of uncertainty, the focus on strict Nash equilibria is, in this sense, unavoidable.  \n    \n2. *On zero-sum games.* A first point here is that zero-sum games may well admit strict equilibria, in which case our results apply verbatim -- for example, consider the min-max payoff matrix $[0 \\quad 1; -1 \\quad 0]$. In general zero-sum games, it can further be shown that FTXL identifies the *support* of the set of Nash equilibria of a zero-sum game at a quadratic, superlinear rate – though, in view of the discussion above, high probability convergence to equilibrium under uncertainty should not be expected if the support is not a singleton (e.g., as in RPS). [We did not include this more specialized result because it was beyond the scope of our submission, but we will be happy to include the above discussion in the first revision opportunity.]\n\n    Finally, even though there is an extensive literature on (usually optimistic) regularized learning methods that converge to equilibrium in zero-sum games with fully mixed Nash equilibria, it should be noted that these results typically concern learning with full, *perfect* information, as per model (10a) in our paper. These results are inherently deterministic and collapse in the presence of persistent randomness and uncertainty, see e.g., https://arxiv.org/abs/2206.06015 or https://arxiv.org/abs/2110.02134, so it is in general quite difficult to achieve convergence to Nash equilibrium without full information in zero-sum games.\n\n3. *On monotone games.* Monotonicity is a condition that primarily concerns continuous games, that is, games with a finite number of players and *continuous* action spaces. By contrast, our paper focuses throughout on *finite* games: the mixed extension of a finite game may indeed be seen as a continuous game, but the players' (mixed) payoff functions are necessarily multilinear in their strategies. As a result, except for trivial cases (like the zero game), *only* two-player games can be monotone, and this only if the players' payoff matrices satisfy very specific conditions that ultimately make the game strategically equivalent to a zero-sum game. The extension of FTXL to (monotone) games with continuous action spaces is a very interesting one, but this is otherwise a completely different framework which lies well beyond the scope of our work.\n\n> Could you provide some insight into how close the initial point needs to be to the equilibrium?\n\nThe determining factor is the minimum payoff difference $d$ at an equilibrium $x^*$ as per Eq. (B.1) of our paper. The neighborhood in question is roughly $\\mathcal{O}(d)$ in $L^1$ diameter, and it is essentially determined by the equation $u_i(x_i^*;x_{-i}) - u_i(x) \\geq d/2$. We provide the relevant details in p.13, Lemma B.1 in Appendix B, and we will be happy to transfer the corresponding expressions to the main body of the paper. \n\n> Why is the update rule of $y_{n+1} = y_n + \\gamma p_{n+1}$ in (FTXL) derived? [...] It seems more natural that $y_{n+1} = y_n + \\gamma (p_{n+1} - p_n)$\n\nThe update rule in (FTXL) is derived by setting $p_n = (y_n - y_{n-1})/\\gamma$ in (9), which is the direct discretization of (FTXL-D), the game-theoretic analogue of (HBVF). [Put differently, mutatis mutandis, (FTXL) is related to (FTXL-D) in the same way that (NAG) is related to (HBVF).] In our original submission, we had devoted Section 3 to provide a detailed discussion on the connection of (FTXL-D) with (NAG) and (HBVF), along with the intuition behind it, referring to the paper of Su, Boyd and Candès for the detailed relation between (HBVF) and (NAG). We will be happy to take advantage of the extra page in the revision to include the details of the link between (HBVF) and (NAG)  for completeness.\n\n> Is it possible to recover FTRL algorithms by setting $r$ appropriately in FTXL?\n\nThat's an interesting question. We tried to find a way to see if it's possible to express FTRL as a limit case of FTXL, but we didn't find one.\n\n---\n\nPlease let us know if you have any follow-up questions, and thank you again for your time!\n\nKind regards,\n\nThe authors", "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": "", "extra_scores": {}}, {"review_id": "rib2tABPkP", "reviewer": "Reviewer_qtGD", "summary": "The paper proposes a momentum-based follow-the-regularized-leader (FTRL) type algorithm for finding the Nash equilibrium in finite games. The paper first investigates the continuous second order ODE and a concrete game, and then devises the appropriate FTRL scheme. The convergence rate for the proposed algorithm in all three information settings of reward is quadratic (O( exp(-T^2))).", "questions": "Minor comments\n1. Are lower bounds of learning a finite game with the three kinds feedbacks known? If so, it would be great to provide a survey.\n2. In line 305 the phrasing \"second-order in space\" is a bit confusing. In my opinion, it would be better to say \"using Hessian information of relevant functions\".\n\nTypo \n1. At Eq FTRL, near line 131, the second equation should be x_i,n = Q_i (y_i, n).", "limitations": "The paper provides a extensive discussion of momentum method for finite game solving, and does not have major limitations in my opnion.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. A rich collection of results on momentum methods for finite-games. The paper has three sets of theoretical results. First, convergence results for the second-order ODE dynamics with vanishing friction (Theorem 1) and non-vanishing friction (Theorem B.1), both under the logit best response. Second, an analysis of a momentum FTRL under full information on a concrete one-player game with vanishing (Prop C.1) and non-vanishing friction (Prop C.2). And finally, analysis momentum FTRL with three kinds of info feedback. \n\n2. The paper discovered an important phenomenon that, in the continuous second order ODE, \"the friction term hinders convergence\". This claim is backed by a concrete analysis of momentum FTRL on a concrete game. In my opinion this phenomenon is interesting to the game learning community.\n\n3. The writing is flowing and smooth.", "weaknesses": "See question.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer qtGD,\n\nThank you for your overwhelmingly positive evaluation and constructive comments. We reply to your questions below:\n\n> Are lower bounds of learning a finite game with the three kinds feedbacks known? If so, it would be great to provide a survey.\n\nThe closest lower bounds that we're aware of are algorithm-specific, e.g., as in the paper of Giannou et al. [15] where the authors argue (but do not prove) a geometric lower bound for FTRL with full information feedback, which is also achieved by FTRL with bandit feedback (so it is tight for both models). We fully share the reviewer's point of view but, regrettably, we are not aware of a more general lower-bound analysis as in the case of convex minimization.\n\n> In line 305 the phrasing \"second-order in space\" is a bit confusing. In my opinion, it would be better to say \"using Hessian information of relevant functions\".\n\nPoint well taken, we will adjust the phrasing accordingly to make sure there is no confusion.\n\n> At Eq FTRL, near line 131, the second equation should be x_i,n = Q_i (y_i, n).\n\nOh, great catch, many thanks - will fix!\n\n\n---\n\nPlease let us know if you have any follow-up questions, and thank you again for your time and overwhelmingly positive evaluation!\n\nKind regards,\n\nThe authors", "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": "", "extra_scores": {}}, {"review_id": "6F9Tznsrqx", "reviewer": "Reviewer_3QUL", "summary": "The submission studies the convergence of finite N-person games. Combining the idea of (NAG) and (FTRL), the submission proposes a continuous-time dynamic (FTXL-D) and its discrete-time scheme (FTXL). The novelty of integrating momentum and regularization into an algorithm allows the construction of quadratic rate methods.", "questions": "- In line 245, the friction parameter is set to zero ($r=0$) according to the discussion of Example 3. This setting, by direct substitution, would cancel out the desired effect of the momentum in (FTXL-D) in line 186 or (4) in line 197. However, in (FTXL) (line 258), the momentum appears to play an important role in the leftmost equality $y_{n+1} = y_n + \\gamma p_n$. Did I misunderstand something?\n- In Figure 1, why does FTXL perform poorly in the early rounds? Is it due to the constants in the bound or is there another reason?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- A novel viewpoint that uses (HBVF)’s interpretation to link (NAG) and (FTRL-D) to form (FTXL-D).\n- Improved converge rates from linear to quadratic are shown in Theorems 1 – 4. Theorems 2 – 4 cover common practical scenarios.\n- Clear comparison between the proposed method and the previous methods, especially at the intuition level.\n- Pinpoint the critical term to focus on the technical details (U in Theorem 3). This greatly increases the time to understand the analysis.\n- Rigorous analysis is provided in the Appendix.", "weaknesses": "- A smoother transition toward (FTXL-D) in lines 182–186 is desired. In a game, $x$ is the response and $y$ is an aggregated payoff. For (HBVF), the interpretation is for a moving object. \n  - What is the correspondence of $x$ and $y$ of a game in (HBVF)? Do we correspond $x$ (position) in (HBVF) to $y$ (payoff) in a game? If so, what corresponds to the response ($x$ in a game) in (HBVF)? Is it the control $w$ (my naive guess)? \n  - These analogs, with the aid of a clearer transition, would help us to better understand the first paragraph of Section 3.2. Maybe the response x in a game and the position x in (HBVF) introduces a bit of confusion, too? \n- There are two sets of notations, one for the continuous-time regime and the other for the discrete-time regime. A small table to distinguish them might help the readability.\n- Although in general, the submission is easy to read, a minor aspect of improving readability could be explaining the meaning $\\dot{y}$ (lines 192 and 196) and $\\ddot{z}$ (line 486), which could ease the reading barrier for people who are more comfortable with discrete-time analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 3QUL,\n\nThank you for your strong positive evaluation and constructive comments! We reply to your questions below:\n\n> A smoother transition toward (FTXL-D) in lines 182–186 is desired. [...] What is the correspondence of $x$ and $y$ of a game in (HBVF)? [...] These analogs, with the aid of a clearer transition, would help us to better understand the first paragraph of Section 3.2. \n\nThe key insight here is that, in the case of regularized learning, the algorithm's latent, state variable – that is, the variable which determines the evolution of the system in an autonomous way – is the \"score variable\" $y$, not the \"strategy variable\" $x$ (which is an ancillary variable obtained from $y$ via the regularized choice map $Q$). In particular, this means that, even though results are stated in terms of the strategy variables $x$ (which are the primary objects of interest), the true state variable of the algorithm's iterative structure is $y$, not $x$. Put differently, the $x$ in (NAG) and (HBVF) should be compared and contrasted to $y$ in (FTXL), not $x$.\n\nWe made this choice of notation to be as close as possible to the work of Su, Boyd and Candès, but we understand that it may have occluded intuition. We will make sure to update the presentation here and provide more details along the above lines at the first revision opportunity.\n\n\n> There are two sets of notations, one for the continuous-time regime and the other for the discrete-time regime. A small table to distinguish them might help the readability.\n\nThis is a great idea, thanks! We were (very sharply) constrained for space in the original submission, but we will be happy to take advantage of the extra page to include such a table. Thanks for the suggestion!\n\n\n> Although in general, the submission is easy to read, a minor aspect of improving readability could be explaining the meaning of $\\dot y$ (lines 192 and 196) and $\\ddot z$ (line 486), which could ease the reading barrier for people who are more comfortable with discrete-time analysis.\n\nPoint well taken. We will include a note about this, and also make a reference to it in the proposed table of notation above.\n\n\n> In line 245, the friction parameter is set to zero ($r=0$) according to the discussion of Example 3. This setting, by direct substitution, would cancel out the desired effect of the momentum in (FTXL-D) in line 186 or (4) in line 197. However, in (FTXL) (line 258), the momentum appears to play an important role in the leftmost equality $y_{n+1} = y_n + \\gamma p_n$. Did I misunderstand something?\n\nThe desired effect of the momentum in (FTXL-D) – but also (NAG) and (HBVF) – is not the friction term, but the fact that the system is second-order in time, so the effects of the momentum are \"baked in\" the algorithm's update structure. The friction term $r\\dot x$ (or $r\\dot y$) has a \"dampening effect\" intended to mitigate the algorithm overshooting a desired state.\n\nWe hope this is clearer now, please let us know if we missed or misunderstood something in your question!\n\n\n> In Figure 1, why does FTXL perform poorly in the early rounds? Is it due to the constants in the bound or is there another reason?\n\nThe reason is that the algorithm is building up momentum in the initial iterations, much like uniformly accelerated motion (like pushing a crate with constant force): the algorithm starts at zero speed and is initially slow, but as it gains more and more momentum, it rapidly accelerates and gains more speed and momentum, which is ultimately responsible for the method's quadratic convergence rate. In this analogy, FTRL would correspond to uniform motion – always moving at \"constant\" speed, so it is faster in the initial iterations, but much slower overall since there is no momentum build-up.\n\n---\n\nThank you again for your strong positive evaluation and encouraging remarks – and please let us know if you have any follow-up questions!\n\nKind regards,\n\nThe authors", "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": "", "extra_scores": {}}, {"review_id": "A8IOsrCXPo", "reviewer": "Reviewer_sdz4", "summary": "The paper studies the extension of Nesterov’s accelerated gradient algorithm to the solution of N-player games, named \"follow the accelerated leader\" (FTXL). The method is studied in both continuous and discrete time, and under various information oracles. The convergence of the algorithm is super-linear when started from an initialization close enough to the NE. Simulations are conducted which confirms the accelerated convergence numerically.", "questions": "Please see Weaknesses section.", "limitations": "Paper of theoretical nature. No negative social impact is foreseeable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well-written and well-motivated. The core contribution, which is the accelerated algorithm with local super-linear convergence, is clearly presented, novel, and significant to my knowledge. That the method works under different information oracles, especially bandit feedback, is also important. \n\nDespite the simplicity, the simulations do numerically verify the accelerated rate established in theory.", "weaknesses": "The convergence of FTXL in all settings requires sufficiently close initialization or has to do with the neighborhood $\\mathcal{U}$. The exact definition of \"sufficiently close\" or this neighborhood is not given in the main paper. I believe this should be added in the statement of the theorems for clarity. The authors should also discuss how realistic it is that the initial point satisfies the requirement (and/or how likely the iterates of FTXL or FTRL may run into this \"good neighborhood\").\n\nIt seems that no assumption on the convexity of the payoff function is made. With a general non-convex payoff function, I wonder what is the problem structure and technical apparatus that allow the authors to derive the quadratic convergence (or even convergence at all). This is currently not sufficiently discussed in the main paper. While I am happy to study the detailed analysis, I would appreciate a sketch of the proof which highlights the main techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer sdz4,\n\nThank you for your positive evaluation and constructive comments! We reply to your questions below:\n\n> The convergence of FTXL in all settings requires sufficiently close initialization or has to do with the neighborhood. The exact definition of \"sufficiently close\" or this neighborhood is not given in the main paper. I believe this should be added in the statement of the theorems for clarity. The authors should also discuss how realistic it is that the initial point satisfies the requirement (and/or how likely the iterates of FTXL or FTRL may run into this \"good neighborhood\").\n\nThe determining factor for the basin of attraction of a given equilibrium $x^*$ is the minimum payoff difference $d$ at equilibrium, as per Eq. (B.1) of our paper. The neighborhood $\\mathcal{U}$ in question is roughly $\\mathcal{O}(d)$ in $L^1$ diameter, and it is essentially determined by the equation $u_i(x_i^*;x_{-i}) - u_i(x) \\geq d/2$. We provide the relevant details in p.13, Lemma B.1 in Appendix B, and we will be happy to transfer the corresponding expressions to the main body of the paper.\n\nAs for the likelihood of (FTXL) being captured by the basin of attraction of a given equilibrium, this depends on the existence or not of non-equilibrium attracting sets – such as the heteroclinic limit cycle in Jordan's matching pennies, which is universally attracting under the replicator dynamics, that is, the first-order version of (FTXL) with entropic regularization. In typical coordination / anti-coordination scenarios, the state space of the game is partitioned into basins of attraction of different strict equilibria, so convergence is almost surely guaranteed. Otherwise, if there are non-equilibrium attracting (or chain-recurrent) sets, we conjecture that (FTXL) could be captured by a spurious attractor on the boundary and fail to converge (as in Jordan's matching pennies). To the best of our knowledge, there is no theory providing a  coherent characterization of when such spurious attractors may arise in finite games; this is a very difficult problem on which very little progress has been done since the 1950's, so we cannot provide more insights here.\n\n> It seems that no assumption on the convexity of the payoff function is made. With a general non-convex payoff function, I wonder what is the problem structure and technical apparatus that allow the authors to derive the quadratic convergence (or even convergence at all). This is currently not sufficiently discussed in the main paper. While I am happy to study the detailed analysis, I would appreciate a sketch of the proof which highlights the main techniques.\n\nPlease note that our paper focuses throughout on *finite* games in normal form, so the players' payoff functions are, de facto, multilinear in the players' mixed strategies – and, in particular, linear in each individual player's strategy. In the case of *continuous* games – that is, games with a finite number of players and a *continuum* of actions per player – things are dramatically different, especially if (as you suggest) there are no individual convexity assumptions made on the players' payoff / cost functions. The extension of FTXL to continuous games (possibly with a monotone structure) is a very fruitful research direction, but it would require a drastic departure from the finite game setting of the current paper, so it lies well beyond the scope of our work.\n\nNow, going back to our particular setting, the basic insight is that strict Nash equilibria have a \"sharp\" variational characterization, in the sense that the players' payoff vector lies in the interior of the normal cone to the point in hand (akin to Polyak's notion of sharpness for minimization problems). This allows the buildup of significant momentum accelerating the algorithm, and since strict equilibria are extreme points (all positivity constraints are saturated except one, owing to the simplex equality constraint), there is no danger of overshooting the point in question. This is the reason that the lack of friction does not hinder convergence – and, of course, it is inextricably tied to the (multi)linear structure of finite games and their strategy domains. We will of course be happy to take advantage of the extra page of the first revision opportunity to describe all this in more detail and provide a technical roadmap of the proof.\n\n---\n\nPlease let us know if you have any follow-up questions, and thank you again for your time and positive evaluation!\n\nKind regards,\n\nThe authors", "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": "", "extra_scores": {}}]

Author rebuttal:
Dear reviewers, dear AC,  

We are sincerely grateful for your time, comments, and positive evaluation!  

To streamline the discussion phase, we replied to each of your questions and comments in a separate rebuttal below, and we will of course integrate all applicable points in the next revision opportunity.  

Thank you again for your input and encouraging remarks, and we are looking forward to a continued constructive exchange during the discussion phase.  

Kind regards,  

The authors

Meta-review: This paper considers the problem of learning in games. The main result is to provide a general family of algorithms called *follow the accelerated leader (FTXL)* which incorporates acceleration into the FTRL framework, and achieves a speedup over vanilla FTRL under various feedback structures.


Reviewers generally agreed that this paper makes a solid and clear contribution by integrating Nesterov-style acceleration into learning in games, and is likely to inspire further work in this direction, meriting acceptance. They also found the paper to be clear and well written.


A minor comment for the final version: The authors use the term "quadratic rate" to refer to exp(-T^2) convergence (or \sqrt{\log(1/eps)} iteration complexity to achieve precision \eps). This is different from the typical use of the term in optimization (e.g., in the context of Newton's method), where quadratic convergence typically refers to exp(-exp(T)) or \log\log(1/eps) convergence. I recommend using another term to avoid confusion here.
Decision: Accept (poster)