Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proves a new assumption named unilateral concentration assumption as a necessary and sufficient dataset coverage condition for achieving optimal (NE) strategies in offline Markov game setting. A new Nash VI-based algorithm with pessimism is also proposed to achieve the minimax lower bound when the game is turn-based or under a stronger uniform concentration assumption. The results are novel and interesting with significant theoretical value.
strengths_and_weaknesses: The paper has a clear description, arguments and proofs about the proposed assumptions and theorems. The motivation is clear. A sharper Bernstein bound is applied with a reference advantage technique from previous paper to make PNVI match the lower bound.

For the argument that no weaker assumption than unilateral concentration can ensure any algorithm to learn NE is true under the hypothesis that this is claimed for all games in the game class. And the proof is conducted by constructing a hard instance. However, from a more practical view, an assumption for a given game would allow a weaker assumption, since most games in the game class are not the hard instance. To this end, it would be interesting to see some weaker assumptions allowing existing any algorithm to learn NE for a certain game that is not hard instance. After all, the data coverage in practice is very hard to guarantee.
questions: Is the sentence "A direct corollary is that uniform concentration (Assumption 2.1) is not sufficient for NE learning." in Sec. 3 a typo? Assumption 2.1 is single strategy concentration.

In page 8 l260, the 'ref' subscripts are missed for reference function.

For data splitting scheme, is it the same as random sample without replacement for each timestep with a fixed sample buffer size? How will sampling with replacement affect the final results?
limitations: As is also noted by the authors, the remaining factor $AB$ in the bound of PNVI is unclear to be removable or not.
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 studies the learning of two player zero-sum Markov games from data. The results introduce a new condition "Unilateral concentration" which informally requires data of plays when one of the player follows a NE equilibrium. The authors show that this is necessary and sufficient condition for learnability. The authors provide a provable bound poly time algorithm under the condition, one weaker bound using Hoeffding inequality and another using empirical Bernstein bounds.

strengths_and_weaknesses: The writing is clear and the results look solid to me. The proof sketches are helpful. I really did not find anything to complain other than few minor points that I state for a more rounded result. I must admit I am not very well versed in offline RL literature but the paper does a good job at comparing with related work.

It would have been good to have a few (even small) experiments - as the work is about learnability from data, it is surprising to not have any experiments.

Little better notation would make things easier to understand, especially for the variance of value function.

The second contribution in intro says "necessary and sufficient dataset coverage assumption for solving offline Markov games" it is important to be state zero-sum here - I know the paper title has zero-sum but this claim is broader.
questions: N/A
limitations: N/A
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 proposes the unilateral concentration condition which provides a necessary and sufficient dataset coverage to learn an NE using offline methods. The paper proposes an algorithm that converges to an NE under these conditions and is minimax optimal.
strengths_and_weaknesses: Offline learning in multiagent domains is an important worthwhile area of study. Two-player zero-sum is an acceptable area to start.

I found the first half of the paper well written. The second was difficult to follow (although my ignorance was a contributing a factor).

Soundness:

I am strongly convinced that the "unilateral concentration condition" claims are true. They seem intuitively true and the proofs are convincing.

I am also convinced of the impossibility results.

The claims around the optimal offline algorithm are plausible. While I did not spot any errors in the proofs, the techniques used in this section are beyond my area of expertise and unfortunately the time constraints on reviewing did not allow me to fully grasp this section as thoroughly as I would have liked. I hope the other reviewers can vouch for the soundness of this section.

Comments:

It may be worth noting that the uniform concentration condition, while trivial, is not that uncommon in practice. For example, data generated using an epsilon-greedy strategy, common in value based methods, or policy gradient methods which are necessarily stochastic would generate data that is uniform concentration.

Rating:

I will be willing to improve my rating if I felt more confident on the Section 4's soundness. I will remain open to other reviewers opinions on this matter and will be ready to improve my score with consensus. [Edit: consensus is that Section 4 is sound, improving my score from 4->6]

Minor comment:
* Line 25: “...two-players sequentially select actions…” - In Markov games players take actions simultaneously (over multiple time steps).
questions: Q1: Would "full concentration" be a better term to use? "Uniform" seems to imply some sort of uniformity over policy or state space, but really it means full-support. Although, I suppose this term has been inherited from the single-agent RL community?

limitations: The main limitations "uniform concentration" or "sequential Makov" were clearly stated. Scaling factors is also discussed.
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 paper studies the relevant offline MARL setting, which is relevant in practice, where only a small amount of data are given to the RL algorithm to infer a policy. The main contribution of the paper is to provide the necessary and sufficient assumption for learning a NE strategy in the offline Markov Game setting. This assumption is different from the one used in the single agent. In fact, in MDPs, the necessary assumption implies that one optimal policy is "covered" in the given dataset. However, in MGs, we need to see also the interaction between the NE policy and all the other agent's policies. 
After this result, the authors construct an algorithm based on pessimism that is provably efficient under this assumption. 
strengths_and_weaknesses: Strengths

1. The paper, as far as I know, is the first one that tracts the offline zero-sum Markov Game problem.

2. In the paper a necessary and sufficient condition for learning in offline zero-sum MG problems is given. The idea behind the proof is quite simple but, although the techniques used are not novel, the result is important for the ML community.

3. The authors provide an algorithm that is provably efficient (although it does not match the lower bound in general).

4. The paper is in general well-written and easy to follow. The authors spent space giving intuition about the different proof of the different theorems. I find this very helpful for a reader who does not want to read the full appendix.

Weaknesses

I think the paper has no important weaknesses. However, I list below the weaknesses.

1. In the paper the authors prove that the Unilateral concentration assumption is the sufficient and necessary assumption to learn in offline MGs problem. However, the paper will become stronger if the authors would give some results that bound the approximation of the NE that the proposed algorithm can achieve when this assumption does not hold and when only the Single strategy concentration assumption holds. Do the authors have an intuition about it?

2. Section 4.1 gives a first result when Hoeffding confidence intervals are used. However, the authors show that with Bernstein's confidence intervals they can improve the previous result. So, why do we need section 4.1? I suggest removing this section and putting in the main paper only Algorithm 2. Moreover, it is important that the reader does not have to go to the appendix to read the main algorithm.

3. From sections 4.1 and 4.2, it is not clear what are the main challenges the authors faced to translate an offline RL algorithm to MGs. Could the authors list these technical challenges in their answer?

questions: See Weaknesses.
limitations: The paper is theoretical, so the main limitations are due to the applicability of the proposed method in practice.

1. The state and action spaces are finite.
2. The algorithm needs to compute at each step a NE for each state and time-step.
3. The paper does not provide an experimental evaluation of the proposed algorithm. 

I think all of these limitations are reasonable since the main contribution of the paper is theoretical.
review_title: null

Meta-review: metareview: This paper is a clear accept, with very positive reviews overall. I trust that the reviewers will address the minor concerns raised by the reviewers in their final version.
confidence: Certain
Decision: Accept