Learning Multi-Agent Communication from Graph Modeling Perspective
Authors: Shengchao Hu
Li Shen
Ya Zhang
Dacheng Tao
Venue: ICLR 2024 poster (2024)
Keywords: communication learning
multi-agent reinforcement learning
Primary area: reinforcement learning

Abstract: In numerous artificial intelligence applications, the collaborative efforts of multiple intelligent agents are imperative for the successful attainment of target objectives. To enhance coordination among these agents, a distributed communication framework is often employed. However, information sharing among all agents proves to be resource-intensive, while the adoption of a manually pre-defined communication architecture imposes limitations on inter-agent communication, thereby constraining the potential for collaborative efforts. In this study, we introduce a novel approach wherein we conceptualize the communication architecture among agents as a learnable graph. We formulate this problem as the task of determining the communication graph while enabling the architecture parameters to update normally, thus necessitating a bi-level optimization process. Utilizing continuous relaxation of the graph representation and incorporating attention units, our proposed approach, CommFormer, efficiently optimizes the communication graph and concurrently refines architectural parameters through gradient descent in an end-to-end manner. Extensive experiments on a variety of cooperative tasks substantiate the robustness of our model across diverse cooperative scenarios, where agents are able to develop more coordinated and sophisticated strategies regardless of changes in the number of agents.

Published as a conference paper at ICLR 2024
LEARNING MULTI-AGENT COMMUNICATION FROM GRAPH MODELING PERSPECTIVE
Shengchao Hu 12, Li Shen'; Ya Zhang!? Dacheng Tao
Shanghai Jiao Tong University, 2 Shanghai AI Laboratory
3 JD Explore Academy, 4 Nanyang Technological University (charles hu,, ya_zhang) jt etu.edu.cn;
(mathshenli, tao)
ABSTRACT
In numerous artificial intelligence applications, the collahorative efforts of multi- ple intelligent agents are imperative for the successful attainment of target objec- lives. To enhance coordination among these agents, distributed communication framework is often employed. However, information sharing among all agents proves to be essource-intensive while the adoption of a manually pre-defined communication architecture imposes limitations on inter-agent communication, thereby constraining the potential for collaborative efforts. In this study, we in- troduce novel approach wherein we conceptualize the communication architec- ture among agents as a learnable graph. We formulate this problem as the task of determining the communication graph while enabling the architecture parame- ters to update normally, thus necessitating a bi-level optimization process. Utiliz- ing continuous relaxation of the graph representation and incorporating attention units, our proposed approach, CommFormer, efficiently optimizes the communi- cation graph and concurrently refines architectural parameters through gradient descent in an end-to-end manner. Extensive experiments on a variety of coop- erative tasks substantiate the robustness of our model across diverse cooperative scenarios, where agents are able to develop more coordinated and sophisticated strategies regardless of changes the number of agents.
INTRODUCTION
Multi-agent reinforcement learning (MARL) algorithms play an essential role in solving complex decision-making tasks through the analysis of interaction data between computerized agents and simulated or physical environments. This paradigm finds prevalent application across domains, in- cluding autonomous driving (Zhou al., 2020 Hu al. Yang et al. 2018), and gaming AI systems (Peng et al. scenarios typically explored in these studies, multiple agents engage in iterative interactions within shared environment, continually refining their policies through learning from observations to col- lectively attain common objective. This problem can be conceptually simplified as an instance of independent RL, wherein each agent regards other agents elements of its environment. How- ever, the strategies employed by other agents exhibit dynamic uncertainty and evolve throughout the training process, rendering the environment intrinsically unstable from the viewpoint of each indi- vidual agent. Consequently, effective collaboration among agents becomes a formidable challenge. Additionally, it's important note that policies acquired through independent RL are susceptible to overfitting with respect to the policies of other agents, as evidenced by Lanctot et al. (2017).
2022). order dispatching (Li et al. [019] 2017 Zhou et al., (023). In the MARL
Communication fundamental pillar in addressing this challenge, serving as cornerstone of intelligence by enabling agents to operate cohesively as a collective entity rather than disparate individuals. Its significance becomes especially apparent when tackling complex real-world tasks where individual agents possess limited capabilities and restricted visibility of the environment (La- joie al.) 2021] Yu et al. 20226 Liu et al.) 2021). In this work, we consider MARL scenarios wherein the task at hand is of cooperative nature and agents are situated in partially observable environment, but each is endowed with different observation power. Each agent underpinned by
"Corresponding author: Li Shen

---

Published as a conference paper at ICLR 2024
100
90
success rate (%)
80
70
60
50
40
3m
8m
1c3s52
MMM
2c vs 642g
3s5z
6m
10m vs 11m
9m
27m vs 30m
MMM2
6h vs 8z
3s5z vs 356z
8m
Figure 1: The performance pre-defined communication architectures across various StarCraftII combat games, each with 10 different seeds. The notable variance observed underscores the impor- tance searching for the optimal communication architecture.
deep feed-forward network, augmented with access to a communication channel conveying continu- ous vectors. Considering meadwitth-relater constraints, particularly in instances involving wireless communication channels, a limited subset of agents is permitted to exchange messages during each time step to ensure reliable message transfer (Kim et al., 2019). This necessitates meticulous con- sideration by agents in selecting both the information they convey and the recipient agent.
To facilitate coordinated message exchange, we adopt the centralized training and distributed execu- tion paradigm, popularized in recent works such Foerster et al. (2018); y; Kuba al. (2022); ;; Yu ct al. (2022a), which allows agents access to global information and knowledge of opponents ac- tions during the training phase. There several approaches for learning communication in MARL including CommNet (Sukhbaatar et al., 2016). TarMAC (Das et al.) (019). and ToM2C (Wang et al,, 2021]. However, methods relying information sharing among all agents or relying on manually pre-defined communication architectures can be problematic. When dealing with a large number of agents, distinguishing valuable information for cooperative decision eecisiinnmmaiing from globally shared data becomes problematic. In such cases, communication may provide limited benefit and could potentially hinder cooperative learning (Jiang full-scale communication between all agents can be costly. demanding high bandwidth, incurring delays, and imposing significant computational complexity. Manual pre-defined architectures ex- hibit substantial variance, evident in Figure 1 which underscores the necessity for meticulous architectural design to achieve optimal communication, as randomly designed architectures may in- advertently hinder cooperation and result in poor overall performance. Dynamic adjustments to the communication graph during inference have garnered significant attention in recent research (Jiang & Lu 2018, Kim al. 2019 Wang al. 2021). However, this approach assumes all agents always need to communicate with one of the other agents, necessitating complex scheduling algorithms, which results the waste of bandwidth consumption and falls outside the scope of this article.
2018). Furthermore, in real-world applications,
To address these challenges, we present a novel approach, named CommFormer, designed to fa- cilitate effective and efficient communication among agents in large-scale MARL within partially observable distributed environments. We conceptualize the communication structure among agents as learnable graph and formulate this problem as the task of determining the communication graph while enabling the architecture parameters to update normally, thus necessitating bi-level opti- mization process. contrast to conventional methods that involve searching through discrete set of candidate communication architectures, we relax the search space into continuous domain, en- abling architecture optimization via gradient descent in an end-to-end manner. Diverging from pre- vious approaches that often employ arithmetic weighted means of internal states before message transmission (Peng et al. 2017; Wang et al., 2021), which may compromise communication effec- tiveness, method directly transmits each agent's local observations and actions specific agents based on the learned communication architecture. Subsequently, each agent employs an attention unit dynamically allocate credit to received messages from the graph modeling perspective, which
2

