Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The paper shows that when all agents in a game use the Optimistic Hedge regret-minimization algorithm, their regret can be bounded as Otilde(1). When no assumption is made about what algorithm the other agents are using, the regret bound of Optimistic Hedge is still bounded as Otilde(sqrt(T)). 
main_review: The paper is very clear and well-organized. It builds on several insights that were already known (for example, the analysis of FTRL in terms of local norms induced by the Hessian of the regularizer, in this case the negative entropy regularizer), and introduces new interesting tools to tighten the analysis of optimistic hedge. The paper cites all the relevant literature I was aware of.

The result is interesting and I think it would be a great addition to NeurIPS. 

I have a couple of question for the authors:
1. Optimistic algorithms were historically developed as "predictive" algorithm, where at each time t the regret minimizer receives a prediction of the next loss before outputting its next decision/strategy $x^t$. It turns out that in most case it makes sense to set the prediction of the next loss to just be the last-received loss. The version of optimistic hedge considered in this paper can clearly be read as making that tacit assumption. However, the proofs in the paper by Syrgkanis et al. apply more generally to any prediction, giving a regret bound that scales with the norm of the mismatch between each loss and its prediction. I wonder if the same can be done in your paper. It would be interesting to figure out "how late" the assumption that prediction = latest loss can be made, and if a more general regret bound that scales with the norm of the mismatch can be given first, and only then under the assumption that prediction = latest loss the bound in the paper can be established. I find that keeping the prediction generic would help intuitively separate what is a general result, and what is "magic" that is made possible only by assuming something special about the prediction of the loss.

2. Is it possible to give a simple estimate for the magnitude of the constants involved in Theorem 3.1?
limitations_and_societal_impact: I think it would be interesting to add a section describing, at a high level, what could be done to extend the positive result in the paper to more general settings. For example: perhaps some ideas from the paper can be extended to predictive OMD/FTRL on more general convex sets, or maybe it's possible to give a more general regret bound that works for any regularizer, akin to the RVU form of the regret bound given by Syrgkanis et al.
review_title: null

final_score: rating: 10: Top 5% of accepted NeurIPS papers, seminal paper
review_content: summary: The paper studies no regret learning in multi-player general sum games. The major result of this paper is to prove that if every player adopts Optimistic Hedge, then individual regrets decays at rate $\tilde{O}(1/T)$, improve upon the previous $O(1/T^{5/6})$ of (Chen and Peng, NeurIPS 2020). 
main_review: Advantage: Learning in games is an important topics, and especially the convergence rate of no regret learning algorithms. The paper proves optimistic Hedge gives a near-optimal convergence rate of multi-player game, this is an important contribution. The technique of this paper is also very novel. 

Drawback: To be picky, the writing of this paper could be improved, it would be better to explain the high level intuitions of the proof, e.g. why one wants to analyses the t-th order.

Summary: This is a very strong paper and I strongly recommend the acceptance of this paper. I didn't go through the proof, so I haven't checked the correctness of the proof. As I suggested above, it would be good to polish the writing, it would make reading easier.


limitations_and_societal_impact: Looks good.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper analyzes the regret of Optimistic Hedge in multi-player general-sum games. The paper shows that the algorithm attains polylog($T$) regret for each player, which improves over known rates that scale polynomially with $T$.
main_review: The focus of this paper is to analyze Optimistic Hedge (which can be seen as an instance of Optimistic Mirror Descent). The main contribution of this paper is the technical improvement in the analysis of this existing algorithm. The key technique, as I understand it, is to control the variance of slowly changing vectors via bounding the variance of its high-order finite differences. While the improvement in the regret bound is certainly substantial, I do have some concerns over the correctness of the results.

