Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper introduces an offline algorithm named SAFARI for solving Mean Field Games, using RKHS embedding of the infinite dimensional distribution of states. No experience are provided, but a bound on the efficiency of the method in terms of approximated value function is provided. This bound depends on the time horizon, the number of offline available trajectories as well as the effective dimension of the for parametrising the value function. It is valid whenever the set of available trajectories satisfies a natural weak coverage assumption. As a by-product, the authors also provide an online version of the algorithm.
main_review: Main comments:
1. The offline learning of Nash equilibria in Mean Field Games is a relevant and new topic, up to my knowledge. The distribution embedding using RKHS approach seems rigorously treated and well chosen for this setting. The literature review is complete and accurate and the paper is overall well written and easy to read. 
2. Can you justify why your method is indeed approximating the Nash of an MFG and not the solution of a corresponding Mean Field Control problem? As you mainly focus on the underpinned value function, this may need clarification. 
3. You are using a metric indicating how close the induced approximated value function is from the optimal one, how does it translates in terms of quality of Nash (with a metric such as exploitability for example) or approximation of the state distribution, which is also a commonly used metric for evaluating the quality of a MFG solution.
4. The class of MFG considered here is still unclear for me. The abstract mentions an episodic MFG while the main paper is less clear about that point. Which assumptions are present in your setting on the dynamics and reward structure, ensuring the existence and more importantly the uniqueness of the Nash? 
5. When using a Mean Field setting for solving MARL problems, one naturally  in an offline setting accumulates trajectories from the N-agents system,  which itself is an approximation of the MF limit. This probably goes beyond the scope of this paper but do these  additional errors fit in your approach? 
6. The theoretical results are interesting (I did not check everything) but could have been completed by experimental results, even in small dimensional settings. This would have been a good occasion to compare online and offline efficiency.

Typo: l 128 "an representative";  
limitations_and_societal_impact: I may have missed it but did not clearly identify where the limitations of the proposed approach are presented in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a method which uses Kernel mean embedding for mean-field based MARLwith  offline settings. Under a weak data coverage assumption, it shows a suboptimality bound in offline settings and extend the result to online settings. No experiments are included in this paper.
main_review: 1) I wonder if the weak data coverage assumption is too strict to implement, which means it needs to be tested in experiments. In addition, it would be better if there were comparisons with other algorithms in MARL.
2) section 5 spend a lot of time to describe various assumptions made, but there is no any experimental verifications.
3) in the online learning setting, we may have no information about the state of other agents. In such cases, what can we do?
4) for eq.5, there is an i.i.d assumption for each kernel mean embedding u, which could be problematic.


limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the Mean-Field Multi-Agent RL problem in the offline regime where pre-collected data is available. Under the assumption that data provides “sufficient” information regarding the optimal policy, the authors propose SAFARI, a pessimistic algorithm, and prove sample complexity guarantees to achieve a certain sub-optimality gap. The obtained data-dependent guarantees do not depend on the (large) number of agents and scale linearly with the effective dimension of the function class (used to parametrize the value function). Moreover, the authors propose another algorithm OMPPO for the online setting and obtain similar sublinear (in $N$; for some kernels) regret guarantees. 
main_review: Recently, both offline RL and mean-field games/RL have received a lot of attention and hence, I think that the paper is timely and considers an original idea of unifying these two problems. The need for offline RL in the mean-field MARL setting is clearly motivated in the paper. The obtained theoretical results are sound. The paper is also clearly written and the related work section nicely covers the existing literature. It would be great to see the performance of the proposed algorithms in simulations and experiments, but since this is a theoretical paper, I understand why this was not done.  

