Near-Optimal No-Regret Learning Dynamics for General Convex Games
Authors: Gabriele Farina
Ioannis Anagnostides
Haipeng Luo
Chung-Wei Lee
Christian Kroer
Tuomas Sandholm
Venue: NeurIPS 2022 Accept (2022)
Keywords: No-regret learning
optimism
extensive-form games
convex games

Abstract:       A recent line of work has established uncoupled learning dynamics such that, when employed by all players in a game, each player's regret after $T$ repetitions grows polylogarithmically in $T$, an exponential improvement over the traditional guarantees within the no-regret framework. However, so far these results have only been limited to certain classes of games with structured strategy spaces---such as normal-form and extensive-form games. The question as to whether $O(\mathrm{polylog} T)$ regret bounds can be obtained for general convex and compact strategy sets---as is the case in many fundamental models in economics and multiagent systems---while retaining efficient strategy updates is an important question. In this paper, we answer this in the positive by establishing the first uncoupled learning algorithm with $O(\log T)$ per-player regret in general convex games, that is, games with concave utility functions supported on arbitrary convex and compact strategy sets. Our learning dynamics are based on an instantiation of optimistic follow-the-regularized-leader over an appropriately lifted space using a self-concordant regularizer that is peculiarly not a barrier for the feasible region. Our learning dynamics are efficiently implementable given access to a proximal oracle for the convex strategy set, leading to $O(\log\log T)$ per-iteration complexity; we also give extensions when access to only a linear optimization oracle is assumed. Finally, we adapt our dynamics to guarantee $O(\sqrt{T})$ regret in the adversarial regime. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-art regret bounds either in terms of the dependence on the number of iterations or on the dimension of the strategy sets.

