Intention Propagation for  Multi-agent Reinforcement Learning
Authors: Chao Qu
Hui Li
Chang Liu
Junwu Xiong
james zhang
Wei Chu
Weiqiang Wang
Yuan Qi
Le Song
Venue:  (2021)

Abstract: A hallmark of an AI agent is to mimic human beings to understand and interact with others. In this paper, we propose a \emph{collaborative} multi-agent reinforcement learning algorithm to learn a \emph{joint} policy through the interactions over agents. To make a joint decision over the group,  each agent makes an initial decision and tells its  policy to its neighbors. Then each agent modifies its own policy properly based on received messages and spreads out its plan. As this intention propagation procedure goes on, we prove that it converges to a mean-field approximation of the joint policy with the framework of neural embedded probabilistic inference. We evaluate our algorithm on several large scale challenging tasks and demonstrate that it outperforms previous state-of-the-arts.

Under review as a conference paper at ICLR 2021
INTENTION PROPAGATION FOR MULTI-AGENT REIN- FORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
A hallmark of an AI agent is to mimic human beings to understand and interact with others. In this paper, we propose collaborative multi-agent reinforcement learning algorithm to learn a joint policy through the interactions over agents. To make joint decision tells its policy to its neighbors. Then each agent modifies its own policy properly based received messages and spreads out its plan. As this intention propagation procedure goes on, we prove that it converges to mean-field approximation of the joint policy with the framework of neural embedded probabilistic inference. We evaluate our algorithm on several large scale challenging tasks and demonstrate that outperforms previous sate-off-the-rr
the group, each agent makes an initial decision and
INTRODUCTION
Collaborative multi-agent reinforcement learning is an important sub-field of the multi-agent rein- forcement learning (MARL), where the agents learn to coordinate to achieve joint success. It has wide applications in traffic control (Kuyer et al. 2008), autonomous driving (Shalev-Shwartz et al.) 2016) and smart grid (Yang al. 2018). To learn coordination, the interactions between agents are indispensable. For instance, humans can reason about other's 's behaviors or know other peoples' intentions through communication and then determine an effective coordination plan. However, how to design a mechanism of such interaction in a principled way and at the same time solve the large scale real-world applications is still challenging problem.
Recently, there is a surge of interest in solving the collaborative MARL problem (Foerster et al. 2018 Qu al. 2019 Lowe et al., (017). Among them, joint policy approaches have demonstrated their superiority (Rashid et al. [2018] Sunehag et al.) 2018 Oliehoek et al. 2016). A straightforward approach is to replace the action the single-agent reinforcement learning by the joint action a = (a1, a2,..., a,), while it obviously suffers from the issue of the exponentially large action space. Thus several approaches have been proposed to factorize the joint action space to mitigate such issue, which be roughly grouped into two categories:
Factorization on policy. This approach explicitly assumes that (als) == Ih (s(a)))), i.e., policies are independent (Foerster et al.) 2018) Zhang et al.) 2018). To mitigate for the instability issue caused by the independent learner, it generally needs centralized critic.
Factorization on value function. This approach has a similar spirit but factorizes the joint value function into several utility functions, each just involving the actions of one agent (Rashid al. 2018: Sunehag et al. 20188.
However, these two approaches lack of the interactions between agents, since in their algorithms agent i does not care about the plan of agent j. Indeed, they may suffer from phenomenon called relative over-generalization game theory observed by Wei Luke (206)) Castellini et al. (2019); Palmer et al. (2018). Approaches based the coordinate graph would effectively prevent such cases, where the value function is factorized as a summation of utility function on pairwise or local joint action (Guestrin et al. 2002; Böhmer et al. 2020). However, they only be applied in discrete action, small scale game.
Furthermore, despite the empirical success of the aforementioned work in certain scenarios, it still lacks theoretical insight. In this work, we only make a simple yet realistic assumption: the reward function r; of each agent just depends on its individual action and the actions of its neighbors (and

---

Under review as a conference paper at ICLR 2021
state), i.e.
(1) where we use N₂ to denote the neighbors of agent i, s to denote the global state. It says the goal or decision of agent is explicitly influenced by a small subset Ns of other agents. Note that such an assumption is reasonable in lots of real scenarios. For instance,
as( = as.
The traffic light an intersection makes the decision on the phase changing mainly relying on the traffic flow around it and the policies of its neighboring traffic light.
The main goal of defender in a soccer game is tackle the opponent's ss attacker, while he rarely needs to pay attention to opponent goalkeeper's is strategy.
Based on the assumption in equation 1 we propose a principled multi-agent reinforcement learning algorithm in the framework of probabilistic inference, where the objective is to maximize the long term reward of the group, i.e., Ei= En r'r (see details in section 4b.
Note since each agent's s reward depends on its neighbor, we still need a joint policy to maximize the global reward through interactions. In this paper, we derive an iterative procedure for such interac- tion to learn the joint policy in collaborative MARL and name intention propagation. Particularly,
In the first round, each agent makes an independent decision and spreads out his plan (we name intention) to neighbors.
In the second round, agents changes its initial intention properly based on its neighbors' intention J E N and propagates its intention i. again. In the third round, it changes the decision in the second round with similar argument.
As this procedure goes on, we show the final output of agents' policy converges to the mean field
approximation (the variational inference method from the probabilistic graphical model (Bishop 2006)) of the joint policy.
In addition, this joint policy has the form of Markov Random Field induced by the locality of the reward function (proposition [] Therefore, such a procedure is computationally efficient when the underlying graph is sparse, since in each round, each agent just needs to care about what its neighbors intend to do. Remark: (1) Our work is not related to the mean-field game (MFG) (Yang) jet al. 2018). The goal of the MFG is to find the Nash equilibrium, while our work aims to the optimal joint policy in the collaborative game. Furthermore, MFG generally assumes agents identical and interchangeable. When the number of agents goes to infinity. MFG can view the state of other agents population state distribution. In problem, do not have such assumptions. (2) our analysis is not limited to the mean-field approximation. When we change the message passing structure of intention propagation, we show that it converges other approximation of the joint policy, e.g., loopy belief propagation in variational inference (Yedidia et al. 2001 (see Appendix B.2)
Contributions: (1) We propose a principled method named intention propagation to solve the joint policy collaborative MARL problem; (2) Our method is computationally efficient, which can scale up to one thousand agents and thus meets the requirement of real applications; (3) Empirically, outperforms state-of-the-art baselines with a wide margin when the number of agents is large; (4) Our work builds a bridge between MARL and neural embedded probabilistic inference, which would lead to new algorithms beyond intention propagation.
of and at represent the state and action of agent i at time step t. The neighbors of agent i are represented as N,. We denote as a random variable with domain and refer to instantiations of X by the lower case character x. We denote density on X' by p(x) and denote the space of all such densities as by P.
Notation:
2 RELATED WORK
We first discuss the work of the factorized approaches on the joint policy. COMA designs a MARL algorithm based on the actor-critic framework with independent actors 7, (a(as)) where the joint policy is factorized as (als)) = -IN n. (agls) (Feesteer et al. 2018). MADDPG considers a MARL competitive setting, where it creates critic for each agent (Lowe et al.)
with the cooperative 2017]. Other similar works may include (de Witt et al., 2019; Wei et al., 2018). Another way is to factorize the value functions into several utility functions, (Sunehag et al. (2018) assumes that the
2

---

Under review as a conference paper at ICLR 2021
overall Q function can be factorized as Q(s, 01, d2,,.,.a3 ax) = Qi(s;, 0:) QMIX extends this work to include a richer class of function, where it assumes the overall Q function is a monotonic function w.r.t each (s;, a4) (Rashid et al., 2018). Similarly, Son et al. (2019) further relax the structure constraint on the joint value function. However these factorized methods suffer from the relative overgeneralization issue (Castellini et al. 2019 Palmer et al.) (018). Generally speaking, it pushes the agents to underestimate a certain action because of the low rewards they receive, while they could get a higher one by perfectly coordinating.
A middle ground between the (fully) joint policy and the factorized policy is the coordination graph (Guestrin et al. 2002). where the value function factorized as a summation of the utility function on the pairwise action. Böhmer et al. (2020); Castellimi et al. (2019) combine deep learning techniques with the coordination graph. It addresses the issue of relative overgeneralization, but still has two limitations especially in the large scale MARL problem.
(1) The max-sum algorithm can just be implemented in the discrete action space since it needs a max-sum operation on the action of Q function. (2) Even in the discrete action case, each step of the Q learning has to do several loops of max-sum operation over the whole graph if there is a cycle in graph. Our algorithm can handle both discrete and continuous action space cases and alleviate the scalability issue by designing an intention propagation network.
Another category of MARL is to consider the communication among agents. The attention mecha- nism is used to decide when and who to communicate with (Das et al.] 2018). Foerster et al. (2016) propose end-to-end method to learn communication protocol. In (Liu et al.] 2019) Chu et al. 2020), each agent sends the action information to it neighbors. In addition, [Chu et al. (2020) require strong assumption that the MDP has the spatial-temporal Markov property. However, they utilizes neighbor's s action information in a heuristic way and thus it is unclear what the agents are learning (e.g., do they learn the optimal joint policy to maximize the group reward? ) Jiang et al. (2020) propose DGN which uses GNN to spread the state embedding information to neighbors. However each agent still uses an independent Q learning to learn the policy and neglects other agents' plans. In contrast, we propose principled algorithm, where each agent makes decision considering other agents' plan. Such procedure can be parameterized by GNN and other neural networks (see section and appendix B.2). We prove its convergence to the solution of variational inference methods.
BACKGROUNDS
Probabilistic Reinforcement Learning: Probabilistic reinforcement learning (PRL) Levine 2018) is our building block. PRL defines the trajectory т up to time step T as T 5t 1 a 8² "..,a..., ".,"".""""" a², S The probability distribution of the trajectory
induced by d²)). While the probability of the trajectory т under the policy T[ass) is defined as p(T) p(s") IT== p(s ( (a'ss"" ). The objective is to minimize the KL divergence between ((F)
the optimal policy is defined as p(r)
II= p(s*+1 st as,, ex
and p(7). It is equivalent to the maximum entropy reinforcement learning
T
max J((T)
Σ Elr(st, + H(T((aa)s)))
where it omits the discount factor y and regularizer factor a of the entropy term, since easy to incorporate them into the transition and reward respectively. Notice in this framework the max operator the Bellman optimality equation would be replaced by the softmax operator and thus its optimal policy is a softmax function related to the Q function (Haarnoja et al.] 2017). Such framework subsumes state-of-the-art algorithms such as soft-actor-critic (SAC) (Haarnoja et al.) 2018). In each iteration, SAC optimizes the following loss function of Q,T,. V. and respectively.
Beer,a [Q(" a²) - rss' a²) - -p (V( 2]]
TE Bug (log π (aa (s*) (s ,a))
EgED (s*)) - Eatana [Q('"1 a²) - log (a') s']]] where D is the replay buffer.
Function Space Embedding of Distribution: In our work, we use the tool of embedding in Re- producing Kernel Hilbert Space (RKHS) to design an intention propagation procedure (Smola et al.) 2007). We let o(X) be implicit feature mapping and X be random variable with distribution p(z). Embeddings of p(z) is given by px := Ex [xX)] = I @(x)p(z)dd where the distribution mapped to its expected feature map. By assuming that there exists feature space such that
3

---

Under review as a conference paper at ICLR 2021
sufficient statistic of the density, i.e., any information we need from the density is preserved in fax (Smola et al. 2007). Such injective assumption generally holds under mild condition (Sriperumbudur al. 2008 This property is important since we can reformulate a functional f P - lK of pl-) using the embedding only, i.e., f(p(z)) = f(ux). It also can be generalized to the operator case. In particular, applying an operator P I to a density can be equivalently carried out using its embedding T o p(z) T oxx, where T F - Ed is the alternative operator working on the embedding. In practice, μxx I and 7 have complicated dependence on d. As such, we approximate them by neural networks, which is known as the neural embedding approach of distribution (Dai et al. 2016).
the embeddings are injective, we treat the embedding дx of the density p(z)
4
OUR METHOD
In this section, we present our method intention propagation for the collaborative multi-agent re- inforcement learning. To begin with, we formally define the problem as networked MDP. The network is characterized by a graph G = (V.E), where each vertex i E V represents an agent and the edge ij & means the communication link between agent and j. We say i.j are neighbors they are connected by this edge. The corresponding networked MDP is characterized by a tuple ((S,) 1 (AA,), P. fr; {r.), ",,))))) where N is the number of agents, S, is the local state of the agent and A, denotes the set of action available to agent i. We let S == I S; and A := II== A, be the global state and joint action space respectively. At time step t 1, the global state s S is drawn from the transition s g ~ p(-ls", conditioned on the current state s' and the joint action a' = (af, .b.....)))) E A. Each transition yields a reward rf = ri( at) for agent and y is the discount factor. The aim of our algorithm is to learn a joint policy x (aa1s)) to maximize the overall long term reward (with an entropy term H(-1s) on the joint action a)
(TT) = E
of H((-s'))),
where each agent can just observe its own state 8; and the message from the neighborhood com- munication. We denote the neighbors of agent i as N₁, and further assume that the reward r; depends on the state and the actions of itself and its neighbors, i.e., Ti a) := rs ag av,). ). Such assump- tion reasonable in many real scenarios as we discussed in the introduction. In the following, we start the derivation with the fully observation case, and discuss how to handle the partial observation later. The roadmap of the following derivation At the beginning. we prove that the optimal policy has Markov Random Field (MRF) form, which reduces the exponential large searching space to a polynomial one. However implement MRF policy is not trivial in the RL setting (e.g., sample an action from the policy). Thus we sort to the varational inference method (focus on mean field approximation in the main paper and leave other methods in the appendix). But it would introduce complicated computations. At last we apply the kernel embedding method introduced in section to solve this problem and learn the kernel embedding by neural networks. We also discuss how to handle the partially observable setting.
4.1 REDUCE POLICY SEARCHING SPACE
Recall that our aim is to maximize the long term reward with the entropy term. Therefore, we follow the definition of the optimal policy in the probabilistic reinforcement learning in [Levine 2018) and obtain the proposition I It says under the assumption ri(s, a) = ri as, aN,). the optimal policy in the form of Markov Random Field (MRF). We prove the following proposition in [.I
Proposition 1 The optimal policy has the form n (a = 2/2 exp(EN Vi(s", atj ax,)), where Z is the normalization term.
This proposition is important since it suggests that we should construct the policy (aalss)) with this form, e.g., parametric family, to contain the optimal policy. If agent and its neighbors compose a clique, the policy reduces to MRF and & is the potential function. One common example is that the reward is a function on pairwise actions, i.e., r(s.a) Eiey a:) + Σ r(s, as az). Then the policy has the form
TTa = Z
1
exp( (s) +
Σ (r.(s,
1EV
(K.))E
4

---

Under review as a conference paper at ICLR 2021
which is the pairwise MRF. For instance, in traffic lights control, we can define 2-D grid network and the pairwise reward function. The MRF formulation on the policy effectively reduces the policy space comparing with the exponentially large one in the fully connected graph.
A straightforward way to leverage such observation is to define a Ta ma(a" ss') as a MRF, and then apply the policy gradient algorithm, e.g., the following way in SAC. VoEg log (a Qu a-)]- However it is still very hard to sample joint action a' from (a(a"(s"). In the next section, we resort to embedding alleviate such problem.
Recall the remaining problem is how to sample the joint action from a MRF policy. Classical ways include the Markov Chain Monte Carlo method and variational inference. 'he former provides the guarantee of producing exact samples from the target density but computationally intensive. Therefore it is not applicable in the multi-agent RL setting, since we need to sample action once in each interaction with the environment. As such, we advocate the second approach. Here we use the mean-fiele approximation for the simplicity of presentation and defer more variational inference methods, e.g., loopy belief propagation, in Appendix(B2 We use an intention propagation network with the embedding of the distribution to represent the update rule of the mean field approximation.
Mean field approximation. We hope to approximate the x² (als) by the mean-field variational family Ps
N I (a (als)),
min
(P1.P2....M) 1=1
where we omit the superscript to simplify the notation.
We denote the optimal solution of above problem as gi- Using the coordinate ascent variational inference,the optimal solution qi should satisfy the following fixed point equation (Bishop 2006). Since the objective function is (generally)
non-convex, such update converges to a local optimum Blei et 2017
(agls) x exp /
II gs (a,ls) log x" (a s))a. jit
(2)
For simplicity of the representation, in the following discussion, we assume that the policy is pairwise MRF but the methodology applies to more general case with more involved expression. Particularly, we assume x =als) 1 exp(Eiev (s, E(iyes bhy (s, a, a,,a))) a,)). We plug this into equation 2 and obtain following fixed point equation.
log (a,ls) c; + (s,0,)) + Σ (Lalaal)))) a, a,)a,, JEN;
(3)
where o; is some constant that does not depend on a;-
We can understand this mean-field update rule from the perspective of intention propagation. Equa- tion basiially says each agent can not make the decision independently. Instead its policy yi should depend on the policies of others, particularly the neighbors in the equation. Clearly, if we con- struct the intention propagation corresponding to equation the final policy obtained from intention propagation will converge to the mean-field approximation of the joint policy. However directly apply this update in our algorithm, since it includes a complicated integral. To this end in the next section resort the embedding of the distribution qi (Smola al. 2007). which maps the distributions into reproducing kernel Hilbert space.
can not
Embed the update rule Observe that the fixed point formulation equation says that q;(a;[s) is a functional of neighborhood marginal distribution {ay(asl)) ((a]ss) f(a,. (eN.). Denote the d-dimensinoal embedding of qソ (a [s) by jy I [ (()()))((ays))dd
i.e..
Notice the form of feature ó is not fixed at the moment and will be learned implicitly by the neural network. Following the assumption that there exists feature space such that the embeddings are injective in Section 3 have the fixed point formulation as
we can replace the distribution by its embedding and
q:(a:ls) = J(ai, ((s))
(4)
For more theoretical guarantee on the kernel embedding, e.g., convergence rate on the empirical mean of the kernel embedding, please refer to (Smola et al. 2007). Roughly speaking, once there
5

---

Under review as a conference paper at ICLR 2021
ANNO
(a) Message Passing
(b) Parameterization of GNN
Figure 1: (a) Illustration of the message passing of intention propagation Ag(als) ( (equation 5 (b) An instance of 2-layer GNN with the discrete action outputs (n agents).
enough data, can believe the learned kernel embedding is close enough to the true kernel embedding. Therefore the update of equation 4 and equation i the following would converge to the fixed point of equation 2 Remind that in section at both sides
do integration w.r.t. the s(as, 8, (ūz) beN, ( Thus
feature map Φ, which yields, b4 J qu (a: ())((s [s)da we can rewrite as a new operator on the embedding, which induces a fixed point equation again i = To o (s, (As)eeN) ). In practice, we do this fix-point update with M iterations.
p F (8, (af"""""eae }JNN,) m 1,,,,,,,, M.
(5)
Finally, we output the distribution qi with gi (a, = f(a;, 8, (in])ee In next section, we show how to represent these variables by neural network.
Parameterization by Neural Networks. In general f and T have complicated dependency on ei and Φb Instead of learning such dependency, we directly approximate o and T by neural networks. For instance, we can represent the operator T in eq é = oW Wis++ W2 ΣjEN, (y)) where a is a nonlinear activation function, W1 and W2 are some matrixes with row number equals to d. Interestingly, this is indeed message passing form of Graph Neural Network (GNN) (Hamilton) et al. 2017). Thus we can use M-hhp (layer) GNN to represent the fixed-point update in eq If the action space is discrete, the output qi (a:]s) () is a softmax function. In this case f is fully connected layer with softmax output. When it is continuous, we can output Gaussian distribution with the reparametrization trick (Kingma & Welling, 2019). We denote this intention propagation procedure as intention propagation network Ag with parameter in Figure
Figure M ()) illustrates the graph and the message passing procedure. Agent I receives the embedding (intention) p 135 1-m-1 P 1 from its neighbors, and then updates the its own embedding with operator 7 and spreads its new embedding i the next iteration. Figure (b) gives the details on the parameterization of GNN. Here use agent I as example. To ease the exposition, assume agent just has one neighbor, agent 2. Each agent observes its own state s,. After a MLP and softmax layer (we do not sample actions here, but just use the probabilities of the actions), we get a embedding p:0, which is the initial distribution of the policy. Then agent 1 receives the embedding رo of its neighbor (agent 2). After GNN layer to combine the information, e.g, Ai Relu (s) + 82) ) + ( + (W,, W2 are shared across all agents as that in GNN), we obtain new embedding Ø1 of agent 1. Notice we also do message passing on state, since in practice the global state is not available. In the second layer, we do similar things. We defer detailed discussion and extension to other neural networks Appendix B due space constraint.
4.2 ALGORITHM
We are ready to give the overall algorithm by combining all pieces together. All detailed derivation on V, Q, for agent and the corresponding loss function will be given in the appendix [ due to the space constraint. Recall we have mean-field approximation gi of the joint-policy, which is obtained by M iterations of intention propagation. We represent this procedure by M-hop graph neural network with parameter 8 discussed above. Notice that this factorization is different from the case (als) = I| x [a, (s) in Zhang et al. 2018 Foerster et al. 2018), since (aa))s) depends on the information of other agents' plan. Using the mean helld approximation g:. we can further decompose
Q Q= E Q and V = > Vi, see appendix [ We use neural networks to approximate Vi and Qi function with parameter 77, and K; respectively. As that in TD3 (Fujimoto et al., 20188), for each agent i we have a target value network Vy, and two Qx, functions to mitigate the overestimation by training them simultaneously with the same data but only selecting minimum of them as the

---

also do the message passing on the state embedding with the graph neural Under review as a conference paper at ICLR 2021
predbeor1
predetor
Landmark
proy
Agent3
Landmark
predeters
Figure 2: Experimental scenarios. Cityflow: Manhattan, Predator-Prey and Cooperative-Navigation
target in the value update. In the following we denote qi (a:]s) as (a)(a) to explicitly indicate its dependence on the intention propagation network Ag. We use D denote the replay buffer. The whole algorithm is presented in Algorithm
Loss Functions. The loss of value function Vj:
((x) = E (6*) ak 19x at axx) log (ca(a(b"))) 9.
The loss of Q:: (R:)) B( DDD ol (Qxs (s", at axx) 2,(s' ab af,
where (s", a d'x)) = r; + BB, (p((len [V (s (s)
N
N
The loss of policy: (() D.
log q, p(ats')
Σ an at axx)] ).
i=1
It is interesting to compare the loss with the counterpart in the single agent SAC in section 3
(.,((a)))) the output of intention propagation network A*(als) parameterized by graph neural network. Thus it depends on the policy of other agents.
Qx, depends on the action of itself and its neighbors, which can also be accomplished by the graph neural network in practice.
Algorithm Intention Propagation
Inputs: Replay buffer D. V₁, Qe for each agent i. Intention propagation network Ag Ag [s) with
N.N outputs (g:.0 f==1- Learning rate l,; lo Moving average parameter for the target network
for each iteration do
for each environment step do sample at ~ III1111 1 o (a (alls)) from the intention propagation network. g'+1 ~ p(s "isss,"") at), D Ds (8), at rf W+1 end for for each gradient step do update 7i. Kgs 0, 17s.
i=1
- - 4-4JJ(m) K; + -
0 - 1. (()),, 7h -T) (1-
end for end for
Handle the Partial Observation: So far, assume that agents observe global state while in practice each agent just observes its own state 8;. Thus besides the communication with the intention propagation, network. The idea of this local state sharing is similar to (Jiang et al. 2020). while the whole structure of our work is quite different from (Jing et al. 2020). See the discussion the related work.
5 EXPERIMENT
In this section, we evaluate our method and eight state-of-the-an art baselines on more than ten different scenarios from three popular MARL platforms: (1) CityFlow, traffic signal control environment

---

Under review as a conference paper at ICLR 2021
9.0
--222
-2.
-2.4
OMI
-0.9
GMX
avange
-35
PL
IOL
M6123G
MADONG
RC
-0.
-10
HADORS
16.
MADOPOS
9
NAD3POS
MADGPGS
CONA
CONA
COMA
MFO
-1.4
150
-1.
stops (X1o6)
(N 1o6]
Stops (x206)
(a) Cathhlownannhattnn
(h) CityPlow: N=100
(c) CityFlow: N=1225
Figure 3: Performance on large-scale traffic lights control scenarios in CityFlow. Horizontal axis:
environmental steps. Vertical axis: average episode reward (negative average travel time). Higher rewards are better. Our intention propagation (IP) performs best especially on large-scale tasks.
Tang et al. 2019). It is an advanced version of SUMO (Lopez et al. 2018 widely used in MARL community. (2) multiple particle environment (MPE) (Mordatch & Abbeel 2017) and (3) grid-world
platform MAgent (Zheng et al. 2018). Our intention propagation (IP) empirically outperforms all baselines on all scenarios especially on the large scale problem.
5.1 SETTINGS
We give a brief introduction to the settings of the experiment and defer the details such as hyper- parameter tuning of intention propagation and baselines appendix D Notice all algorithms tested in the partially observable setting, i.e., each agent just can observe its own state 8;-
In traffic signal control problem (Leff panel in Figure ( each traffic light the intersection is an agent. The goal is to learn policies of traffic lights to reduce the average waiting time to alleviate the traffic jam. Graph for cityflow: graph is a 2-D grid induced by the map (e.g. Figure D The roads are the edges which connects the agents. We can define the cost T; as the traveling time of vehicle around the intersection i, thus the total cost indicates the average traveling time. Obviously, r, has close relationship with the action of neighbors of agent i but has little dependence on the traffic lights far away. Therefore our assumption on reward function holds. evaluate different methods on both real-woll world and synthetic traffic data under the different numbers of intersections.
MPE Mordatch & Abbeel 2017) and MAgent (Zheng et al. 2018) (Figure 2 are popular particle environments MARL (Lowe et al., 2017 Jiang al. 2020). Graph for particle environments : for each agent, it has connections (i.c., the edge of the graph) with nearest neighbors. Since the graph is dynamic, just a small overhead comparing with the training of the neural networks. The reward functions also have local property, since they are explicitly or implicitly affected by the distance between agents. For instance, in heterogeneous navigation, if small agents collide with big agents, they will obtain a large negative reward. Thus their reward depends on the action of the nearby agents. Similarly, in the jungle environment, agent can attack the agents nearby to obtain high reward.
update the adjacency matrix of the graph every step, e.g.,
steps. It is
Baselines. We compare our method against eight different baselines mentioned in introduction and related work section: QMIX (Rashid et al. 2018); MADDPG (Lowe et al.) 2017); permutation invariant critic (PIC) (Liu et al., 2019); graph convolutional reinforcement learning (DGN) (Jiang et al. 2020); independent Q Q-lemiiing (IQL) (Tan 1993); permutation invariant MADDPG with data shuffling mechanism (MADDPGS): COMA (Foerster al. 2018); MFQ (Yang et al. 2018). These baselines are reported as the leading algorithm of solving tasks in CityFlow, MPF and MAgent.
Among them, DGN and MFQ need the communication with neighbors the training and execution. Also notice that PIC assumes the actor can observe the global state. Thus in the partially observable setting, each agent in PIC also needs to communicate to get the global state information in the training and the execution. Further details baselines given in appendix E.
Neural Network and Parameters. Recall the intention propagation network is represented by GNN. In our experiment, our graph neural network has hop (2 GNN layers, i.e., M 2) and fully-connected layer at the top. Each layer contains 128 hidden units. Other hyperparameters are listed in appendix H
5.2 COMPARISON TO SEATE-OF-THE-AA
In this section, we compare intention propagation (IP) with other baselines. The experiments are evaluated by average episode reward (Lowe al. 2017 For CityFlow tasks, average reward refers
8

---

Under review as a conference paper at ICLR 2021
avvenge renare (Xten)
-1.
-0.6
Careooo www.ee OK lel
P pGk
-1.2
DCR
-10
DGV ONE
ONE
ONIK
-14
MAROYOS
-16
COMA
-10
MRQ
-188
0.5
02
0.4
3:6
1.0
12
14
0.0
02
0.3
0.6
0.3
3.4
0.0
62
5.4
5.
08
15
1.2
14
16
Steps (c1e6)
steps
steps led)
(a) Cooperative Nav. (N=30)
(b) Heterogeneous Nav. (N=100)
(c) Prey and Predator (N=100)
Figure 4: Experimental results on Cooperative Navigation, Heterogeneous Navigation, Prey and Predator. Our intention propagation (IP) beats all the baselines.
to negative average travel time. All experiments are repeated for 5 runs with different random seeds. We report the mean and standard deviation in the curves. We report the results on six experiments and defer all the others to appendix due to the limit of space.
CityFlow. We first evaluate our algorithm on traffic control problem. Particularly, we increase the number of intersections (agents) gradually to increase the difficulties of the tasks. B the performance of different methods on both real-world and synthetic CityFlow data with different number of intersections. On the task of Manhattan City, intention propagation (IP) method, the baseline methods PIC and DGN achieve better reward than the other methods while our method approaches higher reward within fewer steps. On the larger task (N=100), both PIC and DGN have large variance and obtain poor performance. The experiment with N=1225 agents an extremely challenging task. Our algorithm outperforms all baselines with wide margin. The runner-up is MADDPG with data shuffligg mechanism. Its final performance is around -464 and suffers from large variance. In contrast, the performance of our method is around 569 (much higher than the baselines). It's clear that, in both real-world and synthetic cityflow scenarios. the proposed IP method obtains the best performance. We defer further experimental results to appendix G
MPE and MAgent. Figure 4 demonstrates the performance of different methods on other three representative scenario instances: a small task cooperative navigation (N=30) and two large-scale tasks heterogeneous navigation (N=100) and prey and predator (N=100). We run all algorithms long enough (more than le6 steps). In all experiments, our algorithm performs best. For cooperative navigution, MADDPGS performs better than MADDPG. The potential improvement comes from data-shufiling mechanism, which makes MADDPGS more robust to handle the manually specified order of agents. QMIX performs much better than MADDPG, MADDPGS and IQL. However, its performance is not stable even on small setting (N=30). DGN is better and more stable than QMIX. However, when solving large-scale settings, its performance is much worse than PIC and our intention propagation (IP). Although PIC can solve large-scale tasks, our IP method is still much better. In prey and predator, there are two groups of agents: good agents and adversaries. To make a fair comparison of rewards of different methods, we fix good agents' policies and use all the methods learn the adversaries' policies. Such setting is commonly used many articles (Lowe)
et al. 2017 Liu et al. 2019).
Stability. Stability
key criterion evaluate MARL. In all experiments, our method is quite stable with small variance. For instance, as shown in Figure (b), (b), DGN approaches - -1210 + 419 on the CityFlow scenario with N=100 intersections while our method approaches -465 + 20 after 1.6 x 10th steps (much better and stable). The reason is that to make the joint decision, the agent in our algorithm can adjust its own policy properly by considering other agents' plans.
We conduct a set of ablation studies related to the effect of joint policy, graph, hop size, number of neighbors and the assumption of the reward function. Particularly, we find the joint policy is essential for the good performance. In Cityflow, the performance of traffic graph (2-d grid induced by the roadmap) is better than the fully connected graph. In MPE and MAgent, We define the adjacent matrix based on the k nearest neighbors and pick A = in large scale problem and k = in small scale problem. In all of our experiment, we choose the 2-hop GNN. Because of the limitation of space, we just summarize our conclusion here and place the details in appendix F
Ablation Study:
REFERENCES
Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.

---

Under review as a conference paper at ICLR 2021
David Blei, Alp Kucukelbir, and Jon McAuliffe. Variational inference: A review for statisticians. In Journal of the American Statistical Association, 2017.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. ICML 2020, 2020.
Jacopo Castellini, Frans A Olichock, Rahul Savani, and Shimon Whiteson. The representational capacity of action-value networks for multi-agent reinforcement learning. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgen Systems, pp. 1862-1864. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Yong Chen, Ming Zhou, Ying Wen, Yaodong Yang. Yufeng Su, Weinan Zhang, Dell Zhang, Jun Wang, and Han Liu. Factorized q-learning for large-scale multi-agent systems. arXiv preprint 0r09:0/800.03755 2018.
Tianshu Chu, Sandeep Chinchali, and Sachin Katti. Multi-agent reinforcement learning for net- worked system control. arXiv preprint arXiv:2004.01339 2020.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for struc- tured data. In International conference on machine learning, pp. 2702-2711, 2016.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Michael Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. ICML. 2019, 2018.
Christian Schroeder de Witt, Jakob Foerster, Gregory Farquhar, Philipp Torr, Wendelin Boehmer, and Shimon Whiteson. Multi-agens common knowledge reinforcement learning. Advances in Neural Information Processing Systems, pp. 9924 9935, 2019.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018
Scott Fujimoto, Herke Van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. ICML 20/8, 2018.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICMI., volume pp. 227-234. Citeseer, 2002.
Tuomas Haarnoja, Haoran Tang. Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based based policies. In Proceedings of the 34th International Conference on Machine Learning-Voluue Volume 70, pp. 1352-1361. JMLR. org, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801. 01200, 2018
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Jiechuan Jiang, Chen Dun, and Zongqing Lu. Graph convolutional reinforcement learning. ICLR, 2020.
Diederik P Kingma and Max Welling. An introduction to variational autoencoders. arXiv preprint 1906.02690, 2019.
Lior Kuyer, Shimon Whiteson, Bram Bakker, and Nikos Vlassis. Multiagent reinforcement learning for urban traffic control using coordination graphs. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 656-671. Springer, 2008
Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv: (0888805000000 2018.
10

---

Under review as a conference paper at ICLR 2021
Iou-Jen Liu, Raymond A Yeh, and Alexander G Schwing. Pic: Permutation invariant critic for multi-agent deep reinforcement learning. Conference on Robot Learning, 2019.
Pablo Alvarez Lopez, Michael Behrisch, Laura Bieker- Walz, Jakob Erdmann, Yun-Pang Flötteröd, Robert Hilbrich, Leonhard Lücken, Johannes Rummel, Peter Wagner, and Evamarie WieBner. Microscopic traffic simulation using sumo. In 2018 2/ International Conference on Intelligent Transportation Systems (ITSC), pp. 2575-2582. IEEE, 2018.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-compeiitve environments. In Advances in Neural Information Processing Systems, pp. 1379-6390) 2017.
Igor Mordatch and Pieter Abbeel. Emergence of grounded compositional language in multi-agent populations. arXiv preprint arXiv: /t0::::77034490000 2017.
Frans A Oliehoek, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume Springer, 2016.
Gregory Palmer, Karl Tuyls, Daan Bloembergen, and Rahul Savani. Lenient multi-agent deep reinforcement learning. In Proceedings of the 17th International Conference Aulonomous Agents and MultiAgent Systems, pp. 443-451. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
Chao Qu, Shie Mannor, Huan Xu, Yuan Qi, Le Song, and Junwu Xiong. Value propagation for decentralized networked deep multi-agent reinforcement learning. Neurips 2019, 2019.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foer- ster, and Shimon Whiteson. Qmix: monotonic value function factorisation for deep multi-agent reinforcement learning. ICML 2018, 2018.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint /6100.0:610.3330 2016.
Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory, pp. 13-31. Springer, 2007.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. ICML 2019, 2019.
Bharath Sriperumbudur, arthur gretton, and Kenji Fukumizu. Injective hilbert space embeddings of probability measures. In COLT, 2008
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinieius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Value-decompooiitoon networks for cooperative multi-agent learning based on team reward. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2085-2087, Inter- national Foundation for Autonomous Agents and Multiagent Systems, 2018
Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent cooperation and competition with deep reinforcement learning. PloS one, 12(4)cc1123355, 2017.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings
of the tenth international conference on machine learning, pp. 330-337, 1993.
Zheng Tang, Milind Naphade, Ming- Yu Liu, Xiaodong Yang, Stan Birchfield, Shuo Wang, Ratnesh Kumar, David Anastasiu, and Jenq-Neng Hwang. Cityflow: A city-scale benchmark for multi- target multi-cament vehicle tracking and re-identification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8797-8806, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.

---

Under review as a conference paper at ICLR 2021
Martin J Wainwright, Tommi S Jaakkola, and Alan S Willsky. Tree-reweighted belief propagation algorithms and approximate ml estimation by aseudo-moment matching. In AISTA7S, 2003.
Ermo Wei and Sean Luke. Lenient learning in independent-teareer stochastic cooperative games. The Journal of Machine Learning Research, 17(1):2914-29555 2016.
Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. In 2018 AAAI
Spring Symposium Series, 2018.
Yaodong Yang, Rui Luo, Minne Li. Ming Zhou, Weinan Zhang, and Jun Wang. Mcan field multi- agent reinforcement learning. ICML, 2018.
Jonathan S Yedidia, William T Freeman, and Yair Weiss. Bethe free energy, kikuchi approximations, and belief propagation algorithms. Advances in neural information processing systems, 13, 2001.
Alan Yuille. Coep algorithms minimize the bethe and kikuchi free energies: Convergent alter- natives to belief propagation. Neural computation, 14(7):1691-122) 2002.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Başar. Fully decentralized multi-
agent reinforcement learning with networked agents. ICML 2018, 2018
Guanjie Zheng, Yuanhao Xiong, Xinshi Zang, Jie Feng, Hua Wei, Huichu Zhang, Yong Li, Kai Xu, and Zhenhui Li. Learning phase competition for traffic signal control. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, pp. 1963-1972, 2019.
Lianmin Zheng, Jiacheng Yang, Han Cai, Ming Zhou, Weinan Zhang, Jun Wang, and Yong Yu. Magent: A many-agent reinforcement learning platform for artificial collective intelligence. In Thirty-Secone AAAI Conference on Artificial Intelligence, 2018
12

---

Under review as a conference paper at ICLR 2021
A ORGANIZATION OF THE APPENDIX
we give the details on the intention propagation network and parameterization of the GNN. We explain intention propgation from the view of the MARL. At last, we extend the intention propagation to other approximations which converges other solutions of the variational inference. Notice such extension on the algorithm can also easily parameterized by neural networks.
In appendix B
In Appendix C we give the details of the algorithm deferred from the main paper. Appendix D summarizes the configuration of the experiment and MARL environment. Appendix E gives more details baselines and the hyperparameters of GNN used in our model. Appendix | conducts the ablation study deferred from the main paper. Appendix G and H give more experimental results and hyperparameters used in the algorithms. At appendix I proposition !
we derive the algorithm and prove the
B INTENTION PROPAGATION NETWORK
B.1 DETAILS ON THE INTENTION PROPAGATION NETWORK
In this section, we give the details on the intention propagation network deferred from the main paper. We first illustrate the message passing of the intention propagation derived in section 4.1 Then we give details on how to construct graph neural network.
Message passing and explanation from the view of MARL: agent i, which represents the intention of the agent i. At O iteration, every agent makes independent decision. The policy of agent is mapped into its embedding u.. We call it the intention of agent i at iteration O. Then agent sends its plan to its neighbors In Figure 5 ped is the d dimensional (d = in this figure) embedding of qi at m-th iteration of intention propagation. We draw the update of ((m) as example. Agent receives the embedding (intention) juz jum-1 Mi m- ,,6 - from its neighbors, and then updates the its own embedding with operator T. After M iterations, obtain j7-d and output the policy distribution Φi using equation 4 Similar procedure holds for other agents. At each RL step f, do this procedure (with M iterations) once to generate joint policy. M in general is small, e.g., M or 3. Thus it is efficient.
j4; is the embedding of policy of
Parameterization GNN: We then illustrate the parameterization of graph neural network in Figure 6 If the action space is discrete, the output (ag(s)) is a softmax function. When it is continuous, we can output Gaussian distribution (mean and variance) with the reparametrization trick (Kingma& & Welling 2019). Here, we draw 2-hop (layer) GNN to parameterize it in discrete action intention propagation. In Figure 6 (b), each agent observe its own state 8;. After a MLP and softmax layer (we do not sample here, and just use the output probabilities of the actions), we get a embedding z7Q, which the initial distribution of the policy. In the following, we use agent as example. To ease the exposition, we assume Agent 1 just has one neighbor, agent 2. Agent receives the embedding nil of its neighbor. After a GNN layer to combine the information, e.g. Relu (11 + s2) W2 (1 p2),, we obtain new embedding ūi of agent 1. Notice we also do
1m-
P6
(1
l1 (a, |s)
5
(m)
(m-1) 1)
M iterations propagation, it outputs q:
3
P1
(m-11)
n
(m-1)
Figure 5: illustrate the message passing in intention propagation network Ag (als).
13

---

Under review as a conference paper at ICLR 2021
Output policy
(cgls)
(agls)
(;(agls)
(n(2,ls)
softmax
MLP softmax
MLP sofemax
03
Embedding after
1 GNN layer
al Relul W. + +W2(d R2)1
p1
F
P3
s;
W,
+ W25z]]
Embedding
F
F
MLP+ softmax
$1
S2
S3
Figure Details of the graph neural network
message passing on state, since in practice the global state is not available. In the second layer, we do similar things. Agent receives the embedding information of júJ from its neighbors and get new embedding j² Then this embedding passes MLP+softmax layer and output probability of action, i.c. 91 (s)
B.2 EXTENSION TO OTHER VARIATIONAL INFERENCE METHODS AND NEURAL NETWORKS
In this section, show how approximate the joint policy with the Loopy Belief Propagation in the variational inference (Yedidia et al., 2001). This will lead to a new form of neural networks beyond vanilla GNN that illustrate above.
The objective function in Loop Belief Propagation is the Beth Free energy YYdidiia et al. 2001 Different from the mean-field approximation, it introduces another variational variable Oij- which brings more flexibility on the approximation. The following is objective function in our case.
Relhi EE E(MGI ge (a(azls) log ((alss) vhi(s, a;)
min
da;
Σ / Ky ayls) log di a,
nyla, ayls) da,daj. (6)
az)
s.t. / a,lsda = (ayls)) / (islan,ays))n = g5(azls)
Solve above problem, we have the fixed point algorithm
mey(ayls) - / II
(ss ada
RENUV
(aaas))) (h, a.) II my)(asls).
JEM.
Similar to the mean-field approximation case, we have
my((ayss) flaj, s, (masheeN
q: (a:]ss) = g(a,,, s, {mai )Mn,),
says the message my and marginals qi are functionals of messages from neighbors.
Denote the embedding Vij I Uy (s, a, mmm((a))))))) (adda, and i. f ()(s,, a:)g: (a: (s)da, we have Bi + (wx to (s. (Dte keNN))
14

---

Under review as a conference paper at ICLR 2021
Again, can parameterize above equation by (graph) neural network Diy a oWis + W2 EMeNyy Pia), i a (Was + W4 ΣkEN, Pks)).
Following similar way, ferent objective function which corresponds to e.g., double-loop belief propagation Yuille 2002).
derive different intention propagation algorithms by changing dif-
tree-reweighted belief propagation (Wainwright et al. 2003) and many others.
C ALGORITHM
We present some remarks of the algorithm Intention Propagation (algorithm deferred from the main paper.
Remark: To calculate the loss function [n:), each agent need to sample the global state and (as, ax;). Thus we first sample global state from the replay buffer and then sample all action once using the intention propagation network.
D FURTHER DETAILS ABOUT ENVIRONMENTS AND EXPERIMETAL SETTING
Table summarizes the setting the tasks in our experiment.
Table I: Tasks. We evaluate MARL algorithms on more than different tasks from three different environ-
ments.
Scenarios
#agents (N)
Realworld:Hang Zhou
N=16
CityFlow
Realworld:Manhattn
N=96
Synthetie Map
N=49, 100, 225, 1225
Cooperative Nav.
N= 30, 200
Heterogeneous Nav.
N=100
Cooperative Push Prey and Predator
N=100
N=100
MAgent
Jungle
2=20, F=12
D.1 CITYFL.Ow
CityFlow (Tang et al. 2019) is an open-source MARL environment for large-scale city traffic signal control After the traffic road map and flow data being fed into the simulators, each vehicle moves from its origin location to the destination. The traffic data contains bidirectional and dynamic flows with turning traffic. We evaluate different methods on both real-world and synthetic traffic data. For real-world data, we select traffic flow data from Gudang sub-district, Hangzhou, China and Manhattan, USA For synthetic data, we simulate several different road networks: 7 x 7 grid network (N 49) and large-scale grid networks with N 10 10 100 15 x 15 225, 35 x 35 = 1225. Each traffic light at the intersection is the agent. In the real-world setting (Hang Zhou, Manhattan), the graph is 2-d grid induced by the roadmap. Particularly, the roads
edges which connect the node (agent) of the graph. For the synthetic data, the map is a n * n 2-d grid (Something like Figure 7]. where edges represents road, node is the traffic light. We present the experimental results deferred from the main paper in Figure I0
D.2 MPE
the observation of each agent contains relative location and velocity of neighboring agents and landmarks. The number of visible neighbors in an agent's observation equal or less than 10. In some scenarios, the observation may contain relative location and velocity of neighboring agents and landmarks.
In MPE (Mordatch Abbeel 2017
thub. www./mitttto.oooo..o from
We download the maps
http:///ittib..com/rree signll controo
sample-code
"To make the environment computation-effhiien,, Liu et (011 provided improved version of
MPF. The code released in htttp:://github.com louJen P
15

---

Under review as a conference paper at ICLR 2021
We consider four scenarios in MPE. (1) cooperative navigation: N agents work together and move to cover L landmarks. If these agents get closer to landmarks, they will obtain a larger reward. In this scenario, the agent observes its location and velocity, and the relative location of the nearest 5 landmarks and N agents. The observation dimension is 26. (2) prey and predator: N slower cooperating agents must chase the faster adversaries around randomly generated environment with L large landmarks. Note that, the landmarks impede the way of all agents and adversaries. This property makes the scenario much more challenging. In this scenario, the agent observes its location and velocity, and the relative location of the nearest 5 landmarks and 5 preys. The observation dimension is 34. (3) cooperative push: N cooperating agents are rewarded to push a large ball to a landmark. In this scenario, each agent can observe 10 nearest agents and 5 nearest landmarks. The observation dimension is 28. (4) heterogeneous navigation: this scenario similar with cooperative navigation except dividing N agents into NVV big and slow agents and AN2 small and fast agents. If small agents collide with big agents, they will obtain a large negative reward. In this scenario, each agent can observe 10 nearest agents and 5 nearest landmarks. The observation dimension is 26.
Further details about this environment can be found at httpp:://itthb..rt http://hhhaa..omoo//eiiiaaa
PIC
D.3 MAGENT
MAgent Zheng et al. 2018 a grid-world platform and serves another popular environment plat- form for evaluating MARL algorithms. Jiang et al. (2020) tested their method on two scenarios: jungle and battle. In jungle, there are N agents and F foods. The agents are rewarded by positive reward if they eat food, but gets higher reward if they attack other agents. This is interesting sce- nario, which called by moral dilemma. In battle, N agents learn to fight against several enemies, which is very similar with the prey and predator scenario in MPE. In our experiment, we evaluate our methods on jungle.
In our experiment, the size for the grid-world environment is 30 30. Each agent refers to one grid and can observe 11 x 11 grids centered at the agent and its own coordinates. The ac- tions includes moving and attacking along the coordinates. Further details about this environment can be found at httpp: //tp:p:://gthhb... com/ wwwp:/cw-.ccooeeeeeeeeeee aiMMagenMMM/nnn and httpd:htp///// :/ /iitbbb. com/
PKU-AI Edge/ DGN
E FURTHER DETAILS ON SETTINGS
E.1 DESCRIPTION OF OUR BASELINES
We compare our method with multi-agent deep deterministic policy gradient (MADDPG) (Lowe) jet al., 2017), a strong actor-critic algorithm based on the framework of centralized training with decentralized execution; QMIX (Rashid et al. 2018). q-learning based monotonic value function factorisation algorithm; permutation invariant critic (PIC) (Liu et al. 2019). a leading algorithm on MPE yielding identical output irrespective of the agent permutation; graph convolutional reinforce- ment learning (DGN) (Jiang et al.] 2020), a deep q- q-learning algorithm based on deep convolutional graph neural network with multi-head attention, which is leading algorithm on MAgent; indepen- dent Q-learning (QQI.) Tan 1993), decomposing a multi-agent problem into a collection of simulta- neous single-agent problems that share the same environment, which usually serves as surprisingly strong benchmark in the mixed and competitive games (Tampuu et al. (017)) In homogeneous set- tings, the input to the centralized critic in MADDPG the concatenation of all agent's observations and actions along the specified agent order, which doesn't 't hold the property of permutation invari- ance. We follow the similar setting in (Liu et al. 2019) and shuffle the agents' observations and actions in training batch 4 In COMA (Foerster et al. 2018), 8). it directly assume the poilcy is factor- ized. calculates the counterfactual baseline to address the credit assignment problem in MARL. In our experiment, since
observe each reward function, each agent can directly approximate the Q function without counterfactual baseline. MFQ derives the algorithm from the view of mean-fiell gane et al. 2018). Notice the aim of mean-field game is find the Nash equilibrium rather
*This operation doesn't 't change the state of the actions.
16

---

Under review as a conference paper at ICLR 2021
1
2
3
Indepedent policy
Intention Propagation
-2
-3
4
5
6
Amm
7
8
9
-0
203
-000
600
1000
steps
Figure 7: (a) toy task on 2d-grid. (b) The performance of independent policy and intention propa- gation.
than maxmization of the total reward of the group. Further more, it needs the assumption that agents are identical.
E.2 NEURAL NETWORKS ARCHITECTURE
To learn feature from structural graph build by the space distance for different agents, we design graph neural network based on the idea of strong graph embedding tool structure2vec (Dai ict al. (2016). which is an effective and scalable approach for structured data representation through embedding latent variable models into feature spaces. Structure2vee extracts features by performing a sequence of function mappings in a way similar to graphical model inference procedures, such mean field and belief propagation. After using M graph neural network layers, each node can receive the information from M -hopps neighbors by message passing. Recently, attention mechanism empirically leads more powerful representation on graph data (Veličković al. 2017: Jiang al., 2020). We employ this idea into our graph neural network. In some settings, such as heterogeneons navigation scenario from MPE, the observations of different group of agents are heterogeneous. To handle this issue, we use different nonlinear functions to extract the features from heterogeneous observations and map the observations into a latent layer, then use the same graph neural networks to learn the policy for all types of agents. In our experiment, our graph neural network has M 2 layers and fully-connected layer at the top. Each layer contains 128 hidden units.
F ABLATION STUDIES
F.1 INDEPENDENT POLICY VS INTENTION PROPAGATION.
We first give a toy example where the independent policy (without communication) fails. To im- plement such algorithm, we just replace the intention propagation network by independent policy network and remain other parts the same. Think about a 3 3 2d-grid in Figure 7 where the global state (can be observed by all agents) is a constant scalar (thus no information). Each agent chooses an action a; 0 or The aim is to maximize reward - (a) a2)² (a) ) (a2 -aa²²
(as og)². (i.e.. summation of the reward function edges). Obviously the optimal value is 0. The optimal policy for agents is aj = d2 =,.... ag or 01 = 02 =...., ag = 1. However independent policy fails, since each agents does not know how its allies pick the action. Thus the learned policy
random. We show the result of this toy example in Figure where intention propagation learns optimal policy.
F.2 GRAPH TYPES, NUMBER OF NEIGHBORS, AND HOP SIZE
We conduct set of ablation studies related to graph types, the number of neighbors, and hop size. Figure a and Figure b)) demonstrate the performance of our method on traffic graph and fully- connected graph the scenarios (N=49 and N=100) of CityFlow. In the experiment, each agent can only get the information from its neighbors through message passing (state embedding and the policy embedding). The result makes sense, since the traffic graph represents the structure of the
17

---

Under review as a conference paper at ICLR 2021
map. Although the agent in the fully connected graph would obtain global information, it may introduce irrelevant information from agents far away.
Figure g c) and Figure ddd) demonstrate the performance under different number of neighbors and hop size on cooperative navigation (N=30) respectively. The algorithm with neighbors=8 has the best performance. Again the the fully connected graph (neighbors=30) may introduce the irrelevant information of the agents far away. Thus its performance is worse than the algorithm with graph constructed by the K-nearest neighbor. In addition the fully connected graph introduces more com- putations in the training. In Figure(8ic) we increase the hop-size from to 3. The performance of IP with hop=2 is much better than that with hop=1. While IP with hop=3 is just slightly better than that with hop=2. It means graph neural network with hop size =2 has aggregated enough information.
In Figure ge), we test the importance of the k-nearest neighbor structure. PFineighoors+))rrande means that we pick 3 agents uniformly at random as the neighbors. Obviously, IP with K-nearest neighbors outperforms the IP with random graph a lot. In Figure M we update adjacency ma- trix every 1, 5, 10 steps. IP(neighbors=8) denotes that we update the adjacency matrix every step, while IP(neighbons=@@)rrseett and (P(neighbors=&)rreeettt cency matrix every 5 and 10 steps respectively. Obviously, IP(neighbors=8) has the best result. [Ponigghoor=+8)rrsett is better than ( The result makes sense, since the adjacency matrix is more accurate if the update interval is smaller.
denote that we update adja-
F.3 ASSUMPTION VIOLATION
The aforementioned experimental evaluations are based the mild assumption: the actions of agents that are far away would not affect the learner because of their physical distance. It would be interesting to see the performance where the assumption is violated. As such, we modify the reward in the experiment of cooperative navigation. In particular, the reward is defined by r r1 + r2, where r1 encourages the agents cover (get close to) landmarks and r2 is the log function of the distances between agents (farther agents have larger impact). To make a violation, we let r2 dominate the reward. We conduct the experiments with hop 1, 3. Figure 9 shows that the rewards obtained by our methods are 4115 = 21, 4564 = 22, and 4586 + 25 respectively. It's expected in this scenario, since we should use large hop to collect information from the far-away agents.
G FURTHER EXPERIMENTAL RESULTS
For most of the experiments, we run them long enough with I million to 1.5 million steps and stop (even in some cases our algorithm does not converge to the asymptotic result), since every experment
in MARL may cost several days. We present the results on Cityflow in Figure TO Figure II
provides the experimental results on the cooperative navigation instances with N 15, N 30 and N 200 agents. Note that, the instance with agents reinforcement learning setting (Chen et al. 2018 Liu et al. (019), which typically needs several days to run millions of steps. It's clear that IQL, MADDPG, MADDPG perform well in the small setting (N=15), however, they failed in large-scale instances (N = 30 and N 200). In the instance with N = 30, MADDPGS performs better than MADDPG. The potential reason that with the help of shuffling, MADDPGS is more robust to handle the manually specified order of agents. Although QMIX performs well in the instance of N = 15 and N = 30, it has large variances in both settings. DGN using graph convolutional network can hold the property of permutation invariance, it obtains much better performance than QMIX on these two settings. However, it also fails solve the large-scale settings with N 200 agents. Empirically, after 1.5 x 10 steps, PIC obtains a large reward (-425085 + 31259) on this large-scale setting. Despite all these. the proposed intention propagation (IP) approaches -329229 14730 and is much better than PIC. Furthermore, Figure TT shows the results of different methods on (d) jungle (N=20, F=12) and (e) prey and predator (N=100). The experimental results shows our method can beats all baselines on these two tasks. On the scenario of cooperative push (N=100) as shown in Figure II it's clear that DGN, QMIX, IQL, MADDPG and MADDPGS all fail to converge to good rewards after 1.5 x 10e environmental steps. In contrast, PIC and the proposed IP method obtain much better rewards than these baselines. Limited by the computational resources, we only show the long-tern performance of the best two methods. Figure (T shows that IP is slightly better than PIC in this setting.
200 is a large-scale and challenging multi-
18

---

Under review as a conference paper at ICLR 2021
-8
average reward (x] 1e2)
-10
average reward
-10
144
Plttraffic graph) IPffc gr sph)
-18
IPttraffcc graph)
IPttc graph)
1.6
steps (x1e6)
steps (x1e6)
(a) CityFlow:777
(b) CityFlow:100 10
-0.9
average (x1e4)
average reward (x3e4)
-1.0
-12
-1.2
Pinnsghbrrs-5)
-13
Plnegghbrr=-B)
P1hop=11
Pinnechbars-101
(Pthop=2)
-14
PPineghbor=:30)
-14
(Pthop=3)
0.0
0.2
0.4
0.6
0.8
0.0
0.2
0.4
0.6
0.8
10
steps (x1e6)
sleps (x1e6)
(c) neighbors on Cooperative Nav. (N=30)
(d) hop on Cooperative Nav. (N=30)
average reward (x1e4)
1eere0 (x1e4)
0.9
-1.0
11.0
-1.1
1..0
#tneighbors-31
Flneighbons:
1.0
-12
Aneighhors=100
Ptneighhors=3)1mm
1.1
PPineighbors:0)
Rnnlighoor--Bi-ran
Fineighbons=
1.1.1
r)+reset110;
-162
0.6
steps (x166)
steps (x1e6)
(e) Random graph Cooperative (N=30)
Nav.
Update adjacency matrix every n=1,5,10
steps. Cooperative Nav. (N=30)
Figure 8: Performance of the proposed method based on different ablation settings. (a) Traffic
graph and fully connected (fc) graph on CityFlow (N=49). (b) Traffic graph and fully connected (fc)
graph CityFlow (N=100) 100). (c) Cooperative Nav. (N=30): Different number of neighbors. (d)
Cooperative Nav. (N=30): Different hop size graph neural networks. (c) Cooperative Nav. (N=30):
Construct random graph d-nnaaest-neighhor graph (k: 3. 8, 10). (f) Cooperative Nav. (N=30):
Update 8-nearest-neet neighor graph every environment steps (5 and 10 respectively.).
19

---

Under review as a conference paper at ICLR 2021
4.6
average reward (xle3)
4.4
4.2
4.0
3.8
IP(hop=1)
3.6
PPhho==2)
IP(hop=3)
3.4
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
steps (x (x1e6)
(a) Coop. Nav. Violation (N=30)
Figure 9; Further experimental results. Cooperative navigation (N=30) with assumption violation.
G.1 POLICY INTERPRETATION
Explicitly analyzing the policy learned by deep multi-agent reinforcement learning algorithm is challenging task, especially for the large-scale problem. We follow the similar ideas from (Zheng et al. 2019) and analyze the learned policy on CityFlow in the following way: We select the same period of environmental steps within (210000, 1600000) and group these steps into 69 intervals (each interval contains about 20000 steps). We compute the ratio of vehicle volume each movement and the sampled action volume from the learned policy (each movement can be assigned to one action according to the internal function in CityFlow). We define the ratio of vehicle volume all movements as the vehicle volume distribution and define the ratio of the sampled action volume from the learned policy over all movements as the sampled action distribution. It's expected that good MARL algorithm will hold the property: these two distributions will very similar over period of time. Figure T2 reports their KI. divergence by intervals. It's clear that the proposed intention propagation method (IP) obtains the lowest KL divergence (much better than the state-of-the-art baselines). Because KL divergence is not symmetrical metric, we also calculate their Euclidean distances. Specifically, the distance of our method is 0.0271 while DGN is 0.0938 and PIC is 0.0933.
H HYPERPARAMETERS
The parameter on the environment. For the max episode length, we follow the similar settings like that in the baselines (Lowe al.) al.] (017) Particularly, we set 25 for MPE and set 100 for CityFlow. For MAgent, we find that setting the max episode length by 25 is better than 100. All the methods share the same setting.
We list the range of hyperparameter that we tune in all baselines and intention propaga- tion. 7 {0.95, 0.98, 0.99, 0.999). learning rate {1,5, 10, 100] x le-4, activation function:
frelu, gelu, tanh), batch size: {128, 256, 512, 1024), gradient steps: 21, 2, 4, 83. Number of hid- den units in MLP: {32, 64, 128, 256, 512]. number layers in MLP:(1, 2, 3} in all experiment. In Qmix, GRU hidden unites (64, 128). A fully connected layer is before and after GRU. Hy- pernetwork and mixing network are both single layer network(64 hidden units with Relu activation from the Qmix paper). The parameter of intention propagation is reported in Table 2
20

---

Under review as a conference paper at ICLR 2021
0.0
average reward (xtel]
-0.5
-10
-1.0
DGN
-15
QMIX
QM
-1.5
11
NADDPG
22
MADOPG
-2.5
COMA
25
MADOPGS
COMA
-3.0
-28
MFQ
0.00
0.25
0.50
0.75
1.00 1.25 steps (x1e6)
1.50
1.75
2.00
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
1.6
steps (x1e6)
(a) CityFlow:Hang Zhou
(b) CityFlow:7
-2.0
average reward (x1e3)
-2.5
-10
DGN
20
OMIX
1OL
IQL
MADDPG
30
MADDPG
MADDPGS
MADDPGS
-4.0
COMA
COMA
MFQ
MFQ
steps (x1e6)
steps (x xee6)
(c) CityFlow: Manhattan, USA.
(d) CityFlow:10
average reward (eles)
SE00 reward (x1e4)
0.2
DGN
-0.4
DGN
QMIX
0.6
QMIX
IQL
P/C
MADDPG
-5
COMA
avera
-12
MADDPGS
COMA
-6-
-1.4
MFQ
0.2
0.4
0.6
0.8
1.0
1.2
1.4
16
0.00
0.30
(x1e6)
(x1e6)
(e) CityFlow:15115
(f) CityFlow:35
Figure 10: Performance different methods on traffic lights control scenarios in CityFlow envi- ronment: (a) N=16 (4 grid), Gudang sub-district, Hangzhou, China. (b) N=49 (7 x 7 grid), (c) N=96 (irregular grid map), Manhattan, USA. (d) N=100 (10 10 grid), (e) N=225 (15 x 15 grid), (f) N=1225 (35 35 grid). The horizontal axis is time steps (interaction with the environment). The vertical axis is average episode reward, which refers to negative average travel time. Higher rewards better. The proposed intention propagation (IP) obtains much better performance than all the baselines on large-scale tasks.
21

