Near-Optimal No-Regret Learning in General Games
Authors: Constantinos Costis Daskalakis
Maxwell Fishelson
Noah Golowich
Venue: NeurIPS 2021 Oral (2021)
Keywords: No-regret learning
coarse correlated equilibrium
Optimistic Hedge

Abstract: We show that Optimistic Hedge -- a common variant of multiplicative-weights-updates with recency bias -- attains ${\rm poly}(\log T)$ regret in multi-player general-sum games. In particular, when every player of the game uses Optimistic Hedge to iteratively update her action in response to the history of play so far, then after $T$ rounds of interaction, each player experiences total regret that is ${\rm poly}(\log T)$. Our bound improves, exponentially, the $O(T^{1/2})$ regret attainable  by standard no-regret learners in games, the $O(T^{1/4})$ regret attainable by no-regret learners with recency bias (Syrgkanis et al., NeurIPS 2015), and the $O(T^{1/6})$ bound that was recently shown for Optimistic Hedge in the special case of two-player games (Chen & Peng, NeurIPS 2020). A direct corollary of our bound is that Optimistic Hedge converges to coarse correlated equilibrium in general games at a rate of $\tilde{O}(1/T)$.

Near-Optimal No-Regret Learning in General Games
Constantinos Daskalakis MIT CSAIL costis@csail.mis mit.edu
Maxwell Fishelson MIT CSAIL maxfish@mi seffiishmiitt edu
Noah Golowich MIT CSAIL nzg@mit edu
Abstract
We show that Optimistic Hedge common variant of multiplicative -weigithttti-wwigttt--- updates with recency bias - attains poly poly(log& T') regret in multi-playe general-sum games. In particular, when every player of the game uses Optimistic Hedge iteratively update her strategy in response to the history of play so far, then after T rounds of interaction, each player experiences total regret that poly T). Our bound improves, exponentially, the ( regret attainable by standard no-regret learners in games, the ((T)/4) regret attainable by no-re no-regret learners with recency bias [SALS15], and the O(T1/6) bound that recently shown for Optimistic Hedge in the special case of two-player games [CP20]. corollary of our bound is that Optimistic Hedge converges coarse correlated equilibrium in general games rate of Ô (+).
Introduction
Online learning has long history that intimately related the development of game theory, convex optimization, and machine learning. One of its earliest instantiations can be traced to Brown's 's proposal [Bro49] of fictitious play as a method to solve two-player zero-sum games. Indeed, as shown by [Rob51], when the players of (zero-sum) matrix game use fictitious play to iteratively update their actions response to each other's history play, the resulting dynamics converge in the following sense: the product of the empirical distributions of strategies for each player converges to the set of Nash equilibria the game, though the rate convergence is now known be exponentially slow [DP14]. Moreover, such convergence to Nash equilibria fails in non-zero-sum games [Sha64].
The slow convergence of fictitious play Nash equilibria in zero-sum matrix games and non- convergence in general-sum games can be mitigated by appealing to the pioneering works [Bla54, Han57] and the ensuing literature on no-regret learning [CBL06]. is known that if both players of zero-sum matrix game experience regret that is at most eT)) the product of the players' empirical distributions of strategies is an (TT))))))apprroxiiaal player of a general-sum, multi-player game experiences regret that is at most e(T). the empirical distribution of joint strategies converges to coarse correlated equilibrium' of the game, at a rate of D((TT)/T) Importantly, multitude of online learning algorithms, such as the celebrated Hedge and Follow-The Peneee-eetuuuedeeeeee when such algorithms employed by all players in game, their O regret implies convergence coarse correlated equilibria (and Nash equilibria of matrix games) rate of O(I/VT).
Nash equilibrium. More generally, if each
algorithms, guarantee adversarial regret O ((VT) [CBL06]. Thus,
While standard no-regret learners guarantee ((vT) regret for each player in game, the players can do better by employing specialized no-regret learning procedures. Indeed, it was established by [DDK11] l] that there exists a somewhat complex no-regret learner based on Nesterov's excessive gap technique [Nes55], which guarantees Olog I') regret to each player of two-player zero-sum game.
In general-sum games, is typical to focus on proving convergence rates for weaker types of equilibrium than Nash, such as coarse correlated equilibria, since finding Nash equilibria is PPAD PPAD-complete [DGPU6, CDT09).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Overview of prior work on fast rates for learning in games. m denotes the number of players, and denotes the number of actions per player (assumed to be the same for all players). For Optimistic Hedge, the adversarial regret bounds in the right-hand column are obtained via choice of adaptive step-sizes. The (-) notation hides factors that are polynomial in log T.
Algorithm
Setting
Regret in games
Adversarial regret
Hedge (& many other algs.)
multi-player, general-sum
O(yTlogn) [CBL06]
O(yTlog [CBL06]
Excessive Gap Technique
2-player, O-sum
Olog n n(log T + 8/2 n))
O log n) [DDK11]
[DDK11]
DS-OptMD, OptDA
2-player, O-sum
log
(0g)()())) [HAM21]
Tlog 2()) (m) [HAM21]
multi-player, general-sum
Ologn /m- T2/1) [RS13b, SALSI5]
Ö(VTlogn)
Optimistic Hedge
[RS13b, SALSI5]
2-player, general-sum
Optimistic Hedge
0llog// n T1/) [CP20]
Ö(yTlogn)
multi-player, general-sum
Ollogn m log log$17 TT) (Theorem 3.1)
Ö(VT n) (Corollary D.1)
Optimistic Hedge
This represents exponential improvement over the regret guaranteed by standard no-regret learners. More generally, [SALS15] established that if players of multi mulli-player, general-sum game use any algorithm from the family of Optimistic Mirror Descent (MD) Optimistic Follow-the-Regularize Leader (FTRL) algorithms (which are analogoues of the MD and FTRL algorithms, respectively, with recency bias), each player enjoys regret that is O This was recently improved by [CP20] to (TT in the special case of two-player games in which the players use Optimistic Hedge, particularly simple representative from both the Optimistic MD and Optimistic FTRL families.
The above results for general-sum games represent significant improvements over the O(vT) regret attainable by standard no-regret learners, but are not as dramatic as the logarithmic regret that has been shown attainable by no-regret learners, albeit more complex ones, in 2-player zero-sum games (c.g.. [DDKI [DKKI]), IJ.. Indeed, despite extensive work on no-regret learning, understanding the optimal regret that can be guaranteed by no-regret learning algorithms in general-sum games has remained clusive. This question is especially intruiging in light of experiments suggesting that polylogarithmic regret should be attainable (SALS15, HAM21J. In this paper we settle this question by showing that no-regret learners can guarantee polylogarithmic regret to each player in general-sum multi-player games. Moreover, this regret is attainable by particularly simple algorithm Optimistic Hedge:
Theorem 1.1 (Abbreviated version of Theorem 3.1). Suppose that players play general-sum multi-player game, with a finite set of n strategies per player, over rounds. Suppose also that each player uses Optimistic Hedge to update her strategy in every round, a function of the history of play so far. Then euch player experiences O(m log log" T) regret.
An immediate corollary of Theorem 1.1 is that the empirical distribution of play is O m log no log' T T
approximate coarse correlated equilibrium (CCE) of the game. We remark that Theorem 1.1 bounds the total regret experienced by each player of the multi-player game, which is the most standard regret objective for no-regret learning in games, and which is essential to achieve convergence to CCE, For the looser objective of the average of all players' regrets, [RS [35]] established O n) bound for Optimistic Hedge in two- two-player zero-sum games, and [SALS15] generalized this bound, to Om log n) m-player general-sumt games. Note that since some players may experience negative regret [HAM21], the average of the players' regrets cannot be used in general to bound the maximum regret experienced by any individual player. Finally, we remark that several results in the literature posit no-regret learning as a model of agents' rational behavior; for instance, [Rou09, ST13, RST17] show that no-regret learners in smooth games enjoy strong Price-of-Anarchy bounds. By showing that each agent can obtain very small regret in games by playing Optimistic Hedge, Theorem 1.1

---

strengthens the plausability of the common assumption made in this literature that each agent will choose use such a no-regret algorithm.
1.1 Related work
Table I summarizes the prior works that aim to establish optimal regret bounds for no-regret learners in games. We remark that [CP20] shows that the regret of Hedge is (2(T)) even in 2-player games where each player has 2 actions, meaning that optimism is necessary to obtain fast rates. The table also includes recent result of [HAM21] showing that when the players in 2-player zero-sum game with n actions per player use variant of Optimistic Hedge with adaptive step size (a special case of their algorithms DS DS-OptMD and OptDA), each player has log O(L) n regret. The techniques of [HAM21] differ substantially from ours: the result in [HAM21] is based showing that the joint strategies z01)) rapidly converge, pointwise, to a Nash equilibrium x². Such result seems very unlikely to extend to our setting of general-sum games, since finding an approximate Nash equilibrium even in 2-player games is PPAD PPAD-complete [CDT09]. We also remark that the earlier work [KHSC18] shows that each player's 's regret is at most O(log T log n) when they use a certain algorithm based on Optimistic MD in 2-player zero-sum games; their technique is heavily tailored to 2-player zero-sum games, relying on the notion of duality in such a setting.
[FLL+16] shows that one can obtain fast rates in games for a broader class of algorithms (e.g.. including Hedge) one adopts relaxed (approximate) notion of optimality. [WL18] uses optimism to obtain adaptive regret bounds for bandit problems. Many recent papers (e.g.. [DP19, GPD20, LGNPw21, HAM21, WLZL21, AIMM21] have studied the last-iterate convergence of algorithms from the Optimistic Mirror Descent family, which includes Optimistic Hedge Finally, long line of papers (c.g., [HMcW 03, DFP+ 10. KLPI1, I. BCM12, PP16, BP18, MPP18, BP19, CP19, VGFL+ has studied the dynamics of learning algorithms in games. Essentially all of these papers do not use optimism, and many of them show vorceneer (e.g., divergence or recurrence) of the iterates of various learning algorithms such as FTRL and Mirror Descent when used in games.
2 Preliminaries
Notation. For positive integer ni let [n] := (1,2....., For a finite set S, let (SS) denote the space of distributions on S. For S = [n]. we will write A := A(S) and interpret elements of A [n]. we denote the jth coordinate of v as v(j). For vectors v, w E IR", write (v, w) = Σラ= v())w( The base-2 logarithm of x > 0 is denoted log x.
as vectors in RT. For a vector E R" and
No-regret learning in games. We consider a game G with m E N players, where player i E [m]] has action space A; with n, := |Asl actions. We may assume that A, [m.] for each player The joint action space is A == Ai x ..... x Am. The specification of the game G is completed by collection of loss functions Li,..., L. A + [o, 1]. For an action profile a = (ai...., am) E A and i E [iz)), (a) is the loss player i experiences when each player i' E [m/] plays ag. A mixed strategy T, E (AA)) for player is a distribution over A,, with the probability of playing action j A, given by z)).). Given mixed strategy profile a = (a1,... )m and a player E [m] we let x=, (or a_s. respectively) denote the profile after removing the ith mixed strategy x; (or the ith action a;, respectively).
(Ii,.... 2m) (or an action profile
The m players play the game for a total of T rounds. At the beginning of each round E [T], each player i chooses a mixed strategy x; (f) E (AA)). The loss vector of player i, denoted e/0) E [0, 1]m4 is defined as ( = E, ____-o! (C,(j,a)))) As a matter of convention, set (0)) = to be the all-zeros vector. We consider the full-information setting in this paper, meaning that player observes its full loss vector 4 for each round t. Finally, player i experiences a loss of (c _,(()) The goal of each player is to minimize its regret, defined as: Reg.r Evetry (or(0) e!!)) -min)emn.) Exerry ( (j)- Optimistic hedge. The Optimistic Hedge algorithm chooses mixed strategies for player i E [m] as follows: at time t 1, it sets 2.!' (1/n,,... .... 1/nz) be the uniform distribution on A, Then for all t < T, player i's strategy at iteration & + is defined as follows, for j E [n.]:
(j)
( exp(-n (2("(() E. (i)) ((+) (J) = Exe(n)) mi (1)) exp(-n (26 (K) - -0.-- (()))
(1)
3

---

Optimistic Hedge is modification of Hedge, which performs the updates af (
Exe(ng) "; (X)) The update (1) modifies the Hedge update by replacing the loss vector
(()) with predictor of the following iteration's 's loss vector, el0 (e_0) -((--)) Hedge corre- sponds to FTRL with negative entropy regularizer (see, e.g., [Bub15]), whereas Optimistic Hedge corresponds to Optimistic FTRL with negative entropy regularizer [RS13b, RS13a].
Distributions & divergences. For distributions P. P.Q on finite domain [n]] the KL divergence
between P,Q is (I(P;Q) = Σド= P() loog
The chi-squared divergence between P, Q QG3
P()
2 - - (P()-QU))* For distribution P on [n] and Q0) vector E RR, we write Varp (v) = Eー= PG) (v(i) - E P())o(A))* Also define
x2 (P; Q) Σラ= QU)
P(D) QG)
|| - V P()) v()).. If further P has full support, then define || V x() The above notations will often be used when the mixed strategy profile æ; for some player and is loss vector Ł;; in such case the norms ||l|| and || are often called local norms.
T()
3 Results
Below we state our main theorem, which shows that when all players in a game play according to Optimistic Hedge with appropriate step size, they experience polylogarinn logartgaii individual regrets.
Theorem 3.1 (Formal version of Theorem 1.1). There are constants C, C' > that the following holds. Suppose a time horizon T E N and a game G with m players and n& actions for each player i [m] is given. Suppose all players play according Optimistic Hedge with any positive step size S C.m T. Then for any E [m], the regret of player i satisfies
log Th
Reg.r S
+ CC log
particular, the players' step size is chosen as 1) = C.m log
then the regret of player i satisfies
Reg,, SO (m log n; log T).
A common goal in the literature on learning in games is to obtain algorithm that achieves fast rates whan played by all players, and so that each player i still obtains the optimal rate of ((VT) in the adversarial setting (i.c., when i receives an arbitrary sequence of losses E(1) ........ (T))) We show in Corollary D.1 (in the appendix) that by running Optimistic Hedge with an adaptive step size, this is possible. Table compares our regret bounds discussed in this section to those of prior work.
Proof overview
In this section we overview the proof of Theorem 3.1; the full proof may be found in the appendix.
4.1 New adversarial regret bound
The first step in the proof of Theorem 3.1 is to prove a new regret bound (Lemma 4.1 below) for Optimistic Hedge that holds for an adversarial sequence losses. We will show in later sections that when all players play according to Optimistic Hedge, the right-hand side of the regret bound (4) is bounded by a quantity that grows only nolyloogarthhmically in T'
Lemma 4.1. There is a constant C so that the following holds. Suppose any player i e [m] follows the Optimistic Hedge updates (I) with step size 1 < 1/C. arbitrary sequence of losses
(T) E [0, 1] Then
Reg. T
log n2
+ t=1
Σ
T
" + +C²)
Var (40-
T
(1-Cn)m
Cn)yn
Var x,
(c (4)
2
2
The detailed proof of Lemma 4.1 can found in Section A, but we sketch the main steps here. The starting point is refinement of [RS1 13a, Lemma 3] (stated as Lemma A.5), which gives upper

---

bound for Reg,r in terms of local norms corresponding to each of the iterates (2) of Optimistic Hedge. The bound involves the difference between the Optimistic Hedge iterates x (t) ((()) defined by a
and iterates
=: (x)p)xxp(x))(ee ( (())
Mn xi (k)-exp( ( (E. (k) (161))
T
T (0,
R
log nh
(1) 5
Var 10 ( ((--1)
1
KT
(1)
Σ
11
7
(5)
We next show (in Lemma A.2) that KL(E,"), (x and KL(x; (t), 1) may be lower bounded by (1/2 - (()) ;aa" and (1/2 - -())) x fact that the KL divergence between two distributions is upper bounded by the chi-squared distribution between them; by contrast, Lemma A.2 can exploit that _,(), (:(') and 2:--1) are close to each other to show reverse inequality. Finally, exploiting the exponential weights-style functional relationship
(a (o
)) respectively. Note it a standard
between z ( and i sx(t-1), we show (in Lemma A.3) that the x² -iveergee x² 2a (((-1)) may be
lower bounded by (1 O())) 17² Var 2000
(e((-1). leading to the term (1-Cn)n Var (2) (((t11)
(1), X diverrgee x² (= 2 (1)), as well as the term
1:000
being subtracted in (4). The bounded in a similar manner to obtain (4).
1 x (0)
in (5)
4.2 Finite differences
Given Lemma 4.1, in order to establish Theorem 3.1, it suffices to show Lemma 4.2 below. Indeed, (6) below implies that the right-hand side of (4) is bounded above by log n + "(log" T), which is
bounded above by O(m log n, log" T)) for the choice 1) = O m-llo
of Theorem 3.1.2
Lemma 4.2 (Abbreviated; detailed version in Section C.3). Suppose all players play according to Optimistic Hedge with step size 1 satifying 1/T' S 1) S Tm-log for sufficiently large constant C.
Then for any i E [m], the losses e(2) ..... (T) E R. for player satisfy:
T Σ
T
Var,.0 (0) (4.)) (((t))((-1))
(1-1)
2 Var (t) (1 + +0 (log" T).
Σ
(6)
The definition below allows us to streamline our notation when proving Lemma 4.2.
Definition 4.1 (Finite differences). Suppose = (I,(),... I(T) is sequence of vectors [(()) E TR.. For integers h 2 0, the order-h finite difference sequence for the sequence L., denoted by D2 L,, is the
sequence D,, L == ((D, L) (1) ,D..,,D,, L) (T)) defined recursively as: (D, L) == (9) for all 1 1 < T, and
(D, () = (Dn-1 ()) ()(+)) -DDn-1 L))
for all h 2 1 h.3
Remark 4.3. Notice that another way of writing (7) is: Dp L D1 Dn-1 L. We also remark for later use that (D,, ( Et (-1
Let H = log where T denotes the fixed time horizon from Theorem 3.1 (and thus Lemma 4.2). In the proof of Lemma 4.2, we will bound the finite differences of order h < H for certain sequences.
The bound (6) of Lemma 4.2 may be rephased as upper bounding Σ Var (()) ((D (t)(t)))))) by
Vara;
(((-1)): to prove this, we proceed in two steps:
"Notiee that the factor 1 in (6) is not important for this argument - any constant less than 1 would suffice. 'We remark that while Definition 4.1 is stated for a 1-indexed sequence [1) I (4) (...... we will also occa- sionally consider 0-indexed sequences (0))) (1)) ...., in which case the same recursive definition (7) holds for the tinite differences (D,, () 0.
5

---

(Upwards induction step) First, in Lemma 4.4 below, we find an upper bound on || 10/ for all t [T), h 2 which decays exponentially in h for h S H. This is done via upwards induction on h, i.e., first proving the base case h = 0 using boundedness of the losses d and then h = 1, inductively. The main technical tool we develop for the inductive step is weak form of the chain rule for finite differences, Lemma 4.5. The inductive step uses the fact that all players are following Optimistie Hedge to relate the hith order finite differences of player i's loss sequence g(t)
to the /ith order finite differences of the strategy sequences L for players i' A i; then we use the exponential-weights style updates of Optimistic Hedge and Lemma 4.5 to relate the hthh order finite differences of the strategies z.p' to the (h- - 1)th order finite differences of the losses e()
2. (Downwards induction step) We next show that for all O S h 2f4)) (IDi ((Dn) (,)
H,
Et Var ((1) ((Dn-1&)) ()))) is bounded above by cn Et= Var,,0)
+ ph..
for some Ch < and nm Ollgg TT). This shown via downwards induction h, namely first establishing the base case h = H by using the result of item 1 for h = H and then treating the cases h = H 1, 2, 2,...... O. The inductive step makes use of the discrete Fourier transform (DFT) to relate the finite differences of different orders (see Lemmas 4.7 and 4.8). In particular, Parseval's ss equality together with a standard relationship between the DFT of the finite differences of sequence to the DFT of that sequence allow us to first prove the inductive step in the frequency domain and then transport it back the original (time) domain.
In the following subsections we explain in further detail how the two steps above are completed.
4.3 Upwards induction proof overview
Addressing item in the previous subsection, the lemma below gives a bound on the supremum norm of the h-th order finite differences of each player's loss vector, when all players play according to Optimistic Hedge and experience losses according to their loss functions Li, Lm A -> [0, 1].
Lemma 4.4 (Abbreviated). Fix a step size r) > 0 satisfying 1 S o m mlogT If all players
follow Optimistic Hedge updates with step size n, then for any player E [m]] integer h satisfying 0 S h S H, and time step E [T - h1] it holds that || (D₁, e,) 11 S <0(m))^ h(h)
detailed version of Lemma 4.4, together with its full proof, may be found in Section B.4. We next 2; show in Section B.4
give proof overview of Lemma 4.4 for the case of 2 players, i.e., how to generalize this computation to general m. Below we introduce the main technical tool in the proof, "boundedness chain rule," and then outline how it is used to prove Lemma 4.4.
Main technical tool for Lemma 4.4: boundedness chain rule. We say that a function R" : - R is softmax-lype function if there are real numbers : En and some E [n] so that for all exp(z,)
(21,..., =n.) E IR",, ((211...,, )n = E (xx)))) Lemma 4.5 below may be interpreted as a "boundedness chain rule" for finite differences. To explain the context for this lemma, recall that given an infinitely differentiable vector- valued function L : - IR" and an infinitely differentiable function Φ: IR" + R. the higher order derivatives of the function of (t)) may be computed in terms of those of L and & using the chain rule. Lemma 4.5 considers an analogous setting where the input variable t to L is discrete-valued, taking values in [T] (and so we identify the function L with the sequence Z()...., ..... (T)). In this case, the higher order fintt differences of the sequence (1)),... L(T) (Definition 4.1) take the place of the higher order derivatives of L with respect to t. Though there is no generic chain rule for finite differences, Lemma 4.5 states that, at least when ó is a softmax-tyr type function, may bound the higher order finite differences of the sequence ("),... ((L(T) In the lemma's 's statement we let o L denote the sequence oi ((L(")), (..)),.............. ((L ()L(
Lemma 4.5 ("Boundedness chain rule" for finite differences: abbreviated). Suppose that h, n e N, á : R" + RR is a softmax-type function, and L = (L ...., (T)) is sequence of vectors in R" satisfying [|o < for i E [T]. Suppose for some a E (0, 1), for each 0 < h'' S h and t E [T h²), it holds that || Dr 1.00 S <O(akk) (h')O()) Then for all t E [T-M) h]. ((D, L)) S O(a"). (h))
detailed version of Lemma 4.5 may be found in Section B.3. While Lemma 4.5 requires & to be a softmax-type function for simplicity (and this is the only type of function & we will need to consider

---

for our case for the case m = 2) we remark that the detailed version of Lemma 4.5 allows é to be from a more general family of analytic functions whose higher order derivatives are appropriately bounded. The proof of Lemma 4.4 for all m 2 2 requires that more general form of Lemma 4.5.
The proof of Lemma 4.5 proceeds by considering the Taylor expansion Pa(.) of the function Ø at the origin, which we write as follows: for 2 = (Z1,...,, 2n) E IR" Po(z) := 2 Exzo hyl 0,2?, where a, E IR, |r| denotes the quantity ? +..... + Yn and >² denotes 27 ... 23". The fact that øi is softmax-type function ensures that the radius of convergence of its Taylor series is at least 1, i.e. <(2) (=( for any satisfying ||=]lo 1. By the assumption that || I for each t,
may therefore decompose (D, (0 o L)) as:
(Di, (0 ())
Σ
a (D,
k bl=k
where I denotes the sequence of scalars (Lv)(0)= = (Z.0)7 for all l. The fact that & is a softmax- type function allows us to establish strong bounds on |a,1 for each in Lemma B.5, The proof of Lemma B.5 bounds the |a,, by exploiting the simple form of the derivative of softmax-type function to decompose each a,y into a sum of hy| terms. Then we establish a bijection between the terms of this decomposition and graph structures we refer to as factorial trees; that bijection together with the use of an appropriate generating function allow us to complete the proof of Lemma B.5.
Thus, to prove Lemma 4.5, suffices to bound (D₁, L>>()) (0) for all y. We do so by using Lemma 4.6.
Lemma 4.6 (Abbreviated; detailed vesion in Section B.2). Fix any h 2 multi-index 7 E Z the and set = hr|- For each of the kh functions π. : [h] + [Kt], and for each r E [k), there are integers W/ {0, 1,..,....... ,h, txr 2 O, and ja.r E [m], that the following holds. For any sequence L(), ,.,,...,,. ((T) I2" of vectors, it holds that, for each E [T' hl.
Σ 11 (DN... (L(),)))) (141)
(Da
-:10]-14==1 r=1
Lemma 4.6 expresses the /ith order finite differences of the sequence Lt as a sum of ka terms, each of which a product of finite order differences of a sequence L (H,,)) (i.c., the jh, coordinate of the vectors (.)), Crucially, when using Lemma 4.6 to prove Lemma 4.5, the assumption of Lemma 4.5 gives that for each j' E [ri], each E [h]. and each t' E [T h²). we have the bound (Dw L(J") (+) < O(a²) (h))0(A)) These assumed bounds may be used to bound the right- side of (9), which together with Lemma 4.6 and (8) lets us complete the proof of Lemma 4.5.
Proving Lemma 4.4 using the boundedness chain rule. Next we discuss how Lemma 4.5 is used
to prove Lemma 4.4, namely to bound || (D,, ())() oo for each / E [T 1t). i E [m]] and 0 < h < H. Lemma 4.4 is proved using induction, with the base case h = 0 being straightforward consequence
of the fact that (Do (,) (+) Ilse = |ee b1 < 1 for all E [m], t E [7'] For the rest of this section we focus on the inductive case, i.e., we pick some [H] and assume Lemma 4.4 holds for all h' h.
The first step is to reduce the claim of Lemma 4.4 to the claim that the upper bound || (D, 22)(() || I O (mr)) A ((0) holds for each f. E [ h), à E [m]. Recalling that we are only sketching here the case m = for simplicity, this reduction proceeds as follows: for i E {1, 2). define the matrix A; E R by (At)a,e2 = Li(a,, 0z), for an E [m1],02 E [nz]. We have assumed that all players are using Optimistic Hedge and thus e((
E
app Wis (a.a.....,,
here (m = 2), this may be rewritten as e(t)
1
(t)
e(t)
AA a11)
Thus
h
A
|| (D₂ 4) (9 1a0 = A1
Σ ==0
(-
(1+))
Σ
((+))
= || (Dn, x2) I|,
where the first equality is from Remark 4.3 and the inequality follows since all entries of A₁ have absolute value < 1. A similar computation allows us show (D,, (2) Ilxo S (D) 21) (t) I11.
7

---

To complete the inductive step it remains to upper bound the quantities I| (Dn, xx)) || for E [m], 1 e [T ht.. To do so, we note that the definition of the Optimistic Hedge updates (1) implies that for any
i [m],t e [T,j [n.]. and t' 2 1. we have
x100 exp (n- (4 -Ei' (1(4100))) (j) -
(1) = Ek= (1 (k) exp 77 (4- (k) -''0 g(et (1)) efetee- (k))
(10)
For L E [T), 2 O. set i,tt == 11 (c(-1) - En'' el(ts)) dett' Also, for each i E [m]..j-
exp((ttt) (n:)) E ERn define )r Σ (4) exp(a(M))
[mi]. / E [7]. and any vector x -
Thus (10) gives that for t' 2 1, n; (t+('() (() = /e,i, ). Viewing t fixed parameter and letting
vary, it follows that for 2 and t' 2 1, DD x2 (+ (1) (t)) = (Dx (dr.s o Es,t)) (+)
Recalling that our goal is to bound (Dn 24 4.5 with o = Hi,i, and a = O(m)). if we can show that its precondition is met, i.c. that Il (Dw ELs) (t') 100 S I Bi L. (h') Boh' for all V/ S h, the appropriate a and appropriate con- stants Bo, B1. Helpfully, the definition of zlt') itt as a partial sum allows us to relate the h'-th order e(() to the (h'-1)=a 1) order finite differences of the sequence e/?)
for each t. we do by using Lemma
finite differences of the sequence as follows:
(Dn EL.)) (t)) 17 (Dw-1 (,) 2n- (Dw (1w=1e,)(00)) (,)
(0+1'1)
(11)
Since h - < h for h < ht the inductive assumption of Lemma 4.4 gives a bound on the foo -nom of the terms on the right-hand side of (11), which are sufficient for us apply Lemma 4.5. Note that the inductive assumption gives an upper bound on || (Dw~1 (.)( oo that only scales with hh- whereas Lemma 4.5 requires scaling of R This discrepancy is corrected by the factor of 1) on the right-hand side of (11), which gives the desired scaling a (since 1) < a for the choice a = (mn)).
4.4 Downwards induction proof overview In this section we discuss in further detail item 2 in Section 4.2; in particular, we will show that there a parameter μ (19m) so that for all integers h satisfying H 2 0.
T-h-1 Var,.") (!" (DD++1 s O(1HH)
T-h
Σ
Var (0) (D)))) + Ō(22)), (12)
where Ô hides factors polynomial in log The validity of (12) for h 0 implies Lemma 4.2. On the other hand, long we choose the value μ in (12) to satisfy μ 2 mnH then Lemma 4.4 implies that ΣT= Var 200) (Dx e)) I O(.2H) This gives that (12) holds for h = H - 1. To show that (12) holds for all H - > h 2 O, we use downwards induction; fix any h, and assume that (12) has been shown for all h satisfying h < h' < H 1. Our main tool in the inductive step is to apply Lemma 4.7 below. To state it, for ( > 0, n E N, we say that a sequence of distributions p())
E A (-consecutively close for each S < T, it holds that 1+ Ç.4 Lemma 4.7 shows that given sequence of vectors for which the variances of its second-order finite differences are bounded by the variances of its first-order finite differences, a similar relationship holds between its first- and peroth-order finite differences.
P(T)
max {|)
pio) pe+t
P
Lemma 4.7. There is sufficiently large constant Co > 1 so that the following holds. For any M, a > and n E N, suppose that p(1) p()),..., p(f) E A and z(3) 2 Z E I-M M| satisfy the following conditions:
1. The sequence p()) p()).... (TT) is (-consecutively close for some Ç E (1//(22), a² /Col
2. It holds that Et' Var (D2 Sa ET= -T-Vaarpe (D, ()) + μ.
'Here, for distributions P,Q PAQEA" P R² denotes the vector whose jth entry P())
8

---

Then Σ Var (ID) S a (1 (1+ Varpeo) (2 + CoM
Given Lemma 4.7, the inductive step for establishing (12) is straightforward: we apply Lemma 4.7 with p(t) 2; and Z (Di ()))) for all t. The fact that x²" are updated with Optimistic Hedge may be used to establish that precondition of Lemma 4.7 holds. Since (D₂ Z) = (Da+1 4) and (D2 () (Dn+2.)) (,)(), that the inductive hypothesis (12) holds for h + 1 implies that precondition of Lemma 4.7 holds for appropriate a, μ > O. Thus Lemma 4.7 implies that (12) holds for the value h, which completes the inductive step.
On the proof of Lemma 4.7. Finally we discuss the proof of Lemma 4.7. One technical challenge the fact that the vectors p(t) are not constant functions of I, but rather change slowly (as constrained by being (-consecutively close). The main tool for dealing with this difficulty is Lemma C.I. which
Var par (Z(0)
shows that for a (-consecutively close sequence p(t), for any vector Z(t),
[1- 1,
Var pieete (2
<]. This fact, together with some algebraic manipulations, lets to reduce to the case that all p(t) are equal. It is also relatively straightforward reduce to the case that (P(t), (+)) = 0 for all t, i.c., so that Var pco (z( = I pin- We may further separate | = P() (Z()))))
into its individual components (() ())² and treat each one separately, thus allowing us to reduce to one-dimensional problem. Finally, we make one further reduction, which is to replace the finite differences D,, (+) in Lemma 4.7 with circular finite differences, defined below:
Definition 4.2 (Circular finite difference). Suppose L = (L ,.... L
a sequence of vectors ( E R For integers h 2 O, the level-h circular finite difference sequence for the sequence L, denoted by D L, is the sequence defined recursively as: (D) L)() = [ for all 0 < t < S, and
(DA () - -
(1+)) - (D)
L) (0)
() - (D) - (T) :t= S 1
(13)
Circular finite differences for sequence I("),.... (8-1) are defined similarly to finite differences (Definition 4. 4) except that unlike for finite differences, where (D,, L) ()(S-)) ...... (D,, L.) (S-1) are not defined, (Dr, ()(8
(Dū, ()(5-)) are defined by "wrapping around" back to the beginning of the sequence. The above-described reductions, which are worked out in detail in Section C.2, allow to reduce proving Lemma 4.7 to proving the following simpler lemma:
Lemma 4.8. Suppose μ. E R, > O, and W(O)
W(S-1)
E IR is sequence of reals satisfying
Σ
S-1
(D))
<a a Σ (D) +
S-1
(14)
Then ES- (D) Sa. -. (w(0)² (w00) + p/a.
To prove Lemma 4.8, we apply the discrete Fourier transform to both sides of (14) and use the Cauchy- Schwarz inequality in frequency domain. For a sequence W( ..... W(S-1) E IR, its (discrete) Fourier transform is the sequence W ..... (T-(- defined by (+)) Σez W e- 3 Below we prove Lemma 4.8 for the special case μ = O: we defer the general case to Section C.I.
Proof of Lemma 4.8for for special case μ = O. We have the following:
T S. Σ (DD = Σ T
Di W (3)
= Σ Wis) ( 2min//111)
1 2
Σ
Wiol
where the first equality uses Parseval's equality, the second uses Fact C.3 (in the appendix) for / = 1, and the inequality uses
Schwarz. By Parseval's 's inequality and Fact C.3 for h = 2, the right-
v E (D)) (D) which, by assumption, is
hand side of the above equals S. V
at most S- ET (WO)). Et_ (D))) 2
Rearranging terms completes the proof. O
9

---

Acknowledgments and Disclosure of Funding
C.D. Supported by NSF Awards CCF- 1901129, DMS-2022448 and DMS-2134108, by a Simons Investigator Award, by the Simons Collaboration on the Theory of Algorithmic Fairness, by a DSTA grant, and by the DOE PhILMs project (No. DE-ACOS- (CC00-76RL00800) N.G. is supported by a Fannie & John Hertz Foundation Fellowship and an NSF Graduate Fellowship.
References
[AIM221]
Waiss Azizian, Franck lutzeler, Jérome Malick, and Panayotis Mertikopoulos. The last-iterate convergence of optimistic mirror descent in stochastic variational incqualities. In Conference on Learning Theory, pages 32, 2021.
[BCM12]
Maria-Florina Balcan. Florin Constantin, and Ruta Mehta. The Weighted Majority Algorithm does not Converge Nearly Zero-sum Games. In ICML Workshop on Markets, Mechanisms, and Multi-Agent Models, 2012.
[Bla54]
David Blackwell. Controlled Random Walks. In Proceedings of the International Congress of Mathematicians, volume 3, pages 336-338, 1954.
[BP18]
James P. Bailey and Georgios Piliouras. Multiplicative Weights Update in Zero-Sum Games. In Proceedings of the 2018 ACM Conference Economics and Computation EC '18, pages 321-338, Ithaca, NY, USA, 2018. ACM Press.
[BP19]
James P. Bailey and Georgios Piliouras. Fast and furious learning in zero-sum games: Vanishing regret with non-vanishing step sizes. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 12977-12987, 2019.
[Bro49]
George W Brown. Some Notes Computation of Games Solutions. Technical report, RAND CORP SANTA MONICA CA, 1949.
[Bub15]
Sébastien Bubeck. Convex Optimization: Algorithms and Complexity. Found. Trends Mach. Learn., 8(3-4):3313357 November 2015.
[CBL06]
Nicolo Cesa- Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge university press, 2006.
[CDT09]
Xi Chen, Xiaotie Deng. and Shang- Teng. Seuling complexity of computing two-player nash equilibria. Journal of the ACM (JACM), 16(3): 2009.
[CP19]
Yun Kuen Cheung and Georgios Piliouras. Vortices instead of equilibria in minmax optimization: Chans and butterfly effects of online learning in zero-sum games. Proceedings of the Thirty- Second Conference on Learning Theory, pages 807-834, 2019.
[CP20]
Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. Advances Neurul Information Processing Systems, volume 33, pages 18990-18999 Curran Associates, Inc., 2020.
[CS04]
Imre Csiszár and Paul Shields. Information Theory and Statisties: A Tutorial. Commun. Inf. Theory, 144)-17-528, December 2004.
[DDKI1]
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near Optimal No- No-Regret Algo- rithms for Zero-Sum Games. Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms (SODA), 2011.
[DFP*10]
Constantinos Daskalakis, Rafacl Frongillo, Christos H. Papadimitriou, George Pierrakos, and Gregory Valiant. On learning algorithms for nash equilibria. Proceedings of the Third Interna- tional Conference on Algorithmic Game Theory, SAGT" 10, page 114-125, Berlin, Hcidelberg. 2010. Springer- Verlag.
[DGP06]
Constantinos Daskalakis, Paul W. Goldberg, and Christos Papadimitriou.. The complexity of computing a nash equilibrium. In Proceedings of the Thirty- Eigtt- Annual ACM Symposium on Theory of Computing (STOC), 2006.
[DP14] Constantinos Daskalakis and Qinxuan Pan. counter-example Karlin's strong conjecture for fictitious play. In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS), 2014.
[DP19]
Constantinos Daskalakis and loannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max Conference, ITCS 2019, Jamuary 10-12, 2019, San Diego, California, USA, volume 124 of LIPlcs. pages 27:1 17:18. Schloss Dagstuhl- Leibniz Zentrum für Informatik, 2019.
max optimization. In 10th Innovations in Theoretical Computer Science
10

---

[FLL* 16]
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. Learning in games: Robustness of fast convergence. In Advances Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[GKP89]
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison Wesley, Reading, 1989.
[GPD20]
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. Advances Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[HAM21]
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference on Leurning Theory, 2021.
[Han57]
James Hanman, Approximation to Bayes risk in repeated play. Contributions to the Theory of Games, 139, 1957.
[HMcW 03] Hart, Andreu Mas-colell Of Jörgen W. Weibull, O Vega, Drew Fudenberg, David K. Levine, Josef Hofhauer, Karl Sigmund, Eric Maskin, Motty Perry, and Er Vasin. Uncoupled dynamics do not lead to nash equilibrium. Amer. Econ. Rev, pages 1830-1836, 2003.
[KHSC18]
Ehsan Asadi Kangarshahi, Ya-Ping Hsich, Mehmet Fatih Sahin, and Volkan Cevher. Let's be honest: An optimal no-regret framework for zero-sum games. In Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings Muchine Learning Research, pages 2488-2496. PMLR, 10-15 2018.
[KLP11]
Robert Kleinberg, Katrina Ligett, and Georgios Piliouras. Beyond the nash equilibrium barrier. In Innovations Computer Science (ICS, pages 125-140, 2011.
[LGNPw21] Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and xiao wang. Last iterate convergence in no-regret learning: constrained min-mat max optimization convex-concat landscapes. Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1441-1449. PMLR, 13-15 Apr 2021.
[MPP18] Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 18, page 2703-2717. USA, 2018. Society for Industrial and Applied Mathematics.
[Nes05]
Yu Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Optimization, 16(1):235 249, 2005.
[PP16]
Christos Papadimitriou and Georgios Piliouras. From nash equilibria to chain recurrent sets: Solution concepts and topology. In Proceedingy the 20/6 ACM Conference Innovations Theoretical Computer Science, ITCS '16 page 227-235, New York, NY, USA, 2016. Association for Computing Machinery.
[Rob51]
Julia Robinson. An Iterative Method Solving Game. Annals of mathematics, pages 296-301, 1951.
[Rou09]
Tim Roughgarden. Intrinsic robustness the price of anarchy. In Proceedings of Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, page 513 522, New York, NY, USA, 2009. Association for Computing Machinery.
[RS13a]
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference on Learning Theory, pages 993-1019, 2013.
[RS13b]
Alexander Rakhlin and Karthik Sridharan. Optimization, Learning, and Games with Predictable Sequences. UrXiv:1331.1860 [cs]. November 2013. arXiv: 1311.1869.
[RSTI7]
Tim Roughgarden, Vasilis Syrgkanis, and Êva Tardos. The price of anarchy in auctions. J. Artif. Int. Res., 1005 May 2017.
[SALSIS]
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In Advances in Neurul Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[Sha64]
L. Shapley. Some Topics in Two-Person Games. Advances in Game theory, 1964.
[ST13]
Vasilis Syrgkanis and Eva Tardos. Composable and efficient mechanisms. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 13, page 211-220, New York, NY, USA, 2013. Association for Computing Machinery.

---

[VGFL*20]
Emmanouil- Vasileios Vlatakis Vlatakis-Gkaragee Gkaragkouiss,, Lampros Flokas, Thanasis Lianeas, Panayotis Mertikopoulos, and Georgios Piliouras. No-regret learning and mixed nash equilibria: They do not mix. Larochelle, Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1380-1391. Curran Associates, Inc., 2020.
[WL18]
Chen Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. Proceedings of the 31st Conference On Learning Theory, pages 1263-1291, 2018.
[WLZL21]
Chen-Yu Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Lincar last-iterate con- vergence in constrained saddle-point optimization. International Conference on Learning Representations, 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Sections and 3.
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 4 and the appendix (in the supplementary material).
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "nRN3ekedPe", "reviewer": "Reviewer_2uVN", "summary": "The paper shows that when all agents in a game use the Optimistic Hedge regret-minimization algorithm, their regret can be bounded as Otilde(1). When no assumption is made about what algorithm the other agents are using, the regret bound of Optimistic Hedge is still bounded as Otilde(sqrt(T)). ", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very clear and well-organized. It builds on several insights that were already known (for example, the analysis of FTRL in terms of local norms induced by the Hessian of the regularizer, in this case the negative entropy regularizer), and introduces new interesting tools to tighten the analysis of optimistic hedge. The paper cites all the relevant literature I was aware of.\n\nThe result is interesting and I think it would be a great addition to NeurIPS. \n\nI have a couple of question for the authors:\n1. Optimistic algorithms were historically developed as \"predictive\" algorithm, where at each time t the regret minimizer receives a prediction of the next loss before outputting its next decision/strategy $x^t$. It turns out that in most case it makes sense to set the prediction of the next loss to just be the last-received loss. The version of optimistic hedge considered in this paper can clearly be read as making that tacit assumption. However, the proofs in the paper by Syrgkanis et al. apply more generally to any prediction, giving a regret bound that scales with the norm of the mismatch between each loss and its prediction. I wonder if the same can be done in your paper. It would be interesting to figure out \"how late\" the assumption that prediction = latest loss can be made, and if a more general regret bound that scales with the norm of the mismatch can be given first, and only then under the assumption that prediction = latest loss the bound in the paper can be established. I find that keeping the prediction generic would help intuitively separate what is a general result, and what is \"magic\" that is made possible only by assuming something special about the prediction of the loss.\n\n2. Is it possible to give a simple estimate for the magnitude of the constants involved in Theorem 3.1?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think it would be interesting to add a section describing, at a high level, what could be done to extend the positive result in the paper to more general settings. For example: perhaps some ideas from the paper can be extended to predictive OMD/FTRL on more general convex sets, or maybe it's possible to give a more general regret bound that works for any regularizer, akin to the RVU form of the regret bound given by Syrgkanis et al.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "mKxQ8OJJnq", "reviewer": "Reviewer_dfrx", "summary": "The paper studies no regret learning in multi-player general sum games. The major result of this paper is to prove that if every player adopts Optimistic Hedge, then individual regrets decays at rate $\\tilde{O}(1/T)$, improve upon the previous $O(1/T^{5/6})$ of (Chen and Peng, NeurIPS 2020). ", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Advantage: Learning in games is an important topics, and especially the convergence rate of no regret learning algorithms. The paper proves optimistic Hedge gives a near-optimal convergence rate of multi-player game, this is an important contribution. The technique of this paper is also very novel. \n\nDrawback: To be picky, the writing of this paper could be improved, it would be better to explain the high level intuitions of the proof, e.g. why one wants to analyses the t-th order.\n\nSummary: This is a very strong paper and I strongly recommend the acceptance of this paper. I didn't go through the proof, so I haven't checked the correctness of the proof. As I suggested above, it would be good to polish the writing, it would make reading easier.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Looks good.", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "E7DpdRwh7Qh", "reviewer": "Reviewer_uZix", "summary": "The paper shows that if all the players of a multi-player general-sum game use Optimistic Hedge with sufficiently small step-size, the regret of each player is bounded as $O(\\log^4 T)$.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "As far as I am aware, this paper is the first to prove that an algorithm enjoys $\\text{poly}(\\log T)$ regret in all multi-player general-sum games. I believe this is an important contribution. Moreover, in my eyes, the proofs are highly technical and non-trivial. This start with the use of local norms which are common for the analysis of online learning algorithms but were less considered for the analysis of Optimistic Hedge, and is followed by several amazing ideas which goes from finite difference sequences to discrete Fourier transform. Unfortunately, I was unable to go through the entire appendix, but the overall schema seems correct.\n\nI would also like to highlight that, with a single theorem proven and fives pages dedicated to the outline of the proof, this paper seems to be quite atypical for NeurIPS. Nonetheless, I think the authors have made an effort to sketch their proof in the main text. Although the use of big O notations makes the statements of the theorems and the proofs a little problematic, the readers can already get an idea about the structure of the proof before potentially looking into the appendix for a more rigorous and complete version.\n\n**Suggestions for potential improvements of the presentation**\n\nGiven the particularity of the paper, I am not really sure about how to further improve it. Below are just some personal thoughts that the authors can take as reference.\n\n1. I found that the paper could benefit from a wrap-up section or paragraph. In fact, both sections 4.3 and 4.4 are technical and devoted to the proof of lemma 4.2 and are thus not directly related to the main result of the work. For sake of completeness, it would be nice to link these back to Theorem 3.1 at the end. (Sure, this may not add any extra value to the work. It is just a matter of taste.)\n\n2. It seems that many constants mentioned in the theorems are in fact absolute constants that come from numerical inequalities. Maybe it is worth making this point clear to the audience, or even directly providing the numerical values for which the inequalities hold.\n\n3. Typos\n    - line 256: right-hand side?\n    - line 267 and the subsequent inequality: the authors seem to confound $A_1$ and $A_2$\n    - I quickly went through the proof of Lemma 4.1 and feel that we should put $\\eta$ instead of $\\eta/2$ both after $+$ and $-$ at the r.h.s of the inequality.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Fine", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6+"}, "extra_text": {}}, {"review_id": "9KlwHUTsmu", "reviewer": "Reviewer_wnsJ", "summary": "This paper analyzes the regret of Optimistic Hedge in multi-player general-sum games. The paper shows that the algorithm attains polylog($T$) regret for each player, which improves over known rates that scale polynomially with $T$.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The focus of this paper is to analyze Optimistic Hedge (which can be seen as an instance of Optimistic Mirror Descent). The main contribution of this paper is the technical improvement in the analysis of this existing algorithm. The key technique, as I understand it, is to control the variance of slowly changing vectors via bounding the variance of its high-order finite differences. While the improvement in the regret bound is certainly substantial, I do have some concerns over the correctness of the results.\n\n1. In Eq. (28) the proof of Lemma 4.1, the second term is \n$\\sum_{t=1}^T \\Vert x_i^{(t)}-\\tilde x_i^{(t)}\\Vert^*_{x_i^{(t)}}\\cdot  \\sqrt{Var_{x^t_i}(l_i^{(t)}-l_i^{(t-1)})}$\n. The dual norm term is then controlled in Eq. (32) by $\\sqrt{(1+C_1\\eta)\\eta^2}\\cdot \\sqrt{Var_{x^t_i}(l_i^{(t)}-l_i^{(t-1)})}$. Thus the whole term should be controlled by $(1+O(1))\\eta \\cdot Var_{x^t_i}(l_i^{(t)}-l_i^{(t-1)})$. Yet in Eq. (27), this term is shown as $(\\frac{1}{2}+O(1))\\eta \\cdot Var_{x^{(t)}_i}(l_i^{(t)}-l_i^{(t-1)})$. I am confused over how does the $\\frac{1}{2}$ factor arise. Note that this factor does matter in the proof of Theorem 3.1 (Eq. (104)-(106)). If the leading constant is indeed $1+O(1)$ instead of $\\frac{1}{2}+O(1)$, the negative term in Eq. (104) would not be sufficient to cancel the second positive term. Perhaps the constant factor ($\\frac{1}{2}$) in Lemma 4.2 should be made smaller?\n\n2. I am also a bit confused over the proof of Lemma 4.2. In particular, how does on get from Eq. (96) to the base case of Eq. (97)? With $h=H-1$, the second term in Eq. (97) is $\\mu^2\\cdot \\frac{2C_0\\cdot H^2}{\\alpha^3 \\cdot \\alpha_0^2H^6}=\\mu^2\\cdot polylog(T)$. Why is this greater than $\\mu^2 T$?\n\nOther comments:\n\n3. The improvement in the dependence on $T$, compared to previous work on Hedge ($\\tilde{O}(\\sqrt{T})$) and Optimistic Hedge ($\\tilde{O}(\\sqrt{m}T^{1/4})$), seems to come at a cost of worse dependence on $m$, the number of players. In this sense, is the regret bound in this work really near-optimal?\n\n4. Is there a trade-off between $m$ and $T$? If not, is it possible achieve $polylog(n,T)$ regret with no dependence on $m$?\n\n5. In the current setting, player $i$ observes $E_{-i}\\left[ \\mathcal{L}_i(a_i, a^{-i})\\right]$ for each $a_i$, instead of $\\mathcal{L}_i(a_i,a^{-i})$. From a game-play point of view the latter feedback seems a bit more natural, as player $i$ don't have access to the randomness controlled by other players. I realize that existing literature also uses the former type of feedback, but is it the best formulation (from a game-play perspective)? Also, since the feedback is deterministic, isn't it possible to achieve regret independent of $T$?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is purely theoretical and do not present foreseeable negative social impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper resolves a fundamental question on individual regret of 
optimistic Hedge in a multi-player general-sum game setting, which was 
left open since the work of Syrgkanis et al. 2015. Despite the recent 
progress by Chen & Peng, 2020 which shows T^{1/6} regret, to achieve 
polylog(T) regret this paper proposes significantly new ideas, which we 
believe could be highly beneficial for the community. All reviewers are 
excited about this result. 
Decision: Accept (Oral)