Year: 2018

Abstract:
A deep reinforcement learning solution is developed for a collaborative multiagent system. Individual agents choose actions in response to the state of the environment, their own state, and possibly partial information about the state of other agents. Actions are chosen to maximize a collaborative long term discounted reward that encompasses the individual rewards collected by each agent. The paper focuses on developing a scalable approach that applies to large swarms of homogeneous agents. This is accomplished by forcing the policies of all agents to be the same resulting in a constrained formulation in which the experiences of each agent inform the learning process of the whole team, thereby enhancing the sample efficiency of the learning process. A projected coordinate policy gradient descent algorithm is derived to solve the constrained reinforcement learning problem. Experimental evaluations in collaborative navigation, a multi-predator-multi-prey game, and a multiagent survival game show marked improvements relative to methods that do not exploit the policy equivalence that naturally arises in homogeneous swarms.

heading: 1 INTRODUCTION
text: We consider problems in which groups of agents learn to collaborate. The setup consists of a world, or environment, in which individual agents observe the state of the world, their own state, and possibly some partial information about the state of other agents. Out of the available information agents settle on a choice of action that determines the collection of an instantaneous reward. Our interest is in long term collaborative setups in which the team as a whole acts to maximize the sum of discounted rewards collected by all the members of the group. We restrict attention to homogeneous teams where all agents have identical dynamics and reward structures and, even if our methods work for small number of agents, we focus the effort on large swarms with up to a few hundred agents. Although having a homogeneous team is perhaps the simplest multiagent learning problem we can conceive, the challenges are still significant because the action choices of any agent can have, and most likely will have, some bearing on the actions chosen by other agents. Indeed, agents’ actions have a direct effect on the evolution of their own state, the state of the world, and the states of other agents. But this generates an indirect coupling between the actions of different agents as they reason about the collective effects of their individual choices (Eksin et al. (2013a;b)).
Collaborative homogeneous swarms are as common in robotics as they are complex. A somewhat canonical example is a collaborative navigation problem in which a group of n autonomous agents must stake positions in a set ofm surveyed points (Berman et al. (2009)). More practical examples are autonomous warehouse management (Enright & Wurman (2011)), collaborative assembly (Knepper et al. (2013)), and concurrent control and communication for teams of robots Stephan et al. (2017). A large literature exists to generate the necessary autonomous collective behavior but the inherent hardness of the problem limits their applicability to relatively small teams (Solovey & Halperin (2016)). Our goal here is to leverage the increasing success of deep neural networks in reinforcement learning (Mnih et al. (2013; 2016); Levine et al. (2015); Pathak et al. (2017); Khan et al. (2018); Gupta et al. (2017)) to develop a generic methodology for learning in the context of large scale collaborative homogeneous swarms.
In principle, we can think of the team as a whole as a system to which we apply some reinforcement learning technique. This is certainly a viable approach with interesting variations of actor-critic models having found particular success (Foerster et al. (2017); Lowe et al. (2017)). However, these
techniques are limited in their applicability to small teams with a few agents. This is not unexpected because the sample inefficiency of conventional reinforcement learning gets compounded with the exponential complexity of having agents learning with respect to each other. To circumvent this limitation we exploit the homogeneity of the team. Under this assumption it is natural to conclude that two different agents faced with the same state and information about the state of other agents must have the same policy. Therefore, we can force the learning procedure to find a common policy for all agents, an observation that constitutes the first contribution of this paper:
(C1) We formulate collaborative learning for homogeneous teams as a constrained dynamic program in which different agents are required to find a shared common policy.
In forcing all agents to find a common policy we mitigate the sample inefficiency of reinforcement learning as the experiences of any given agent inform the learning process of all other agents. The situation is not unlike meta-learning where we cross-pollinate different tasks to effectively enlarge the size of the training set (Al-Shedivat et al. (2017); Finn et al. (2017)). This similarity of purpose notwithstanding the differences are sufficiently important to warrant the development of a custom learning technique. We do so by working on a variation of the policy gradient method which we adapt to solve the collaborative learning constrained dynamic program mentioned in (C1).
Interestingly, the equivalence between policies can be incorporated into the problem formulation in several different ways (see Section 2). Our experimental results show that the most convenient formulation is one in which we introduce a (fictitious) common policy and require all agents to find policies that agree with this common policy. In order to solve this optimization we utilize a coordinate projected policy gradient algorithm whose development is the second contribution of this paper:
(C2) We develop a coordinate projected policy gradient algorithm. At each step of this iterative algorithm agents roll out trajectories according to the common policy and utilize the experience to update their individual policies. This is a policy gradient descent step along individual agent coordinates. After this update we roll out trajectories in which individual policies are pitched out against the common centralized policy. This is used to implement a policy gradient descent step on the central policy. After these two separate coordinate descent steps we project the disparate policies into a common policy and proceed to the next iteration.
We provide experimental evaluations in a collaborative navigation problem and a multi-predatormulti-prey game (from Lowe et al. (2017)), and a multiagent survival game (from Zheng et al. (2017). The numerical experiments show marked improvements in rewards relative to methods that do not force policy equivalence (Lowe et al. (2017)).

heading: 1.1 RELATED WORK
text: Multiagent reinforcement learning problems have a long history Littman (1994); Hu & Wellman (2003); Busoniu et al. (2006); Conitzer & Sandholm (2007). Early approaches focused on tabular methods to compute Q-values for Markov games (e.g, Hu & Wellman (2003)) and developed several solution methodologies for finding competitive and collaborative equilibrium (e.g., Conitzer & Sandholm (2007)). Building on the success of deep reinforcement learning there has been a recent buildup of interest in using high capacity neural network models. These include the use of neural networks in two-player games (Tampuu et al. (2017)) and in generic Bayesian games (Da Silva et al. (2006); Eksin et al. (2013a;b); Hong et al. (2018)) in which each of the agents must build a model for the behavior of other agents. In terms of novel algorithmic development, (Foerster et al. (2017)) and (Lowe et al. (2017)) propose a variation of actor-critic methods in which each agent is modeled as a decentralized actor working in conjunction with a centralized critic with parameter sharing among the agents. In Bayesian games formulations as well as in actor-critic approaches, it is possible to have a heterogeneous agent mix but it is difficult to scale the number of agents. This is different from our interest which is on leveraging homogeneity to provide scalability to large swarms. An alternative approach to achieve scalability is to work with mean field game models in which we assume the number of agents to be infinite and train policies that can be deployed on individual robots while operating on summary statistics of the team’s state (Mguni et al. (2018); Yang et al. (2017)). Our work differs in that we operate on information about the state of individual agents which can be incomplete and typically involves a few agents only.

heading: 2 MARKOV COLLABORATIVE REINFORCEMENT LEARNING
text: We consider policy learning problems in a collaborative Markov team (Littman (1994)). The team is composed of N agents generically indexed by n which at any given point in time t occupy a position xnt ∈ X in configuration space and must choose an action ant ∈ A in action space. Agents operate in a world, or environment, whose state at time t we denote as wt. The team and environment are assumed Markov so that if we collect all agents’ configurations in the vector xt := [x1t; . . . ;xNt] and all actions in the vector at := [a1t; . . . ; aNt] ∈ AN the evolution of the system is completely determined by the conditional transition probability p ( xt+1, wt+1
∣∣xt,at, wt). We further assume that agents are statistically identical in that the probability transition kernel is invariant to agent permutations. This implies the transition dynamics are the same for all agents so that if we swap two of them in configuration and action space we expect to see the same statistical evolution. The assumption is justified because the robotic swarm is assumed homogeneous.
In order to choose their actions ant, agents have access to their own states xnt, the state of the world wt and some possibly partial information I(x−nt) about the state of other agents x−nt = [xmt]m6=n. All of these variables are grouped in the local state snt = (xnt, wt, I(x−nt)). The action ant is chosen to be Markov with respect to this state. Therefore, the policy of agent n is a function πn that chooses actions according to
ant = πn(snt) = πn(xnt, wt, I(x−nt)). (1)
Observe that the policy is chosen to be Markov even though there may be advantages in keeping track of past states and past information. The team is Markov but from the perspective of an individual agent the evolution of the system is not necessarily Markov unless the information I(x−nt) is a complete description of the states of other agents. For future reference we define π := [π1; . . . ;πN ] to group the policies of all agents and π−n = [πm]m6=n to group the policies of all agents except n.
As agents operate in their environment, they collect individual rewards rn(xt, wt, ant) which depend on the configuration of the team xt, the state of the world wt and their own individual action ant. The quantity of interest to agent n is not this instantaneous reward but rather the long term reward accumulated over a time horizon T as discounted by a factor γ,
Rn := T∑ t=0 γtrn(xt, wt, ant). (2)
The reward Rn in equation 2 is stochastic as it depends on the trajectory’s realization. In conventional reinforcement learning, agent n would define the cost L̃n(πn) := Eπn(Rn) and search for a policy πn that maximizes this long term expected reward. Naturally, the expectation Eπn(Rn) implicitly depends on the policies of other agents since this would affect the transition probability p ( xt+1, wt+1
∣∣xt,at, wt). To emphasize this fact we write L̃n(πn) = Eπn,π−n(Rn) where, we recall, π−n = [πm]m 6=n represents the policies of all agents except n. Since we are interested in collaborative teams, we consider a different formulation in which agents strive to maximize the sum of accumulated rewards across all members of the team
Eπ [ N∑ n=1 Rn ] = N∑ n=1 Eπn,π−n [Rn] := N∑ n=1 Ln(πn,π−n), (3)
where we have defined Ln(πn,π−n) := Eπn,π−n [Rn] which is the component of the reward that is collected by agent n. To clarify ideas we discuss an example.
Example 1 (Collaborative Navigation) To illustrate the problem formulation consider a collaborative navigation task whereby a team of N agents are tasked with reaching N preassigned goals; see Figure 2 (left). The goals are fixed and we denote their locations as yn. The agents move to approach these goals and at each point in time t, the position of agent n is denoted as xnt ∈ R2. Agent n observes its location in space perfectly. This is the agent’s position in configuration space [cf. equation 1]. Agent n also observes perfectly the location of all goals. Thus, the state of the world available to all agents is wt = [yn; . . . ; yn]. Observe that this is an static state of the world. A time varying world state is obtained if the goals are moving around. In addition to this, agent n also observes the positions of other agents relative to its own position. I.e., the information I(x−nt)
is a collection of relative locations xmt − xnt for all m 6= n. This is a full information example. Partial information is obtained if the location of some agents is unknown or if the location of the agents is known with some error. The reward collected by agent n varies inversely with the distance ‖xnt − yn‖ to its assigned target and incorporate a negative reward for colliding with other agents. We wish to learn a policy that maximizes the sum of accumulated rewards across all members of the team [cf. equation 3]. We expect that this will induce a behavior in which all agents move to their assigned targets while avoiding collisions with each other.

heading: 2.1 OPTIMAL COMMON POLICIES
text: In the loss in equation 3 agent n collects rewards rn(xt, wt, ant) whose expectation with respect to the joint policy π is Ln(πn,π−n). The team acts as a group to make the expected cumulative reward ∑N n=1 Ln(πn,π−n) as large as possible. This would call for finding the policy π † =
argmaxπ ∑N n=1 Ln(πn,π−n). While this is indeed a sensible definition for an optimal policy, it requires learning separate policies for each individual agent. This is intractable for large N , motivating a restriction in which all agents are required to execute a common policy,
π∗n := argmax N∑ n=1 Ln(πn,π−n), s. t. πn = πm, for all n 6= m. (4)
The multi-agent reinforcement learning formulation in equation 4 takes advantage of the fact that agents are statistically identical to simplify the learning space. We emphasize that the policies π∗n in equation 5 can be different from the individual policies that compose the joint policy π † =
argmaxπ ∑N n=1 Ln(πn,π−n) even when agents are statistically identical as it may be beneficial for different agents to take different actions when faced with the same state.
The formulation in equation 4 can be further simplified with the definition of a common policy π. When we do this, we can replace the N2 constraints πn = πm by the N constraints πn = π. More importantly, the policy π−n of other agents that appears as an argument in the loss Ln(πn,π−n) can be replaced by a policy π−n in which πm = π for all m 6= n. Denoting the resulting loss as Ln(πn,π−n) = Ln(πn, π) we can reformulate equation 4 as
(π∗n, π ∗) = argmax N∑ n=1 Ln(πn, π), s. t. πn = π for all n. (5)
In the spirit of having simpler problem formulations, we can eliminate the individual policies altogether. Given that the optimal policies are such that π∗n = π
∗ for all n we can simply replace the Ln(πn, π) by Ln(π) := Ln(π, π) and remove the constraints to write
π∗ = argmax N∑ n=1 Ln(π) (6)
The problem formulations in equation 4, equation 5, and equation 6 are all equivalent. However, this doesn’t imply that algorithms to solve them are equivalent. Our experiments have shown that a projected gradient descent algorithm working on equation 5 is most effective. Therefore, the purpose of this paper is to develop a policy gradient algorithm for solving equation 5.

heading: 3 PROJECTED COORDINATE POLICY GRADIENT
text: Let us reiterate the problem in equation 4 in terms of the parameterization of the policy. Eqn 4 can be interpreted as a problem where we aim to solve is to find the best set of parameters θ∗ that parameterizes a policy πθ to maximize the sum of rewards Ri for all agents over some time horizon T . Thus parametrized version of equation 4 can be written as :
(θ∗n) = argmax N∑ n=1 Ln(θn,θ−n), s. t. θn = θm for all n 6= m. (7)
However, as stated above this problem can be intractable for large N . Rewriting the parametrized version of the more tractable optimization in Eqn 5 we get:
(θ∗n, θ ∗) = argmax N∑ n=1 Ln(θn, θ), s. t. θn = θ for all n. (8)
The difference between Eqn 7 and Eqn 8 is that we have formed N copies of θ labeled θn and put a constraint that θ = θn. This approach allows us to look at the problem in a different light. Similar to other distributed optimization problems such as ADMM Boyd et al. (2011), we can decouple the optimization over θn from that of θ. The general approach is an iterative process where
1. For each agent n, optimize the corresponding θn
2. Consolidate the θn into θ
This is often realized as a projected gradient descent where for each agent n, we apply the gradients θn ← θn + α1∇θnL(θ, θn) as well as applying a gradient θ ← θ + α2∇θ ∑N n=1 L(θ, θn). Then, in the next iteration all agents start at θn where θn is realized by taking a projection step such that θn = θ ← 1N+1 (θ + ∑N n=1 θn) is taken to satisfy the constraint in equation 8. However, when computing this projected gradient step, we need to keep track of all θn to compute the average. This is infeasible if this is done for a large number of agents. Instead a simple approximation to the projected gradient is used by setting θn ← θ. In the next subsection, we present our algorithm Distributed Multi Agent Policy Gradient or DiMA-PG and its practical implementation.

heading: 3.1 DISTRIBUTED MULTI-AGENT POLICY GRADIENTS (DIMA-PG)
text: In this section, we propose the Distributed Multi Agent Policy Gradient (DiMA-PG) algorithm which learns a centralized policy that can be deployed across all agents. Consider a population Pop from which N statistically identical agents are sampled according to a distribution P (Pop). The parameters θn of this agent-specific policy are updated by taking the gradient w.r.t θ at the specific value of θ = θ0 (where θ0 is your current central (or common) policy):
θn ← θ0 + α1∇θnLn(θn, θ)|θ=θ0,θn=θ0 (9)
where α is step size hyperparameter and L(θ, θn) is as defined in Eqn 2. Note that L(θ0, θ0) is when all agents follow policies πθ0 while L(θ0, θn) is when agent n follows πθn and all other agents follow πθ0 . We do this because, when the environment is held constant w.r.t agent, then the problem for agent n reduces to a MDP Sutton & Barto (1998).
In practice, we can take k gradient steps instead of just one as presented in Eqn 9. This can be done with the following inductive steps
θ[0]n = θ0 θ[k]n = θ [k−1] n + α2∇θnLn(θ, θn)|θ=θ0,θn=θ[k−1]n
θn = θ [k] n
(10)
Finally, we update θ:
θ ← θ + ∇θ N∑ n=1 Ln(θn, θ) (11)
Numerically, we approximate ∇θnLn(θn, θ) by drawing l trajectories where agent n uses policy πθn while all other agents uses policy πθ and averaging over the policy gradients that each trajectory provides (Williams (1992); Sutton & Barto (1998)).
Let us define the trajectory τθn when all agents are following policy πθ τθn = { [st0,θn , a t0,θ n , a t0,θ 1,...N 6=n, r t0 n ], [s t1,θ n , a t1,θ n , a t1,θ 1,...N 6=n, r t1 n ] . . . , [s tT ,θ n , a tT ,θ n , a tT ,θ 1,...N 6=n, r tT n ] }
(12)
and τθ,θnn to be the trajectory when agent n follows policy πθn and all other agents follow policy πθ. τθ,θnn = { [st0,θnn , a t0,θn n , a t0,θ 1,...N 6=n, r t0 n ], [s t1,θn n , a t1,θn n , a t1,θ 1,...N 6=n, r t1 n ],
. . . , [stT ,θnn , a tT ,θn n , a tT ,θ 1,...N 6=n, r tT n ] } (13)
The trajectories τθn and τ θ,θn n are random variables drawn from distributions Pn(τ θ n|θ) and Pn(τ θ,θn n |θ, θn) respectively. The individual agent policy parameters, θn are also random variables with distribution Pn(θn|θ). The overall optimization can be written as:
max θ
En∼P (Pop) [ Eτθn∼Pn(τθn|θ) [ Eτθ,θnn ∼Pn(τθ,θnn |θ,θn)[Ln(θn, θ)|(τ θ n, θ)] ]] (14)
Assuming, we sample N agents, Eqn. 14 can be rewritten as:
max θ
1
N N∑ n=1 [ Eτθn∼Pn(τθn|θ) [ Eτθ,θnn ∼Pn(τθ,θnn |θ,θn)[Ln(θn, θ)|(τ θ n, θ)] ]] (15)
To learn θ, we use policy gradient methods (Williams (1992); Sutton & Barto (1998)) which operate by taking the gradient of Eqn. 15. One can also use recently proposed state of the art methods for policy gradient methods (Schulman et al. (2015b;a)). The gradient for each agent in Eqn 15 (the quantity inside the sum) w.r.t θ can be written as:
∇θLn(θ, θn) = E τθn∼Pn(.|θ),τ θ,θn n ∼Pn(.|θ,θn)
[ Ln(θn, θ)∇θ log πθn(τθ,θnn ) + Ln(θn, θ)∇θn log πθ(τθn) ] (16)
The policy gradient for each agent consists of two policy gradient terms, one over the trajectories τθ,θnn sampled using (θ, θn) and another term over the trajectories τ θ n sampled using θ. It may be noted that the terms from the agent specific policy improvement when the other agents are held stationary (Eqn 10) do not appear in the final term. We show that it is possible to marginalize these terms out in the derivation for the gradient and point the reader to the appendix for a full derivation of the policy gradient. The full algorithm for DiMA-PG is presented in Algorithm 1.

heading: 4 EXPERIMENTS

heading: 4.1 ENVIRONMENTS
text: To test the effectiveness of DIMAPG, we perform experiments on both collaborative and competitive tasks. The environments from (Lowe et al. (2017)) and the many-agent (MAgent) environment from
Algorithm 1 Distributed Multi Agent with Policy Gradients (DIMA-PG) Require: Initial random central policy θ, step-size hyperparameters α1, α2, and distribution over
agent population P(Pop) 1: while True do 2: Sample N agents ∼ P(Pop) 3: for all agents do 4: Collect trajectory τθn as given in Eqn 12 and evaluate agent loss Ln(θn, θ)|θ=θ0,θn=θ0 5: Compute agent specific policy θn according to Eqn 9 6: Using θ and θn compute trajectory τθ,θn according to Eqn 13 7: end for 8: Compute policy gradient∇θLn(θn, θ) for every agent according to Eqn 16 9: Update central policy θ ← θ + ∇θ ∑N n=1 Ln(θn, θ) (Eqn 11)
10: end while
(Zheng et al. (2017)) are adapted for our experiments. We setup the following experiments to test out our algorithm :
Collaborative Navigation This task consists of N agents and N goals. All agents are identical, and each agent observes the position of the goals and the other agents relative to its own position. The agents are collectively rewarded based on the how far any agent is from each goal. Further, the agents get negative reward for colliding with other agents. This can be seen as a coverage task where all agents must learn to cover all goals without colliding into each other. We test increasing the number of agents and goal regions and report the minimum reward across all agents.
Predator Prey This task environment consists of two populations - predators and preys. Prey are faster than the predators. The environment is also populated with static obstacles that the agents must learn to avoid or use to their advantage. All agents observe relative positions and velocities of other agents and the positions of the static obstacles. Predators are rewarded positively when they collide with the preys and the preys are rewarded are negatively.
Survival This task consists of a large number of agents operating in an environment with limited resources or food. Agents get reward for eating food but also get reward for killing other agents (reward for eating food is higher). Agents must either rush to get reward from eating food or monopolize the food by killing other agents. However, when the agents kill other agents they incur a small negative reward. Each agent’s observations consists of a spatial local view component and a non spatial component. The local view component encodes information about other agents within a range while the non spatial component encodes features such as the agents ID, last action executed, last reward and the relative position of the agent in the environment.

heading: 4.2 EXPERIMENTAL RESULTS
text: For all experiments, we use a neural network policy that consists of two hidden layers with 100 units each and uses ReLU nonlinearity. For the collaborative navigation task, we use the vanilla policy gradient or REINFORCE (Williams (1992)) to compute updates (θn) and TRPO (Schulman et al. (2015a)) to compute θ. For the Predator Prey and Survival tasks we switch to using REINFORCE for
both θ and θn. To establish baselines, we compare against both centralized and decentralized deep MARL approaches. For decentralized learning, we use MADDPG from (Lowe et al. (2017)) using the online implementation open sourced by the authors. Since the authors in Lowe et al. (2017) already show MADDPG agents work better than other methods on the exact same environments that we are using, where individual agents are trained by DDPG, REINFORCE, Actor-Critic, TRPO, DQN, we do not re implement those algorithms. Instead, we implement a centralized A3C (Actor-Critic) (Mnih et al. (2016)) and centralized TRPO that take in as input the joint space of all agents observations and output actions over the joint space of all agents. We call this the Kitchensink approach. Details about the policy architecture for A3C_Kitchenshink and TRPO_Kitchensink are provided in the appendix.

heading: 4.2.1 COLLABORATIVE NAVIGATION
text: We setup collaborative navigation as described in Section 4.1. Agents are rewarded for being close to the goals (negative square of distance to the goals) and get negatively rewarded for colliding into each other or when they step out of the environment boundary. We also observe that in order to stabilize training, we need to clip our rewards in the range [-1,1]. We use a horizon T = 200 after which episodes are terminated. Additional hyper parameters are provided in the Appendix.
We run our proposed algorithm and baselines on this environment when number of agents n = 3 and n = 10. Since the baselines A3C_Kitchenshink and TRPO_Kitchensink operate over the joint space, they are setup to maximize the minimum reward across all agents. To have a fair comparison among baselines, we report the minimum reward across all agents. The training curve for our tasks can be seen in Fig 3. We notice that for the simple case, A3C_Kitchenshink performs very well and quickly converges. This is expected since the number of agents is low and the dimensionality of the input space is not large. TRPO_Kitchenshink and MADDPG perform worse and while they converge, the con-
vergence is only seen after 300-400k episodes. When n is increased to ten, we observe that only DIMAPG is able to quickly learn policies for all agents.
In our initial hypothesis, we sought to use θ across all agents since we assumed that the policies for all agents in a given population live close to each other in parameter space. We observe from Table 1 that after training using θ or θ′i (after k-shot adaptation from θ) yields almost similar results thus, verifying our hypothesis. We also consider the case where we train only 1 agent and then fine tune the same policy across all agents. We observe that this yields poor results when the number of agents are increased and is indicated by the "Fine Tune" entry in Table 1

heading: 4.3 PREDATOR PREY
text: The goal of this experiment is to compare the effectiveness of DIMAPG on competitive tasks. In this task, there exist 2 populations of agents; predators and preys. Extending our hypothesis to this
task, we would like to learn a single policy for all predators and a single policy for all preys. It is important to note that even though, the policies are different, they are trained in parallel which in the centralized setup enables us to condition each agents trajectory on the actions of other agents even if they are in a different population. We experiment with two scenarios; 12vs1 and 3vs1 predator prey games where the prey are faster than the predator. The horizon used is T = 200.
Our results are presented in Fig 4. We observe that DIMAPG is able to effectively learn better policies than both MADDPG and the centralized Kitchensink methods on this competitive task. Similar results with DIMAPG are achieved even when the number of predators and preys are increased.

heading: 4.4 SURVIVAL
text: The goal of this experiment is to demonstrate the effectiveness of DIMAPG on environments with a large number of agents. The environment is populated with agents and food (the food is static particles at the center). Agents must learn to survive by eating food. To do so they can either rush to gather food and get reward or monopolize the food by first killing other agents (killing other agents results in a small negative reward). We use DIMAPG to learn the central policy that is deployed across all agents by randomly sampling N agents from the population. We roll out each episode for a horizon of T = 200. Each environment is populated with 160 food particles (eating one food particle yields a reward of +5). For this task, it is infeasible to train the other baselines and hence we do not benchmark for this experiment.
We gauge the performance of DIMAPG on this task by evaluating the number of surviving agents and the food left at the end of the episode as well as the average reward over agents per episode.(Table 2). It is observed in the case when N = 225, the agents do not kill each other and instead learn to gather food. When the number of agents is increased to N = 630 agents close to the food rush in to gather food while those further away start killing other agents.

heading: 5 CONCLUSION AND OUTLOOK
text: Thus, in this work we have proposed a distributed optimization setup for multi-agent reinforcement learning that learns to combine information from all agents into a single policy that works well for
large populations of homogeneous agents. We show that our proposed algorithm performs better than other state of the art deep multi agent reinforcement learning algorithms when the number of agents are increased. In future work, we intend to explore the idea of learning a policy for teams of heterogeneous agents.

heading: A DERIVATION FOR MULTI-AGENT POLICY GRADIENT
text: Following Section 3.1, the overall optimization problem for distributed multi agent reinforcement learning was given as :
max θ
En∼P (Pop) [ Eτθn∼Pn(τθn|θ) [ Eτθ,θnn ∼Pn(τθ,θnn |θ,θn)[Ln(θn, θ)|(τ θ n, θ)] ]] (17)
where trajectories τθn and τ θ,θn n are random variables with distributions Pn(τ θ n|θ) and Pn(τθ,θnn |θ, θn) respectively. Assuming, we sample N agents, the above Eqn 17 can be rewritten as:
max θ
1
N N∑ n=1 [ Eτθn∼Pn(τθn|θ) [ Eτθ,θnn ∼Pn(τθ,θnn |θ,θn)[Ln(θn, θ)|(τ θ n, θ)] ]] (18)
Let : Ln(θn, θ) = [ Eτθn∼Pn(τθn|θ) [ Eτθ,θnn ∼Pn(τθ,θnn |θ,θn)[Ln(θn, θ)|(τ θ n, θ)] ]] (19)
Since it is required that we maximize only over theta, we are interested in marginalizing θn. Expanding all expectations we can write:
Ln(θn, θ) = ∫ ∫ ∫ Ln(θn, θ)Pn(τ θ,θn n |(θ, θn))Pn(θn|θ, τθn)Pn(τθn|θ)dτθndτθ,θnn dθn (20)
Assuming, we use the k gradient steps instead of just one as presented in Eqn 10 in the main paper, this can be rewritten as :
Ln(θn, θ) = ∫ Ln(θn, θ)Pn(τ θ,θn n |(θ, θn))Pn(θ[k]n |θ[k−1]n , τ θ[k−1]n n )Pn(θ [k−1] n |θ[k−2]n , τ θ[k−2]n n ) . . .
Pn(θ [1] n |θ[0]n , τ θ[0]n n )Pn(τ θ n|θ)dτθndτ θ,θ[0]n n dτ θ,θ[1]n n . . . dτ θ,θ[k]n n dθn
(21)
The term Pn(θn|θ, τθn)dθn in the above Eqn 20 can be integrated out if we assume a delta distribution for Pn(θn|θ, τθn):
Pn(θn|θ, τθn) = δ ( θ0 + α1∇θnLn(θn, θ)|θ=θ0,θn=θ0 ) (22)
A similar observation can be made for the intermediate terms Pn(θ [1] n |θ[0]n , τθ [0] n n ), Pn(θ [2] n |θ[1]n , τθ [1] n n ), . . ., Pn(θ [k] n |θ[k−1]n , τθ [k−1] n n ) in the above Eqn 21. Thus after integrating these terms out (in the above Eqn 20 or 21, we are left with:
Ln(θn, θ) = ∫ ∫ Ln(θn, θ)Pn(τ θ,θn n |(θ, θn))Pn(τθn|θ)dτθndτθ,θnn (23)
Taking the gradient of this above equation 23, rewriting the probability distributions in the policy form and rewriting it as an expectation form we get:
∇θLn(θn, θ) = E τθn∼Pn(.|θ),τ θ,θn n ∼Pn(.|θ,θn)
[ Ln(θn, θ)∇θ log πθn(τθ,θnn ) + Ln(θn, θ)∇θn log πθ(τθn) ] (24)

heading: B CONNECTION TO META-LEARNING
text: We observe that there exists a natural connection between our proposed distributed learning and gradient based meta-learning techniques such as the one used in [23,24]. We briefly introduce gradient based meta-learning here and draw connections from our work to that of meta-learning.
B.1 MODEL-AGNOSTIC META LEARNING (MAML)
Consider a series of RL tasks Ti that one would like to learn. Each task can be thought of as a Markov Decision Process (MDP)M(S,A,R,P ′) consisting of observations s ∈ S, actions a ∈ A, a state transition function P ′(st+1|st, at) and a reward function R(st, at). To solve the MDP (for each task), one would like to learn a policy π : s→ a that maximizes the expected sum of rewards over a finite time horizon H , maxπ[ ∑H t=1Rt(st, at)]. Let the policy be represented by some function fθ where θ is the initial parameters of the function.
In MAML [24] the authors show that, it is possible to learn a policy πθ which can be used on a task Ti to collect a limited number of trajectories τθ or experience D and quickly adapt to a task specific policy πθ′i that minimizes the task specific loss LTi(τθ) = −Est,at∼τθ [ ∑H t=1Rt(st, at)]. MAML learns task specific policy πθ′i by taking the gradient of LTi(τθ) w.r.t θ. This is then followed by collecting new trajectories τθ′i or experience set D ′ i using πθ′i in task Ti. θ is then updated by taking the gradient of LTi(τθ′i) w.r.t θ over all tasks. The update equations for θ ′ and θ are given as:
θ′i := θ − α∇θLTi(τθ), θ := θ − β∇θ ∑ Ti LTi(τθ′i) (25)
where α and β are the hyperparameters for step size. Authors in [23] extend MAML to show that one can think about MAML from a probabilistic perspective where all tasks, trajectories and policies can be thought as random variables and θ′ is generated from some conditional distribution P (θ′|θ, τθ).
B.2 DISTRIBUTED OPTIMIZATION FOR MULTI AGENT SYSTEMS
We observe the meta-policy πθ that MAML attempts to learn and uses as an initialization point for the different tasks is similar in spirit to the central policy θ DIMAPG attempts to learn and execute on all agents. In both, approaches θ captures information across multiple tasks or multiple agents. An important difference between our work and MAML or meta-learning is that during execution (post training) we execute θ while MAML uses θ to do a 1-shot adaptation for task Ti and then executes θ′i on Ti. Another interesting point to note here is the difference in the trajectories τθ′i that is used by MAML and the trajectory τθ,θnn that is used by DIMAPG to update task or agent specific policy θ ′ i or θn. In the distributed optimization for multi-agent setting, due to the non-stationarity, it is absolutely necessary that we ensure the other agents are held constant (to θ) while agent n is optimizing its task specific policy θn. MAML has no such requirement.

heading: C EXPERIMENTAL DETAILS
text: C.1 A3C KITCHENSINK AND TRPO KITCHENSINK
For A3C KitchenSink, we input the agents observation and reshape it into a n×m matrix. This is then fed into a 2D convolution layer with 16 outputs, Elu activation and a kernel size of 2, stride of 1. The output from this layer is fed into another 2D convolution layer with 32 outputs,Elu activation and a kernel size of 2, stride of 1. The output from this layer is flattened and fed into a fully connected layer with 256 outputs and Elu activation. This is followed by feeding into a LSTM layer with 256 hidden units. The output from the LSTM is then fed into two separate fully connected layers to get the policy estimate and the value function estimate. Actor-critic loss is setup and minimzied using Adam with learning rate 1e-4. For TRPO Kitchensink, we setup similar policy layer and value function layer.
C.2 DIMAPG
For this task, we used a neural network policy with two hidden layers with 100 units each. The network uses a ReLU non-linearity. Depending on the experiment we compute agent specific gradient updates using REINFORCE and TRPO for the central policy gradient updates. The baseline is fitted separately at each iteration for all agents sampled from the population. We use the standard linear feature baseline. The learning rate for agent specific policy updates α1=α2=0.01. Learning rate for
central policy updates = 0.05. In practice, to adapt θ to θn we do multiple gradient steps. We observe k=3 (number of gradient steps) is a good choice for most tasks. For both θ and θn updates, we collect 25 trajectories.
C.3 PREDATOR PREY
For the predator prey experiment, we would also like to report additional results showing that after termination, the DIMAPG agents are able to learn faster than the agents trained using other baselines.
C.4 SURVIVOR
In this experiment, the environment is populated with agents and food particles. The agents must learn to survive by eating food. To do so they can either rush to gather food and get reward or monopolize the food by first killing other agents (killing other agents results in a small negative reward). Each agent in this environment also has orientation. The agents can either chose to one of 12 neighboring cells or stay as is, or chose to attack any agent or entity in 8 neighboring cells. Finally the agent can also choose to turn right or left. At every step, the agents receive a "step reward" of -0.01. If the agent dies, its given a reward of -1. If the agent attacks another agent, it receives a penalty of -0.1. However, if it chooses to attack another agent by forming a group it receives an award of 1. The agent also gets a reward of +5 for eating food.
As stated in the main paper, it is observed that in the case when N = 225, the agents do not kill each other and instead learn to gather food. When the number of agents is increased to N = 630 agents close to the food rush in to gather food while those further away start killing other agents. We present a snapshot of the learned policy in Figure 1 and Figure 2.

Review summaries:
The authors present an approach to training collaborative swarms of agents based around giving all agents identical (or near identical) policies. The training regime involves individual agents rolling out trajectories based on slight perturbations of an agent of focus keeping the policy of other agents fixed. This is repeated for each agent, then these trajectories are used to batch update the joint policy with an average gradient.