---

Under review as a conference paper at ICLR 2021
average reward (x163)
-2
average m reward [X] 141
-3
DGN
DGN
QMIX
IQL
-4
PIC
MADDRG
MADDRES
MADOPGS
COMA
-6
MFQ
-18
0.0
0.2
0.4
0.6
0.8
1.0
1.2
144
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
steps (x 1e6)
steps
(x1e6)
(a)
(b)
average reward (x]e5]
-3.5
-4.0
1P
DGN
-4.5
OMIX
QMIX
IQI
-3.0
-3.
MADDPG MADDPOS
averagg
1.0
MADDPG
MADDPGS
660
COMA
COMA
-6.5
MFQ
MEQ
steps (x1e6)
steps
(x1e6)
(d)
average reward (x1e4)
10
IP
-6.5
IP
DGN
QMIX
average reward
-7.5
QMIX
PIC
-8.0
PIC
MADDPG MADDPES
MADDPG
MADDPGS
COMA
-9.0
COMA
MFQ
-9.5
MFQ
1.0
1.2
1.6
steps (x1e6)
steps (x1e6)
Figure 11: Comparison on instances with different number of agents: cooperative navigation (a) N=15, (b) N=30 and (c) N=200 respectively. (d) jungle (N=20, F=12). (c) prey and predator (N=100), and (f) cooperative push (N=100). The horizontal axis is environmental steps (number of interactions with the enviroment). The vertical axis is average episode reward. The larger average reward indicates better result. The proposed intention propagation (IP) beats all the baselines on different scale of instances.
IP
DGN
QMIX
kl divergence
IQL
PIC
MADDPG
0
10
20
30
40
50
60
70
step interval
Figure 12: Policy interpreation on CityFlow task (N=49)
22

