{'fraction_non_alphanumeric': 0.05372972972972973, 'fraction_numerical': 0.013972972972972973, 'mean_word_length': 4.155496725651386, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach

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 a 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.


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 own long term rewards while interacting with one another in a common environment. With breakthroughs in deep learning, MARL algorithms equipped with deep neural networks 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 is recently described as the curse of many agents (Menda et al., 2018). To tackle this Yan Li, Jiachen Yang, Ethan Wang, and Tuo Zhao are affiliated with Georgia Institute of Technology; Lingxiao Wang, Zhaoran Wang are affiliated with Northwestern University; Hongyuan Zha is affiliated with The Chinese University of Hong Kong, Shenzhen. Tuo Zhao is the corresponding author; Email: tourzhao@gatech.edu. 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 MARL 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 et al., 2013;Kalyanakrishnan et al., 2006), and also in the case of heterogeneous groups where invariance holds within each group (Liu et al., 2019b). More importantly, we further find that permutation invariance has significant practical implications, as the optimal value functions remains invariant when permuting the joint state-action pairs. Such an observation strongly advocates a 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 Convolutional Network (GCN) (Kipf and Welling, 2017). Sunehag et al. (2017) propose value decomposition, which together with parameter sharing, leads to a joint critic network that is permutation invariant over 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 policy in homogeneous systems. In addition, we adopt the DeepSet (Zaheer et al., 2017) architecture, which is well suited for handling homogeneity of agents, with much simpler operations to induce permutation invariance, and being much more parameter efficient by doing so.
To scale up learning in MARL problem 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. Yang et al. (2017) consider a mean-field game with deterministic linear state transitions, and show it can be reformulated as a mean-field MDP, with mean-field state residing in a finite-dimensional probability simplex. Yang et al. (2018) take the 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 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. Carmona et al. (2019) motivate a mean-field MDP from the perspective of mean-field control. The mean-field state therein lies in a probability simplex and thus continuous in nature. To enable the ensuing Q-learning algorithm, discretization of the joint state-action space is necessary. Wang et al. (2020) 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 joint state space. In contrast, our formulation of mean-field approximation allows agents to make their own local actions without resorting to a centralized controller.
We propose a mean-field Markov decision process motivated from the permutation invariance structure of cooperative MARL, which can be viewed as a natural limit of finite-agent MDP by taking the number of agents to infinity. Such a 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, even 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 a smaller number of model parameters and attains a better performance compared to multiple baselines.
Notations. For a set X, we denote P (X) as the set of distribution on X. δ x denotes the Dirac measure supported at x. For s = (s 1 , . . . , s N ), we use s ∼ p to denote that each s i is independently sampled from distribution p. For a function f : X → R and a distribution π ∈ P (X), we write f , π = E a∼π f (a). We write [m] in short for {1, . . . , m}.

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 a Markov decision process (S N , A N , P, 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 joint action space A N . The homogeneous nature of the system is reflected in the transition kernel P and the shared reward r, which satisfies: r(s t , a t ) = r (κ(s t ), κ(a t )) , P(s t+1 |s t , a t ) = P (κ(s t+1 )|κ(s t ), κ(a t )) , for all (s t , a t ) ∈ S N × A N and permutation mapping κ(·). In other words, it is the configuration, rather than the identities of the agents, that affects the team reward, and the transition to the next configuration solely depends on the current configuration. See Figure 1 for a detailed illustration. Such permutation invariance can be found in many real-world scenarios, such as distributed control of multiple autonomous vehicles, team sports and social economic systems (Zheng et al., 2020;Cao et al., 2013;Kalyanakrishnan et al., 2006). Our goal is to find the optimal policy ν within a policy class which maximizes the expected discounted reward Our first result shows that learning with permutation invariance advocates permutation invariant network design.
Proposition 2.1. For cooperative MARL satisfying (1), there exists an optimal policy ν * that is permutation invariant, i.e., ν * (s, a) = ν * (κ(s), κ(a)) for any permutation mapping κ(·). In addition, for any permutation invariant policy ν, the value function V (·) and the state-action value function Q(·) is also permutation invariant Proposition 2.1 has an important implication for architecture design, as it states that it suffices to search within the permutation invariant policy class and value function class. 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 parameter sharing scheme, where each agent makes its own decision given local state. Specifically, the joint policy ν can be factorized as ν(a|s) = N i=1 µ(a i |s i ), where µ(·) denotes the shared local mapping. Such a policy class is widely adopted in the celebrated centralized training -decentralized execution paradigm (Lowe et al., 2017), 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 stateaction value function, denoted as Q ν (s, a). The search space during learning is (|S| × |A|) N , which scales exponentially with respect to the number of agents. The large search space poses as a significant roadblock for efficient learning, and was recently coined as the curse of many agents (Menda et al., 2018).
To address the curse of many agents, we exploit the homogeneity of the system and take meanfield approximation. We begin by taking the perspective of agent i, which is arbitrarily chosen from the N agents. We denote the state of such agent by s and the states of the rest of the agents by s r . 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.
Additionally, there exists g ν such that: where p s r = 1 N s∈s r δ s is the empirical state distribution over the rest of the agents.
For a 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 distribution of the population. 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, d S ) ∈ S ⊆ S × P (S); action a ∈ A ⊆ A S ; reward r(s, d S , a); transition kernel P(s , d S |s, d S , a).
The defined mean-field MDP has an intimate connection with our previously discussed finiteagent MDP: here (s, d S ) represents the joint state viewed from the individual agent with state s; each agent makes a local decision using the shared local mapping a : S → A and receive a local reward, whose cumulative effect is captured by the team reward r(s, d S , a); finally, the joint state transits to (s , d S ) according to kernel P(s , d S |s, d S , a). We can clearly see that the mean-field MDP has a step-to-step correspondence with the finite-agent MDP with homogeneous agents, thus making it a natural generalization in the presence of large number of agents.
Our goal is to learn efficiently a policy π whose expected discounted reward is maximized. To facilitate ensuing discussions, we define the value function as where (s 0 , d S,0 ) = (s, d S ), a t ∼ π(s t , d S,t ), ∀t ≥ 0, and Q-function as where (s 0 , d S,0 ) = (s, d S ), a 0 = a, a t ∼ π(s t , d S,t ). The optimal policy is then denoted by π * ∈ argmax V π (s, d S ).
Despite the intuitive analogy to finite-agent MDP, solving the mean-field MDP posses some unique challenges. In addition to the unknown transition kernel and reward, the mean-field MDP takes a distribution as its state, which we do not have complete information of during training. In the following section, we propose our mean-field Proximal Policy Optimization (MF-PPO) algorithm that, with a careful architecture design, can solve such mean-field MDP in a model-free fashion efficiently.

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 a fixed number of agents here.
Throughout the rest of the section, we assume that for any joint state (s, d S ) ∈ S × P (S), the agent has access to N i.i.d. samples We denote concatenation of such samples as s ∈ S N and write s MF-PPO maintains a pair of actor (denoted by F A ) and critic networks (denoted by F Q ), and uses the actor network to induce an energy-based policy π(a|s, d S ). Specifically, given state (s, d S ), the actor network induces a distribution on the action set A according to where τ denotes the temperature parameter. We use π ∝ exp F A to denote the dependency of the policy on the energy function.
• Permutation-invariant Actor and Critic. We adopt a permutation invariant design of the actor and critic network. Specifically, given individual state s ∈ S and sampled states s for any permutation mapping κ. With permutation invariance, the search space of the actor/critic network polynomially depends on the number of agents N .
Proposition 3.1. The search space of a permutation invariance actor (critic) network is at the order of Additionally, if |S| < N , then the search space depends on N at the order of N |S| .
Compared to architectures without permutation invariance, whose search space depends on N at the order of (|S||A|) N , we can clearly see the search space of MF-PPO can be exponentially smaller.
Motivated by the characterization of the permutation invariant set function in Zaheer et al. (2017), the actor/critic network in MF-PPO takes the form of Deep Sets architecture, i.e., Both networks first aggregate local information by averaging over the output of a shared subnetwork among agents, before feeding the aggregated information into a subsequent network.
See Figure 2 for a detailed illustration. Effectively, by the average pooling layer and the preceding parameter sharing scheme, the network can keep its output unchanged when permuting the ordering of agents. Compared to a Graph Convolutional Neural Network (Kipf and Welling, 2017), the averaging operations are well suited for homogeneous agents and more parameter-efficient.
Naturally, the actor network when given the joint state-action pair (s, d S , a) is given by We assume F A is parameterized by a neural network with parameters α ∈ R D , which is to be learned during training. We let the function class of all possible actor networks be denoted by F A . This same architecture design applies to the critic network, with learnable parameters denoted by θ ∈ R D and the function class denoted by F Q . MF-PPO then consists of successive iterations of policy evaluation and policy improvement steps described in detail below. • Policy Evaluation. At the k-th iteration of MF-PPO, we first update the critic network F Q by minimizing the mean squared Bellman error while holding the actor network F A,k fixed. We denote the policy induced by the actor network as π k , the stationary state distribution of policy π k as ν k , and the stationary state-action distribution as σ k = ν k π k . Thus, we follow the update where B(θ 0 , R θ ) denotes the Euclidean ball with radius R θ centered at the initialized parameter θ 0 , and the Bellman evaluation operator T π is given by where d S ∼ P(·|d S , a), a ∼ π(·|s , d S ). We solve (2) by T-step temporal-difference (TD) update and output θ k = θ(T ). At the t-th iteration of the TD update, We use Π X (·) to denote the orthogonal projection onto set X, and η to denote the step size. The details are summarized in Algorithm 2 in Appendix A.
• Policy Improvement. Following the policy evaluation step, MF-PPO updates its policy by updating the policy network F A , which is the energy function associated with the policy. We update the policy network by The update rule intuitively reads as increasing the probability for choosing action a if it yields a higher value for critic network F Q (s, d S , a), which can be viewed as a softened version of policy iteration (Bertsekas, 2011). Additionally, by controlling the proximity parameter υ k , we can control the softness of the update, with υ → 0 yielding the vanilla policy iteration. Moreover, without constraint of F A,k+1 ∈ F A , such an update would have a nice closed form expression, and π k+1 itself is another energy-based policy.
To take into account that the representable function of actor network resides in F A , we update the policy by projecting the energy function of π k+1 back to F A . Specifically, by denoting we recover the next actor network F A α k+1 (i.e., energy) by performing the following regression task where σ k = ν k π 0 . We approximately solve (3) via T-step stochastic gradient descent (SGD), and output where we sample (s, d S , a) ∼ σ k , and s i.i.d.
∼ d S , and η is the step size. The details are summarized in Algorithm 3 of Appendix A. Finally, we present the complete MF-PPO in Algorithm 1.

Algorithm 1 Mean-Field Proximal Policy Optimization
Require: Mean-field MDP (S, A, P, r), discount factor γ; number of outer iterations K, number of inner updates T ; policy update parameter υ, step size η, projection radius R α , R θ .
Set temperature parameter τ k+1 ← υ √ K/(k + 1), and proximity parameter υ k ← υ √ K Solve (2) to update the critic network F Q θ k , using TD update (Algorithm 2) Solve (3) to update the actor network for F A α k+1 , using SGD update (Algorithm 3) Update policy: We present the global convergence of MF-PPO algorithm for two-layer permutation-invariant parameterization of actor and critic network. We remark that our analysis can be extended to multilayer permutation-invariant networks, and we present the two-layer case here for simplicity of exposition. Specifically, the actor and critic networks take the form where m A (resp. m Q ) is the width of the actor (resp. critic) network, and σ (x) = max{x, 0} denotes the ReLU activation. We randomly initialize u j (resp. v j ) and first layer weights For the ease of analysis, we take m = m A = m Q and share the initialization of α 0 and θ 0 (resp. u 0 and v 0 ). Additionally, we keep u j 's fixed during training, and α (resp. θ) within the ball B(α 0 , R A ) (resp. B(θ 0 , R Q )) throughout training. We define the following function class characterizing the class of previously defined actor/critic network for large network width.
where v j , β 0,j are random weights sampled according to F β,m also induces the function class over S × P (S) × A given by It is well known that functions within F β,m approximate functions within the reproducing kernel Hilbert space associated with kernel K(x, y) = E z∼N (0,I d /d) {1(z x > 0, z y > 0)} for large network width m (Jacot et al., 2018;Chizat and Bach, 2018;Cai et al., 2019;Arora et al., 2019), whose RKHS norm is bounded by R β . For large R β and m, F β,m represents a rich class of functions. Additionally, functions within F P β,m can be viewed as the mean-embedding of the joint state-action pair onto the RKHS space (Muandet et al., 2016;Song et al., 2009;Smola et al., 2007). Below, we make one technical assumption which states that F P θ,m Q is rich enough to represent the Q-function of all the policies within our policy class.

Assumption 1. For any policy π induced by
We define two mild conditions stating (1) boundedness of reward, and (2) regularity of the joint state and the policy.
Assumption 2. Reward function r(·) ≤ r for some r > 0. Additionally, for any (s, d S ) ∈ S and any π, there exists c > 0 such that for any z ∈ R d and t > 0.
We remark that the condition in Assumption 2 holds whenever S is bounded and d S × π has an upper bounded density.
We measure the progress of MF-PPO in Algorithm 1 using the expected total reward where ν * is the stationary state distribution of the optimal policy π * . We also denote σ * as the stationary state-action distribution induced by π * . Note that we have: for any policy π. Our main results are presented in the following theorem, showing that L(π k ) converges to L(π * ) at a sub-linear rate.  s , a)) 2 +2R 2 A , ε k and ε k are defined in Lemma 4.3. In particular, suppose at each iteration of MF-PPO, we observe

agents, and the actor/critic network satisfies
Theorem 4.1 states that, given sufficiently many agents and a large enough actor/critic network, MF-PPO attains global optimality at a sublinear rate. Our result shows that when solving the mean-field MDP, having more agents serves as a blessing instead of a curse. In addition, as will be demonstrated in our proof sketch, there exists an inherent phase transition depending on the number of agents, where the final optimality gap is dominated by statistical error for a small number of agents (first phase); and by optimization error for a large number of agents (second phase).
The complete proof of Theorem 4.1 takes a careful analysis on the error from policy evaluation (2) and the improvement step (3). 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 (ε k , ε k ) describes the the effect of policy update when using approximate policy evaluation and policy improvement, and will be further clarified in the ensuing discussion. We present here the skeleton of our proof, and defer the technical detail to the appendix.
Proof Sketch. We first establish the global convergence of the policy evaluation (2) and improvement step (3).
Lemma 4.1 (Policy Evaluation). Under the same assumptions in Theorem 4.1, let Q π k denote the Qfunction of policy π k , let Lemma 4.2 (Policy Improvement). Under the same assumptions in Theorem 4.1, let denote policy optimization error, where α(T ) is the output of Algorithm 3, we have Lemma 4.1 and 4.2 show that despite non-convexity, both the policy evaluation and the policy improvement steps converge approximately to the global optimal solution. In particular, given networks with large width, for a small number of iterations T , the optimization error O T −1/2 dominates the optimality gap; for a large number of iterations T , the statistical error O N −1/2 dominates the optimality gap.
With Lemma 4.1 and 4.2, we illustrate the main argument for the proof of Theorem 4.1. Let us assume the ideal case when k = k+1 = 0. Note that for k = 0, we obtain the exact Q-function of policy π k . For k+1 = 0, we obtain the ideal energy-based updated policy defined in Proposition 3.2. That is, Without function approximation, problem (5) can be solved by treating each joint state (s, d S ) independently, hence one can apply the well known three-point lemma in mirror descent (Chen and Teboulle, 1993) and obtain that, for all (s, d S ) ∈ S × P (S): From Lemma 6.1 in Kakade and Langford (2002), the expectation of the left hand side yields exactly (1 − γ) {L(π * ) − L(π k )}. Hence we have Pinsker's Inequality combined with the observation Q π k (s, d S , ·) ∞ ≤ r, and basic inequality −ax 2 + bx ≤ b 2 /(4a) for a > 0 gives us By setting υ k = O( √ K), and telescoping the above inequality from k = 0 to K − 1, we obtain: Note that the key element in the global convergence of MF-PPO is the recursion defined in (6), which holds whenever we have the exact Q-function of current policy and no function approximation is used when updating the next policy. Now MF-PPO conducts approximate policy evaluation ( k > 0), and after obtaining the approximate Q-function, conducts approximate policy improvement step ( k+1 > 0). In addition, the error of approximating the Q-function introduced in the evaluation step can be further compounded in the improvement step. Nevertheless, recursion (6) still holds approximately, with additional terms representing the policy evaluation/improvement errors. where In addition, φ * k and ψ * k are defined by: Finally, from Lemma 4.3, by telescoping inequality (8) from k = 0 to K − 1, we complete the proof of Theorem 4.1.

Experiments
We perform experiments on the benchmark multi-agent particle environment (MPE) used in prior work (Lowe et al., 2017;Mordatch and Abbeel, 2018;Liu et al., 2019b). In the cooperative navigation task, N agents each with position x i ∈ R 2 must move to cover N fixed landmarks at positions y i ∈ R 2 . They receive a team reward R = − N i=1 min j∈[N ] y i − x j 2 ; In the cooperative push task, N agents with position x i ∈ R 2 work together to push a ball x ∈ R 2 to a fixed landmark y ∈ R 2 . They receive a team reward R = − min j∈ [N ] x j − x 2 − x − y 2 . Both tasks involve homogeneous agents.
We We compare with two other critic representations: one that uses MLP for the centralized 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 permutation invariant if one imposes a fullyconnected 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) to the case of continuous action spaces, labeled MF-A, in which each independent DDPG agent i has a decentralized critic Q(s i , a i ,ā i ) that takes in the mean of all other agents' actionsā i := 1 N −1 j i a j . Empirically, as 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 et al., 2017) for all N ≥ 15 cases. For a 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 and MF-PS to learn faster or reach a higher performance than all other representations and methods in the MPE with 6, 15, 30 and 200 agents. Figure 4a 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. For the cooperative push task, Figure 4b demonstrates similar performance improvement of MF compared to all other methods. We provide additional experiment detail in Appendix B. Computational Improvements. Theorem 4.1 states that to obtain a small optimality gap in MF-PPO, one needs to compute the update on a large number of agents. We remark that with the dual embedding techniques developed in Dai et al. (2017), one can avoid computation on all the agents by sampling a small number of agents to compute the update. This technique could be readily incorporated into MF-PPO to improve its computational efficiency.

Conclusion
We propose a principled approach to exploit agent homogeneity and permutation invariance through the mean-field approximation in MARL. Moreover, our results are also the first to provably show the global convergence of MARL algorithms with neural networks as function approximators. This is in sharp contrast to current practices, which are mostly heuristic methods without convergence guarantees. Zheng, S., Trott, A., Srinivasa, S., Naik, N., Gruesbeck, M., Parkes, D. C. and Socher, R.

Supplementary Material for A Permutation Invariant Approach to Deep Mean-Field Multi-Agent Reinforcement Learning
A Algorithms for Policy Evaluation/Improvement Algorithm 2 Policy Evaluation via TD

Algorithm 3 Policy Improvement via SGD
Require: Mean-field MDP (S, A, P, r, γ), sample {(s t , s t , a t }, number of iterations T  2019b)) with ReLU activation, and f 3 is a linear layer with output size 1. ♦ MLP. The centralized critic is an MLP with two hidden layers of size 138,187,75,42,7 for the case of N = 3, 6, 15, 30, 200 agents, respectively, such that total number of trainable parameters is approximately equal to that in GCN (Liu et al., 2019b). The joint policy has the same representation as the one in MF for both PPO-based and MADDPG-based implementations. ♦ Hyperparameters. We used the Adam optimizer for all algorithms. For experiments based on PPO, the common hyperparameters across all algorithms are: discount factor γ = 0.99, KL divergence target d targ = 0.01, KL divergence initial coefficient β = 3, and GAE λ = 0.95 (see Schulman et al. (2017)), policy entropy loss coefficient 0.01, max gradient norm 0.5, and actor learning rate 10 −4 . Each PPO training step uses 5 epochs with minibatch size 2. We did a sweep of critic learning rate for each critic architecture, choosing 10 −3 for MF, 10 −4 for GCN and MLP, and 10 −2 for MF-A.
For experiments based on MADDPG, the common hyperparameters are: actor learning rate 0.01, critic learning rate 0.01, batch size 1024, discount factor γ = 0.95, replay buffer size 10 5 , 8 actor and critic updates per 100 environment steps, and target network update rate τ = 0.01.

C Proofs in Section 2
Proof of Proposition 2.1. We first prove the first part of claim. We begin by showing that the optimal Q-function Q * is permutation invariant, i.e., Q * (s, a) = Q * (κ(s), κ(a)) for all permutation mapping κ. Note that Q * is the unique solution to Bellman optimality condition over the space of That is, Q(κ(s), κ(a)) is also a solution to the Bellman optimality condition (9). From the uniqueness of the solution, we have Q * (s, a) = Q * (κ(s), κ(a)). Hence the optimal policy ν * (s) = argmax a Q * (s, a) is permutation invariant. For second part of the proposition, we show the detailed proof for permutation invariance of value function V . For any permutation invariance policy ν, let R ν (s) = E a∼ν R(s, a), and P ν (s |s) = E a∼ν P(s |s, a) denote the key elements of the induced Markov reward process. One can clearly see that from permutation invariance defined in (1), we have that both R ν and P ν (s |s) is permutation invariant. We define the k-step value function V ν k as the expected reward from time 0 to time k, then: We can see from above recursion that V ν k is permutation invariant for all k ≥ 1. From V ν = lim k→∞ V ν k , we can conclude that V ν is also permutation invariant. For permutation invariance of Q-function, recall that Q ν (s, a) is the unique solution of the following Bellman evaluation equation From the permutation invariance of r, P and ν, we have Q ν is also a solution to (10), as Q(κ(s), κ(a)) = r(s, a) + s ,a P(s |s, a)Q(κ(s ), κ(a ))ν(s , a ).
Proof of Proposition 2.2. The proof for showing V ν (s, s r ) = V ν (s, κ(s r )) follows the exact same ingredients as in the proof for Proposition 2.1. Following Theorem 11 in Bloem-Reddy and Teh Proof of Proposition 3.2. Note that the maximization problem can be solved separately for each s, d S . Hence we can equivalently solve which is an optimization problem over finite-dimensional parameter π(·|s, d S ) ∈ R A . Setting the derivative w.r.t. π(a|s, d S ) for each a ∈ A equal to zero, we have or equivalently, π(a|s, d S ) ∝ π k (a|s, d S ) exp{υ −1 k F Q θ k (s, d S , a)}. Plug in the definition of π k ∝ exp τ −1 k F A α k completes the proof.