Near-Optimal No-Regret Learning Dynamics for General Convex Games
Gabriele Farina"
Ioannis Anagnostides" Carnegie Mellon University Pittshurgh, PA 15213
Carnegie Mellon University Pittsburgh, PA 15213 gfarinaccs. cmu. edu
ianagnos@cs. cmu. .du
Haipeng Luo University of Southern California Los Angeles, CA 90007 haipengl@usc.om edu
Chung- Wei Lee
University Southern California Los Angeles, CA 90007 Leechung@usc.edn edu
Christian Kroer Columbia University
Tuomas Sandholm
Carnegie Mellon University Strategy Robot, Inc. Optimized Markets, Inc. Strategic Machine, Inc. Pittsburgh, PA 15213 sandholm@cs. cmu, edu
New York, NY 10027
christian chrristtian..krrr@@couubbbbb. kroer@roolumiaa.edd
Abstract
A recent line of work has established uncoupled learning dynamics such that, when employed by players in game, each player's regret after T repeti- tions grows polylogarithmicaly in T, an exponential improvement over the tra- ditional guarantees within the no-regret framework. However, so far these re- sults have only been limited to certain classes of games with structured strat- egy spaces-such as normal-form and extensive-form games. The question as to whether (polyyog 7) regret bounds can be obtained for general convex and compact strategy setch occur many fundamental models economies and multiagent systems-whin tant question. In this paper, we answer this in the positive by establishing the first uncoupled learning algorithm with (log T') per-player regret in general convex games, that is, games with concave utility functions supported on arbitrary convex and compact strategy sets. Our learning dynamics based optimistic follow-ther reeguaee-eeullrizedd leader over an appropriately lifted space using a self-concordant regularizer that is peculiarly not barrier for the feasible region. Our learning dynamics are efficiently implementable given access to proximal oracle for the convex strategy set, leading to O(lgg log T') per-iteration complex- ity; we also give extensions when access to only a linear optimization oracle is assumed. Finally, we adapt our dynamics to guarantee O(vT)) regret in the adver- sarial regime. Even in those special cases where prior results apply, our algorithm improves over the state-of-the-an regret bounds either in terms of the dependence on the number of iterations or on the dimension of the strategy sets.
retaining efficient strategy updates is impor-
instantiation of
Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Introduction
Regret minimization is a celebrated framework that has been central in the development of online learning and the theory of multiagent systems. Indeed, fundamental connections have been forged between no-regret learning and theoreth solution concepts [Freund and Schapire, 1999, Hart and Mas-Colell, 2000, Foster and Vohra, 1997, Roughgarden, 2015]. More broadly, regret is an intrinsic measure of performance in online learning and games. Furthermore, regret minimization algorithms have enjoyed remarkable practical success, being a primary component in recent land- mark results in Al [Bowling et al., 2015, Moravčík et al., 2017, Brown and Sandholm, 2017, 2019]. These advances were guided by game-theoretic principles, made possible by training the AI agents using self-play under regret-mining minimizing algorithms, an approach that has proven to be more scal- able compared to linear programming techniques. Nevertheless, the traditional no-regret framework is overly pessimistic, insisting on modeling the environment in a fully adversarial way. While this well-understood worst-case view might be justifiable for applications such a security games, it could be far from optimal in more benign and predictable environments, including the setting of training agents using self-play, This begs the question: What are the optimal performance guarantees we can obtain when learning agents are competing against each other in general games?
This fundamental question was first formulated and addressed by Daskalakis et al. [2011] within the context of zero-sum games. Since then, there has been a considerable interest in extending their guarantee to more general settings [Rakhlin and Sridharan, 2013, Syrgkanis al., Foserr Foster al., 2016, Chen and Peng, 2020, Daskalakis and Golowich, 2022, Piliouras et al., 2022]. In particular, Daskalakis et al. [2021] recently established that when all players in a general normal- game employ an optimistic variant of multiplicatiive weights update (MWU), the regret of each player grows nearly-optimally as O(log" T) after T repetitions of the game, leading to an exponential im- provement over the guarantees obtained using traditional techniques within the no-regret framework. However, while normal-form games are a common way to represent strategic interactions in theory, most settings of practical significance inevitably involve more complex strategy spaces. For those settings, any faithful approximation of the game using the normal form is typically inefficient, re- quiring an action space that exponential in the natural parameters of the problem, thereby limiting the practical implications of those prior results. This motivates our central question:
Can we establish near-optimal, efficiently implementable, and strongly uncoupled no-regrel learning dynamics in general convex games?
Convex games are a rich class of games wherein the strategy space of each player is an arbitrary convex and compact set, while the utility of each player is an arbitrary concave function (see Sec- tion 2 for a formal description). games, but go well-beyond to many other fundamental settings in economic theory including routing games, resource allocation problems, and competition between firms. Our primary contribution in this paper is to substantially extend prior results to all such games, addressing Question
such, convex games encompass normal-form and extensive-fore
1.1 Our Contributions
In this paper we introduce a novel no-regret learning algorithm, which we coin listed log-regularized optimistic follow the regularized leader (LRL-OFTRL). LRI-OFTRL settles Question in the posi- tive, as summarized in the following theorem.
Theorem (Detailed version in Theorem 4). Consider any general convex game. When all players employ our strongly uncoupled learning dynamics (LRL-OFTRL) the regret of each player grows as Olog T). At the same time, if the player is facing adversarial utilities we guarantee O(VT)) regret.
Importantly, our learning dynamics are efficiently implementable given access proximal oracle for the set (Equation (7)), requiring only O(log log 2') operations per iteration (Theorem 5); such an oracle weaker than relatelivvely standard in convex optimization quadratic optimization oracle. We also point out extensions under a weaker linear optimization oracle, albeit with a worse per-iteration complexity (Theorem 6). Our no-regret learning dynamics imply the first efficiently implementable and near-optimal regret guarantees in general convex games, significantly extending
Forr simplicity in the exposition we use the O(-) notation in our introduction to suppress time- inneeindeenndent parameters that depend (polynomially) the game; precise statements deferred to Section 3.

---

Method
Applies to
Regret bound
Cost per iteration
OFTRL / OMD
General convex set
OVVIRT44/
Regularizer- & oracle- dependent
[Syrgkanis et al., 2015]
OMWU
Simplex A
O log doog T)
O(d)
[Daskalakis et al., 2021]
Clairvoyant MWU
(n
Simplex A
O(d)
[Piliouras al., 2022]
Subsequence only?
Kemeliied OMWU
Polytope Ωt = col with V = [0.1]4
On [V] log" T)
d of kemel
[Farina et al., 2022]
Oracle depeedendedddntt:
LRL-OFTRL [This paper]
General convex set O( log
O log 2) proximal oracle calls
X' C R
Oppoyy 7) linear opt. oracle calls
Table 1: Comparison of prior results on minimizing external regret in games. For simplicity, we have suppressed dependencies on the smoothness and the range of the utilities. We use to denote the number of players: I to denote the number of repetitions; 9 indicate a parameter that depends on the regularizer; col' to denote the convex hull of V; and || to denote a bound on the maximum & norm of any strategy. & Unlike all other algorithms. the full sequence of iterates produced by Clairvoyant MWU (CMWU) is not known to achieve sublinear regret. Rather, after running CMWU for T' iterations, only a smaller subsequence of length ( log T') iterates is known to attain the regret stated in the table. So, we remark that in order to achieve a comparable approximation of coarse correlated equilibrium, CMWU needs to be run for ( log T) iterations.
the scope of prior Oppolylog rregeet guarantees [Daskalakis et al., 2021, Farina et al., 2022]; a comparison with prior approaches is included in Table 1. We remark that Theorem establishes near-optimal regret both under self-play, and in the adversarial regime-meaning that the other players act so as to minimize the player's utility; the latter feature of adversarial robustness has been a central desideratum in this line of work (e.g., see the discussion in [Kangarshahi et al., 2018, Daskalakis al., 2011]).
Our proposed learning dynamics lie within the general framework of optimistic no-regret learning, pioneered by Chiang al. [2012] and Rakhlin and Sridharan [2013]. We leverage the OFTRL algo- rithm of Syrgkanis et al. [2015], but with some important twists. First, as detailed in Algorithm 1, the OFTRL optimization step is performed over a "lifted" space. While prior work in online learn- ing has employed similar in spirit approaches [Lee et al., 2020, Luo et al., 2022], our lifting is quite different, ensuring that the regret incurred by OFTRL is nonnegative (Theorem 2). Further, we employ a logarithmic self-concordant regularizer; interestingly, and perhaps surprisingly. this not barrier for the underlying feasible set. This deviates substantially from the typical use of self-concordant regularization (especially within the bandit setting [Abernethy et al., 2008, Wei and Luo, 2018, Bubeck et al., 2019]). A pictorial overview of our construction is given in the caption of Algorithm 1.
The of the logarithmic regularizer serves two main purposes. First, we show that it guarantees multiplicative stability of the strategies, a refined notion of stability that is also leveraged in the work of Daskalakis et al. [2021]. Nonetheless, we are the first leverage such properties in gen- eral domains, going well beyond the guarantees of (Optimistic) MWU on the simplex [Daskalakis al., 2021]. Further, the local norm induced by the logarithmic regularizer enables to cast regret bounds from the lifted space to the original space, while preserving the RVU property [Syrgka- nis al., 2015, Definition 3]. In turn, this implies near-optimal regret by establishing that the second-ored order path lengths up to time T are bounded by O'log (Theorem 3), building on a re- cent technique of Anagnostides al. [2022a] which crucially leverages the nonnegativity of swap regret.3 3
'To see why nonnegativity is crucial, note that the RVU bound implies optimal sum of players' re- grets [Syrgkanis et al., 2015]. Thus, nonnegativity would imply the same bound for each player's regret.
3

---

1.2 Further Related Work
The rich line work pursuing improved regret guarantees in games was pioneered by Daskalakis al. [2011]. Specifically, they developed strongly uncoupled learning dynamics that the play- ers' regrets grow as O(log T). an exponential improvement over the guarantee one could hope for in adversarial environments [Shalev-Shwartz, 2012, Cesa-Bianchi and Lugosi, 2006]. Their sult was significantly simplified by Rakhlin and Sridharan [2013]-again zero-sum games- who introduced a simple variant of mirror descent with a recency bias-a.k.a. optimistic mirror de- scent (OMD). It is worth noting that, beyond the benefits of optimism from an optimization stand- point [Polyak, 1987], recency bias has been experimentally documented in natural learning environ- ments in economics [Fudenberg and Peysakhovich, 2014].
Subsequently, Syrgkanis et al. [2015] crystallized the RVU property, an adversarial regret bound applicable for a broad class of optimistic no-regret learning algorithms. Using that property, they showed that the individual regret each player grows as O/T1/4) in general games, thereby con- verging to the set of coarse correlated equilibria with a rate of O(T))/2), A near-optimal bound of (ppolylog(T) in normal-form games was finally established by Daskalakis et al. [2021], while Fa- rina et al. [2022] generalized that result in a class of polyhedral games that includes extensive- form games. Some extensions of the previous results have also been established for the stronger notion of no-swap-regre learning dynamics in normal-form games [Chen and Peng, 2020, Anagnostides work builds
very recent technique of Anagnostides et al. [2022a], which established Ologg T) swap regret in normal-form games using as a regularizer a self-concordant barrier function. On the other hand, establishing even sublinear o(T) swap regret in extensive-form games is a notorious open question. Finally, an interesting new approach for obtaining near-optimal external regret in normal-form games recently proposed in concurrent work by Piliouras et al. [2022].*
al., 2022b,a]. In particular,
Games with continuous strategy spaces have received a lot of attention in the literature; e.g., (Roughgarden and Schoppmann, 2015, Even-Dat et al., 2009, Harks and Klimm, 2011, Hsich et al., 2021, Mertikopoulos and Zhou, 2019, Stein et al., 2011, Stoltz and Lugosi, 2007], and references therein. Such games encompass a wide variety of applications in economics and multiagent systems; give several examples in Section 2. Indeed, in many applications of interest faithful approxi- mation of the game requires an extremely large or even infinite action space; such settings could be abstracted Littlestone games in the sense of the recent work of Daskalakis and Golowich [2022].
2 No-Regret Learning and Convex Games
In this section review the general setting of convex games which encompasses number of important applications, as explained in Section 2.2. We then formally define the framework of uncoupled and online no-regret learning in games in Section 2.3.
Notation We let N (1, be the of natural numbers. For vector æ Rd we denote by æ[r] its r-th coordinate, for some index [d]] = 2..2..... d). We will typically represent the players using subscripts; superscripts are reserved for the time index, denoted by the variable t.
2.1 Convex Games
Let [m] = f1. n be set of players, with n E N. In a convex game, every player i E [n]] has nonempty convex and compact set of strategies X; C Rdd, For joint strategy profile x = (xI,...,,,,, E X X,, the reward of player given by a continuously differentiable utility function u, x,= X, + E subject to the following standard assumption.
'An earlier version of the paper [Piliouras et al., 2021] proposed preliminary and not uncoupled version of the Clairvoyant MWU algorithm whose iterates were guaranteed to be no-regret and require OO T) per-iteration complexity. The 2022 revision of that paper provides uncoupled version with time-indeeen ineeinddeendeett O(d) per-iteration complexity, albeit at the cost losing the no-regret guarantee on the entire sequence of iterates. See also footnote & in Table
'Sometimes these referred to as concave games [Rosen, 1965] continuous games [Hsieh et al., 2021].

---

Assumption (Convex games), The utility function Dn) of any player E [ra] satisfies the following properties:
1. (Concavity) (...;;.-)) is concave in De for x- (011..... Zi Di Li+l. Fnd E X jzi Xj;
2. (Bounded gradients) for any (f1,...,,a.) X==1 Zz. Vn, Uy (7) Lnn) m0 S B, for some parameter B > 0; and
3. (L-smoothness) there exists L 0 that for any two joint strategy profiles x' E EXj=1 Xz.
|| a. (x) V (x S L
Σ bzy
2'111.
2.2 Applications and Examples of Convex Games
Here we discuss several different classes of games which can all be analyzed under the common framework of convex games. For simplicity, we describe Cournot competion in the one-dimensional setting, but it can be readily generalized in more general domains. For more examples, we refer to [Even-Dar et al., 2009, Hsich al., 2021], and references therein.
Normal-Form Games In normal-form games (NFGs) every player
|n]] has finite and nonempty set of strategies Ar. Player i's strategy set contains all probability distributions sup- ported on Ag that is, X; = A(A:). The utility of player i can be expressed as the multilinear
function ua (2) == Ea (Ba=)(((()) (a)], for some arbitrary function Ui X"= A; +.
Extensive-Form Games Extensive-form games (EFGs) generalize NFGs by capturing both se- quential and simultaneous moves, stochasticity from the environment, as well as imperfect information. EFGs are abstracted on a directed tree. Once the game reaches a terminal (or leaf) node z E Z, each player i E [n] receives a utility (z), for some U; Z R. The strategy space of each player E [m]] can be compactly represented using the sequence-form polytope Q; [Romanovskii, 1962, Koller al., 1996]. If pe(2) is the probability of reach- ing terminal node 2 E Z over "chance moves", the utility of player i can be expressed as (
where q = (q), qn) E X" j=1 2j the joint strategy profile, and 9, g is the probability mass assigned to the last sequence J,,; encoun- tered by player j before reaching 2. The smoothness and the concavity of the utilities follow directly from multilinearity; for a more detailed account on EFGs we refer the interested reader to the excellent book of Shoham and Leyton-Brown Brown [2008].
u; (4) == E==2P((>)(((> (=)=))
Splittable Routing Games In these games [Roughgarden and Schoppmann, 2015] every player has to route flow Sa from source to a destination in an undirected graph G' = (V, F). Every edge e E is associated with a latency function & (fe) mapping the amount flow passing through the edge to some latency. The set of strategies of player corresponds to the possible ways of "splitting" the flow f; into paths from the source to the destination. Under suitable restrictions the latency functions, those games satisfy Assumption (see [Syrgkanis et al., 2015]).
Cournot Competition This game is played among n firms (players). Every firm i decides the quantity s; E S C R20 common good to produce, where S; is an interval. Further, a cost function c; : S, + E assigns a production cost to a given quantity, while p X + Rzo is the price of the good determined by the the joint choice of quantity s ($1,..., sn) across the firms. Then, the utility of firm i is defined as (s(s) == s,p(s) (s,).. In linear Cournot competition, p(s) := a-b ( = s;), for some a, b > 0, while the cost functions c; assumed to be smooth and convex [Even-Dat et al., 2009].
2.3 Online Linear Optimization and No-Regret Learning
In the online learning framework a learning agent has to select a strategy (1) E X' C Rd at every time E N. Then, the full information model, the learner receives as feedback from the environment linear utility function æ + (x,, measure of performance is the notion of regret, defined for time horizon T' E N as follows.
(z,,(())) (t)), for some vector (!)) E Rd The canonical
T Σ fo0" u (0)
I
Reg" max
(t), 2u 1)).
(I)
x EX
5

