Multi-Agent Coordination via Multi-Level Communication
Authors: Ziluo Ding
Zeyuan Liu
Zhirui Fang
Kefan Su
Liwen Zhu
Zongqing Lu
Venue: NeurIPS 2024 poster (2024)
Keywords: multi-agent reinforcement learning
Primary area: reinforcement_learning
TL;DR: We propose SeqComm, a multi-agent communication scheme that enhances coordination by prioritizing actions and communication.

Abstract: The partial observability and stochasticity in multi-agent settings can be mitigated by accessing more information about others via communication. However, the coordination problem still exists since agents cannot communicate actual actions with each other at the same time due to the circular dependencies. In this paper, we propose a novel multi-level communication scheme, Sequential Communication (SeqComm). SeqComm treats agents asynchronously (the upper-level agents make decisions before the lower-level ones) and has two communication phases. In the negotiation phase, agents determine the priority of decision-making by communicating hidden states of observations and comparing the value of intention, which is obtained by modeling the environment dynamics. In the launching phase, the upper-level agents take the lead in making decisions and then communicate their actions with the lower-level agents. Theoretically, we prove the policies learned by SeqComm are guaranteed to improve monotonically and converge. Empirically, we show that SeqComm outperforms existing methods in a variety of cooperative multi-agent tasks.

Multi-Agent Coordination via Multi-Level Communication
Ziluo 1:2e
Zeyuan Liu
Zhirui Fang!
Kefan Su?
Liwen Zhu?
Zongqing Lu².t
Tsinghua Shenzhen International Graduate School, Tsinghua University, "eeking University, Teeneett Al Lab
Abstract
The partial observability and stochasticity in multi-agent settings can be mitigated by accessing more information about others via communication. However, the coordination problem still exists since agents cannot communicate actual actions with each other at the same time due to the circular dependencies. In this paper, we propose a novel multi-level communication scheme, Sequential Communicution (SeqComm). SeqComm treats agents asynchronously (the upper-level agents make decisions before the lower-level ones) and has two communication phases. the negotiation phase, agents determine the priority of decision -aasinnn by communicating hidden states of observations and comparing the value of intention, obtained by modeling the environment dynamics. In the launching phase, the upper-level agents take the lead in making decisions and then communicate their actions with the lower-level agents. Theoretically, we prove the policies learned by SeqComm are guaranteed to improve monotonically and converge. Empirically, we show that SeqComm outperforms existing methods in various cooperative multi-agent tasks.
Introduction
Centralized training with decentralized execution (CTDE) [Lowe et al., 2017] is popular learning paradigm in cooperative multi-agent reinforcement learning (MARL). Although the centralized value function be learned to evaluate the joint policy of agents, the decentralized policies of agents are essentially independent. Therefore, a coordination problem arises. That is, agents may make sub-optimal actions by mistakenly assuming others' actions when there exist multiple optimal joint actions [Busoniu et al., 2008]. Communication allows agents to obtain information about others avoid miscoordination [Jiang al., 2024]. However, most existing work only focuses on communicating messages, e.g., the information of agents' current observation or historical trajectory (Jiang and Lu, 2018, Singh et al., 2019, Das et al., 2019, Ding al., 2020]. It is impossible for an agent to acquire other's s actions before making decisions since the game model is usually synchronous, i.e., agents make decisions and execute actions simultaneously.
A general approach to solving the coordination problem is to make sure that ties between equally good actions broken by all agents. One simple mechanism for doing is to know exactly what others will do and adjust the behavior accordingly under a unique ordering of agents and actions
'Equal contribution.
Correspondence to Zongqing Lu <zongqing. lu pkw.edu.cn>>. Ziluo Ding <ziluoding @ chaaiacc.cn A Work done during an internship Tsinghua Shenzhen International Graduate School, Tsinghua University.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