I like how the mean embeddings come into play when parametrizing the reward and transition (also, later on, when concentration results for empirical mean embedding are invoked in the analysis). By having a feature mapping that depends on $\mathcal{S} \times \mathcal{S} \times \mathcal{A}$, it is very convenient to invoke upper bounds on $d_{\text{eff}}$ in the final results. However, I feel that this parametrization also has its disadvantages,  as under such parametrization, the reward function (also transition) is only averaged with respect to $d_s$, i.e., the dependency on $d_s$ is quite simple and can be thought of as averaging over a single contextual parameter. This is reflected in the main bounds where $d$ corresponds to the dimension of the $S \times S \times A$ (thinking of it in this way, it appears that the problem/algorithm is not much different than the single-agent setup with a contextual variable (or two agent setting), which is also reflected in the bounds). Alternatively, one can consider having a kernel that is defined over $\mathcal{M}(S)$ instead of $S$ (i.e., $S \times \mathcal{M}(S) \times A$), and allow for rewards and transitions that depend on $d_s$ in more complex ways. I’m wondering if the authors can briefly comment on this.         


Can you comment on the assumption on line 238 that involves $v_h(x)$ and provide the intuition behind it? This assumption seems like an atypical one to me. How does it impact the analysis?   

It’d be great if the authors can comment on some of the implementation details of SAFARI. In particular, solving for the optimal policy $\hat{\pi_h}$ when the set of actions is infinite. Moreover, if I understood correctly (since it is not explicitly written in the algorithm) when searching for the optimal policy $\hat{\pi}_h$, one needs to solve the previous argmax problem for each $w \in \Omega$? How should this be done in practice given that $\Omega$ contains $\mathcal{M}(S)$ (i.e., space of probability distributions)?

In summary, I think this paper considers an interesting problem, provides further insights into the mean-field MARL, and contains some nice theoretical results/algorithms. 

Minor comments:

-- Line 15-16: “we also propose a variant of our SAFARI algorithm”; I would argue that this is a new algorithm rather than a variant of SAFARI.

-- Line 140: $d_{h+1,j}$; Should it be $s_{h+1,j}$ instead?

-- Line 77: “these methods focus -on- the online setting”

-- Line 304: “we denote $s_0$ as the representative agent” 

-- Line 196: “gram” -> “Gram”

-- Equation 5: $\alpha?$

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper (mainly) provides a pessimism based offline RL algorithm for MF-MARL. It extends existing literature by
1. Generalizing pessimism based offline RL algorithms from single agent to MF-MARL
2. Considering MF-MARL from an offline regime
It also extends existing literature on online MF-MARL by converting the pessimism penalty to a optimistic bonus and showed the sample efficiency of the algorithm under this regime.
main_review: - Originality: the key ideas behind SAFARI, as the authors mention in the paper, were first discussed in [1] (reference [70] in the paper itself) and the proof structure of theorem 1 largely follows the same paper. While MF-MARL is an interesting area and analyzing it from an offline perspective is indeed interesting, the proposed algorithm largely follows existing research on offline learning of linear MDPs. 

- Quality: theorems and claims are well supported by theory, which are meticulously proven in the appendix.

- Clarity: well written paper with thoroughly explained proofs and very few (if any) grammatical errors. Easy to follow and clearly explained.

- Significance: it should be noted that some benefits of the algorithm (e.g. no curse of multiple agents) are caused by the nature of the MF-MARL problem, rather than the proposed algorithm. Additionally, unlike the aforementioned [1], the paper does not demonstrate the sample efficiency of the algorithm in the offline regime (of course its efficiency in the online regime is well-demonstrated and should be somewhat indicative of the offline regime). However, combining MF-MARL with PEVI is an interesting idea and, especially in the context of social welfare optimization, offline RL algorithms are appreciated and necessary.

[1] Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL?525arXiv preprint arXiv:2012.15085, 2020.
limitations_and_societal_impact: Limitations: assumptions of the paper are clearly stated and the paper is entirely devoted to MF-MARL.

Societal impact: purely theoretical & no direct societal impact.
review_title: null

Meta-review: The reviewers raised some concerns with regard to lack of experimental results in this paper. Despite that they agree that the paper considers an interesting and relevant problem and it provides non-trivial theoretical results in terms of sample complexity of the proposed pessimistic method. Please provide the simple illustrative experiments in the final version.
Decision: Accept (Poster)