---

That is, the performance of the agent is compared to the optimal fixed strategy in hindsight. It is important note that regret can be negative. In the context of convex games, it is assumed that every player E [n] receives at time the "linearized" utility function æ; u,
+ (ais (t)) where
va (z)x)t)). By concavity (Assumption 1),
T (u,(a) x (1) ui(((()))
Σ x Va, (z(()())). Ex
max E.A:
max
As result, regret bound on the linearized regret-ing the sense of ( automatically translates to a regret bound in the convex game.
Strongly Uncoupled Learning Dynamics In this setting, all learning dynamies are uncoupled in the sense of Hart and Mas-Colell [2003]: every player is oblivious to the other players' utilities. In fact, players need not have any prior knowledge about the game, even about their own utilities; this captures the condition of strong uncoupledness of Daskalakis et al. [2011], along with a suitable bound on the memory of each player.
Near-Optimal No-Regret Learning in Convex Games
In this section describe algorithm, Log-Regularized Lifted Optimistic FTRL (henceforth LRL-OFTRL). The central result of this section, Theorem 4, asserts that when all players learn using LRL-OFTRI, their regret only grows logarithmically with respect the number of repetitions of the game. Detailed proofs for this section are available in Appendix A.
3.1 Setup
In the sequel, will define and analyze the regret cumulated by LRL-OFTRL from the perspective of generic player, omitting player subscripts.
We denote the set of strategies of the player by X' C IR.d. Without loss of generality, we will assume that S [0, +oo)""; otherwise, suffices to first shift the set. Furthermore, we assume without loss of generality that there is no index E [d] such that æfr] = 0 for all æ E X' not, dropping the identically-zer zero dimension would not alter regret. We define the lifting of ser as the following set:
Rd+1 2 X = {(>, y) E [0, 11. E XX)
(2)
Further, we define the & norm |/11/2 of X as the maximum 4-nnrmm of any vector æ E X, that is, || == max ||ж]|]: for example, || = 1.
The logarithmic regularizer for 12++1 is the function
R(A y) = 18-log log A
Σ log wirl.
v(A v) E Rdt1
Given any vector (),
X IRd+1 we denote with centered (>, y) induced by R(,, y), defined as
(l and || II the local norms
( (..)) =
@
a
d +
( = (a))2 ~ (=(rlur))
d
for any (a, 2) E Id++1 These are the norms induced by the Hessian matrix of at (A, y) and its inverse. is well-known fact that || (),, is the dual norm of (l(A.))) and vice versa.
3.2 Overview of Our Algorithm
Our algorithm (Algorithm 1) leverages optimistic follow the regularized leader (OFTRL), a simple variant of FTRL introduced by Syrgkanis et al. [2015], but with some important twists. First, the optimization is performed over the lifting & of the set X. More precisely, at every iteration the

---

observed utility (t)) R will be transformed to a(() Rd+1 according to Line 6; this ensures that ( is orthogonal to the vector (1, (1)) Then, this utility vector w is given as input to regret minimizer operating over X' employing OFTRL under the logarithmic regularizer (A y); this step described in Line We discuss how such an optimization problem can be solved efficiently in Section 3.5. Below we point out that Line 3 is indeed well-defined.
Proposition 1. For any γ 2 0 and at all times t N, the OFTRL optimization problem on Line of Algorithm I admits a unique optimal solution (X(1) (()) E 0
Finally, given the iterate (A(0) (() output by the OFTRL step at time i, our regret minimizer over X selects the next strategy (9) = y (()) /2(0) (Line 4); this is indeed valid strategy in X' by definition of X' in (2), as well as the fact that (() > as asserted in Proposition 1.
Algorithm 1: Log-Roeee Regulaaizd Lifted Optimistic FTRL (LRL-OFTRL)
(1)
i
OFTRL with log regularizer
(1 (
x
X
Lifting
Normalization
Data: Learning rate !)
Set (1)), (0) <- 0 E IR++1
2 for I,, do
3 Set (1(1) y((()
(00
000 (00+++0 +ū(t))) (2) )7))
arg max
log +
Σ log yrr
[p OFTRL]
(A.)))
(())
4 Play strategy (() = Alí EX
[ Normalization]
5 Observe (+) Rd
(- (2))) (1))
6 Set (4)
[p Lifting]
(1)
7 Set (t+11) t + (1)
3.3 Regret Analysis
In this section, we study the regret of LRL-OFTRL under the idealized assumption that the optimiza- tion problem on Line 3 (OFTRL step) is solved exactly at each time t. In Section 3.5 we will relax that assumption, and study regret LRL-OFTRL when the solution to Line approximated using variants of Newton's method.
To study the regret Reg" of LRL-OFTRL, defined in (1), is useful to introduce the quantity Reg" which measures the regret incurred by the internal OFTRL algorithm (Line 3) up time T E N in the lifted space &, ie..
T
1-
(14))
Reg =
max (A* DEE
(()
(1)
As the following theorem clarifies, there is strong connection between Reg and Reg".
Theorem 2. For any time T E NN it holds that Reg T T' Reg 2 0 and Reg" < RReg for any T N.
max(0, Reg""). In particular, it follows that
T
The nonnegativity of Reg" will be a crucial property in establishing Theorem Further, Theorem implies that guarantee over the lifted space can be automatically translated to a regret bound over the original space X. Now let
|| 1le (1(00)
and
I || (1.10,,200,
7

---

be the local norms centered at point (A(9, (+) produced by OFTRL at time t (Line 3), In the next proposition we establish a refined RVU (Regret bounded by Variation Utilities) bound in terms of this primal-dual norm pair.
Proposition 2 (RVU bound of OFTRL in local norms), Let Reg be the regret cumulated up to time T by the internal OFTRL algorithm. If
[ (
|oo S at all times t E [T], then for any time
horizon T E N and learning rate
S 50'
Reg' 54+ (d+ 1)lg' T
T
+ 5n
i (1)
(1--1)
()(+1))
(10 (()))
"
7,t 27n
(We recall that (0)) = 0.) Proposition differs from prior analogous results in that the regularizer not barrier over the feasible set. Next, we show that the iterates produced by OFTRL satisfy refined notion of stability, which we refer to as multiplicative stability.
Proposition (Multiplicative Stability). For any time t E and learning rate n S 50 if [|u(0) |l | < 1.
(x(et) y
((00)
y
227/.
Intuitively, this property ensures that coordinates of successive iterates will have a small multiplica- tive deviation. We leverage this refined notion of stability to establish the following crucial lemma.
Lemma 1. For any time E N and learning rate 1 S 50 if 110111 1
( (4++))
(119)
)
(2x(++)) -z S 4 ||111|1
(1()
Combining this lemma with Proposition 2 allows us to obtain an RVU bound for the original space X. with no dependencies on local norms.
Corollary (RVU bound in the original (unlifted) space). Fix any time T E N, and suppose that
1l S B for any t [T]. If 260
Reg T
<6 + logg +167 1
1 (++1) 20 512n
T-1
(++1)
x (4)
x
3.4
Main Result
So far, in Section 3.3, we have performed the analysis from the perspective of a single player, obtaining regret bounds that apply under an arbitrary sequence utilities. Next, we assume that all players follow our dynamics such that the variation in one's 's utilities is now related to the variation in the joint strategies based on the smoothness condition of the utility function, connecting the last two terms of the RVU bound. Further leveraging the nonnegativity of the regrets in the lifted space, we establish that the second-orde path lengths of the dynamics up to time T are bounded by Olog T):
Theorem 3. Suppose that Assumption 1 holds for some parameters B, L > O. If all players follow LRL LRL-OFTRL with learning rate 1) S min 256li|aa11 1288L1A²11 J where || = max || then
((+1) | ay 101 B14 1024n 1) log
(4)
Here we made the mild assumption that each player knows the values of n, L, B and || in order to appropriately tune the learning rate; otherwise, similar guarantees are possible via a standard ap- plication of the doubling trick. It is interesting to point out that (4) holds even without the concavity condition (recall Assumption 1). We next leverage Theorem to establish Theorem the detailed version of which is given below.
8

---

Theorem 4 (Detailed Version of Theorem 1). Suppose that Assumption 1 holds for some parameters
B, > If all players LRL-OFTRL with learning rate = min { | 128mL]IA11 J then for any T E N the regret Reg. of each player E [[]] can be bounded as Regi & || + 256(d + 1) max (2, log Furthermore, the algorithm can be adaptive so that if player is instead facing adversarial utilities, then Reg; = =.VT).
(5)
For clarity, below cast (5) of Theorem 4 in normal-form games with utilities normalized in the range [-1,1], in which case we can take B = 1, L and || 1=
Corollary 2 (Normal-form Games). Suppose that all players in a normal-form game with 2 2 follow LRL-OFTRL with learning rate 1l 128n Then, for any T E IN and player i E [m].
Reg T < 12 + 256mdd + log
3.5 Implementation and Iteration Complexity
In this section, we discuss the implementation and iteration complexity of LRL-OFTRL. The main difficulty in the implementation is the computation of the solution to the strictly concave nonsmooth constrained optimization problem in Line 3. We start by studying how the guarantees laid out in Theorem 4 are affected when the exact solution to the OFTRL problem (Line 4) in Algorithm is replaced with approximation. Specifically, suppose that at all times t the solution to the OFTRL step (Line 3) in Algorithm 1 is only approximately solved within tolerance (1) in the sense that
(AC)) (1(1)
56(0
(6)
)
where (1) E TRSt and
(0)
/ ū
( + +ū a(-1))
( y ))+
(
= arg max (A.))E&
+ log À +
log y [r]
Then, it can be proven directly from the definition of regret that the guarantees given in Corollary deteriorate by additive factor proportional to the sum of the tolerances ΣT= e(t) As immedi- ate corollary, when c(*) := 1/T, the conclusion of Theorem 4 applies even when the solution to the optimization problem on Line is only approximated up to tolerance. Therefore, to complete our construction, it suffices to show that it is indeed possible efficiently compute approximate solutions to the OFTRL step (see Appendix A.5). In the remainder of this section, we show that this is indeed the case assuming access to two different type of oracles. It should be stressed that optimizing over a general convex set introduces several challenges not present under simplex do- mains, inevitably leading to an increased per-iteration complexity compared to algorithms designed specifically for normal-fome games suche-such&a as OMWU.
Proximal Oracle First, we will assume access to a proximal oracle in local norm for the set X, that is, access to function that is able compute the solution the (positive-definite) quadratic optimization problem
1 - }} (7)
1 (g) arg min á T
9
7 -1 w 11:
arg min EE
9
for arbitrary centers E IRd+1 and gradients ğ Rd+1, For certain sets X C Rd, exact proximal oracles with polynomial complexity in the dimension d can be given. In particular, we show that this is the case when X' is the strategy set of normal-fone form and extensive-form games by extending the approach of Gilpin [2009, pp. 128-133], as formalized below.
Proposition Let X C Rd be the polytope of sequence- form strategies for a player in perfect- recall extensive-form game. Then, the local proximal oracle lā)()) defined in (7) can be imple- mented exactly in time polynomial in the dimension d for any i Rdd) and ğ E pd+1

---

We provide the details and a more precise statement in Appendix B. In this context, the following guarantee employs the proximal Newton algorithm of Tran-Dinh al. [2015]; see Algorithm 2.
Theorem (Proximal Newton). Given any > O, it is possible to compute (A19, y))) E &' &niss T such that (6) holds for c(t) using ( log(//)) operations and (log log(1/c)) calls to the proximal oracle defined in Equation (7).
Linear Maximization Oracle tion oracle (LMO) for the set X::
Moreover, we consider having access to weaker linear maximiza-
Cx(u) = arg max( u). xEX
(8)
Such an oracle is more realistic in many settings [Jaggi, 2013], and is particularly natural in the context of games, where it can be thought of as a best response oracle. We point out that an LMO for X' automatically implies an LMO for X. The following guarantee follows readily by applying the Frank- Wolfe (projected) Newton method [Liu et al., 2020, Algotihms and 2].
Theorem 6 (Frank- Wolfe Newton). Given any c > 0, it is possible to compute (x())y(() E X n R&+1 such that (6) holds for e (!)) = e using (1poly(1/e) operations and (ppoy( (1/e)) calls to the LMO oracle defined in Equation (8).
Experiments Finally, while our main contribution is of theoretical nature, we also support our theory by conducting experiments on some standard extensive-form games (Appendix C). The ex- periments verify that under LRL-OFTRL the regret of each player grows as O(log T).
4 Conclusions
In this paper we developed LRL-OFTRL, a novel no-regret learning algorithm. We showed that when all players in general convex game employ LRL-OFTRL, the regret of each player grows only as Ollog 7), thereby significantly extending and strengthening the scope of all prior work. Further, be efficiently implemented using, for example,
uncoupled no-regret learning dynamics proximal oracle for the underlying feasible set.
One caveat of our framework applied to the special dence on the dimension is linear (Corollary 2) as opposed to logarithmic [Daskalakis et al., 2021]. Whether the entropic wehularizer-which induces OMWU-can be incorporated into our framework an important open question. Another interesting avenue for future research would be to explore having access different types of oracles. For example, is it possible to extend Theorem using separation oracle for the underlying set of strategies? If so, the ellipsoid algorithm [Bubeck, 2015] would be the obvious candidate route implementing LRL-OFTRI.
of normal-form games is that the depen-
Acknowledgments
We are grateful to anonymous NeurlPS reviewers for many helpful comments. This material is based on work supported by the National Science Foundation under grants I1S-1718457, IIS-1901403, 194-1943607, and CCF-1733556, and the ARO under award W911NF2010082 Christian Kroer is supported by the Office of Naval Research Young Investigator Program under grant N00014-22-1- 2530.
References
Yoav Freund and Robert Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79-103, 1999.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68: 187-1100,, 2000.
Dean Foster and Rakesh Vohra. Calibrated learning and correlated equilibrium. Games and Eco- nomic Behavior, 21:40-55, 1997.
10

---

Libratus beats Tim Roughgarden. Intrinsic robustmess of the price of anarcby. J. ACM, 62(5):32:1 2015.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold' em poker is solved. Science, 347(6218), 18), January 2015.
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, May 2017.
Noam Brown and Tuomas Sandholm. Superhuman Al for heads-up no-limit poker: top professionals. Science, page eaaol733, Dec. 2017.
Noam Brown and Tuomas Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456): 885-890, 2019.
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algorithms for zero-sum games. Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable se- quences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence regu- larized learning in games. In Advances in Neural Information Processing Systems, pages 2989-
2015.
Dylan J. Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Éva Tardos. Learning in games: Robustness of fast convergence. In Advances in Neural Information Processing Systems 29: Anmual Conference on Neural Information Processing Systems 2016, pages 4727-4735, 2016.
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.
Constantinos Daskalakis and Noah Golowich. Fast rates for nonparametric online learning: from realizability to learning in games. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pages 846-859. ACM, 2022.
Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Beyond time-average convergence: Near- optimal uncoupled online learning via clairvoyant multiplicative weights update. arXiv preprint, 2022. URL https: //arxiv////xxv.../ arxia. org/ abs/2111...../////////////.///11 14737v4.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, pages
2021.
Gabriele Farina, Chung-War Wei Lee, Haipeng Luo, and Christian Kroer.
Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games. In International Conference on Machine Learning, ICML. 2022, volume 162 of Proceedings of Machine Learning Research, pages 6337-6357. PMLR, 2022.
Ehsan Asadi Kangarshahi, Ya- Ya-Ping Hsieh, 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 on Machine Learning, ICML 2018, volume 80 of Proceedings of Machine Learning Research, pages 2493-2501 PMLR, 2018.
Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference on Learning Theory, pages 6-1, 2012.
Chung-War Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: high-probabilityy data-dependent regret bounds for adversarial bandits and mdps. In Advances in Neurul Informa- fion Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
11

---

Haipeng Luo, Mengxiao Zhang, and Peng Zhao. Adaptive bandit convex optimization with het- erogeneous curvature. In Po-Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 1576-1612. PMLR, 2022.
Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algo- rithm for bandit linear optimization. In Proceedings of the 21 Annual Conference on Learning Theory (COLT), 2008.
Chen-Ye Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Conference Learning Theory, COL7' 2018, volume 75 of Proceedings of Machine Learning Research, pages 1263-1291, PMLR, 2018.
Sébastien Bubeck, Yuanzhi Li, Haipeng Luo, and Chen- Yu Wei. Improved path-length regret bounds for bandits. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, volume 99 of Proceedings of Machine Learning Research, pages 508-528 PMLR, 2019.
loannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-War Wei Lee, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with Ollog 7') swap regret in multiplayer games, 2022a.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning. 4(2), 2012. ISSN 1935-8237.
Nicolo Desa-Bianchi and Gabor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
Boris Polyak. Introduction to optimization. optimization software. Inc., Publications Division, New York, 1:32, 1987.
Drew Fudenberg and Alexander Peysakhovich. Recency, records and recaps: Learning and non- equilibrium behavior in simple decision problem. In Proceedings of the Fifteenth ACM Con- ference on Economics and Computation, EC '1,, page 971-986. Association for Computing Ma- chinery, 2014.
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 '22: 54th Annual ACM SIGACT Symposium on The- ory of Computing, 2022, pages 736-749. ACM, 2022b.
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, 2021. URL wwtp:///www/a.....////./. 14737v1.
Tim Roughgarden and Florian Schoppmann. Local smoothness and the price of anarchy in splittable congestion games. Econ. Theory, 156:317-342, 2015.
Eyal Even-Dar, Yishay Mansour, and Uri Nadav. On the convergence of regret minimization dy- namics in concave games. In Michael Mitzenmacher, editor, Proceedings of the 41 Annual ACM Symposium on Theory of Computing, STOC 2009, pages 523-532. ACM, 2009.
Tobias Harks and Max Klimm. Demand allocation games: Integrating discrete and continuous strategy spaces. In Ning Chen, Edith Elkind, and Elias Koutsoupias, editors, Internet and Network Economics 7th International Workshop, WINE 2011, volume 7090 of Lecture Notes in Computer Science, pages 195-205. Springer, 2011.
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning con- tinuous games: Optimal regret bounds and convergence to nash equilibrium. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, volume 134 Pro- ceedings of Machine Learning Research, pages 2388-2422 PMLR, 2021.
Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Math. Program., (73(1-2):465-507 2019,
12

---

Noah D. Stein, Pablo A. Parrilo, and Asuman E. Ozdaglar. Correlated equilibria in continuous games: Characterization and computation. Games Econ. Behav., 71(2):336-455, 2011.
Gilles Stoltz and Gábor Lugosi. Learning correlated equilibria in games with compact sets of strate- gies. Games Econ. Behav., 59(1):187-208 2007.
B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games, Econo- metrica, 33(3):520-534, 1965.
I. Romanovskii. Reduction of game with complete memory matrix game, Soviet Mathematics, 3, 1962.
Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2), 1996.
Yoav Shoham and Kevin Leyton- prrton-Broow.... Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.
Sergiu Hart and Andreu Mas-Colell, Uncoupled dynamics do not lead to Nash equilibrium. Ameri- can Economic Review, 93: 1830-1836, 2003.
Andrew Gilpin. Algorithms for abstracting and solving imperfect information games. Doctoral dissertation, Computer Science Department, Carnegie Mellon University, Pittsburgh, 2009.
Quoe Tran- Finh, Anastasios Kyrillidis, and Volkan Cevher. Composite celf-concordant minimiza- tion. J. Mach. Learn. Res., 16:371-416, 2015.
Martin Jaggi. Revisiting frank-wolfe: of the 30th International Conference on Machine Learning, ICML 2013, volume 28 of JMLR Workshop and Conference Proceedings, pages 427-435. JMLR.org. 2013.
Projection-free sparse convex optimization. In Proceedings
Deyi Liu, Volkan Cevher, and Quoc Tran-Dinh. A newton frank-wolfe method constrained self-concordant minimization. CoRR, abs/2002.07003, 2020.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn., 8(3-4):231-357, 2015.
Samid Hoda, Andrew Gilpin, Javier Peña, and Tuomas Sandholm. Smoothing techniques for com- puting Nash equilibria of sequential games. Mathematics of Operations Research, 35(2), 2010.
H. W. Kuhn. Extensive games. Proc. of the National Academy of Sciences, 36:570-576, 1950.
Sheldon M Ross. Goofspiel- the game of pure strategy. Journal of Applied Probability, 8(3): 621-625, 1971.
Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm. Correlation in extensive-form games: Saddle-point formulation and benchmarks. Conference on Neural Information Pro- cessing Systems (NeurIPS), 2019.
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] Sections and 4
(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? [Yss]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
13

---

(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices A and B
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] See Ap- pendix C
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix C
(c) Did you report enror bars (e.g., with respect to 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, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix C
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any 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 'r using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing 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]
14


Reviews:
[{"review_id": "q9w4JylwWk", "reviewer": "Reviewer_v5uW", "summary": "This paper proposes a new novel algorithm named LRL-OFTRL which can achieve near-optimal for general convex games. In particular, when all players employ LRL-OFTRL, the regret of each player grows in logarithm speed. Their results significantly extend the result derived by Daskalakis et al. [2021] and can be applied to many subareas such as normal-form games, extensive-form games, splittable routing games, and Cournot competition. ", "questions": "Since I am not familiar with the area of convex games, I have no technical criticism for this paper.\n\n", "limitations": "The authors have addressed their work's limitations and potential negative social impact.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nOriginality: This paper proposes a new novel algorithm named LRL-OFTRL which can achieve near-optimal for general convex games.  \n\nQuality: The theory is technically solid and is supported by proof. This is complete work. \n\nClarity: this paper is well written and organized. The main theorems are supported by proof, but I\n\nSignificance: This paper proposes a new algorithm with a novel technique that significantly extends and improves the prior works. I think it is novel. \n\nThere are no experiments in this paper. It would make the result more significant if the authors could add some experiments (simulated and/or real data), which (1). shows that the proposed algorithm is implementable, and (2). if possible, show the advantage compared with Kernelized OMWU [Farina et al., 2022].", "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": "dVzjBJux61j", "reviewer": "Reviewer_SdzV", "summary": "The paper considers a convex game (i.e., utility functions that are smooth, and convex given the other actions) between n players, where each player gets the gradient of its utility function at the end of every turn (i.e., full information). An optimistic follow-the-regularized-leader variation is proposed such that if all players use this algorithm with the same tuning, they all achieve a regret of O(logT). If this is not the case, each player can detect that and switch to an algorithm that achieves O(sqrt(T)) against an adversary. The algorithm requires to solve an optimization problem, and the paper proposes two oracles that can provide good approximate solutions to this problem, and analyzes the complexity and the implication for the regret bound. ", "questions": "1) What do you mean by \"efficiently implantable\"? especially in light of algorithms like OMWU that seem far more efficient? \n\n2) Is there any concrete motivation that I missed, other than computing the coarse correlated equilibrium? would the regret make sense as a benchmark in some game scenarios? \n\n3) Are there examples for applications where the \"full game information\" assumption is reasonable? ", "limitations": "This is a theory pape so there is no societal impact. The technical limitations could be better discussed, as I explain above. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well-written and the results are novel and explained well. General convex games are indeed a very broad and interesting class of games. The math is sound and the technical derivations are neat. I'm a bit hesitant regarding the significance or relevance of the results. Some of these issues can be mitigated or at least be presented more accurately, while others are inherent to the type of question the paper is interested in. I do believe that assuming that this question is interesting, the results of the paper are impressive. \n\nThe first issue is with the motivation: why would anybody need an algorithm with the (impressive) guarantees proven here. Using the same definition of regret for this game scenario is not obvious to me. It compares the sum of rewards of the players with something completely artificial - the sum of rewards the players would have gotten by playing a fixed action, while all players still follow their sequence of play. However, this sequence of play was generated partly in response to the player's actions. The paper does mention one possible motivation, which is to compute the coarse correlated equilibrium of the game. I think that's a good motivation overall, but if the motivation is computational, it sets some different priorities. Most importantly, I'm not sure if the computational complexity offered by this algorithm makes it a good choice (which I discuss below). \n\nThe second issue is with the feedback. Being able to evaluate the gradient in a data-driven scenario is one thing, but being able to do so (with no error) in a game is a different thing. The gradient of player i's utility with respect to its action depends on the actions of other players and this function depends on the structure of the game. I find it a very strong assumption. Even if the algorithm is used to compute a coarse correlated equilibrium (CCE), it's only interesting when the utility functions are unknown - otherwise computing the CCE can be done directly. Providing examples where one easily knows the gradient but not the utility function would help to justify this model, and by that, the motivation of the paper. The examples provided in Section 2.2 are for convex games, and indeed the convexity assumptions are very mild: but the feedback assumption isn't, and I'm not sure how and when it would be satisfied in the given examples. In terms of presentation, the paper claims that the proposed algorithm is an \"uncoupled learning algorithm\", where uncoupled is defined as \"every player is oblivious to the other players’ utilities\". First, this definition is soft and vague. Then, it is claimed that the algorithm is even \"strongly uncoupled\" since players need not have any prior knowledge about the game whatsoever. I don't see how this is the case here if the gradient of the utility function of each player is (indirectly) highly related to the other players' utilities. Is this fair to say the algorithm is uncoupled where all that couples a player to others is given to this player for free, as an arbitrary modeling assumption? Additionally, it seems like the players need to know the Lipschitz parameter L, and the number of players, so I'm not sure if this statement is accurate. \n\nThe third issue, which can be easily fixed, is that the paper makes some over statements or just vague technical ones:\n\n1) The statement that the dynamics are \"efficiently implementable\" is puzzling to me. The number of oracle calls per iteration is T-dependent. Then, each oracle call needs to give an approximate solution with an error of O(1/T), which will require again T-dependent complexity. The proximal oracle requires O(log(log(T)) calls which is nice, but each call will be complicated to implement (providing more detail here is recommended). There, an alternative linear optimization oracle is proposed, but this one needs poly(T) calls per iteration. Now, T needs to be very large to make the regret improvement from O(log^4(T)) significant. In light of this, in what sense is this efficient? numerical simulations could have helped to demonstrate the that algorithm runs in a reasonable time. I find this issue very important if the motivation of the paper is to compute coarse correlated equilibrium. If the overall computation is infeasible, then it's unclear why the  O(log(T)) regret is worst the struggle. I can see why improving the state-of-the-art regret bound for games might require heavy computational machinery like these oracles, but it looks like the paper is claiming that this computational disadvantage is in fact an advantage. \n\nThe line about the \"best-response oracle\" is a bit misleading. Usually, best-response is used in finite discrete games where the \"oracle\" is just going over the actions. In continuous convex games, best-response amounts to solving a convex problem, so it's not any easier or more common. \n\nTogether with the \"uncoupling issue\" above,  I think that claiming that the algorithm is both uncoupled and efficiently implementable (which is the main presented research question here) is an overstatement (also line 69 and other places). \n\n2) The assumption that the product of the norms, in line 193, is at most 1, is not exactly without the loss of generality. Indeed, one can always rescale the rewards, but as discussed in lines 275-280, this adds a factor to the regret. This factor is recognized in the comparison in Table 1, but not in other places. I don't see why this assumption is needed, instead of just including this factor. This assumption holds for the simplex as the action space, but not, for example, in a multi-dimensional Cournot competition. It's also easy to miss this assumption which is not given near the assumption on the game or the statement of the results, which makes the regret bounds look better than they are in general action spaces. \n\n3) The statement that the algorithm can be adaptive so that if player i is instead facing adversarial utilities the regret is O(sqrt(T)) is a bit vague. The meaning of this adaptivity only becomes clear when reading the proof of the Theorem. But then, it looks like this adaptivity requires each player to know the number of players n, and the Lipschitz parameter L. The step size also requires the player to know these parameters, but at least then one imagine what can be done if they don't know them (or what's the resulting factor in the regret). Since, against an adversary, there are no players at all, this means that the player excepts to play against n-1 other players, and if it finds himself playing against any other number (or players with different tuning), the regret can jump to O(sqrt(T)). I still think that this adaptivity is nice, but I think that the statement in the theorem needs to be more rigorous and include all detail and implicit assumptions. \n\n4) The comparison to Piliouras et al. [2021] is perhaps a bit unfair. Their paper does claim their algorithm is uncoupled, which line 117 here refutes. This seems a very subtle issue given that I'm not sure if the proposed algorithm is uncoupled. I think that discussing how the proposed algorithm is at least \"more uncoupled\" than Piliouras et al. [2021] is necessary. Then, Table 1 is very confusing with regard to Piliouras et al. [2021]. Where is the T dependence of the regret bound? Also, isn't Piliouras et al. [2021] for finite discrete games, whereas this paper is for continuous games? \n\nI would be happy if I missed some critical details that can mitigate some of these issues. Disconnected from the confusing motivation, the proposed algorithm is creative and neat. Providing some intuition so why and how this lifting and regularizer do the trick can be interesting. \n\nMinor Comments:\n\nThe title of Section 2.3 seems inappropriate. This should be the problem formulation. \n\nline 539 - saying that G is defined in (11) can help.\n\nmissing period before line 599.\n\nI wasn't able to follow the proof of Proposition 5. What vector is used as the fixed (lambda,y) -star vector here? how come the additional term in the regret bound has the 2 factor, without the 1/(27*eta)? \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": "cuM0PwcGLHv", "reviewer": "Reviewer_ZFFJ", "summary": "This paper studies online learning for general convex games, where the decision set of each player is general convex. The authors propose an algorithm and prove an $O(\\log T)$ regret each player, where $T$ is the number of rounds. It improves the best $T^{1/4}$ regret achieved by OMD. At the core of their algorithm is a lifting strategy with a regularized FTRL framework that updates both the utility and the regularization parameter simultaneously. ", "questions": "- The authors mention that their algorithm will achieve an $\\sqrt{T}$ regret under the adversarial setting. Can the authors explain what the adversarial setting is since I do not find the definition in the main text?\n\n- From the algorithm description and the proof, it seems that both the theoretical result and the algorithm can be regarded as those counterparts for a 'single-player' setting, since the regret reg_i cares nothing but the relative optimality of player i, and the algorithm also deals nothing with other players. Can the authors explain more about that?\n\n", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The results are important in theory since it provides the first $\\log(T)$ type regret for general convex games.\n- The discussion is comprehensive. \n- The proof is technically sound.\n\nWeaknesses:\n-  There can be more explanation about the problem setting. See questions. ", "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": "bZXTx29OrtR", "reviewer": "Reviewer_S1Jh", "summary": "This paper studies the uncoupled learning for general convex games, which is absolutely of interest to the audience in the community of online learning and game theory. The paper presents novel algorithms equipped with strong regret guarantee in the sense that only poly log T regret is incurred for each player; and also the algorithm can be efficiently implemented given a certain oracle. The crucial novelty in the technical stuff lies in the usage of the lifting to ensure nonengativeity of the regret and also the log barrier function to enhance the stability.", "questions": "See above.", "limitations": "See above.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem studied in this paper is very interesting and challenging. This paper studies the uncoupled learning for general convex games, which is absolutely of interest to the audience in the community of online learning and game theory. The paper presents novel algorithms equipped with strong regret guarantee in the sense that only poly log T regret is incurred for each player; and also the algorithm can be efficiently implemented given a certain oracle. The crucial novelty in the technical stuff lies in the usage of the lifting to ensure nonengativeity of the regret and also the log barrier function to enhance the stability. To the best of my knowledge, there is no similar result of uncoupled learning for convex games even though there is a large body of researches in this thread. The paper writing is of high quality and make the reader feel enjoyable.\n\nThe usage of lifting to ensure the nonnegativity is very interesting. Although the lifting idea was used in earlier studies [1,2], using it in uncoupled learning dynamics is very new to the best of my knowledge.\n\nIt is a pity that authors fail to cite the two prior works that also use the lifting ideas (in other bandit problems though).\n[1] Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs. NeurIPS 2020.\n\n[2] Adaptive Bandit Convex Optimization with Heterogeneous Curvature. COLT 2022.\n\nThe authors are suggested to explain more on the lifting operation as stated in Eq. (2). Note that the augmented dimension $\\lambda$ also affects the remaining dimensions due to the constraint $y \\in \\lambda X$, which exhibits salient difference to earlier papers [1,2] that only pave a constant 1 in the augmented dimension. \n\n\nUsing the self-concordant barrier function for full-information game setting is interesting. This will introduce strengthened stability as argued and proven in the paper, while the log barrier function will also make the dimensional dependency worse. \n\n\nminor comments: Line 191. players need not have any prior --> need not to have", "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": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept