Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work leverages recent techniques for variance reduction in solving variational inequalities to obtain better bounds simultaneously in individual and sum of all players' regret for a general type of games.
More precisely, in their model, the authors endowed continuous functions as utility functions (not necessarily convex loss/concave gain) but the strategy of each player belongs to the simplex of a discrete action set, which is actually equivalent to normal form games. (Please correct me if I am wrong)
strength_and_weaknesses: Strengths:
1) Introduction of a new variance reduction method (LVE) resolving the curse of dimensionality of Carmon's et al 19 estimator
2) Leveraging SVRG techniques for VI and EG to describe an Optimistic Var Reduction Stochastic Mirror Descent method.
3) Better bounds for the regret for each player.
4) General Functions for simplex functions.

Please, I request from the authors for each of the weakness prescribed below to address it as a statement/question that necessates clarification
Weaknesses:
1) It was not clear to me what are the guarantees for the expected regret of the sum of all players and what is the statement for the pseudo-regret of the sum of all players. Can you please clarify
2) Obtaining convergence to a weak CCE via a pseudo-regret has been typically described in the literature? Is there any novelty in this point? I assume no, the ingenuity starts with the variance reduction methods, correct?
3) The authors proposed LVE instead of classical IWE with exploration term. Can the authors explain the details of their estimator. It would help if they provide some extended answer. how they derive this estimator. Is it something standard in the literature?
4)There is another point which was not clear, the regret statements are correct if all the players employ the same algorithm? Do we have the adversarial 1/\sqrt{T} case, if one of the players plays adversarially/stochastically?
clarity,_quality,_novelty_and_reproducibility: See below
summary_of_the_review: I had the chance to review the paper in this initial phase as emergency reviewer. 
Having said that, I am very open to the discussion to be sure that I have not misunderstood anything in the paper. I am very familiar with the work of AM21 and the connections of Regret and CCE. Someone could say that there is at a first glance a plug-and-play situation. However, it seems that a new MC estimator is also a necessary contribution to go from minimization of one agent (AM21) to our CCE (collaborative regret minimization). 

I have set a series of questions which if they will be addressed, I will be convinced that the paper deserves a clear accept. My positive score should be explained as my positive propensity for the papers' result.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies regret minimization in general-sum finite games. Such guarantees directly translate into the ones on convergence rate to approximated coarse correlated equilibrium. The main contribution is a stochastic version of the optimistic mirror descent algorithm that allows to achieve smaller regret (in expectation) within a given computational budget. In particular, a SVRG-like variance reduction mechanism along with a tailored sampling distribution are the key components that enable the improvement.
strength_and_weaknesses: **Strength**

The paper brings variance reduction into general-sum games and shows promising results in computing a CCE more efficiently. This seems to be a worthful attempt on the road to addressing more complicated games in a efficient manner by incorporating stochasticity.

The main algorithm construction and the design choices are clearly explained, modulo some minor points that may hinder the understanding (as listed below).

**Weakness**

