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: While there is an extensive literature on both multi-agent reinforcement learning (MARL) and offline RL separately, this work explores a setting that combines the two. In the MARL setting, the size of the joint action space grows exponentially with the number of agents, which is a key challenge in this subarea. This paper investigates how to tackle this problem and whether we can find a Nash equilibrium strategy in the offline MARL setting given unilateral coverage. 
Specifically, to construct a confidence interval for each state-action pair in the offline MARL setting, the authors proposes to estimate each strategy separately to circumvent the dependence of the joint action space which grows exponentially with the number of agents. Besides, based on this, the authors also develop two different algorithm frameworks under the tabular case for both the offline two-player zero-sum Markov games as well as the offline multi-player general-sum Markov games separately. 


strengths_and_weaknesses: This paper helps to improve our current understanding of algorithms for the offline MARL under the tabular setting. The major contribution is the proposed strategy-wise bonus, which firstly estimates the state value functions for a strategy and then add the bonus on them. However, if the strategies are complicated and therefore the class space not well structured, the calculation for state value functions for the strategy could be challenging. 

Given this, for the two-player zero-sum Markov games, the proposed framework utilizes a strategy-wise bonus as well as maximin-optimization-type algorithm. For the multi-player general-sum Markov game, as there is no saddle point structure, this paper proposes a surrogate function to minimize the performance gap, which, however, requires to enumerate the strategy class in the worst case and thus not computationally efficient. 

Another concern regarding the current version is that the data assumption adopted in this work (Assumption 1) assumes that the all the tuples in the logged dataset are independent, while this is not true in most real-world scenarios. As in many real-world applications, this assumption is very restrictive on the dataset and therefore usually does not hold. To derive practical algorithms based on the theoretical analysis and test the efficacy of the proposed methods in practice, the work should consider the impact of the violation of this assumption on the algorithm performance. 




questions: The analysis of this paper is based on a pre-specified policy class that contains the NE. The structure of the strategy class is a critical component in the proposed algorithm frameworks, which is especially true for the efficient computation of the surrogate function in the multi-player general-sum Markov game setting. Is a principled approach for structuring the strategy class? 
In addition, while the strategy-wise bonus can avoid the exponential dependence of the number of players, what the potential downsides or limitations of this approach compared to point-wise estimations? 
limitations: The authors has addressed some potential limitations.
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: In this paper, the authors study the offline multi-agent RL. They propose the strategy-wise concentration principle in contrast to the point-wise concentration principle in existing works. By the new concentration principle, they propose novel algorithms with strategy-wise bonuses for both zero-sum and general-sum games, which achieve better sample complexities than the existing works. The sample complexity of the new method does not scale with the size of the joint action space. Moreover, the proposed algorithms can take a pre-specified strategy class as input and output a strategy that is close to the best strategy in such a class. 
strengths_and_weaknesses: This paper proposes novel algorithms with the strategy-wise bonus, which leads to better sample complexities than the existing works. I think it is an important contribution to the theoretical analysis of the offline Markov games as the new sample complexity result does not scale with the size of the joint action space. In addition, the writing of this work is good in general and this paper is well structured. 

However, I was not able to find the discussion of the limitation in the paper although the author answered yes in the checklist. It would be much better if the authors can explicitly summarize the limitation of their work in the conclusion section or in the checklist.

Besides, is it possible to apply such a strategy-wise bonus to the online Markov game setting?
questions: I have a small question regarding this strategy-wise concentration method. Is it possible to apply such a strategy-wise bonus to the online Markov game setting?
limitations: I was not able to find the discussion of the limitation. It would be much better if the authors can explicitly summarize the limitation of their work in the conclusion section or in the checklist.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper considers offline multi-agent reinforcement learning.
strengths_and_weaknesses: The sample complexity for multi-agent general sum MDP is at least $N = \prod_{i=1}^m A_i$, where $A_i$'s denote the effective action space size for each agent (i.e., the number of actions obeying $\pi_i(a) > 0$).
Specifically, to ensure $\hat{C} < \infty$, one needs at least $N$ samples such that ${\hat{d}}h(s, a) > 0$ when $d_h^{\pi}(s, a) > 0$.
In addition, the assumption $C < \infty$ implies there are at least $N$ actions satisfying $d_h(s, a) > 0$, which leads to $1/p_{\min} \ge N$.
Hence, all results for the multi-agent case in Section 3.2 exhibit an exponential dependence on the number of agents, except the case that almost all agents will choose only one action.

On the other hand, it is well known to find the NE for multi-agent case is computationally hard. Then is it possible to compute CCE effectively for offline multi-agent RL?
questions: The sample complexity for multi-agent general sum MDP is exponential.
limitations: The sample complexity for multi-agent general sum MDP is exponential.
review_title: null

Meta-review: metareview: Reviewers appreciate the paper's contribution to a novel intersection of fields: offline and multi-agent RL. While feasibility of the results is limited to cases where prior knowledge allows strategy-wise decomposition, it is nonetheless an interesting step in this field. Reviewers are concerned that the above substantial limitation of the work has not been sufficiently discussed in the paper, and the authors are asked to clarify this aspect in a subsequent revision.
confidence: Certain
Decision: Accept