Uncoupled Learning Dynamics with $O(\log T)$ Swap Regret in Multiplayer Games
Authors: Ioannis Anagnostides
Gabriele Farina
Christian Kroer
Chung-Wei Lee
Haipeng Luo
Tuomas Sandholm
Venue: NeurIPS 2022 Accept (2022)
Keywords: Uncoupled learning dynamics
optimism
swap regret
correlated equilibria

Abstract: In this paper we establish efficient and \emph{uncoupled} learning dynamics so that, when employed by all players in a general-sum multiplayer game, the \emph{swap regret} of each player after $T$ repetitions of the game is bounded by $O(\log T)$, improving over the prior best bounds of $O(\log^4 (T))$. At the same time, we guarantee optimal $O(\sqrt{T})$ swap regret in the adversarial regime as well. To obtain these results, our primary contribution is to show that when all players follow our dynamics with a \emph{time-invariant} learning rate, the \emph{second-order path lengths} of the dynamics up to time $T$ are bounded by $O(\log T)$, a fundamental property which could have further implications beyond near-optimally bounding the (swap) regret. Our proposed learning dynamics combine in a novel way \emph{optimistic} regularized learning with the use of \emph{self-concordant barriers}. Further, our analysis is remarkably simple, bypassing the cumbersome framework of higher-order smoothness recently developed by Daskalakis, Fishelson, and Golowich (NeurIPS'21).

Uncoupled Learning Dynamies with O(lgg T) Swap Regret in Multiplayer Games
Ioannis Anagnostides Carnegie Mellon University Pittsburgh, PA 15213 ianagnos@cs. cmu edu
Gabriele Farina
Carnegie Mellon University Pittsburgh, PA 15213 gfarinaccs. cmu. cmu.edu
Christian Kroer
Chung- Lee University of Southern California Los Angeles, CA 90007 Leechungo@usc.cm edu
Columbia University
New York, NY 10027
christian. www..kkrrrroolueltoo edu
Haipeng Luo
Tuomas Sandholm Camegie Mellon University Strategy Robot, Inc. Optimized Markets, Inc. Strategic Machine, Inc. Pittsburgh, PA 15213 sandholm@cs. cmu edu
University of Southern California
Los Angeles, CA 90007
haipengl@usc.o edu
Abstract
In this paper establish efficient and uncoupled learning dynamics that, when employed by all players in a general-sum multiplayer game, the swap regret each player after 7 repetitions of the game is bounded by O(log T"), improving over the prior best bounds of (log (T)). At the same time, guarantee optimal ((VT) swap regret in the adversarial regime well. To obtain these results, our primary contribution is to show that when all players follow our dynamics with a time-invariant learning rate, the second-order path lengths of the dynamics to time 7' are bounded by Ollog T',, a fundamental property which could have further implications beyond near-optimally bounding the (swap) regret. Our proposed learning dynamics combine in novel way optimistic regularized learning with the use of concorannnt barriers. Further, our analysis remarkably simple, bypassing the cumbersome framework of higher-order smoothness recently developed by Daskalakis, Fishelson, and Golowich (NeurIPS'21)..
Introduction
Online learning and game theory share an intricately connected history tracing back the inception of the modern no-regret framework with Robinson's 's analysis of fictitouus play [Robinson 1951 and Blackwell's approachability theorem [Blackwell] [956]. Indeed, the no-regret framework addresses the fundamental question of how independent and decentralized agents can "learn" with only limited feedback from their environment, and has led celebrated connections with game- theoretic equilibrium concepts [Hart and Mas-Colell, 2000 Foster and Vohra 1997]. One of the remarkable features of these results is that the learning dynamics are fully uncoupled (Hart and Mas-Coled 2000]: each player is completely agnostic to the utilities of the other players. Thus, there
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is no communication between the players or any centralized authority dictating behavior throughout the game. Instead, the only "coordination device" is the common history of play. An additional desideratum, which is fundamentally tied to the no-regret framework, is what waskaaasaaa et al. [2011] refer to as strong uncoupledness! players have no information whatsoever about the game (even their own utilities), and they only make decisions based on the utilities received as feedback throughout the repeated game.
In this context, it is well-known that there are broad families of no-regret learning algorithms that, after I" repetitions, guarantee regret bounded by O(vT), and this bound is known to be insuperable in adversarial environments [Cesa-Bianchi and Lugosi 2006]. However, this begs the question: What if the player is not facing adversarial utilities, but instead is competing with other learning agents in a repeated game? ? This question was first formulated and addressed by Daskallaii et al. 2201), who devised strongly uncoupled dynamies converging with a near-optimal rate of O log in zero-sum games, a substantial improvement over the O(I/VT) rate obtained via traditional approaches within the no-regret framework. Thereafter, there has been a considerable amount of effort in strengthening their result, leading to extensions along several important lines [Rakhlin and Sridharan 2013 Syrgkanis al. 2015] Chen and Peng 2020 Farina et al. 2019 Daskalakis et al. 2021 Anagnostides et al. 2022a Wei and Luo 2018 Foster et al. 2016]] Anagnostides et al. 2022b]. In particular, recent breakthrough result, Daskalakis et al. [2021 showed that when all players in general game employ an optimistic variant of multiplicutive weights update (MWU) (henceforth OMWU), the external regret of each player grows as Ollog (I)). That result was also subsequently extended to the substantially more challenging performance measure of swap regret [Anagnostides et al., 2022a]. Perhaps the main drawback of the latter results is the complexity of the analysis, relying on establishing a refined property for the dynamics they refer to as higher-order order smoothness. Our primary contribution in this paper is to develop a novel and much simpler framework, which furthermore improves the prior state of the art O(log" (T)) regret bounds to Olog T) in general multiplayer games.
1.1 Overview of Our Contributions
Before we state our main result, let us first introduce some basic notation. We assume that each player i E [n]] selects every iteration & of the repeated game probability distribution (mixed strategy)
over the set of available actions x²() E ((A,) (see Section 2 for further details). The following
theorem is the primary contribution of our work
Theorem 1.1 (Precise Statement in Theorem 4.4). There exist strongly uncoupled no-swap-regret learning dynamics so that when employed by all players with learning rate (1), the second- order path lengths of the dynamics up to any time T E N are bounded by O(log T); that is,
n
1 (t)
(t 11 O"logT). x
We are not aware of even an o(T) bound for the second-order path lengths under a time-invariant learning rate- rate-prior to our work, except for very restricted classes of games such zero-sum games.
template of Blum and Mansour [007]: (ii) the follow the regularizer leader (OFTRL) algorithm of Syrgkanis
The dynamics of Theorem combine: (i) the celebrated no-
et al. 2015]; and (iii) using a self-concordant barrier as a regularizer. The latter was introduced
in online learning in the seminal work of Abernethy et al. 20088), where the authors obtained the first near-optimal and efficient online learning algorithm for linear bandit optimization; the way leverage the log-barrier in the setting of no-regret learning in games is novel, and crucially
leverages the local norm induced by the regularizer. The dynamics of Theorem [.] are also efficiently implementable (see Remark 4.7
The implication of Theorem is perhaps surprising in view of the inherent cycling aspect of no-regret learning in general games. Indeed, it is by now well-understood that any no-regret dynamics
Daskalakis et al. 2 also impose that players are only allowed (privately) store only constant number of observed utilities, an assumption also espoused in our work.
'For simplicity in the exposition, we use the O(-) notation in our introduction to suppress parameters that depend (polynomially) on the natural parameters of the game; precise statements are given in Section 4

---

Reference
Algorithm
Swap Regret in Games
Adversarial Swap Regret
Blum Mansour 2007
E.g. BM-MWU
Olv m Olymlog (mlg(m)) 0(yml)
Chen and Peng 2020
BM-OMWU
O (ym(m log(m) ( O logim) log (T)) (T))
Anugnostides 2022a
BM-OMWU
This paper
BM-OFTRL-Logghe
O(nm 9/2 (T)
Oly Olymbon (l)m)g(m)))
Table 1: Prior results regarding the no-swap-regret algorithm of Blum and Mansour [2007] (BM). The second column indicates the algorithm internally employed by the "master" BM algorithm: our construction uses OFTRL with log-barrier regularization (Section 3). Further, m is the maximum number of actions available to each player. We point out that in the adversarial swap regret bound we have suppressed lower order factors in terms of T. We further remark that the near-optimal internal regret guarantee of Anagnostides et al. 2022aa] in turn implies Onm log(m) log (T)) swap regret
for each individual player, but is obtained via the algorithm of Stoltz and Lugosi (005
will fail to converge-al least for certain games (e.g., see [Milionis et al. 2022)). Nevertheless, Theorem I.] jimpiies that players will change their strategies arbitrarily slowly as the game progresses. As such, players will observe utilities that exhibit very small variation over time, immediately implying near-optimal swap regret.
Corollary 1.2 (Precise Statement in Corollaries 4.5 and 4.6). There exist strongly uncoupled no- swap-regret learning dynamics so that when employed by all players, the individual swap regret of each player is bounded by Ollog T). At the same time, when faced against udversarial utilities each player guarantees ((VT) swap regret.
Corollary 1.2 improves over the prior best bounds of Olog (T)) Daskalakis et al. 2021 Anagnos
lides et al. 2022a]: ; a comparison with prior works regarding the algorithm of Blum and Mansour to our knowledge, the first no- no-regret guar- antee general games for uncoupled methods when players use time-invariant learning rate, a feature that has been extensively motivated in prior works (see, e.g., the discussion in (Bailey and the adversarial regime as well, crucial desideratum in this line of work. Finally, swap regret is powerful notion of hindsight rationality, trivially subsuming external regret. In particular, in light of well-established connections (see Theorem 2.3). we obtain the best known rate of convergence of O log in general games.
[2007] is given in Table In fact, Corollary (orollaryy.22)ieellee
Piliouras 2019])- Corollary 1.2 also establishes near-optimality
to correlated equilibria T
Corollary 1.3. There exist strongly uncoupled learning dynamics so thut, when employed by all players, the average correlated distribution of play after T repetitions of the game is an O log approximate correlated equilibrium.
T
From a technical standpoint, our approach is conceptually remarkably simple and direct. Specifically, Theorem [.J is shown by first establishing the RVU bound-a fundamental property first identified
in [Syrgkanis al. 2013] Definition 3]-for swap regret in Theorem 4.3 the key ingredient is Lemma 4.2 which crucially leverages the local norm induced by the log-barrier regularizer over the simplex. Next, Theorem I.I follows directly by making a seemingly trivial observation: swap regrer is always nonnegative. A related approach was recently employed in (Anagnostides et al.) [202cc] for external regret, but only works for very restricted classes of games such as zero-sum. As such, we bypasses the cumbersome framework of higher-order smoothness recently introduced by Daskalakis al. 2021).
1.2 Further Related Work
The first accelerated dynamies in general games were established by Syrgkanis et al. (2015.. In particular, they identified a broad class of no-regret learning dynamics cisamiccs-atiffyiiiii satisfying the so-called RVU property-for which the sum of the players' regrets is ((1). On the other hand, they only obtained an O(T4/4) bound for the individual external regret of each player. This crucial given that the rate of convergence to coarse correlated equilibria is driven by the maximum of the external regrets. It is important to note that a bound for the sum of the external regrets does not necessarily translate to bound for the maximum since external regrets be negative. This is in stark contrast to swap regret
3

---

(Observation 2.1 a property crucially leveraged in our work. Furthermore, the O(T)/4) bounds for the individual external regret in [Syrgkanis et al. 2013] were only recently extended swap regret by [Chen and Peng 2020]. The main challenge with swap pegret-which is also the main focus of our paper-is that the underlying dynamics are much more complex, maintaining and aggregating over multiple independent external regret minimizers. In addition, the dynamics involve fixed point operation- the stationary distribution of a Markov chain posing new challenges compared to the analysis of no-external-regre algorithms (Chen and Peng 2020]. Finally, a very intriguing approach for obtaining near-optimal no-externa-reeret dynamics was recently introduced by Piliouras et al. [022]] The main caveat of that result is that the dynamies they propose not uncoupled, which has been a central desideratum in the line of work on no-regret learning in games. For this reason, the result in [Piliouras al. 2021 is not directly comparable with the previous approaches.
2 Preliminaries
In this section introduce the basic background online optimization and learning in games. For a comprehensive treatment on the subject we refer the interested reader to the excellent book of afCCesa- Cianchiaanci and Lugosi [2006].
Conventions We denote by N = (1, the set of natural numbers. We use the shorthand notation [n]] == : n..
Subscripts are typically used to indicate the player, or parameter uniquely associated with a player (such as an action available to the player). On the other hand, superscripts are reserved almost exclusively for the (discrete) time index, which is represented via the variable f. Also, the r-th coordinate of a d-dimensional vector E RRd is denoted by æ(r). Finally, we let log(-) be the natural logarithm.
:
2.1 Online Learning and Phi-Regre
Let X S Rd be nonempty convex and compact set of strategies, for some d E N. In the online learning framework the learner has to select at every iteration E N strategy x!!) E X. Then, the environment- be it the "nature" or some "adversary" ceatversar""rreuurrr returns a (linear) utility function ((()= X x (ar, u ()),, for some utility vector (*) E RR, so that the learner receives utility of (x) (t) at time In the full information model the learner receives feedback the entire utility function, represented by u The canonical measure of performance in online learning is based on the notion of regret, or more generally, on Phi-regret [Greenwald and Jafari 2003] [Stoltz and Lugosi 2007 Gordon et al. 2008 Formally, for a set of transfornations : X X. the Ø-regret of regret minimization algorithm Ri up to time horizon T E N is defined as
E(o((s()) 2u0
} [ - (0)).
T = max Reg
(1)
@ Ex
Naturally, a broader collection of transformations leads to stronger notion of hindsight rationality; canonical instantiations of Phi-regret include:
External regret (denoted by Reg): & includes only constant transformations;
Swap regret (denoted by SwapReg): & includes all possible linear transformations.
As such, swap regret induces the more powerful notion of hindsight rationality. We point out that our main focus in this paper (Section 4 will be for the special case where X is the probability simplex. A crucial property of swap regret is that SwapReg 2 0, as formalized below.
Observation 2.1. Fix any time horizon T E N. For any sequence of utilities (1) ....., (T) and any sequence of strategies ..),, it holds that SwapReg" T
> 0.
In proof, just consider the identity transformation + 3 o x + x in In contrast, this property does not necessarily hold for external regret.
Moreover, it will be convenient to model regret minimization algorithm A as a black box which interacts with its environment via the following two subroutines.

---

(i) T.NEETSSRRATEGY (): Dt returns the next strategy of the leamne;
(ii) R. OBSERVEUTILLTY R receives as feedback from the environment a utility vector u, and may adapt its internal state accordingly.
2.2 No-Regret Learning and Correlated Equilibria
fundamental connection ensures that as long as all players employ no-swap-regret learning dynamics
(in the sense that SwapReg" )) the average correlated distribution of play converges the set of correlated equilibria [Hart and Mas-Colell] 2000) Foster and Vohra 1997, Blum and Mansour) 2007 Before we formalize this connection, let us first introduce some basic background on games.
n) be the set of players, with 2 2. In a (finite) game, represented in normal form, each player i E [n] has a finite set of actions A; for notational simplicity, we will let m, = |A, 2 2. For a given joint action profile
Finite Games Let [n] ==
(a1..... ax) E X== Ad, the (normalized) utility received by player i is given by some arbitrary function us - A: 11, Players are allowed to randomize by selecting a (mixed) strategy æ; (AA = {
x E RRAL Eajes, æ[a:] =1 =1]: that is, probability distribution over the available (#1....,,,.) Rn), player receives an expected utility of
actions. For a joint strategy profile Ea (onaz(u(())) [a)] = EaEn (a(a) [[ 2y(ay].
In the problem of no-regret learning in games, every player receives as feedback at time E N a utility vector u!" E R|A. so that u,
(8) [o.] [o.] = ua x ")) Ea i~w (a, a=))], for any a, A;; here, we used the notation a-; to represent the joint action profile excluding i's component, and analogously for the notation æ - No other information is available to the player. We now ready to introduce the concept of a correlated equilibrium due to AAumann [1974].
Definition 2.2 (Correlated Equilibrium [Aumann| 1974)). A probability distribution over X A; an c-approximate correlated equilibrium, for c 2 0. if for any player E [[n] and any swap function Ai,
Φ A
Earu iu (a)) 2 (d))))
Theorem 2.3 (Folklore). Suppose that each player i [n] employs a no-swap-regret algorithm such that the cumulative swap regret up to time T N is upper bounded by SwapReg? Further, let ( - x be the average correlated distribution of play up to time T. Then, j is a max? (SwapReg) (T)- approximate correlated equilibrium.
x & xx 8 ..... & on be the product distribution at time t E [T', and f == - (())
(1)
Consequently, central challenge for correlated equilibria is that the rate of convergence is driven by the maximum of the swap regrets; this is in contrast to, for example, the rate of convergence of the (utilitarian) social welfare in smooth games, which is driven by the sum of the players' external regrets [Syrgkanis et al. 2015 Roughgarden 2015).
3 Optimistic Learning with Con-Concordaat Barriers
Optimistic follow the regularizer leader (OFTRL) (Syrgkanis et al. 2015 a predictive variant of the standard FTRL paradigm. Specifically, OFTRL maintains internal prediction vector m!!)) Rd and can be expressed with the following update rule for E N.
t-1 (+) = x. m + Σ (r))
(1) = arg max #EX
)
R(xx)
(OFTRL)
here, 77 > 0 serves as the learning rate, and R. is the regularizer. For convenience, we also define (0) = arg mingex R(x). Unless specified otherwise, (OFTRL) will be instantiated with m!!) = u (t-1), for E N. (For convenience in the analysis, and without any loss, we assume that players initially obtain the utilities corresponding to the other players' strategies at time = 0.)
In [Syrgkanis et al. 2015 the regularizer R was assumed be 1-strongly convex with respect to some (static) norm
on Rd. On the other hand, we are introducing an important twist: R will
5

---

be a self-concordant barrier functiio over X In this context, we first extend (in Appendix B) the so-called RVU bound established [Syrgkamis et al., 2015] under self-concordant regulanization. More precisely, we assume that X' has nonempty interior int( Further, for u E Rd the primal local norm with respect to E E (n'( is defined || == v /u (zz)), while the dual norm defined as || = Vu (V²R(z))) -u,, assuming that R. nondegenerate- in the sense that its Hessian is positive definite. Finally, for the purpose of the analysis, we let g denote the be the leader sequence (see (BTL) in Appendix B); attempt was made to optimize universal constants.
Theorem 3.1 (RVU for Self Celf-Concordant Regularizers). Suppose that R is a nondegenerate self- concordant function for int (n)) Moreover, let 1) > be such that nllee(t) "m!" (|,,e!1)) S and 7l|m(() (I 1I S 1 for all t E [T]. Then, the regret Reg' J (x*) of (FFRL) with respect to any ( can be bounded by
2
comparator x² E iin((X)) under any sequence of utilities u1))
R(x*) + 2n
(1(t) m 11
1
-1z(0)-'())
- g000 10 + ||x)(t) -g
((t 11gg()))s)))
4n
Here, we also used the standard notation Reg" (x=) == Et= - x011, (u()),) Next, we instantiate
Theorem using the log- log-barrier on the (probability) simplex: R(x) E log(z/r)). While the probability simplex has empty interior, there a simple transformation on the relative interior relint A ") that addresses that issue (see Appendix B
Corollary 3.2 (RVU for Log-Barries on the Simplex). Suppose that R is the log-barrier on the simplex and 1j S 1. Then, the regret of (OFTRL) under any sequence of utilities u ,..., (T) can be bounded as
(x")xx))= R(x*) + 2m
(t))) u 11
1
[zx(1)
x (t-1)) (e
(t(()))
167
for any x" E relint(AA), where (xx(0) (tt-
13
Ed=
[r)" 2:
-1 2
[
We remark that a similar regret bound for optimistic mirror descent under barrberrier regularization was shown by (Wei and Luo 2018 Theorem 7J.
Rakhlin and Sridharan 2013
4 Main Result
In this section we sketch the proof of our main result, namely Theorem 1.1
leading Corollaries T.2 and [1.3, detailed proofs are deferred to Appendix C In this context, we first employ the general template Blum and Mansour [2007) for constructing a no-swap-regret minimizer Rawop Over the simplex. We proceed with a brief overview of their construction (summarized in Algorithm Ip. In the sequel, we first perform the analysis from the perspective of single player, without explicitly indicating so in our notation.
The Algorithm of Blum and Mansour Blum and Mansour (007 construct a "master" regret minimization algorithm R Rewap by maintaining a separate and independent external regret minimizer
R, for every action a E A. To compute the next strategy, R. Rsoop first obtains the strategy x!!) (AA) of Rg, for every a E A. Then, a (row) stochastic matrix Q(t) e g/ constructed, so that the row associated with action
A is equal to the distribution (4) while Rswap outputs as the next strategy (+) E ((AA any stationary distribution of ((); that is, (Q(!) ((()) (Q()))=x(())
(+)), Next, upon observing a utility (t) R|A Rswap forwards to each individual regret minimizer R. the utility u = u (n E TR| TRIAI, This construction is summarized in Algorithm
'To keep the exposition reasonably self-contained we give an overview of self-concordant barriers in Appendix[A]

---

Algorithm 1:
Blum and Mansour [0077]
Input: set of external regret minimizers {RoloEA' each for the simplex ((A)
function NEXTŠTRATEGY()
Q(1) < [XX|A
for A do
1 [a NEXTSTTRATT))) xx1) STATIOVARRDDISTRIBUUIOOOO
return (1)
7 function OBSERVEUTILITT(X"))
for A do
R. DABBBBEEEUUUULLIY(("MPM (!)
Blum and Mansour 2007 showed that this algorithm guarantees no-swap-regret long as each individual regret minimizer has sublinear external regret; this is formalized in the theorem below.
Theorem 4.1 (From External to Swap Regret [Blum and Mansour 2007]). Let SwapReg" be the swap regret of Rewap and Rega be the external regret of Ra for each A, up time T N. Then,
SwapReg"
Reg
aEA
In this context, we will instantiate each individual regret minimizer R. with (OFTRL) under log- barrier regularization and the same learning rate 77 > We will refer the resulting algorithm as BM-OFTRE HN-OOFRRL-LoBar A central ingredient in our proof of Theorem 1.1 is to establish that the resulting no-swap-regret algorithm Rswap will enjoy an RVU bound. stated in Theorem 4.. To this end, we first apply Corollary 3.2 for each individual regret minimizer Ra, implying that SwapReg" ΣAEA Reg. (by Theorem 4.1 is upper bounded as
and
2m2 log
SwapReg" <
+ 2n Σ
Σ
[a] - (t-1)
()-1)) [a]1 (t
aEA
[(001) x0(1-111 (t-1))
(t-1)
167
REA [=1
The log T factor derives from the diameter of the log-barrier regularizer (see Theorem A.9 and appears to unavoidable using our approach. Now the crux in establishing an RVU bound for Ri sowap to upper bound the last term in (2) in terms of the "movement" of the stationary distribution. This is exactly where the local norm induced by the log-barric turns out to be crucial, leading to the following key technical ingredient.
Lemma 4.2. Suppose that each regret minimizer R. employs OFTRL with log-barrier regulariza- N,
tion and r) S 16. Then, for any
[|x( (t- S 64|AA Σ |xl x (1-11)
aEA
Intuitively, this lemma ensures that the "movement" of the stationary distribution is smooth in terms of the "movement" of each row of the transition matrix Q(1), To show this, we use the Markov chain tree theorem (Theorem C.3 which provides a closed-form combinatorial formula for the stationary distribution an ergodic Markov chain, along with the fact that the log-barrie barrier regularizer guarantees "multiplicative stability" of the iterates (Corollary C.I). While similar in spirit results have been documented the literature for dynamics akin to MWU [Candogan et al. 2013 Chen and Peng 2020), our proof of Lemma 4.2 crucially hinges on the local norm induced by the log-barrier regularizer. Thus, we are now ready to derive an RVU bound for swap regret.
Theorem 4.3 (RVU Bound for Swap Regret). Suppose that each R. employs OFTRL with log- barrier regularization and 77 < 128.m Then, for T 2 2, the swap regret of Rewap is bounded
7

---

as
2m log T
SwapReg
4n
(1 u 11
xx x (c- (1-1 112.
7
2048mm
This theorem follows directly from (2) and Lemma 4.2 So far we have focused on bounding the swap regret of each player when faced agansst arbitrary utilities. Next, we use Theorem to establish new fundamental property when all players employ the dynamies. Our proof crucially relies on the (recall Observation
seemingly insignificant fact that SwapReg!
Theorem 4.4 (Log- BegudBdddd Second-Order Path Lengths), Suppose that each player E [n|] employs BY-OFTRL-LLogar with 128(n max [ym=]] Then, for T 2 2.
T
(1-1) S 8192 max mmx{m;)
Σ i=1
m log
sEim]
Proof. Consider any player i [n] Given that [u,(a)) s 1, for any E A (by the normalization assumption), we have that for any E [T].
1u u; (t-1) 11x S
Σ G-EEA_
[ay]
1 J
(t-1)
I1:
where used that the total variation distance between two product distributions is bounded by the sum of the total variations of each individual marginal distribution [Hoeffding and Wolfowitz 1958 Thus,
)
2 S (n Σ j
(111)) ul!" 110
Σl j+i
2
|a=00 x 11.
As result, using Theorem 4.3 we conclude that Σi= SwapReg? can be upper bounded by
log?
m
+ 4m(n
1)
T
|
(0)
(1-1)
|1
a (t)
x.
17
2048m
jtt t=1
log T
m?
4n(n
1)²
1
(1)
x (t-
11-)
|
1
2048m
m
1
(t-1)
2 log
x
4096
m&T
1=1
since
But, given that 0 < E SwapReg, T
we conclude that
128(n-1) max ( (mm))'
1
(t-1) x
1 < 8192 max
2 m log T.
maxielnl (mms)
[n]
i=1
We not aware of even o(T') bounds for the second-order path lengths in prior works (using inne-invariant learning rate), except in very restricted classes of games such as zero-sum and potential games [Anagnostides al. 2022c An example of the implication of Theorem 4.4 in variant of
Shapley 's game [Shapley 1964 Daskalakis et al. 2010)] is illustrated in Figure 1 Although the dynamics appear to cycle, and the Nash gap the maximum of the best response gaps- is always large. the players are changing their (mixed) strategies with gradually diminishing speed; further discussion and experiments included in Appendix D
As an immediate consequence, combining Theorem with Theorem implies near-optimal individual swap regret.

---

1.0
Player
Goo
0.8
Player
Probability
0.8
Player
0.6
0.4
Player
0.4
0.2
0.2
0.0
0.0
15000
20000
15000
25000
Iteration
Iberation
Figure 1: The trajectories of the BN-OFTRL-LogBar algorithm.
Corollary 4.5 (Near-Optimal Individual Swap Regret). Suppose that all players use BN-OFTRL--Logar with 1) 128(n maxccto (ymm Then, the individual swap regret SwapReg! up to time T 2 2 of each player i E [n]] can be bounded as
SwapReg, T s 256 max (ymz) JE[m]
(n- 1)m
Σ my
log T.
We point out that our distributed protocol makes the very mild assumption that each player knows upper bound on the total number of players and the maximum number of actions in order to appropriately tune the learning rate. Further, as is the case with the result in [Daskalakis et al. 2021]] the individual regret of each player predicted by Corollary 4.5 grows linearly with the number of players. This can be unsatisfactory in games with large number of players-i.e -ie,, n > 1. For this reason, in Theorem C.4 we refine and improve the guarantee of Corollary |.5 in games where the utility of each player depends only on small number of other players, and each player's actions only affect small number of others players; no other constraint is imposed the game. Understanding whether the linear dependence on is necessary to obtain near-optimal (swap) regret is left as an interesting question for future work.
Finally, we adapt the learning dynamics so that each player enjoys at the same time near-optimal swap regret in the adversarial regime as well.
Corollary 4.6 (Adversarial Robustness). There exist dynamics such that when all players follow them the individual swap regret of each player grows as in Corollary 4.5 Moreover, when faced against adversarial utilities, such that [|u 11x0 for all E [T]. the algorithm guarantees that
(t)
n
SwapReg? T < 256 max }mj} jE[n]
(n- (n-1m²
Σ m3 log T + 2 m. log m,T 2.
Our adaptation is particularly natural: If all players follow the prescribed protocol, Theorem 4.4 implies that the observed utilities of each player i will be such that Σ ||u u, (r- |cc
Ollog t). So, if at any time the player identifies that the previous condition was violated, it suffices to switch no-swap-regret minimizer (such BM-MWU) tuned to face advarsarial losses-in which case it is crucial to vanishing learning rate 17 O(1/TT).
Remark 4.7 (Numerical Precision). As is standard, we assumed that the iterates of (OFTRL) were computed exactly, without taking into account issues relating to numerical precision. To justify this, one can use Damped Newton's 's method in order to determine an e-nearby point to the optimal in Ollog log(1/ iterations (Nemirovski and Todd 2008). This would extend all the regret bounds with up to O(eT) error. So, with only O(log log 7') repetitions of Damped Newton's method (per iteration) the error in the regret bounds becomes (11) and all of our guarantees immediately extend; Farrnn al. 2022 Appendix A.5] for analogous extension under approximate iterates.

---

Discussion
Our main contribution this paper was to establish a fundamental new property characterizing the trajectories of certain uncoupled no-regret learning dynamics, summarized in Theorem T.1 This property directly guarantees the best known and near-optimal bound of O(log T)) for the swap regret incurred by each player in general multiplayer game. Investigating further consequences of Theorem 1.1 is an interesting direction for the future. We also believe that our framework could have new implications for learning in games with partial information; e.g., (Wei and Luo, 2018). Another interesting avenue to extend our scope to more general and combinatorial sets beyond the probability simplex, in order (efficiently) encompass, for example, games in extensive form.
Further, our no-swap-regret learning dynamics have external regret trivially bounded according to Corollary 4.5 Consequently, our construction yields no-external-reeree learning dynamics with a more favorable dependence on compared to DDakkalakis et al. 2021] (log compared to the log'(7) of the latter), but with a worse dependence on the number of actions (polynomial rather than logarithmic). Our method also has higher per-iteration complexity. For these reasons, extending the scope of our framework beyond self-concordant regularization is an important direction for future rescarch. Indeed, we conjecture that OMWU has bounded second-order path lengths, property that would imply the first uncoupled learning dynamics with bounded regret, but establishing that likely requires new insights.
Acknowledgments
We are thankful the anonymous NeurIPS reviewers for many helpful comments, Ioannis Anag- nostides is grateful to Dimitris Achlioptas for helpful discussions. Christian Kroer is supported by the Office of Naval Research Young Investigator Program under grant N00014-22-1-2530 Haipeng Luo is supported by the National Science Foundation under grant I[S-1943607 (part of this work was done while he was visiting the Simons Institute for the Theory of Computing). Tuomas Sandholm supported by the National Science Foundation under grants IIS- IS-1990403 and CCF-1733556.
References
Julia Robinson. An iterative method solving game. Annals of Mathematics, 54:296-301, 1951.
David Blackwell. An analog of the minmax theorem for vector payoffs. Pacific Journal of Mathemat- ics, 6:1-8, 1956.
Sergiu Hart and Andreu Mas-Coled A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68: 1150, 2000.
Dean Foster and Rakesh Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21 :50-55, 1997.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. In Anmual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
Nicolo Cesa- Bianchi and Gabor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances Neural Information Processing Systems, pages 3066-3074, 2013.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, pages 2989-2997, 2015.
Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
10

---

Gabriele Farina, Christian Kroer, Noam Brown, and Tuomas Sandholm. Stable- preeicppe optimistic counterfactual regret minimization. International Conference on Machine Learning (ICML), 2019.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. CoRR, aws/a100..//2222 069244, 2021.
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In STOC '2: 54th Annual ACM SIGACT Symposium on Theory of Computing. 2022. pages 736-749. ACM, 2022a.
Chen- Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages PMLR, 2018.
Dylan J. Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. Learning in games: Robustness of fast convergence. In Advances in Neural Information Processing Systems 29; Annual Conference on Neural Information Processing Systems 2016, pages 4727-4735, 2016.
Joannis Anagnostides, Gabriele Farina, Christian Kroer, Andrea Celli, and Tuomas Sandholm. Faster no-regret learning dynamics for extensive-form correlated and coarse correlated equilibria. In EC 22: The 23rd ACM Conference on Economics and Computation, 2022, pages 915-916. ACM, 2022b.
Avrim Blum and Yishay Mansour. From external to internal regret. J. Mach. Learn. Res., 1307-1324, 2007.
Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In In Proceedings of the 21st Annual Conference on Learning Theory (COLT), 2008
Jason Milionis, Christos Papadimitriou, Georgios Piliouras, and Kelly Spendlove. Nash, conley, and computation: Impossibility and incompleteness in game dynamics, 2022.
James 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, NeurIPS 2019, pages 12977-12987,2011
Gilles Stoltz and Gábor Lugosi. Internal regret in on-line portfolio selection. Machine Learning, 59 (1-2):125-1533 2005.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning, ICML 2022, volume 162 of Proceedings of Machine Learning Research, pages 536-581. PMLR, 2022c.
Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Optimal no-regret learning in general games: Bounded regret with unbounded step-sizes via clairvoyant mwu. arXiv preprint arXiv:2111.1477 2021.
Amy Greenwald and Amir Jafari. general class of no-regret learning algorithms and game-theoretic equilibria. In Conference Learning Theory (COLT), Washington, D.C., 2003.
Gilles Stoltz and Gábor Lugosi. Learning correlated equilibria in games with compact sets of strategies. Games Econ. Behav., 59(1):187-200 2007.
Geoffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th international conference on Machine learning, pages 360-367. ACM, 2008.
Robert Aumann. Subjectivity and correlation randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974.

---

Tim Roughgarden. Intrinsic robustmess of the price of anarchy. J. ACM. 62(5):32:1-32444 2015.
Ozan Candogan, Asuman E. Ozdaglar, and Pablo A. Parrilo. Dynamics in near-potential games. Games Econ. Behav., 82:66-90 90, 2013.
Wassily Hoeffding and J. Wolfowitz. Distinguishability of sets of distributions. The Annals of Mathematical Statistics, 29(3):700-718, 1958.
Lloyd S Shapley. Some topics in two-person games. In M. Drescher, L. S. Shapley, and A. W. Tucker, editors, Advances Game Theory. Princeton University Press, 1964.
Constantinos Daskalakis, Rafael M. Frongillo, Christos H. Papadimitriou, George Pierrakos, and Gregory Valiant. On learning algorithms for nash equilibria. In Algorithmic Game Theory Third International Symposium, SAGT 2010, volume 6386 Lecture Notes in Computer Science, pages 114-125. Springer, 2010.
Arkadi S Nemirovski and Michael J Todd. Interior-point methods for optimization. Acta Numerica, 17:191-234, 2008
Gabricle Farina, Joannis Anagnostides, Haipeng Luo, Chung-Wet Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning for general convex games. CoRR, abs/2206.08742. 2022.
Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, 2004.
Arkadi Nemirovski. Interior point polynomial time methods in convex programming. Lecture notes, 42(16):3215-3224, 2004.
V. Anantharam and P. Tsoucas. A proof of the markov chain tree theorem. Statistics & Probability Letters, 8(2)1199-192, 1989.
David Avis, Gabriel D. Rosenberg, Rahul Savani, and Bernhard Stengel. Enumeration of nash cquilibria for two-player games. Economic Theory, 42(1):9-37, 2010.
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] See Section 5
(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 all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Appendix [
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix [
(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) If your work uses existing assets, did you cite the creators? [N/A]
12

---

(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 URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) 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 to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "yXnmIfighWQ", "reviewer": "Reviewer_8Ear", "summary": "This paper studies accelerated no-regret learning algorithms for minimizing the swap regret in multi-player normal-form games. The main contribution is an algorithm that enjoys $O(\\log T)$ swap regret when employed by all players simultaneously, which improves slightly over the prior best result $O(\\log^4 T)$. The algorithm BM-OMWU-LogBar combines the classical Blum & Mansour’s no-swap-to-external reduction (henceforth BM reduction), and Optimistic Follow-The-Regularized-Leader (OFTRL) with log-barrier regularization for external regret minimization.\n", "questions": "In Table 1, for fair comparisons, perhaps the algorithm “SL-OMWU” from (Anagnostides et al. 2021) should also be mentioned? That algorithm achieves $O(n\\log m\\log ^4 T)$ internal regret, and thus $O(nm\\log m\\log^4 T)$ swap regret, by the standard bound SwapReg <= m * max{InternalReg, 0}.\n\nI feel like the importance of the “nonnegativity of regret” should be emphasized even more in the presentation. Right now, this fact is only briefly mentioned in Line 93-97 & 261-262. In my opinion, this is precisely what allows the proof to be much simpler than (Daskalakis et al. 2021), and closer to the original arguments of (Rakhlin & Sridharan 2013, Syrgkanis et al. 2015). \n\n---\nAfter rebuttal: I thank the authors for their response, and would be glad to keep my current evaluation of the paper.\n", "limitations": "/", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper is an addition to the line of work on accelerated no-regret learning in normal-form games, when all players deploy the same no-regret learning algorithm. This type of results imply faster than $1/\\sqrt{T}$ convergence to equilibria in games and thus could be of interest to the online learning / games community.  \nIn particular, the result can be seen as a follow-up to the recent breakthrough of $O(\\log^4 T)$ regret of Optimistic Hedge in multiplayer general-sum games (Daskalakis et al. 2021) and $O(\\log^4 T)$ swap regret in the follow-up work of (Anagnostides et al. 2021). \n\nThe main strength of this paper, in my opinion, is a new proof route of this type of result using the nonnegativity of individual regrets plus the log-barrier regularization. The proof route appears to be much simpler than the above existing work. \n* The “nonnegativity of individual regrets”, which holds for the swap regret but not the usual external regret, allows the individual swap regrets for each player to be bounded by their total (summed) regrets, which is much simpler to bound. For external regret, this lack of nonnegativity was precisely the reason why $O({\\rm polylog}(T))$ regret in multiplayer general-sum games (Daskalakis et al. 2021) was much more challenging to establish than two-player zero-sum games (Rakhlin & Sridharan 2013). \n* The log-barrier regularizer induces an RVU bound whose “negative iterate stability” term directly controls the stability of the fixed-point operation within the BM reduction (Corollary 3.2 & Lemma 4.2), which can then directly bound the \"positive loss stability\" term within the RVU bound when summed over all players\n\nOverall, I think this line of arguments is new to this line of work (even though the two facts above are standard / known), and substantially simplifies the challenge of establishing $O({\\rm polylog}(T))$ regret over the arguments of (Daskalakis et al. 2021, Anagnostides et al. 2021).\n\nWeaknesses:\n\nThe improvement from $\\log ^4T$ to $\\log T$ is perhaps a bit incremental. There is also an improvement in the action ($m$) dependence over the prior algorithm BM-OMWU, though I think another algorithm SL-OMWU in the same work achieves even better action dependence already? (see “Questions” below.)\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "u62oa6K6FmL", "reviewer": "Reviewer_Wcat", "summary": "The authors consider the problem of no-regret learning in general-sum multiplayer games. They propose an algorithm for each player which guarantees that the individual swap regret after $T$ rounds is bounded by $O(\\log T)$, improving upon the previously best known bound of $O(\\log^4 T)$ in general-sum games. This in turn leads to an algorithm for computing an approximate correlated equilibrium in general-sum games. The proposed algorithm for each player is decentralized, in the sense that every player only needs to observe her own losses in order to update her policy after each round, and is oblivious to the actions taken by other players. In addition, the authors establish adversarial robustness of the proposed algorithm, i.e. that each player is guaranteed $O(\\sqrt{T})$ regret when faced with an adversarial loss sequence.\n\nThe algorithm follows a swap-regret minimization paradigm introduced originally by Blum and Mansour (2007), instantiated over several instances of \"optimistic follow-the-regularized-leader\" with a log-barrier regularizer. The analysis in the paper mainly hinges on two properties of the learning dynamics: $O(\\log T)$-bounded second-order path length of each player's policy sequence, and an RVU property of the swap-regret minimization algorithm.", "questions": "The method of analysis presented in the paper naturally raises the question of whether or not the Optimistic Hedge algorithm (which has been shown by Daskalakis et al. [2021] to obtain polylog($T$) regret) enjoys a bounded path length property similar to the property given in Theorem 4.4 for BM-OFTRL-LogBar. If this was indeed the case, then combining the RVU property of optimistic hedge with this bounded path length would yield a logarithmic regret bound, with a considerably simpler algorithm. My question for the authors regarding this observation is whether or not they looked into the possibility of optimistic hedge having log-bounded path length, or rather is it maybe straightforward to see that it does not have this property?", "limitations": "See the main review.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The main result of this paper is highly non-trivial and strictly improves upon the previously known regret guarantees in general-sum games in terms of the dependence on $T$. In addition, this result is achieved by a simple and efficient decentralized algorithm.\n* The analysis of the proposed algorithm is novel, interesting and surprising in its simplicity compared to previous works. Specifically, the use of swap-regret minimization in order to guarantee non-negativity of the regret, which together with a non-trivial RVU property, yields a path length bound on the players' iterates, and in turn the desired regret bound.\n* The proofs of the technical claims presented in the paper are clear and the novel ideas in the analysis may be useful for future works.\n\nWeaknesses:\n* The following is only a minor issue, though I think it's worth mentioning.  The regret bound presented in the paper suffers from a polynomial dependence on $m_i$, the number of actions available to each player. This is in contrast to the previously best known regret bound of Daskalakis et al. (2021) in which the dependence on the number of actions is only logarithmic. Presumably this dependence on $m_i$ stems from the fact that each player $i$ uses an algorithm comprised of $m_i$ instances of optimistic FTRL, and this causes the number of actions to appear as a multiplicative factor in the regret bound. I think the authors could briefly discuss this discrepancy compared to the previous result by Daskalakis et al., even though it is arguably a lot less substantial than the improved dependence on $T$.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MYultwGy67", "reviewer": "Reviewer_YHrW", "summary": "\nThis paper studies how to design an uncoupled online learning algorithm to learn a correlated equilibrium, a fundamental problem in online learning and game theory. This paper develop a novel framework to analyze Optimistic FTRL that bypasses the high-order differentiation framework of [DFG21]. It gives regret bounds with better $T$ dependency compared to previous work.\n", "questions": "\n1. I would think it as a little overclaim by saying the framework *bypassing* the *cumbersome* framework of [DFG21]. First, [DFG21] could give regret bound that only scale with $m$ while this paper requires $m^{5/2}$. Therefore, I think it is inappropriate to say that the framework could bypass the framework of [DFG21], because it could be possible (though might be unlikely) that the framework of [DFG21] could not be bypassed to show regret bound that only scales with $m$. \n3. In Table 1, $O(\\sqrt{m \\log mT})$ should be written as $O(\\sqrt{m T \\log m})$ in order to avoid confusation with $O(\\sqrt{m \\log(mT)})$.\n4. If one only need to converge to coarse correlated equilibrium, could the algorithm in this paper (perhaps without the BM modification) give better regret bound with dependency on $m$ smaller than $m^{5/2}$? \n5. Do we have a good explanation for why some plots in Figure 2 oscillates? and why the plot (2,2) seems not to scale with $O(\\log T)$ at all?", "limitations": "\n1. The regret bound only scales with $m^{5/2}$, making it worse than the bounds in previous work. Though the $\\log T$ result is strong, from a learning perspective, it is more important to optimize dependency on polynomial factors instead of poly-log factors. I think the author acknowledged this. ", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n\nStrengths:\n1. This paper gives the first regret bound that only scales with $O(\\log T)$, improving upon the previous best $O(\\log^4 T)$ dependency. \n2. The algorithm in this paper maintains both $\\log T$-type swap regret and $\\sqrt{T}$-type adversarial regret, which is desirable from both theoretical and empirical perspectives.\n3. Synthetic experiments are conducted to illustrate the theoretical results.\n4. The paper is well-organized and the writing is good. I did not find typo.\n\nSee Limitations for 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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept