A Principled Permutation Invariant Approach to Mean-Field Multi-Agent Reinforcement Learning
Authors: Yan Li
Lingxiao Wang
Jiachen Yang
Ethan Wang
Zhaoran Wang
Tuo Zhao
Hongyuan Zha
Venue: ICLR 2022 Submitted (2022)

Abstract: Multi-agent reinforcement learning (MARL) becomes more challenging in the presence of more agents, as the capacity of the joint state and action spaces grows exponentially in the number of agents. To address such a challenge of scale, we identify a class of cooperative MARL problems with permutation invariance, and formulate it as mean-field Markov decision processes (MDP). To exploit the permutation invariance therein, we propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation- invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence. Moreover, its sample complexity is independent of the number of agents. We validate the theoretical advantages of MF-PPO with numerical experiments in the multi-agent particle environment (MPE). In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors with a smaller number of model parameters, which is the key to its generalization performance.


Under review as a conference paper at ICLR 2022
A PRINCIPLED PERMUTATION INVARIANT APPROACH TO MEAN-FIELD MULTI-AGENT REINNTRCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Multi-agent reinforcement learning (MARL.) becomes more challenging in the presence more agents, as the capacity of the joint state and action spaces grows exponentially in the number of agents. To address such challenge of scale, we identify a class of cooperative MARL problems with permutation invariance, and formulate it mean-field Markov decision processes (MDP). To exploit the permutation invariance therein, we propose the mean-fiele proximal policy optimization (MF-PPO) algorithm, the core of which is a permutation- invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy sublinear rate of convergence. Moreover, its sample complexity is independent of the number of agents. We validate the theoretical advantages MF-PPO with numerical experiments in the multi-agent particle environment (MPE). In particular, we show that the inductive bias introduced by the permutation- invariant neural architecture enables MF-PPO to outperform existing competitors with a smaller number of model parameters, which is the key to its generalization performance.
INTRODUCTION
Multi-Agent Reinforcement Learning (Littman 1994, Zhang et al. 2019) generalizes Reinforcement Learning (Sutton and Barto 2018) to address the sequential decision-making problem of multiple agents maximizing their individual long term rewards while interacting with each other in a common environment. With breakthroughs in deep learning, MARL algorithms equipped with deep neural net- works have seen significant empirical successes in various domains, including simulated autonomous driving (Shalev-Shwartz et al. 2016), multi-agent robotic control (Matarić 1997. Kober et al. 2013). and E-sports (Vinyals et al.) 2019).
Despite tremendous successes, MARL is notoriously hard to scale to the many-agent setting, as the size of the state-action space grows exponentially with respect to the number of agents. This phenomenon recently described as the curse many agents (Menda et al., 2018). To tackle this challenge, we focus on cooperative MARL, where agents work together to maximize their team reward (Panait and Luke, 2005). We identify and exploit a key property of cooperative MARI with homogeneous agents, namely the invariance with respect to the permutation of agents. Such permutation invariance can be found in many real-world scenarios with homogeneous agents, such as distributed control of multiple autonomous vehicles and team sports (Cao al. [013 Kalyanakrishnan et al. 2006), but also in scenarios with heterogeneous agent groups, where invariance holds within each group (Liu et al., 2019b). More importantly, we find that permutation invariance has significant practical implications, as the optimal value functions remain invariant when permuting the joint state-action pairs. Such an observation strongly advocates permutation invariant design for learning, which helps reduce the effective search space of the policy/value functions from exponential dependence on the number of agents to polynomial dependence.
Several empirical methods have been proposed to incorporate permutation invariance into solving MARL problems. Liu et al. (2019b) implement a permutation invariant critic based on Graph Convolu- tional Network (GCN) KKipf and Welling 2017). Sunchag et al. (2017) propose value decomposition, which together with parameter sharing, leads to a joint critic network that is permutation invariant agents. While these methods are based on heuristics, we are the first to provide theoretical principles for introducing permutation invariance as an inductive bias for learning value functions and policies in homogeneous systems. In addition, adopt the DeepSet (Zaheer al. 2017)

---