E Proofs in Section 4
We provide a unified analysis of the policy evaluation and policy improvement step. The policy evaluation and improvement steps can be described as minimizing the following mean-squared loss: where the operator ζ maps function F β to Formulation (11) includes policy improvement and policy evaluation as special cases: Policy Improvement. This corresponds to S , a)), τ = 1, µ = 0, Policy Evaluation. This corresponds to ρ = σ k , τ = 1 − γ, µ = γ, ξ(s, d S , a) = r(s, d S , a). Note that ζ F θ (s, d S , a) equals to the Bellman operator: ζ F θ (s, d S , a) = T π F θ (s, d S , a).
where (s, d S , a) ∼ ρ, (s , d S ) ∼ P(·|s, d S , a), a ∼ π(·|s , d S ). Instead of knowing s, d S exactly, we only have access to s, d S via N independent samples represented as the states of N agents. Hence, we perform the following update: where (s, d S , a) ∼ ρ, (s , d S ) ∼ P(·|s, d S , a), a ∼ π(·|s , d S ); and s , we recover the policy improvement update in Algorithm 2. Policy Evaluation Updates. For ρ = σ k , τ = (1−γ), µ = γ, ξ(s, d S , a) = r(s, d S , a), R β = R θ , we recover the policy evaluation update in Algorithm 3.
We define a few more notations before we proceed where (s, d S , a) ∼ ρ, (s , d S ) ∼ P(·|s, d S , a), a ∼ π k (·|s , d S ).
We also define the associated finite sample approximation: ∼ d S . Note that given g is not an unbiased estimator of g, as E s,s g(s, s, a, s , s , a ) g(s, d S , a, s , d S , a ).

E.1 Linearization at Initialization
For a two layer ReLU network defined as f β,u (s, x, a) = 1 √ m m j=1 u j σ (β j (s, x, a)), where σ (x) = max{0, x}, we define its linearization at the initialization (s, x, a). , a), β , which equivalently means f 0 β is the local linearization of f β at its initialization β(0) (note we do not train the second layer u).
We define and similarly define δ 0 , g 0 , g 0 , δ 0 , and g 0 , with everything related to F β , F β replaced by F 0 β , F 0 β . Our main objectives are to show that the objective in (11) can be replaced by replacing everything related to F with its local linearization F 0 , and the linearized stochastic semi-gradient g 0 remains close to the population semi-gradient g when the number of hidden units m and number of agents are large enough. By doing so, we can conclude that learning with linearized stochastic semi-gradient g is sufficient to solve (11) to high accuracy, when the number of hidden units m and number of agents are large enough. For the ease of exposition, we also make the following assumptions, Assumption 3. We assume (s, x, a) 2 ≤ 1 for all (s, x, a) ∈ S × S × A.
We first bound the difference between F 0 β (s, d S , a) and F β (s, d S , a).
Lemma E.1. With Assumption 2 and 3, we have Proof. Be definition of F 0 β (s, d S , a) and F β (s, d S , a) and Jensen's inequality, we have We can further bound the right hand side with where the last inequality comes from that fact that 1{β j (0) (s, x, a) > 0} 1{β j (s, x, a) > 0} implies where in the third inequality we use Assumption 2.
Next, we bound the difference between g and and g 0 .
We then bound the variance of g(s, s, a, s , s , a ) for fixed d S , d S . Now apply Lemma E.3 and Lemma E.4, the claim follow immediately.
We are now ready to show the convergence of using updates (13) and (14) to solve problem (11). We denote F 0 β * to be the function within the class F R,m , which satisfies the stationary condition: where Π X (·) denotes the Euclidean projection onto set X. Condition (21) is equivalent to: With the definition of operator ζ F in (12), we know that From (22) and (23), we have which is equivalent to that F 0 β * = Π F R β ,m (ζ F 0 β * ). That is, F 0 β * is the projection (with metric defined w.r.t ·, · ρ ), after applying operator ζ to itself.
We first consider the second term in (24) Re-arrange and telescope, we have Notice that the left hand side of (31) is convex with respect to β(t), we can take average of {β(t)} T −1 t=0 . Define β T = 1