---

Under review as a conference paper at ICLR 2021
Table 2: Hyperparameters
Parameter
Value
optimizer
Adam
learning rate of all networks
0.01
discount of reward
0.95
replay buffer size
106
max episode length in MAgent
25
max episode length in MPE, CityFlow
100
number of hidden units per layer number of samples per minibatch nonlinearity
128
1024
ReLU
target smoothing coefficient (r)
0.01
target update interval
I
gradient steps regularizer factor((:)
8
0.2
I DERIVATION
1.1 PROOF OF PROPOSITION
We prove the result by induction using the backward view.
To see that, plug r(s", a²) En re(s", al o'x;) into the distribution of the optimal policy defined
in section 3
II p( 47 ls, a exp Σ N t=0
p(T) = (p(s")
Σ
ri(s", at, a'v.)
Recall the goal is to find the best approximation of =(a*|s*) such that the trajectory dis- tribution P(7) induced by this policy can match the optimal trajectory probability p(T).
Thus we minimize the KL divergence between them min, (xz()())lp(T)) where p(T)
p(s)) IT (s' a²) )²)==("(s'" We can do optimization w.r.t. (aalls s²) that in (Levine 2018
and obtain backward algorithm on the policy π (aaalss)) (See equation 13 in 1.2
T
1 Z
TT' (aa((s**
exp (Bpostir a
rals"
log (aa 1s )). (7)
PEtEll
t'++1
Using the result equation when t T, the optimal policy is
t" (' (a=lsT)) % exp
(sT (f,))
Obviously, it satisfies the form n" "a" |5 exp Ci N Now suppose from step + to T, we have
vi" of a)ss))
N
n ("aa"
exp
th of xx))
(8)
7
for 1' = t 1, I..., T. Recall that we have the result
T N
T
xt' (aa (s0') 7 exp (Ep(ottiiz a
1
ri a/y;) Σ
log (a" 18 I].
1'= 1
p'1+1
23

---

Under review as a conference paper at ICLR 2021
Now plug equation into equation 9 we have
1 s'aa"s²)) exp (
ri(s" af (
Σ
Vo de axx
C]),
z
(10)
where some constant related the normalization term. Thus, we redefine a new term
(s d', d'y.)= (0
Σ (ri(s" (.
E vi a" dxx)))- (11)
1=t+1
Then obviously x² =""a"|ss Is") satisfies the form what we need by absorbing the constant C into the normalization term Thus we have the result.
I.2 DERIVATION THE ALGORITHM
We start the derivation with minimization of the KL divergence KI(((T))(((T)) where p(T) = P exp EE ΣN (i ax,)), p(T) = p(s IT p(st a (()
KL(G(T)IP(T)) =E,
Σ
ri(s a ax:))
log (agg(("))"))
1=U
1=1
El(s') 9)
II p(s p (aalass))
re rs(s a axx)) log (aa))=)))
(12)
Now we optimize KL divergence w.r.t π (-1s"). Considering the constraint E, Tf|ss) 1, we
troduce a Lagrangian multiplier > T(jls²) 1) (Rigorously speaking, we need to consider another constraint that each element of is larger than O, but later we will see the optimal value satis- fies this constraint automatically). Now we take gradient of K + w.r.t (-1s), set it to zero, and obtain
x -
T
N
T
log x" (a'ls") = Ep at
rs(s"
(.v -
Σ 1=t+1
log (aa -1 11
Therefore
T N
T Σ
(a'l's")) x exp (E 177 a()
rils"
a ; (xx))
log ( ( ())
(=t i=1
e'1+1
Since we know E3 T(]s") 1, thus we have
T
"'' *"(a'lb*)= exp (Bp
rils
a
a
Σ
log (a
(s I]). (13)
v=++1
For convenience, we define the soft V function and Q function as that Levinne 2018). and will show how decompose them into Vi and Q; later.
24

---

Under review as a conference paper at ICLR 2021
N
V(s =
Ta(s ag axx)) - log log aaa ||2tt]]
#'=++1
(14)
at)) riss' a a'y,) + Bpp ())))))))))))))))))))))))))))))) (V) [V(stt1)) Q(6' Σ
Thus V(s*) E (Q(t d') log (s)) The optimal policy n" (aals")
expl Q(pplQC'.ar ,a)) exp Q(s", ad)daa by
plugging the definition of Q into equation 13
Remind in section 4.1 we have approximated the optimal joint policy by the mean field approxima-
tion q: (a:a (s). We now plug this into the definition of equation 14 and consider the discount
factor. Notice it is easy to incorporate the discount factor by defining a absorbing state where each
transition have (1 - 7) probability to go to that state. Thus we have
T
N
V(s = E
Tils" af ax)
log (a (s 1)}
M=f+1
1=1
(15)
Q a²) = Σ rs a a'y,) + p [V(
Thus we can further decompose V and Q into and Q.. We define V; and Qi the following way.
= E Σ (ra(s" af .ax)) log aiaa ss 1)
n't+1
Qils' ai d'.) = ri(s", ,af, a'x)) + Ep a (V((s++))
Obviously we have V Σm and Q = Σie Qi. For V,, according to our definition, we obtain
Vi(s') = E. a: [r:(s", at, a'x.) - log (aa)ss") + Spottisa V((s+t)) Now relate it to Q,, and have
(16)
Vi(st) = = E (Q) at, - log (a:ls²))
"Bals"")))[a,,,rr/ee B(a,ax,) Qi(s) at, - log go (a
Thus it suggests that we should construct the loss function on Vi and Q₂ in the following way. In the following, we use parametric family (c.g. neural network) characterized by n7, and n; approximate V; and Q; respectively.
J(n) Baen 1 (Vn, (5') (o (8', a/))) log (at()))))
J(H,) = of bl (2t (s", at, axx,) Qs' at a)x)))
(17)
where (i' at, axx;) = =r; + EE,, ( a [V,, (V (st+))].
Now we are ready to derive the update rule of the policy, i.e., the intention propagation network.
Remind the intention propagation network actually is mean-field approximation of the joint-policy.
N
min P1.P2.....PP
KL pa(a pe(adss))
is the optimization over the function ps rather than certain parameters. We have proved that after M iteration of intention propagation, we have output the nearly optimal solution 4.
25

---

Under review as a conference paper at ICLR 2021
In the following, will demonstrate how to update the parameter & of the propagation network As (aa((ss), s'),, if we use neural network to approximate it. Again we minimize the KL divergence
N min E, KL II a (a (a')ss)))
Plug the (aass"²) I exp Q(=t jda, into the KL divergence. It is easy see, it is equivalent to the following the optimization problem by the definition of the KI. divergence.
exp a²)
max Eg:
[La (
E Cn a5.)
Σ
log qu (
Thus we sample state from the replay buffer and have the loss of the policy as
N
J(0) B't (a
log q.o
o (a
Σ Qx (s ax,
26


Reviews:
[{"review_id": "oRva9CJyCcS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method for generating policies in cooperative games, using a neighbourhood-based factorisation of reward, and an iterative algorithm which independently updates policies based on neighbour policies and then propagates the policy to neighbours using function space embedding.\n\nThe experimental results looked promising, so there seems to be an idea here worth communicating.\n\nThe paper was very hard for me to follow. I'm not an expert in the area and wouldn't expect to follow all of the reasoning in constructing the method, but I would be expect to be able to follow some clear statements of the algorithm, or its theoretical properties (guarantees of some solution quality given certain assumptions, the parameters affecting this, etc.). Instead the main body of the paper felt like a collection of pieces that were used when developing the algorithm. I would suggest it might be easier to follow if written from the top down, instead: present a high-level overview of the idea, give a (detailed!) description of the algorithm, the experiments, and leave the derivation to the appendix.\n\nDespite being in the appendix, the algorithm is less than half a page, and doesn't explain the variables. eta and kappa might be described elsewhere, but it would be helpful to reference where. J is a loss: which one?\n\nOne of the claimed contributions is this is *principled* method. However, the exact assumptions are not clear, and the chain of issues discussed throughout section 4 seems to include discussion of approximation. What makes this principled? This would seem to need a clear statemen\nOne of the claimed contributions is this is *principled* method. However, the exact assumptions are not clear, and the chain of issues discussed throughout section 4 seems to include discussion of approximation. What makes this principled? This would seem to need a clear statement: what are the exact assumptions, and what precisely is the quality of the output? Is it exact? What are the complete set of parameters? Where does approximation fit in?\nt: what are the exact assumptions, and what precisely is the quality of the output? Is it exact? What are the complete set of parameters? Where does approximation fit in?\n\nAnother claimed contribution is computational efficiency. How does the computational cost compare to the baselines in the experiments?\n\n\nProposition 1: \"The optimal policy has the form ... 1/Z exp(...)\"\nI found the use of optimal slightly hard to follow throughout this. The usual definition of optimal policy would be a value maximising policy, which would be an argmax rather than a softmax. Following that definition, this proposition wouldn't be true, so it seems like it needs more explanation, or more careful wording.\nThe cited PRL article (Levine 2018) seems to retain this standard use of optimal: it uses a distribution over trajectories with an equation similar to here (a softmax over accumulated trajectory rewards), and makes use of the property that trajectories corresponding to an optimal policy have maximum probability in that distribution.\nCan the authors clarify this use of optimal?\n\nProposition 1:\nFor clarity, explain the intention of psi. Is this the future accumulated reward given the current state and selected action?\n\n=-= comments after author discussion\nThe authors were quite active in editing the submission, and addressing the concerns I had. I still find the paper a bit hard to follow, but none of my original concerns remain.", "extra_scores": {}, "extra_text": {}}, {"review_id": "aCOqCrFw5wT", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a scalable approach via intention propagation to learn a multi-agent RL algorithm using communication in a structured environment. An agent encodes its policy and sends the “intention” to the neighboring agents with the assumption that only the closest agents would be the affected by it. The approach involves using techniques from the embedded probabilistic inference literature using mean-field variational inference. The joint-policy is estimated using the mean-field approximation that is obtained via propagating intents in an iterative manner. So this approach helps in avoiding the need to factorize the value function explicitly.\n\nThe related works section does a nice survey of related approaches and the paper shows conceptual differences to an earlier proposed MFG that has stricter requirements. \n\nThe experiments shown cover many important baselines that are shown to be good baselines in respective environments. IP outperforms all the baselines in three competitive benchmarks.\n\nI have a few questions about the clarity of the presentation.\n\n- How important is the graph structure defined by k-means? A comparison with a randomized graph and ablation with different reset time (n) intervals would be interesting.\n\n- In the experiments, it would be interesting to check if intention only helps the nearby agents. How does adding/removing agents to the set of neighbors affect learning? A comparison with a fully connected graph should be sufficient. The plot in the Appendix shows results on the CityFlow task which has very structured observation with the set of immediate neighbors always set of 4. Doing such an analysis on a more dynamic environment like MPE would be helpful.\n\n- What is the computational cost of a densely connected graph as compared to method without using a fixed topology?\n\n- Fig 4c does not show plots until convergence.\n\nOverall I feel some restructuring of the paper would benefit the reader explaining some missing portions of the algorithm. For eg, taking out the environment images from the main text.", "extra_scores": {}, "extra_text": {}}, {"review_id": "QGERUw110U3", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a multi-hop communication method for multi-agent reinforcement learning. This method is based on the loosely coupled reward structures among agents, which, as far as I am concerned, are generally held in complex multi-agent settings. The authors use experiments on CityFlow, MPE, and MAgent to demonstrate that their method can outperform the SoTA methods and is scalable. The empirical results is impressive. However, it is some concerns regarding methods that lead to my overall negative rating.\n\nFirstly, also the most importantly. Although the authors emphasize that they are communicating the intentions of agents, I think their method is quite similar to those communicating local observations, like NDQ (https://arxiv.org/abs/1910.05366), DGN, or CollaQ (https://arxiv.org/abs/2010.08531). One way to interpret the proposed communicating network structure is a normal multi-hop communication mechanism, but only with a softmax activation function. \n\nCompared to previous works studying communications of local observations, the proposed work (1) needs to address the problems induced by the joint policy, like sampling from it. The author use a variational influence approach to conduct sampling. However, this approach may hurt the scalability. And it (2) requires agents have access to the global states. For partial observable environments, the proposed methods needs to reply on DGN. \n\nSome other points: (1) I was expecting ablation studies where DGN is ablated on partial observable environments. (2) Some parts in the method section are hard to follow.", "extra_scores": {}, "extra_text": {}}, {"review_id": "20JhlFxTogY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Paper Summary\nThe paper considers the cooperative multiagent MARL setting where each agent’s reward depends on the state and the actions of itself and its neighbors The paper has a theoretical claim that, for such reward structure, the optimal maximum entropy joint policy in the form that can be factored into potential functions, one for each agent. In particular, if the sum of all agents’ rewards is a function on pairwise actions, those potential functions are one for each agent and one for each pair of actions (i.e. the equation after Proposition 1).\nThen, the paper proposes to use mean-field approximation to approximate the optimal joint policy (Equation (3)), which leads to a concrete algorithm that relies on passing the embedding of each agent’s local policy around to neighbors. The paper then empirically shows that the algorithm is particularly effective for domains with a large number of agents.\n \n \nMajor Comments/Questions\n1. Although the motivation has an interpretation of intention propagation, the resulting architecture (Figure 1b) and loss functions (Section 4.2) seems to be a standard messaging passing architecture with SAC loss functions that loses the *intention* semantics. I do not see too much algorithmic novelty here.\n \n2. For the baselines used in the experiments, it seems that only IP and DGN allow communication/message passing *during execution*, which makes it unsurprising that the two methods outperform other baselines. \n \nMinor Comments/Questions\n1. The beginning of Section 3 says the paper considers maximum entropy as the optimization objective, while eta(pi) at the beginning of Section 4 says the objective is long-term reward (no entropy). This seems to be an inconsistency here.\n \n2. For the assumptions on rewards, Proposition 1 assumes that each agent’s reward depends on its neighbors, while the derivation of Equation (3) (and thus the following algorithm) further assumes that the reward depends on pairwise actions. It is a little bit unclear what assumptions are required for all the theoretical and experimental claims of this paper. \n \n3. Is there reason to believe that the multi-round message passing will converge to the fixed-point of Equation (2)?\n\n4. What is the \"overgeneralization issue\"?\n \n \nOverall (weak accept)\nThe paper has a clear introduction and motivation of the proposed algorithm. The insight that optimal maximum entropy joint policy takes the format of Markov Random Field might be of some value and interest. However, I don’t think the resulting method has much algorithmic novelty.\n\n\n--------------\nThanks for the response and I've increased my score. I am satisfied with the response but still not convinced about the algorithmic novelty on the intention semantics built into the method, even after reading B.1.  In particular, it seems that the loss functions do not drive mu's represented by NNs to the fixed point solution of Eq (3); psi shows up in Eq (3) but does not play a role in the following development of the method. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper describes a framework for multi-agent reinforcement learning that uses Markov Random Fields. Unfortunately, the paper is not clearly written and would benefit from significant revisions that improve its structure and make the model and approximations more explicit.

In particular, the paper says a graph says which agents $i,j$ communicate. This is typically called the "coordination graph" in this setting, see
"Collaborative Multiagent Reinforcement Learning by Payoff Propagation", Kok and Vlassis, 2006. Note that within that paper they provide Q-function decomposition, which can only serve to approximate the optimal policy.

The authors of this submission claim that an MRF is sufficient for optimal policies. I fail to see how this is true. In particular, Proposition 1 has to be checked more carefully. I tried to go through it, but it did not seem to make sense to me. Why is there an exp() term in the definitoin of the optimal trajectory probability? Why would minimising the KL divergence be enough to obtain an optimal policy? Perhaps it gives an optimal policy within the class of MRF policies, but that's not the same thing as the globally optimal policy.

Overall, I find the lack of clarity and in depth discussion of early related work disturbing, particularly with respect to the theoretical claims in the paper.

Decision: Reject