Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper deals with a class of cooperative MARL problems with permutation invariance. It first shows that, for such problems, there exists an optimal policy that is permutation invariant, and the value function can be characterized as a function of the local state of one agent and the empirical state distribution over the rest of agents. Based on these observations, the authors introduce the mean-field MDP as the limit of the MARL problem with infinitely many homogeneous agents and design a mean-field proximal policy optimization (MF-PPO) algorithm to solve it. It shows with permutation invariance, the search space of the actor/critic network polynomially depends on the number of agents $N$ and establishes the global convergence of MF-PPO. Some numerical results show better performance compared with some existing algorithms.
main_review: Multi-agent cooperative systems are important research topics and using mean-field approximation to design algorithms is an interesting research direction. This paper gives some theoretical analysis on the motivation of the mean-field approximation and proposes algorithm MF-PPO to solve mean-field MDP, which is new in related fields. However, there are also some major issues, as listed below.
1. This paper provide some analysis on multi-agent cooperative systems with permutation invariance property, to motivate mean-field MDP. However, I have some concerns with respect to the motivation. 
    * In proposition 2.2, function $g_\nu$ should have some conditions: for example, it is possible that it depends on the number of agents $N$ in the system (when $r=\sum_{i=1}^N s_i$, it is permutation invariant and $g_\nu$ depends on $N$). In such cases, it’s not clear to see why the corresponding mean-field MDP exists when $N$ goes to infinity. There seems to be some additional assumptions needed other than homogeneity and permutation invariance. Besides, the proof of Proposition 2.2 is hard to follow. The authors should make it clearer why Theorem 11 in [Bloem-Reddy and Teh (2019)] can be adapted. 
    * In the finite-agent MDP, the policies considered are randomized policies (which I infer from the notation $a_t\sim \nu(s_t)$). However in the mean-field MDP, the policy for each agent $\bar a$ becomes deterministic (as it says $\bar a:\mathcal{S}\rightarrow\mathcal{A}$). The authors should give some explanations here why the space of the agent’s policies changes. In sum, it would be nice if the authors can provide more explanations on why Definition 2.1 can be viewed as the corresponding limit model, given that they claim “the mean-field MDP has a step-to-step correspondence with the finite-agent MDP with homogeneous agents”.
2. Proposition 3.1 seems standard for any symmetric game. See for example [A]. This does not rely on mean-field approximation or the actor critic framework. The benefit of using mean-field approximation is not clear, and the authors should elaborate more on that. Especially the permutation invariance idea for MARL has already been explored in [Liu et al. (2019b)].
3. Given that the authors already cited [Gu et al. (2019), Gu et al. (2020)] and they also proposed mean-field MARL algorithms, it is not clear why they are not compared in the numerical experiments. 
4. Some notations in the paper are not rigorous. For example, the space of $\nu$ and $\pi$ are not specified. On top of page 5, $\sigma_k=\nu_k\pi_k$ seems problematic. 

[A] Computing equilibria in multi-player games. Christos H. Papadimitriou and Tim Roughgarden.
summary_of_the_review: This paper proposes to combine mean-field approximation with the permutation invariance idea in [Liu et al., 2019b], which is an interesting direction. Both theoretical analyses and numerical experiments are provided. However, the theoretical justification of the mean-field approximation is very unclear. Also, some closely related algorithms are not compared.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors present a principled method of solving problems with multiple homogenous agents. 
main_review: I am shared about this paper. It seems to be a valid theoretical contribution, but since it is beyond the scope of my expertise, it is hard for me to fully validate/appreciate. As to the experimental part, I find it to be relatively weak, which might still be ok, if the theoretical part is strong enough. 

I raise some concrete questions, which hopefully will clarify some of my doubts during the rebuttal.

1. Why are energy models used for policy training, is it matter of convenience, or is there a deeper reason?

2. Why there is restriction to $B(\theta_0, R_\theta)$? Shouldn't it be $B(\theta_{k-1}, R_\theta)$ in the equation (3.1).

