Graph Convolutional Reinforcement Learning
Authors: Jiechuan Jiang
Chen Dun
Tiejun Huang
Zongqing Lu
Venue:  (2020)

Abstract: Learning to cooperate is crucially important in multi-agent environments. The key is to understand the mutual interplay between agents. However, multi-agent environments are highly dynamic, where agents keep moving and their neighbors change quickly. This makes it hard to learn abstract representations of mutual interplay between agents. To tackle these difficulties, we propose graph convolutional reinforcement learning, where graph convolution adapts to the dynamics of the underlying graph of the multi-agent environment, and relation kernels capture the interplay between agents by their relation representations. Latent features produced by convolutional layers from gradually increased receptive fields are exploited to learn cooperation, and cooperation is further improved by temporal relation regularization for consistency. Empirically, we show that our method substantially outperforms existing methods in a variety of cooperative scenarios.

Published as a conference paper at ICLR 2020
GRAPH CONVOLUTIONAL REINFORCEMENT LEARNING
Jiechuan Jiang', Chen Dun? Tiejun Huang' & Zongqing Lu
!Peking University, "Rice University
ABSTRACT
Learning to cooperate is crucially important in multi-agent environments. The key is to understand the mutual interplay between agents. However, multi-agent environments are highly dynamic, where agents keep moving and their neighbors change quickly. This makes it hard to learn abstract representations of mutual interplay between agents. To tackle these difficulties, we propose graph convo- lutional reinforcement learning, where graph convolution adapts the dynamics of the underlying graph of the multi-agent environment, and relation kernels cap- ture the interplay between agents by their relation representations. Latent features produced by convolutional layers from gradually increased receptive fields are exploited to learn cooperation, and cooperation is further improved by temporal relation regularization for consistency. Empirically, we show that our method sub- stantially outperforms existing methods in a variety of cooperative scenarios.
INTRODUCTION
Cooperation is widespread phenomenon in nature from viruses, bacteria, and social amoehae to insect societies, social animals, and humans (Melis & Semmann, 2010). Human exceeds all other species in terms of range and scale of cooperation. The development of human cooperation is facilitated by the underlying graph of human societies (Ohtsuki et al., 2006; Apicella et al., 2012), where the mutual interplay between humans is abstracted by their relations.
is crucially important to enable agents to learn to cooperate in multi- environments for many applications, e.g., autonomous driving SShale--Shward et al., 2016), traffic light control (Wiering, 2000), smart grid control (Yang et al., 201 8a), and multi-robot control (Matignon et al., 2012). Multi- agent reinforcement learning (MARL) facilitated by communication (Sukhbaatar et al., 2016; Peng et al,, 2017; Jiang & Lu, 2018), mean field theory (Yang et al., 201 2018b), and causal influence (Jaques et al., 2019) have been exploited for multi-agent cooperation. However, communication among all agents (Sukhbaatar et al., 2016; Peng et al., 2017) makes it hard to extract valuable information for cooperation, while communication with only nearby agents (Jiang Lu, 2018) may restrain the range of cooperation. MeanField (Yang et al., 2018b) captures the interplay of agents by mean action, but the mean action eliminates the difference among agents and thus incurs the loss of im- portant information that could help cooperation. Causal influence (Jaques et al., 2019) is a measure of action influence, which is the policy change of an agent in the presence of an action of another agent. However, causal influence is not directly related to the reward of the environment and thus may not encourage cooperation. Unlike existing work, we consider the underlying graph of agents, which could potentially help understand agents' mutual interplay and promote their cooperation as it does in human cooperation (Ohtsuki et al., 2006; Apicella et al., 2012).
In this paper, propose graph convolutional reinforcement learning, where the multi-agent envi- ronment is modeled as a graph. Each agent is a node, the encoding of local observation of agent is the feature of node, and there is edge between node and its each neighbor. We apply convolution to the graph of agents. By employing multi-head attention (Vaswani et al., 2017) as the convolution kernel, graph convolution able to extract the relation representation between nodes and convolve the features from neighboring nodes just like neuron in convolutional neural network (CNN). Latent features extracted from gradually increased receptive fields are exploited to learn cooperative policies. Moreover, the relation representation is temporally regularized to help the agent develop consistent cooperative policy.
Work done at Peking University.
1 "Corrsponndence Zongqing Lu <xongging.ludopuuuucd......

---