---

Published as a conference paper at ICLR 2024
Comm. Graph
Encoder
Decoder
v(0 ... v(O
v(ot
Edge Emb.
Nede Emi..
Edge Emn.
Nedi Erub.
Choice
Mondhy
Multi-Head Attention
Hesking
Multi-Head Attention
Figure 2: The overview our proposed CommFormer. CommFormer initiates by establishing the communication graph, which subsequently serves both the masking and edge embeddings in the encoder and decoder to ensure that agents can exclusively access messages from communicated agents, Subsequently, the encoder and decoder modules come into play, processing sequence of agents' observations and transforming them into a sequence of optimal actions.
enjoys monotonic performance improvement guarantee (Wen al. 2022). Extensive experiments conducted in a variety cooperative tasks substantiate the robustness of our model across diverse cooperative scenarios. CommFormer consistently outperforms strong baselines and achieves com- parable performance to methods allowing information sharing among all agents, demonstrating its effectiveness regardless of variations in the number of agents.
Our contributions can be summarized as follows:
We conceptualize the communication structure as a graph and introduce an innovative algorithm for learning it through bi-level optimization, which efficiently enables the simultancous optimiza- tion of the communication graph and architectural parameters.
We propose the adoption of the attention unit within the framework of graph modeling to dynam- ically allocate credit to received messages, thereby enjoying monotonic performance improve- ment guarantee while also improving communication efficiency.
Through extensive experiments performs robust baseline methods and achieves performance levels comparable to approaches that permit unrestricted information sharing among all agents.
variety of cooperative tasks, CommFormer consistently out-
2 RELATED WORK
Multi-agent Cooperation. As natural extension of single-agent RL, MARL has garnered consid- erable attention for addressing complex problems within the framework of Markov Games (Yang & Wang 2020). Numerous MARL methodologies have been developed to tackle cooperative tasks in an online setting, where all participating agents collaborate toward a shared reward objective. To address the challenge of non-stationarity in MARL, algorithms typically operate within two overar- ching frameworks: centralized and decentralized learning. Centralized methods (Claus & Boutilier) 1998) involve the direct learning of single policy responsible for generating joint actions for all agents. On the other hand, decentralized learning (Littman] 1994) entails each agent independently optimizing its own reward function. While these methods can handle general- sum games, they may encounter instability issues, even in relatively simple matrix games (Foerster et al. 2017). Central- ized training and decentralized execution (CTDE) algorithms represent middle ground between these two frameworks. One category of CTDE algorithms is value-decomposition (VD) methods, wherein the joint f-function is formulated as a function dependent on the individual agents' local O-functions (Rashid et al. 2020 Son al. 2019 Sunehag et al., 2017). The others (Lowe al.) 2017 Foerster et al.) 20188) employ actor-critic architectures and learn a centralized critic that takes global information into account. In this work, we introduce innovative approach operating under
3

---

Published as a conference paper at ICLR 2024
the CTDE paradigm, with limited communication capabilittis, which achieves comparable superior performance when compared to these established baselines.
Communication Learning. Learning to facilitate communication is viable approach to enhance multi-agent cooperation. DIAL (Focrster et al., 2016) is the pioneer in proposing learnable commu- nication through pack-propagation with deep Q-networks. In this method, each agent generates message at each timestep, which serves as input for other agents in the subsequent timestep. Build- ing upon this work, variety of approaches have emerged in the field of multi-agent communicatinn. Some methods adopt pre-defined communication architectures, e.g. CommNet (Sukhbaatar et al., 2016). BiCNet (Peng al.] 2017). and GA-Coomm (Liu et al., 2020). These techniques establish fixed communication structures to facilitate information exchange among agents, often utilizing GNN models (Niu et al. [202]] [Bettini et al. 2023). In contrast, other approaches such as ATOC (Jiang & Lu. 2018), TarMAC (Das et al., 2019). and ToM2C (Wang et al., (02T) explore dynamic adaptation of communication structures during inference, enabling agents to selectively transmit or receive information. In our research, we align with the former approach, establishing fixed com- munication architecture pre-inference. Each agent transmits its local observation and action as a message to shared channel. Our novel CommFormer approach extends this concept by learning an optimal communication architecture through back proppappaggtiion In contrast to CDC (Pesce & Montana 2023), which dynamically alters the communication graph through diffusion process perspective, and TWG-Q (Liu et al.] (022), which emphasizes temporal weight learning and the application of weighted GCN, CommForme adopts a different approach. It focuses on learning a static graph, aimed at optimizing communication efficiency prior to the inference phase, setting it apart from the traditional methodologies employed by the aforementioned approaches.
METHOD
The goal of our proposed method is to address the multi-agent collaborative communication prob- lem, which enables agents to operate cohesively as a collective entity rather than disparate individ- uals. In this paper, we are specifically interested in learning to construct the communication gruph and learning how to cooperate with received messages in heddwithh-limite way.
3.1 PROBLEM FORMULATION
The MARL problems can be modeled by Markov games (N, O, A.A, R, P. (Lttman 1994). The set of agents is denoted as N {1. . N). The product of the local observation spaces of the agents forms the joint observation space, denoted as O = I O' Similarly, the product of the agents' action spaces constitutes the joint action space, represented as A I A'. The joint reward function, R: O A [-Ruaxx Rmaa], maps the joint observation and action spaces the reward range [-R Rmxx R. The transition probability function, P : O x A x O + R, defines the probability distribution of transitioning from one joint observation and action to another. Lastly, the discount factor, denoted as 7 E [0, 1), plays a crucial role in discounting future rewards.
At time step i N. an agent i E A receives an observation denoted as oj E O', The collection of these individual observations o (o'...... "o',...,""" oa) forms the "joint" observation. Agent i then selects an action at based on its policy x'. It's worth noting that T' represents the policy of the jth agent, which is component of the agents' joint policy denoted л. Apart from its own local observation of, each agent possesses the capability receive observations of from other agents, along with their actions (auto-regressively) af through a communication channel. At the end of each time step, the entire team collectively receives a joint reward denoted as R R(o,, a²) and observes 0z+1, following probability distribution (- or, ).). Over an infinite sequence of such steps, the agents accumulate a discounted cumulative return denoted as R A Di 7 R(o,,
In practical scenarios where agents have the capability to communicate with each other over shared medium, two critical constraints are imposed: bandwidth and contention for medium access (Kim) et al. 2019). The bandwidth constraint implies that there is limited capacity for transmitting bits per unit time, and the contention constraint necessitates the avoidance of collisions among multiple transmissions, which is natural aspect of signal broadcasting in wireless communication. Conse- quently, each agent can only transmit their message to a restricted number of other agents during each time step to ensure reliable message transfer. In this paper, we conceptualize the communica-
4

---