[Busoniu et al., 2008]. Inspired by this, we reconsider the cooperative game from an asynchronous perspective. In other words, each agent assigned a priority (i.e. order) of decision decision-making at each step, thus the Stackelberg equilibrium (SE) [Von Stackelberg, 2010] is naturally set up as the learning objective. Specifically, the upper-level agents make decisions before the lower-level agents (Fach agent represents a unique level, with upper and lower levels being relative.). Therefore, the lower-level agents can acquire the actual actions of the upper-level agents by communication and make their decisions conditioned on what the upper-level agents would do. Importantly, we never break the fundamental dynamic, p( St, a 12k-1),, ), in the multi-agent system. The agents make decisions asynchronously but perform actions simultaneously as the default environment setting.
Under this setting, the SE is likely to be Pareto superior to the average Nash equilibrium (NE) in games that require high cooperation level [Zhang et al., 2020]. However, is it necessary to decide specific priority of perisionnmakinng for each agent? Ideally, the optimal joint policy can be decomposed by any orders [Wen et al., 2019], e.g., n² (a1, 00]s))2)))))))))) = x² (a1 (01ls))** (02 88 @1) = x" (aaals)) (a1 |s, 02). But during the learning process, agents are unlikely to use other agents' optimal actions for gradient calculation, making it still vulnerable to the relative overgeneralization problem [Wei et al., 2018]. This means there is no guarantee that different orders will converge to the same suboptimal. We also claim that the different priorities of decision-makir the learning algorithm in Section 3. Note that relative overgeneralization occurs when a suboptimal NE in the joint space of actions is preferred over an optimal NE because each agent's 's action in the suboptimal equilibrium is a better choice when matched with arbitrary actions from the cooperative agents.
may affect the optimality of the convergence of
This work proposes novel multi-level communication scheme for cooperative MARL, Sequential Communication (SeqComm), to enable agents to coordinate with each other explicitly. Specifically, SeqComm has two-phase communication, negotiation phase and launching phase. In the negotiation phase, agents communicate their hidden states of observations with others simultaneously. Then, they can generate multiple predicted trajectories, called intention, by modeling the environmental dynamics and other agents' actions. In addition, the priority of decision decision-making is determined by communicating and comparing the agents' intentions, which are evaluated by their state-value functions. The value of each intention represents the predicted rewards obtained by treating that agent as the first mover of the order sequence. The sequence of others follows the same procedure as aforementioned with the upper-level agents fixed. In the launching phase, the upper-level agents take the lead in maaiingn and communicate their actual actions with the lower-level agents. The actual actions will be executed simultaneously in the environment without changes.
SeqComm is currently built on MAPPO [Yu et al., 2021J. Theoretically, we prove the policies learned by SeqComm are guaranteed to improve monotonically and converge. Empirically, we evaluate SeqComm on StarCraft multi-agent challenge v2 (SMACv2) [Samvelyan et al., 2019]. We demonstrate that SeqComm outperforms existing communication-free and communication- based methods in various maps in SMACv2. By ablation studies, we confirm that treating agents asynchronously is more effective way to promote coordination, and SeqComm can provide the proper priority of decision-makingg for agents to develop better coordination.
2 Related Work
Communication. Existing work [Jiang and Lu, 2018, Kim al., 2019, Singh al., 2019, Das et al., 2019, Zhang et al., 2019, Jiang et al., 2020, Ding et al., 2020, Konan et al., 2022] in this realm mainly focus on how to extract valuable messages. ATOC [Jiang and Lu, 2018] and IC3Net [Singh et al., 2019] utilize gate mechanisms to decide when to communicate with other agents. Several studies [Das et al. 2019, Konan et al., 2022] employ multi-round communication to fully reason the intentions of others and establish complex collaboration strategies. Social influence [Jaques et al., 2019] uses communication to influence the behaviors of others. I2C [Ding et al., 2020] only communicates with agents that are relevant and influential which are determined by causal inference. However, all these methods focus on how to exploit valuable information from current or past partial observations effectively and properly. More recently, some studies [Kim et al., 2021, Du et., 2021, Pretorius et al., 2021] begin to answer the question: can we favor cooperation beyond sharing partial observation? They allow agents to imagine their future states with world model and communicate those with others. IS [Pretorius et al., 2021], as the representation of this line of research, enables each agent to share its intention with other agents in the form of the encoded imagined trajectory and use the

---

attention module to figure out the importance of the received intention. However, two concerns arise. On one hand, circular dependencies can lead to inaccurate predicted future trajectories as long as the multi-agent system treats agents synchronously. On the other hand, MARL struggles in extracting useful information from numerous messages, not to mention more complex and dubious messages, Lee predicted future trajectories. Unlike these studies, we treat the agents from an asynchronous perspective, therefore, circular dependencies can be naturally resolved. Moreover, agents send actions to lower-level agents, making the messages compact and informative.
Coordination. The agents are essentially independent decision- makers in execution and may break ties between equally good actions randomly. Thus, in the absence of additional mechanisms, different agents may break ties in different ways, and the resulting joint actions may be suboptimal. Coordination graphs [Guestrin et al., 2002, Böhmer et al., 2020, Wang et al., 2021] simplify the coordination when the global Q-function can be additively decomposed into local Q-functions that only depend on the actions of a subset of agents. Typically, coordination graph expresses a higher- order value decomposition among agents. This improves the representational capacity to distinguish other agents' effects local utility functions, which addresses the miscoordination problems caused by partial observability.
Another general approach to solving the coordination problem is to make sure that ties are broken by all agents in the same way, requiring that random action choices are somehow coordinated or negotiated. Social conventions [Boutilier, 1996] or role assignments [Prasad et al., 1998] encode prior preferences towards certain joint actions and help break ties during action selection. Communication [Fischer et al., 2004, Vlassis, 2007] can be used to negotiate action choices, either alone or in combination with the aforementioned techniques. Our method follows this line of research by utilizing the ordering of agents and actions to break the ties, other than the enhanced representational capacity of the local value function.
More discussions of related work are in Appendix C.
3 Problem Formulation
Cost-Free Communication. The decentralized partially observable Markov decision process (Dec- POMDP) can be extended to multi multi-agent POMDP [Oliehoek et al., 2016] by sharing observations among agents via communication. The joint observations are not necessarily equivalent to the state. However, joint observations can be used to represent the state better than single observations.
Previous work [Pynadath and Tambe, 2002] shows that under cost-free communication, agents would share optimal messages for mutual interest. If the communication cost is high, there is a balance between delivering all the useful messages for greater benefits and keeping the amount of communication as low as possible. In addition, analyzing this extreme case gives us some understanding of the benefit of communication, even if the results do not apply across all domains. However, even under multi-agent POMDP where agents can get joint observations, coordination problems can still arise [Busoniu et al., 2008]. Suppose the centralized critic has learnt actions pairs (01, a2] and [by, by] that are equally optimal. Without any prior information, the individual policies T and T2 learned from the centralized critic can break the ties randomly and may choose ai and b2. respectively.
Multi-Agent Sequential Decision-Making. We consider fully cooperative multi-agent tasks that are modeled as multi-agent POMDP, where n agents interact with the environment according the following procedure, which we refer to as multi-agent sequential decision-making
At each timestep f,, assume the priority (i.e. order) of decision-making for all agents is given and each priority level has only one agent (ie., agents make decisions one by one). Note that the smaller the level index, the higher priority of decision-making is. The agent at each level i gets its own observation of drawn from the state 8t, and receives messages m, kk from all other agents, where m, & A {(o), at), (op-1 a - ot ..... of }. Equivalently, m, can be written as (o, at 1:k-1), where o, denotes the joint observations of all agents except k (in practice, agents communicate the hidden states/encodings of observations), and a 1 denotes the joint actions of agents 1 to 1. For the agent the first level (i.e., 1), a. ! = 2. Then, the agent determines its action at sampled from its policy me(-log m. or equivalently (- at 1:1-1) and sends it to the level agents. After all, agents have determined their actions, they perform the joint actions
3

---

12
Agent
10
11
b2
bg
Agent A
Q1
6
B
A -+B
02
-6
8
0
Simuttaneous
Learned
03
0
Sleg
1e6
(a) payoff matrix of the game
(b) evaluations of different methods
Figure 1: (a) Payoff matrix for one-step game. There multiple local optima. (b) Evaluations of different methods for the game in terms the mean reward and standard deviation ten runs. A 4 B, B + A, Simultaneous, and Learned represent that agent A makes decisions first, agent B makes decisions first, two agents make decisions simultaneously. and there is another learned policy determining the priority of decision making, respectively. MAPPO [Yu et al., 2021] is used as the backbone.
ag, which can seen sampled from the joint policy T- (1)) factorized as IT (T a d in the environment and get shared reward r(st, az) and the state transitions to next state s' according the transition probability p(s" (ss, a.). All agents aim maximize the expected return Σ 7 rr where is the discount factor. The value function and action- value function of the level-k agent defined as follows:
VaL (1n-1)
r'relso s, ag" 1:k-1 aa ll:k-1]
$1.00
Qn
E
rrllso 8, a. a l1².
t=
For the setting of multi-agen aggent sequential decision mekiinn discussed above, we have the following proposition.
Proposition 1. If all the agents update their policy with individual TRPO [Schulman el al., 2015] se- quentially in multi-agent sequential decision-making. then the joint policy of all agents are guaranteed improve monotonically and converge.
Proof. The proof is given in Appendix A.
Proposition indicates that SeqComm has the performance guarantee regardless of the priority of decision-making in multi-agen agent sequential decision making. However, the priority of decision decision-makinn making indeed affects the optimality of the converged joint policy, and we have the following claim.
Claim 1. The different priorities of decision miissinn-making affect the optimality the convergence the learning algorithm due to the relative overgeneralization problem.
We use one-step matrix game as an example, illustrated in Figure I(a), demonstrate the influence of the priority of decision-making on the learning process. Due to relative overgeneralization [Wei al., 2018], agent / tends choose by or 63. Specifically, b2 or by in the suboptimal equilibrium is a better choice than by in the optimal equilibrium when matched with arbitrary actions from agent A. Therefore, as shown Figure 1(b), B conditions on the action of B) and Simultaneous (i.e., two agents make decisions simultaneously and independently) are easily trapped into local optima. However, agent goes first, things can be different, as A > B achieves the optimum. As long as agent A does not suffer from relative overgeneralization, it can help agent get rid of local optima by narrowing down the search space of B. Besides, policy that determines the priority of decision-male maakin can be learned under the
(i.e., agent B makes decisions before A, and A's policy

---

negobation phase
launching phuse
Figure 2: Overview of SeqComm. SeqComm has two communication phases, the negotiation phase (left) and the launching phase (right). the negotiation phase, agents communicate hidden states of observations with others and obtain their own intention. The priority of decision-making is determined by sharing and comparing the value of all the intentions. In the launching phase, the agents who hold the upper-level positions will make decisions prior to the lower-level agents. Besides, their actions will be shared with anyone that has not yet made decisions.
guidance of the state-value function, denoted as Learned. It obtains better performance than B A and Simultaneous, which indicates that dynamically determining the order during policy learning can be beneficial as we do not know the optimal priority in advance.
The priority (i.e. order) of decision-making affects the optimality of the converged joint policy in multi-agent sequential decision decision-making, thus it is critical to determine the order. However, learning the order directly requires an additional centralized policy execution. which not generalizable in a scenario where the number of agents varies. Moreover, its learning complexity exponentially increases with the number of agents, making it infeasible in many cases.
Remark 1.
Sequential Communication
In this paper, we cast our eyes in another direction and resort to the world model, which is the dynamic model of the environment. Ideally, them under the world model (see Section 4.1), and choose the order sequence that is deemed the most promising under the true dynamic. SeqComm is designed based this principle determine the priority of drcision-making via communication.
randomly sample candidate order sequences, evaluate
In SeqComm, communication is separated into phases serving different purposes and multi-round communication in one phase is possible. One is the negotiation phase for agents to determine the priority of decision-making. Another is the launching phase for agents to act conditioning on actual actions upper-level agents will take to implement explicil coordination via communication. The overview of SeqComm is illustrated in Figure 2. Each SeqComm agent consists of policy, critic, and a world model, as illustrated in Figure 3, and the parameters of all networks are shared across agents [Gupta et al., 2017].
World Model. The world model is needed to predict and evaluate future trajectories. SeqComm, unlike previous works [Kim et al., 2021, Du et al., 2021, Pretorius et al., 2021], can utilize received hidden states of other agents the first round of communication to model more precise environment dynamics for the explicit coordination in the next round of communication. Once an agent can access other agents' hidden states, shall have adequate information to estimate their actions since all agents are homogeneous and parameter-sharing Therefore, the world model MM() takes as input the joint hidden states h; = {h].... ... he } and actions a,, and predicts the next joint observations and reward. In practice, before the inputs pass into the world model, the attention module AM, is utilized to process the input.
0 fet1 = (A,, at))-
The reason that we adopt the attention module is to entitle the world model to be generalizable the scenarios where additional agents introduced existing agents are removed.
5

---

4.1 Negotiation Phase
In the negotiation phase, the observation encoder first takes or as input and outputs a hidden state hy to compress the information, which is used to communicate with others. Note that many studies [Ding et al., 2020, Jiang and Lu, 2018] found that redundant messages may impair the learning process empirically. In more detail, the model can converge slowly or sometimes lead to a worse sub-optimal. Agents then determine the priority of recision-making by intentions which established and evaluated based on the world model.
Priority of Decision-Making Intention is the key element in determining the priority of decision- making. The notion of intention is described as an agent's 's future behavior in previous works [Rabinowitz et al., 2018, Raileanu al., 2018, Kim al., 2021]. However, we define the intention as an agent's 's future behavior without considering others.
As mentioned before, agent's intention considering others can lead to eircular dependencies and cause miscoordination. By our definition, the intention of an agent should be depicted as all future trajectories considering that agent as the first mover and ignoring the others. However, there are many possible future trajectories as the priority of the rest of the agents is unfixed. In practice, we use the Monte Carlo method to estimate the intention value based on all future trajectories. Note that is uniform across priorities for unfixed agents. Each order should be treated equally since we do not have any prior for the distribution.
Taking agent at timestep to illustrate, it firstly considers itself as the first-mover and produces its action only based on the joint hidden states, a ~ TT( (.M-|AM,, 0). where we again an attention module AM, to handle the input. For the order sequence of lower-level agents, we randomly sample of order sequences from unfixed agents. Assume agent j is the second-moved agent models j's action by considering the upper-level action following its own policy of ग.. 7t(-AAM, (h,, a()). The same procedure is applied to predict the actions of all other agents following the sampled order sequence. Based on the joint hidden states and predicted actions, the next joint observations ot-1 can be predicted by the world model M. The length of the predicted future trajectory is H and it can then be written as r {ō++1, d.t1.... Ou+H H. ā H } by repeating the procedure aforementioned.
Then, the agent uses its critic (state-value function) to evaluate the future trajectory and output value Myt. The intention value is defined as the average value of F future trajectories with different sampled order sequences. Through the critic, we have linked the order and agent performance together.
After all the agents have computed their intentions and the corresponding value, they again commu- nicate their intention values to others. Then, agents would compare and choose the agent with the highest intention value to be the first mover. The priority of lower-level decision-making follows the same procedure with the upper-level agents fixed. Note that some agents may communicate intention values with others multiple times until the priority of decision-making making is finally determined.
4.2 Negotiation Phase for Local Communication
The full communication version of SeqComm is constructed based on theoretical derivation. It has a theoretical guarantee to some extent, but some assumptions, e.g., broadcast communication, can be unrealistic and incur lots of communication overhead. Therefore, we provide another version of SeqComm in scenarios where agents can only communicate with nearby agents (agents within limited communication range).
In more detail, the agent first calculates its intention value based only on the hidden states of nearby agents. After comparing with the intention values of nearby agents (intention values are communicated with the nearby agents), the agent determine the upper-level and lower-level nearby agents. Unlike the previous version of SeqComm, agents cannot distinguish the detailed order sequence of the leper-level nearby agents since their communication ranges may not overlap. Therefore, the intention values are calculated and communicated among agents for only one time. The local communication version greatly reduces communication overhead, making more suitable for many real applications.
For more details of the algorithms, please refer to the Appendix D for the pseudo-code.
4.3 Launching Phase

---

TOUS
As for the launching phase, agents communi- cate to obtain additional information to make decisions. Apart from the received hidden states from the last phase, we allow agents to get what actual actions the upper-level agents will take in execution, while other studies can only infer oth- ers' actions by opponent modeling [Rabinowitz et al., 2018, Raileanu et al., 2018] or communi- cating intentions [Kim et al., 2021]. Therefore, miscoordination can be naturally avoided, and better cooperation strategy possible since lower-level agents can adjust their behaviors ac- cordingly.
AM,
Pelicy
[6
AM,
AM,
World
Cricc
nower
(a).07)
AM,
R,s (0) (0.
lower-level agent i make decision follow- ing the policy T. Fr(-IAMa(h,, a, a,pPe")). where a, upper means received actual actions from all upper-level agents. As long as the agent has de- cided on an action, it will send the action to all other lower-level agents through the communica- tion channel. Note that the actions are executed simulhaneously and distributedly in execution, though agents make decisions sequentially.
Figure 3: Architecture of SeqComm. The critic and policy of each agent take input as its own ob- servation and received messages. The world model takes as input the joint hidden states and predicted joint actions.
4.4 Theoretical Analysis
As intention values determine the priority of decision-making, SeqComm is likely to choose different orders at different timesteps during training. However, we have the following proposition that theoretically guarantees the performance of the learned joint policy under SeqComm.
Proposition 2. The monotonic improvement and convergence of the joint policy in SeqComm independent of the priority of recision-making of agents at each timestep.
Proof. The proof is given in Appendix A.
The priority of decision- maasing chosen under the world model, thus the compounding errors the world model can result in discrepancies between the predicted returns of the same order under the world model and the true dynamics. We then analyze the monotonic improvement for the joint policy under the world model based on Janner et al. [2019].
Theorem Let the expected total variation between two transition distributions be bounded at each timestep as max; Eew DDr (p(s'Is, a) ()ssss''|s,
S Em. and the policy divergences at level is be bounded as mi DTv (TT.A (a*1s [s, a 12:k-11 1 the data collecting policy for the model and f( 6(s8|s, [s, a) is the transition distribution under the model. Then the model return and true return 7i of the policy π are bounded as:
a=* S Emp where πA is
(|[T]] 2 -|[>]-
2aymaa max (Cm + 2 2 Ek= Cx.)
+ 4r Ammax Σk=1 CTA
(1 (1- 7
(1 (1-7)
OlemsExrin)
Proof. The proof is given Appendix B.
Remark Theorem I provides a useful relationship between the compounding errors and the policy update. As long we improve the return under the true dynamic by more than the gap, C(Cm Cri.. ). we can guarantee the policy improvement under the world model. no such policy exists to overcome the gap, it implies the model error is too high, that is, there is a large discrepancy between the world model and true dynamics. Thus the order sequence obtained under the world model not reliable. Such an order sequence is almost the same as random one. Though random order sequence also has the theoretical guarantee Proposition 2, we will show in Section 5.2 that random order sequence leads to poor local optimum empirically.
7

---

0.8
TarMAC
0.5
SeqCamm (oral)
SegComm
SenComm (ocall
0.6
TrrMe
TaYMAC
TU/MAG (ocall
MANOO
0.3
MAPPO
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0M
2M
4M
6M
8M
10M
0M
2M
41
6M
8M
10M
0M
2MM
4M
6M
6M
10M
(a) protoss. 5.v
(b) protoss
protoss. 10. 10_vs_11
0.6
0.15
0.4 TarMAc Blagh
(pocal)
0.2
0.2
0.05
0.0
0.00
0M
2M
4M
6M
8M
10M
DM
2M
4M
6M
8M
10M
0M
2M
4M
6M
BM
10M
(d) terran_5_vs.
(c) Cerram.10.vs.ll.
(f) Cerran_10.vs.11.
SeaComm
Seotomm
SeaComm
TrrMAC
ThrMANC
0.4
TwrMAC
0.4
0.4
(leal)
0.2
0.0
0.0
0.0
10M
0M
2M
4M
6M
8M
10M
(g) zerg 5_vs_5
(h) 10
(i) 10.g.10.vv.11
Figure Learning curves of SeqComm and baselines nine SMACv2 maps.
Experiments
SeqComm is currently instantiated based on MAPPO [Yu et al., 2021]. We evaluate SeqComm nine maps in StarCraft multi- agent challenge v2 (SMACv2) [Ellis et al., 2024].
In the experiments, SeqComm and baselines are parameter-sharing for fast convergence [Gupta et al,, 2017, Terry et al., 2020]. We have fine-tuned the baselines for a fair comparison. The world model in the SMACv2 environment is trained from scratch and kept fine-tuned the learning process. Therefore, no extra prior knowledge is provided. Please refer to the Appendix for the hyperparameter settings, All results are presented terms of the mean and standard deviation of five runs with different random seeds.
5.1 Results
SMACv2. We have evaluated method the most representative and challenging multi-agent environment currently available. Compared with SMAC [Samvelyan et 2019], SMACv2 has some better properties, i.e. stochasticity and partial observability. In other words, agents need to cooperate more in the new environment to complete tasks, whereas they could achieve a certain success rate without cooperation in the original environment.
We have chosen nine maps for extensive evaluation and made some minor changes to the observation part of agents to make it more difficult. Specifically, the sight range of agents is reduced from 9 to 3, and agents cannot perceive any information about their allies even they are within the sight range. NDQ [Wang et al., 2020] adopts similar change increase the difficulty of action coordination. The rest of the settings remain the same as the default. summary, we require the environment to be one where high success rule cannot be achieved solely based individual observations.
We also evaluate the local communication version of SeqComm. Agents can only communicate with nearby agents (agents within their communication range). Note that the map size and the total number

---

0.8
SeqComm (range
0.5
SeqComm (range 9)
SeqComm (local)
SeqComm (local)
0.6
SeqComm frange.3 3)
SeqComm (range 3)
SeqComm Jeag
Seofomm genge
0.4
MAP
0.3
RAPPO
0.2
0.2
0.1
0.0
0.0
0M
2M
4M
6M
8M
10M
0M
2M
4M
6M
8M
10M
(a) protoss. 10_vs_10
(b) terran. 10_vs_10
Figure Ablation studies of the communication ranges.
of agents restrict the number of nearby agents. As the task progresses, the number of nearby agents is from 2 to
Analysis. The learning curves of SegComm and the baselines in terms of the win rate are illustrated in Figure 4. All communication-bor based methods perform better than communicaion-free method (MAPPO). In easy scenarios, communication may not be very useful, but experiments have shown that in cases with significant partial observability and stochasticity, communication can greatly enhance agent ability.
We compare our method with TarMAC [Das al., 2019], which holds similar position in communi- cation settings to that of MAPPO in communication-free settings. SeqComm outperforms TarMAC all maps, which verifies the gain of explicit action coordination. Moreover, the full-communiattoon version performs better than the local-communicee information. However, also costs more communication overhead.
version because the former can access more
5.2 Ablation Studies
Priority of Decision-Making. We primarily want to contribute practical version to the community. Moreover, the fewer communicative agents there are, the fewer possible orders there are, thus increasing the probability of randomly obtaining a good order. It would be more meaningful to demonstrate that devoting effort finding good order still important in such a scenario. Therefore, we do the ablation study for the local version of the SeqComm. In more detail, we compare SeqComm with two ablation baselines: the priority of decision-making is determined randomly at each timestep, denoted Random, and agents only access the observations of others during training and execution, denoted as No action.
As depicted in Figure 7, SeqComm achieves a higher win rate than Random and No action in all the maps. These results verify the importance of the priority of decision-makee and the necessity to adjust it continuously during one episode. It is also demonstrated that SeqComm can provide proper priority of meaeii..nmmaiing..... As discussed in Section 4.4, although Random also has the theoretical guarantee, they converge to poor local optima in practice. Surprisingly, in most tasks, Random performs worse than No action. again verifies that bad order may fail improve coordination or even impair it.
Communication Range We also conduct experiments to demonstrate the impact of different communication ranges. We set communication ranges (1, 9). in addition to the default range of 6. We notice a steady improvement in performance the communication range increases. Therefore, the choice of communication range a trade-off between communication overhead and agent performance. In our previous experiments, we choose compromise value of for the local version validate the effectiveness of method. Results refer to Figure 5,
0.4
SeaComm llocal)
TaMMAC (local)
0.3
Socform Loccal migi
0.2
0.1
0.0
Figure 6: Ablation studies on the net- work mechanisms.

---

0.8
SecComm adiann)
SeqComm action) SegComm (rendoen)
SeqComm action)
0.6
Corm magoe
SegComm (randam)
MAPSO
MAPPO
0.4
0.2
0.2
0.1
0.0
0.0
0M
2M
4M
6M
8M
10M
0M
2M
41
6M
8M
10M
0M
2M
4M
6M
6M
10M
(a) protoss. vs_5
(b) protoss
protoss. 10. 10.vs_11
(leca))
SceComm
0.15
0.3
0.2
0.05
0.0
0.00
0M
2M
4M
6M
8M
10M
DM
2M
4M
6M
8M
10M
0M
2M
4M
6M
BM
10M
(d) terran_5_vss
(c) 10.vs_10_vv_10
(f) 10.vsn1
SuaComm (bcal)
Seetom (lcal)
0.4
SegComm Socall
CorCormm (nCaehin
SeqComm (no actlos)
GegComm action)
SooComi
SooComm (riddmm.
0.4
Coupeey
0.4
0.2
0.1
0.0
0.0
0.0
10M
2M
4M
6M
8M
10M
(g) zerg 5_vs_5
(h)
10_v_10
(i) 10.g.10.vs.11
Figure Ablation studies under local communication in SMACv2.
Network Mechanisum. We replaced the attention mechanism for local communication with aggregation method. In more detail, messages are concatenated and passd into a five-layer linear neural networks. The curve is based on 3 random seeds and tested the terran 10v10 map. The results refer to Figure 6.
6 Conclusions
We have proposed SeqComm, which enables agents to coordinate well and explicitly with each other, and it, from an asynchronous perspective, allows agents to make decisions sequentially. A two-phase communication scheme has been adopted to determine the priority of decision-making and transfer messages accordingly. Empirically, it is demonstrated that SeqComm outperforms baselines in variety cooperative multi-agent scenarios.
Limitations. The assumption of accessing the local observation of any other agent could be strong since unsuitable for all applications. Thus, we provide local communication version of SeqComm for assumption relaxation in the experiment.
Acknowledgements
This work was supported by the STI 2030-Major Projects under Grant 2021ZD0201404 and the NSFC under Grants 62450001 and 62476008.
10

---

References
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference Machine Learning (ICML), 2020.
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. In Conference on Theoretical Aspects of Rationality and Knowledge, 1996.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent reinforcement learning. JEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-177 2008.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. In International Conference on Machine Learning (ICML), 2019.
Ziluo Ding, Tiejun Huang, and Zongqing Lu. Learning individually inferred communication for multi-agent cooperation. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Yali Du, Yifan Zhao, Meng Fang, Jun Wang, Gangyan Xu, and Haifeng Zhang. Learning predictive communication by imagination in networked system control, 2021.
Benjamin Ellis, Jonathan Cook, Skander Moalla, Mikayel Samvelyan, Mingfei Sun, Anuj Mahajan, Jakob Foerster, and Shimon Whiteson. Smacv2: An improved benchmark for cooperative multi- agent reinforcement learning, Advances in Neural Information Processing Systems, 36, 2024.
Felix Fischer, Michael Rovatsos, and Gerhard Weiss. Hierarchical reinforcement learning in conmunication-mediine multiagent coordination. In International Joint Conference on Au- tonomous Agents and Multiagent Systems (AAMAS), 2004.
Amy Greenwald, Keith Hall, and Roberto Serrano. Correlated q-learnin. In A comprehensive survey of multiagent reinforcement learning, 2003.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In International Conference on Machine Learning (ICML), 2002.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi- agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2017.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, Dj Strouse, Joel Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning (ICML), 2019.
Haobin Jiang, Ziluo Ding, and Zongqing Lu. Settling decentralized multi-agent coordinated ex- ploration by novelty sharing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 17444 17452, 2024.
Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent cooperation. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongqing Lu. Graph convolutional reinforcement learning. International Conference on Learning Representation (ICLR), 2020.
Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. Learning to schedule communication in multi-agent reinforcement learning. In International Conference on Learning Representations (ICLR), 2019.
Woojun Kim, Jongeui Park, and Youngchul Sung. Communication in multi-agent reinforcement learning: Intention sharing. In International Conference on Learning Representations (ICLR), 2021.
11

---

Sachin Konan, Esmaeil Seraj, and Matthew Gombolay. Iterated reasoning with mutual information in cooperative and byzantine decentralized teaming. International Conference on Learning Representations (ICIR), 2022.
Ville Könönen. Asymmetric multiagent reinforcement learning. Web Intelligence and Agent Systems: An international journal, 105):1 2004.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed Processing Systems (NeurIPS), 2017.
environments. In Advances in Neural Information
Hang Ma, Daniel Harabor, Peter J Stuckey, Jiaoyang Li, and Sven Koenig. Searching with consistent prioritization for multi-agent path finding. In AAAI Conference on Artificial Intelligence (AAAI), 2019.
Frans A Oliehoek, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume Springer, 2016.
MV Nagendra Prasad, Victor R Lesser, and Susan E Lander. Learning organizational roles for negotiated search in a multiagent system. International Journal of Claman-Computer Studies, 48 (1):51-67, 1998.
Arnu Pretorius, Scott Cameron, Andries Petrus Smit, Elan van Biljon, Lawrence Francis, Femi Azeez, Alexandre Laterre, and Karim Beguir. Learning to communicate through imagination with model-based deep multi-agen reinforcement learning, 2021.
David V. Pynadath and Milind Tambe. The communicative multiagent team decision problem: Analyzing teamwork theories and models. J. Artif. Intell. Res., 16:389-423, 2002.
Neil Rabinowitz, Frank Perbet, Francis Song. Chiyuan Zhang, SM Ali Eslami, and Matthew Botvinick. Machine theory of mind. In International Conference on Machine Learning (ICML), 2018.
Roberta Raileanu, Emily Denton, Arthur Szlam, and Rob Fergus. Modeling others using oneself in multi-agent reinforcement learning. In International Conference on Machine Learning (ICML), 2018.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philiph H. S. Torr, Jakob Foerster, and Shimon Whiteson. The StarCraft Multi-Agent Challenge. arXiv preprint arXiv: 94.404443 2019.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning (ICML), 2015.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Individualized controlled continuous com- munication model for multiagent cooperative and competitive tasks. In International Conference on Learning Representations (ICLR), 2019.
Eric Sodomka, Elizabeth Hilliard, Michael Littman, and Amy Greenwald. Coco-q: Learning in stochastic games with side payments. In International Conference on Machine Learning (ICML), 2013.
Justin K. Terry, Nathaniel Grammel, Ananth Hari, Luis Santos, Benjamin Black, and Dinesh Manocha. Parameter sharing is surprisingly useful for multi-agent deep reinforcement learning, arXiv preprint 0rXiv:2005.13625 2020.
Jur P Van Den Berg and Mark H Overmars. Prioritized motion planning for multiple robots. In JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2005.
Nikos Vlassis. A concise introduction to multiagent systems and distributed artificial intelligence.
Synthesis Lectures Artificial Intelligence and Machine Learning, 1(1):1-11,201
Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science Business Media, 2010.
12

---

Tonghan Wang. Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decomposable value functions via communication minimization. In International Conference on Learning Representation (ICIR), 2020.
Tonghan Wang, Liang Zeng, Weijun Dong, Qianlan Yang, Yang Yu, and Chongjie Zhang, Context- aware sparse deep coordination graphs. arXiv preprint wrXi:2206.022866 2021.
Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. In AAAI Spring Symposium Series, 2018.
Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and W Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In International Conference on Learning Representations (ICLR), 2019.
Chao Yu, Akash Velu, Fugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.0/955 2021.
Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. AAAI Conference on Artificial Intelligence (AAAI), 2020.
Sai Qian Zhang, Qi Zhang, and Jieyu Lin. Efficient communication in multi-agent reinforcement learning via variance based control. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
13

---

A Proofs of Proposition and Proposition 2
Lemma (Agent-by-AAee PPO). If we update the policy of each agent with TRPO Schulman et al. [2015] (or approximately PPO) when fixing all the other agent's policies, then the joint policy will improve monotonically.
Proof. We consider the joint surrogate objective in TRPO T.maa (Tnew) where Wold is the joint policy before updating and new the joint policy after updating.
Given that new Told' have:
matia (Tnww) = Baw
Amraa (s, a)]
Tnew (a
=
Rawword
Told Wold(a
Amona (8,
T Nnow (a*1s)
Bawwaal
Amaul (8, a)]
Tota (a'ls)
F (a*1s)
B. inordd (Aroa (s, (s,a',a"))
nld (a'ls)
Nnow (a'1s))))
Hold (0, a²)
oodd (a
= Lou (Fnew):
where A as) E -- [Amasa (s, a', "] ] the individual advantage agent and the third equation is from the condition Tnow Told
With the result TRPO, we have the following conclusion:
J (nnew) (Tola) Limrs (Tnew) CDRL (Tuew (old)
= - (Thew)
CD
max KL (T [|
(from Tnew - -old
This means the individual objective is the same as the joint objective so the monotonic improvement guaranteed.
Then we can show the proof of Proposition 1.
Proof. We will build new MDP M based on the original MDP. We keep the action space À = A A', A where A is the original action space of agent The new state space contains multiple layers. We define S* state space. Then a new state z E Sh means that 3* = (s, a a² ... .a*). The total new state space defined as - St. Next we define the transition probability P as following:
(x (x= A+) for 1, ... n and S 5, where S is the original
1 a a (1+1)) 1 (5' (st,a k < -
15 h+2 a (1+1)) =1 5'' E 5o) P( x+), k= n=n-
This means that the state in the layer & can only transition to the state in the layer k + 1 with the corresponding action, and the state in the layer n will transition to the layer 0 with the probability P in the original MDP. The reward function is defined as following:
f(5, a) = E So a()
This means the reward is only obtained when the state in layer 0 and the value is the same as the original reward function. Now we obtain the total definition of the new MDP M = {$, A, P, n). Then we claim that if all agents learn in multi-agent sequential decision-making by PPO, they are actually taking agent-by-agent PPO in the new MDP M. To be precise, one update of multi-agent
14

---

sequential decision making in the original MDP M equals to round of update from agent to agent by agent-by-agent PPO in the new MDP M. Moreover, the total reward of round in the new MDP M is the same as the reward in one timestep in the original MDP M. With this conclusion and Lemma we complete the proof.
The proof of Proposition 2 can be seen as a corollary of the proof of Proposition 1.
Proof. From Lemma we know that the monotonic improvement of the joint policy in the new MDP M guaranteed for each update one single agent's 's policy. So even the different round of updates the new MDP M is with different order of the secision-making the monotonic improvement the joint policy is still guaranteed. Finally, from the proof of Proposition 1, we know that the monotonic improvement in the new MDP M equals to the monotonic improvement in the original MDP M. These complete proof.
B Proofs of Theorem
Lemma (TVD of the joint distributions). Suppose we have two distribution pi (xx Pi (x)p1 (xly) and p2(x. (z(x)))(z(y) We can bound the total variation distance of the joint as:
Drv(pi(a, (llpsaa s (rv(e max DTw
Proof. See [Janner et al., 2019] (Lemma B.1).
Lemma (Markov chain TVD bound, time-varing). Suppose the expected KL-divergence between two transition is bounded max, (s)p).(s) DKL (p1 (s'ss))(p(( (s){ 6, and the initial state distributions are the same ps) P2)=0(s). Then the distance in the state marginal is bounded as:
Drv (s)) s t5
Proof. See [Janner et al., 2019] (Lemma B.2).
Lemma (Branched Returns Bound). Suppose the expected Kl.-divergence between two dynamics distributions is bounded max, Ee (DV (s") P2) 8/18, a))}, and the policy diver-
gences at level are bounded as max Drv (a 8, a 1:k 1| (a a.,.akk-1)) S emp Then the returns are bounded as:
25 max (mm + Eh= CTT)
2rmax Σn= Exe 1-7
1m - S
7)-
where Tmax is the upper bound of the reward function.
Proof. Here, 7n denotes the returns of πi under dynamics Pı (s'1s, a), and m) denotes the returns of under dynamics Pa (s'ls, a). Then we have
(pi(s, - -p((s,))))(ss Σ
17 mpl
s.a
Σ
- (p
Y (p),((s p2.
s.a
ΣΣ (p,,((s, p2.(s, a))
mmax
15

---

By Lemma 2, we get
max maxDDr((((abslls(a
max
DTv(Ti |s, (1, "s, (|,aa)) a²))
5,81
+ max ( (mml
max (Tv(Ti(alss, a - " a, 1)))
s.akk-
mma
We then apply Lemma 3, using å = 6m + Ek= Sou (via Lemma 3 and 2) to get
Drv(pi,())llp2.(s)) max Es-p, (3) D pp) s))
max Es-m Drv
& t(max (pi
+ max Eompla(s) max D (T) (
S 1 +
mm)
k=1
And we also get Drv(pLi(s, a)).ss,)lll2.(.... a)) S t(Em + Ek=l Exe) + Ek=l Cn by Lemma 2. Thus, by plugging this back, we get:
11
72l
Tmax Σ - -2,,(s,,
a
2r max Σ (t(emm ΣGTL)
Exe)
Exc
(6m + + CTT))
2k= Cxp
2r max
(1-7)²
1 7-7
Then show the proof of Theorem
1.
Proof. Let n denote the data collecting policy. We use Lemma 4 to bound the returns, but will require bounded model error under the policy æ. Thus, need introduce π by adding and subtracting 7/ a)) to get:
n| + 1/ [r]. n|Ā] -]
we can bound L2 and Ly both using Lemma 4 by using ō = Σn CTu and 5 = 6m + Eb Cru respectively, and obtain:
2 mnax Ek= ETa
2r max Σk= ExT
L 2
(1 (1-))2
(1-2) 7)
L2 2 max (Em. + >i ExTE)
2rmax Ek | Exk
7)2
(1 7)
Adding these two bounds together yields the conclusion.
16

---

C Additional Related Work
Reinforcement Learning in Stackelberg Game Many previous studies [Könönen, 2004, Sodomka at. 2013, Greenwald et al., 2003, Zhang et al., 2020] have investigated reinforcement learning in finding Stackelberg equilibrium. Bi-AC [Zhang al., 2020] is a bi-level actor-critic method that allows agents to have different knowledge base so that Stackelberg equilibrium (SE) is possible to find. The actions can still be executed simultaneously and distributedly. It empirically studies the relationship between the cooperation level and the superiority of Stackelberg equilibrium to Nash equilibrium. AQL [Könönen, 2004] updates the Q-value by solving the SE in each iteration and can be regarded the value-baset version of Bi-AC.
Existing work mainly focuses on two-agent settings, and their order is fixed in advance. However, fixed order can hardly be an optimal solution, especially for large-scale homogeneous agent scenarios. To address this issue, we exploit agents' intentions dynamically determine the priority of decision- making along the way of interacting with each other.
Multi-Agent Path Finding (MAPF) MAPF aims to plan collision-free paths for multiple agents on a given graph from their given start vertices to target vertices. In MAPF, prioritized planning is deeply coupled with collision avoidance [Van Den Berg and Overmars, 2005, Ma et al., 2019], where collision is used to design constraints or heuristics for planning.
We will distinguish MAPF from our work from three perspectives, i.e. problem definition, the motivation behind agent ordering, and the incompatibility of the two methods.
Problem definition: MAPF aims to plan collision-free paths for multiple agents on given graph from their given start vertices to their given target vertices. However, we aim to find a communication- based solution for any Markov decision process with interests aligned. MDP covers lots of possible coordination-neede scenarios, not just avoiding collisions. Besides, each agent has no specific given target.
Motivation: In MAPE, prioritized planning does not offer completeness optimality guarantees. It nevertheless popular because of its efficiency. In addition, the order is mainly used for avoiding colli- sion. Unlike MAPF, our main contribution a method to determine the priority of docision-making To the best of our knowledge, determining the priority of docision-makinn for learning algorithms has not been investigated. Moreover, combining with learning algorithms will make prioritized decision crtision-maiing more general (solving MDPs), not just motion planning.
introduce prioritized decision-making MARL and
Methods: The different motivations and problems to solve will lead to the incompatibility of the algorithms in the two fields. For MAPF, the order is assigned arbitrarily or derived from the problem at hand. Collision is the keyword and prioritized planning is deeply coupled with this specific coordination problem that better performance can be achieved. Taking the method Ma et al. [2019] as an example, their two algorithms are conflict-driven search frameworks. That is, collision is used to design some constraints which are guided for search. In MARL, we have lots of unseen coordination problems and we cannot enumerate them all to design constraints.
D Implementation Details
D.1 Algorithm
In this part, we provide the pseudo-code of SeqComm as below:
Algorithm Negotiation Phase
Require: Number of agents N
P []: already determined priority
.A {1. 2, .... N): remaining agents
* Agents communicate the hidden state h of their observations with each other*/
for i = 1, 2, ..., do
for in A do
Compute agent j's intention value ey via Algorithm end for
17

---

1 Agents in A communicate the intention values with each other*/ Set p; be the agent j with the maximum Fj Append pt to P and remove it from A end for
Algorithm 2 Intention Value Calculation of Agent
Require: Already determined priority P. remaining agents A, number of sampling trajectories F,
length of predicted future trajectory H, policy т and attention module AM,, world model M and attention module A discount factor 7
for = 1, .... F' do
Randomly shuffle {a} sample decision- making priority PAysa) of the remaining agents except agent
for ==
H do
â "upper = f:: predicted actions from all upper-level agents for k: in Concat [a], (a)) do
Sample a² following TT- T-||AMa [ (hi+s, )Pper)
Append at apper
end for
Rollout one step with the world model Ó P+tj+1 = (MMMM (hits, ampper) end for Compute the return of the trajectory 1 = 21'=++1 7 1t ft-1-1ip via the critic end for
Compute the average return v = F. ΣE=1" 1
Algorithm Launching Phase
Require: Decision-making priority P. policy æ and AM,
at aupper ={): actions from all upper-level agents for á in P do
Sample af following Te (-Ma)Maahh a, (PPPer))
Append af to a. upper
1 Send a, hppee to the lower agent*/
end for Interact with the environment with d;
We also provide the pseudo-code of the local communication version as below:
Algorithm Local Negotiation Phase of Agent
Require:
Neighbouring agents AV
* Agents communicate the hidden state h of their observations with neighbouring agents#/ Compute local intention Va via Algorithm 5
** Send v. neighbouring agents and receive {2% Jee from them #/
Set upper-level neighbouring agents A Aupper = {i 1/2 > Va, E N} Set lower-level neighbouring agents N Voowwr {il 0/ < va E N7
Algorithm 5 Local Intention Value Calculation of Agent
Require: Neighbouring agents N, number of sampling trajectories F, length of predicted future trajectory H, policy π and A.,,, world model M and AM,, discount factor ? for i = 1,,,..., F do
Randomly shuffle N to sample local decision decision-making priority PN for j 0,
H do
à upper = []: predicted actions from all upper-level agents for 1: in Concat ([a), Pv) do
Sample at following (-IIAMa (hee, (pper))
Append at to à apper
end for
Rollout one step with the world model à o,-441, P44411 M(AM (hetj, a opper))
18

---

end for Compute the return of the trajectory 1 end for
E44
21 -t
Compute the average return e = Ei= U/ via the critic
Algorithm 6 Local Launching Phase of Agent a
Require: Upper-level neighbouring agents N Nupper, lower-level lowerveel neighbouring agents Ntower, policy
and A.M.
1 Receive upper-level actions a, upper from upper-level neighbouring agents N Nupper /* Sample of following Tz(. (-J.MM. at a)))er))
1* Send aj to all lower-level neighbouring agents Altwer */
Interact with the environment with a;
D.2 Architecture and Hyperparameters
Our models, including SeyComm and its ablations, are implemented based MAPPO. Two fully connected layers realize the critic and policy network. As for the attention module, key, query, and value have one fully connected layer each. The size of the hidden layers is 100. Tanh functions used as nonlinearity. As there is no released code of TarMAC, we implement TarMAC by ourselves, following the instructions mentioned in the original papers [Das et al., 2019].
For the world model, observations and actions are firstly encoded by a fully connected layer. The output size for the observation encoder is 48, and the output size for the action encoder is 16. Then, the outputs of the encoder will be passed into the attention module using the same structure aforementioned. Finally, the nonlinearity.
fully connected layer to decode. In these layers, Tanh is used as
SeqComm and its ablation baseline share the same hyperparameters. For Protoss, the learning rate is 1e 1e-b, while for Terran and Zerg, the learning rate is 2.5c H and F for calculating intention value is set to 20 and 2. For TarMAC, the learning rate is tuned as 5e -5 TarMAC adopts MAPPO as the backbone and two-round communication mechanism. For MAPPO, we follow the default settings of the official code [Yu et al., 2021].
D.3 Attention Module
Attention module (AM) is applied process messages in the world model, critic network, and policy network. AM consists three components: query, key, and values. The output of AM the weighted sum of values, where the weight of value is determined by the dot product of the query and the corresponding key.
For AM the world model denoted as AM agent gets messages m, h, from all other agents at timestep negotiation phase, and predicts query vector of following AM (ht). The query is used to compute a dot product with keys k = [Ny
kr). Note that ki is obtained by the message from agent following AM, (ht) for j A i, and ky is from AM non (Nt). Besides, it is scaled by 1/vde followed by a softmax to obtain attention weights a for each value vector:
T of Vdk
kl
oi ddz
kg
o
kn
a2 softmax
Vd
The output of attention module is defined as: of = Eド assyee. where of is obtained from messages or its own hidden state of observation following AM (-).
As for AM in the policy and critic network denoted as AM, agent i gets additional messages from upper-level agent in the launching phase. The message from upper-level and lower-level agent can be expanded as m, hpper = [hppper a, [upper] and moower- = [hlower, 0), respectively. In addition, the query depends on agent's own hidden state of observation hi; but keys and values are only from messages of other agents.
19

---

D.4 Training
The training SeqComm is an extension MAPPO. The observation encoder e, the critic V, and the policy are respectively parameterized by 8., 8.. fx. Besides, the attention module AM, is parameterized by 0 and takes as input the agent's hidden state, the messages (hidden states of other agents) in the negotiation phase, and the messages (the actions of upper-level agents) in launching phase. Let D {Tx } be a of trajectories by running policy in the environment. Note that we drop time in the following notations for simplicity.
The value function fitted by regression on mean-squared error:
C(O,.. Ba: 0.)
Σ TED
V(AM,(c(0).a Aell?
(2)
KT
where R is the discount rewards-to-go
We update the policy by maximizing the PPO-Clip objective:
min n (aa) (M((e a upper))
C(Ox, 0c) = KT
Totd (a (M))) ()pper)) Axai g(E, Amau))
(3)
TED t=
+ 6)A
A 2
where g(e, A)
and Agaia (0, a upper, a) is computed using the GAE method.
A < 0'
The world model .M is parameterized by ow is trained regression model using the training data set S. It is updated with the loss:
[()m.)
Σ
((GM)))(((MM(())....
S
o,a,o',res
We trained our model on one GeForce GTX 1050 Ti and Intel(R) Core(TM) 19-9900K CPU @ 3.60GHz.
D.5 Addtional Ablation Studies
We conduct a comparison of SeqComm against MAIC and CommFormer across six different maps: Protoss, Terran, and Zerg in 5v5 scenarios (first row) and Protoss, Terran, and Zerg in 10v 10 scenarios (second row). The evaluation uses the official codebase for each method, with three random seeds per map under full communication setting. The results refer to Figure 8.
D.6 Emergence of Behavioral Patterns
We have visualized several key frames in Figure 9 to highlight the observed behavioral patterns. In the combat game, concentrating attacks on a single enemy is consistently more effective than dispersing them. In frames 1-3, the agents lack specific targets until agent, located the end of the orange arrow, approaches an enemy in the bottom right corner. By frame 4, following the negotiation phase, this agent designated as the highest-level agent (level 5), given its advantageous position choose an enemy to attack. Once lower-level agents receive the actions from higher-level agents (represented by the white dashed line), all the red units cease random roaming and instead coordinate unified attack on the blue units. A similar pattern can be observed in frames 7-9.
20

---

0.6
0.8
MAT:
0.8
Formet
Commooorme
0.6
MAp
MAPPO
0.2
0.2
0.2
0.0
0.0
0.0
0M
2M
4M
6M
8M
10M
0M
2M
414
6M
8M
10M
0M
2M
4M
6M
6M
10M
(a) protoss. vs_55
terran. 5 vs.5
(c) zerg 5_vs.5
SooComm
0.8
Comminorrtt
MAPPO
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0M
2M
4M
6M
8M
10M
DM
2M
414
6M
8M
10M
0M
2M
4M
10M
(d) protoss_IO_vs.I1
(c) 10.r.a.10.vv.10
(1) 2erg-_10.vs_100
Figure 8: Results of experiments with extra baseline algorithms.
Lovel
Level
escrennuumry
Gluocoeenbummy
Level
Level1
Figure 9: Illustration of the Emergence of Behavioral Patterns
NeurIPS Paper Checklist
1. Claims
Do main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the Abstract, we outlined our contributions and reiterated our scope in the introduction.
Guidelines:
21

---

The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss our limitations in the Conclusions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
The Method or Appendix includes all assumptions and proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
22

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We fully disclose all the information needed reproduce the main experimen- tal results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
We plan to release data and code ASAP/upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://nips.cd cc/ pptltt//giiiee/ddddtttiiiisiaapp
for more details.
23

---

While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cctppcppppccccccccccccc wwwbbii/ggiiess///eeeee /tt.ge/oooe/dduiiiiiiiiin TrodeSubmissionPP.
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the training and test details in the Experiments and Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report error bars that are suitably and correctly defined, along with other appropriate information about the statistical significance of the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
24

---

If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes].
Justification:
We provide sufficient information on the computer resources in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpa /ttp//eeeurppppeeee/eeeeee cc cctppblic//eeeeeecececcccceceeet cttt://eeeetcciieeeeeeeeeeeeeee
Answer:
[Yes]
Justification:
All the research conducted conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: SeqComm is MARL method that does not have potential societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
25

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks. mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual- usal-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We properly credit all the assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi th com datasets has curated licenses for some datasets. Their licensing guide can help determine license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
26

---

Researchers should communicate the details of the dataset/codeemmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "LkW4TwNkNn", "reviewer": "Reviewer_iQrt", "summary": "This paper introduces SeqComm, a novel multi-agent reinforcement learning (MARL) method that addresses coordination issues through sequential decision-making and multi-level communication. The main contributions include:\n\n1. A new asynchronous perspective on MARL, allowing agents to make decisions sequentially.\n2. A two-phase communication scheme: negotiation phase for determining decision priorities, and launching phase for explicit coordination.\n3. Theoretical guarantees of monotonic improvement and convergence for the learned policies.\n4. Empirical evaluation on SMACv2 demonstrating superior performance over existing methods.", "questions": "(1) Could you elaborate on your choice of SMACv2 as the primary benchmark for evaluating SeqComm? Are there specific characteristics of SMACv2 that make it particularly suitable for demonstrating the advantages of your method? Additionally, do you believe the results from SMACv2 would generalize well to other MARL environments, and if so, why?\n(2) Have you considered the possibility of deadlocks in your asynchronous mechanism? What measures, if any, have been implemented to prevent or resolve potential deadlocks?\n(3) Can you provide an analysis of the computational complexity of SeqComm compared to existing methods, especially for large-scale multi-agent systems?\n(4) How sensitive is SeqComm to the choice of hyperparameters, particularly F and H? Are there any guidelines for selecting these values?", "limitations": "The authors have made an effort to address some limitations of their work, which is commendable. They acknowledge that the assumption of access to other agents' local observations might not be realistic in all applications. This transparency is appreciated and aligns with the NeurIPS guidelines on discussing limitations.\nHowever, there are several areas where the discussion of limitations could be expanded:\n\nScalability: The authors could further discuss how SeqComm's performance and computational requirements might change as the number of agents increases.\nGeneralizability: While SMACv2 is a valuable benchmark, the authors could address how well they expect their results to generalize to other MARL environments.\nPotential for deadlocks: Given the asynchronous nature of the method, a discussion on the possibility of deadlocks and how they are prevented or resolved would be beneficial.\nHyperparameter sensitivity: The authors could elaborate on how sensitive their method is to the choice of hyperparameters, particularly F and H.\n\nRegarding societal impact, the authors have not explicitly discussed potential negative consequences. While the immediate applications of this work may seem benign, it would be beneficial to consider and discuss potential misuse scenarios or unintended consequences of more efficient multi-agent coordination.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) Innovative methodology: The paper proposes a novel approach to MARL by introducing sequential decision-making and multi-level communication, which effectively addresses coordination issues.\n(2) Theoretical foundation: The authors provide rigorous theoretical analysis, including proofs of monotonic improvement and convergence for the learned policies.\n(3) Comprehensive empirical evaluation: The method is thoroughly evaluated on multiple maps in SMACv2, demonstrating consistent performance improvements over existing baselines.\n(4) Ablation studies: The paper includes detailed ablation studies that validate the importance of dynamic decision priority determination.\n(5) Practical considerations: The authors provide both a full communication version and a local communication version, addressing potential limitations in real-world applications.", "weaknesses": "(1) Computational complexity: The paper lacks a detailed analysis of the computational overhead introduced by the multi-level communication scheme, especially for large-scale multi-agent systems.\n(2) Sensitivity analysis: There is no discussion on the sensitivity of the method to hyperparameters, such as the number of sampling trajectories (F) or the length of predicted future trajectories (H).\n(3) Potential for deadlocks: The paper lacks a thorough discussion on the possibility of deadlocks in the proposed asynchronous mechanism, which is a critical consideration for any asynchronous system.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To begin with, we thank the reviewer for the carefully reviewing and insightful advice.\n\n>Could you elaborate on your choice of SMACv2 as the primary benchmark for evaluating SeqComm? \n\nIn cooperative MARL, SMAC is the most popular testbed for the centralized training and decentralized execution paradigm. Other important testbeds are Google Research Football (GRF) and Multiple Particle Environment (MPE). \n\nComparing the SMAC and other testbeds (MPE and GRF), SMACv2 (upgraded version of SMAC) is the latest testbed and proposed in 2023. This work critiques the original benchmark for lacking stochasticity and meaningful partial observability (SMAC, MPE, and GRF) and claims they simplify the coordination. It deliberately increases the stochasticity, meaning partial observability, and conducts thorough experiments to verify it. Our method aims to address the coordination issue in MARL and this problem is mostly induced by the partial observability of the agents. Therefore, our method is possible to demonstrate the superiority on the benchmark requiring high-level coordination, otherwise, the performance gap is not obvious for the benchmark where agents do not even need to coordinate to finish the tasks. \n\nCompared with other benchmarks, SMACv2 is more challenging from the following points. 1. Complex observation dimension (hundreds). 2. Diversity (many maps and unit types with different functions). 3. Stochasticity (different designed start positions). 4. meaningful partial observability (mask many irrelevant information). We believe the results from SMACv2 would generalize well to other MARL environments suffering from coordination issues since we chose the most challenging benchmark in this field. \n\n>Have you considered the possibility of deadlocks in your asynchronous mechanism? What measures, if any, have been implemented to prevent or resolve potential deadlocks?\n\nDeadlock occurs when two or more agents obtain the same intention value at the same time, and then they need another rule to determine the priority. In our implementation, each agent is assigned an index, and the rule to break the deadlock is the agent with a small index to determine first. \n\n> Can you provide an analysis of the computational complexity of SeqComm compared to existing methods, especially for large-scale multi-agent systems? \n\nThe computational complexity of SeqComm mainly related to communication overhead. \n\nFor full communication, SeqComm needs more rounds, but it only transmits observation information for one time. For the rest n − 1 round communication with total (n − 1)/2 broadcasts per agent, only a single intention value and an action will be exchanged. Considering there are n! permutations of different order choices for n agents, our method has greatly reduced computation overhead since each agent needs to calculate up to n times to search for a satisfying order. \n\nFor local communication, there are only two communication rounds. One is for sharing observations information. Another is for intention values. \n\n>How sensitive is SeqComm to the choice of hyperparameters, particularly F and H? Are there any guidelines for selecting these values?\n\nH is the length of the trajectory. Empirically, we found that 2-4 can lead to decent performance. For too long length, the error caused by the world model can be too large. Besides, since the order of each step can change, the observation after more steps is meaningless \n\nF is the number of the future trajectories. Theoretically, the higher the number of F, the more accurate the estimation, but the computational cost also increases. Therefore, in practice, we need to seek a trade-off.", "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": "BUHwSV87b2", "reviewer": "Reviewer_bJxi", "summary": "This paper introduces SeqComm, a novel multi-level communication scheme for multi-agent reinforcement learning. SeqComm enables agents to coordinate asynchronously, with upper-level agents making decisions before lower-level ones. The approach involves two communication phases: negotiation and launching. In the negotiation phase, agents communicate hidden states to determine decision-making priority, while in the launching phase, upper-level agents lead in decision-making and share actions with lower-level agents.", "questions": "None", "limitations": "refer to the \"weaknesses\" part.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. SeqComm introduces a novel communication scheme that significantly improves coordination in multi-agent settings.\n2. This paper demonstrates theoretical guarantees of monotonic improvement and convergence.\n3. This method outperforms existing approaches in various cooperative tasks, showcasing its effectiveness in challenging environments.", "weaknesses": "1. The assumptions regarding local observations and communications might not be realistic for all applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">The assumptions regarding local observations and communications might not be realistic for all applications.\n\nThank you for pointing out the limitations. We agree that the settings cannot be applied to all the applications. However, our setting is more realistic compared to other full communication and global observation settings. \n\nIn more detail, local observations are widespread in the real world because of the limitations of distance, hardware, or other objective factors. For example, not all information can be measured and obtained by the sensors in the real world, which makes global observations unrealistic.  \n\nFor communication, it is widely used in the real world. People use wireless communication to access the Internet. Also, the Internet of Vehicles and the Internet of Things aim to connect all things with communication by 5G, which means many works believe communication is necessary despite the difficulty in implementation.", "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": "7Nfjz5axSn", "reviewer": "Reviewer_LzSK", "summary": "This paper introduces SeqComm, a novel multi-level communication scheme for multi-agent coordination in reinforcement learning. The key contributions are:\n\n1. A new approach treating agents asynchronously with two communication phases: negotiation and launching.\n2. Theoretical analysis proving monotonic improvement and convergence of learned policies.\n3. Empirical evaluation on StarCraft multi-agent challenge v2 (SMACv2) showing superior performance over existing methods.\n\nThe paper addresses the coordination problem in multi-agent settings by allowing agents to communicate actual actions and determine decision-making priorities dynamically.", "questions": "1. How does the computational complexity of SeqComm scale with the number of agents, particularly in the negotiation phase? Is there a point where the overhead becomes prohibitive?\n2. Have you explored the performance of SeqComm in heterogeneous agent scenarios where parameter sharing may not be applicable? \n3. How might the method be adapted for such settings?\n4. How sensitive is the approach to the quality of the world model, especially in more complex environments? What happens if the world model is significantly inaccurate?\n5. The paper mentions that SeqComm can provide a proper priority of decision-making. How does this prioritization mechanism perform in highly dynamic environments where optimal decision order may change rapidly?\n6. Have you investigated the potential emergence of behavioral patterns or strategies across agents due to the asynchronous decision-making process? Are there any interesting emergent behaviors?\n7. How does the attention mechanism perform compared to simpler aggregation methods? An ablation study could illuminate this.\n8. Does the attention mechanism learn meaningful patterns of inter-agent importance? Visualizing attention weights could provide insights into learned coordination strategies.\n9. How does the computational cost of the attention mechanism scale with the number of agents, especially in the full communication scenario?\n10. Could more advanced attention mechanisms (e.g., multi-head attention) provide further improvements?\n11. How is the attention mechanism modified to handle the local communication scenario effectively?", "limitations": "- The evaluation is limited to one type of environment (SMACv2). It's unclear how well the method generalizes to other multi-agent scenarios with different dynamics or objectives.\n- The heavy dependence on a world model could be a significant limitation in environments where accurate modeling is challenging or computationally expensive.\n- While the paper addresses local communication, there's limited discussion on the trade-offs between communication frequency, accuracy, and overall system performance.\n- The empirical results are not significantly better in a lot of environments and changing the sight range from SmacV2 makes comparisons to previous work harder.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a solid theoretical foundation with proofs for policy improvement and convergence (Propositions 1 and 2, Theorem 1). The experimental methodology is sound, using the challenging SMACv2 benchmark and comparing against relevant baselines. The ablation studies support the importance of the proposed components.\n\nThe paper is generally well-written and organized. The introduction clearly motivates the problem and contributions. The method section provides a detailed explanation of SeqComm. Figures and algorithms help illustrate the approach. \n\nThe paper presents a novel and significant contribution to multi-agent reinforcement learning. The idea of asynchronous decision-making with dynamic priority determination is original and addresses an important challenge in the field. The theoretical guarantees and strong empirical results on a challenging benchmark demonstrate the value of the approach.\n\nOverall the strengths are:\n- Novel multi-level communication scheme addressing the coordination problem\n- Theoretical analysis providing performance guarantees\n- Fairly strong empirical results on SMACv2, outperforming existing methods\n- Ablation studies demonstrating the importance of key components\n- Addresses both full and local communication scenarios\n\nI'd also like to point out that this was run on a GTX 1050, which makes the model approachable to a general audience.", "weaknesses": "- The reliance on homogeneous agents with parameter sharing may limit the applicability of SeqComm in real-world scenarios where agents often have diverse capabilities. However, it is a commonly accepted assumption.\n- The approach heavily relies on a world model, but there's limited discussion on how the quality of this model affects performance, especially in more complex environments. Also the effect of the attention module is not analysed thoroughly. Attention mechanisms can be computationally expensive, especially as the number of agents increases. The paper doesn't address how this affects the overall scalability of SeqComm. It's not entirely clear how the attention mechanism is adapted for the local communication scenario, where agents only communicate with nearby agents. Furthermore, attention weights could potentially provide insights into which agents or information are most important for decision-making, but this aspect isn't explored in the paper.\n- Overall, I believe a table reporting IQM values over all environments would strengthen the paper and help with reproducibility. Furthermore, plots showing wall-clock time in comparison to other models would be insightful, especially since final performance only appears to be significantly better in p_10v10 and t_10v10.\n- While the paper addresses local communication, there's limited discussion on the trade-offs between communication frequency, accuracy, and overall system performance.\n- Though not standard in related work either, the paper doesn't thoroughly explore the robustness of SeqComm to noisy observations, communication failures, or adversarial agents, which are common challenges in real-world multi-agent systems.\n- While TarMAC is a strong baseline, the paper could benefit from comparisons with more recent state-of-the-art methods in multi-agent communication.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To begin with, we thank the reviewer for the carefully reviewing and insightful advice.\n\n>Computational complexity. \n\nThe computational complexity of SeqComm is mainly related to communication overhead. \n\nFor full communication, SeqComm needs more rounds, but it only transmits observation information for one time. For the rest n − 1 round communication with total (n − 1)/2 broadcasts per agent, only a single intention value and an action will be exchanged. Considering there are n! permutations of different order choices for n agents, our method has greatly reduced computation overhead since each agent needs to calculate up to n times to search for a satisfying order. Note that, in Section 3, we mentioned the cost-free communication setting. This extreme case gives us a better understanding of the benefit of communication, even if the results do not apply across all domains. Therefore, we propose a more applicable setting.\n\nFor local communication, there are only two communication rounds. One is for sharing observations and information. Another is for intention values. \n\n>Heterogeneous agent scenarios.\n\nWe would like to point out that the agents in SMACv2 can be heterogeneous. Each map has three types of agents. Three types have different functions (Ranged and melee types), and the types are randomly refreshed. It turns out our methods can be applied to heterogeneous agent scenarios. One policy can learn different strategies for different types of agents. Note that the observation contains the information of the agent type. \n\n>World model.\n\nTheorem 1 provides a useful relationship between the compounding errors and the police update. As long as we improve the return under the true dynamic by more than the gap (mentioned in line 292), we can guarantee the policy improvement under the world model. If no such policy exists to overcome the gap, it implies the model error is too high, that is, there is a large discrepancy between the world model and true dynamics. Thus, the order sequence obtained under the world model is not reliable. Such an order sequence is almost the same as a random one. Though a random order sequence also has the theoretical guarantee of Proposition 2, we have shown in Section 5.2 that a random order sequence leads to a poor local optimum empirically but it still can converge. \n\n>The prioritization mechanism \n\nIn each step, we will recompute the order based on the current situation. The proposition 2 shows that, even the order changes each step, the monotonic improvement and convergence of the joint policy in SeqComm will not be affected. \n\n>Emergence of behavioral patterns \n\nWe have visualized some key frames to illustrate the behavioral patterns in Figure 2 (pdf in the global response). In the combat game, the unified attack on one enemy is always more effective than dispersing attacks. From frames 1-3, agents have no target until one agent (at the end of the orange arrow) is close to an enemy (the bottom right corner). In frame 4, through the negotiation phase, that agent is chosen as the highest-level agent (level 5) since it has a better position to choose one enemy to attack. After lower-level agents obtained the actions of higher-level agents (illustrated by a white dashed line), all the red units ended their random roaming and instead launched a unified attack on the blue units.\n\n\nA similar behavioral pattern can also be observed in Frames 7-9.\n\n> Simpler aggregation methods.\n\nWe have done the ablation study as requested in Figure 1 (pdf in the global response). It turns out the attention mechanism performs better than a simpler aggregation method. The reason is simple aggregation the observations will expand the dimension input of the neural network. It will impair the learning process since high-dimension input may contain many irrelevant information [1]. However, the attention mechanism helps focus on more important information by learning different weights on different observations. \n\n[1] Learning individually inferred communication for multi-agent cooperation. NIPS 2020.\n\n> Attention mechanism learns meaningful patterns.\n\nWe have observed two patterns. One is upper-level agents will be highlighted since important actions are provided. Another is the agents that are far away will be overlooked. \n\n> How does the computational cost of the attention mechanism scale with the number of agents, especially in the full communication scenario?\n\nIn full communication scenarios, the computation cost increases linearly with the number of agents. \n\nIn the local communication scenarios, due to the limitation of the communication range, the number of local communicated agents will also be limited. Therefore, the communication cost has an upper bound.\n\n>More advanced attention mechanisms (e.g., multi-head attention).\n\nYes, it may help to process the incoming messages from other agents. However, since the main contributions are not from the attention mechanism, we did not spend too much time investigating this. However, how the attention mechanisms or transformers architecture influences the learning process is another high-profile line of research in RL.\n\n> How is the attention mechanism modified to handle the local communication scenario effectively?\n\nThe attention mechanism is originally used in natural language processing, where they are inherently capable of processing input of different lengths, just like recurrent neural networks.", "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": "58CunzuUk6", "reviewer": "Reviewer_gF4i", "summary": "This paper proposed a multi-level sequential communication framework that has two communication phases. It also proved that the policies learned in this way are guaranteed to improve and converge. Instead of the observations, this paper focus on make agents communicate about the action selections. Each agent is assigned a priority of decision-making first and an equilibrium is set up to be the learning objective for all agents working together.", "questions": "See the weakness section above.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper is well-written and well motivated, it borrows ideas from game theory and try to bring the equilibrium into multi-agent decision-making process.", "weaknesses": "1. If the authors formulate this problem as multi-agent sequential decision making problem, the Markovian property required for formulating the problem as an MDP is no longer satisfied and there is a need proving an alternative policy gradient theorem before simply inserting the Seqcomm into MAPPO.\n2. In Figure 2's caption, the authors stated that 'in the launching phase, the agents who hold the upper-level positions will make decisions prior to the lower-level agents. Besides, their actions will be shared with anyone that has not yet made decisions', then how to change the structure of MAPPO model to make it fit this change? And how to adjust the time step based on this change?\n3. There is no code available in this submission, the details of the models' structures could not be seen. The reproducibility remains unsure.\n4. Only comparing to TarMAC is not enough, this MARL with communication algorithm was proposed in 2019, there are more recent MARL communication algorithms outperforming TarMAC.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To begin with, we thank the reviewer for the carefully reviewing and insightful advice.\n\n>If the authors formulate this problem as a multi-agent sequential decision-making problem, the Markovian property required for formulating the problem as an MDP is no longer satisfied and there is a need to prove an alternative policy gradient theorem before simply inserting the Seqcomm into MAPPO.\n\nTo connect SeqComm and MAPPO while avoiding this problem, we build a new MDP $\\tilde{M}$ based on the original MDP $M$. The state space of $\\tilde{M}$ can be divided into multiple layers and the state transitions only occur between consecutive layers. The sequential decision-making process in the original MDP corresponds to a round of agent-by-agent decision-making process while the Markovian property of $\\tilde{M}$ is preserved. We show SeqComm in original MDP equals Agent-by-agent PPO in new MDP $\\tilde{M}$. More detailed discussions are included in Appendix A.\n\n>In Figure 2's caption, the authors stated that 'in the launching phase, the agents who hold the upper-level positions will make decisions prior to the lower-level agents. Besides, their actions will be shared with anyone that has not yet made decisions, then how to change the structure of the MAPPO model to make it fit this change? And how to adjust the time step based on this change?\n\nAssume there are two agents, in the original MAPPO, the police of each agent is p(ai|s) and the value function is v(s). In our setting, the second level agent’s policy is p(a2|s, $ \\emptyset $) and the value function is v(s, $ \\emptyset $), we change the structure of the first level agent, its policy is p(a1|s, a2) and value function is v(s, a2). Other training procedures are the same. In practice, we use communication channels to achieve information sharing. \n\nWe did not change the time step, since after all the agents make decisions, they execute the actions to interact with the environment simultaneously. Note that we did not break the fundamental dynamic, p(s’|s, a1,a2).\n\n>There is no code available in this submission, the details of the models' structures could not be seen. The reproducibility remains unsure.\n\nMany methods in communication-based MARL did not share the code, which makes the comparison very hard. We also do not like this trend, and we guarantee we will release the code as soon as this paper gets accepted. We also guarantee all the results can be reproduced. \n\n>Only comparing to TarMAC is not enough, this MARL with communication algorithm was proposed in 2019, and there are more recent MARL communication algorithms outperforming TarMAC.\n\nWe add more baselines as requested in Figure 3 (pdf in the global response). Note that many methods in communication-based MARL did not share the code, meaning many baselines cannot be compared fairly. We choose two baselines for comparison (CommFormer [1] and MAIC[2]) with two criteria, 1. Published in the recent top conference; 2. Release the code for a fair comparison. \n\nThe result shows that SeqComm still outperforms these baselines by a large margin. Surprisingly, we have tried our best to tuned the parameters under the limited timeline, but CommFormer (2024 baselines) still performs worsen than MAIC (2022 baselines). \n\n[1]. Learning Multi-Agent Communication from Graph Modeling Perspective. ICLR 2024\n\n[2]. Multi-Agent Incentive Communication via Decentralized Teammate Modeling. AAAI 2022", "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:
First of all, we are very grateful to the reviewers for their thorough review of our paper. We highly appreciate your valuable comments. We will emphasize the key points mentioned during the rebuttal period in the revised version. 

Additionally, we have provided some extra experiments: Figure 1 includes the attention module vs. the aggregation method; Figure 2 shows some behavioral analysis; Figure 3 shows the comparison with additional baselines.

Meta-review: This paper introduces a multi-level communication scheme named SeqComm for multi-agent reinforcement learning. SeqComm enables agents to coordinate asynchronously, with upper-level agents making decisions before lower-level ones. The approach involves two communication phases: negotiation and launching. In the negotiation phase, agents communicate hidden states to determine decision-making priority, while in the launching phase, upper-level agents lead in decision-making and share actions with lower-level agents. The paper provides a solid theoretical foundation with proofs for policy improvement and convergence. The paper is generally well-written and organized. The introduction clearly motivates the problem and contributions. The method section provides a detailed explanation of SeqComm. The approach offers an innovative solution to multi-agent coordination through multi-level communication, firmly grounded in Stackelberg Equilibrium theory. Regard to the contributions, I recommend to accept the paper.

In the rebuttal period, the authors claimed that “many methods in communication-based MARL did not share the code, meaning many baselines cannot be compared fairly”, but this statement was not true, e.g., the SARNet paper (Learning Multi-Agent Communication through Structured Attentive Reasoning, NeurIPS 2020) released their codes including lots of other baselines as well. Moreover, the statement is somehow contradicted to “we don't think code submission should be the core criterion for judging this paper”. If nobody makes their codes public, a lot of work would be (or even impossible) very difficult to be repeated. So, it would be much better that the authors could do what they said “We promise to publish the code”.
Decision: Accept (poster)