No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation
Authors: Yu-Guan Hsieh
Kimon Antonakopoulos
Volkan Cevher
Panayotis Mertikopoulos
Venue: NeurIPS 2022 Accept (2022)
Keywords: Learning in game
Regret
Noise
Optimism
Adaptivity
Nash equilibrium

Abstract: We examine the problem of regret minimization when the learner is involved in a continuous game with other optimizing agents: in this case, if all players follow a no-regret algorithm, it is possible to achieve significantly lower regret relative to fully adversarial environments. We study this problem in the context of variationally stable games (a class of continuous games which includes all convex-concave and monotone games), and when the players only have access to noisy estimates of their individual payoff gradients. If the noise is additive, the game-theoretic and purely adversarial settings enjoy similar regret guarantees; however, if the noise is \emph{multiplicative}, we show that the learners can, in fact, achieve \emph{constant} regret. We achieve this faster rate via an optimistic gradient scheme with \emph{learning rate separation} \textendash\ that is, the method's extrapolation and update steps are tuned to different schedules, depending on the noise profile. Subsequently, to eliminate the need for delicate hyperparameter tuning, we propose a fully adaptive method that smoothly interpolates between worst- and best-case regret guarantees.

No-regret learning in games with noisy feedback:
Faster rates and adaptivity via learning rate separation
Yu-Guan Hsieh"
Kimon Antonakopoulos! kimon. antonakopoullss@ppf... ch
yu yu-guan.cm www.inniiiiiroooeeeeeeeeo fr
Volkan Cevher volkan. celkan.cevherrepfl.ch
Panayotis Mertikopoulos** panayotis mettikopouloseenngg
Abstract
We examine the problem regret minimization when the learner is involved in continuous game with other optimizing agents: in this case, if all players follow a no-regret algorithm, is possible to achieve significantly lower regret relative fully adversarial environments. We study this problem in the context of variationally stable games (a class continuous games which includes all convex- concave and monotone games), and when the players only have access noisy estimates their individual payoff gradients. the noise is additive, the game- theoretic and purely adversarial settings enjoy similar regret guarantees; however, if the noise is multiplicative, we show that the learners can, in fact, achieve constant regret. We achieve this faster via an optimistic gradient scheme with learning rate separation that is, the method's extrapolation and update steps are tuned to different schedules, depending on the noise profile. Subsequently, to eliminate the need for delicate hyperparameter tuning, we propose fully adaptive method that attains nearly the same guarantees as non-adapted counterpart, while operating without knowledge of either the game or of the noise profile.
Introduction
Owing to its simplicity and versatility, the notion of regret has been the mainstay of online learning ever since the field's first steps [6, 17]. Stated abstractly, it concerns processes of the following form:
1. At each stage 1,2...., ., the learner selects action 2; from some d-dimensional real space.
2. The environment determines convex loss function 4, and the learner incurs loss of (xx).
3. Based on this loss (and any other piece of information revealed), the learner updates their action Ft It+1 and the process repeats.
In this general setting, the agent's regret Reg, is defined as the difference between the cumulative loss incurred by the sequence vt, 1, 2...... ., T, versus that of the best fixed action over the horizon of play T. Accordingly, the learner's objective is to minimize the growth rate of Regr. guaranteeing in this way that the chosen sequence of actions becomes asymptotically efficient over time.
Without further assumptions on the learner's environment or the type loss functions encountered. is not possible to go beyond the well-known minimax regret bound of R(VT) [18, 37], which is achieved by the online gradient descent (OGD) policy of Zinkevich [39]. However, this lower bound concerns environments that are "adversarial" and loss functions that may vary arbitrarily from one stage to the next: if the environment is "smoother" and not actively seeking to sabotage the leamer's efforts one could plausibly expect faster regret minimization rates.
"Uniy. Grenoble Alpes tEPFI
CCNSS, Inria, LIG & Criteo AT Lab
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Player might wett
6000
10"
no"
10"
Disanoa
10"
10
-400
10
-900
200C
6000
8000
2000
6000
8000
10000
llerations
llerations
OG: 9g 0.03
OG 0.10/++1
OG+ y 0.1. 0.01
Adaptive OpIDA+
Figure 1: The behavior of different algorithms on the game mingER maXtER 0e when the feedback is corrupted by noise. Left: trajectories of play. Center: regret of Player 1. Right: distance to equilibrium. Adaptive OptDA+ run with y = 1/4. See Example for the details of the model and Appendix for additional figures.
This question is particularly relevant and has received significant attention - in the backdrop of multi-agent learning in games. Here, the Iearners' environment no longer arbitrary: instead, each player interacts with other regret minimizing players, and every player's 's individual loss function determined by the actions chosen by all players via a fixed underlying mechanism that of a con-cooperative game. Because of this mechanism and the fact that players are changing their actions incrementally from one round the next the learners are facing much more "predictable" sequence of events. As result, there has been a number of research threads in the literature showing that it is possible to attain near-constant regrel (i.e., at most polylogarithmic) in different classes of games, from the work of [10, 23] on finite two-player zero-sum games, to more recent works on general-sun sum finite games [1, 2, 12], extensive form games [16]. and even continuous games [20].
Our contributions in the context of related work. The enabling technology for this range of near-constant regret guarantees is the optimistic gradient (OG) algorithmic template, itself a variant of the extra-gradien grard-ggrdient (EG) algorithm of Korpelevich [25]. The salient feature of this method - first game-theoretie setting and subsequently popularized by Rakhlin and Sridharan [35] in the context of online learning - is that players use past gradient information to take a more informed "look-ahead" gradient step that stabilizes the method and leads lower regret. This, however, comes with an important caveat: all of the above works crucially rely on the players' having access exact payoff gradients, an assumption which often violated in practice. When the players' feedback is corrupted by noise (or other uncertainty factors), the very same algorithms discussed above may incur superlinear regret (cf. Figure I). We are thus led to the following natural question:
examined by Popov [34]
Is it possible to achieve constant regret in the presence of noise and uncertainty?
Our paper seeks to address this question in class of continuous games that satisfy a variational stability condition in the spirit of [20, 27]. This class contains all bilinear min-max games (the unconstrained analogue of two-player, zero-sum finite games), cocoercive and monotone games, and is one the settings of choice when considering applications to generative models and robust reinforcement learning [7, 19, 22, 26]. As for the noise contaminating the players' gradient feedback, we consider two standard models that build on a classical distinction by Polyak [33]: (a) additive; and (b) multiplicative gradient noise. The first model is more common when dealing with problem- agnostic first-order oracles [30]: the latter arises naturally in the study of randomized coordinate descent [30], asynchronous player updating schemes [4], signal processing and control [36], etc.
In this general context, our contributions can be summarized follows:
1. We introduce a learning rate separation mechanism that effectively disjoins the extrapolation and update steps of the OG algorithm. The resulting method, which we call OG+, guarantees O (vTT) regret the presence of additive gradient noise; however, if the noise is multiplicative and the method is tuned appropriately, it achieves constant ((1) regret.
2. On the downside, OG+ may fail to achieve sublinear regret in an adversarial environment. To counter this, we propose a "primal-dual" variant of OG+, which we call OptDA+, and which retains the above properties OG+, while achieving O(VT) regret in the adversarial case.
3. Subsequently, obviate the need for delicate hyperparameter tuning, we propose fully adaptive method that enjoys nearly the same regret guarantees as mentioned above, without any prior knowledge of the game or of the uncertainties involved. Interestingly, our method features

---

Adversarial
All players run the same algorithm
Bounded feedback
Additive noise
Multiplicative noise
Regret
Regret
Convergence
Regret
Convergence
OG
x
X
X
OG+
Vogg t Vi Vt
constant
OptDA+
Vt t3/4
constant
AdaOpiDA+ (q = 1/4)
constant
Table 1: Summary of the results obtained in the paper. The cross X indicates negative result (divergence of trajectory potentially unbounded regret with decreasing stepsize) while dash "_" means that the behavior of the algorithm unknown. Our methods improve upon vanilla OG by separating the two step-size schedules.
trade-off between achieving small regret when facing adversarial opponents and achieving small regret when facing opponents that adopt the same prescribed strategy, which prevents us from obtaining the optimal
O(v regret bound in the former situation.
4. Finally, complement our analysis with series of equilibrium convergence results for the range of algorithms presented above under both additive and multiplicative noise.
To the best of our knowledge, our work the first the literature point out that constant regret may still be achievable in the presence of stochasticity (even in the simplest case where the noise profile is known advance). In this regard, can be seen as a first estimation the degree uncertainty that can enter the process before the aspiration of constant (or polylogarithmic) regret becomes an impossible proposition."
summary of our results is presented in Table 1. the paper's appendix, we discuss some further related works that are relevant but not directly related to our work. We also mention here that our paper focuses on the unconstrained setting, as this simplifies considerably the presentation and treatment of multiplicative noise models. We defer the constrained case (where players must project their actions to a convex subset of IRd), future work.
2 Problem Setup
Throughout this paper, we focus on deriving optimal regret minimization guarantees for multi-agent game-theoretic settings with noisy feedback. Starting with the single-agent case, given sequence of actions I, E X = and a sequence of loss functions fe: X' + R, we define the associated regret induced by x, relative to benchmark action p X'
T
Regr (p) -((((z)) f(())-
(1)
We then say that learner has regret if (egr(p) o(T) for all p X. In the sequel, we extend case, and we discuss the various feedback
this basic framework to the multi-agent, agent, model available to the optimizer(s).
No-regret learning in games. The game-theoretic analogue of the above framework is defined as follows. We consider a finite set of players indexed by i E N = (1...., N....,,N.... each with their individual action space X' g and their associated loss function é: X + R. where X 1I denotes the game's s joint action space. For clarity, any ensemble of actions or functions whose definition involves multiple players will be typeset in bold. In particular,
will write x = (x² x ") E X for the action profile of all players, where x' and x respectively denote the action of player and the joint action of all players other than i. In this way, each player / incurs at round a loss e (xx) which is determined not only by their individual action xi, but also by the
We also note that under the additional assumption of cocoercivity, a constant regret bound can be derived from [26. Th. 4.4). That being said, extending this result to the broader family of variationally stable games that address here requires non-trivial modifications (to both the algorithm and the analysis).

---

actions x, of all other players. Thus, by drawing a direct link with (1), given sequence of play zi;- the individual regret of each player i N is defined as
T Σ ( - ((pp,xT').
Regi (p*)
(2)
From a static viewpoint, the most widely spread solution concept in game theory is that of a Nash equilibrium, i.e., state from which player has incentive deviate unilaterally. Formally, point x, E X is a Nash equilibrium if for all E N and all x' E X2, we have (1(,,, x.") I (x xx"). ) In particular, if the players' loss functions are assumed individually convex (see below), Nash equilibria coincide precisely with the zeros of the players' individual gradient field, denoted by V = V z. l". That is, X, is Nash equilibrium if and only if Vxx)) 0. We will make the following blanket assumptions for all this:
Assumption 1 (Convexity and Smoothness). For all E N. E ('(,x"") is convex at all x and the individual gradient of each player 2 d is L-Lipschitz continuous.
Assumption 2 (Variational Stability). The solution set X. Ex V(x) 03 of the game is nonempty, and for all x E X, X. E X., we have (V(x), x - x. EiEN -x)==)))) 2.
The convexity requirement in Assumption I is crucial in the literature of online learning; otherwise, it not possible to transform iterative gradient bounds to bona fide regret guarantees. In similar vein, variational stability can be seen variant of the convexity assumption for multi- environments, where unilateral convexity assumptions do not suffice to give rise to a learnable game- for example, finite games are unilaterally linear, but finding a Nash equilibrium of finite game is PPAD- complete problem [9]. Our work thus focuses on games that satisfy the variational stability condition. Some important families of games that covered by this criterion monotone games (i.e., V is monotone), which in their turn include convex-concave zero-sum games, zero-sum polymatrix games, Cournot oligopolies, etc.
It is also worth noting that several recent works [1. 12, 15] have managed to bypass Assumption 2 when the players have access to perfect feedback; whether these techniques are applicable in the stochastic setup is an open question. In any case, Assumption 2 seems crucial for the last-iterate convergence presented in Section 6.
Oracle feedback and noise models. In terms of feedback, we will assume that players have access to noisy estimates of their individual payoff gradients, and we will consider two noise models, additive noise and multiplicative noise. To illustrate the difference hetween these two models, suppose we wish to estimate the value of some quantity v E TR. Then, an estimate of e with additive noise a random Eadd for some zero-mean noise variable Eadd: analogously,
variable oadd of the form oadd multiplicative noise model for U is a random variable of the form @mult = v(1 + Emult) for some zero- mean noise variable Emult. The two models can be compared directly via the additive representation of the multiplicative noise model as mmult = 0 + Emmlt which gives Var[fada] = u
With all this in mind, we will consider the following oracle feedback model: let gf V'(x,) Ei denote the gradient feedback to player at round f, where ? represents the aggregate measurement error relative to V (x(x). Then, with (JF)ren denoting the natural filtration associated to (x:)ee and E.[.] = E[ F.] representing the corresponding conditional expectation, we make the following standard assumption for the measurement error vector &,- = (G))
Assumption The noise vector (E:)re satisfies the following requirements for some a OM 2 0.
(a) Zero-mean: For all i N and E N, Eelgi] 0.
(b) Finite variance: For all i E A and t N. E, 111 < oZ + (x))
As an example of the above, the case a FM corresponds to "perfect information". i.e., when players have full access to their payoff gradients. The case A > 0, πM = O, is often referred to as "absolute noise", and it is a popular agntext-agnostic model for stochastic first-order methods, cf. [21, 29] and references therein. Conversely, the case σ = 0, αы > 0, is sometimes called "relative noise" [33], and it widely used as a model for randomized coordinate descent methods [30], randomized player updates in game theory [4], physical measurements in signal processing and control [36), etc. In the sequel, we will treat both models concurrently, and we will use the term "noise" to tacitly refer to the presence of both additive and multiplicative components.

---

3 Optimistic gradient methods: Definitions, difficulties, and a test case
To illustrate some of the difficulties faced by first-order methods in game-theoretic setting, consider the standard bilinear problem minøeR maX 0Φ, i.e., ( Φ) = 0Φ = (0, Φ). This simple game has unique Nash equilibrium at (0, 0) but, despite this uniqueness, it is well known that standard gradient descent/ascent methods diverge on this simple problem [11, 28]. To remedy this failure, one popular solution consists of incorporating an additional extrapolation step each iteration of the algorithm, leading to the optimistic gradient (OG) method
4 2 27 M/---
where of is player i's learning rate at round t. For posterity, it will be convenient to introduce the auxiliary iterate X and write X; 2+1 = xt for the actual sequence of actions. The above update rule then becomes
x = x - nigi-1. = N6419/-
(OG)
This form of the algorithm effectively decouples the learner's extrapolation step (performed with gi-1, which acts here as an optimistic guess for the upcoming feedback), and the bona fide update step, which exploits the received feedback de to update the player's action state from X; to X X This mechanism helps the players attain a) lower regret when their utilities vary slowly (from an online learning viewpoint) [8. 35]; and b) near-constant regret when all players employ the said algorithm in certain classes of games [1, 2, 12, 16, 20].
However, the above guarantees concern only the case of perfect gradient feedback, and may fail completely when the feedback contaminated by noise, as illustrated the following example.
Example 1. Suppose that the game's 's objective is an expectation over L1 (0, Φ) 30 and L2 o) -06 so that 1/2 and return the gradient of the sampled function as feedback. Assumption 3 is clearly satisfied here with A = 0 and σи = 2, i.e., the noise is multiplicative; however, as shown in Figure 1, running (OG) with either constant decreasing learning rate leads to i) divergent trajectories of play; and ii) regret oscillations that grow linearly or even superlinearly in magnitude over time. S
-2² = (Li + /2. At each round, we randomly draw L1 or L2 with probability
In view of the above negative results, we propose in the next section a simple fix of the algorithm that allows us retain its constant regret guarantees in the presence of multiplicative noise.
4 Regret minimization with noisy feedback
In this section, we introduce OG+ and OptDA+, our backbone algorithms for learning under uncer- tainty, and we present their guarantees in different settings. All proofs are deferred to the appendix.
Learning rate separation and the role of averaging. Viewed abstractly, the failure of OG in the face of uncertainty should be attributed to its inability of separating noise from the expected variation of utilities. In fact, noisy environment, the two consecutive pieces of feedback are only close in expectation, so player can only exploit this similarity when the noise is mitigated appropriately.
To overcome this difficulty, we adopt a learning rate separation strategy originally proposed for the EG algorithm by Hsieh al. [19]. The key observation here is that by taking larger extrapolation step, the noise effectively becomes an order of magnitude smaller relative to the expected variation of utilities. We refer to this generalization of OG as OG+. and we define it formally as
4 = X Til
X X; 14
(OG+)
where 7/ 2 m/t >> 0 are the player's 's learning rates (assumed F throughout the sequel). Nonetheless, the design of OG+ is somehow counter intuutire because the players' feedback enters the algorithm with decreasing weights. This feature opens up the algorithm adversarial attacks that can drive it to suboptimal regime in early iterations, as formally shown in [32, Thm. 3].
To circumvent this issue, we also consider a dual averaging variant of OG+ that we refer to as OptDA+, and which treats the gradient feedback used to update the players' chosen actions with the
By superlinear we mean that the regret grows faster than @(T), and this is possible here because neither the action set nor the feedback magnitude is bounded.
5

---

same weight. Specifically, OptDA+ combines the mechanisms of optimism [11, 35], dual averaging [20, 31, 38) and learning rate separation [19] as follows
X = xi 1
Xi+1 Xi
Mi+1
g'
(OpiDA+)
a=1
As we shall see below, these mechanisms dovetail in an efficient manner and allow the algorithm to achieve sublinear regret even in the adversarial regime. [Of course, OG+ and OptDA+ coincide when the update learning rate T/. is taken constant.]
Quasi-descent inequality. Before stating our main results on the regret incurred by OG+ and OptDA+, we present the key quasi-descent inequality that underlies our analysis, as it provides theoretical evidence on how the separation of learning rates can lead to concrete performance benefits.
Lemma 1. Let Assumptions and hold and all players run either (OG+) or (OptDA+) with non-increasing learning rale sequences To Hi- Then, for all i E EN, 12 2, and p¹ E X", we have
|
-p'l
[ -P'12
(1)
1
E1-1
E
+
llu - -p'1? T/.
(3a)
7
Th
1/11
-((Vi(X++) 2+ (xxx++))xxx3 ) - p²)
(3b)
- -ZE01IV'X c+ )112 + (Xx
(3c)
- -Ixx; Xx / 2/22/ V
(X,, x))
V'(X,
f)
(3d)
+ (1:2 11? + L I1in +7,3² + 2nil1 |?
(3e)
where i) ||E1- 112 +..)) = Σラ (vé + u/ = X1 player i runs (OptDA+).
II? and ii) ot = Xi if player i runs (OG+) and o6 >
Lemma indicates how the (weighted) distance between the player's chosen actions and a fixed benchmark action evolves over time. In order to provide some intuition on how this inequality will be used to derive results, we sketch below the role that each term plays in our analysis.
1. Thanks to the convexity of the players' loss functions, the regret of each player can be bounded by the sum of the pairing terms in (3b). On the other hand, taking x, X., p = 2 and summing from i = to N, we obtain -2(V (VVV(++))) (x++)) X x.), which is non-positive by Assumption 2, and can thus be dropped from the inequality.
2. The weighted squared distance to p', i.e., || p²1l?/nj,, telescopes when controlling the regret (Section 4) and serves
Lyapunov function for equilibrium convergence (Section 6).
3. The negative term in (3c) provides consistent negative drift that partially cancels out the noise.
4. The difference in (3d) can be bounded using the smoothness assumption and leaves out terms that are the order of ?
5. Line (3e) contains a range of positive terms of the order (1²)² + ny. To ensure that they are sufficiently small with respect to the decrease of (3c), both (n )ee and ni/1t should be small.
Applying Assumption 3 gives [ 2] < E[(1 + o V (X, 444 Ill + o%). revealing that 2//ni needs be least in the order of (1 + 33))
6. Last but not least, (1/rit 1/v p'1 simply telescopes for OptDA+ (in which case u² = X but is otherwise difficult to control for OG+ when 7 differs from o/.- This additional difficulty forces us to use global learning rate common across all players when analysing OG+.
To summarize, OG+ and OptDA+ are more suitable for learning games with noisy feedback because the scale separation between the extrapolation and the update steps delivers consistent negative drift (3c) that is an order of magnitude greater relative to the deleterious effects of the noise. We will exploit this property to derive our main results for OG+ and OptDA+ below.
Constant regret under uncertainty. We are now in position to state regret guarantees:

---

Theorem 1. Suppose that Assumptions 1-3 hold and all players run (OG+) with non non-increasing learning rate sequences "/. and Tt such that
7t and " S 2(1 + 2.
S min
for all LE E.N. (4)
/L d1) 2(4N + +)
Then, for all e N and all pt X2, we have
(a) ih = 0 (1/ t)) and nn. = (11 f)), then E (1))]
(b) If the noise is maltiplicative and the learning rates are constant, then E [Reg (n²) - O(1)
The first part of Theorem guarantees the standard ((VT) regret in the presence of additive noise, in accordance with existing results in the literature. What is far more surprising is the second part of Theorem 1 which shows that when the noise is multiplicatiie (i.e., when σλ 0), it is still possible to achieve constant regret. This represents a dramatic improvement in performance, which illustrate in Figure 1: by simply taking the extrapolation step be 10 times larger, the player's regret becomes completely stabilized. In this regard, Theorem provides fairly conclusive evidence that having access to exact gradient payoff's is not absolute requisite for achieving constant regret in thme-theoretic context.
On the downside, the above result requires all players to use the same learning rate sequences, a technical difficulty that we overcome below by means of the dual averaging mechanism of OptDA+.
Theorem 2. Suppose that Assumptions 1-3 hold and all players run (OptDA+) with non- con-increasing learning rate sequences ot and ny. such that
1
f for all E,E,NNNEN
1/ S 2L
min
and Tt S 4(1 + o.d
V3 + O (AN + 1)033
(5)
Then, for any i E and p' E Ex;, we have:
(a) If If = (11/t) and पi = O(1/Vt) for all j E N, then E [Regī (p') O(VT).
(b) If the noise is multiplicativv and the learning rates are constant, then E [Reg'r (p) = O().
The similarity between Theorems and 2 suggests that OptDA+ enjoys nearly the same regret guarantee as OG+ while allowing for the use of player-specific learning rates. As OptDA+ and OG+ coincide when run with constant learning rates, Theorem 1(b) is in fact special case of Theorem 2(b). However, when the algorithms are run with decreasing learning rates, they actually lead to different trajectories. In particular, when the feedback is corrupted by additive noise, this difference translates into the removal of logarithmic factors in the regret bound. More importantly, as we show below, it also helps to achieve sublinear regret when the opponents do not follow the same learning strategy, i.e., in the fully arbitrary, adversarial case.
Proposition 1. Suppose that Assumption 3 holds and player runs (OptDA+) with non-increasing learning rates 7/- = ((1/t==9) and ni = @ for some E [0. 1/4]. "oup=eex:lVV'((t +00, we have E Regi (p')) ) = O(T f every benchmark action p' X
We introduce the exponent in Proposition 1 because as suggested by Theorem 2(a), the whole range of E j0, 1/4] leads to the optimal O(vT) regret bound for additive noise when all the players adhere to the use of OptDA+. However, turns out that taking smaller q (i.e., smaller extrapolation step) is more favorable in the adversarial regime. This is because arbitrarily different successive feedback may make the extrapolation step harmful rather than helpful. On the other hand, our previous discussion also suggests that taking larger q (i.e., larger extrapolation steps), should be more beneficial when all the players use OptDA+. We will quantify this effect in Section 6; however, before doing so, we proceed in the next section show how the learning rates of Proposition I can lead to the design of a fully adaptive, parameter-agnostee algorithm.
5 Adaptive learning rates
So far, we have focused exclusively on algorithms run with predetermined learning rates, whose tuning requires knowledge of the various parameters of the model. Nonetheless, even though a player
7

---

might be aware of their own loss function, there is little hope that the relseed parameters are also known by the player. Our goal in this section will be to address precisely this issue through the design of adaptive methods enjoying the following desirable properties:
The method should be implementable by every individual player using only local information and without any prior knowledge of the setring's ' parameters (for the noise profile and the game alike).
The method should guarantee sublinear individual regret against any bounded feedback sequence.
When employed by all players, the method should guarantee (VVT) regret under additive noise and (11) regret under multiplicative noise.
In order to achieve the above, inspired by the learning rate requirements of Theorem 2 and Proposi- tion I, we fix q E (0, 1/4] and consider the following Adagrad-style [13] learning rate schedule.
22-
Th
(Adapt)
VI+ (119)112
||x; x2+1
As in Adagrad, the sum of the squared norm of the feedback appears in the denominator. This helps controlling the various positive terms appearing in Lemma I, such as L m and 2m l Nonetheless, this sum is not taken the same exponent in the definition of the two learning
rates. This scale separation ensures that the contribution of the term (X(++ x )ll appearing in (3c) remains negative, and it is the key for deriving constant regret under multiplicative noise.
As technical detail, the term ||X; - X;+1l "x;=>;;11 2|2 is involved in the definition of o/ for controlling the
difference of (3d). Finally, we do not include the previous received feedback 9i in the definition of oi and n/.. This makes these learning rates 1 measurable, which in turn implies Elginisi y] = O.
From a high-level perspective, the goal with (Adapt) is to recover automatically the learning rate schedules of Theorem 2. This in particular means that 7/ and ny should at least be in the order of 0(1/t3 9) and 12(1/ /t), suggesting the following boundedness assumptions on the feedback.
Assumption 4. There exists G, a 2 0 such that i) [[V'(z*)] < G for all i E N, x² E X2; and ti) || S ē for all i N. t N with probability 1.
These assumptions are standard in the literature on adaptive methods, cf. [3, 5, 14, 24).
Regret. We begin with the method's fallback guarantees, deferring all proofs to the appendix. Proposition 2. Suppose that Assumption 4 holds and player E NN follows (OptDA+) with learning rates given by (Adapt). Then, for any benchmark action p¹ E X we have E[Rei (p') O
Proposition 2 provides exactly the same rate as Proposition 1, illustrating in this way the benefit of taking a smaller for achieving smaller regret against adversarial opponents. Nonetheless, as we see below, taking smaller q may incur higher regret when adaptive OptDA+ is employed by all players. In particular, we require q > 0 in order to obtain constant regret under multiplicative noise, and this prevents us from obtaining the optimal O(VT) regret in fully adversarial environments.
Theorem 3. Suppose that Assumptions 1-4 hold and all players run (OptDA+) with learning rates given by (Adapt). Then, for any N and point p¹ X we have E|Regr (p'terr(p")) O(VT). Moreover, if the noise is multiplicative A 0), we have E(Regr (p') ((exp(1/(22))
The proof of Theorem is based on Lemma 1; we also note that the (VVT)) regret guarantee can in fact be derived for any q S 1/4 (even negative ones). The main difficulty here consists in bounding (3d), which does not directly cancel out since y/ might not be small enough. To overcome this challenge, we have involved the squared difference | X x 1| in the definition of nú so that the sum of these terms cannot be too large when of is not small enough. More details on this aspect can be found in the proof of Lemma 18 in the appendix.
Importantly, the O( ((VT) guarantee above does not depend on the choice of q. This comes in sharp contrast to the constant regret bounds (in 7') that we obtain for multiplicative noise. In fact, a key constant C, we have
step for proving this is to show that for some (envitonmentt-eeeeddeee)
N
to
N
E
1+
1
Σ
12 s=1
for all t e
(6)
8

---

This inequality is derived from Lemma by carefully bounding (3a), (3d), (3e) from above and bounding (3b). (3c) from below. Applying Jensen's inequality, we then further deduce that the right- hand side of inequality (6) is bounded by some constant. This constant, however, is exponential in 1/q. This leads to an inherent trade-off in the choice of q: larger values of q favor the situation where all players adopt adaptive OptDA+ under multiplicative noise, while smaller values of provide better fallback guarantees adversarial environments.
6 Trajectory analysis
In this section, we shift our focus to the analysis of the joint trajectory of play when all players follow the same learning strategy. We derive the convergence the trajectory of play induced by the algorithms (cf. Figure 1) and provide bounds on the sum of the players' payoff gradient norms E/= VV + >ll". This may be regarded as a relaxed convergence criterion, and by the design of the algorithms, feedback sequence of smaller magnitude also suggests more stable trajectory.
Convergence of trajectories under multiplicative noise. When the noise is multiplicative, its effect is in expectation absorbed by the progress brought by the extrapolation step. We thus expect convergence results that are similar to the noiseless case. This is confirmed by the following theorem.
Theorem 4. Suppose that Assumptions 1-3 hold with A 0 and all players run (OG+) (OptDA+) with learning rates given in Theorem 2(b). 6 Then, X
b+ rium and enjoys the stabilization guarantee Σt V (XIVV(++)))) (X++))191 +o0.
X converges almost surely to a Nash equilib-
Idea of proof. The proof of Theorem 4 follows the following steps.
1. We first show Et=1 E (XX++ 3)1 +oo using Lemma 1. This implies EE=IIV(X, y))? is finite almost surely, and thus with probability 1, [|V(X )ll converges to and all cluster point of (X + )aEN is a solution.
Il?
2. Applying the Robbins-Siegmund theorem to suitable quasi-descent inequality then gives the almost sure convergence of TE, Ii xx ///"///] to finite value for any x, E X..
3. The conditioning on Ft-1 makes the above quantity not directly amenable to analysis. This difficulty is specific to the optimistic algorithms that we consider here as they make use of past feedback in each iteration. We overcome this issue by introducing virtual iterate X, (X)) with X; x n' that serves as a -eeesrbbaee surrogate for X,. We then derive the almost sure convergence of El - . /1///'.
4. To conclude, along with the almost sure convergence of |X,+3 Xell and | ((x++)) to we derive the almost convergence of X to Nash equilibrium.
In case where the players run the adaptive variant of OptDA+, we expect the learning rates to behave constants asymptotically and thus similar reasoning can still apply. Formally, we show in the appendix that under multiplicative noise the learning rates of the players converge almost surely to positive constants, and prove the following results concerning the induced trajectory.
Theorem 5. Suppose that Assumptions 1-4 hold with a O and all players run (OptDA++) with learning rates (Adapt). Then, i) Σta II((X, 1 +oo with probability 1, and ii) X converges almost surely to a Nash equilibrium.
Compared to Theorem 4, we can now only bound Σee |V +1)l an almost sure sense. This is because in the case of adaptive learning rates, our proof relies on inequality (6), and deriving a bound on De -t=11 [XX 1 [[]] from this inequality does not seem possible. Nonetheless, with the almost convergence of the learning rates to positive constants, we still manage prove almost sure iast-iterate convergence of the trajectory of play towards a Nash equilibrium.
Such last-iterate convergence results for adaptive methods are relatively rare in the literature, and most of them assume perfect oracle feedback. To the best of our knowledge, the closest antecedents
'Reaal that OG+ and OptDA+ are equivalent when run with constant learning rates.

---

to our result are [2, 26], but both works make the more stringent cocoercive assumptions and consider adaptive learning rate that is the same for all the players. In particular, their learning rates are computed with global feedback and are thus less suitable for the learning-in-game setup.
Convergence of trajectories under additive noise. To ensure small regret under additive noise, take vanishing learning rates. This makes the analysis much more difficult as the term (1/1/41 - 11/n - p'll² appearing on the right-hand side of inequality (3a) is no longer summable. Nonetheless, it still possible provide bound the sum of the squared operator norms.
Theorem 6. Suppose that Assumptions 1-3 hold and either i) all players run (OG+) with learning rates described in Theorem I(a) and " = 2111t2 -) for some q E [0, 1/4]; if) all players run (OptDA+) with learning rates described in Theorem 2(a) and 7 = Q11/tà (9) for all E N for some q [0, 1/4]; or iii all players run (OptDA+) with learning rales (Adapt) and Assumption holds. Then, Σ E [XIV +4 =))+++ Ö(T
Theorem 6 suggests that the convergence speed of |V(X ++ IlI under additive noise actually depends on Therefore, though the entire range of E [0, 1/4] leads to O(vT) regret, taking larger may result in more stabilized trajectory. This again goes against Propositions and which suggests smaller leads to smaller regret in the face of adversarial opponents.
Finally, we also show last-iterate convergence of the trajectory of OG+ under additive noise.
Theorem 7. Suppose that Assumptions 1-3 hold and all players run (OG+) with non-increasing learning rate sequences and satisfying (4) and " (11/(t2= 7/2 ((1/(VEloo) )) for some 9 E (0, 1/4]. Then, X, converges almost surely to a Nash equilibrium. Moreover, if SUPIEn E E,1 < +00, then ++4 converges almost surely to a Nash equilibrium.
Theorem 7, in showing that the sequence X; generated by OG+ converges under suitable learning rates, resolves an open question of [19]. By contrast, the analysis of OG+ is much more involved due to the use of past feedback, as explained in the proof of Theorem 4. Going further, in the second part of statement, we show that X also converges to a Nash equilibrium as long as the 4-th moment of the noise is bounded. Compared to OptDA+, it is possible to show last-iterate convergence for OG+ under additive noise because we use 1
x, || (with x, E X.) Lyapunov function. The same strategy does not apply to OptDA+ due to summability issues. This is a common challenge shared by trajectory convergence analysis of the dual averaging template under additive noise.
Concluding remarks
In this paper, we look into the fundamental problem of no-regret learning in games under uncertainty. We exhibited algorithms that enjoy constant regret under multiplicative noise. Building upon this encouraging result, we further studied an adaptive variant and proved trajectory convergence of the considered algorithms. A central element that is ubiquitous in our work is the trade-off between robustness in the fully adversarial setting and faster convergence in the game-theoretic case, as encoded by the exponent q. Whether this trade-off is inherent to the problem or an artifact of the algorithm design warrants further investigation.
Moving forward, there are many important problems that remain to be addressed. On the technical side, first goal would be deepen our understanding on the convergence behavior of OptDA+ under additive noise. Extension of our results to learning in other type of games and/or under different types of uncertainty such as learning in finite games with sampling- payoff-basee based feedback would likewise be a valuable contribution. Going one step further, analyzing the situation where only fraction of players deviate is practically relevant (the cases studied in this paper represent the extreme of this spectrum). Taking into account other type of regret that may be more suitable for name-theoretic settings is yet another fruitful research direction to pursue.
Acknowledgments
This work received financial support from Grenolle Alpes (ANR-19 19-P31A-0003), the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement n 725594- time-data), and the Swiss National Science Foundation (SNSF) under grant number 200021 200021_205011 1, P. Mertikopoulos also supported by the grant ALIAS (ANR-19) 19-CC48-000 CE48-0018-01).
10

---

References
[1] loannis 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. arXiv preprint arXiv:211 1,.02000100000 2021.
[2] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-War Wei Lec, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with o(logt) swap regret in multiplayer games. arXiv preprint arXiv:2204. 11417, 2022.
[3] Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror- prox method for variational inequalities with singular operators. In Advances Neural Infor- mation Processing Systems, volume 32, 2019.
[4] Kimon Antonakopoulos, Thomas Pethick, Ali Kavis, Panayotis Mertikopoulos, and Volkan Cevher. Sifting through the noise: Universal first-order methods for stochastic variational inequalities. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 13099-13111, 2021.
[5] Francis Bach and Kfir Levy. A universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference on Learning Theory, pages 164-194. PMLR, 2019.
[6] David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathematics, 6(1):188, 1956.
Tatjana Chavdarova, Gauthier Gidel, François Fleuret, and Simon Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. In Advances in Neural Information Processing Systems, 2019.
[8] Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. Conference on Learning Theory, 2012.
[9] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1):195-25) 2009.
[10] Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. Near-optimal no-regret algo- rithms for zero-sum games. In Proceedings of the tventy-second annual ACM-SIAM symposium on Discrete Algorithms, pages 235-254. STAM, 2011.
[11] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference on Learning Representations, 2018.
[12] Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34, 2021.
[13] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121-2159, 2011.
[14] Alina Ene and Huy L Nguyen. Adaptive and universal algorithms for variational inequalities with optimal convergence. In 36th AAAI Conference on Artificial Intelligence, 2022.
[15] Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung Wei Lee, Christian Kroer, and Tuomas Sandholm. Near-optimal no-regret learning for general convex games. arXiv preprint MwXiv:2206.08722. 2022.
[16] Gabriele Farina, Chung- Shung-Wei Lee, Haipeng Luo, and Christian Kroer. Kernelized multiplicative weights for -ooyphlyll games: Bridging the gap between learning in extensive-form and normal-form games. arXiv preprint arXiv:2202.0000
2022.
[17] James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3(2):97-139, 1957.
[18] Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimiza- tion, 2(3-4):157-325, 2016.
[19] Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In Advances Neural Information Processing Systems, volume 33, pages 16223-16234, 2020.

---

[20] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos, Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Conference on Learning Theory, 2021.
[21] Anatoli Juditsky, Arkadi Semen Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[22] Parameswaran Kamalaruban, Yu-Ting Huang, Ya-Ping Hsieh, Paul Rolland, Cheng Shi, and Volkan Cevher. Robust reinforcement learning via adversarial training with langevin dynamics. In Advances in Neural Information Processing Systems, volume 33, pages 8127-8138, 2020.
[23] Ehsan Asadi Kangarshahi, Ya-Ping Hsieh, Mehmet Fatih Sahin, and Volkan Cevher. Let's be honest: An optimal no-regret framework for zero-sum games. In International Conference on Machine Learning, pages 2488 2496, 2018.
[24] Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algo- rithm with optimal guarantees for constrained optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
[25] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonom. i Mat. Metody, 12:747-756, 1976.
[26] Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael I Jordan. Finite-tima last-iterate convergence for multi-agent learning in games. In International Conference on Machine Learning, pages 6161-6171, 2020.
[27] Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173(1-2):465-577, January 2019.
[28] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-poin problems: Going the extra (gradient) mile. In International Conference on Learning Representations, 2019.
[29] Arkadi Semen Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-1699 2009.
[30] Yurii Nesterov. Introductory Lectures on Convex Optimizaaiin: A Basic Course, Number 87 in Applied Optimization. Kluwer Academic Publishers, 2004.
[31] Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Program- ming, (20(1):221-259) 2009.
[32] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50-69, 2018.
[33] Boris Teodorovich Polyak. Introduction to Optimization. Optimization Software, New York, NY, USA, 1987.
[34] Leonid Denisovich Popov. A modification of the Arrow-Hurwiez method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845-88) 848, 1980.
[35] Alexander Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, 2013.
[36] Gesualdo Scutari, Daniel P Palomar, Francisco Facchinei, and Jong-Shi Pang. Convex optimiza- tion, game theory, and variational inequality theory. IEEE Signal Processing Magazine, 27(3): 35-49, 2010.
[37] Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
[38] Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543-259, October 2010.
[39] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent.
In International Conference on Machine Learning, pages 928-936, 2003.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethies review guidelines and ensured that your paper conforms them?
[Yes]
2. If you including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't '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 conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to 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": "qXQGVZvSxIH", "reviewer": "Reviewer_yRqj", "summary": "This paper studies no-regret learning in multi-player smooth games in the presence of noise. The paper analyzes variants of optimistic gradient descent, and shows that when the noise is purely multiplicative, i.e. when the strength of noise is proportional to the gradient norm, all players can achieve regret independent of $T$. An adaptive learning rate scheme is then proposed to eliminate the need to know the learning rates of other players.", "questions": "- Can Assumption 4 be avoided, since the final regret guarantees have some sort of boundedness assumptions?\n\n- Can be it be shown that extrapolation is algorithmically necessary? In other words, is it possible for online gradient descent to achieve a similar $O(1)$ regret bound?\n\n- The abstract mentions a smooth extrapolation between worst- and best- case guarantees. However, based on the statement of Theorem 3, it seems that the deviation of any player from the Adapt scheduling would lead to the worse fallback regret bound. Is there an actual \"extrapolation\" between the two cases? In other words, can regret bounds between $O(exp(1/2q))$ and $O(T^{0.5+q})$ be provided, if only a small number of players deviate slightly from the Adapt scheme?", "limitations": "Limitations of this work are appropriately discussed.", "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- The algorithms are simple, tuning only the learning rates and extrapolation parameter in vanilla OGD. They are also very practical, since they enjoy guarantees in both cooperative (Theorem 3) and adversarial (Proposition 2) scenarios, and can be made parameter-free.\n- The results would be a nice addition to online learning literature, where few results beyond the $O(\\sqrt{T})$ bound exist when the feedback is noisy.\n- The analysis of optimistic gradient descent with noise is novel.\n\nWeaknesses:\n- The setting is a bit restricted, since only the unconstrained case is handled, and the interesting results are for the multiplicative noise setting. Dealing with unconstrained space precludes application to matrix games (strategies constrained on simplices) and creates issues in the definition of regret (an artificial bounded set $\\mathcal{K}$ is introduced for that). While multiplicative noise is a common assumption in optimization literature, it might not be the most suitable one for game settings, since arguably one of the most common sources of noise is the sampling noise from mixed strategies, which is additive rather than multiplicative. This work would greatly benefit if it can be applied to learning in multi-player matrix games with bandit feedback.\n- The authors claim that the $O(1)$ regret bound in the presence of noise to be the first of its kind. It seems to me, however, that Theorem 4.4 in Lin et al. [24] also implies an $O(1)$ regret bound, albeit under a stronger setting. If this is the case, I would suggest rephrasing this claim.", "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": "nx0qsnpRpD", "reviewer": "Reviewer_vptX", "summary": "The paper studies simultaneous no-regret learning in a subset of convex games (satisfying a variational stability condition) when players observe noisy estimates of their gradients. An optimistic gradient algorithm is proposed which uses learning rate separation. This allows to prove O(sqrt(T)) regret in the presence of additive noise, and O(1) regret in case of multiplicative noise. This was not possible with existing optimistic gradient schemes. Moreover, the authors propose a primal-dual variant of their method which retains the same guarantees but ensures also O(sqrt(T)) regret in fully adversarial environments. Authors consider also adaptive learning rate selection methods that do not require a-priori global knowledge of the game and finally study the last-iterate convergence of the aforementioned approaches under the considered noise models.", "questions": "I have the following questions/comments: \n- The authors make the blankett assumptions of convexity and variational stability. Perhaps a discussion about these, and why are they needed/helpful would be beneficial. \n- Besides the lack of global optimality and regret guarantees, would the proposed time-scale separation be beneficial for non-convex games too? Why?\n", "limitations": "I don't foresee potential negative societal impact.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Simultaneous learning in games is a relevant problem, which has received significant attention in the past years. Moreover, the study of such dynamics in the presence of noise is definitely important. The results presented are very impressive, original, and sound. Moreover, the authors did a very good job in putting them into the context of existing works and providing intuitions along the way.\nHence, I definitely recommend acceptance. \nI don't think the paper has major weaknesses. However, I feel additional experimental results would have made a stronger impact and could serve as ablation for the different convergence bounds and noise models considered.", "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": "hm76YActITq", "reviewer": "Reviewer_NjYe", "summary": "The paper studies the expected regret achievable by individual players\nin the general class of variationally stable games when the gradient\nobservations are perturbed by noise that can be either additive or\nmultiplicative. An important technique is learning rate separation for\noptimistic methods, which refers to scaling the optimistic extrapolation\nsteps by a larger step size than the update steps. Learning rate\nseparation was previously introduced by Hsieh et al for optimistic\nonline gradient descent in the context of additive noise, but their\nalgorithm is vulnerable to adversarial attacks in early iterations, so\nthe present paper adapts it for optimistic dual\naveraging/follow-the-regularized-leader. The paper considers two cases:\n\n1. All players use (more or less) the same algorithm, which is described\nin the paper;\n2. Some of the players use an arbitrary strategy.\n\nFor case 1, Thms 1&2 show that all players can achieve constant regret\nif the noise is multiplicative. (It is also shown that, with a different\nstep size tuning, they can get tilde O(sqrt{T}) regret, but that would\nalready be achievable using standard results, so this seems of interest\nonly as a lead-up to the adaptive results in the next section.)\n\nIn section 5, adaptive step sizes are introduced, which achieve a type of\nbest-of-both-worlds result:\n* If some of the other players do not use the same algorithm, then they\n  get O(T^{1/2 + q}) regret, where q is a hyperparameter of the\n  algorithm. This is optimal for q=0, and slightly suboptimal otherwise.\n* If all players use the same algorithm with these adaptive step sizes,\n  then they get:\n  - constant regret for q>0 if the noise is multiplicative, where the\n    constant depends on q.\n  - O(sqrt{T}) regret otherwise.\n\nFinally, section 6 contains a trajectory analysis for the proposed\nmethods with non-adaptive step sizes.\n\nMinor remarks:\n\n* In Theorems 1 and 2, \"Reg_{p^i}(T)\" should be \"Reg_T(p^i)\" and the\n  statement should contain a \"for all p^i\".\n* In Theorem 3: there should be parentheses around \"2q\" to show that q\n  is in the denominator of the fraction and not in the numerator.\n* Line 102: \"widely solution\" is missing a word.\n* Assumption 1: add \"for all x^{-i}\"\n* Assumption 2: define cal{X}_* \n", "questions": "* Could the authors comment on whether the following simple crude\n  approach would also work to get an adaptive method?\n  - Run the non-adaptive method from Theorems 1&2 that guarantees\n    constant regret if the noise is multiplicative. \n  - If the regret ever exceeds the constant from the regret bound,\n    restart with any standard method that gets O(sqrt{T}) regret.\n  Clearly this is not as elegant as the approach in the paper, but it\n  seems it would solve the suboptimal dependence on q.\n", "limitations": "* The fact that the adaptive method does not recover the optimal rate,\n  but O(T^{1/2 + q}) for case 2 should be mentioned much earlier. It\n  should at least be mentioned in the introduction, and possibly also in\n  the abstract.\n\n* The rates depend on the optimal comparator points p^i, but this\n  dependence is not made explicit in the big-Oh notation, and no attempt\n  is made to achieve an optimal dependence in the tuning of the step\n  sizes. This limitation is clear from the results and not uncommon in\n  the related work, so it is perfectly fine and requires no extra\n  discussion.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a well-written paper, with a nice new adaptive result. It\ncontains a novel approach of using learning rate separation to deal with\nmultiplicative noise, which is shown to stabilize the last iterate of\nthe dual averaging algorithm, and therefore constant regret becomes\npossible. The importance of studying multiplicative noise is\nsufficiently motivated.\n\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": "bIyemohKNY1", "reviewer": "Reviewer_sxiN", "summary": "The paper considers learning in variationally stable games, with noisy gradient feedback. The cost function of each player is assumed to be convex and smooth. It is shown that optimistic gradients methods can achieve constant regret with multiplicative noise while still achieving O(sqrt(T)) for additive noise. The key novelty in the methods is to separate the step-size sequence that multiplies the current gradient with the sequence that multiplies the \"optimistic\" term. Two methods are proposed, where the second one is shown to also maintain O(sqrt(T)) regret against an adversary. An adaptive version of both is shown that doesn't need to be tuned. Finally, convergence to Nash equilibrium is shown if all players use one of these algorithms (even if with different sequences). ", "questions": "1) Do you see any meaning to the regret against other players beyond its connection with convergence to equilibrium? (average or last iterate)?\n\n2) Do you have a sense of whether the O(sqrt(T)) result for additive noise is tight? in other words, what is the answer to the main question in line 52 for noise that is more general than multiplicative? if unknown, I think it would be interesting to state that in the concluding remakes. ", "limitations": "This is a theory paper with no societal impact. The paper clearly states all technical limitations. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well-written, and the technical contribution is solid and significant. The paper advances the understanding of gradient learning methods in variationally stable games, which to the best of my knowledge are the largest class of games where gradients methods are known to converge.  It was definitely interesting and enjoyable to read. I believe the paper should be accepted. \n\nMy main issue is with the presentation and position of the results. I'll admit this is highly subjective, but perhaps can be useful when revising the paper: \n\nThe paper can easily be made more interesting to a broader audience. As written, the paper is mainly interesting for readers who already agree that the technical questions tackled here are interesting. I think that the main issue is that the notion of regret loses its meaning against other players since the benchmark is arbitrary - it is how much the best action in hindsight would achieve if for some reason the other players were forced to play the same thing they played against the algorithm, without responding to this best action. Indeed, the technical reason this regret is still interesting (at least to me) is that gives convergence to equilibrium, which in this case is the Nash equilibrium, which is even the last iterate convergence rather than the immediate average iterate convergence (given the regret). While the statement in Line 25 about the learner's objective makes sense against an oblivious adversary (or a stochastic environment), I'm not sure if it still does for multiplayer environments. Why would a learner concern itself with optimizing the regret against other players, if the benchmark has no meaning? Low regret doesn't show that \"the sequence is efficient\" in the multi-player case. Without the convergence rate to Nash as motivating, going beyond the O(sqrt(T)) lower bound therefore seems purely mathematical. Of course, I might have missed something here, so please see the question below. \n\nThe way the introduction is written, I got the impression that the main goal of the paper is to prove lower regret guarantees for a multiplayer environment with noisy gradient feedback. However, this is only done for multiplicative noise. Where certainly impressive on its own, it gives an (unjustified) sense of disappointment as a partial answer to the question in line 52. I'm therefore not sure if this question properly motivates the great results in the paper.  At the same time, the paper acheives something very impressive with no qualifiers - it provides the first gradient methods that converge to Nash in variationally stable games with noisy gradient feedback, even if they're not strict (to the best of my knowledge, so please verify). It also provides convergence rates. Along with the fact that regret is an arbitrary performance measure against other players, I find this to be the main contribution of the paper. Then, discussing the comparison with [40] is necessary to highlight this contribution. I would consider highlighting this aspect of the results. \n\nMinor comments: \n\n1) What do you mean by superlinear regret in line 51? worse than O(T)? \n\n2) Please provide a reference for \"Nash equilibria coincide precisely with the zeros...\" in line 106.\n\n3) The V notation is easy to miss since it's in the text above Assumption 2, which doesn't state it's a definition. \n\n4) A table mapping the results in this paper can help. I don't mean the conversion table in the appendix, but one that gives a brief meaning for each result. \n\n5)  The notation X compared to x is confusing since it's usually reserved for random variables, whereas here both are random. \n\n6)  Line 146 can emphasize that the 1/2 shifted sequence is the actual sequence of actions.\n\n7) Lines 150-151: here the utilities don't change, or do you mean from a single-player point of view? it's better to explain why you're interested in these methods. Then, \"in certain classes of games\" is vague, please provide a reference. \n\n8) Line 160-161 should mention that the regret is constant only for multiplicative noise. \n\n9)  In Theorem 3, provide the variance parameters to supplement the statement  \"if the noise is multiplicative\".\n\n10) Line 340 - probably a typo, this is Theorem 5.\n\n11) Line 345 - \"relative\" - relatively \n\n12) Line 768 - \"The proof is proved\" - the result is proved. \n\n13) Lemma 8 - \"holds\" - hold.\n\n14) Unify \"infinity\" and \"+infinity\". \n\n15) (24) - I think this should be \\eta_{t+1} ", "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