3. Why the mean-field MDP uses $(s, \text{d}_\mathcal{S})$. It should be enough to just take  $\text{d}_\mathcal{S}$ (i.e. none of the agents is special)? [The same question applies to Prop 2.2].

4. Is the proof a novel one?

5. What is the exact experimental setup:

6. 1. What are the details about the environments used? What are the interactions between agents? How intensive are they?
   2. What is the algorithmic setup? I am confused as it suggests using DDPG, which is somewhat detached from the theoretical analysis. 
summary_of_the_review: As for the moment, I find the contribution below the standard of a top-tier conference like ICLR. It is not clear what the exact theoretical contributions are and how they are related to the experimental part.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a mean-field proximal policy optimization algorithm (MF-PPO) for MARL with a large population of homogenuous agents. The sample complexity is derived based on a two-layer neural network approximation and the proposed algorithm is tested in several detailed experiments.
main_review: The paper is nicely written and easy to follow. I like very much the way that the authors motivate and demonstrate how the permutation invariance property helps to reduce the complexity of the MARL problem with homogeneous agents.

The techniques used to show the sample complexity is based on (1) the neural policy gradient paper (Wang, Cai, Yang, and Wang, 2019) for the single-agent case and (2) the law of large number used in the mean-field approximation. I am confident that the main results are correct.

I have several minor suggestions that may help to further improve the exposition:

(1) The paragraph starting with "To scale MARL algorithms ..." on page 2: The authors gave an overview on mean-field MARL in this paragraph. I view mean-field game (MFG) and mean-field control (MFC) are two different sets of problems with the MFG solving for Nash equilibria and the MFC solving for social optimal solutions. The authors did not distinguish these two when providing the overview. I suggest the authors divide the literature review into two parts and treat the references for MFG and MFC separately. A reference that might be relevant to include: Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach (Gu et al., 2021)

(2) Permutation mapping $\kappa(\cdot)$: I understand what the authors mean by "permutation mapping" and it can be any function of the empirical distribution (e.g, first moment and second moment). But I suggest the authors provide a more rigorous (mathematical) definition of permutation mapping.

(3) Factorization $\nu(a|s)$ on page 3: The authors may add more discussions on $o_i$ which is the informaton observed by agent $i$.

(4) Generality of the definition for mean-field MDP: Is it possible to include $(a,d_{\mathcal{A}})$ in the formulation (reward and transition) instead of only the average action ($\bar{a}$)?

(5) Theorem 4.1: The authors may add a discussion on the comparison to the single-agent paper (Wang, Cai, Yang, and Wang, 2019) and highlight the additional technical differences (i.e., handling the mean-field part). How does the term $M$ depend on N?

(6) Lemma 4.1: The authors may add a discussion on why $\sqrt{1/N}$ appears in the upper bound (I believe it's from the law of large numbers).


summary_of_the_review: The submission is well written and provides a good contribution to the MARL literature.
review_title: null

Meta-review: This paper proposes a new multi-agent RL algorithm, based on the PPO algorithm, that uses a mean-field approximation, which results in a a permutation- invariant actor-critic neural architecture. The paper includes a detailed theoretical analysis that shows that the algorithm finds a globally optimal policy at a sub-linear rate of convergence, and that its sample complexity is independent of the number of agents. The paper include some experiments that validate the proposed algorithm.

The reviews of this paper are mixed. Most of the reviewers appreciate the theoretical analysis, but one reviewer does not find the theoretical justification of the mean-field approximation clear. The reviewer also points out to the absence of comparisons to relevant competing algorithms. These concerns are addressed by the authors in their rebuttal. A key issue with this work is the weakness of the empirical evaluation. The proposed method is tested on only two simple tasks, and the results on the second task do not show a considerable advantage of the proposed algorithm. This paper can be strengthened by adding experiments that clearly indicate the advantage of the proposed technique.
Decision: Reject