Under review as a conference paper at ICLR 2022
architecture, which is well suited for handling homogeneity of agents, with much simpler operations to induce permutation invariance and greater parameter efficiency.
To scale MARL algorithms in the presence of a large number, even infinitely many, agents, mean-field approximation has been explored to directly model the population behavior of the agents, Mean-fiel field game considers large populations of rational agents that play a noncooperative game, Yang et al. (2017) consider a mean-field game with deterministic linear state transitions, and show that it can be reformulated as a mean-fiel feeld MDP, where the mean-field state lies in dinee-dimensional probability simplex. Yang et al. (2018) take mean-field approximation over actions, such that the interaction for any given agent and the population is approximated by the interaction between the agent's 's action and the averaged actions of its neighboring agents. However, the motivation for averaging over local actions remains unclear, and it generally requires a sparse graph over agents. In practice, properly identifying such structure also demands extensive prior knowledge. Mean-field control instead considers a central controller who aims to compute strategy to optimize the average payoff across the population. Carmona et al. (2019) motivate a mean-field MDP from the perspective of mean-fiell field control. The mean-field field state therein lies in probability simplex and is thus continuous in nature. To enable the ensuing Q-learning algorithm, discretization of the joint state-action space is necessary. In addition, the dynamic programming principles of such mean-field control problem has been studied in (Gu et al, 2019). Gu et al. (2020) also propose a Q-learning type algorithm, where the state-action space is first discretized into an epsilon-net. The kernel regression operator is used to construct an estimate of the unknown Q-function from samples. Gu et al. (202T) propose a localized training, decentralized execution framework by locally grouping homogenous agents using their states. Wang eet al. (020)) motivate a mean-field MDP from permutation invariance, but assume a central controller coordinating the actions of all the agents, and hence is restricted to handling the curse of many agents from the exponential blowup of the joint state space. Our formulation of mean-field approximation allows agents to make their own local actions without resorting to centralized controller.
We propose mean- mean-field -felddfiddddd Markov decision process motivated from the permutation invariance structure of cooperative MARL, which can be viewed a natural limit of finite-agent MDP by taking the number of agents to infinity. Such mean-field MDP generalizes traditional MDP, with each state representing a distribution over the state space of a single agent. The mean-field MDP provides us a tractable formulation to model MDP with many agents, including an infinite number of agents. We further propose the Mean-Field Proximal Policy Optimization (MF-PPO) algorithm, at the core of which is a pair of permutation invariant actor and critic neural networks. These networks are implemented based on DeepSet (Zaheer et al. 2017), which uses convolutional type operations to induce permutation invariance over the set of inputs. We show that with sufficiently many agents, MF-PPO converges to the optimal policy of the mean-field MDP with a sublinear sample complexity independent of the number of agents. To support our theory, we conduct numerical experiments on the benchmark multi-agent particle environment (MPE) and show that our proposed method requires smaller number of model parameters and attains better performance than multiple baselines.
Notations. W denote P(X) as the set of distribution on set X. &g denotes the Dirac measure i.i.d. supported at v. For s = ($1,-. : 8N), we use ~ p to denote that each 8; independently sampled from distribution p. For f X + IR and a distribution π E PPX)., we write (J,z) = =aa=z We write [m] in short for [1...., m)) and As for the standard probability simplex in Rdd.
2 PROBLEM SETUP
We focus on studying multi-agent systems with cooperative, homogeneous agents, where the agents within the system are of similar nature and hence cannot be distinguished from each other. Specifically, we consider a discrete time control problem with N agents, formulated as Markov decision process (SN, .AN, IP,)). r). We define the joint state space S.N to be the Cartesian product of the finite state space S for each agent, and similarly define the joint action space A The homogeneous nature of the system is reflected in the transition kernel TP and the shared reward r, which satisfies:
(2.1) for all (st, ar) E SN x A and the permutation mapping x(-) E SN. where Sy is the set of all one-to-one mapping from [N] to itself. In other words, it is the configuration, rather than individual identities, that affects the team reward, and the transition to the next configuration solely depends on the current configuration. See Figure for detailed illustration. Such permutation invariance finds applications in many real-won wollw scenarios, including distributed control of autonomous vehicles, and social economic systems (Zheng et al. 2020 Cao et al. 2013 Kalyanakrishnan et al. (006).
r(Se, ag) = r (*<()),, k(a))), P(( [St, at) = F (x(()=)))<<(s)) ((a)))()))))))))))
2

---

