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 studies the problem of finding the Nash equilibria in two-player zero-sum Markov games with a generative model. The authors established a minimax optimal sample complexity in this setting.

strengths_and_weaknesses:  I think this problem is very interesting for the RL committee. But perhaps for too technical reasons, the paper is hard to follow. I hope the authors can make more comments to make the paper clearer. See the questions below for details.

questions: 1. The previous method (V-learning) only updates V functions and thus breaks the curse of multiagents. So I am curious about that why the proposed algorithm, which updates Q functions, can break the curse of multiagents.

2. Because the proof is too long, I did not read the proof in its entirety. Can the authors briefly describe the general idea of ​​the proof? I also encourage the authors to add a proof sketch. 

3. I hope the authors make more comments on why this method cannot be applied to the online setting.

I will consider increasing the score if the authors can address the above concerns.
limitations: Yes
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: This work focuses on closing the sample complexity gap in learning two-player zero-sum Markov games. With previous results suffering either the curse of multi-agent or a loose horizon-dependency, this work breaks both barriers simultaneously in the setting of a generative model and approaches the optimal rate up to logarithmic factors. The algorithm design benefits from two core ideas: the optimism to tackle the uncertainty of the environment and the adversarial learning (FTRL in particular) to overcome the non-stationary environment from each player's perspective. The core technique that contributes to the tight sample complexity is the data-driven Bernstein-style bonus.
strengths_and_weaknesses: - (S) While many advances in learning in MGs have been made in recent years, how to achieve the optimal sample complexity remains open even in the "simplest" case of two-player zero-sum games and generative models, as considered in this work. The progress of this work largely contributes to a deeper understanding of this problem and should inspire future works.
- (S) The techniques utilized in this work nicely improve previous ones. While optimism and adversarial learning in MG have been investigated in MGs [27], this work nicely spots that the looseness of the previous result is due to the failure of considering variance-type bounds. While similar ideas of using Bernstein-type bounds to sharpen the horizon-dependency are philosophically well-recognized in RL, this work still skilfully implements it in the context of MGs and combines it with adversarial learning.
- (S) While this work is heavy in theory, the major design intuitions are given and the results are illustrated clearly, which is a joy to read.
- (S) The tools developed in this work, especially the variance-type bound for FTRL should be of independent usage and may benefit other studies beyond MGs.
- (W) If have to say something about weakness, the design idea of this work is similar to that of [27] although this work successfully incorporated the variance-type analysis (which is lacking in [27]). Also, the assumption of the generative model is somewhat limited. However, I still believe that compared with [27], sufficient contributions are made even assuming the generative model.
questions: **I am overall very satisfied with this work. The following questions are more from my own curiosities.**
- [27] mentions that its result is loose due to two reasons (see the illustration below their Thm 4). One reason is the incremental update and use of the learning rate therein. Another reason is that [27] did not have a variance-aware analysis. The improvement over the second point is clear in this work. I am wondering how this work addresses the first point. Especially, is the generative model alleviate the first point directly? Or the learning rate chosen in this work (different from which in [27]) plays a critical role?
- Regarding the variance-aware design, I noticed that it is considered in both the confidence-bound design and the learning rates for FTRL (i.e., $\eta$). I am wondering about the reason for each individual consideration. Hopefully, the authors can give some intuitive explanations.
- Additionally, for the confidence bound, the update of the Q value and the V value uses two different confidence bounds. They share similar formats but it will still be helpful if the authors can illustrate their relationships. 
- Another question regarding this work and [27] is that the output policy in [27] is typically non-Markovian, I am wondering whether the authors can give some illustration on why this work can output a Markov policy. I did not find much emphasis on this point and wonder whether there is any particular reason that outputting a Markov policy is straightforward in this work.
limitations: Yes, the authors have addressed the limitation of this work and there is no major negative societal impact given its theoretical nature.
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: This paper provides a new algorithm for learning a Nash equilibrium in a zero-sum Markov game and proves that the sample complexity is much tighter than in the previous works, in a sense that the bound is nearly optimal.
strengths_and_weaknesses: Strengths:
1. The algorithm and the theoretical results seem novel and appealing. As stated in the paper, it is proven that the proposed algorithm overcomes (i) the curse of multiple agents, and (ii) the curse of horizon. The results seem sound and significant.
2. The paper is well structured and well written. The notation is clear and easy to follow.

Weaknesses:
1.  The "main results" section is short, and the theoretical results are not explained clearly. How do we get to Theorem 1? Since this is a theoretical paper, I think an outline of the proof is needed here to help the readers to get the idea quickly.
2. Eq. (27) makes sense to me. However, it is a bit risky to say that the bound proven in the paper is "nearly improvable" without proof.
questions: None.
limitations: The limitations have been stated clearly in the paper.
review_title: null

Meta-review: metareview: This paper received uniformly positive reviews on a topic of relevance to the theory-ML community where understanding how to achieve tight sample complexity results in Markov Games has been of significant interest in recent years. 
confidence: Certain
Decision: Accept