Published as a conference paper at ICLR 2024
tion architecture directed graph, denoted 9 (V,E), where each node 24 V represents an agent, and an edge Ci-+j E & signifies message passing from agent 8s to agent øj. The restriction on communication can be mathematically expressed the sparsity S of the adjaceney matrix of the edge connections at. This sparsity parameter, S, controls the allowed number of connected edges, which is given by S x N2, where N is the number of agents.
3.2 ARCHITECTURE
The overall architecture of our proposed CommFormer is illustrated in Figure
MARL paradigm, we introduce the Communication Transformer or CommFormer, which adopts graph modeling paradigm, inspired by developments in sequence modeling (Hu et al., 2023] Wen et al.) 2022) We apply the Transformer architecture which facilitates the mapping between the input, consisting of agents' observation se- quences (o'..... ......,,,,, and the output, which comprises agents' action sequences (a'....,dd aa)) Con- sidering communication constraints, each agent has limited capacity to communicate with subset of other agents, represented by the sparsity of the adjacency matrix of the edge connections. To identify the optimal communication graph, we treat multiple agents nodes in graph and intro- duce learnable adjacency matrix, represented by the parameter matrix a E TR. NxN. which are optimized during training an end-to-end manner.
Communication Graph. To design a communication-effiie
Encoder. The encoder, whose parameters are denoted by Φ. takes a sequence of observations (ot...., .")) as input and passes them through several computational blocks. Each such block consists of a delation-enhancee perceptron (MLP), as well as residual connections to prevent gradient vanishing and network degra- dation with the increase of depth. In the vanilla multi-head attention, the attention score between the element of and of can be formulated as the dot-proe cot-product between their query vector and key vector:
mechanism (Hu et al. 2023] Cai & Lam 2020) and multi-layer
8ij = [ o²) = o'W,, Weo?
Sij can be regarded as implicit information associated with the edge Cj-vo where agent of queries the information sent from agent of. To identify the most influential edge contributing to the final performance, we augment the implicit attention score with explicit edge information:
Sij g(o', "oo',,orri-jj ((--)
= (o' + WW W +Tz-s),
where r. obtained from an embedding layer that takes the adjacency matrix a as input. We also apply mask to the attention scores using the adjacency matrix to ensure that only information from connected agents is accessible:
Sijs
Cjti =1 1,
81j -00,
(3)
Cj+t = O.
We represent the encoded observations as (o',..., o²), which capture not only the individual agent information but also the higher-level inter-dependencies between agents through communication. To facilitate the learning of expressive representations, during the training phase, we treat the encoder as the critic and introduce an additional projection to estimate the value functions:
Lencoder (i)
())
Σ
R(o,, a.) + +VVa(0 Va (6,²))
(4)
Tn
where Ø is the target network's parameter, which is a separate neural network that a copy of the main value function. The update mechanism for ő is executed either through exponential moving average or via periodic updates a "hard" manner (Mnih et al. 2015).
Decoder. The decoder, characterized by its parameters 0, processes the embedded joint action a 0:m-1 m = 1.... n through a series of decoding blocks. The decoding block also incorporates relation-en enhaoncedeeeecddddddeee mechanism for calculating attention between encoded actions and observation representations, along with an MLP and residual connections. In addition to the adjacency matrix mask, we apply constraint that limits attention computation occur only between agent and its
5

---

Published as a conference paper at ICLR 2024
preceding agents j where j < i. This constraint maintains the sequential update scheme, ensuring that the decoder produces the action sequence an auto-regressive manner: "g" (a" 1:m 1am 1mm-1
which guarantees monotonic performance improvement during training (Wen et al. 2022 We apply the PPO algorithm (Schulman et al. 2017) to train the decoder agent:
T-1
Decoder (0)
Tn Σ
Σ
min (0) (0)
mmm t
(5)
#g (a."" 6 a,
1.m
1 (0) Bau (a?" [ 1:m 1am-11
where Ae is an estimate of the joint advantage function, which can be formulated Vi m= V(,,") Schulman et al. 2015).
3.3 TRAINING AND EXECUTION
We employ the CTDE paradigm: during centralized training, there are no restrictions on communi- cation between agents. However, once the learned policies are executed in decentralized manner, agents can only communicate through a constrained bandwidth channel.
3.3.1 CENTRALIZED TRAINING
During the training stage, need to determine the communication matrix while allowing the architecture parameters á and 9 to update normally. This implies a bi-level optimization problem
Annadaliiggm & Friesz, 1992 Colson al. 2007) with the upper level variable and and
as the lower-level variable:
min
s.t. (a)))) 0" (a) arg min Cerasn (0,0, 0, a),
0.0
aa| S S x N
(8)
where C (oncoder()) DDnnnddr()++Leeedt((((( with different online rollouts for training Lerain and validation Lvals and |ar] denotes the number of connected edges. Evaluating the architecture gradient exactly can be prohibitive due to the expensive inner optimization, and each value in a is represented by discrete value in f0, 1}. We propose a simple approximation scheme that alternately updates the following formula and relaxes a as a continuous matrix to enable differentiable updating:
Φ = Φ <V Ctrain (Ø, 0, a), 0 Ltrain (0,0,00000 a.)..
and
a = a - - Loat 0, a),
(10)
where Φ, denote the current weights maintained by the algorithm, and E, are the learning rate for step of inner and outer optimization. The idea is to approximate o² (a)),, 0 (():) by adapting and 0 using only single training step, without fully solving the imner optimization (Equation 7 by training until convergence.
To update the discrete adjacency matrix a, we utilize the Gumbel-Max trick (Jang et al. 2016 Maddison al. 2016) sample the binary adjacency matrix, which facilitates the continuous rep- resentation of a and enables the normal back propagation of gradients during training. To satisfy constraint we extend the original one-hot Gumbel-Man trick k- k-hot, enabling each agent send messages to fixed number of & S x N agents:
e k hot (k- arg max [Softmax(aa;) + gz)) for ..)... where gj is sampled from 1O,) and e; NN represents the edges connected to agent i.
(11)
3.3.2 DISTRIBUTED EXECUTION
During execution, each agent has access to local observations and actions, as well as additional information transmitted by other agents through communication. The adjacency matrix is derived from the parameters a without any randomness as follows:
e, hot (k- arg max (oij. for b....,n)).
(12)

---

Published as a conference paper at ICLR 2024
Note that each action is generated retresseggrssillyy.. in the sense that a" will be inserted back into the decoder again to generate am*+1 (starting with d and ending with a am-)). Through the use of limited communication. each agent is still able to effectively select actions when compared to fully connected agents, which leads to significant reductions in communication costs and overhead. The overall pseudocode is presented in Algorithm
Algorithm Commerrmer
1: Input: Batch size B, number of agents NN, episodes K, steps per episode T, sparsity S.
2: Initialize: Encoder {ń)) Decoder {0}, Replay buffer B, Adjacency matrix RR"x.
3: for k = 0. 0....... K-
do
4: fort 1. ................................ T
do
5: Collect a sequence of observations of,...,,'?
of from environments.
6: // inference wi th CommF
7:
Generate the matrix E {0,1]axe according to the a with Equation
8:
Generate representation sequence o oi....,0? of via Encoder & with attention score (Equation 2) and mask (Equation 3). similar to the Decoder.
9:
for m 1......... nn do 0r and of.... o,...., at to the Decoder 0 and infer am with the auto-
10:
Input o.-- regressive manner.
11:
end for
12:
Execute joint actions .f....,.. az in environments and collect the reward R(o,, az). Insert (o,, at, R(o,, a.) in to B.
13:
14:
end for
15:
// train the CommFo rmer
16:
Sample a random minibatch B steps from B.
Generate the matrix e E {0, 1 according the with Equation 11 Generate (o) with the output layer of the Encoder & and compute the joint advantage
18:
function Á based on (0) with GAE.
19:
Input Ø² . 6" and a
a a==1 generate Ty..... ".....; To at once with the Decoder A.
20:
Calculate the training loss = ((nonde(()) + Decoder (0) with Equation 4 Iaand Equation (5)
21:
Iteratively update the Φ, 0 and with Equation and Equation 10
22:
end for
EXPERIMENT
To evaluate the properties and performance of our proposed CommFormer we conduct a series of experiments using four environments, including Predator-Pres (PP) (Singh et al.) (018). Predator- Capture-Pres (PCP) (Seraj al., 2022). StarCraftll Multi-Agent Challenge (SMAC) (Samvelyan) al. 2019), and Google Research Foot)all(GRF) (Kurach et al. 2020). A comprehensive descrip- tion each environment can be found in the Appendix is worth noting that in certain domains, objective extends beyond maximizing the average success rate cumulative rewards. We also aim to minimize the average number of steps required to complete an episode, emphasizing the ability to achieve goals in the shortest possible time.
4.1 BASELINES
We compare CommFormer with strong CTDE baselines that do not involve communication, e.g. HAPPO (Yu al. 2022a), MAPPO Yu et al. 2022a) and QMIX (Rashid al.) 2020). as well as popular communication methods, e.g. MAGIC Niu et al. 2021). TarMAC (Das et al. 2019). and QGNN (Kortvelesy & Prorok 2022) highlight its effectiveness. Details for each method are pro- vided in Appendix B During experiments, the implementations of baseline methods are consistent with their official repositories, all hyper-parameters left unchanged the origin perfoommin status. We also include the fully connected CommFormer (FC) configuration, where there are no limitations on communication bandwidth. this configuration, each agent can communicate with all other agents, implying that the sparsity parameter S is set to 1. FC serves as the upper bound of our methods and demonstrates strong performance on cooperative MARL tasks.
Our code is available http://///tgtttoo.ooooooeeeeaaea

---

Published as a conference paper at ICLR 2024
Table 1: Performance evaluations of different metrics and standard deviation on the selected bench- mark, where UPDeT's official codebase supports several Marine-based tasks only. Note that the sparsity parameter S in CommFormer is consistently set to 0.4 for all tasks.
Task
Difficulty
CommFormerO44)
MAPPO
HAPPO
QMIX
UPDsT
Steps
Easy
100.0.o
100.0uu:
100.0xs
100.0.2
96.9.
100.0:0
100.0.a
5e5
Hasy
100,0cn
100.0ooc
96.8cm
9
97.71x
96.3em
100.0..
leh
Fasy
100.0es
100.0
100.0.0
97.5
96.9.9
100.0.
266
MMH
Easy
100.0c.
83.3
95.6uss
81,2
91,2
100.0cm
2:6
Hard
100.0ss
100.0k.1
100.0.2:
90.044
90.34
100.0:.0
Sc6
Hard
100.0..
74.0
72.5rs
90.0ks
84.3,
100.0..0
366
Hard
89.6
$1.3
88.2
73.8.
75.8.
90.6
Hard
100.0..
96.9 96.9pm
93.81%%
92.6x1
100.0
Se6
Hard
100.00.o
100.0ka
96.3
77.5
95.8x3
100,0sn
Sc6
Hard
100,0se
100.037:
0.6a.
2.5
Ste Dit
Hard+
96.9
80.2
93.1os
0.0km
39.2a
100.0so
1c7
seusd
Hard+
100.0...
96.9mm
$1.8us.
0.3
88.30
100.0...
le7
Hard=
96-9k1
48.4
9.7a
100.0
1c7
Hard+
87.5au
79.2mm
84.3um
82.8
68. Sa13
100.0c.
2:7
Task
Difficulty
CommFormer(0.4)
QGNN
SMS
TeMAC
NDQ
MAGIC
QMIX
Steps
Hard+
96.9..s
93,8cn
76.4
39.1
77.1
22.3
$1.1
207
Hard+
100.0cce
92.2
59.9
44,2
48.9
0.0
82.6
167
b
Hard.
96.9km
98.0ka
86.0
78.1
267
Task
Metric
CommFormen((.4)
MAGIC:
HetNer
Comm
13CNet
TarMAC
GA-Comm
Steps
GRF
Success Rate
100,ken
28.2am
70.dem
73.3
Kon
Steps Taken
25.4k4
34,3a2
39.304
40.4az
41.5cm
39.1am
PP
Aug. Cumulative
Steps Taken
4.12Iniee
4.99
0.386mm0
10.6
0.2322
8.30
-0.366
8.97mm
00342
9.69k
18 Am
0.563mse
PCP
Avg. Cunulaaive R
Steps
0.197
7.6lu
-0. 60.394
10.8
-0.36 00.364amm
9.98xus
-0. -0.3940om
11.30
-0.411amm
11.5
-0,548mmmn
17.0uam
4.2
MAIN RESULTS
According to the results presented in Table and Figure 1 our CommFormer with a sparsity param- eter S 0.4 significantly outperforms the state-of theth--rt baselines. It consistently finds the optimal communication architecture across diverse cooperative scenarios, regardless of changes in the num- ber of agents. Take the task 385z as an example, where the algorithm needs to control different types of agents: stalkers and zealots. This requires careful design of the communication architecture based on the capabilities of different units. Otherwise, it can even have a detrimental impact on per- formance, as indicated by the substantial variance displayed in Figure [ The outcome of 3s5z pre- sented in Table [ consistently highlights CommFormer" 's ability to attain optimal performance with different random seeds, which underscores the robustness and efficiency of our proposed method. Furthermore, in comparison to the FC method, CommFormer nearly matches its performance while retaining only 40% of the edges. This indicates that with an appropriate communication architec- ture, many communication channels can be eliminated, thereby significantly reducing the hardware communication equipment requirements and expanding its applicability. Finally, it's worth noting that all the results presented in Table [ are based the same number of training steps, demon- strating the robustness and effectiveness of our bi-level optimization approach, which consistently converges to the optimal solution while maintaining sample efficiency. The pppee--rrameters used in the study and additional detailed results can be found in the Appendix.
4.3 ABLATIONS
We conduct several ablation studies, primarily focusing on the SMAC environments, to examine specific aspects of our CommFormer. The parameter S, which determines the sparsity of the com- munication graph, impacts the number of connected edges. Lower values of S imply reduced costs associated with communication but may also lead to performance degradation. Additionally, we con- duct ablation studies to investigate the essence of architecture searching, where we generate various pre-defined architectures using different random seeds, simulating manually pre-defined settings.
The parameter S introduced in our bi-level optimization controls the number of connected edges, ensuring that it does not exceed S x Nx as specified in Equation g To simplify this constraint, ensure that the total number of edges |o:| equals S x N with each agent communicating with fixed number of S x N agents. Smaller values of S reduce the cost associated with communication but may also result in performance degradation. To investigate the impact of varying S, conduct
Sparsity.
8

---

Published as a conference paper at ICLR 2024
1J.03 Sagae
Dii Www.omeer: 2943
Eity communt stige
3.7
Dic Detoemerr
Performance comparison SMAC tasks with different sparsity 8. Note that the value of sparsity S gradually increases, the performance of Commeormer improves across various environments. This effect is particularly pronounced environments with large number of agents.
Figure 3:
194M
3652
HwV
0.25
0.50
1.09
125
3.50
21.
20
Figure 4: Performance comparison on SMAC tasks with different manually pre-defined communi- cation architectures. CommFormer consistently achieves optimal performance, which underscores its capability to autonomously search for the optimal communication architecture, highlighting its adaptability across various scenarios and tasks.
series of experiments, whose results presented Figure For simpler tasks, such Ic3s5z, achieving 100% win rate is possible even when each agent can only communicate with one other agent. Nevertheless, As task complexity and the number of participating agents increase, a larger value of sparsity S becomes necessary to attain superior performance.
Architecture Searching. In light of the constraints imposed by limited bandwidth and contention for medium access, designing the communication architecture for each agent becomes critical task. To investigate the impact of different communication graph configurations, we conduct ex- periments using various random seeds, simulating different individuals' approaches to the problem. The results, as depicted in Figure [ and 4 highlight that manually pre-defining the communica- tion architecture often leads to significant performance variance, demanding expert knowledge for achieving better results. In contrast, our proposed method leverages the continuous relaxation of the graph representation. This innovative approach allows for the simultaneous optimization of both the communication graph and architectural parameters an end-to-end fashion, all while maintaining sample efficiency. This underscores the essentiality and effectiveness of approach in tackling the challenges of multi-agent communication in constrained environments.
5 CONCLUSION
In this paper, we introduce novel approach called CommFormer, which addresses the challenge of learning multi-agent communication from graph modeling perspective. Our approach treats the communication architecture among agents as a learnable graph and formulates this problem as the task of determining the communication graph while enabling the architecture parameters update normally, thus necessitating a bi-level optimization process. By leveraging continuous relaxation of graph representation and incorporating attention mechanisms within the graph modeling framework, CommFormer enables the concurrent optimization of the communication graph and architectural parameters in an end-to-end manner. Extensive experiments conducted on variety of cooperative tasks illustrate the significant performance advantage of our approach compared to other state-of- the-art baseline methods. In fact, CommFormer approaches the upper bound in scenarios where unrestricted information sharing among all agents permitted. We believe that our work opens up new possibilities for the application communication learning in the field of MARL, where effective communication plays pivotal role in addressing various challenges.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENTS
This paper does not raise any ethics concerns. This study does not involve any human subjects, practices to data set releases, potentially harmful insights, methodologies and applications, poten- tial conflicts of interest and sponsorship, disciiiination/bas/faannsss concerns, privacy and security issues, legal compliance, and research integrity issues.
ACKNOWLEDGMENTS
This work is supported by the National Key R&D Program of China (No. 2022ZD0160702), STCSM (No. 20611106101, No. 225110,,700, No. 21DZI 100100), 111 plan (No. BP0719010) and National Natural Science Foundation of China (No. 62306178).
REFERENCES
Anandalingam and Terry Friesz. Hierarchical optimization: An introduction. Annals of Opera- lions Research, 1992.
Matteo Bettini, Ajay Shankar, and Amanda Prorok. Heterogeneous multi-robot reinforcement learn- ing. arXiv preprint arXiv:2301.0713/ 2023.
Deng Cai and Wai Lam. Graph transformer for graph-to-sequence learning. In AAAI, 2020.
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multia- gent systems, AAAI/AAА,, 1998.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 2007.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. In ICML, 2019.
Jakob Foerster, Ioannis Alexandros Assacl, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. NeurlPS, 2016.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In AAAI, 2018.
Jakob N Foerster, Richard Y Chen, Maruan Al-Shedivar, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leaming awareness. arXiv preprint arXiv: 2017.
Shengchao Hu, Li Chen, Penghao Wu, Hongyang Li, Junehi Yan, and Dacheng Tao. St-p3: End-to- end vision-based autonomous driving via spatial-temporal feature learning. In ECCV, 2022.
Shengehao Hu, Shen, Ya Zhang, and Dacheng Tao. Graph decision transformer. arXiv preprint arXiv:2303.03747, 2023.
Siyi Hu, Fengda Zhu, Xiaojun Chang, and Xiaodan Liang. Updet: Universal multi-agent reinforce- ment learning via policy decoupling with transformers. arXiv preprint arXiv:2101.0800) 2021.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv:1611.01144 2016.
Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent cooperation. NewrlPS, 2018.
Daewoo Kim, Sangwoo Moon. David Hostallero, Wan Ju Kang, Tacyoung Lee, Kyunghwan Son, and Yung Yi. Learning to schedule communication in multi-agent reinforcement learning. arXiv preprint arXiv: 1902 2019.
Ryan Kortvelesy and Amanda Prorok. Qgnn: Value function factorisation with graph neural net- works. arXiv preprint arXiv:2205. 13005, 2022.
10

---

Published as a conference paper at ICLR 2024
Jakub Grudzien Kuba, Ruiqing Chen, Munning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. ICLR, 2022.
Karol Kurach, Anton Raichuk, Piotr Stańczyk, Michal Zajac, Olivier Bachem, Lasse Espeholt, Car- los Riquelme, Damien Vincent, Marcin Michalski, Olivier Bousquet, et al. Google research football: novel reinforcement learning environment. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 4501-4510, 2020.
Pierre Yves Lajoie, Benjamin Ramtoula, Fang Wu, and Giovanni Beltrame. Towards collaborative simultaneous localization and mapping: a survey of the current research landscape. arXiv preprint (:Xiv:2/0800832. 2021.
Mare Lanctot, Vinieius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent rein- forcement learning. NeurIPS, 2017.
Minne Li, Zhiwei Qin, Yan Jiao, Yaodong Yang, Jun Wang, Chenxi Wang, Guobin Wu, and Jieping Ye. Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning, In www, 2019.
Michael Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, Elsevier, 1994.
Bo Liu, Qiang Liu, Peter Stone, Animesh Garg, Yuke Zhu, and Anima Anandkumar. Coach-player multi-agent reinforvement learning for dynamic team composition. In ICML, 2021.
Yong Liu, Weixun Wang, Yujing Hu, Jianye Hao, Xingguo Chen, and Yang Gao. Multi-agent game abstraction via graph attention neural network. In AAAI, 2020.
Yuntao Liu, Yong Dou, Yuan Li, Xinhai Xu, and Donghong Liu. Temporal dynamic weighted graph convolution for multi-agent reinforcement learning. In CogSci. 2022.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- agent actor-critic for mixed cooperative-compettive environments. NeurIPS, 2017.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.0077 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning, nature. 2015.
Yaru Niu, Rohan R Paleja, and Matthew Gombolay. Multi-agent and teaming. In AAMAS, 2021.
communication
Peng Peng. Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang. Haitao Long, and Jun Wang. Multiagent indirettionally-cordinate nets: Emergence human-level coordination learning to play stareraft combat games. arXiv preprint arXiv: 1003, 2017.
Emanuele Pesce and Giovanni Montana. Learning multi-agent coordination through connectivity- driven communication. Machine Learning, 2023.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement learning. JMLR, 2020.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint
2019.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint /506:/550.00433333 2015.

---

Published as a conference paper at ICLR 2024
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
Esmaeil Seraj. Zheyuan Wang, Rohan Paleja, Daniel Martin, Matthew Sklar, Anirudh Patel, and Matthew Gombolay. Learning efficient diverse communication for cooperative heterogeneous teaming. In AAMAS, 2022.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when to communicate at scale in multiagent cooperative and competitive tasks. arXiv preprint arXiv: 2018.
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. In ICML,, 2019.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropaga- tion. NeurIPS, 2016.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint (Tlf::/0060990 2017.
Tonghan Wang. Jianhao Wang. Chongyi Zheng, and Chongjie Zhang. Learning nearly decompos- able value functions via communication minimization. arXiv preprint arXiv:1910.053366, 2019.
Yuanfei Wang, Fangwei Zhong, Jing Xu, and Yizhou Wang. Tom2c: Target-oriented multi-agent communication and cooperation with theory of mind. arXiv preprint arXiv:2111.09189, 2021.
Muning Wen, Jakub Kuba, Runji Lin, Weinan Zhang, Ying Wen, Jun Wang, and Yaodong Yang. Multi-agent reinforcement learning is a sequence modeling problem. NeurIPS, 2022.
Di Xue, Lei Yuan, Zongzhang Zhang, and Yang Yu. Efficient multi-agent communication via shap- ley message value. In IJCAI, 2022.
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theo- retical perspective. arXiv preprint 201i::2011.00588 2020.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. In ICML, 2018.
Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. NeurIPS, 2022a.
Chao Yu, Akash Velu, Fugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games, NeurIPS, 2022b.
Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Mont- gomery Alban, Iman Fadakar, Zheng Chen, al. Smarts: Scalable multi-agent reinforcement learning training school for autonomous driving. arXiv preprint arXiv:2010.0977% 2020.
Ming Zhou, Ziyu Wan, Hanjing Wang, Muning Wen, Runzhe Wu, Ying Wen, Yaodong Yang, Yong Yu, Jun Wang, and Weinan Zhang. Malib: A parallel framework for population aopseed multi-agent reinforcement learning. J. Mach. Learn. Res., 2023.
12

---

Published as a conference paper at ICLR 2024
Appendices
A DETAILED DESCRIPTION OF ENVIRONMENTS.
During the main experiments, compare our method within four environments, including Predator-Prey (PP) (Singh et al. 2018), Predator-Capttur-Prey (PCP) (Seraj et al. 2022), StarCraftII Multi-Agent Challenge (SMAC) (Samvelyan et al. 2019), and Google Research (oO))all(GRF) (Krrch et al. 2020).
PP. The goal is for N predator agents with limited vision to find a stationary prey and move to its location. The agents in this domain all belong the same class (i.e., identical state, observation and action spaces),
PCP. We have two classes of predator and capture agents. Agents of the predator class have the goal of finding the prey with limited vision (similar to agents in PP). Agents of the capture class, have the goal of locating the prey and capturing it with an additional capture-prey eeelurreprryyaae action in their action-space, while not having any observation imputs (e.g., lack of scanning sensors).
SMAC. In these experiments, CommFormer controls group of agents tasked with defeating en- emy units controlled by the built-in AI. The level of combat difficulty can be adjusted by varying the unit types and the number of units on both sides. We measure the winning rate and com- pare it with state-of-the-ar baseline approaches. Notably, the maps /ol0b Ir and 1o2r vs 4r present formidable challenges attributed limited observational scope, while the map St_vs_uul necessitates heightened levels of coordination to attain successful outcomes.
GRF We evaluate algorithms in the football academy scenario 3 vs. 2, where we have 3 attackers vs. I defender, and goalie. The three offending agents are controlled by the MARL algorithm, and the two defending agents are controlled by built-in AI. We find that utilizing 3 vs. 2 scenario challenges the robustness of MARL algorithms to stochasticity and sparse rewards.
B DETAILED BASELINES
We compare our CommFormer with strong baselines without communication, and popular com- munication methods to showcase the effectiveness. During the SMAC environments, the baseline methods are as follows, each of them is based on the CTDE paradigm to ensure fair comparison: (1) MAPPO (Yu et al. 2022a) directly apply PPO in MARL and use one shared set of parameters for all agents, without any communication. (2) HAPPO (Kuba et al. (022)) implement multi-agent trust-region learning by the sequential update scheme with a monotonic improvement guarantee. (3) QMIX (Rashid et al.) 2020) incorporates a centralized value function to facilitate decentralized decision-making and efficient coordination among agents while addressing credit assignment issues. (4) UPDeT (Hu et al. 2 decouples each agent's 's observations into sequence of observation en- tities and uses a Transformer to match different action- oitionnnbservttion.. (5) MAT (Wen et al.] (2022) treats cooperative MARL as sequence modeling and adopts fixed encoder and fully decentral- ized actor for each individual agent.
(6) SMS (Xue et al.] 2022) calculates the Shapley Message Value to explicitly evaluate each message's 's value, learning an efficient communication protocol in more complex scenarios. (7) TarMAC (Das et al., 2019) utilizes an attention mechanism to inte- grate messages according to their relative importance. (8) NDQ (Wang et al.) 2019) aims at learning nearly decomposable Q functions via communication minimization. (9) MAGIC (Niu et al.) 2021) makes use of hard attention construct dynamic communication graph, which then combines with a graph attention neural network to process the messages. (10) QGNN (Kortvelesy & Prorok 2022] introduces a value factorisation method that uses a graph neural network based model.
For other domains, we benchmark our approach against a variety of -tate-of-the-art communication- based MARL baselines: (1) CommNet (Sukhbaatar et al. 2016) uses continuous communication for fully cooperative tasks, where the model consists of multiple agents and the communication be- tween them is learned alongside their policy. (2) 13CNet (Singh et al. 2018) controls continuous communication with gating mechanism and uses individualized rewards for each agent gain better performance and scalability while fixing credit assignment issues. (3) GA-Comm (Liu et al.] 2020) models the relationship between agents by complete graph and proposes novel game ab-
13

