Venue: NeurIPS 2022 Conference

Reviews:

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 proposes Clairvoyant Multiplicative Weight Update (CMWU), a simple alternative of Optimistic MWU that can compute CCE of a general-sum game in log(t)/t rates in a uncoupled manner. The idea of the algorithm is to compute the fixed point of the exponential weight update, similar to the idea of proximal-point method. It can be shown that if all players follow this dynamics, the time average of their iterates will be an approximate CCE, with the accuracy of approximation dependent on the step size. 

Due to the intractability of computing the fixed point, the authors proposes to approximate it when the step size is smaller than a constant, exploiting the fact that when the step size is sufficiently small, the exponential weight update is a contraction mapping. When every player synchronizes to find the fixed point, they can find the fixed point up to accuracy of 1/t in t steps. The procedure can be decoupled across all players and is very efficient. 

Overall, the algorithm can find CCE in a rate of $n\log(m)\log(t)/t$, where $n$ is the number of players and $m$ is the number of pure strategies (for a single player).  
strengths_and_weaknesses: Strength: 
- The proposed algorithm has simple implementation and simple analysis, and achieves the state-of-the-art rate of computing CCE in a uncoupled manner. 

Weakness: 
- The proposed algorithm requires stronger coordination among players compared to OMWU, which might sacrifice some merits of OMWU. For example, the uncoupled version of CMWU requires a synchronization among players in updating z, what if the synchronization fails or the periods used by players differ? 
- Similarly, OMWU has the benefit of being a no-regret algorithm against any adversary (if the learning rate is adaptive). Can CMWU also be a no-regret algorithm? 
questions: - Please answer the questions asked in the "weakness" part above. 
- Corollary 3.3: the $\eta$ should be in the denominator? 
- Is there a computational complexity lower bound (might be restricted to some class of algorithms) for the considered setting? 

limitations: There is little/no limitations or potential negative societal impact.
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 considers using no-regret algorithms for solving general games. Their proposed algorithm for the players, named CMWU, achieves an O(nVlogmlogT) regret, which improves the previous best results by an O(log^3 T) factor. The main idea is to use future decision to update the current one in MWU.
strengths_and_weaknesses: Strengths:

1. The proposed algorithm improves the previous state of the art algorithm by an O(log^3 T) factor. 

2. The main idea of the algorithm, i.e., using the future to update the current decision in MWU, to my knowledge is novel. I think the main obstacle here is the computational issue, and it seems that the authors have successfully overcome it under certain assumptions. However, I have some concerns about this point, which is listed in the next part. 



Weakness: 

1. My main concern is about the computational complexity of the proposed algorithm (I realized that the authors say in Line 75 that the update only “requiring a single step of MWU”, so I may have some misunderstanding, and I hope the authors could help me clear the concerns): 

1) in general, as the authors pointed out, the CMWU update (Line 173) is very difficult to compute. 

2)  Under certain assumptions, the authors show that “the update can be computed linear fast via a contraction map”. However, I have two questions about this conclusion: 
a) for the linear convergence rate, do the authors mean one can get a $\epsilon$-approximate solution with O(log (1/epsilon)) number of iterations? 
B) If so, will the error  accumulate at each round? And will the real number of iterations become something like TlogT instead of T? 

3) I also have a question about the assumption related to the maximum eta. I was wondering if the authors could be more specific about how to set eta to get the regret bound in Table 1? 

2. Apart from the improvement on regret, another contribution is the more general deduction rule. Can the authors be more clear about the importance of this contribution? Why is it a significant result?

3. I find the paper is not easy to read, especially to people who are not familiar with the specific area. For example, in the introduction, the authors leave many terminologies unexpaterned, such as mixed strightey and sparse sub-trajectory. 
questions: The main questions are listed above.

Putting the game framework aside, I am a bit curious about this problem: can CMWU be applied to a learning with expert problem? If so, what is the regret? And what’s the relationship to OMWU?
limitations: I have some questions about the computational complexity, which are listed above.
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: The paper introduces an uncoupled learning algorithm with efficient strategy updates, coined Clairvoyant Multiplicative Weights Update (CMWU). The algorithm produces a sequence of strategies, a subsequence of which minimizes regret.

The main idea behind CMWU stems from the known fact that by having a perfect (clairvoyant) prediction of the next loss vector in optimistic MWU, the regret of optimistic MWU grows constant. The contribution of the paper is in showing that such clairvoyant predictions can be obtained efficiently through fixed-point iterations of a contraction, and show that such fixed-point iterations can be interpreted as additional (but ignored in the computation of regret) iterates of a learning algorithm.
strengths_and_weaknesses: While the paper relies on a simple and well-known observation---namely that the observation that clairvoyance leads to constant regret in MWU, which can be already found in these notes from 2008 (Section 2.3, [1])---and the proof of the contraction is incredibly elementary, I think the final result is noteworthy and deserves recognition. Indeed, I think that in this case the simplicity of the argument is a strength and not a weakness, and it is perhaps even surprising that this result had not been noted before.

