Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.
Hence, I definitely recommend acceptance. 
I 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.
questions: I have the following questions/comments: 
- 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. 
- Besides the lack of global optimality and regret guarantees, would the proposed time-scale separation be beneficial for non-convex games too? Why?

limitations: I don't foresee potential negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- 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.
- 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.
- The analysis of optimistic gradient descent with noise is novel.

Weaknesses:
- 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.
- 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.
questions: - Can Assumption 4 be avoided, since the final regret guarantees have some sort of boundedness assumptions?

- 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?

- 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the expected regret achievable by individual players
in the general class of variationally stable games when the gradient
observations are perturbed by noise that can be either additive or
multiplicative. An important technique is learning rate separation for
optimistic methods, which refers to scaling the optimistic extrapolation
steps by a larger step size than the update steps. Learning rate
separation was previously introduced by Hsieh et al for optimistic
online gradient descent in the context of additive noise, but their
algorithm is vulnerable to adversarial attacks in early iterations, so
the present paper adapts it for optimistic dual
averaging/follow-the-regularized-leader. The paper considers two cases:

1. All players use (more or less) the same algorithm, which is described
in the paper;
2. Some of the players use an arbitrary strategy.

For case 1, Thms 1&2 show that all players can achieve constant regret
if the noise is multiplicative. (It is also shown that, with a different
step size tuning, they can get tilde O(sqrt{T}) regret, but that would
already be achievable using standard results, so this seems of interest
only as a lead-up to the adaptive results in the next section.)

In section 5, adaptive step sizes are introduced, which achieve a type of
best-of-both-worlds result:
* If some of the other players do not use the same algorithm, then they
  get O(T^{1/2 + q}) regret, where q is a hyperparameter of the
  algorithm. This is optimal for q=0, and slightly suboptimal otherwise.
* If all players use the same algorithm with these adaptive step sizes,
  then they get:
  - constant regret for q>0 if the noise is multiplicative, where the
    constant depends on q.
  - O(sqrt{T}) regret otherwise.

Finally, section 6 contains a trajectory analysis for the proposed
methods with non-adaptive step sizes.

Minor remarks:

* In Theorems 1 and 2, "Reg_{p^i}(T)" should be "Reg_T(p^i)" and the
  statement should contain a "for all p^i".
* In Theorem 3: there should be parentheses around "2q" to show that q
  is in the denominator of the fraction and not in the numerator.
* Line 102: "widely solution" is missing a word.
* Assumption 1: add "for all x^{-i}"
* Assumption 2: define cal{X}_* 

strengths_and_weaknesses: This is a well-written paper, with a nice new adaptive result. It
contains a novel approach of using learning rate separation to deal with
multiplicative noise, which is shown to stabilize the last iterate of
the dual averaging algorithm, and therefore constant regret becomes
possible. The importance of studying multiplicative noise is
sufficiently motivated.


questions: * Could the authors comment on whether the following simple crude
  approach would also work to get an adaptive method?
  - Run the non-adaptive method from Theorems 1&2 that guarantees
    constant regret if the noise is multiplicative. 
  - If the regret ever exceeds the constant from the regret bound,
    restart with any standard method that gets O(sqrt{T}) regret.
  Clearly this is not as elegant as the approach in the paper, but it
  seems it would solve the suboptimal dependence on q.

limitations: * The fact that the adaptive method does not recover the optimal rate,
  but O(T^{1/2 + q}) for case 2 should be mentioned much earlier. It
  should at least be mentioned in the introduction, and possibly also in
  the abstract.

* The rates depend on the optimal comparator points p^i, but this
  dependence is not made explicit in the big-Oh notation, and no attempt
  is made to achieve an optimal dependence in the tuning of the step
  sizes. This limitation is clear from the results and not uncommon in
  the related work, so it is perfectly fine and requires no extra
  discussion.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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). 
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. 

My 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: 

The 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. 

The 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. 

Minor comments: 

1) What do you mean by superlinear regret in line 51? worse than O(T)? 

2) Please provide a reference for "Nash equilibria coincide precisely with the zeros..." in line 106.

3) The V notation is easy to miss since it's in the text above Assumption 2, which doesn't state it's a definition. 

4) 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. 

5)  The notation X compared to x is confusing since it's usually reserved for random variables, whereas here both are random. 

6)  Line 146 can emphasize that the 1/2 shifted sequence is the actual sequence of actions.

7) 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. 

8) Line 160-161 should mention that the regret is constant only for multiplicative noise. 

9)  In Theorem 3, provide the variance parameters to supplement the statement  "if the noise is multiplicative".

10) Line 340 - probably a typo, this is Theorem 5.

11) Line 345 - "relative" - relatively 

12) Line 768 - "The proof is proved" - the result is proved. 

13) Lemma 8 - "holds" - hold.

14) Unify "infinity" and "+infinity". 

15) (24) - I think this should be \eta_{t+1} 
questions: 1) Do you see any meaning to the regret against other players beyond its connection with convergence to equilibrium? (average or last iterate)?

2) 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.
review_title: null

Meta-review: metareview: Reviewers are all positive and appreciate the theoretical contributions of the paper. Great work! Please make sure you address all the reviewers' comments and incorporate them (and any new experimental results, if applicable) in your camera-ready.
confidence: Certain
Decision: Accept