1. In Eq. (28) the proof of Lemma 4.1, the second term is 
$\sum_{t=1}^T \Vert x_i^{(t)}-\tilde x_i^{(t)}\Vert^*_{x_i^{(t)}}\cdot  \sqrt{Var_{x^t_i}(l_i^{(t)}-l_i^{(t-1)})}$
. The dual norm term is then controlled in Eq. (32) by $\sqrt{(1+C_1\eta)\eta^2}\cdot \sqrt{Var_{x^t_i}(l_i^{(t)}-l_i^{(t-1)})}$. Thus the whole term should be controlled by $(1+O(1))\eta \cdot Var_{x^t_i}(l_i^{(t)}-l_i^{(t-1)})$. Yet in Eq. (27), this term is shown as $(\frac{1}{2}+O(1))\eta \cdot Var_{x^{(t)}_i}(l_i^{(t)}-l_i^{(t-1)})$. I am confused over how does the $\frac{1}{2}$ factor arise. Note that this factor does matter in the proof of Theorem 3.1 (Eq. (104)-(106)). If the leading constant is indeed $1+O(1)$ instead of $\frac{1}{2}+O(1)$, the negative term in Eq. (104) would not be sufficient to cancel the second positive term. Perhaps the constant factor ($\frac{1}{2}$) in Lemma 4.2 should be made smaller?

2. I am also a bit confused over the proof of Lemma 4.2. In particular, how does on get from Eq. (96) to the base case of Eq. (97)? With $h=H-1$, the second term in Eq. (97) is $\mu^2\cdot \frac{2C_0\cdot H^2}{\alpha^3 \cdot \alpha_0^2H^6}=\mu^2\cdot polylog(T)$. Why is this greater than $\mu^2 T$?

Other comments:

3. The improvement in the dependence on $T$, compared to previous work on Hedge ($\tilde{O}(\sqrt{T})$) and Optimistic Hedge ($\tilde{O}(\sqrt{m}T^{1/4})$), seems to come at a cost of worse dependence on $m$, the number of players. In this sense, is the regret bound in this work really near-optimal?

4. Is there a trade-off between $m$ and $T$? If not, is it possible achieve $polylog(n,T)$ regret with no dependence on $m$?

5. In the current setting, player $i$ observes $E_{-i}\left[ \mathcal{L}_i(a_i, a^{-i})\right]$ for each $a_i$, instead of $\mathcal{L}_i(a_i,a^{-i})$. From a game-play point of view the latter feedback seems a bit more natural, as player $i$ don't have access to the randomness controlled by other players. I realize that existing literature also uses the former type of feedback, but is it the best formulation (from a game-play perspective)? Also, since the feedback is deterministic, isn't it possible to achieve regret independent of $T$?
limitations_and_societal_impact: This work is purely theoretical and do not present foreseeable negative social impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper shows that if all the players of a multi-player general-sum game use Optimistic Hedge with sufficiently small step-size, the regret of each player is bounded as $O(\log^4 T)$.
main_review: As far as I am aware, this paper is the first to prove that an algorithm enjoys $\text{poly}(\log T)$ regret in all multi-player general-sum games. I believe this is an important contribution. Moreover, in my eyes, the proofs are highly technical and non-trivial. This start with the use of local norms which are common for the analysis of online learning algorithms but were less considered for the analysis of Optimistic Hedge, and is followed by several amazing ideas which goes from finite difference sequences to discrete Fourier transform. Unfortunately, I was unable to go through the entire appendix, but the overall schema seems correct.

I would also like to highlight that, with a single theorem proven and fives pages dedicated to the outline of the proof, this paper seems to be quite atypical for NeurIPS. Nonetheless, I think the authors have made an effort to sketch their proof in the main text. Although the use of big O notations makes the statements of the theorems and the proofs a little problematic, the readers can already get an idea about the structure of the proof before potentially looking into the appendix for a more rigorous and complete version.

**Suggestions for potential improvements of the presentation**

Given the particularity of the paper, I am not really sure about how to further improve it. Below are just some personal thoughts that the authors can take as reference.

1. I found that the paper could benefit from a wrap-up section or paragraph. In fact, both sections 4.3 and 4.4 are technical and devoted to the proof of lemma 4.2 and are thus not directly related to the main result of the work. For sake of completeness, it would be nice to link these back to Theorem 3.1 at the end. (Sure, this may not add any extra value to the work. It is just a matter of taste.)

2. It seems that many constants mentioned in the theorems are in fact absolute constants that come from numerical inequalities. Maybe it is worth making this point clear to the audience, or even directly providing the numerical values for which the inequalities hold.

3. Typos
    - line 256: right-hand side?
    - line 267 and the subsequent inequality: the authors seem to confound $A_1$ and $A_2$
    - I quickly went through the proof of Lemma 4.1 and feel that we should put $\eta$ instead of $\eta/2$ both after $+$ and $-$ at the r.h.s of the inequality.
limitations_and_societal_impact: Fine
review_title: null

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