Published as a conference paper at ICLR 2020
Graph convolutional reinforcement learning, namely DGN, is instantiated based deep Q net- work and trained end-to-end. DGN shares weights among all agents, making it easy to scale. DGN abstracts the mutual interplay between agents by relation kernels, extracts latent features by convo- lution, and induces consistent cooperation by temporal relation regularization. We empirically show the learning effectiveness of DGN in jungle and battle games and routing in packet switching net- works. We demonstrate that DGN agents are able to develop cooperative and sophisticated strategies and DGN outperforms existing methods in a large margin.
By ablation studies, we confirm the following. Graph convolution greatly enhances the cooperation of agents. Unlike other parameter-sharing methods, graph convolution allows the policy to be op- timized by jointly considering the agents in the receptive field of an agent, promoting the mutual help. Relation kernels that are independent from the input order of features can effectively capture the interplay between agents and abstract relation representation to further improve cooperation. Temporal regularization, which minimizes the KI. divergence of relation representations in succes- sive timesteps. boosts the cooperation, helping the agent to form a long-term and consistent policy in the highly dynamic environment with many moving agents.
2 RELATED WORK
MARL. MADDPG (Lowe et al., 2017) and COMA (Foerster et al., 2018) are actor-critic mod- els for the settings of local reward and shared reward, respectively. A centralized critic that takes as imput the observations and actions of all agents are used in both, which makes them hard to scale. PR-ORPO (Gupta et al., 2017) solves problems that were previously considered intractable by most MARL. algorithms via sharing of policy parameters that also improves multi-agent cooper- ation. However, the cooperation is still limited without sharing information among agents. Sharing parameters of value function among agents is considered in (Zhang et al., 2018) and convergence guarantee is provided for linear function approximation. However, the proposed algorithms and their convergence are established only in fully observable environments. Value propagation is proposed in (Qu et al., 2019) for networked MARL, which uses softmax temporal consistency connect value and policy updates. However, this method only works on networked agents with static connectivity. CommNet (Sukhbaatar al., 2016) and BiCNet (Peng et al., 2017) communicate the encoding of local observation among agents. ATOC (Jiang & Lu, 2018) and TarMAC (Das et al., 2019) enable agents to learn when to communicate and who to send messages to, respectively, using attention mechanism. These communication models prove that communication does help for cooperation. However, full communication costly and inefficient, while restrained communication may limit the range of cooperation.
Graph Convolution and Relation. Many important real-world applications come in the form of graphs. such as social networks (Kipf & Welling, 2017), protein-interaction networks (Duvenaud et al., 2015), and 3D point cloud (Charles et al., 2017). Several frameworks (Henaff et al., 2015; Niepert et al., 2016; Kipf & Welling, 2017; Velickovic et al., 2017) have been architected to extract locally connected features from arbitrary graphs. A graph convolutional network (GCN) takes as input the feature matrix that summarizes the attributes of each node and outputs node-level feature matrix. The function is similar to the convolution operation in CNNs, where the kernels are con- volved across local regions of the input to produce feature maps. Using GCNs, interaction networks can reason the objects, relations and physics in complex systems, which has been proven difficult for CNNs. A few interaction frameworks have been proposed predict the future states and under- lying properties, such as IN (Battaglia et al., 2016), VIN (Watters et al., 2017), and VAIN (Hoshen, 2017). Relational reinforcement learning (RRL) (Zambaldi et al., 2018) embeds multi-head dot- product attention (Vaswani et al., 2017) as relation block into neural networks to learn pairwise interaction representation of set of entities in the agent's 's state, helping the agent solve tasks with complex logic. Relational Forward Models (RFM) (Tacchetti et al., 2019) use supervised learning to predict the actions of all other agents based on global state. However, in partially observable environments, it is hard for RFM to learn to make accurate prediction with only local observation. MAGnet (Malysheva et al., 2018) learns relevance information in the form of a relevance graph, where relation weights are learned by pre-defined loss function based on heuristic rules, but relation weights in DGN are learned by directly minimizing the cemporal-differene error of value function end-to-end, Agarwal al. (2019) used attention mechanism for communication and proposed
2

---

Published as a conference paper at ICLR 2020
curriculum learning for transferable cooperation. However, these two methods require the objects in the environment are explicitly labeled, which is infeasible in many real-world applications.
3 METHOD
We construct the multi-agent environment as a graph, where agents in the environment are repre- sented by the nodes of the graph and each node has set of neighbors, IB, which is determined by distance other metrics, depending in i's communication range or local observation). Moreover, neighboring nodes can communicate with each other. The intuition behind this is neighboring agents are more likely and affect each other. In addition, in many multi-agent environments, it may be costly and less helpful to take all other agents into consideration, because receiving large amount of information requires high bandwidth and incurs high computational complexity, and agents cannot differentiate valuable information from globally shared information (Tan, 1993; Jiang & Lu, 2018). As convolu- tion can gradually increase the receptive field of an agent', the scope of cooperation is not restricted. Therefore, it is efficient and effective to consider only neighboring agents. Unlike the static graph considered in GCNs, the graph of multi-agent environment is dynamic and continuously changing over time as agents move or enter/leave the environment. Therefore, DGN should be able to adapt to the dynamics of the graph and learn as the multi-agent environment evolves.
the environment, and varies over time (e.g., the agents
interact with
3.1 GRAPH CONVOLUTION
The problem is formulated as Decentralized Par- tially Observable Markov Decision Process (Dec- POMDP), where at each timestep t each agent re- ceives a local observation of. which is the property of node i in the graph, takes action at and gets an in- dividual reward rς. The objective is to maximize the sum of all agents' expected returns. DGN consists of three types of modules: observation encoder, con- volutional layer and Q network, as illustrated in Fig- ure 1. The local observation of is encoded into a fea- ture vector h by MLP for ow-dimensional input or CNN for visual input. The convolutional layer inte- grates the feature vectors the local region (includ- ing node i and its neighbors B,) and generates the latent feature vector hit By stacking more convolu- tional layers, the receptive field of an agent gradu- ally grows, where more information is gathered, and thus the scope of cooperation can also increase. That is, by one convolutional layer, node i can directly acquire the feature vectors from the encoders of nodes in one-hop (i.e., BB,). By stacking two layers, node can get the output of the first con- volutional layer of the nodes in one-hop, which contains the information from nodes in two-hop. However, regardless of how many convolutional layers are stacked, node only communicates with its neighbors. This makes DGN practical in real-wont wolld applications, where each agent has lim- ited communication range. In addition, details of the convolution kernel will be discussed in next subsection.
Convolutional Layar (relation karnel)
Convolutional Layer (relation kerme))
Encoder (MLPICAN)
Figure 1: DGN consists of three modules: en- coder, convolutional layer, and Q network. All agents share weights and gradients accumu- lated to update the weights.
As the number and position of agents vary over time, the underlying graph continuously changes, which brings difficulties to graph convolution. To address the issue, we merge all agents' feature vectors at time into a feature matrix F' with size N L the order of index, where N is the number of agents and L is the length of feature vector. Then,
construct adjacency matrix Of with size (IB. + 1) x N for agent i, where the first row is the one-hot representation of the index of node i, and the jth row, neighbor. Then, we can obtain the feature vectors in the local region of node i by C x Ft.
2, .., BBal + 1, is the one-hot representation of the index of the (j 1)th
Inspired by DenseNet (Huang al., 2017), for each agent, the features of all the preceding layers concatenated and fed into the Q network, so as to assemble and reuse the observation representation
TThe receptive field of agent convolutional layer its perceived agents that layer.
3

---

