Venue: NeurIPS 2022 Conference

Reviews:

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: This paper proves a new phenomenon about the Optimistic Mirror Descent (OMD) algorithm in two-player general-sum matrix games (bimatrix games): The iterates either converge to an approximate Nash Equilibrium (NE), or converge to a Strong Coarse Correlated Equilibrium (CCE). This result links and improves over two existing understandings: (1) Convergence to NE is unlikely to be generally achievable by any efficient algorithm due to its PPAD-hardness; (2) Convergence to approximate CCE is achievable by any no-regret algorithm, but it is unclear whether such CCE is a strong CCE (in the present paper’s sense).
strengths_and_weaknesses: Strengths:

The main message of this paper is conceptually quite interesting and new. Most existing works consider learning NE in two-player zero-sum games and CCE in multi-player general-sum games as parallel goals, as they can both be achieved by no-regret learning. On the other hand, learning NE in general-sum games is likely computationally challenging due to its PPAD hardness, and thus very sparsely studied in the context of no-regret learning (which mostly consider computationally efficient algorithms). 

This paper essentially proves that, for the OMD algorithm and *two-player* general-sum games, if NE is not achieved, then convergence to CCE is stronger than standard bounds—you actually converge to $O(-\epsilon)$-CCE (what’s called the “strong CCE” in the paper) rather than $O(\epsilon)$-CCE. At a high level this seems to say something about the “optimization landscape” of bimatrix games, like it is perhaps more benign than the worst-case hardness / convergence results suggests. 

Technically, it appears that the result follows by playing with the fundamental RVU property (and its proof) of OMD algorithms and making several smart observations. In particular, the proof (for the Reg_X part) follows by the observation that if NE is not achieved, then OMD iterates must move substantially (Proposition 3.2), which makes the negative term in the RVU dominate the positive term if learning rate is small enough, hence a *negative* regret and convergence to strong CCE. This argument appears new and may be applied in future work. It also gives me an impression that the RVU property may have other fruitful consequences yet to be discovered, despite its already powerful consequences for large bodies of work in this area. 

It is also good to see the numerical experiments, in particular the fact that convergence to both NE and strong CCE are possible in general-sum games (so that the “either-or” statement in the theorem is unlikely to be improved, at least for this algorithm).


Weaknesses:

The result has a feeling of being slightly preliminary and not very complete. One caveat is the perhaps restrictive set of assumptions: global smoothness of regularizer, two-player games, and very small learning rate. In particular I am a bit bothered by the small learning rate, which is $O(\epsilon^2)$ compared with the standard $\Theta(1)$ learning rate for OMD type algorithms. This also makes convergence to NE/Strong CCE slower than standard $1/\epsilon^2$ time. I understand it is necessary in the current proof, but I wonder have the authors thought about larger learning rates (as mentioned in Appendix B)? Or alternatively, infinitesimally small learning rate like in gradient flow?

Also, the assumption of global smoothness of the regularizer rules out the very standard example of entropic regularizer on the probability simplex (whose smoothness grows to $\infty$ as we approach the boundary) for normal-form games, as mentioned in the open questions section in Appendix B. In numerical experiments, the authors consider L2 regularizers which are indeed globally smooth (thus satisfying the conditions of the theorem) but less standard. 

Section 4.1 needs a bit more polishing. Some important quantities are not well-defined (e.g. what is “incentive-compatibility parameter?) Apart from that, Figure 2 is also a bit confusing (e.g. what are the policies used to plot Figure 2? Since policies have much more degrees of freedom than 2). Some of the numerical details in the text also does not seem too important and may be moved to the Appendix. I do like Figure 3 which shows very clearly the negative regret and the improvement in social welfare. 

questions: Please find some of my questions in the “weaknesses” part.

Additional questions:

How is Lemma 3.3 different from standard RVU bound (e.g. Proposition 2.1 & Corollary 3.1)? Skimming over the proof, it seems not a corollary of the RVU bound, but the proof steps are quite similar to that of RVU. Could the authors provide more intuition on this Lemma?

Last sentence in abstract, “our results suggest that cycling behavior of no-regret learning algorithms in games can be justified in terms of efficiency”--- is a bit unclear to me what it means? Does “efficiency” mean convergence to Strong CCE? Or better social welfare? Same goes with the statement on Line 54-55. Perhaps the authors could expand or modify these statements to clarify. 

