Exponential Topology-enabled Scalable Communication in Multi-agent Reinforcement Learning
Authors: Xinran Li
Xiaolu Wang
Chenjia Bai
Jun Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: multi-agent reinforcement learning
communication
Primary area: reinforcement learning
TL;DR: We introduce ExpoComm, a scalable communication protocol that leverages exponential topologies for efficient information dissemination among many agents in large-scale multi-agent reinforcement learning.

Abstract: In cooperative multi-agent reinforcement learning (MARL), well-designed communication protocols can effectively facilitate consensus among agents, thereby enhancing task performance. Moreover, in large-scale multi-agent systems commonly found in real-world applications, effective communication plays an even more critical role due to the escalated challenge of partial observability compared to smaller-scale setups. In this work, we endeavor to develop a scalable communication protocol for MARL. Unlike previous methods that focus on selecting optimal pairwise communication links—a task that becomes increasingly complex as the number of agents grows—we adopt a global perspective on communication topology design. Specifically, we propose utilizing the exponential topology to enable rapid information dissemination among agents by leveraging its small-diameter and small-size properties. This approach leads to a scalable communication protocol, named ExpoComm. To fully unlock the potential of exponential graphs as communication topologies, we employ memory-based message processors and auxiliary tasks to ground messages, ensuring that they reflect global information and benefit decision-making. Extensive experiments on large-scale cooperative benchmarks, including MAgent and Infrastructure Management Planning, demonstrate the superior performance and robust zero-shot transferability of ExpoComm compared to existing communication strategies. The
code is publicly available at [https://github.com/LXXXXR/ExpoComm](https://github.com/LXXXXR/ExpoComm).

Published as a conference paper at ICLR 2025
EXPONENTIAL
TOPOLOGY-ENABLED SCALABLE COMMUNICATION IN MULTI-AGENT REINFORCEMENT
LEARNING
Xinran Li Xiaolu Wang Chenjia Bai²
Jun Zhang!
'The Hong Kong University of Science and Technology
Institute of Artificial Intelligence (TeleAI), China Telecom
Software Engineering Institute, East China Normal University xinran. li@connect ust hk, xiaoluwang@sei www.:eeeeeeeee.eeeeeeeeeeeeeeeee ecnu. edu. en
baicf@chinatelecom en, eejzhangeust.he
ABSTRACT
In cooperative multi-agent reinforcement learning (MARL), well-designed com- munication protocols effectively facilitate consensus among agents, thereby enhancing task performance. Moreover, in large-scale multi-agent systems commonly found in real-world applications, effective communication plays even more critical role due to the escalated challenge of partial observability compared smaller-scale setups. this work, we endeavor develop a scalable communication protocol for MARL. Unlike previous methods that focus on se- lecting optimal pairwise communication links task that becomes increasingly complex as the number of agents grows-we adopt a global perspective on com- munication topology design. Specifically, we propose utilizing the exponential topology to enable rapid information dissemination among agents by leveraging small-diameter and small-size properties. This approach leads communication protocol, named ExpoComm. To fully unlock the potential of exponential graphs as communication topologies, we employ memory-based mes- sage processors and auxiliary tasks to ground messages, ensuring that they reflect global information and benefit decision- maaiin.. Extensive experiments on large- scale cooperative benchmarks, including MAgent and Infrastructure Management Planning, demonstrate the superior performance and robust zero-shot transfer- ability ExpoComm compared existing communication strategies. The code is publicly available at pettps://githan com/ LXXXXR/ ExpoComm
scalable
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) has recently emerged promising ap- proach for complex decision-makin making tasks across diverse real-world applications, such as resource allocation (Ying & Dayong 2005). package delivery (Seuken & Zilberstein (007). autonomous driving (Zhou et al., 2001)) robot control (Swamy et al. 2020). and infrastructure management plan- ning (Leroy al. 2004). Under the widely adopted centralized training and decentralized execution (CTDE) paradigm (Kraemer & Banerjee 2016 Lyu et al. (022), algorithms like MADDPG (Lowe et al. 2017), COMA (Foerster et al. 2018). MATD3 (Ackermann et al. 2019), QMIX (Rashid al.
2020 and MAPPO (Yu et al.) 2022 have achieved notable success.
To enhance agent collaboration in partially observable scenarios, communication mechanisms have been incorporated into multi-agent systems (MASs) to assist in decentralized decision- making (Sukhbaatar et al.) 2016). Enabling information exchange during execution helps MARL algorithms to address non-stationarity and partial observability prevalent in these environments. Building upon this foundation. researchers have devoted efforts to designing effective communi- cation protocols, focusing on three core considerations: 1) whom the agents should communicate with (Ding et al. 2020, Hu et al.) 2024); 2) when communication should occur (Hu et al. 2021] Kim al. 2019) and 3) how the agents should design and utilize the communication messages
"Corresoonding author.

---