I don't think there are any major flaws. Here are a few typos and minor remarks that I think should be addressed.
1. In the caption of Table 1, there are two phrases that begin with "For stochastic algorithms". The first one should be removed. Moreover, in the second one the first expected should be removed (i.e. the time complexity is the ~~expected~~ running time of achieving an expected approximation error).
2. The authors mention that weak $\epsilon$-CCE is related to social welfare without further explanation. Some clarification may be needed here. As far as I am aware, this does not apply to all the general-sum games but only to those that satisfy a certain 'smoothness' condition.
3. While the algorithm stated in the pseudo-code is correct, equation (1) seems to be wrong. In particular, the term $\sigma_i^k-\tau(\ldots)$ mixes quantities that live in the primal (players' strategies) and live in the dual (gradients).
4. At the beginning of Section 4: "where $a_{-i}\in\mathcal{A}_{-i}$ denote**s** a random variable ..." (add s)
5. LVE used in Algorithm 1 is not yet defined at this point.
6. It seems that $w^0_i$ and $\sigma^0_i$ used in the definition of $U_i$ are never defined (I suppose they are uniform distribution over the simplex).
7. On the third line of page 6, the phrase "sampled from $q_{-i}$" seems to be redundant.
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear with novel algorithms that can be interest to the community.
summary_of_the_review: Overall, I believe both the variance-reduction and the sampling algorithms are valuable (in terms of novelty, the former is a rather straightforward generalization from the two-player case while the later requires non-trivial modification). I thus recommend acceptance of the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors in this paper provide an algorithm which is a stochastic variant of OMD, that converges in the expected sense to a weak and strong $\varepsilon$-CCE. This is done by bounding the expected regret of the algorithm by, extending the
theoretical framework of analyzing regret bounds of stochastic OMD in (Alacaoglu and Malitsky 2021)  from two-player
zero-sum games to general sum games. In addition, they propose a low-variance Monte-Carlo estimator
for general sum games and the computational complexity of this estimator is only $O(A(N-1))$, where $A$ is the number of actions and $N$ is the number of players in the game, whereas previous works (Carmon et al. 2019) and (Alacaoglu and Malitsky 2021) analyze the stochastic variant of OMD for two player zero-sum games.

strength_and_weaknesses: Strengths:
This paper extends the idea of using stochastic methods for learning the CCE in normal form general games and show convergence in the expected sense to a weak $\varepsilon$-CCE and strong  $\varepsilon$-CCE This requires a new low-variance estimator that is different from (Alacaoglu and Malitsky 2021)  and (Carmon et al. 2019). This matches the time-complexity in (Alacaoglu and Malitsky 2021)  and (Carmon et al. 2019), when its a two player zero-sum game and when dealing with $\varepsilon$-Nash equilibrium. For general games the time complexity for convergence to a weak $\varepsilon$-CCE is arguably claimed to be faster than (Daskalakis, Fishelson and Golowich 21).

Weaknesses:
They mainly analyze the expected regret with a stochastic algorithm, whilst (Daskalakis, Fishelson and Golowich 21) analyze the actual regret, albeit they have a deterministic algorithm. In my view, the time to converge may not be directly comparable as it is currently done in Table 1. However, one can see this is an extension to papers like (Alacaoglu and Malitsky 2021) and (Carmon et al. 2019), which is focused on the general-sum game setting.

In addition, in the algorithm, all the players seem to have a shared random bit. Do the authors think it is possible to overcome this? 

One minor comment: In Line 6 of the Algorithm 1, it says compute $\hat{\sigma}^{k}_i$ such that... But nowhere, is the actual $\hat{\sigma}^{k}_i$ used and all the proofs mainly require the gradient, which is the term on the right hand side. I think it might be better to say that we compute the gradient of h, than the actual estimate $\hat{\sigma}^{k}_i$. 
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear, most of the ideas and algorithms are extensions of papers (Carmon et al. 2019) and (Alacaoglu and Malitsky 2021), but need to be adapted to this setting and introduces a new estimator for sampling and computing the loss vector.
summary_of_the_review: Overall, I think the paper tries to address an interesting direction to understand stochastic variants of OMD algorithms for general sum-games and its convergence to CCE's.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studied a notion of variance-reduced stochastic OMD for multi-agent general-sum standard games with an improved convergence speed over prior stochastic methods. The methods show improved convergence complexity over deterministic algorithms, especially when computing the full loss vector for each player is expensive. The method is a nontrivial generalization over the previous two-player zero-sum variance-reduced methods which uses Monte-Carlo estimator to deal with the challenge in high-variance of previous estimators due to the potentially large number of players.
strength_and_weaknesses: I think the paper studies a natural and important problem, the presentation is clear and the results look sound to me. I have greatly enjoyed reading this paper. I only have a few minor comments:

1) When presenting the table for comparison in time complexities, it may be helpful to highlight in which regime the first time in your complexity bound will directly dominate? And for what threshold of cost will your method offer improvement over prior ones? It may also be helpful to r remark that your method actually recovers two-player zero-sum case in prior work. Out of curiosity, I also wonder would a purely stochastic method (without variance reduction) work and be favorable here?

2) In section 5, it may be helpful (if you know about it) to remark a bit on the optimality of your constructed estimator, in terms of variance and computational complexity.

clarity,_quality,_novelty_and_reproducibility: Although the notation is heavy, I think this is almost unavoidable for studying multi-agent games. Besides that the paper is well-written and explains its motivation and makes clear comparison and literature review of prior work. 

While following the general framework of variance-reduced methods in prior work, the idea of constructing low-variance computationally-efficient gradient estimator for the OMD step is interesting and novel. I think this may have a positive impact for studying general-sum games more broadly.
summary_of_the_review: I think this is a technically nice paper that studies an important problem for stochastic OMD for multi-agent games. The authors clearly state their contribution and point out the future work in their main paper. Due to these reasons I recommend acceptance of the paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the convergence of the optimistic mirror descent (OMD) method to coarse correlated equilibrium in general finite games.
 
The main bottleneck targeted by the authors is that the calculation of the players' mixed payoff vectors can be very costly (exponential in the number of players), so they instead utilize only the sampled payoff vectors (i.e., those consisting of the payoffs resulting from the players' actual actions). This device reduces the per-iteration complexity of OMD dramatically but, on the negative side, it also introduces randomness, which can reduce the overall oracle complexity of the algorithm. The authors mitigate this via a suitable variance reduction mechanism which achieves a CCE convergence rate close to the deterministic case (but with a lighter per-iteration cost). [The authors also examine convergence to weak-CCE, but this result was deemed to be less significant in scope]

The committee felt unanimously that the paper cleared the acceptance bar, so an accept recommendation was reached early on.
justification_for_why_not_higher_score: The authors did not justify why no-regret algorithms are relevant for the *computation* of CCE: even though no-regret learning is the norm from an online learning perspective, it is not clear why this would be relevant from a computational standpoint when the game is fully known to the computational device(s).
justification_for_why_not_lower_score: The combination of variance reduction with mixed-strategy sampling is an idea that hasn't been sufficiently explored in the literature, and the paper provides an interesting study.
Decision: Accept: poster