limitations: /
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: Precisely as per the title, the paper shows that optimistic mirror descent (OMD) either converges to epsilon-approximate Nash equilibria, or the average emprical distribution of correlated play converges to an approximate-"strong-coarse correlated equilibrium (eps-SCC). Here an epsilon-strong-coarse correlated equilibrium is parameterized by epsilon, which dictates the extent to which players see a decrease in utility from unilaterally deviating from the correlated distribution of play (where deviations are such that a player uses a single fixed strategy rather than following the correlated distribution's signals). An interesting consequence of the result lies in the fact that for constant epsilon, an eps-SCC is in fact an exact coarse correlated equilibrium, hence if the dynamic has not reached an eps-approximate, it must forcibly give rise to an exact coarse correlated equilibrium. Finally, the authors provide an in-depth analysis/visualization of the performance of OMW on a specific 3x3 game instance, as well as general performance on several game benchmarks
strengths_and_weaknesses: Strengths: 
-The paper is very clear and results are well-motivated. A large part of the clarity stems from the fact that results are simple to state with interesting consequences. Furthermore, the overall intuition behind main proofs is well-explained in spite of technique details being in the appendix. Furthermore, the results will be of interest to the general community at Neurips.

Weaknesses:
-The paper could have had more exposition regarding the setting where players do not have access to the full representation of the bimatrix game but rather infer knowledge of the game through oracles.
-A minor point really, but it would be interesting to map the trajectory of play for the game instance in Section 4, especially for different intializations as mentioned at the end of 4.1. This would be especially useful to visualize for the main Lemmas of section 3.

Minor point:
In the appendix you mention that the state of the art for approximate eps-Nash being the Tsaknakis and Spirakis 0.3393 + delta result. Recently there has been a paper Deligkas et al. (https://arxiv.org/pdf/2204.11525.pdf) which improves this to 1/3 + delta

questions: In the experimental section you mention the possibility of different initializations for OGD. Are there games where different intializations to the same game can give rise to either of the guarantees of your result (eps-Nash or eps-strong CCE)? 

Supposing that players do not have access to the representation of the game and infer utilities from potentially noisy oracles, are results robust to such a setting? 

limitations: The main limitation that came to mind was the applicability of methods to games with more than 2 players, but this was adequately adressed in the paper as a potential thread of future research.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studied the dynamic behaviour of Optimistic Mirror Descent beyond two-player zero-sum games and consider two-player general sum games (bimatrix games). It shows that the dynamic either visits an $\epsilon$-NE or achieve a strong coarse correlated equilibria. 
In order to prove that, the authors observe the correlation in behaviour of two players 's strategies (Lemma 3.3 in Appendix) along with the existing regret bound of OMD (Proposition 2.1).
strengths_and_weaknesses: I really like the result of strong CCE and negative regret bound for both players (theorem 3.4) as they are new and fundamentally better compared to previous results. However, the condition in which the paper needs to achieve these results is hard to interpret. That is, the dynamic needs not to visit an $\epsilon$-Nash Equilibrium in the whole $T$ rounds. Hypothetically, OMD can have a chaotic behaviour while still visiting an $\epsilon$-Nash Equilibrium. This type of chaotic behaviour is known for many no-regret algorithms. Thus, the result of visiting $\epsilon$-Nash Equilibrium is less exciting and provides little information. Besides, visiting $\epsilon$-Nash Equilibrium and last round convergence are two very different, thus Theorem 1 does not imply the existing last round convergence result of OMD in zero-sum games. 

The paper will be much stronger if the results in Theorem 1 can implement last-round convergence to NE (not visiting) or strong CCE. A relevant result in zero-sum games about $\epsilon$-NE leading to last round convergence can be found in "Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization".
questions: I have a few questions to better understand the paper.

1. I am wondering whether the existence of a strong CCE is guaranteed in every bimatrix game?
2. In experiments, do the authors observe chaos behaviour of OMD? (e.g., the dynamic keeps approaching and moving away from a NE repeatedly)? 


limitations: there is no negative societal impact.
review_title: null

Meta-review: metareview: This paper proves a new phenomenon about the Optimistic Mirror Descent (OMD) algorithm in two-player general-sum matrix games (bimatrix games): The iterates either converge to an approximate Nash Equilibrium (NE), or converge to a Strong Coarse Correlated Equilibrium (CCE). This result links and improves over two existing understandings: (1) Convergence to NE is unlikely to be generally achievable by any efficient algorithm due to its PPAD-hardness; (2) Convergence to approximate CCE is achievable by any no-regret algorithm, but it is unclear whether such CCE is a strong CCE (in the present paper’s sense).

Given the phenomenon is not only new but also fundamental and important to the game theory community, I believe it is worth the attention of NeurIPS audience, and thus recommend acceptance.
confidence: Certain
Decision: Accept