Under review as a conference paper at ICLR 2022
Our goal is to find the optimal policy v, where v(s) E AnNi for all s E SN and maximize the expected discounted reward (*(s) = (1 - 7) (2 7'r(s;, ] so =s at as))(s;), vt20). Our first result shows that learning with permutation invariance advocates invariant network design.
Proposition 2.1. For cooperative MARL satisfying I.I.. there exists an optimal policy v² that is permutation invariant, i.e., 1/" (/ a) v² (x(s), k(a)) for any permutation mapping x(.). In addition, for any permutation invariant policy v. the value function (.) and the sate-action value function Q(-) is also permutation invariant, i.e. (s( = V (n((s), (s. = Q" (((s),((a)) where Q" a) = Ex (r(s,a) + >s)(s))
Proposition 2.1 has an important implication for architecture design, as it states that it suffices to search within the permutation invariant policy and value function classes. To the best of our knowledge, this is the first theoretical justification of permutation invariant network design for learning with homogeneous agents.
We focus on the factorized policy class with a param- eter sharing scheme, where each agent makes its own decision without consolidating with others. Specifi- cally, the joint policy v can be factorized as v(a|s) =
BLay
Cettagon
IT= p where ju(-) denotes the shared local mapping and o; denotes the local observation. Such policy class is widely adopted in the celebrated central- ized training- decentralized execution paradigm (Lowe) et al. (017). due to its light overhead in the deployment phase and favorable performances. However, directly learning such factorized policy remains challenging, as each agent needs to estimate its state-action value a). The search space during learning is ([5) x AA) scaling exponentially with respect to the number of agents. The large search space poses as a significant roadblock for efficient learning, and is coined the curse of many agents.
Figure I: Illustration of permutation invari- ance. Exchanging identities of the agents (first and third row) does not change the transition of the system (second row).
function, denoted as
To address the curse of many agents, we exploit the homogeneity of the system and take the mean-fich approximation. We begin by taking the perspective of agent i, which is arbitrarily chosen from the N agents. We denote its state as 8 and the states of the rest of the agents by S,- One can verify that when permuting the state of all the other agents, the value function remains unchanged; additionally, we can further characterize the value function as a function of the local state and the empirical state distribution over the rest of agents.
Proposition 2.2. For any permutation mapping sd(-), the value function satisfies ("(ss s.)) (* k(s,)). Additionally, there exists gu such that: (" Sp) ( Ps.); where Ps. 1 N E.es, 8g is the empirical distribution over the states of rest of the agents s,,
For system with a large number of agents (e.g.. financial markets, social networks), the empirical state distribution can be seen as the concrete realization of the underlying population distribution of the agents. Motivated from this observation and Proposition| 2.2 we formulate the following mean-field MDP that can be seen as the limit of finite-agent MDP in the presence of infinitely many homogeneous agents.
Definition 2.1 (mean-field MDP), The mean-field MDP consists of elements of the following: state (s, ds) E S x P(S); action a E Á C AS; reward r(s, ds,a)) transition kernel IP(s', d's (s, ds, a).
The mean-field MDP has an intimate connection with our previously discussed finite-agent MDP. Since the the agents are homogeneous, the system is the same from any agent's perspective. We choose any agent (referred to as representative agent), the state information of such an agent includes the local state s, and the mean-field state ds. With state information, the agent selects a meta action a E A E AS, and uses such a meta action to make local decision such a modeling of decision process allows the agent to make decision on both its local information (local state s) and the global information imean-field state ds). From homogeneity we assume all the rest of the agents uses the same meta action a to make their local actions. Note that different agents can still make different local actions due to their different local states, i.e., a(z) A a(z') in general for
a(s) E A. We remark that
3

---

Under review as a conference paper at ICLR 2022
2 # S. The joint state at the next timestep (s', d'')) naturally depends on the current global state (8, (8,ds) and the meta action a (since all the other agents use to generate their local actions), and is specified by the transition kernel P(s', d's 8, dss a). In addition, the representative agents receives a reward r(s, ds, a), which depends on the local state and meean-field sate, and the meta action a.
Our goal is to learn efficiently a policy x, where T--ss, ds) E LAA for all (s, ds) E x P(S), for maximized expected discounted reward. To facilitate discussions, we define the value function (T ds) = (1 {_r= = T'I(St, ds ke)} where (so, ds = (s, ds), a T(s,,ds,)) Vt 2 O; and Q-fucttion Q (s. ds, 7) = (1 T) (E:. 7'r(st. ds.s, T where (So, ds.o) = (s, ds), 0g = a, a. ~ (st, ds,z). The optimal policy is denoted by x² E argmax (s,,
Despite the intuitive analogy to agete- MDP, solving the mean-field MDP poses some unique challenges. In addition to having an unknown transition kernel and reward, the mean-field MDP takes distribution its state, which do not have complete information of during training. In the following section, we propose our mcan-fiele field Neural Proximal Policy Optimization (MF-PPO) algorithm that, with a careful architecture design, can solve such mean-field MDP in model-free fashion efficiently.
3 MEAN-FIELD PROXIMAL POLICY OPTIMIZATION
Our algorithm falls into the category of the actor-critic learning paradigm, consisting of alternating iterations of policy evaluation and improvement. The unique features of MF-PPO lie in the facts: (1) it exploits permutation invariance of the system, reducing search space of the actor/critic networks drastically and enables much more efficient learning: (2) it can handle a varying number of agents. For simplicity of exposition, we consider fixed number of agents here.
Throughout the rest of the section, we assume that for any joint state ds)) E S x P(S), the agent has access to N i..d. samples {s, ) from dg. We denote concatenation of such samples
as s E S. and write i.i.d. ds. MF-PPO maintains a pair of actor (denoted by FÅ) and critic networks (denoted by FR), and uses the actor network to induce an energy-based policy (ā s. ds). Specifically, given state (s, ds), the actor network induces a distribution on set A according to (als, ds) x exp {-- (s, ds, a)} where denotes the temperature parameter. We use æ xx exp { [FA) to denote the dependency of the policy on the energy function.
Actor and Critic. We adopt permutation invariant design of the actor and critic network. Specifically, given individual state E S and sampled states s E SN, the actor (resp. critic) network FA (resp. F satisfies (s s, a) F k(s), a) for any permutation mapping k. With permutation invariance, the search space of the actor/critic network polynomially depends on the number of agents N.
Permutation-invarii
Proposition 3.1. The search space of a permutation invariance actor (critic) network is at the order of min((s),NN) (N-1) (11) | Additionally, iS\ < N, then the search space depends on N Dk=l at the order of Niis.
Compared to architectures without permutation invariance, whose search space depends on N at the order of (IS)) we can clearly see the search space of MF-PPO is exponentially smaller.
Motivated by the characterization of the permuta- tion invariant set function in Zaheer al. (2017). the actor/critic network in MF-PPO takes the form of Deep Sets architecture, i.e., (A s,))
(Oulput)
(Surmary Feature)
(Evex d(s, s', a)/N). Both networks first aggregate local information by averaging over the output of a shared sub-network. among agents, before feeding the aggregated information into a subsequent network h(-). See Figure 2 for detailed illustration. Effectively, by the average pooling layer and the preceding parameter eterized critic network.
Agrnt
Agrns
Agent N
Agont
Figure 2: Illustration of a DeepSet param-
sharing scheme, the network can keep its output unchanged when permuting the ordering of agents. Compared to Graph Convolutional Neural Network (Kipf and Welling 2017). which uses two sets of weights for the linear transformation layer, one for the the agent itself and one for the aggregation state coming from the rest of the agents. The averaging operation is well suited for homogeneous agents and more parameter-efficin efficieet.. It also naturally allows us to handle varying number of agents during training and evaluation, which is not readily achievable by GCN network.
4

---

Under review as a conference paper at ICLR 2022
Naturally, the actor network when given the joint state-action pair (s, dg. a) is given by (A ds; a) = h (0, _a)) We assume F is parameterized by neural network with parameters a RD, which to be learned during training. We let the function class of all possible actor networks be denoted by FA, This same architecture design applies to the critic network, with learnable parameters denoted by E IR and the function class denoted by FQ, MF-PPO then consists of successive iterations of policy evaluation and poliey improvement described below.
Policy Evaluation. At the k-th iteration of MF-PPO, we first update the critic network F by minimizing the mean squared Bellman error while holding the actor network FA, fixed. We denote the policy induced by the actor network as Th. the stationary state distribution of policy Tę as Ve. and the stationary state-action distribution as on (8, ds, a) (x(s,, update
d (als)))aaasss,).) ds). Thus, we follow the
0g = argminges(eo.Rg, Ro) E. F
(s, (s. dg. - [ F.O (s, d).
(3.1)
where B(,,, Ro) denotes the Euclidean ball with radius Hy centered at the initialized pa- rameter to. and the Bellman evaluation operator T is given by T (s, = (1-2))(s, ds, @) + 7 (s',d's,)) ")). where (s',''s) ~ P(-ls, a), a' ~ a(Is', We solve (3.1) by T-step temporal-difee differeeee (TD) update and output 02 ((T). At the t-th iteration of the TD update,
O(t 1/2) 0(1) - o (s, (1 7)r( - (s', sss's'' a Vol (s, 0l1 + 1) = (l) (0(L + 1/2)),
where we sample (s, ds.. a) ~ ok, (s','s) ~ P(.ls,ds,a) a), d' ~ (T(--s' (-ssss lid. ds, s Lid d's. We use (-) to denote the orthogonal projection onto set X, and r7 to denote the step size. Note that here for the simplicity of analyses, we sample the state-action pair (s, ds, @) independently from the stationary distribution. We remark that trajectory samples can also be used, which essentially requires bounding the bias of the gradient at each iteration due to the dependencies between trajectory samples, and we can readily apply the fast-mixing property of Markov chains to control such bias Bhandari et al. 2018). The details of policy evaluation are summarized in Algorithm 2 Appendix A
Policy Improvement. Following the policy evaluation step, MF-PPO updates its policy by updating the policy network FA, which is the energy function associated with the policy. We update the policy network by
argmax mexexp paR+1]. Bug { (F (6s) KL (TT-1s, ds) (+(ss, }-
M++1
pdkkleFF EEF
The update rule intuitively reads as increasing the probability for choosing action ā if it yields higher value for critic network F dg.a), Q), which can be viewed as a softened version of policy iteration (Bertsekas) 2011). Additionally, by controlling the proximity parameter Ukk the softness of the update, with u + O yielding the vanilla policy iteration. Moreover, without constraint of PAA++ E FA, such an update would have a nice closed form expression, and m itself is another energy-based policy.
control
Proposition 3.2. Let Th x exp (T (P)) denote the energy-based policy, then the update
Th+1 = argmax, E., { ( (F (s, ds. ), r (-18, (ssssdss)))))) - KL. dss- ds))
yields कh+1 x exp F + T r.
To take into account that the representable function of actor network resides in FA. we update the policy by projecting the energy function of тe+1 back to FA. Specifically, by denoting T x exp(TTi) F' at_, J. we recover the next actor network FA (i.c., energy) by performing the following regression task
au+s
{ (Fd (s, ds, a) Tkt1 Us F (s, + T T (s, ds, d)) })
} (3.2)
0++1
argmin Eag REB(Ra
5

---

Under review conference paper at ICLR 2022
where o2. MyTT. We approximately solve (3.2) via T-step stochastic gradient descent (SGD), and output 0%+1 a(T) = "k+1 At the 1-th iteration of SGD,
Tht1 (vx F (s.s + F a(t + 1/2) at) - 7/ a (s, (,,s ( a(v) (s,
(s, s) }.
att + 1) (o)) (a(t 1/2)),
where we sample (s, ds, a) ~ k. and s iid ds. and is the step size. The details are summarized in Aggorithm3oo Appendix Finally, we present the complete MF-PPO in Algorithm 1
Algorithm Mean-Field Neural Proximal Policy Optimization
Require:
Mean-field MDP P(S), A, IP, r). discount factor y; number of outer iterations K, number of inner updates T; policy update parameter u, step size 7), projection radius Ra Rg.
Initialize: To < 1, FA.0 +- 0, 3g x exp(To FA.00 (uniform policy).
for k = O,.... K 1 do
Set temperature parameter Th-1 + UVK/ (k + 1), and proximity parameter Uy t VVK
Solve (.1 update the critic network F. using TD update (Algorithm
Solve 3.2 update the actor network for FA
det1" using SGD update (Algorithm)
Update policy: T&+1 ix exp(Te+1 FAA (a+1)
end for
4 GLOBAL CONVERGENCE OF MF-PPO
We present the global convergence of MF-PPO algorithm for the two-layer permutation-invarian parameterization of the actor and critic networks. We remark that our analysis can be extended to multi-layer permutation-invarian networks, and we present the two-layer case here for simplicity of exposition. Specifically, the actor and critic networks take the form
Fd (s,
1
ΣE ugo (a] (s,s',T)) (s,
mA
1
Σ uya (0, (ss.s'a))
V
VMN
J=l''Es
j=l
where mA (resp. mQ) is the width of the actor (resp. critic) network, and (xx = max(x.0) denotes the ReLU activation. We randomly initialize Uy (resp. 0ÿ) and first layer weights og [ap.1..... ".....,,T,mm,, " Rdma (resp. 0g E Rdmma by
Uy ~ Unif
ao.j ~ (O Vie
For ease of analysis, we take m = mA = mg and share the initialization of og and 0g (resp. uo and vo). Additionally, we keep Uj 's fixed during training, and (resp. 0) within ball B(oo, RA) (resp. (O,, RQ)) throughout training. We define the following function class which approximates the class of previously defined actor/critic network for large network width.
Definition 4.1. Given R3 > 0, define the function class over domain S x S x A by
Fp.m [sa(1) Sa(s, a) Vm j=1
1
Σ 0, 1,
()) 1 B0ll2 S Ra}.
where Ug Bu.j are random weights sampled according to Ug Unif { [-1,+1}, ,1,,,,,,,,, Po.j ~ Ia Vj E [m].
FB.m also induces the function class over S x P(S) x A given by
FP p.m [F(-) F(s. a) E. rds (s, s a), fa E F
is well known that functions within Fp.m approximate functions within the reproducing kernel Hilbert space associated with kernel K(x, y) E_ A [[(2 [T 0, > 0)} for a large network width m (Jacot et al. 2018 Chizat and Bach 2018 Cai et al. 2019 Arora et al. 2019) and whose RKHS norm is bounded by R,3. For large Rs and m, F p.m. represents a rich class of functions. Additionally, functions within F& can be viewed as the mean mean-embedding of the joint state-action pair onto the RKHS space (Muandet et al. (2066] Song al. 2009); Smola et al.] (007). Below, make one important assumption, which assumes that F&ym is rich enough to represent the Q-function of all the policies within our policy class.
m.m.

---

Under review as a conference paper at ICLR 2022
Assumption 1. For any policy x induced by FA E EF,, we have Q" F..maa
We remark that Assumption can be relaxed into requiring that F 3,m has approximation error when parameterizing the set of Q-functions, with an additional term appearing in the convergence bound developed in Theorem
Lan 2021).
We define mild conditions stating boundedness of reward, and regularity of stationary distributions. Assumption 2. Reward function r(-) I for some F > 0. Additionally, there exists > 0 such that E [1 (|= (s,s',a) a)] S } S c. T for any 2 E R2 and t > 0.
We measure the progress of MF-PPO in Algorithm Srerrttmmuuiine Duing the expected total reward ((T) = E,- [V* ds)] = E,, {1Q" ds), (--ls, ds))
(4.1)
where v² is the stationary state distribution of the optimal policy x². We also denote o" as the stationary state-action distribution induced by Note that we have: [(x²) = E,- [V (s, ds)] z Eg- [V* d ((r),, for any policy и. Our main results are presented the following theorem, showing that ( converges to ((xx) ) at sub-linear rate.
1K Theorem 4.1 (Global Convergence of MF-PPO). Under Assumptions and 2 the policies {
generated by Algorithm satisiff
minogkgk (f(TT) - [(TT)) 1 oolog ( (1-7)VR
(1-3)eVR)
where M =1=EE Ey- max particular, suppose at each ieeration of MFJPPO, we observe = -O(K ((*K1 R² + K KR2 aggetts
(s. "',))'))))))))))))))) a1)2 (12 2R3, Er and to are defined in Lemma 4.3 In
and the actor/critic network satisfies mA = (K& R + K K ((P) T= Ω (KK
mQ 12 (K²R2)) and
(Knrt, IA + KRt). then we have
mino -(())))))(())))))))))))))))))()) < (log A+OU))+
(1-))evK
Theorem states that, given sufficiently many agents and a large enough actor/critic network, MF-PPO attains global optimality at sublinear rate. Our result shows that when solving the mean-field MDP, having more agents serves as a blessing instead of a curse. addition, as will be demonstrated in our proof sketch, there exists inherent phase transition, where the final optimality gap is dominated by statistical error for a small number of agents (first phase); and by optimization error for large number of agents (second phase).
The complete proof of Theorem 4. takes careful analysis on the error from policy evaluation 3.1 and the improvement step (322). The analysis on the outer iterations of MF-PPO can be overviewed as approximate mirror descent, which needs to take into account how the evaluation and improvement error interacts. Intuitively, the tuple (ER, < describes the the effect of policy update when using approximate policy evaluation and policy improvement, and will be further clarified the ensuing discussion. We present here the skeleton of our proof, and defer the technical detail the appendix.
Proof Sketch. We first establish the convergence of the policy evaluation and improvement step. Lemma 4.1 (Policy Evaluation). Under the same assumptions in Theorem 4.1 let QT denote 2
the Q-function of policy Th, let 6 = Einit,oy ((TT) ()==(())))
denote policy evaluation error,
where ((T) is the output of Algorithm 2 we have EN = =
R TAYE
RE/2 174
R2 N+7
mg
ma
Lemma 4.2 (Policy Improvement). Under the same assumptions in Theorem
4.1
let
6441
Emit,o { [Fam)(() Ts+1 Up F (1) FA, ()))
denote policy optimization error, where (T)
is the output of Algorithm 3. we have 6h.1 = O
R²
R2/2
R²
R²
T172
Lemma and 4.2 show that despite non-convexity, both policy evaluation and policy improvement steps converge approximately to the global optimal solution. In particular, for both policy evaluation steps and improvement steps, given networks with large width, for small number of iterations T. the optimization error O (T-1/2) dominates the optimality gap; for large number of iterations T, the statistical error O (N-1/2) dominates the optimality gap.
7

---

Under review as a conference paper at ICLR 2022
With Lemma 4.1 and 4.2 we illustrate the main argument for the proof of Theorem Let us assume the ideal case when < <E+1 = 0. Note that for e; = 0, we obtain the exact Q f-unctio of policy Ty. For 4+1 = O, we obtain the ideal energy-based updated policy define in Proposition 3.2 That is,
*k+1 = argmax E., (QTH (s, ds. 1), (-1( ds)) KL (IT(-ss, ds) Th (-|s, (ssssss)}
(4.2)
Without function approximation, problem (4.2) can be solved by treating each joint state (s. ds) independently, hence one can apply the well known three-point lemma in mirror descent (Chen and Teboulle 1993) and obtain that, for all (s, ds) E S x P(S):
'QTh (s, ds, ),, ( (sss =x(-ss,ds)
Sun
[K. <vx(KT.
(n (1s ds), (18. - KT. (x" ((s,ds)]l=x (+1s, ds)) - KT. (T (Is + +Q" (s, (s, ds. )) (-11, ds) T& (-|s, ds)).
From Lemma 6.1 in Kakade and Langford (2002), the expectation of the left hand side yields exactly 7) (<(TT) [(T))}. Hence we have
(1-?) ([()))(())))))))))))))()))))[[ - [(Tx)}
SubRE {KT. ((sss (s)) KT. ( (-17(111111 (-88, (5) ds))
-KL ( [T) + E. (Q"A (s, ds. :)
- (x(-ss,ds))
Pinsker's Inequality KL (T4+ (+|s, ds) ( (1)s,, ds)) 2 1 |k+1 - Tull? combined with observation
(8, < </((1 - 7), and basic inequality -ax² bu < b2 (44a for gives
(1-7) [(T+))
72
SunlE {KL (a" (-1s, ds)] TH (11s, - KL (s
22 (1 - 7)
By setting Uy ((VK), and telescoping the above inequality from k mingsks<- ( [(xx))
K 1, we obtain: = (11/VK). K). Note that the key element in the global convergence of ME-PPO is the recursion defined in the previous inequality, which holds whenever we have an exact Q-function of the current policy and no function approximation is used when updating the next policy. Now MF-PPO conducts approximate policy evaluation é& > 0, and after obtaining the approximate Q-function, conducts approximate policy improvement step c > 0 with function approximation. In addition, the етгоr of approximating the Q-function introduced in the evaluation step can be further compounded in the improvement step. Nevertheless, the previous incquality still holds approximately, with additional terms representing the policy evaluation/improoemeet errors.
Lemma 4.3 (Liu et al. (2019a)). Let ex (evaluation error) and é'441 (improvement error) be defined as Lemma and Lemma 4.2 respectively. We have:
(1 7) (f(=*) [(T+)) S Ex {KL (77 (-18,ds) ds).l (ss, KL (-1s,, ds), (T ds))
uk (Ex kk) + Ux MM.
(4.3)
where
2 (5, (s, a)
Ek = -Teii tht1 0b+1 + UK enbi 5 = A (14+1) M Ey.
F
+ 2R2
max a
In addition, 0% and Uoz are defined by:
e = [|d7*/dmm - dTTp/ d 1/2
1t = Eoy [Ido - d(v" x kx)/doa 12122
Finally, by telescoping inequality 4.3) from k = to K - 1, we complete the proof of Theorem 4.1
EXPERIMENTS
We perform experiments on the benchmark multi agget particle environment (MPE) used in prior work (Lowe et al., 2017 Mordatch and Abbeel 20188] Liu et al. (2019b). In the cooperative navigation task, N agents each with position x; < - must move to cover N fixed landmarks at positions y; E R² They receive a team reward = - EM min 14 I; 2l In the cooperative push task, N agents with position x; E 2² work together to push a ball x E I2² to a fixed landmark E R?. They receive team reward R min 1|,, 2112 || 3/ 2/12- Both tasks involve homogeneous
8

---

Under review as a conference paper at ICLR 2022
-1503
-0335
-25000
H+
Air aphoddo
-1003
-3300
1003
OCN
M7-A
Average
-1003
-250600
3sered
VON
1503
Stops
34c
Stops
Steps
(a) N 15
(b) .V- 30
(c) .
200
(d) N = 500
Figure 3: Performance versus number of environment steps in the multi-agent cooperative navigation task, over five independent runs per method. Points are taken every 1000 training episodes, with the first point taken after the first 1000, and is the average reward of 1000 evaluation episodes. MF significantly outperforms other critic representations for various number of agents.
agents, and all the agents share the same team reward. Note that MPE environment also models interaction between agents, including collision, and the collided agents receive negative rewards.
We instantiate our method MF, by parameterizing the centralized critic function using a DeepSet (Zaheer et al., (017) network, with two hidden layers. We use standard two-layer multi-layer perception (MLP) for the centralized actor network in all algorithms. The actor network outputs the mean and diagonal covariance of Gaussian distribution over the joint action space. We refer interested readers to Appendix B for detailed configurations of hyperparameters.
We compare with two other critic repre- sentations: one that uses MLP for the cen- tralized critic, labeled MLP, and another that uses a graph convolutional network for the critic (Liu et al., 2019b), labeled GCN. Note that the GCN representation is per- mutation invariant if one imposes fully- connected graph for the agents in the MPE, but this invariance property does not hold for all graphs in general. We also compare with an extension of (Yang et al., 2018) the case of continuous action spaces, la- beled MF-A, in which each independent DDPG agent i has decentralized critic (ss;, a;, ā.) that takes in the mean of all other agents' actions ā = N-1 Σg4; ay. Finally, we include comparison with VDN (Sunehag et al. 2017). where the centralized critic network the direct summation of local critic networks and thus being permutation invariant. Empirically,
Averaee epaende rewent
-150
-200
-0000
-230
GCN
VF
Averas cotece
-200
310
-3530
-350
24
501
VP-A VON
-420
N" 502
201
302
30 02
08 Steps
Steps
(a) N = 15
(b) Varying critic size
Figure 4: (a) Performance versus number of environ-
ment steps in the multi-agent cooperative push task. (b) MF outperforms GCN even with a fewer number of critic network parameters (N = 3).
we find that off-policy RL learns faster than on-policy RL in the MPE with higher agent number, regardless of the critic representation, we make all comparisons on top of MADDPG (Lowe al.) (017). For fair comparison of all critic representations, we ensure that all neural network architectures contain approximately the same number of trainable weights.
For the cooperative navigation task, Figure 3 shows that the permutation invariant critic representation based on DeepSet enables MF to learn faster or reach a higher performance than all other representa- tions and methods in the MPE with 15, 200, and 500 agents. For the cooperative push task, Figure 4al demonstrates a similar performance improvement provided by MF. In addition, we also demonstrate the superior parameter efficiency of MF compared GCN. Figure 4b shows that MF consistently and significantly outperforms GCN as the number of parameters in their critic network varies over a range, with all other settings fixed. In particular, MF requires much fewer critic parameters to achieve higher performance than GCN.
Computational Improvements. Theorem 4.1 states that to obtain a small optimality gap in MF- PPO, one needs to compute the update embedding techniques developed in Dai et (211)), one can avoid computation on all the agents by sampling small number of agents to compute the update. This technique could be readily incorporated into MF-PPO to improve its computational efficiency.
large number of agents. We remark that with the dual
We propose principled approach to exploit agent homogeneity and permutation invariance through the mean-field approximation in MARL. Our results are also the first to show the global convergence of MARL algorithms with neural networks function approximators. This is in sharp contrast to current practices, which are mostly heuristic methods without convergence guarantees.
Conclusion.

---

Under review conference paper at ICLR 2022
REFERENCES
ARORA, S., DU, S. S., HU, W., LI, Z. and WANG, R. (2019). Fine-grained analysis of opti- mization and generalization for overparameterized two-layer neural networks. arXiv preprint
BERTSEKAS, D. P. (2011). Approximate policy iteration: A survey and some new methods, Journal of Control Theory and Applications 310-335.
BHANDARI, J., RUSSO, D. and SINGAL, R. (2018). A finite time analysis of temporal difference learning with linear function approximation. Conference On Learning Theory. PMLR.
BLOEM-REDDY, B. and TEH, Y. W. (2019). Probabilistic symmetry and invariant neural networks. arXiv preprint Xr..vv9901.00000 1901.06022.
CAI, Q., YANG, Z., LEE, D. and WANG, Z. (2019). Neural temporal-diiference learning converges to global optima. In Advances in Neural Information Processing Systems.
CAO, Y., YU, W., REN, W. and CHEN, G. (2013). An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial informatics 9 427-438.
CARMONA, R., LAURIÈRE, M. and TAN, Z. (2019). Model-free mean- field reinforcement learning: mean-field mdp and mean-field q-learning. arXiv preprint arXiv:1910.1288 12802..
CHEN, G. and TEBOULLE, M. (1993). Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal Optimization 3 538-543.
CHIZAT, L. and BACH, (2018). note on lazy training supervised differentiable programming. arXiv preprint
8.
DAI, B., SHAw, A., L1, L.., XIAO, L.., HE, N., LIU, Z., CHEN, and SONG, (2017). Sbeed: Convergent reinforcement learning with nonlinear function approximation. arXiv preprint arXiv:1712.10285
GU, H., Guo, X., WEI, X. and Xu, R. (2019). Dynamic programming principles for learning mfcs. arXiv preprint arXiv:1911.07311
GU, H., GUO, X., WEI, X. and Xu, R. (2020). Mean-field controls with q-learning for cooperative marl: Convergence and complexity analysis. arXiv preprint a<Xiv:2002.04131.
GU, H., GUO, X., WEL, X. and Xu, R. (2021). Mean-field multi-agent reinforcement learning: A decentralized network approach. arXiv preprint arXiv:2108.0273)
JACOT, A., GABRIEL, F. and HONGLER, C. (2018). Neural tangent kerel:: Convergence and generalization in neural networks. In Advances neural information processing systems.
KAKADE, S. and LANGFORD, J. (2002). Approximately optimal approximate reinforcement learning. In ICML, vol.
KALYANAKRISHNAN, S., LIU, Y. and STONE, P. (2006). Half field offense in robocup soccer: A multiagent reinforcement learning case study. In Robot Soccer World Cup. Springer.
KIPF, T. N. and WELLING, M. (2017). Semi-supervised classification with graph convolutional networks, In International Conference on Learning Representatioons.
KOBER, J., BAGNELI,, J. A. and PETERS, J. (2013). Reinforcement learning in robotics: A survey. The International Journal of Robotics Research 1238-1274.
LAN, G. (2021). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. arXiv preprint arXiv:2102.00135.
LITTMAN, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994. Elsevier, 157-163.
10

---

Under review conference paper at ICLR 2022
LIU, B., CAI, Q.. YANG, and WANG, Z. (2019a). Neural proximal/trust region policy optimization attains globally optimal policy. arXiv preprint arXiv: 1906. 10306
LIU, I.-J., YEH, R. A. and SCHWING, A. G. (2019b). Pic: Permutation invariant critic for multi-agent deep reinforcement learning. arXiv preprint [tt::////.0000//
LOWE, R., WU, Y., TAMAR, A., HARB, J., ABBELL, O. P. and MORDATCH, 1. (2017). Multi-agent actor-critic for mixed cooperative-compettiive environments. In Advances Neural Information Processing Systems.
MATARIĆ, M. J. (1997). Reinforcement learning in the multi-robot domain. In Robot colonies. Springer, 73-83.
MENDA, K., CHEN, Y.-C., GRANA, J., BoNo, J. W., TRACEY, B. D., KOCHENDERFER, M. and WOLPERT, D. (2018). Deep reinforcement learning for event-driven multi-agent decision processes. IEEE Transuctions on Intelligent Transportation Systems 20 1259-1268.
MORDATCH, and ABBEEL, P. (2018). Emergence of grounded compositional language in multi- agent populations. In Thirty-Second AAAI Conference on Artificial Intelligence.
MUANDET, K., FUKUMIZU, K., SRIPERUMBUDUR, B. and SCHÖLKOPF, B. (2016). Kernel mean embedding of distributions: A review and beyond. arXiv preprint arXiv:1605.0952. 09.6222...92.....
PANAIT, I.. and LUKE, S. (2005). Cooperative multi-agent learning: The state of the art. Autonomous agents and multi-agent systems 11 387-434.
SCHULMAN, J., WOLSKI, F., DHARIWAL, P., RADFORD, A. and KLIMOV, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.00347
SHALEV-SHWARTZ. S., SHAMMAH, S. and SHASHUA, A. (2016). Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295.
SMOLA, A., GRETTON, A., SONG, L. and SCHŌLKOPF, B. (2007). A hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory. Springer.
SONG, L., HUANG, J., SMOLA, A. and FUKUMIZU, K. (2009). Hilbert space embeddings of conditional distributions with applications to dynamical systems. In Proceedings of the 26th Annual International Conference on Machine Learning.
SUNEHAG, P., LEVER, G., GRUSLYS, A., CZARNECKL, W. M., ZAMBALDI, V., JADERBERG, M.,
LANCTOT, M., SONNERAT, N., LEIBO, J. Z., TUYLS, K. ET AL. (2017). deloppsccoopoiiiionn networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.0m 1706.05296
SUTTON, R. S. and BARTO, A. G. (2018). Reinforcement learning: An introduction. MIT press.
VINYALS, O.,, BABUSCHKIN, I., CZARNECKI, W. M., MATHIEU, M., DUDZIK, A., CHUNG, J., CHOI, D. H., POWELL, R., EWALDS, T., GEORGIEV, P. ET AL. (2019). Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature 575 350-354.
WANG, L., YANG, Z. and WANG, Z. (2020). Breaking the curse of many agents: Provable mean embedding q-iteration for mean-field reinforcement learning. In International Conference on Machine Learning. PMLR.
YANG, J., YE, X., TRIVEDI, R., XU, H. and ZHA, H. (2017). Learning deep mean field games for modeling large population behavior. arXiv preprint arXiv:
YANG, Y., LUO, R., LI, M., ZHOU, M., ZHANG, W. and WANG. (2018). Mean field multi-agent reinforcement learning. arXiv preprint 1XXi::802.00533
ZAHEER, M., KOTTUR, S., RAVANBAKHSH, S., PoCZOs, B., SALAKHUTDINOv, R. R. and SMOLA, A. J. (2017). Deep sets. In Advances in neural information processing systems.

---

Under review conference paper at ICLR 2022
ZHANG, K., YANG, Z. and BAŞAR, T. (2019). Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv:
ZHENG, S., TROTT, A., SRINIVASA, S., NAIK, N., GRUESBECK, M., PARKES, D. C. and SOCHER, R. (2020). The ai economist: Improving equality and productivity with ai-driven tax policies. arXiv preprint arXiv:2004. 13332.
12


Reviews:
[{"review_id": "z0kmQhC8J7O", "reviewer": "Reviewer_6Xxz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nI raise some concrete questions, which hopefully will clarify some of my doubts during the rebuttal.\n\n1. Why are energy models used for policy training, is it matter of convenience, or is there a deeper reason?\n\n2. 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).\n\n3. 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].\n\n4. Is the proof a novel one?\n\n5. What is the exact experimental setup:\n\n6. 1. What are the details about the environments used? What are the interactions between agents? How intensive are they?\n   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_paper": "The authors present a principled method of solving problems with multiple homogenous agents. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "vbJCgGxbtH7", "reviewer": "Reviewer_fcc8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n1. 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. \n    * 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. \n    * 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”.\n2. 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)].\n3. 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. \n4. 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. \n\n[A] Computing equilibria in multi-player games. Christos H. Papadimitriou and Tim Roughgarden.", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QdGW7vOIMHg", "reviewer": "Reviewer_979E", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nI have several minor suggestions that may help to further improve the exposition:\n\n(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)\n\n(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.\n\n(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$.\n\n(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}$)?\n\n(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?\n\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).\n\n", "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.", "summary_of_the_review": "The submission is well written and provides a good contribution to the MARL literature.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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