---

Published as a conference paper at ICLR 2024
straction mechanism based two-stage attention network. (4) HetNet (Seraj al. 2022) learns ef- ficient and diverse communication models for coordinating cooperative heterogeneous teams based on heterogeneous graph-attention networks.
C HAPER-PARAMETER SETTINGS
During experiments, maintain consistency in the implementations of bascline methods by using their official repositories, and we keep all hyperparameters unchanged from their original best-performing configurations. Specific hyperparameters used for different algorithms and tasks can be found in Tables to 4 To ensure fair comparison and validate that CommFormer achieves optimal performance without compromising sample efficiency, we adopted the same hyperparameter settings as MAT (Wen et al. 2022).
D DETAILS OF EXPERIMENTAL RESULTS
We provide detailed training figures (Figure 6 for various methods to substantiate our claim that our approach facilitates simultaneous optimization of the communication graph and architectural parameters in an end-to-end manner, all while preserving sample efficiency.
E MORE VISUAL RESULTS
We present additional visual results (Figure 5) that showcase the final communication architecture obtained through our search process. These visualizations offer more intuitive understanding the architecture's 's evolution during training. As training progresses, the communication structure adapts to improve performance. Additionally, as we move towards the later stages training, the model's architecture stabilizes, with only minimal changes observed, typically involving 1 or 2 edges.
Searching Process
C
Figure 5: The searching process of CommFormer in the SMAC task 1c3s5z. this representation, a white square corresponds to value of 1, indicating the presence of an edge connection.
F APPLICATION CONSIDERATION
A possible application of this study is create efficient communication framework tailored for enclosed, finite environments, typical of logistics warehouses. In these settings, agent movement limited to designated zones, and communication facilitated through overhead wires, akin trolleybus system.
In contrast, open environments present unique challenges, primarily due the potential vast dis- tances between agents, which require wireless communication and may hinder effective communica- tion. To address this, straightforward approach could be add bidirectional edges between agents when they come within close proximity, enabling communication between them (Seraj et al. 2022). However, more effective solution may involve hybrid approach that considers the constraint on the available bandwidth: initially segmenting agents into groups based on proximity. followed by an internal search for an optimal communication graph within each group. If agent distances vary dynamically during testing, this process is repeated necessary to adjust the communication graph real time, ensuring continuous adaptability to changing environmental conditions.
14

---

Published as a conference paper at ICLR 2024
Table 2: Common hyper--arameters used for our method in the experiments.
hyper-parameters
value
hyper-parameters
value
hyper-parameters
value
critic
5e-4
actor
5e-4
use gae
True
gain
0.01
optim eps
le-5
batch size
3200
training threads
16
num mini-batch
rollout threads
32
entropy coef
0.01
max grad norm
10
episode length
100
optimizer
Adam
hidden layer dim
use huber loss
True
Table 3: Specific hyper-paramette parameters used for our method in the experiments.
hyper-parametent in PP
value
hyper-parameters in PCP
value
hyper-parameters in GRF
value
Number Agents
3
Number Predators
2
Number Agents
3
Number Enemies
Number Captures
eval episode length
200
vision
Number Enemies
eval episode length
20
vision
eval episode length
20
Table 4: Different hyper-parameters used for CommFormer in different tasks.
tasks
ppo epochs
ppo clip
blocks
heads
stacked frames
steps
7
3m
15
0.2
5c5
0.99
8m
15
0.2
le6
0.99
1c3s5z
10
0.2
2e6
0.99
MMM
15
0.2
2e6
0.99
2c 64zg
10
0.05
1
5e6
0.99
3s vs 5z
15
0.05
4
5e6
0.99
3s5z
10
0.05
3e6
0.99
5m 6m
10
0.05
le7
0.99
8m 9m
10
0.05
5e6
0.99
10m vs 11m
0.05
5e6
0.99
25m
0.05
2e6
0.99
27m vs 30m
0.2
le7
0.99
MMM2
0.05
1c7
0.99
6h vs
0.05
1e7
0.99
3s5z vs 3s6z
5
0.05
2e7
0.99
lo10b vs 1r
0.2
2e7
0.99
1o2r vs 4r
5
0.05
1e7
0.99
5z vs Jul
10
0.05
lc7
0.99
PP
10
0.05
1c7
0.99
PCP
10
0.05
1e7
0.99
GRF
10
0.05
1e7
0.99
15

---

Published as a conference paper at ICLR 2024
Gonefore
Goneforer
Goreforw
oonnec thpt 940y
IW wwweorrr
Coreforer
2.39
Gomeforee
Gomefooee
wareent coge
Goneeore
0.2
0.2
107
856 mamieee
Figure 6: Performance comparison SMAC tasks. CommFormer consistently outperforms strong baselines and achieves comparable performance to methods allowing information sharing among all agents, demonstrating its effectiveness regardless of variations in the number of agents.
16


Reviews:
[{"review_id": "jBw0e6Jd8B", "reviewer": "Reviewer_9cgB", "summary": "This paper proposes a method for learning optimal communication graphs in multi-agent systems using attention. Unlike previous methods that use a predefined graph communication structure with unlimited comms bandwidth, CommFormer learns to create directed communication links such that some level of graph sparsity $S$ is maintained. To do this, they formulate a constrained optimization problem to learn a value encoder and action decoder with an upper bound on the norm of the graph adjacency matrix. In reality, they create a bi-level optimization that steps the encoder/decoder optimizers to find approximate optima then update the adjacency matrix. They perform experiments on StarCraftII with various value-based and policy gradient-based baselines and demonstrate that ComFormer can outperform the baselines in SMAC tasks ranging from Easy to Super Hard.", "questions": "1. Can the authors compare their method to QGNN \n2. How is the ordering of agents decided when inputting to the transformer and is there positional encoding?\n3. I understand that graph sparsity if a necessary assumption to manage the bandwidth of any given agent. However, can the authors discuss or demonstrate what would happen if more realistic assumptions on graph communication were made, such as only communicating with agents within some specified communication range?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is an interesting and well written paper. To my knowledge, the learned graph for graph communication using transformers is a novel idea with clear applications to the real world. The architecture is simple/clear and the motivation for the necessity of this solution is motivated very well in Figure 1.\n\n1. The CommFormer method significantly outperforms most of the baselines on most of the tasks (with the exception of some super hard SMAC tasks)\n2. Performs ablative studies to demonstrate the importance of the sparsity claimed in the paper. \n3. Adaptable to various actor-critic methods, not just PPO", "weaknesses": "There are some concerns I have about the problem formulation. It is assumed in many MARL tasks that communication at test time is limited, as per the CTDE paradigm. However, my understanding is that at each time step, the CommFormer can choose to create/destroy communication links between any arbitrary agents as long as a sparsity measure is met. While this is not unreasonable, it is a very large assumption to make while claiming the CTDE paradigm. Further, in seciton 3.2, the authors state that they restrict communication of agent $i$ to only agents $j$ where $j< i$; this assumes that there is some implicit (or explicit) ordering of the agents that we are assuming. Again, I don't think this is unreasonable as many MARL algorithms use one-hot agent id encoding, it imposes additional nuances that are important to the functioning of the algorithm.\n\nFinally, the authors do not compare to a recent graph-based MARL baseline called QGNN[1]\n\n[1] Ryan Kortvelesy and Amanda Prorok.  QGNN: Value Function Factorisation with Graph Neural Networks", "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": "", "extra_scores": {}}, {"review_id": "0DUCmt14FB", "reviewer": "Reviewer_q3Zy", "summary": "- learning to leverage communication in bandwidth-restricted settings with a learnable adjacency matrix\n\n- continuous relaxation of adjacency matrix to enable differentiable updating of the parameters and adjacency matrix with bootstrapping", "questions": "Why do Dynamic adjustments fall outside the scope of the paper? It seems like this is more about considering a simplified problem setting, where the communication graph between training and execution must be similar. Did you run any experiments testing the performance of CommFormer when the nature of the communication graph changes between training and execution?\n\n\"where  ̄φ is the target network’s parameter, which is non-differentiable and updated every few epochs\" what does this mean?\n\nHow does the actual runtime complexity (i.e. walltime or asymptotic) compare between the different methods? S = 0.4 is still quadratic in the number of agents, which can be limiting for large numbers of agents. Rather than having a sparsity proportion, wouldn't it be more relevant to evaluate sparsity as the actual number of non-zero values in the matrix?\n\nDoesn't this method overfit its communication graph to the task? What does a train/test split look like in such a scenario? Do I need to assume with this training method that the communication graph remains the same between training and testing?\n\nWhy does additional environment steps seem to solve the sparsity problem in 25m?\n\nIn figure 6, any intuition as to what kind of tasks lead Commformer to perform similarly to MAT, and under FC? Since MAT allows unrestricted communication between agents, it's weird that FC seems to massively outperform MAT on some tasks.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Solid formalization of the communication graph problem\n\n- novel contribution**\n\n- impressive experimental results on SMAC compared to SOTA methods\n\n- well written paper, a pleasure to read\n\n** Possible related work: Learning multi-agent coordination through connectivity-driven communication, Pesce and Montana, 2022, springer https://link.springer.com/article/10.1007/s10994-022-06286-6", "weaknesses": "- fixed communication network after training. Despite the authors claiming that dynamic adjustments fall outside the scope of the paper, it would be interesting to see performance comparisons.\n\n- task 8m is not in figure 4 (as opposed to what the \"Sparsity\" paragraph would suggest in 4.3 Ablations).\n\n- \"Nevertheless, As task complexity and the number of participating agents increase, a higher\nlevel of sparsity becomes necessary to attain superior performance.\" this is a very confusing way to say that the matrix needs to be *less* sparse.", "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": "", "extra_scores": {}}, {"review_id": "DFePICuLgc", "reviewer": "Reviewer_Ux29", "summary": "The paper introduces CommFormer, a novel approach for optimizing the communication architecture among multiple intelligent agents involved in collaborative tasks. By conceptualizing the architecture as a learnable graph and employing a bi-level optimization process with attention units, CommFormer enables agents to efficiently optimize their communication and adapt more coordinated strategies in a variety of scenarios, as demonstrated in experiments on StarCraft II combat games.\n\nI have several comments and questions that need to be addressed before publication:\n\n- what if the communication graph determined by your approach is not physically feasible, for instance due to environmental constraints such as a far physical distance, etc.? Isn’t a graph communication approach that determines the communication based on physical proximity better in such real-world scenarios? Maybe the best solution is a hybrid approach where environment constraints are considered and baked into the problem for determining the communication graph?\n\n- I find the presented related work section to be weak and relatively old. Many recent SOTA graph-based multi-agent communication learning approaches are never mentioned or discussed, despite their high relevance to the proposed approach. For instance, [1]-[4] below are only a few of such works. Almost all of these works offer a distributed graph-based learned multi-agent communication method that work under POMDPs and are trained under CTDE. There are more of such recent paper. I believe the authors need to perform a more comprehensive search on the recent literature.\n\n[1] Seraj, Esmaeil, et al. \"Learning efficient diverse communication for cooperative heterogeneous teaming.\" Proceedings of the 21st international conference on autonomous agents and multiagent systems. 2022.\n\n[2] Niu, Yaru, Rohan R. Paleja, and Matthew C. Gombolay. \"Multi-Agent Graph-Attention Communication and Teaming.\" AAMAS. 2021.\n\n[3] Bettini, Matteo, Ajay Shankar, and Amanda Prorok. \"Heterogeneous Multi-Robot Reinforcement Learning.\" Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. 2023.\n\n[4] Meneghetti, Douglas De Rizzo, and Reinaldo Augusto da Costa Bianchi. \"Towards heterogeneous multi-agent reinforcement learning with graph neural networks.\" arXiv preprint arXiv:2009.13161 (2020).\n\n- There are many existing recent, SOTA graph-based multi-agent communication learning approaches, see above [1]-[4] (which are not even mentioned in the paper), that could be a competition for the proposed approach. The selected benchmarks do not necessarily specialize in graph-based distributed communication. The proposed learned communication graph approach should be experimented and evaluated against other graph-based methods.\n\n- All the evaluations are performed in SMAC domains. Is this approach specialized and designed for SMAC? If not, and the solution is in fact generalizable, other domains and different problem settings must be considered. Many of such standard domains can be found in the prior work. Although SMAC domains are interesting game scenarios, the point is to have a comparable baseline performance in standard domains that can also solve other multi-agent coordination and collaboration problems, social interactions, etc.\n\n- Related to the point above, if the presented approach does not apply to other multi-agent problems and scenarios, this should be mentioned and discussed as a limitation. Otherwise, only presenting results in one domain does not suffice.\n\n- The second contribution bullet-point mentions the use of attention units for allocating credit to received messages. Doesn’t TarMAC already do that?\n\n- What are the limitations of the approach? The limitations are never discussed.\n\nAt current states I vote weak rejection, since the algorithm seems to be sound and working, however there are some notable weaknesses in literature review and benchmarking (methods and domains) that need to be addressed as much as possible. I’d be happy to increase my score further when authors satisfactorily addressed my comments and questions.", "questions": "See above.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "See above.", "weaknesses": "See above.", "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": "", "extra_scores": {}}, {"review_id": "C9Xis9ffPQ", "reviewer": "Reviewer_WiJp", "summary": "This paper introduces a novel approach called CommFormer, which addresses the challenge of learning multi-agent communication from a graph modeling perspective. The communication architecture among agents is modelled as a learnable graph. The problem is treated as the task of determining the communication graph while enabling the architecture parameters to update normally, thus necessitating a bi-level optimization process. By leveraging continuous relaxation of graph representation and incorporating attention mechanisms within the graph modeling framework, CommFormer enables the concurrent optimization of the communication graph and architectural parameters in an end-to-end manner.", "questions": "1. The paper proposes a communication-based MARL method. In fact the paradigm CTDE is not suited for such method. There are still some communications among agents for the execution of policies. It seems that CTCE is more suited for the proposed method. Some CTCE based MARL methods. for example, graph-based MARL methods, should be considered for the comparison in the experiment. \n\n2. In Table 1, the FC is a little bit confusing. Even there are no constrictions on the communication bandwidth, the win rate is still hard to be 100% as it depends how the opponents perform. Of course, 100% is the maximum value for the win rate, but it is a meaningless upper bound. Further, how the value 93.8 is obtained in FC column as the upper bound?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper introduces a novel approach which models the communication architecture among agents as a learnable graph. The considered problem is formulated as the task of determining the communication graph while enabling the architecture parameters to update normally, thus necessitating a bi-level optimization process.", "weaknesses": "There have been some works which learns multi-agent cooperative behaviors based on learnable graphs. It would be better to illustrate the differences of the paper compared to them. An example is provided below.\n\nLiu, Y., Dou, Y., Li, Y., Xu, X., & Liu, D. (2022). Temporal Dynamic Weighted Graph Convolution for Multi-agent Reinforcement Learning. Proceedings of the Annual Meeting of the Cognitive Science Society.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)