Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied the sample complexity for learning the coarse correlated equilibrium (CCE) and correlated equilibrium (CE) of m-player general-sum Markov games (MG), as well as learning the Nash equilibrium (NE) of Markov potential games (MPG). For MG, the authors proposed an algorithm with sample complexity that grows polynomially in $\max_{i\leq m} A_i$ to achieve $\epsilon$-approximate CCE and CE. For MPG, the authors proposed an algorithm with sample complexity that grows polynomially in $\sum_{i\leq m} A_i$ to achieve $\epsilon$-approximate NE.
main_review: Strengths:
+ The sample complexity of learning Markov games is a timely and important topic in the areas of multi-agent reinforcement learning.
+ This paper provides new insights on what type of equilibria and/or structural assumptions on Markov games may admit sample-efficient learning polynomially in the size of the joint action spaces.

Weaknesses:
- Although the authors showed polynomial sample complexity for NE of Markov potential games, there appears to be a large gap to the lower bound.
- Some part of the paper is hard to follow and need better explanations.
summary_of_the_review: 1. This paper considered the sample complexity of learning multi-player Markov games with relaxed equilibrium notions (CE and CCE) and special structure (Markov potential games). The results in this paper are quite interesting. However, starting from Section 4, the presentation is a bit hard to follow. First, the algorithm for CCE, the first key equilibrium of MG, is relegated to the appendix. I went over the proof quickly and it appears a technique from [Tian et al. 2021] has been adopted to improve an H factor in [Bai et al. 2020]. However, [Bai et al. 2020] considered NE and it remains unclear what difference the properties of CCE make in this paper to allow the authors to achieve the claimed sample complexity.

2. The description of the CE algorithm is also unclear. It seems the FTRL technique is the key to the design of this algorithm. Is this technique brand new or adapted from some earlier work? Also, it might be better to define some jargons (e.g., sub-expert) for readers to fully understand the meaning of the algorithm. Also, it would be better to provide more intuition behind the algorithm design for CE. The authors mentioned that they adopted and modified the policy of [Bai et al. 2020]. It would be better if the authors could be more specific on what modifications are needed here.

3. Although the paper is mostly a theory paper, it would be nice if the authors could provide some experimental results to verify the sample complexity of the proposed algorithms.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies general sum episodic Markov Games. They provide an algorithm which is effectively V-learning with Follow the regularized leader subroutine (FTRL is hedge algorithm in their case). They prove convergence of their algorithm to $\epsilon$- CCE (coarse correlated equilibria) and $\epsilon$-CE equilibrium policies in $1/\epsilon^2$ with dependence on \max_{i} A_{i} (cardinality of action space of an individual rather than the whole action space). This happens due to ``independent updates" of the agents. Moreover for the case of potential markov games, they manage to show $1/\epsilon^3$ convergence to $\epsilon$-Nash pure Nash policies, improving Leonardos et al paper and solving an open question about convergence to deterministic policies. 
However, the agents do not update simultaneously (i.e., the updates are not concurrent!). They also provide lower bounds.
main_review: This is technical paper with very impressive results. I am really surprised with the running time of the provided algorithm for convergence of their algorithm to Nash equilibria in Markov potential games ($1/\epsilon^3$ improving the $1/\epsilon^6$). Note though that the updates are not simultaneous, in the sense that one agent updates at a time. Moreover, the analysis and lower bounds look quite nice. I feel this paper should get accepted!
summary_of_the_review: I feel the paper has quite nice technical contributions. The results are very interesting too.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the problem of finite horizon multi-agent general-sum Markov games.  The proposed algorithm CE-V-Learning achieves $\epsilon$-coarse correlated equilibirum (CCE) using $\tilde{O}(H^5S\max_{1\leq i \leq m}A_i/\epsilon^2)$  episodes, and $\epsilon$-correlated equilibrium (CE) using $\tilde{O}(H^6S\max_{1\leq i \leq m}A_i/\epsilon^2)$  episodes. The sample complexity is polynomial in $\max_{1\leq i\leq m}A_i$, while previous results had an exponential dependence on $m$ ($\Pi_{1\leq i\leq m}A_i$).
main_review: Strengths:
1. The sample complexity of  $\epsilon$-CE for general-sum games is significant and worth publishing. 
2. The proof of Theorem 6 is novel to me. In particular, the authors utilize the weighted swap regret lemma to derive the gap to the best CE agent. 

Weaknesses:
1. The result of $\epsilon$-CCE (Theorem 3) is based on previous results. It is not surprising given previous analysis about Nash-V learning (Tian 2021, et. al,)
2. As pointed by the authors, the dependences on $S$ and $H$ are not tight yet.
summary_of_the_review: Overall, the paper is well written and the theorectical results are worth publishing.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes algorithm for learning coarse correlated equilibrium (CCE) and correlated equilibrium (CE) of multi-player general-Sum Markov Games, the propose algorithm has polynomial dependence on the number of state and the horizons. The proposed algorithm builds upon the Nash V-learning of (Bai et al. 2020), and incorporate several new ideas.
main_review: Strength: The paper presents the first sample efficient algorithm for multi-player general sum Markov game and prove its convergence to CCE and CE. Though there are many *similar* types of paper in the field of theoretical reinforcement learning (i.e., a new setting with new sample efficient algorithm etc.), I found this one interesting. It solves an important question and the technique is non-trivial.



Minor issues:
(1) Proposition 1 and Theorem A.2 are results of Rubinstein et al. 2016. Though the authors make this clear enough, I suggest them make it cleaner (e.g. merge into one single proposition), since it is not the contribution of this paper, and I think it is only used to motivated this paper (hence no need to expand with one page.)

(2) There are some recent paper that accelerates the classic no regret algorithms that approach CE or CCE. Though it is not directly related, I suggest cite them as they are closely related to this paper.

[1] Syrgkanis, Vasilis, et al. "Fast Convergence of Regularized Learning in Games." Advances in Neural Information Processing Systems 28 (2015)

[2] Chen, Xi, and Binghui Peng. "Hedging in games: Faster convergence of external and swap regrets." Advances in Neural Information Processing Systems 33 (2020).
summary_of_the_review: Overall, I think it is interesting paper with solid contribution. I vote for acceptance.


------------------------------------------------------
Post rebuttal:

The author revised their paper and addressed some minor issues. My positive evaluation for the paper remains and I vote for acceptance.
review_title: null

Meta-review: This paper proposes algorithms for learning (coarse) correlated equilibrium in multi-agent general-sum Markov games, with improved sample complexities that are polynomial in the maximum size of the action sets of different players. This is a very solid work along the line of multi-agent reinforcement learning and there is unanimous support to accept this paper. Thus, I recommend acceptance.
Decision: Accept (Poster)