Published as a conference paper at ICLR 2025
effectively (Das et al. 2019: Guan et al., 2022 By leveraging tools such attention and graph
neural networks (GNNs), leamable and adaptive communication mechanisms have significantly advanced MARL performance.
Despite considerable success, most existing communication strategies are designed for small scale MASS (Lowe et al., 2017, Samvelyan et al. scale to dozens or even hundreds of agents, which are ubiquitous in real-world applications (Cui)
2019 Peng et al. (021) and may struggle as systems
al. 2022 Schmidt et al. 2022 Yang et al. 2023 Ma et al. 2024). In these many-agent systems, existing methods that learn pairwise connectivity among agents falter for two reasons: First, these methods often require agents receive messages only from "useful" peers. However, identifying these peers becomes increasingly challenging as the number of agents grows, potentially compro- mising the effectiveness of communication protocols (Guan et al.] 2022). Second, the overhead of these methods scales poorly. Specifically, training memory consumption quickly becomes pro- hibitively large, as shown in our empirical evaluation, and the communication overhead during exe- cution scales quadratically with the number of agents, which is infeasible for many-agent systems.
This motivates a fundamental rethinking of scalable MARL communication: Can we adopt a global perspective and design overall topology that propagates information among all agents effectively and at low cost, rather than relying on finding task-specific pairwise connectivity? In this vein, we propose an exponential cppology-enablle communication protocol, termed ExpoComm,, as a scalable solution for MARI. communication. Unlike previous works that seek to identify useful communication links at each timestep, ExpoComm draws inspiration from graph theory and leverages the small-diameter property of exponential topologies to ensure effective commu- nication by facilitating message flow across all agents within limited number of timesteps. The inherent sparsity (small size) of exponential topologies allows ExpoComm's 's communication cost to scale mnear))linearly with the number of agents. Moreover, fully leverage the small-size and small-diameter properties of exponential graphs for efficient information dissemination, we employ memory-based blocks for message processing and auxiliary tasks to ground messages, ensuring that they effectively reflect global information. Extensive experiments across twelve scenarios on large-scale benchmarks, including MAgent (Zheng et al., 2018) and Infrastructure Management Planning (IMP) (Leroy et al., 2024), demonstrate the superior performance of ExpoComm com- pared to baseline algorithms when handling large numbers of agents up to hundred. Additionally, owing its global perspective without pairwise reliance, ExpoComm exhibits remarkable zero-shot transferability to larger numbers of agents during test time.
RELATED WORK
Communication MASS Communication among agents in MARL was first introduced by Sukhbaatar et al. (2016): Foersterrr et al. (2016) and has since become an active research area due to its potential to enhance cooperation and improve task performance. The flexibility of communication protocols makes finding effective solutions for the MARL paradigm challenging (Zhu et al.) 2024). To address this difficulty, many studies have focused on optimizing communication components, such message generators, message aggregators, and connectivity among agents, through end-to- end training (Peng et al., 2017). From the sender side, ToM2C (Wang et al. 2022) and MAIC (Yuan 2022) enhance message generation through teammate modeling. while CACL (Lo et al. 2024) uses contrastive learning techniques to learn communication encoding in a decentralized training paradigm. From the receiver side, TarMAC (Das et al., 2019). G2ANet (Liu et al.) 2020). and MASIA (Guan et al. 2022) improve message aggregation using attention- based strategies.
Recently, researchers have addressed challenges posed by real-world communication systems. No- tably, NDQ (Wang et al., (020b) and TMC (Zhang et al. 2020) reduce communication costs by crafting succinct messages, while ATOC (Jiang & L.u] [2018]. IC3 (Singh et al., 2019), 12C (Ding et al. 2020). and CommFormer (Hu et al. (024) manage overhead by pruning unnecessary commu- nication links. Additionally, Freed et al. (2020) propose a stochastic encoding/decoding scheme to handle noisy channels, and DACOM (Yuan et al. 2023) introduces delay-aware communication to account for the high latency of wireless channels.
Despite these advancements, scalability in communication mechanisms has been largely overlooked, often due to the guadratically increasing communication cost associated with fully cully-connected graphs as the number of agents grows. Although few works explicitly address the scalability issue, efforts to
2

---

Published as a conference paper at ICLR 2025
design communication topologies among agents offer potential solutions. These can be categorized into colneccon,ec,ed, rule-based, and learned topologies. Early works (Sukhbaatar et al. 2016
Foerster et al.] 2016 Peng et al. 2017) typically adopt fully-connected topologies to demonstrate communication benefits, but at the cost of high bandwidth requirements. Later on, to reduce the
overall communication overhead, Jiang al. (2020) and Weil et al. (2024) restrict communication to nearby neighbors based on distance, while NeurComm (Chu et al., (2020) limits communication neighboring agents in networked MASs. In spite of achieving significant performance gains, their further applicability may be limited since they require extra information beyond local observation to determine the communication topology. In contrast, learned topology methods assume no such requirements and offer high flexibility. In particular, ATOC [Jiang & Lu 2018). IC3 (Singh et al.) 2019), 12C (Ding et al. 2020) locally deploy gates for agents decide they should engage in communication. However, these methods may result in uncontrollable overall communication costs due to individual control schemes. Alternatively, MAGIC (Niu et al. 2021) utilizes graph attention mechanisms to Iearn the communication topology, while CommFormer (Hu et al. (024) extends the idea and enables control over the overall communication sparsity. Although effective in small-scall MASs, peer-wise connectivity becomes increasingly difficult learn in large-scale MASs, and high sparsity may impair performance, as discussed by Hu et al. (2024).
Our proposed ExpoComm, which incorporates rule-based topologies for rapid information dis- semination among all agents, complements existing efforts in MAS communication by explicitly addressing scalability challenges.
Exponential Graphs Exponential graphs are class of graph topologies that exhibit strong scal-
ability properties with respect to the number of nodes. They have been primarily used in distributed learning to periodically synchronize model updates across devices. Assran et al. (2019) investigate exponential graphs with gossip algorithms and achieve high consensus rates for decentralized
learning. Follow-up works (Wang al.) 2020a; Ying et al. 2021 Kong et al.) 2021 Yuan et al.,
2021) build upon this topology, optimizing model weight update algorithms and providing empirical evidence and theoretical guarantees for the effectiveness of exponential graphs. Beyond distributed learning, exponential graphs also have applications in chip design (Wang et al. [201]] (0166) Overall, exponential graphs demonstrate efficient information dissemination across many nodes, making them a promising candidate topology for achieving scalable communication in MARL.
SCALABLE COMMUNICATION WITH EXPONENTIAL GRAPH IN MARL
In this section, we propose ExpoComm, which leverages exponential graphs as communication topologies among agents in MARL to enable scalable communication. We structure the following subsections to address three key questions: 1) Why and how should exponential graphs be adapted for agent communication? 2) How can the corresponding neural network architecture be designed to effectively utilize the messages transmitted through these topologies? 3) How can messages propagated among agents be grounded to ensure their usefulness?
we outline the requirements for scalable communication: effective information dis- semination among agents and low communication overhead. We translate these requirements into the challenge of identifying topologies with small diameters and sizes, key properties of exponential topologies. In Section 3.2 we discuss how memory-based message processors ingful message encoding, leveraging the small-diameter property over multiple timesteps within exponential topologies. In Section [.3] we adopt a global perspective ground messages using global state reconstruction auxiliary task and contrastive learning, as ExpoComm aims to facilitate message flow across the entire graph rather than focusing local features.
In Section 3.T
enable mean-
3.1 EXPONENTIAL GRAPH AS THE COMMUNICATION TOPOLOGY
3.1.1 PROBLEM SETTING
In this work, we consider a fully cooperative partially observable multi-agen task, which can be modeled decentralized partially observable Markov decision process (Dec-POMDP) (Olichoek] & Amato 2016). The Dec- POMDP is defined by a tuple M = (S, A, P. R. S2 O, N. with N being the number of agents and 7 E (0, being the discount factor. At each timestep 1, with the
3

---

global observation s¹ E S, agent i receives local observation of Ω and then communicates with other agents. Upon receiving the messages from other agents, agent then selects an action of E A based on its local policy T,. These individual actions collectively form a joint action a' AN leading to a transition to the next global observation 8 g P(s a') and inducing global Published as a conference paper at ICLR 2025
3k
3k
3k
2
2
(a) Static exponential graph.
(b) One-peer exponential graph. & is integer.
Figure I: Illustraiion of exponential graphs with N = 8.
reward y² R(s',a²). The team objective is to learn the policies that maximize the expected discounted cumulative return G2 E, 2'r
3.1.2 COMMUNICATION TOPOLOGIES
To design effective and scalable communication protocol in many-agent systems, it is essential to determine whom to communicate with, i.e., to construct the communication topology so that communication is both beneficial for decision-making and cost-effective. While previous work (Hu) et al. 2024) assumes static communication topology, we adopt more flexible, time-varying di- rected graph G (V, E where node vi V denotes agent and edge eiا E indicates communication link from agent to agent at timestep t.
From a graph perspective, we consider the following desiderata for the communication topology:
Small graph diameter for fast information dissemination: Formally defined as diameter(G") maxe,,,,ev d(u;, Uz) with d(e;, ey) representing the shortest path distance from v; to Vj. the graph diameter indicates how quickly messages travel through the graph. Since communication aids multi-agen agent decision-make making by providing the locally observant agents with global information and alleviating the non sen-stttionartt. a graph with a small diameter can expe- dite message exchange and is therefore desirable.
Small size for low communication overhead: Formally defined as |E the size of graph denotes the total number of edges, corresponding to the number of communication links in an MAS. We assume that any message transmission incurs the same overhead, therefore the total overhead scales with the number of links. Given the high hardware requirement for communica- tion modules and the potential delays induced by densely connected communication topologies, we prefer graphs with small size in many- settings.
3.1.3 EXPONENTIAL GRAPHS
Based on the desiderata above for the communication topologies, we draw inspiration from graph literature and choose exponential graphs (Assran et al. 2019 Ying al., (021) as promising candidate for communication topology in many- -agett systems. Below, we introduce two variants of exponential graphs and demonstrate their small-diameter and small-size properties through an illustrative example.
Static Exponential Graph Assuming a randomly sequential ordering of agents 0, , NxN, x.N in the static exponential graph, each agent communicates with peers that are 20, 21 ......? logg (N-1)) hops away, which illustrated by Figure Ta Formally, we have
and the corresponding adjacency matrix E [
E [1
if log ((i i) mod N) is integer or = otherwise
{
4

---

Published as a conference paper at ICLR 2025
t=0
8
t=
(a) Distance-based graph with [E"
N log, N.
(b) Distance-based graph with |88 = N.
t=
(c) Erdös Rényi graph with |8 = N log, N.
(d) Erdös Rényi graph with [8 = N.
8
t=
(e) Static exponential graph with [E*| N logg N.
(l) One-peer exponential graph with |E N.
Figure 2: A toy example to illustrate the message dissemination with different graph topologies. We demonstrate how the messages, represented by red dots, travel from random agent to other agents over time, following different graph structures. In distance-based graphs (Jiang et al.] 2020). agents connected to top-K nearest neighbors. In Erdös-Rényi random graphs (Erdos al., 1960), the adjacency matrices are sampled uniformly from all the graphs satisfying the diameter and size conditions. In exponential graphs, the adjacency matrices follow Equations and (2).
One-peer Exponential Graph In the one-peer exponential graph, each agent iterates through dif- ferent peers that are 2 ...,.., 2 llgg (N [N-1]] hops away, which is illustrated by Figure lb Formally, we have
E fane peer)
if log2 ())-i) mod N) = mod [log2 (N 1) otherwise
Properties Using the adjacency matrices defined above, verify that the graph diameter for both static and one-peer exponential graphs is floge (N - 1)] (see Appendix [or details). As discussed in Section 3.1.2 small diameter facilitates efficient information dissemination, especially when the number of agents N' is large.
Regarding communication costs, static exponential graphs have size of N [log, (N 1)J, while one-peer exponential graphs have size of N. Notably, the size of one-peer exponential graphs scales linearly with the number of agents, meaning the overall communication overhead also scales linearly.
To illustrate these properties, we provide a toy example Figure We visualize the message dissemination abilities of different communication topologies under varying communication bud- gets. In this example, with N 256 agents, graph sizes (communication budgets) |E*] are set to N l N and N, respectively. In Figure 2 we observe that for each communication topology, re- ducing the graph sizes (as shown in Figures 2d and 2f) typically slows down dissemination speed due to increased graph diameters. This illustrates trade-off between graph diameter and size, flecting the trade-off between communication performance and overhead in many-agent systems. Sparser graphs with smaller sizes result in slower message dissemination but lighter communication overhead. However, exponential topologies strike a balance in this trade-off, demonstrating strong information diffusion even with minimal communication budget of N.
Based on these observations, we conclude that exponential topologies are well-suited for many-agent communication because: In exponential topologies, any agents exchange messages in
5

---

Published as a conference paper at ICLR 2025
One-peer
Agent j
Agent N
A
History
[m]]
FC
RNN
of
Msg
Static
m
MLP
h
m
[ms]
Agent
Auxx
FC
Attention
Agent
m
Agent NV
Figure 3: Neural network architecture for ExpoComm. For the static exponential topologies, atten- tion blocks used for message aggregation. For the one-peer exponential topologies, RNN blocks are used for message aggregation.
most [log2 (N 1)] timesteps, ensuring timely information exchange decentralized decision- making problems. 2) The communication overhead scales nearly linearly with the number of agents, which is crucial for many-agent systems. 3) With a rule-based topology, exponential graphs are easy to deploy and adapt to systems with varying numbers of agents, empirically verified in Section 4.2
3.2 NEURAL NETWORK ARCHITECTURE DESIGN
With exponential graphs serving as the communication topology in ExpoComm, we we elaborate on the neural network architecture help agents utilize received messages for better decision-making. The overall architecture is illustrated in Figure ExpoComm based on the concept of facilitating message flow across all agents within certain timeframe, where the graph diameter indicates the length of such timeframe. To capitalize on the small graph diameter of exponential graphs, the message-procee processing module at each agent should ideally preserve all information received within diameter((" (g)) timesteps. However, preserving all messages across multiple timesteps is not memory- efficient, so we employ sequential neural networks, such as attention blocks and recurrent neural networks (RNNs), for message processing.
3.3 TRAINING AND EXECUTION DETAILS
Following the QMI Rashid et al. 2020) algorithm, we update the network parameters 0 with the objective of minimizing the temporal difference (TD) error loss:
(0) Es of sftt ,'+1)= [1 Qroe(s' "o'ss,'',,n o''
a'; 0))
(3)
where yot = r + y maxa Qt o+11 a: ))) and 0 represents the parameters of the target network as in DQN.
However, communication inevitably enlarges the policy space, making more challenging to find the optimal policy relying solely the MARL training objective (Li & Zhang 2024). To facili- tate learning meaningful messages, we introduce auxiliary tasks to restore global information from local messages. From message perspective, we aim for it traverse among agents over multiple timesteps, accumulating new information along the way, and ultimately reflecting global information useful for decision-making.
Message grounding with the global state In scenarios where the global state is available during training, the auxiliary loss is given by the prediction error of the current global state:
C (0, , Φ) Bss of [s f(m;; 0)
where the learnalle auxiliary network for prediction f(: is used to ground the messages and can be discarded after training.

---

Published as a conference paper at ICLR 2025
Algorithm Training and Execution Procedure of ExpoComm
1: Init: Network parameters 0, D 0, step 0
2: while step muu do
3: 0. Reset the environment.
4: for t q
limit do Decentralized execution at agent
5:
6:
Update local history !g based on current observation of and previous history hi-1
7:
Update agent i's message m based on previous local message mi f-1 and previously re- ceived messages [m²) f-1
8:
// Communication
9:
Send message m. to peers {j E =1
{o Equations and
10:
// Action, which can happen concurrently with communication Sample action af based on current history h and current message m env.step(a')
11:
Interact with the environment (s o'+1
13:
Save the experience D= DU (s o', a'
o
end for
15:
At some interval, update network parameters 0, Φ and 0
{D Equation
end while
17:
Output: Policy networks parameters 0
Message grounding without the global state Alternatively, when the global state is unavailable during training, 2024). Specifically, we treat messages from different agents at the same timestep as positive pairs and messages with intervals larger than diameter((")) as negative pairs, encouraging local messages m, to reflect the current global latent state. The corresponding auxiliary loss is given as the InfoNCE loss (Oord et 2018):
contrastive learning for meaningful message encoding, similar to Lo et al.
exp (g(m!) g(m))/T)
CA (0) = -ii
log Σ ΣmEm exp (g(m²) g(m)/TT)
(5)
where is uniformly sampled from {O...., is uniformly sampled from ,O,...,N j + i). M = {m] k (O....,,N] N), & [1- (I-dimmtter("", + diameter(G*)))
with [M| = M+1
and m is uniformly sampled from M. g(-) is the normalization function, M the hyperparameter indicating the number of negative pairs and is the temperature hyperparameter. The overall training loss is:
( = (T) + a- _A Φ),
where the hyperparameter and (- (-) is the auxiliary loss defined by Equation (4) or Equa- tion (5), depending on whether global information is available during training. The training and execution procedures are summarized in Algorithm
EXPERIMENTAL RESULTS
In this section, we evaluate ExpoComm on two large-scale multi-agent benchmarks: MA- gent (Zheng et al., 2018) and Infrastructure Management Planning (IMP) (Leroy al., 2024). All experiments are averaged over five random seeds and the shaded areas represent the 95% confi- dence interval. Details on network architecture and the training hyperparameters are available in Appendix B.T
4.1 EXPERIMENTAL SETUPS
Environment descriptions In this section, We test ExpoComm and baselines across twelve scenarios in two large-scale benchmarks, with the number of agents ranging from 20 to 100. Specifically, MAgent a particle-based gridworld environment representative of the typical MARL gaming benchmarks. To expand the variety of tasks, also include the IMP benchmark, with tasks oriented from world applications. More details regarding the environment settings are provided in Appendix B.2
7

---

Published as a conference paper at ICLR 2025
ExpoComm
CommFormer
ER
DGN+TurMAC
IDQN
Evaluation Roturn
Evaluation Rotum
Evaluation Retum
75
75
75
50
50
50
25
0
0
2
Timesteps
le6
Timesteps
1e6
Timesteps
166
(a) AdversarialPursuit w/ agents (b) AdversarialPursui w/ agents (c) AdversarialPursuit 61 agents
1.0
Evaluation Win Rate
Evalaatio Win Rate
0.8
0.8
0.8
Evaluation Win
0.6
0.6
0.6
0.4
0.4
0.2
0.0
0.0
0.0
0
2
3
Timesteps
lef
Timesteps
le6
Timesteps
leb
(d) Battle w/ agents
(e) Battle 42 agents
(I) Battle w/ agents
Figure 4: Performance comparison with baselines MAgent tasks. Solid lines represent commu- nication budgets of = while dashed lines represent budgets of = [log2 N1. Runs requiring more than 40 GB of GPU memory excluded due to extreme training costs compared to other methods.
Communication Budgets Denoting the number of agents each agent communicates to by K, for each baseline in each scenario, we test two communication budgets: K = [log2 N1 and 1, where N is the number of agents in the systems.
Baselines In the following. we compare our proposed ExpoComm with four baselines: () IDQN/OMIX (Rashid al. 2020): Base algorithms without communication; (ii) DGN+TarMAC (Jiang et al., 20200; gies in which agents communicate with their nearest neighbors and TarMAC structure to aggregate messages; (iii) ER: ExpoComm with the exponential graph topologies replaced by random graph communication topologies following the Erdös-Rényi et al., 2024): Learned communication topologies using GNN. For ExpoComm, we use the static exponential graph variant for K = [log, N and the one-peer exponential graph variant for K 1. For DGN+TarMAC, agents communicate to top-K nearest neighbors. For ER, communication graphs are sampled uniformally from all the K K-in-regular directed graphs. CommFormer uses con- straints with varying sparsity levels for different communication budgets. Official implementations of these baselines are utilized wherever available; otherwise, we closely follow the descriptions from their respective papers, integrating them into the base algorithms. More implementation details can be found in Appendix B.3
Das et al., 2019) Position-based communication topolo-
Rényi model; (iv) CommFormer (Hu)
4.2 RESULTS
Benchmark results We present the comparative performance ExpoComm and baselines in MAgent and IMP enviromments with Figure 4 and Table [ respectively. Overall, ExpoComm demonstrates superior performance these large-scale benchmarks under both communication bud- gets, underscoring the scalability and robustness of ExpoComm strategies. Notably, the one-peer version of ExpoComm achieves the best performance in most scenarios, despite communication costs that only grow linearly with the number of agents. This makes it the most suitable method for handling large-scale MARL communication problems under very low communication budgets. Additional visualization results to illustrate the learned policies provided in Appendix C.1
Zero-shot transfer Similar to the experimental settings suggested by Wang et al. 2022), we test the zero-shot transfer ability of proposed ExpoComm and the baseline methods, reporting the
8

---

Published as a conference paper at ICLR 2025
Table 1: Performance comparison with baselines on IMP tasks. Results are reported the mean and standard deviation of the percentage of normalized discounted rewards relative to expert-based heuristic policies, following Leroy al. (2024), with details Appendix B.2 The best-performing
method is indicated in bold, and the second best is underlined.
QMIX
ER
ExpoComm
Scenario
K = 0
K 1
K = 1log2 N]
K =
K = flog2 N7
N 50
Uncorrelated Correlated
26.42 (3.43)
24.91 (3.77)
26.62 (2.03)
27.31 (2.26)
28.26 (2.51)
24.81 (4.16)
(9.72)
34.76 (G.07)
43.82 (6.33)
40.01 (3.19)
OWF
62.45 (3.46)
62.99 (3.02)
61.70
64.66 (0.26)
65. 19 (0.51)
N 100
Uncorrelated
12.86 (6.88)
21.94
18.36 (12.92)
27.34 (13.32)
27.81 (5.71)
Correlated
40.20 (96.35)
65. 155.1400 (65.08)
9.84 (32.27)
19.17 (23.94)
17.25 (22.70)
OWF
65.55 (0.53)
66. 70 (0.50)
65.92 (0.87)
65.26 (1.34)
66.23 (0.38)
DGN+TarMAC is not suitable for this benchmark because requires the physical positions of agents, which are not available in this environment.
Methods that require more than 40 GB GPU memory are excluded from comparison due to the extreme training cost compared to other methads.
Win Count
IDQN
DGN TTrMAC
ER ExpuComm
20 20
20 42
20 81
121
Win Count
121
Figure 5: Zero-shot transfer results on Battle scenario. The subtitle "X to Y" indicates that methods are trained with X agents and tested with Y agents. Filled bars represent communication budgets of K= [log, N), while hatched bars represent budgets of K = 1. Baseline CommFormer not excluded in this experiment because learns a fixed peer-to-peed communication topology among agents in specific scenario and it is non-trivial to transfer such topology to scenarios with
different numbers agents.
results in Figure Specifically, we train the agent policies and their corresponding communication policies in scenarios with smaller numbers of agents and directly test these policies against each other larger agent scenarios the competitive task Battle. We test each pair of methods over 200 games, record the method with more wins as the winner, and summarize the results in Figure 5 We observe that both ER and ExpoComm demonstrate good transfer ability compared to other baselines, with ExpoComm performing better under smaller communication budgets. The superior transfer ability of ER and ExpoComm may be attributed to the grounding of messages, which reflects global information.
Ablation studies We conduct ablation studies to assess the impact various design elements in ExpoComm, with results presented in Figure 6 In particular, we compare ExpoComm with two ablations: (i) ExpoComm w/o mem, in which the message generators are not memory-based as described in Section 3.2 (ii) ExpoComm w/o aux, which lacks the auxiliary loss term described in Section From the results, we see that removing the memory blocks from the message generators hinders effective message generation, especially in scenarios with strong time correlation such as

---

Published as a conference paper at ICLR 2025
ExpoComm
ExpoComm w/o mem
ExpoComm w/o aux
100
-400
-150
Evaluation Retum
Evaluation Retum
-40
Evaluation Return
200
-500
250
25
-55
-600
0.0
0.5
1,0
1.5
2.0
0.0
0.5
1.0 Timestops
1.5
2.0
Timesteps
Timestops
(a) AdversarialPursui w/ 25 agents
(b) OWF w/ 50 agents
(c) Uncorrelated w/ 50 agents
Figure Ablation studies on MAgent and IMP benchmarks.
Adversarial Puriall t. Auxiliary tasks primarily aid in grounding the messages, without which the messages could lack guidance and even be detrimental to
Discussion As discussed in Section 2 existing methods suitable for large-scale multi-agent com- munication fall into Iwo categories: position-based methods (e.g.. DGN+TarMAC) and GNN-based methods (e.g., CommFormer). We propose third category based on specific graph structures. In this category, ExpoComm utilizes exponential topologies, and we construct the baseline ER using random graphs. Based on our analysis and experiments, the advantages of ExpoComm are follows:
Superior task performance: Due to the small diameter of exponential graphs and memory- based message generators, ExpoComm facilitates fast message dissemination among all agents. It efficiently collects and carries local information from all agents, aiding decentralized decision- making. This advantage is supported by experiments shown in Figure 4 and Table [
Low communication costs: The compact size of exponential graphs ensures that ExpoComm's communication costs scale (near- Minnarlyy with the number of agents N, crucial for managing communication costs multi-agent systems. Unlike position- based methods or ER, which can only control the number of in-edges or out-edges without global scheduling, ExpoComm natu- rally balances communication overhead across agents.
Versatile adaptability: ExpoComm shows strong transferability across different numbers of agents, seen in Figure This is due to its global message dissemination strategies, which focus on overall communication rather than pairwise relationships, allowing it to adapt to more agents. Additionally, ExpoComm handles wide range of tasks, regardless of the task nature or agent count. Unlike position-based methods, which may struggle with non-gridworld tasks like IMP due to assumptions about knowledge of agent locations. ExpoComm makes no such as- sumptions. Moreover, while learning effective pairwise communication topologies using GNNs can lead to significant GPU memory consumption, ExpoComm bypasses these challenges. does not rely on the expensive task of learning a scenario- communication topology guided by the MARL task itself but instead uses well-designed rule-based topology based on the communication desiderata analyzed in Section 3.1.2
5 CONCLUSIONS
In this work, we explored scalable communication strategies in MARL and introduced ExpoComm, an exponential topology-enabled communication protocol. We proposed a framework with communication topologies featuring small diameters for fast information dissemination and small graph sizes for low communication overhead. This framework is complemented by memory-based message processors and message grounding through auxiliary objectives to achieve effective global information representation. Despite requiring only (near-)linear communication costs relative to the number of agents, ExpoComm demonstrated superior performance and strong transferability on large-scale benchmarks like MAgent and IMP. This study highlights the potential for enhancing the scalability of MARL communication strategies through the explicit design of communication topologies.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
Method and implementation details are provided in Section Appendix [B.1| and Appendix [B.3]
Experiment settings and details are described in Section 4.1 and Appendix B.2 Information about
the experimental infrastructure is available in Appendix B.4 The code is publicly available at
https://github com/LXxxxx3//xpCCommm
ACKNOWLEDGMENT
This work was supported by the Hong Kong Research Grants Council under the NSFC/RGC Collaborative Research Scheme grant CRS_ HRS_HHUST003/22 and the Shanghai Sailing Program 24YF2710200. We thank the anonymous reviewers for their valuable feedback and suggestions.
REFERENCES
Johannes Ackermann, Volker Gabler, Takayuki Osa, and Masashi Sugiyama. estimation bias in multi-agent domains using double centralized critics.
Reducing over- arXiv preprint
arXiv:1910.01665 2019.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In Proceedings of the 36th International Conference Machine Learning, pp. 344-353. PMLR, 2019.
Tianshu Chu, Sandeep Chinchali, and Sachin Katti. Multi-agent reinforcement learning for net- worked system control. In Proceedings of the 8th International Conference on Learning Repre- sentations, 2020.
Kai Cui, Anam Tahir, Gizem Ekinci, Ahmed Elshamanhory, Yannick Eich, Mengguang Li, and Heinz Koeppl. A survey on auge-populattin systems and scalable multi-agent reinforeement learning. arXiv preprint arXiv:2209.03859 2022.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. In Proceedings of the 36th Interna- tional Conference on Machine Learning, pp. 1538-1546. PMLR, 2019.
Ziluo Ding, Tiejun Huang, and Zongqing Lu. Learning individually inferred communication for multi-agent cooperation. In Advances in Neural Information Processing Systems, volume 33, pp. 22069-22079, 2020.
Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 5(1):17-60, 1960.
Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning, In Advances in Neural Information Processing Systems, volume 29, 2016.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018
Benjamin Freed, Guillaume Sartoretti, Jiaheng Hu, and Howie Choset. Communication learning via backpropagation in discrete channels with unknown noise. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 7160-7168, 2020.
Cong Guan, Feng Chen, Lei Yuan, Chenghe Wang, Hao Yin, Zongzhang Zhang, and Yang Yu. Efficient multi-agent communication via self-supervised information aggregation. Advances in Newral Information Processing Systems, volume 35, pp. 1020-1033, 2022.
Guangzheng Hu, Yuanheng Zhu, Dongbin Zhao. Mengchen Zhao, and Jianye Hao. Event-triggered communication network with manitedbbnnwwidte constraint for multi- reinforcement learn- ing. IEEE Transactions Neural Networks and Learning Systems, 2021.

---

Published as a conference paper at ICLR 2025
Shengchao Hu, Li Shen, Ya Zhang, and Dacheng Tao. Learning multi-agent communication from graph modeling perspective. In Proceedings of the 12th International Conference on Learning Representations, 2024.
Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi- cooperation. In Advances in Neural Information Processing Systems, volume 31, 2018.
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement learning. In Proceedings of the 8th International Conference on Learning Representations 2020.
Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. Learning schedule communication in multi-agent reinforcement learning. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian Stich. Consensus control for decentralized deep learning. In Proceedings of the 38th International Conference on Machine Learning, pp. 5686-5696. 2021.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82-94, 2016.
Pascal Leroy, Pablo G Morato, Jonathan Pisane, Athanasios Kolios, and Damien Ernst. IMP-MARL: suite of environments for large-scale infrastructure management planning via MARL. In Ad- vances in Neural Information Processing Systems, volume 36, 2024.
Xinran Li and Jun Zhang. Context-aware communication for multi multi-agent reinforcement learning. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 1156-1164, 2024.
Yong Liu, Weixun Wang. Yujing Hu, Jianye Hao, Xingguo Chen, and Yang Gao. Multi-agent game abstraction via graph attention neural network. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 721 1- 1-7218, 2020.
Yat Long Lo, Biswa Sengupta, Jakob Nicolaus Foerster, and Michael Noukhovitch. Learning multi- agent communication with contrastive learning. In Proceedings of the 12th International Confer- ence on Learning Representations, 2024.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative compeeiiiveee environments. In Advances Neural Information Pro- cessing Systems, volume 30, 2017.
Xueguang Lyu, Yuchen Xiao, Brett Daley, and Christopher Amato. Contrasting centralized and de- centralized critics in multi-agent reinforcement learning. In Proceedings of the 20th International Conference on Autonomous Agents and Mulliagent Systems, pp. 844-852, 2021.
Chengdong Ma, Aming Li, Yali Du, Hao Dong, and Yaodong Yang. Efficient and scalable rein- forcement learning for large-scale network control. Nature Machine Intelligence, pp. 1-15, 2024.
Yaru Niu, Rohan R Paleja, and Matthew C Gombolay, Multi-agent graph-attention communication and teaming. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, volume 21, pp. 964 97, 2021.
Frans A Oliehoek and Christopher Amato. A concise introduction to decentralized POMDPs. Springer, 2016.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint 1rXiv:1807.03744 2018.
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. In Proceedings of the Neural Information Proneaaaatooooooossstisisi Processing Systems Track on Datasets and Benchmarks, 2021. URL http: //arxivv.org/aas/2000666
12

---

Published as a conference paper at ICLR 2025
Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Fierre-Alexand Kamienny, Philip Torr Wendelin Böhmer, and Shimon Whiteson. Facmac: Factored multi- centralised policy gra- dients. In Advances in Neural Information Processing Systems, volume 34, pp. (2208-12221 2021.
Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent pnarrretiionallycoornnattt nets: Emergence of human-level coordination in learning to play starcraft combat games. arXiv preprint urXiv:/703: 10069, 2017.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi-agent reinforcement 2020.
learning. The Journal of Machine Learning Research, 21(1):7234-77)
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 White- son. The starcraft multi-agent challenge. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2186-2188 2019.
Lukas M Schmidt, Johanna Brosig, Axel Plinge, Bjoem M Eskofier, and Christopher Mutschler. An introduction to multi-agent reinforcement learning and review of its application to autonomous mobility. In IEEE 25th International Conference on Intelligent Transportation Systems (ITSC), pp. 1342-1349, IEEE, 2022.
Sven Seuken and Shlomo Zilberstein. Improved memory-bounded dynamic programming for de- centralized pomdps. In Proceedings of the Twenty- Conference on Uncertainty in Artificial Intelligence, pp. 344-351, 2007.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when to communicate at scale in multiagent cooperative and competitive tasks. Proceedings of the 7th International Conference on Learning Representations, 2019.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropaga- tion. In Advances Neural Information Prucessing Systems, volume 29, 2016.
Gokul Swamy, Siddharth Reddy, Sergey Levine, and Anca Dragan. Scaled autonomy: Enabling human operators to control robot fleets. In 2020 IEEE International Conference on Robotics and Automation, pp. 5942-5948. IEEE, 2020.
Jordan Terry, Benjamin Black, and Mario Jayakumar. Magent. htttps://githb..r com/ Farama-Foundat ion.mnddaiio///Meetttt 2020. GitHub repository.
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael G. Rabbat. Slowmo:
Improving communication-efficennn distributed SGD with slow momentum. Proceedings of 8th Inter- national Conference Learning Representations, 2020a.
Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decom- posable value functions via communication minimization. In Proceedings of the International Conference on Learning Representations, 2020b.
Xiaolu Wang, Huaxi Gu, Yintang Yang, Kun Wang, and Qinfen Hao. RPNoC: A ring-based packet- switched optical network-on-chip. IEEE Photonics Technology Letters, 27(4):423-426, 2015.
Xiaolu Wang, Huaxi Gu, Yintang Yang, Kun Wang, and Qinfen Hao. highly scalable optical network-on-chip with small network diameter and deadlock freedom. IEEE Transactions Very Large Scale Integration (VLSI) Systems, 24(12):344-34436 2016.
Yuanfei Wang, Fangwei Zhong, Jing Xu, and Yizhou Wang. ToM2C: Target-oriented multi-agent communication and cooperation with theory of mind. In Proceedings of the 10th International Conference on Learning Representations, 2022.
Jannis Weil, Zhenghua Bаo, Osama Abboud, and Tobias Meuser. Towards generalizability of multi- agent reinforcement learning in graphs with recurrent message passing. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pp. 1919-1927, 2024.
13

---

Published as a conference paper at ICLR 2025
Xianliang Yang, Zhihao Liu, Wei Jiang, Chuheng Zhang, Li Zhao, Lei Song, and Jiang Bian. A ver- satile multi-agent reinforcement learning benchmark for inventory management. arXiv preprint arXiv:2306.07542, 2023.
Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. In Advances in Neural Information Processing Systems, volume 34, pp. 13975-13989 2021.
Wang Ying and Sang Dayong. Multi-agent framework for third party logistics in E-commerce. Expert Systems with Applications, 29(2):431-436 2005,
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. In Advances in Neural Information Processing Systems, volume 35, pp. 24611 14624, 2022.
Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan. Yinghui Xu, and Wotao Yin. Decentlam: Decentralized momentum sgd for large-batch deep training. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 3029-3039, 2021.
Lei Yuan, Jianhao Wang, Fuxiang Zhang, Chenghe Wang, Zongzhang Zhang, Yang Yu, and Chongjie Zhang. Multi-agent incentive communication via decentralized teammate modeling. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9466-9474, 2022.
Tingting Yuan, Hwei-Ming Chung, Jie Yuan, and Xiaoming Fu. Dacom: Learning delay-aware communication for multi-agent reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 11733-11771, 2023.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. In Proceedings of the 35th International Conference on Machine Learning, pp. 5872-5881. PMLR, 2018.
Sai Qian Zhang, Qi Zhang, and Jieyu Lin. Succinct and robust multi-agent communication with temporal message control. In Advances in Neural Information Processing Systems, volume 33, pp. 17271-17282, 2020.
Lianmin Zheng, Jiacheng Yang, Han Cai, Ming Zhou, Weinan Zhang, Jun Wang, and Yong Yu. Magent: A many-agent reinforcement learning platform for artificial collective intelligence. In Proceedings of the AAAI conference artificial intelligence, volume 32, 2018.
Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Mont- gomery Alban, Iman Fadakar, Zheng Chen, et al. Smarts: An open-source scalable multi-agent RL training school for autonomous driving. In Proceedings of the Conference on Robot Learning, pp. 264-285. PMLR, 2021.
Changxi Zhu, Mehdi Dastani, and Shihan Wang. A survey of multi-agent deep reinforcement learn- ing with communication. In Mehdi Dastani, Jaime Simão Sichman, Natasha Alechina, and Vir- ginia Dignum (eds.). Proceedings of the 23rd International Conference on Autonomous Agents and MultiAgent Systems, pp. 2845-2847, 2024.
14

---

Published as a conference paper at ICLR 2025
A THEORETICAL ANALYSIS
In this section, we analyze the communication effect of exponential topologies.
Theorem 1. Suppose that Eú; defined by Equation 2 Let T = [log2 (N - 1)}. Then, the following holds:
Eig X6 b)
E++1 Xg... B. E 11T;
(7)
where X denotes logical (Boolean) matrix multiplication.
Remark 1. If the information each agent remains valid within timesteps and there is infor- mation loss during aggregation, the one-peer exponential topology ensures information exchange between any two agents in the system with timesteps.
Remark 2. Static exponential topologies exhibit similar communication effect described in Theorem Specifically, Vi.j that Frj
(e(one-peor) 1, it holds that Fr(cua))
Proof. Define function Z 1 - [0,1] such that
1, 0,
Z(x)
(8)
0, x=
Then, for all x, 1/ u, O, the following equivalence holds:
zy +
= (Z(x) Z(v)) to (Z(u) X I(u)) 0,
(9)
where X denotes logical (Boolean) And, and + denotes logical (Boolean) Or. Now, consider the connection between ((x) and the structure of an all-one matrix. For a non-negative matrix X, holds that Xi, E R Vi,j > Z(X) = 11".
Therefore, by applying Appendix to B E Fly X6 F+++1 .b... p++r-1
$ 11
Ying et al. 2021). we have
11
B EXPERIMENT DETAILS
B.1 NETWORK ARCHITECTURE AND HYPERPARAMETERS
Codebase codebase:
Our implementation of ExpoComm and baseline algorithms is based the following
EPyMARL (Papoudakis et al.
2021): http://///attuuoocooo///oee/aaaa
CommFormer Hu et (2024)
CommNet (Sukhbaatar et al.
2016): httpss//ggthub..com//papssss////
The code for ExpoComn
ExpoComm is
publicly available https::/github.com
Neural network architecture Following previous work Papoudakis et al. (2021), employ deep neural networks consisting multilayer perceptrons (MLPs) with rectified linear unit (ReLU) ac- tivation functions and gated recurrent units (GRUs) parameterize the agent networks. In Ex- poComm, the message memory blocks described in Section 3.2 are implemented using a single GRU or an attention block. The prediction network f(: described in Section 3.3 is implemented using a two-layer MLP.
To ensure fair comparison, we implement our method and self-constructed baselines using the same codebase with the same set of hyperparameters, with the exception of method-specific ones and the learning rate. general, we follow the common settings provided by Papoudakis et al. (2021) for MAgent benchmark and adopt the settings in IMP paper (Leroy jet al., 2024) for the IMP benchmark. The common hyperparameters are listed in Table 2 The ExppoComm-specffic hyperparameters are provided in Table 3 For learning rate, search among
Hyperparameters
15

---

Published as a conference paper at ICLR 2025
(0.0001, 0.0005) for ExpoComm and baselines. We use the value of 0.0005 for base algorithms without communication; 0.0005 for DGN+TarMAC
MAgent and 0.0001 for DGN+TarMAC in IMP; 0.0001 for ExpoComm in IMP with 50 agents and 0.0005 for other scenarios. For Comm- Former, we adopt the optimal value in its official implementation.
Table 2: Common hyperparameters.
Hyperparameter
Benchmark
Value
Hidden sizes
64
MAgent
0.99
Discount factor y
IMP
0.95
MAgent
32
Batch size
IMP
64
Replay buffer size
2000
MAgent
10
Number of environment steps
IMP
2 x 106
MAgent
x 10s
Epsilon anneal steps
IMP
10
MAgent
x 104
Test interval steps
IMP
2.5 104
Number of test episode
100
Table 3: Hyperparameters used for ExpoComm.
Hyperparameter
Value
Auxillary loss coefficient
0.1
Temperature
0.07
Number of negative pairs M
20
B.2
ENVIRONMENTAL DETAILS
Codebase
The environments used in this work are listed below with descriptions in Table
MAgent (Zheng et al.
2018 Terry al. 2020
https://qithub com / Farama Fourdation/MAgents
IMP (Leroy et al.
2024 http:://gthhb..cco///rrrttotoggp
Table 4: Environments details.
Environment
Scenarios
Number of agents
Adversarial Pursuit Battle
(25, 45, 61) (20, 42, 64)
MAgent
Uncorrelated: uncorrelated k-out-of-n; campaign cost
(50, 100)
IMP
Correlated: correlated k-out-of-n; campaign cost
(50, 100)
OWF: offshore wind farm; campaign cost
(50, 100)
The number of agents in this scenario is determined by setting the map size to 25, 35, 40,
respectively.
The number of agents in this scenario is determined by setting the map size to 45, 60, 70, respectively.
MAgent MAgent is highly scalable gridworld gaming benchmark shown Figure 7 In Adversaria Pursuit t, agents aim tag adversaries while adversaries try escape. Agents
16

---

Published as a conference paper at ICLR 2025
25 vB 50
81 V9 81
(a) AdversarialPursui..
(b) Battle.
Figure 7: Environments from the MAgent benchmark suite Teery et al. 2020 each scenario, the MARL algorithms control the red agents, while the blue adversary agents controlled by pretrained policies.
System failure risk
System failure risk
System fuilure risk
Component /Agent
Damage probability
Component /Agent
Damage probability
Component /Agent
Damage probability
Q
I
h
Figure 8: IMP environment (Leroy al., 2024). This environment simulates an engineering system with multiple components controlled by agents. The objective is to minimize overall system failure risk low costs. The system risk depends on component damage probabilities, which evolve over time and can be influenced by agent inspection or repair actions.
can choose actions from move, tag or do nothing. Agents are rewarded for successfully tag- ging adversary and penalized for unsuccessful tagging attempts. In Battle, agents attempt to attack and eliminate adversaries, with the same goal for adversaries. Agents can choose actions from move, attack do nothing. A team wins by eliminating all opponents or having more surviving agents when the episode ends.
individual reward setting with IDQN as the base algorithm. Due to the high-dimensional observations in MAgent, storing experi- ence in replay buffer be challenging because of hardware constraints. We adopt preprocessing procedure following Jiang et al. (2020), compressing observations by concatenating [my _team_hp _hp obstacle/off the map, other team hp- obstacle/off the map]. To facilitate the use communication, we use small view ranges (8 for Adversare
Following the official implementation (Terry et al. 2020),
Plluuuuitt and for Bat Battle). le). In both scenarios, we pretrain the adversary policies using the IDQN algorithm with a self-play scheme and use these pretrained policies to test the performance of different algorithms.
IMP IMP platform for benchmarking the scalability of cooperative MARL methods in real- world engineering applications, illustrated in Figure This environment simulates infras- tructure management planning problem with agents controlling different components. Agents can choose actions from inspect ion, repair do nothing. In different scenarios, the corre- lation between agent deterioration processes and the system failure function are defined differently, posing unique challenges.
17

---

Published as a conference paper at ICLR 2025
Following the official implementation of IMP, as the base algorithm due to its stable performance across scenarios. We adopt the campaign cost setting, which requires higher cooperation among agents. As recommended by Leroy et al. 2024),
global reward setting and choose QMIX
results are normalized with respect to expert-based heuristic policies using (a (== H) where is the discounted rewards of the tested algorithm, and H is the discounted rewards achieved by heuristic policies listed in 5
Table 5: Heuristic policies performance on the IMP benchmark.
Scenario
Number of agents N
Discounted reward H
50
-232.7 -231.5
Uncorrelated
100
50
-211.0
Correlated
100
-194.0
50
-1248.2
OWF
100
2433.3
B.3 IMPLEMENTATION DETAILS
In MAgent, implement our proposed ExpoComm along with baselines DGN+TarMAC and ER on top of the IDQN base algorithm. In IMP, these are implemented on top of QMIX. For Ex- poComm, we use Equation for MAgent benchmark because the global state is provided in this environment, and Equation (5) for IMP, as the global state is a concatenation of all observations and compact or suitable for message grounding.
B.4 EXPERIMENTAL INFRASTRUCTURE
The experiments were conducted using NVIDIA GeForce RTX 3080 GPUs and NVIDIA A A100GPUs. Each experimental run required less than 2 days to complete.
C MORE RESULTS AND DISCUSSION
C.I VISUALIZATION RESULTS
We visualize the final trained policies of ExpoComm and IDQN in AversariaaPurssee and Battle with Figure 9 and Figure 10 respectively to demonstrate how ExpoComm enhances co- operation among agents. As shown in Figure 9a and Figure [0a] agents adopt global perspective and act cooperatively with ExpoComm policies, demonstrating effectiveness even under extreme communication budgets( K = 1). In comparison, IDQN agents focus only on local observations and often become trapped in suboptimal solutions due to lack of coordination.
C.2 COMPARISON WITH PROXY-BASED COMMUNICATION
Although we primarily focus on decentralized communication- MASS without centralized proxies, also compare ExpoComm against the proxy-based CommNet (Sukhbaatar et al.) 2016). As seen in Figure [ and Table 6) ExpoComm outperforms CommNet in most scenar- 1os, especially in IMP benchmarks. However, CommNet achieves comparable performance the Adversari a Pauuruuuuui t tasks. This implies that a global perspective is more crucial for success in these scenarios, possibly explaining ExpoComm's larger advantage over other baselines in this scenario.
C.3 LIMITATIONS AND FUTURE WORK
While ExpoComm demonstrates strong performance and scalability cooperative multi-agent tasks, some limitations remain.
18

---

Published as a conference paper at ICLR 2025
0
28
t = 56
t
t= 112
t= 140
168
196
(a) ExpoComm policies with K = 1. Red agents push blue adversary agents to the edge of the frame and trap them there obtain high rewards by repeatedly tagging them.
t= 0
t= 28
t 56
84
t= 112
140
168
t 196
(b) IDQN policies.
Figure 9: Visualization in AdversarialPursui w/ 61 agents.
First, ExpoComm does not explicitly incorporate agent heterogeneity or properties of the underlying environmental MDP when constructing the communication topology. This could result in subopti- mal performance in scenarios requiring targeted messaging between specific agents (Yuan et al., 2022 or networked MDPs (Zhang et al. 2018 Ma et al.) 2024). Therefore, Incorporating factors like agent identities relationships presents promising direction for further improvements in such settings.
Second, we evaluated ExpoComm primarily in fully cooperative tasks. Partially competitive settings requiring agents to learn to communicate only when necessary remain challenging. Examining ExpoComm' capabilities and limitations in such partially competitive tasks presents important avenue for future work.
Finally, communication scalability in multi-agent systems remains under-explored area despite the attempt of this work. For instance, incorporating finer graph topologies beyond exponential graphs may enhance performance, and exploiting temporal communication sparsity could further reduce costs. There are still many open questions in scaling communication efficiently.
19

---

Published as a conference paper at ICLR 2025
t= 0
t= 11
t= 21 Per
== 31
t= 41
51
t= 61
[ 71
(a) ExpoComm policies with K Agents coordinate ensure red agents outnumber blue adversaries on the front line (t = 11, 21), securing an advantage. Once red agents substantially outnumber blue adversaries, they surround the remaining adversaries (1 61, /= 71) eliminate them.
t
t
(b) IDQN policies.
Figure 10: Visualization in Battle 64 agents.
20

---

Published as a conference paper at ICLR 2025
ExpoComm w/
ExpoComm w/ K = [logzN]
CommNet
100
100
100
Evaluatin Retur
Evaluation Retum
Evaluation Retur
75
50
50
50
25
25
25
Timesteps
Timesteps
Timesteps
(a) AdversarialPursuii w/ 25 agents (b) AdversarialPursuit w/ 45 agents (c) AdversarialPursuit w/ 61 agents
1.0
Evaluation Win Rate
0.8
Evaluation Win Rate
0.8
0.6
0.6
Evaltation
0.4
0.4
0.2
0.2
Timestops
Timesteps
Timesteps
(d) Battle w/ 20 agents
(e) Battle w/ 42 agents
(I) Battle w/ 64 agents
Figure 11: Performance comparison with proxy-basee baselines on MAgent tasks.
Table 6: Performance comparison with proxy-based baselines on IMP tasks. Re- sults are reported as the mean and standard deviation of the percentage of nor- malized discounted rewards relative to expert- based heuristic policies, following Leroy et al. (2024), with details in Appendix B.2 The best-performing method is indicated in bold, and the second best underlined.
CommNet
ExpoComm
Scenario
with communication proxy
K
K log N
50
Uncorrelated
26.07 (6.82)
27.31 (2.26)
28. 26 (2.51)
Correlated
26.14 (16.87)
43.87 (6.33)
40.01 (3.19)
OWF
53.71 (1.27)
64.66 (0.26)
65.19 (0.51)
N 100
Uncorrelated
65.92 (125.03)
(1333))
27.81 (5.71)
Correlated
-82.76 (48.62)
19.17 (23.94)
17.25 (22.7) (22770)
OWF
34.71 (5.34)
(5.2661.3)
66. 23 (0.38)
21


Reviews:
[{"review_id": "WTOPfmbfWy", "reviewer": "Reviewer_MSLo", "summary": "This paper proposes to utilize the exponential topology to enable rapid information dissemination among agents, which leads to scalable communication protocol ExpoComm. A memory-based message processors are employed and auxiliary loss is introduced to ground message. Experiments are conducted to validate their algorithm.", "questions": "- In figure 4(f), why does the test win rate of ExpoComm start to drop from 4*1e6 step? \n- This algorithm should excel in large-scale multi-agent environment, so can we suppose the performance gap between the algorithm proposed and other baselines should increase when the number of agents increase? If so, why can't we see such trend in figure 4?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Extensive experiments\n- Superior performance against other baselines", "weaknesses": "- The presentation of section 3.3 is not ideal, e.g. line 323, can you elaborate more on the prediction function f? line 354 to line 355, what is t'?", "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": "C1KhPQ0aJO", "reviewer": "Reviewer_9jpX", "summary": "The paper introduces ExpoComm, a scalable communication protocol for multi-agent reinforcement learning that uses exponential graph topologies to efficiently manage information flow among numerous agents in large-scale environments. Exponential graphs offer a small-diameter structure enabling ExpoComm to have rapid and cost-effective communication across agents. The method overcomes the need to finding task specific pairwise communication. The authors utilize a memory based message network for processing messages over time and to allow agents to accumulate and utilize past information. In addition, auxiliary tasks are used to align messages with global information, either through direct access to the global state (when available) or through contrastive learning techniques. The method is evaluated on MAgent gridworld benchmarks and compared with baselines having varying communication protocols.  The one-peer verison of the exponential graph performed the best despite only requiring a linear scaling communication cost.", "questions": "The proposed exponential topology works well for cooperative tasks. However, could the authors clarify how this approach might be adapted for tasks where agents require specific pairwise connectivity? For instance, if a task necessitates more targeted information sharing between certain agents due to task-specific roles, would ExpoComm accommodate such requirements?\n\nHow would the proposed protocol perform in scenarios where some agents are adversarial or non-cooperative?\n\nCould the authors provide more details about the experimental setups? Including environment visualizations or schematic diagrams would be extremely helpful for understanding the experimental conditions. Such visual aids could illustrate the setup, agent interactions, and communication patterns in more detail.\n\nIn Figures 4 and 6, the x-axis is labeled as \"test return,\" although it appears to show plots related to training return. Could the authors clarify this discrepancy?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The use of exponential graphs as a communication topology in MARL is an innovative approach.  Combining memory-based message processing and auxiliary tasks to enhance message relevance is also a strong contribution. The authors have performed extensive experiments with multiple baselines. The zero-shot transferability demonstrates a level of generalization. The method’s scalability and efficiency in managing communication in large agent populations without sacrificing performance have implications for large-scale MARL applications. Overall, the manuscript is well-organized and clearly presents both the motivation and implementation details of the proposed approach.", "weaknesses": "The paper would benefit from a more explicit discussion of the limitations of ExpoComm. Specifically, scenarios where the proposed exponential topology may not be ideal---such as tasks requiring task-specific pairwise communication links or settings where agents are non-cooperative or adversarial---are not fully addressed.", "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": "5Rmn4XSwaW", "reviewer": "Reviewer_56ww", "summary": "The work focuses on the improving communication in large scale multi-agent reinforcement learning. The authors propose using exponential topology as a communication pattern among agents. The authors show that this method can improve the multi-agent performance in a large scale environment using the MAgent and Infrastructure Management Planning environments.", "questions": "- How does the proposed method performs compared to traditional mulitcast type of multi-agent communication method such as CommNet, as it seems more global communication is beneficial for the target scenarios?\n- How does the proposed exponential graph compared with random selection of communication peers? (keeping the number of communication peers the same)?\n- What are the limitation of this method? Based on the results in Figure 4, the benefit of the method is more obvious for AdversarialPursuit than for Battle. It seems it's only learning after for the Battle environments. Is it learning faster for Battle because there is less communication peers for each node?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The author studies the problem of improving large scale MARL communication, which can be helpful for MARL research and deployment.\n- The paper is well written and easy to follow. The toy example and figures presented is helpful for understanding.\n- The proposed method seems to show improved performance for the AdversarialPursuit case.", "weaknesses": "- It is unclear how the proposed exponential graph can be helpful for improving agent communication under target scenario. Providing some theoretically analysis or motivating example would be helpful. The toy example is helpful, but random global communication is not considered there.\n- Beside the exponential graph, the contribution of this work seems limited. Highlighting and clarifying the contributions of this work would be helpful for better understanding.\n- Evaluation seems incomplete. Comparing the proposed method to the traditional broadcast communication methods can help make the claim more persuasive.", "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": "RmQilNqqWo", "reviewer": "Reviewer_6QM3", "summary": "This work focuses on the problem of learning scalable communication in many-agent systems through multi-agent reinforcement learning. To tackle this problem, this work uses exponential graphs to model the communication topology, and memory-based message processors and message grounding for information representation. Through examples and baseline comparisons, the authors demonstrate that exponential graphs can balance the trade-off between dissemination speed and redundancy; thereby allowing agents to receive messages from other connected members in the graph without additional communication overhead.", "questions": "-  Do you have any theories why CommFormer performs so terribly in the Adversarial Pursuit 25 agent case? It performs similarly to ExpoComm in the Battle Environment 20 agent case; I would be interested to hear your theories on why it doesn’t generalize well or performs similarly to ExpoComm in that one case. \n\n- The performance of ER and ExpoComm are very smilar in the filled bar transferability cases (i.e. K=log2N). Do you have theories about why this is? \n\n- Did you experiment with more K values beyond log2N and 1? If so, what did you observe and why did you believe these two values in the paper would be representative examples?\n\n- Does communication overhead in this paper refer to number of messages passed? Can you provide a definition in-text? Are there additional communciation savings that can be achieved by your method beyond its exponential graph structure? (i.e. savings due to pruning or shorter timesteps or less redundant agents communicated with to compared to other techniques)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The problem this paper seeks to address is an interesting and important issue in multi-agent reinforcement learning regarding scalable communication. The idea of using exponential graphs in this application is novel to me, and I appreciated the way that the authors helped the reader build intuition for the benefits ofgraph design in section 3.1; an exponential  I thought this was clear and very well-written. The experiments on the transferability of the method were very thorough, and I appreciated the comparisons for both K cases. The ablation studies served to reiterate the author's point and useful aspects of their architecture.", "weaknesses": "Overall, my concerns with this paper lie in the framing regarding communication overhead. \n- The definition of communication overhead in this paper is rather ambiguous. It would probably be best to add a formalized definition, as communication overhead has very field-specific connotations beyond computer science. While addressed by the authors in the introduction, it is possible to reduce communication overhead by only communicating with a subset of peers. If ExpoComm does produce lower communication overhead, I think this paper could be strengthened significantly by adding additional metrics where the number of messages (or unique messages) ExpoComm has sent is directly compared against another method that only communicates with a subset of agents (eg DGN). From my understanding, Table 1 lacks these comparisons now. If ExpoComm does not result in lower numbers of messages passed between agents against comparable baselines (eg. MAGIC, DGN), then I would recommend clarifying the wording throughout the paper, to be in line with your definition of communication overhead.", "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)