I find the biggest limitation of the work to be the fact that the iterates produced by the proposed algorithm, CMWU, do not minimize regret. Rather, only a specific (log T)-spaced subsequence of the iterates do. It is not known whether the full sequence of iterates (and not only the specific subsequence) is regret minimizing. For that reason, I find calling CMWU an "algorithm for regret minimization" (abstract, line 2) misleading, especially given that the paper insists on the algorithm being uncoupled. I would encourage the authors to reword the abstract to avoid the confusion. 

Continuing on the previous points, the authors call the fact that the dynamics only minimize regret when restricting to a specific (log T)-spaced subsequence of the iterates a "critical conceptual innovation" (line 255-256). On line 59-60, the authors try to back up the innovation by saying that "it is not clear why time-average behavior should be the only way to deduce a CCE". I only partially agree with this. I certainly agree that if the goal is CCE computation, then an alternative deduction rule that preserves uncoupledness and efficient strategy updates remains interesting (and in fact many alternative deduction rules have been tried in the literature, for instance alternative averaging of iterates are very popular in the extensive-form game community). Yet, assuming that dynamics are not run with the objective of computing a CCE, and rather only to guarantee some form of rational (i.e., regret-minimizing in this context) play/learning between the agents, the fact that the iterates as a whole do not minimize regret is clearly a downside. The paper seems to dance between these two intertwined but different goals---computing a CCE and defining regret-minimizing online play/learning---and so a clear discussion of the limitations of the alternative deduction rule (good for one scenario but not the other) gets missed. I strongly encourage the authors to elaborate on the downsides of the lack of the regret minimization property (at least in the usual sense) of their algorithm, and what problems remain open.


[1] http://www.mit.edu/~rakhlin/papers/online_learning.pdf
questions: Please feel free to push back on my analysis of weaknesses above, I'm certainly open to change my mind.

Beyond that, I have a few questions:
1. Other works in this space (e.g., the recent paper by Daskalakis et al. on near-optimal regret in games) stressed how the accelerated regret bounds can fall back to the usual, non accelerated, $O(\sqrt T)$ regret dynamics when facing adversarial opponents. Is the same possible for CMWU?

2. Can CMWU be run as an anytime algorithm, that is, without knowing the value of $T$ a priori? If so, I find that that would be an important addition to the paper.
limitations: Please see Strengths and Weaknesses above for a description of what limitations where not addressed adequately by the authors.
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 authors propose a Clairvoyant Multiplicative Weights Updates (CMWU) for learning normal-form games. The new method achieves the optimal regret with constant stepsize. The authors also provide an efficient decentralized implementation of the proposed method, which enjoys the optimal regret for learning a CCE.
strengths_and_weaknesses: ## Originality

- The proposed CMWU is new and it improves existing regret bounds that have been compared. 

- The proof has several novel ingredients, e.g., contraction property of MWU mapping. 

- An uncoupled implementation of CMWU is a new decentralized multi-agent online learning algorithm.  

## Quality & Clarity

- The paper is well written and all claims are justified via proofs. 

## Significance

- The proposed CMWU takes a nice decentralized online implementation which is important for online multi-agent game learning.

- The defined regret bound measures performance via sparse part of history instead of time average of history. This goes beyond the standard metric in learning games. 

- The established regret bound improves the dependence on $T$ compared with the existing methods. This is an important advance in learning normal form games. 

questions: - Why are regret bounds in Table 1 called **Rate of Convergence**? 

- References about Theorem 2.4 would be helpful.

- Do you have experimental justification of improvements shown in Table 1? It would be very helpful.

- Do you assume that the number of players is fixed? Is it restrictive? 

- A typo in line 159: implementatio
limitations: Yes.
review_title: null

Meta-review: metareview: This paper proposes a new uncoupled method for computing CCE of a general-sum normal-form game with a SOTA rate.
As the reviewers point out, the biggest issue of this work is that the proposed algorithm is not no-regret considering all iterates. We strongly encourage the authors to make this clearer and avoid making misleading/confusing statements. Reviewer k1YV's concern on the "synchronization" requirement is also a very valid point, and the authors' response did not really address this concern. We encourage the authors to also make this clearer in the revision.
confidence: Less certain
Decision: Accept