Published as a conference paper at ICLR 2020
and features from different receptive fields, which respectively have distinctive contributions to the strategy that takes the cooperation at different scopes into consideration.
During training, at each timestep, we store the tuple (O, O', R, C) in the replay buffer, where O = (or ... ON } is the set of observations, A = {a aN) is the set of actions, O' = for, (N) is the set of next observations, R {ri, NN) is the set of rewards, and C= (C,,... Gu} is the set of adjacency matrix. Note that we drop time in the notations for simplicity. Then, we sample random minibatch of size S from the replay buffer and minimize the loss
N Σ
((0) =
y3 Q (00,c,0000)
(I)
Onc ,0, C O denotes the set of observations of the agents in i's receptive fields determined by C, y is the discount factor, and Q function, parameterized by 8, takes O&c as input and outputs Q value for agent i. The action of agent can change the graph at next timestep. Ideally, Q function should be learned on the changing graph. However, the graph may change quickly, which makes Q network difficult to converge. Thus, we keep C unchanged in two successive timesteps when computing the Q-loss in training to ease this learning difficulty. The gradients of Q-loss of all agents are accumulated to update the parameters. Then, we softly update the target network as 0' 30 + (1 3)0'.
where yi -. + +-ymaxx.--00 (0' dis
Like CommNet (Sukhbaatar et al., 2016), DGN can also be seen as factorization of a centralized policy that outputs actions for all the agents to optimize the average expected return. The factoriza- tion is that all agents share 9 and the model of each agent is connected to its neighbors, dynamically determined by the graph of agents at each timestep. More convolutional layers (i.e., larger receptive field) yield a higher degree of centralization that mitigates non-stationarity. In addition, unlike other methods with parameter-sharing samples experiences based on the graph of agents, not individual agents, and thus takes into con- sideration the interactions between agents. Nevertheless, the parameter-sharing of DGN does not prevent the emergence of sophisticated cooperative strategies, as we will show in the experiments. Note that during execution each agent only requires the (latent) features from its neighbors (e.g., via communication) regardless of the number of agents, which makes DGN easily scale.
e.g., DQN, that sample experiences from individual agents, DGN
3.2 RELATION KERNEL
Convolution kernels integrate the feature in the receptive field to extract the latent feature. One of the most important properties is that the kernel should be independent from the order of the input feature vectors. Mean operation as in CommNet (Sukhbaatar et al., 2016) meets this requirement, but it leads to only marginal performance gain. BiCNet (Peng et al., 2017) uses the learnable kernel, i.e., RNN. However, the input order of feature vectors severely impacts the performance, though the affect is alleviated by bi-direction mechanism. Further, convolution kernels should be able to learn how to abstract the relation between agents so as to integrate their input features.
Inspired by RRL (Zambaldi et al., 2018), we use multi-head dot-produe attention as the convolu- tional kernel to compute interactions between agents. For each agent i, let B+, denote B, and The input feature of each agent is projected to query, key and value representation by each independent attention head. For attention head m, the relation between and j E B45 is computed
exp (T Wahh (WThy)")
(2)
EKE exp (T With (W
where 7 is a scaling factor. For each attention head, the value representations of all the input features are weighted by the relation and summed together. Then, the outputs of M attention heads for agent i concatenated and then fed into function a, i.e., one-layer MLP with ReLU non-linearities, to produce the output of the convolutional layer,
hi = a (concatenate)
Σ JEB+
Wilhy, Vm E M)).
(3)
Figure 2 illustrates the computation of the convolutional layer with relation kernel. Multi-head attention makes the kernel independent from the order of input feature vectors, and allows the kemel
4

---

Published as a conference paper at ICLR 2020
to jointly attend to different representation subspaces. More attention heads give more relation representations and make the training more stable empirically (Vaswani et al., 2017). Moreover, with multiple convolutional layers, higher order relation representations can be extracted, which effectively capture the interplay between agents and greatly help to make cooperative decision.
3.3 TEMPORAL RELATION REGULARIZATION
Cooperation is a persistent and long-term process. Who to cooperate with and how cooperate should be consistent and stable for least short period of time even when the state/feature of surrounding agents changes. Thus, the relation representation, L.e. the at- tention weight distribution over the neighbor- ing agents produced by the relation kernel (Equation 2), should be also consistent and stable for short period of time. To make the learned attention weight distribution stable over timesteps, we propose temporal relation regularization, In- spired by cmmporal-differoen the target for the current attention weight distribution. We adopt KL divergence to measure how the current attention weight distribution is different from the target attention weight distribution. Mini- mizing the KL divergence as regularization will encourage the agent to form the consistent relation representation and hence consistent cooperation. In CNNs/GCNs, higher layer learns more abstract representation. Similarly, in DGN, the relation representation captured by upper layer should be more abstract and stable. Thus, we apply temporal relation regularization to the upper layer. Mov- ing average and RNN structures might help the relation representation be stable in static graph. However, in dynamic environment where the neighbors of the agent quickly change, averaging or integrating cannot be performed on the attention weights of different neighbors.
12.00
Ln 0 adjacincy matiie
feature matio
Figure 2:
Illustration of computation the convolutional layer with relation kernel of multi-hcad attention.
learning, we use the attention weight distribution in the next state as
should be noted that we only use target network produce the target Q value. For the calculation of KL divergence between relation representations in two timesteps, we apply current network to the next state to produce the target relation representation. This is because relation representation is highly correlated with the weights of feature extraction. But update of such weights in target network always lags behind that of current network, making the relation representation produced by target network not consistent with that produced by current network.
Let 9% (O..c 0) denotes the attention weight distribution of relation representations of attention head m at convolutional layer for agent i. Then, with temporal relation regularization, the loss is modified as below
M Σ
Σ =
((0) = E
+
1 M
(Or: (O,c: (4)
where À is the coefficient for the regularization loss. Temporal relation regularization of upper layer in DGN helps the agent to form long-term and consistent action policy in the highly dynamical environment with many moving agents. This will further help agents to form cooperative behavior since many cooperative tasks need long-term consistent cooperation among agents get the final reward. We will further analyze this in the experiments.
4 EXPERIMENTS
For the experiments, we adopt grid-world platform MAgent (Zheng et al., 2017). In the 30 x 30 grid-world environment, each agent corresponds to one grid and has a local observation that con- tains a square view with 11 x 11 grids centered at the agent and its own coordinates. The discrete actions are moving or attacking. Two scenarios, battle and jungle, are considered to investigate the cooperation among agents. Also, we build an environment, rouling, that simulates routing in packet switching networks. These three scenarios are illustrated in Figure 3. In the experiments, we com- pare DGN with independent Q-learning, DQN, which is fully decentralized, CommNet (Sukhbaatar et al., 2016), and MeanField Q-learning (MFQ) (Yang et al., 2018b). We also evaluate two vari- ants of DGN for ablation study, which are DGN without temporal relation regularization, denoted
5

---

Published as a conference paper at ICLR 2020
reward for being kileed
reward +2 for attacking other egent
reward -4 for being sitacked
reward 10 for reaching the destination
reward -0 for attempling to enter the loaded link
bandwidth
reward +5 for ettacking the enemy
reward +1 for eating
food
router
packot
choose one of the links nothing
Figure Illustration of experimental scenarios: battle (left), (mid), and routing (right).
as DGN-R, and further DGN-R with mean kernels instead of relation kernels, denoted as DGN-M. In the experiments, DGN and the baselines are parameter-sharing and trained using Q-learning Moreover, to ensure the comparison is fair, their basic hyperparameters are the same and their parameter sizes are also similar. Please refer to Appendix for hyperparameters and experimental settings. The code of DGN is available https: /ttpt//tttttt///tt www/cco-o//p// Btt//PKU-AI-EEge//GG..
4.1 BATTLE
In this scenario, agents learn to fight against L enemies who have superior abilities than the agents. The moving or attacking range of the agent is the four neighbor grids, however, the enemy can move to one of twelve nearest grids or attack one of eight neighbor grids. Each agent/enemy has six hit points (i.e., being killed by six attacks). After the death of an agent/enemy, the balance will be easily lost and hence we will add new agent/enemy at random location to maintain the balance. By that, we can make fair comparison among different methods in terms of kills, deaths and kill-deatt ratio besides reward for given timesteps. The pretrained DQN model built-in MAgent takes the role of enemy. As individual enemy much powerful than individual agent, an agent has to collaborate with others to develop coordinated tactics to fight enemies. Moreover, as the hit point of enemy is six, agents have to consistently cooperate to kill an enemy.
We trained all the models with the setting of N 20 and = 12 for 2000 episodes. Figure shows their leamn- ing curves in terms of mean reward. For all the mod- els, the shadowed area enclosed by the min and max value of three training runs, and the solid line in middle is the mean value (same for jungle and routing). DGN con-
mesn reward
DGN
verges to much higher mean reward than other baselines, and its learning curve is more stable. MFQ outperforms CommNet and DQN which first get relative high reward, but eventually converge to much lower reward. As ob- served the experiment, at the beginning training, DQN and CommNet learn sub-optimum policies such gathering as a group in a corner to avoid being attacked,
DCN
DCN-4
Mro
CommWer
DCN
0.6-
500
episode
Figure 4: Learning curves in battle.
since such behaviors generate relatively high reward. However, since the distribution of reward is uneven, i.e., agents at the exterior of the group are casily attacked, learning from the "low reward experiences" produced by the sub-optimum policy, DQN and CommNet converge more passive policies, which lead to much lower reward. We evaluate DGN and the baselines by running 30 test games, each game unrolled with 300 timesteps. Table shows the mean reward, kills, deaths, and kill-death ratio.
DGN agents learn series of tactical maneuvers, such encireling and envelopment of single flank. For single enemy, DGN agents learn to encircle and attack it together. For a group of en-
Table 1: Battle
DGN DGN-R DGN-M MFQ CommNet
DQN
mean reward
0.91
0.84
0.50
0.70
0.03
-0.03
# kills
220
208
121
193
7
2
# deaths
101
84
92
27
74
kill-death ratio
2.27
2.06
1.44
2.09
0.26
0.03

---

Published as a conference paper at ICLR 2020
emies, DGN agents learn to move against and attack one of the enemy's open flanks, as depicted in Figure 5a. CommNet agents adopt an active defense strategy. They seldom launch attacks but rather run away or gather together to avoid being attacked. DQN agents driven by self-interes, fail to learn a rational policy. They are usually forced into a corner and passively react to the enemy's attack, as shown in Figure 5b. MFQ agents do not effectively cooperate with each other because the mean action incurs the loss of important information that could help cooperation. In DGN, relation kernels can extract high order relations between agents through graph convolution, which can be easily exploited to yield cooperation. Therefore, DGN outperforms other baselines.
Ablations. As shown in Figure and Table comparing DGN and DGN-R, we see that the re- moval of temporal relation regularization incurs slight drop in performance. In the experiment, it observed that DGN agents indeed behave more consistently and synchronously with each other, while DGN-R agents are more likely to be distracted by the new appearance of enemy or friend nearby and abandon its original intended trajectory. This results in fewer appearances of successful formation of encircling of a moving enemy, which might need consistent cooperation of agents to move across the field. DGN agents often overcome such distraction and show more long-term strat- egy and aim by moving more synchronously to chase the enemy until encircle and destroy it. From this experiment, we can see that temporal relation regularization indeed helps agents to form more consistent cooperation. Moreover, comparing DGN-R and DGN-M, we confirm that relation kernels that abstract the relation representation between agents indeed helps to learn cooperation. Although DGN-M and CommNet both use mean operation, DGN-M substantially outperforms CommNet. This is attributed to graph convolution can effectively extract latent features from gradually increased receptive field. The performance of DGN with different receptive fields is available Appendix.
Encireling
Hesitttion
Innoolopmeer single flank
Passively cacaping
Recomrbble allscaion
Flare confiit
Sneak wttack
Being the COrTET
(a) DGN in battle
(b) DQN in battle
(c) DGN in jungle
(d) DQN in jungle
Figure 5: Illustration of representative behaviors of DGN and DQN agents in battle and jungle.
4.2 JUNGLE
This scenario is moral dilemma. There are N agents and L foods in the field, where foods are stationary. An agent gets positive reward by eating food, but gets higher reward by attacking other agent. At each timestep, each agent move to attack one of four neighboring grids. Attacking a blank grid gets a small negative reward (in- hibiting excessive attacks). This experiment is exam- ine whether agents can learn collaboratively sharing re- sources rather than attacking each other. We trained all the models in the setting of N = 20 and L = 12 for 2000 episodes. Table 2 shows the mean reward and number of attacks between agents over 30 test runs, each game un- rolled with 120 timesteps. Figure 6 shows their learning curves. DGN outperforms all the baselines during training and test in terms of mean reward and number attacks between agents. observed that DGN agents can properly select the close food and seldom hurt each other, and the food can be allocated rationally by the surrounding agents, as
5.5
mwan raward
0.2-
-14
-16
Commiot
-2.8
DON
5000
1252
2500
opisode
Figure 6: Learning curves in jungle.
Table 2: Jungle
DGN MFQ CommNet DQN
mean reward
0.66
0.62
0.30
0.24
attacks
1.14
2.74
5.44
7.35
7

---

Published as a conference paper at ICLR 2020
Table 3: Routing
(N,
Floyd Floyd w/ BL
DGN
MFQ
CommNet
DQN
mean reward delay throughput
1.23
1.02
0.49
0.18
(20, 20)
6.3
8.7
8.0
9.4
18.6
46.7
3.17
2.30
2.50
2.13
1.08
0.43
mean reward delay 6.3
0.86
0.78
0.39
0.12
(40, 20)
13.7
9.8
11.8
23.5
83.6
throughput 6.34
2.91
4.08
3.39
1.70
0.49
mean reward delay 6.3
0.73
0.59
0.31
0.06
(60, 20)
14.7
12.6
15.5
27.0
132.0
throughput 9.52
4.08
4.76
3.87
2.22
0.45
shown in Figure 5c. Moreover, attacks between DGN agents are much less than others, egg. 2x less than MFQ. Sneak attack, fierce conffict, and hesitation are the characteristics of CommNet and DQN agents, illustrated in Figure 5d, verifying their failure of learning cooperation.
4.3 ROUTING
The network consists of L routers. Each router is randomly connected to a constant number of routers (three in the experiment), and the network topology is stationary. There are data packets with random size, and each packet is randomly assigned source and destination router. If there are multiple packets with the sum size larger than the bandwidth of a link, they cannot go through the link simultaneously. In the experiment, data packets agents, and they aim quickly reach the destination while avoiding congestion. At each timestep. the observation of a packet is its own attributes (i.e., current location, destination, and data size), the attributes of cables connected to its current location (i.e., load, length), and neighboring data packets (on the connected cable or routers). It takes some timesteps for data packet to go through cable, linear function of the cable length. The action space of packet is the choices of next hop. Once the data packet arrives at the destination, it leaves the system and another data packet enters the system with random initialization.
We trained all the models with the setting of N = 20 and L 20 for 2000 episodes. Figure shows their learning curves. DGN converges much higher mean reward and more quickly than the baselines. We evaluate all the models by running 10 test games, each game unrolled with 300 timesteps. Table 3 shows the mean reward, mean delay of data packets, and throughput, where the delay of packet is measured by the timesteps taken from source to destination and the throughput is the number of delivered packets per timestep.
To better interpret the performance of the models, we cal- culate the shortest path for every pair nodes in the net-
MFG Commbtt
work using Floyd algorithm. Then, during test, di- rectly calculate the delay and throughout based on the shortest path of each packet, which is Floyd in Table 3.
mean reward
Note that this delay is without considering the bandwidth limitation (i.e., data packets can go through any link si- multancously). Thus, this is the ideal case for the routing problem. When considering the bandwidth limit, we let each packet follow its shortest path, and if link is con- gested, the packet will wait the router until the link is unblocked. This is Floyd with Bandwidth Limit (BI. in Table 3, which can be considered as the practical solution. As shown in Table 3, the performance of DGN is much better than other models and Floyd with BL.
0.6-
6.4-
6.-
0.2
250
500
750
1000
1250
2500
3750
2002
episode
Figure 7: Learning curves in routing.
In the experiment, it observed that DGN agents tend to select the shortest path to the destination, and more interestingly, learn to select different paths when congestion is about to occur. DQN agents cannot learn the shortest path due to myopia and easily cause congestion at some links without considering the influence of other agents. Communication indeed helps MFQ and CommNet outperform DQN. However, they are unable to develop the sophisticated strategies as DGN does and eventually converge much lower performance.
8

---

Published as a conference paper at ICLR 2020
To investigate how network traffic affects the performance of the models, performed the exper- iments with heavier data traffic, i.e., N = 40 and = 20, where all the models are directly applied to the setting without retraining. From Table 3, can that DGN is much better than Floyd with BI., and MFQ is also better than Floyd with BI.. The reason is that Floyd with BL (i.e. simply following the shortest path) is favorable when traffic is light and congestion is rare, while it does not work well when traffic is heavy and congestion easily occurs. We further apply all the models learned in 20 and 20 the setting of N 60 and L 20. DGN still outperforms Floyd with BL, while MFQ become worse than Floyd with BL. It is observed in the experiments that DGN without retraining outperforms Floyd with BL up N 140 and From the experiments, we can see that our model trained with fewer agents can well generalize to the setting with much more agents, which demonstrates that the policy that takes as input the integrated features from neighboring agents based on their relations scales well with the number of agents.
20, available in Appendix.
5 CONCLUSIONS
We have proposed graph convolutional reinforcement learning. DGN adapts to the dynamics of the underlying graph of the multi-agent enviromment and exploits convolution with relation kernels to extract latent features from gradually increased receptive fields for learning cooperative strategies. Moreover, the relation representation between agents are temporally regularized to make the coop- eration more consistent. Empirically, DGN significantly outperforms existing methods in variety of cooperative multi-agent scenarios.
ACKNOWLEDGMENTS
This work was supported part by NSF China under grant 61872009, Huawei Noah's 's Ark Lab, and Peng Cheng Lab.
REFERENCES
Akshat Agarwal, Sumit Kumar, and Katia Sycara. Learning transferable cooperative behavior in multi-agent teams. arXiv preprint (rXiv:1906.0/200) 2019.
Coren L. Apicella, Frank W Marlowe, James Fowler, and Nicholas A Christakis. Social networks and cooperation in hunter-gatherers. Nature, 481(7382):497, 2012.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In NeurlPS, 2016.
R Qi Charles, Hao Su, Mo Kaichun, and Leonidas J Guibas. Pointnet: Deep learning point sets for 3d classification and segmentation. In CVPR, 2017.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Michael Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. ICML, 2019.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Capuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In NeurlPS, 2015.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI, 2018.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In AAMAS, 2017.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:7506.051633 2015.
Yedid Hoshen. Vain: Attentional multi-agent predictive modeling. In NewrlPS, 2017.
Gao Huang. Zhuang Liu, Laurens van der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In CVPR, 2017.

---

Published as a conference paper at ICLR 2020
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcchre, Pedro A Ortega. DJ Strouse, Joel Z Leibo, and Nando de Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. ICML, 2019.
Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent cooperation. NeurlPS, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competitie environments. In NeurlPS, 2017.
Aleksandra Malysheva, Tegg Taekyong Sung, Chae-Bong Sohn, Daniel Kudenko, and Aleksei Shpilman. Deep multi-agent reinforcement learning with relevance graphs. arXiv preprint arXiv:1811.12551 2018.
Laëtitia Matignon, Laurent Jeanpierre, Abdel-Illat Mouaddib, et al. Coordinated multi-robot explo- ration under communication constraints using decentralized markov decision processes. In AAAI, 2012.
Alicia P Melis and Dirk Semmann. How is human cooperation different? Philosophical Transac- tions of the Royal Society of London B: Biological Sciences, 365(1553):2663 2674, 2010.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In ICML, 2016.
Hisashi Ohtsuki, Christoph Hauert, Frez Lieberman, and Martin A Nowak. A simple rule for the evolution of cooperation graphs and social networks. Nature, 441((092):502, 2006.
Peng Peng. Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent snnrrcttionally-ooodniiin nets: Emergence of buman-level coordination learning to play starcraft combat games. arXiv preprint arXiv: /703. 10069, 2017.
Chao Qu, Shie Mannor, Huan Xu, Yuan Qi, Le Song, and Junwu Xiong. Value propagation for decentralized networked deep multi-agent reinforcement learning. In NeurlPS, 2019.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv./610.03295, 2016.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropaga- tion. In NeurlPS, 2016.
Andrea Tacchetti, H Francis Song, Pedro AM Mediano, Vinicius Zambaldi, Neil C Rabinowitz, Thore Graepel, Matthew Botvinick, and Peter W Battaglia. Relational forward models for multi- agent learning. In ICLR, 2019.
Ming Tan. Multi-agent reinforcement learning: Independent cooperative agents. In ICML, 1993.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NewrIPS, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua 2017.
Bengio. Graph attention networks. arXiv preprint
Nicholas Watters, Andrea Tacchetti, Theophane Weber, Razvan Pascanu, Peter Battaglia, and Daniel Zoran. Visual interaction networks. arXiv preprini arXiv: 706.0133,,, 2017.
MA Wiering. Multi-agent reinforcement learning for traffic light control. In ICML, 2000.
Yaodong Yang. Jianye Hao, Mingyang Sun, Zan Wang, Changjic Fan, and Goran Strbac. Recurrent deep multiagent g-laarning for autonomous brokers in smart grid. In IJCAI, 2018a.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. In ICMI., 2018b.
10

---

Published as a conference paper at ICLR 2020
Vinicius Zambaldi, David Raposo, Adam Santoro, Victor Bapst, Yujia Li, Igor Babuschkin, Karl Tuyls, David Reichert, Timothy Lillicrap, Edward Lockhart, et al. Relational deep reinforcement learning. arXiv preprint arXiv:1806.01888 2018.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Başar. Fully decentralized multi- agent reinforcement learning with networked agents. In ICML, 2018.
Lianmin Zheng, Jiacheng Yang, Han Cai, Weinan Zhang, Jun Wang, and Yong Yu. Magent: A many-agent reinforcement learning platform for artificial collective intelligence. arXiv preprint arXiv:1712.00600, 2017.

---

Published as a conference paper at ICLR 2020
A HYPERPARAMETERS
Table 4 summarizes the hyperparameters used by DGN and the baselines in the experiments.
Table 4: Hyperparameters
Hyperparameter
DGN
CommNet
MFQ
DQN
discount (r)
0.96, 0.96, 0.98
batch size
10
buffer capacity
2 10
0.01
and decay optimizer
0.6/0.996
Adam 10
learning rate
# neighbors # convolutional layers attention heads
3
0.25
0.03
encoder MIP layers # encoder MLP units
2
(512, 128)
(512, 128)
Q network MLP activation initializer
afline transformation affine transformation (1024, (1024, 256)
ReLU random normal
B EXPERIMENTAL SETTINGS
In jungle, the reward is 0 for moving, +1 for attacking (cating) the food, +2 for attacking other agent, -4 for being attacked, and -0.01 for attacking blank grid. In battle, the reward is +-5 for attacking the enemy, -2 for being killed, and -0.01 for attacking blank grid. In routing, the bandwidth of each link is the same and set to Each data packet is with a random size between and 1. If the link to the next hop selected by data packet is overloaded, the data packet will stay the current router and be punished with a reward -0.2. Once the data packet arrives at the destination, it leaves the system and gets reward +10. In the experiments,
fix the size of B 3, because DGN currently implemented based on TensorFlow which does not support dynamic computing graph (varying size of B). We also show how different sizes of affect DGN's performance in the following. Indeed, DGN adapts to dynamic environments, no matter how the number of agents changes, how the graph of agents changes, and how many neighbors each agent has.
C ADDITIONAL EXPERIMENTS
As aforemenntooeed, larger receptive field yields a higher degree of centralization that mitigates non- stationarity. We also investigate this in the experiments. First examine how DGN performs with different number convolution layers. As illustrated in Figure 8, two convolutional layers indeed yield more stable learning curve than one layer as expected.
Foodd great
#23ode
apicde
apiiace
Figure 8: DGN with different number of convolutional layers in battle.
Figure 9: DGN with different number of neighbors for each agent in jungle.
Learning curves of DGN fixed graph and unfixed graph in battle.
Figure 10:
12

---

Published as a conference paper at ICLR 2020
We also investigate how the size of neighbors [B affects the performance of DGN. We set [B] of each agent to 1, 2, 3 and in jungle. As illustrated in Figure 9, when [B] increases from to 3, the performance improves. However, when [B| 4. the performance drops, equivalent [B] 1. In addition, as shown in Figure 6, the full communication method, CommNet, has very limited performance. These verify that it may be less helpful and even negatively affect the performance take all other agents into consideration.
Ideally, Q function should be learned the changing graph of agents. However, the quickly chang- ing graph can make Q function difficult to converge. Thus, we fix the graph in two successive timesteps to mitigate the effect of changing graph and ease the learning difficulty. As shown in Figure 10, the learning curve of fixed graph indeed converges faster than that of unfixed graph. As keeping the graph of agents unchanged is necessary for temporal relation regularization, for fair comparison, we also remove temporal relation regularization for fixed graph.
We also perform additional ex- periments to compare DGN with ATOC and TarMAC Battle. As shown in Figure 11, DGN outperforms ATOC. The reason that LSTM kernel is worse than multi-head attention kernel in capturing relation between agents, Like CommNet, Tar- MAC is also full communica- tion method. Similarly, DGN also outperforms TarMAC. This again verifies that receiving re- dundant information may negatively affect the performance.
215
Flyy
20.
204
68
122
1908
Die
20
Pacees
Figure 11: Learning curves
Figure 12: DGN versus Floyd with BL under increasingly heavier traf- fie in routing.
DGN, ATOC and TarMAC in bat- tle.
We also conducted additional experiments in routing to compare DGN (learned in the setting of = 20 and L 20) and Floyd with BL under increasingly heavier traffic, in terms of mean delay. As shown in Figure 12, DGN continuously outperforms Floyd with BL up to N 140. After that, Floyd with BL outperforms DGN. The reason is that when the traffic becomes so heavy, the network fully congested and there is way improve the performance. DGN learned in much lighter traffic may still try to find better routes, but this incurs extra delay.
Figure 13 and Figure 14 show the learning curves of DGN, DGN-R and DGN-M in jungle and routing, respectively. We can see that DGN and DGN- R outperforms DGN-M. DGN slightly outperforms DGN-R routing, and they performs sim- ilarly in jungle. The reason is that in both jungle and routing the agents do not require cooper- ation consistency as much as in battle. In battle the agents need to cooperatively and consistently attack enemy since it has six hit points. However, in jun- gle agents seldom move once they reach the status of sharing food, while in routing data packets (agents) with different destinations seldom share many links (cooperate continuously) along their paths.
Doin
moai reward
now
26
50
1236
1956
1hi8 1965
356 836
150
1999 2909 1950 The 198
Figure 13: Learning curves of DGN, DGN-R, and DGN-M in jungle.
Figure Learning curves of DGN, DGN-R, and DGN-M in routing.
13


Reviews:
[{"review_id": "SygTyGcOcr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 addresses the problem of coordination in the multi-agent reinforcement learning setting. It proposes the value function factorization similar to independent Q-learning conditioning on the output of the graph convolutional neural network, where the graph topology is based on the agents’ nearest neighbours. The paper is interesting and has some great ideas, for example, KL term to ensure temporal cooperation consistency. However, the paper has its drawbacks and I feel obliged to point them out below. I vote for the weak acceptance of this paper.\n\nOne of the main drawbacks of the paper is that it is extremely hard to grasp. Even the Abstract and Introduction are hard to understand without having a pass over the whole paper. The authors often use vague terms such as 'highly dynamic environments' or 'dynamics of the graph' which make it hard to understand what they mean. The paper would benefit from a more precise language. Some of the important notions of the paper are used before they are introduced, which make the general picture very hard to understand and to relate the work to the existing research.\n\n'Related Work' section seems to be missing some recent work applying graph neural networks to multi-agent learning settings:\n• Malysheva, Aleksandra, Tegg Taekyong Sung, Chae-Bong Sohn, Daniel Kudenko, and Aleksei Shpilman. \"Deep Multi-Agent Reinforcement Learning with Relevance Graphs.\" arXiv preprint arXiv:1811.12557 (2018).\n• Agarwal, Akshat, Sumit Kumar, and Katia Sycara. \"Learning Transferable Cooperative Behavior in Multi-Agent Teams.\" arXiv preprint arXiv:1906.01202 (2019).\n\nMy questions to the authors:\n\n• In section 3 you mention 'a set of neighbours ..., which is determined by distance or other metrics'. Can you elaborate on that? What are these metrics in your case?\n• Just before the Section 3.1, you say 'In addition, in many multi-agent environments, it may be costly and less helpful to take all other agents into consideration.' Have you run any experiments on that? In the appendix, you show, that making the neighbourhood smaller negatively affects the performance, but what if you make it bigger? Ideally, I would like to see an extended version of Figure 8 and 9 in the main part of the paper since they are very interesting and important for the claims the paper makes.\n• At the end of Section 3.1, you mention the soft update of the target network. Later, in 3.3, you say that that you do not use the target network. Can you elaborate more on that?\n• In Equation 4, is it a separate KL for each of the attention heads? If yes, this is not clear from the formula.\n• It will be useful to see the ablation experiments for all of the testbeds, not only for Battle.\n• Why do you think the DQN performance drops in the second half of the training in Figure 4 for all of the runs?\n• Have you tried summation instead of the mean aggregation step?\n\nI will put comments for particular parts of the paper below.\n\nABSTRACT\n\n>>> ...environments are highly dynamic\n\nWhat do you mean precisely here?\n\n>>> ...graph convolution adapts to the dynamics of the underlying graph of the multi-agent environment\n\nWhat is the 'dynamics of the underlying graph'? What is the 'graph of the multi-agent environment'?\n\n>>> 'coordination is further boosted'\n\nNot sure that 'boosted' is the right word here.\n\nINTRODUCTION\n\n>>> '...where mutual interplay between humans is abstracted by their relations'\n\nNot sure what it means.\n\n>>> we consider the underlying graph of agents...\n\nThe agent graph has not been introduced yet.\n\n>>> DGN shares weights among all agent(s) making it easy to scale\n\nWhat do you mean precisely by 'easy to scale'? Can you support this claim?\n\n>>> We empirically show the learning effectiveness of DGN in jungle\n\nNeeds a reference to the testbed.\n\n>>>  ... interplay between agents and abstract relation representation\n\nWhat is 'abstract relation representation?\n\n>>> We consider partially observable environments.\n\nWhat do you mean precisely by that? What is the MDP formalism most suitable for your problem statement? What is objective under your formalism?\n\n>>> However, more convolutional layers will not increase the local region of node i.\n\nWhat do you mean by that?\n\n>>> As the number and position of agents vary over time, the underlying graph continuously changes, which brings difficulties to graph convolution.\n\nWhat kind of difficulties?\n\n>>> As the action of agent can change the graph at next timestep which makes it hard to learn Q function.\n\nWhy does it make it hard?\n\n>>> DGN can also be seen as a factorization of a centralized policy that outputs actions for all the agents to optimize the average expected return.\n\nIt would be useful for the reader to compare your approach with all the others type of the value function factorization. To me, your approach looks like a more sophisticated version of independent Q-learning, is that true?\n\nMinor comments:\n\n* In 3.2 it would be very helpful to put the dimensions for all of the variables for easier understanding.\n* The brackets in the equation 3 are not very clear (what are you concatenating across?)\n* In section 4, when describing an environment you say 'local observation that contains a square view with 11x11 grids'. What is the total size of the environment?\n* The performance plots for Battle include ablations before the ablation subsection is introduced. This is a bit confusing.\n* All figures/tables captions should be more detailed and descriptive.\n* ‘However, causal influence is not directly related to the reward of environment.’ Should be ‘of the environment’.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "SJx0QUYOdB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 introduces Graph Convolutional Reinforcement Learning (referred to as DGN). DGN is a Deep Q-Learning (DQN) agent structured as a graph neural network / graph convolutional network with multi-head dot product attention as a message aggregation function. Graphs are obtained based on spatial neighborhoods (e.g. k nearest neighbors) or based on network structure in the domain. DGN considers a multi-agent setting with a centralized learning algorithm and shared parameters across all (controlled) agents, but individually allocated reward. Further, the paper considers environments where other non-learning agents are present which follow a pre-trained, stationary policy. In addition to the attention-based multi-agent architecture, the paper introduces a regularizer on attention weights similar to the use of target networks in DQN, to stabilize training. Results demonstrate that the proposed model architecture outperforms related earlier agent architectures that do not use attention or use a fully-connected graph.\n\nOverall, this paper addresses an interesting problem, introduces a novel combination of well-established architecture/agent building blocks and introduces a novel regularizer. The novelty and significance of the contributions, however is limited, as many recent works have explored using graph-structured representations and attention in multi-agent domains (e.g. VAIN: Hoshen (NeurIPS 2017), Zambaldi et al. (ICLR 2019), Tacchetti et al. (ICLR 2019)). The combination of these blocks and the considered problem setting is novel, but otherwise incremental. Nonetheless, the results are interesting, the overall architecture is simple (which I consider to be a good sign), and the attention regularizer is novel, hence I would rate this paper as relevant to the ICLR audience.\n\nMy main concern with this paper is clarity of writing: I have the feeling that important details are missing and some modeling decisions and formulas are difficult to understand. For example, I found section 3.3 difficult to read. The following sentences/statements need revision or further explanation:\n* “Intuitively, if the relation representation produced by the relation kernel of upper layer truly captures the abstract relation between surrounding agents and itself, such relation representation should be stable/consistent” (Please clarify)\n* “We use the attention weight distribution in the next state as the target for the current attention weight distribution” (What is the reasoning behind this? Would an exponential moving average of attention logits/weights work as well?)\n* “While RNN/LSTM forces consistent action, regardless of cooperation” (unclear)\n* “Since we only focus on the self-consistent of the relation representation based on the current feature extraction network we apply current network to the next state to produce the new relation representation instead of the target network as in deep Q learning” (unclear)\n* The KL term in Eq. 4 is odd: z_i is defined as G^K and vice versa, neither of them appear to be distributions. I suppose one of the two arguments of the KL term should be the attention distribution for the current time step and the other argument for the next time step (if I understood the motivation in the earlier paragraph correctly), but this is not evident from Eq. 4.\n* KL is not symmetric -- what motivates the particular ordering in your case? Did you consider symmetric divergences such as Jensen-Shannon divergence (JSD)?\n\nI also wonder about the necessity of assembling adjacency matrices per node to create an intermediate ordered representation of the neighborhood on which, afterwards, an order-invariant operation such as mean pooling or self-attentive pooling is applied. Wouldn't it be more efficient to implement these operations directly using sparse scatter/gather operations as most recent GNN frameworks implement these techniques (e.g. PyTorch Geometric or DeepMind's graph_nets library)?\n\nFurther, important experimental details are missing, e.g., how observations / node features are represented / obtained from the environment and preprocessed. Do you encode position (continuous/discrete) and normalize in some way? It should further be mentioned that some of the baselines are trained with a different training algorithm and do not only differ in agent architecture (e.g. CommNet) — what is the effect of this?\n\nExperimentally, the results seem sound, but the variance in the results is suprisingly low (see e.g. Figure 7 DQN) — did you change the random seed between runs (both environment seed and the seed for initializing the agent weights)?\n\nOverall, this paper is interesting but needs revision in terms of clarity. Novelty is incremental, but if the paper would otherwise be very well written, I think it could qualify for acceptance. In its current state, I recommend a weak reject.\n\n\n--- UPDATE AFTER REVISION ---\nThe clarity in the revised manuscript is significantly improved and I feel confident in recommending acceptance of the paper. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byxv13sAFS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 an algorithm allowing \"cooperation\" between agents in multi-agent reinforcement learning, modeling agents as nodes in a graph. Each agent having only a partial view of the environment, the proposed algorithm uses multi-head attention as a (graph) convolution kernel but otherwise remains similar to the DQN algorithm. Performance is evaluated on three tasks using the MAgent framework.\n\nThe paper is reasonably well motivated, grounded and written. It addresses an interesting question: how to make agents cooperate in an efficient way? It does so by combining ideas from two lines of work, bringing incremental novelty. \n\nMy main concern relates to the experiments. It seems that ATOC and TarMAC would be the best baselines to compare against for a fair evaluation of the algorithm. Could they be added?\n\nOne question for the authors: at the beginning of Section 3, it is stated that \"it may be costly and less helpful to take all other agents into consideration\". It seems counter intuitive that DGN with several convolutional layers (to have a large receptive field) would be less costly than directly receiving global information? And isn't, in a sense, DGN also making use of global information when it has a large enough receptive field, even if indirectly? In this case, would it also make sense to more thoroughly compare DGN with RFM or other global state algorithms? Can this be clarified?\n\nFinally, readability is somewhat hindered by several small issues:\n- Acronyms used in the paper should really be introduced, at least when they are first used. DGN is never introduced, DGN-R/DGN-M are introduced several paragraphs after being first mentioned and BL needs some guessing.\n- Re-citing the same paper several times when mentioned in different sections is good practice. I found myself going over and over back to the related work section to find references and acronyms.\n\nSome typos:\nPage 1: among all agent -> among all agents\nPage 3: of S -> of size S\nPage 4: weighed -> weighted, concate -> concatenate\nPage 5: respecitvely -> respectively\nPage 6: regularation\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The work proposes a graph convolutional network based approach to multi-agent reinforcement learning. This approach is designed to be able to adaptively capture changing interactions between agents. Initial reviews highlighted several limitations but these were largely addressed by the authors. The resulting paper makes a valuable contribution by proposing a well-motivated approach, and by conducting extensive empirical validation and analysis that result in novel insights. I encourage the authors to take on board any remaining reviewer suggestions as they prepare the camera ready version of the paper.
Decision: Accept (Poster)