Multi-Agent Sequential Decision-Making via Communication
Authors: Ziluo Ding
Kefan Su
Weixin Hong
Liwen Zhu
Tiejun Huang
Zongqing Lu
Venue: Submitted to ICLR 2023 (2023)
Keywords: multi-agent communication
multi-agent reinforcement learning

Abstract:  Communication helps agents to obtain information about others so that better coordinated behavior can be learned. Some existing work communicates predicted future trajectory with others, hoping to get clues about what others would do for better coordination. However, circular dependencies sometimes can occur when agents are treated synchronously so it is hard to coordinate decision-making. In this paper, we propose a novel 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 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 launching phase, the upper-level agents take the lead in making decisions and 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 multi-agent cooperative tasks.


Under review as a conference paper at ICLR 2023
MULTI-AGENT SEQUENTIAL DECISION-MAKING VIA COMMUNICATION
Anonymous authors Paper under double-blind review
ABSTRACT
Communication helps agents to obtain information about others so that better coordinated behavior can learned. Some existing work communicates predicted future trajectory with others, hoping to get clues about what others would do for better coordination. However, circular dependencies sometimes can occur when agents are treated synchronously it is hard to coordinate decision-making. In this paper, we propose a novel 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 nego- by communicating
tiation phase, agents determine the priority of decision-make hidden states of observations and comparing the value of intention, which is ob- tained by modeling the environment dynamics. In launching phase, the upper-level agents take the lead in making decisions and 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 multi-agent cooperative tasks.
INTRODUCTION
The partial observability and stochasticity inherent to the nature of multi-agent systems can easily impede the cooperation among agents and lead to catastrophic miscoordination (Ding et al., 2020). Communication has been exploited to help agents obtain extra information during both training and execution to mitigate such problems (Foerster et al., 2016; Sukhbaatar et al., 2016; Peng et al., 2017). Specifically, agents can share their information with others via trainable communication channel.
Centralized training with decentralized execution (CTDE) is a popular learning paradigm in coop- erative multi-agent reinforcement learning (MARL). Although the centralized value function can 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 to avoid miscoordination. However, most existing work only focuses communicating messages, e.g., the information of agents' current observation or historical trajectory (Jiang & Lu, 2018; Singh et al., 2019; Das et al., 2019; Ding et al., 2020).
impossible for agent acquire other's actions before making decisions since the game model is usually synchronous, i.e., agents make decisions and execute actions simultaneously. Recently, intention imagination, depicted by combination of predicted actions and observations of many future steps. has been proposed as part of messages (Kim et al., 2021; Pretorius et al., 2021). However, circular dependencies can still occur, it may be hard to coordinate decision-making under synchronous settings.
general approach to solving the coordination problem is to make sure that ties between equally good actions are broken by all agents. One simple mechanism for doing so is to know exactly what others will do and adjust the behavior accordingly under a unique ordering of agents and actions (Busoniu al., 2008). Inspired by this, In other words, each agent is assigned a priority (i.e., order) of decision maainn each step in both training and execution, 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. Therefore, the lower-level agents can acquire the actual actions of the upper-level agents by
reconsider the cooperative game from asynchronous perspective.

---

Under review as a conference paper at ICLR 2023
communication and make their decisions conditioned on what the upper-level agents would do. 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 decide a specific priority of (recision-making for each agent? Ideally, the optimal joint policy can be decomposed by any orders (Wen al., 2019), e-g., πT" [a1,02) (2]s) xt [a1 (aa|s))" (ag 8, a1) xx" (aa) (sals)="" (a1l (s, 02). But during the learning process, it is unlikely for agents to use the optimal actions of other agents for gradient calculation, making it still vulnerable to the relative overgeneralization problem (Wei et al.,
2018). Overall, there is no guarantee that the above equation will hold in the learning process, thus ordering should be carefully concerned.
In this paper, we propose novel model-based multi-round communication scheme for cooperative MARL,, Sequential Communication (SeqComm), to enable agents to explicitly coordinate with each other. 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 are able to generate multiple predicted trajectories, called intention, by modeling the environmental dynamics and other agents' actions. addition, the priority of deeision-making is determined by communicating and comparing the corresponding values of agents' intentions. The value of each intention represents the rewards obtained by letting that agent take the upper-level position 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 decision-making and communicate their actual actions with the lower-level agents. Note that the actual actions will be executed simultancously in the environment without any changes.
SeqComm currently built on MAPPO (Yu et al., 2021). Theoretically, we prove the policies learned by SeqComm are guaranteed to improve monotonically and converge. Empirically, we evaluate SeqComm on set of tasks in multi-agent particle environment (MPE) (Lowe al., 2017) and StarCraft multi-agent challenge (SMAC) (Samvelyan et al., 2019). In all these tasks, we demonstrate that SeqComm outperforms prior communication-fres and communication based methods. 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-makinn for agents to develop better coordination.
2 RELATED WORK
Communication. Existing studies (Jiang & Lu, 2018: Kim et al., 2019; Singh et 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& & Lu, 2018) 8) and IC3Net (Singh et al., 2019) utilize gate mechanisms to decide when to communicate with other agents. Many works (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 al., 2020) only communicates with agents that are relevant and influential which are determined by causal inference. However, all these methods focus how exploit valuable information from current or past partial observations effectively and properly. More recently, some studies (Kim et al., 2021; Du et al., 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 a world model and communicate those with others. IS (Pretorius 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, i.e., predicted future trajectories.
Unlike these works, treat the agents from asynchronously perspective therefore circular dependencies can be naturally resolved. Furthermore, agents only send actions to lower-level agents besides partial observations to make sure the messages compact well informative.
Cuordination. 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
2

---

Under review as a conference paper at ICLR 2023
agents may break ties in different ways, and the resulting joint actions may be suboptimal. Coordina- tion graphs (Guestrin et al., 2002; Böhmer et al., 2020; Wang et al., 2021b) simplify the coordination when the global Q-function can be additively decomposed into local Q-functions that only depend on the actions of subset of agents. Typically, a coordination graph expresses a higher-order value decomposition among agents. This improves the representational capacity to distinguish other agents' effects on 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 selec- tion. 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 tics, other than the enhanced representational capacity of the local value function.
3 PROBLEM FORMULATION
Cost-Free Communication. The decentralized partially observable Markov decision process (Dec- POMDP) can be extended to explicitly incorporate broadcasting observations. The resulting model is called multi-agent POMDP (Olichoek et al., 2016).
Pynadath & Tambe (2002) showed that under cost-free communication, a joint communication policy that shares local observations each stage is optimal. Many studies have also investigated sharing local observations in models that are similar to multi-agent POMDP (Pynadath & Tambe, 2002: Ooi & Wornell, 1996; Nair et al., 2004; Roth et al., 2005a:b; Spaan et al., 2006; Olichock et al., 2007; Becker et al., 2004). These works focus on issues other than communication cost and we foues on the coordination problem. Note that even under multi-agent POMDP where agents can get joint observations, coordination problem can still arise (Busoniu et al., 2008). Suppose the centralized critic has learnt actions pairs [a1, a2] and [b,, b2] are equally optimal. Without any prior information, the individual policies Ti and सy learnt from the centralized critic can break the ties randomly and may choose 01 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 to the following procedure, which we refer 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 (i.e., 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 k gets its own observation of drawn from the state 8t, and receives messages m, k from all other agents, where m, A {{o], J......, : {ot 1 k 1), ++1 ...., of Equivalently, m, can be written as for -k 1:k- where o denotes the joint observations of all agents except k. and a, lik-1 denotes a. the joint actions of agents 1 to k- - 1. For the agent at the first level (i.e., k = 1), a, 1:k-1 = 2. Then, the agent determines its action at sampled from its policy Tu(-lo²; m,, or equivalently Tu(-lor, a, 1:6-1) and sends it to the lower-level agents. After all agents have determined their actions, they perform the joint actions a,, which can be seen as sampled from the joint policy т (-]ss) factorized as II ( or, a l.b-1), ), in the environment and get a shared reward r(st, az) and the state according the transition probability (68]|s,, a.). All agents aim to
state transitions maximize the expected return 20207"re where is the discount factor. The state-value function and action-value function of the level-k agent are defined as follows:
Va (3, a 1 A
r = 8, ab 1:k-1 = 1:k-
$1000 "
(s, )
E
2 relso s, a. = 1:k]
ag A+ wo a1ioo N
1=0
3

---

Under review as a conference paper at ICLR 2023
For the setting of multi-agent sequential decision decision-making discussed above, we have the following proposition.
Proposition 1. If all the agents update its policy with individual TRPO (Schulman al., 2015) sequentially in multi-agent sequential decision-making, then the joint policy of all agents is guaranteed to improve monotonically and converge.
Proof. The proof is given in Appendix A.
Proposition 1 indicates that SeqComm has the performance guarantee regardless of the priority of decision decision-making in multi- agent sequential decision decision-making. However, the priority of decision decision-making making indeed affects the optimality of the converged joint policy, and we have the following claim.
Claim 1. The different priorities of decision- affect the optimality of the convergence of the learning algorithm due to the relative overgeneralization problem.
We use one-step matrix game as an example, as illustrated in Figure ((a), to demonstrate the influence of the pri- ority of decision-making on the learn- ing process. Due to relative overgen- eralization (Wei et al., 2018), agent B tends to choose b2 or by. Specifically, b2 or by in the suboptimal equilibrium is better choice than d, in the opti- mal equilibrium when matched with arbitrary actions from agent A. There- fore, as shown in Figure 1(b), B + A (i.e., agent B makes decisions before A, and A's policy conditions on the action of B) and Simultaneous (i.e., two agents make decisions simultane- ously and independently) are easily trapped into local optima. However, things can be different if agent A goes first, A > B achieves the optimum. As long agent A does not suffer from relative overgen- eralization, it can help agent B get rid of local optima by narrowing down the search space of B. Besides, a policy that determines the priority of decision-making can be learned under the 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.
Agent B
12
bj
b2
by
11
Agent A
01
6
022
6
8
0
0g
0
(a) payoff matrix of the gume
evaluations of differrent methods
Figure I: (a) Payoff matrix for a one-step game. There are multiple local optima. (b) Evaluations of different methods for the game in terms of the mean reward and standard de- viation of runs. A + B, B + A, Simultaneous, and Learned represent that agent A makes decisions first, agent B makes decisions first, two agents make decisions simulta- neously, and there is another learned policy determining the priority of decision making, respectively. MAPPO (Yu et al., 2021) is used as the backbone.
The priority (i.e, order) of preiiion-mmainn affects the optimality of the converged joint policy in multi-agent sequential decision-making thus it is critical to determine the order. However, learning the order directly requires an additional centralized policy in execution, which is not generalizable in the 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.
4 SEQUENTIAL COMMUNICATION
In this paper, we cast our eyes in another direction and resort to the world model. Ideally. we can randomly sample candidate order sequences, evaluate 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 designed based on this principle to determine the priority of decision- makinn via communication.
SeqComm adopts multi-round communication mechanism, ie.,, agents are allowed to communicate with others in multiple rounds. Importantly, communication is separated into phases serving different purposes. 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 explicit coordination via communication. The overview of SeyComm is illustrated in Figure 2. Each SeqComm agent consists of a policy, a critic, and a world model, as illustrated in Figure 3, and the parameters of all networks are shared across agents (Gupta et al., 2017).
4

---

Under review as a conference paper at ICLR 2023
negotiation phase
Launchiing
Heartor
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 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.
4.1 NEGOTIATION PHASE
In the negotiation phase, the observation encoder first takes o input and outputs hidden state h which is used communicate with others. Agents then determine the priority of secision-making by intention which is established and evaluated based on the world model.
World Model. The world model needed to predict and evaluate future trajectories. SeqComm, unlike previous works (Kim al., 2021; Du et al., 2021; Pretorius et al., 2021). 1). 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 agent access other agents' hidden states, it shall have adequate information to estimate their actions since all agents homogeneous and parameter-sharing Therefore, the world model MM-) takes as input the joint hidden states h, = [h. hP) and actions a; and predicts the next joint observations and reward,
0:41, fz+1 (MM, (he, az)),
where AM is the attention module. The reason that we adopt the attention module is entitle the world model to be generalizable in the scenarios where additional agents are introduced or existing agents are removed.
Priority of Decision-Making. The intention the key element to determine the priority of decision-making. The notion of intention is de- scribed as an agent's 's future behavior in previous works (Rabinowitz et al., 2018: Raileanu et al., 2018; Kim et al., 2021). However, we define the intention an agent's future behavior without considering others.
Polkcy
Seord
14))
AM,
AM, World Model
As mentioned before, an agent's intention con- sidering others can lead to circular 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. How- ever, there are many possible future trajectories as the priority of the rest agents is unfixed. In practice, we use the Monte Carlo method to eval- uate intention.
Prtley
Citie
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.
Taking agent i at timestep to illustrate, it firstly considers itself as the first-moved and produces its action only based on the joint hidden states, á Tc(+AAM, (h+)), where again use
5

---

Under review as a conference paper at ICLR 2023
attention module AM, to handle the input. For the order sequence of lower-level agents, randomly sample a set of order sequences from unfixed agents. Assume agent j is the second-mover, agent models j's action by considering the upper-level action following its own policy af ~ T+(+)MM 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 0r4.1 and corresponding reward f14.1 can be predicted by the world model. The length of the predicted future trajectory is H and it can then be written as r' = {ōr+1: a1+1..... O Bs+Hl by repeating the procedure aforementioned and the value of one trajectory defined the return of that trajectory V/- = De=t+1 74 f fr/H H. addition, the intention value is defined as the average value of F future trajectories with different sampled order sequences. The choice of F is tradeoff between the computation overhead and the accuracy of the estimation.
After all the agents have computed their own intention and the corresponding value, they again communicate their intention values to others. Then agents would compare and choose the agent with the highest intention value to he the first-mover. The priority of lower-level decision-making follows the same procedure with the upper-level agents fixed. Note that some agents are required to communicate intention values with others multiple times until the priority of decision-makee maaiion is finally determined.
4.2 LAUNCHING PHASE
As for the launching phase, agents communicate for obtaining 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 others' actions by opponent modeling (Rabinowitz et al., 2018; Raileanu et al., 2018) or communicating intentions (Kim et al., 2021). Therefore, miscoordination can be naturally avoided and a better cooperation strategy is possible since lower-level agents can adjust their behaviors accordingly. A lower-level agent make decision following the policy x. (-IMM, (h,, a.pper)), where a, apppper means received actual actions from all upper-level agents. As long as the agent has decided its action, it will send its action to all other lower-level agents by the communication channel. Note that the actions are executed simultaneously and distributedly in execution, though agents make decisions sequentially.
Communication Overhead. Two communication phases alternate until all agents determine their levels and get upper-level actions. Note that many previous works also adopt the multi-round communication scheme (Das et al., 2019; Singh et al., 2019). As for implementation in practice, compared with communicating high-dimensionall hidden states/observations by multiple rounds (Das et al., 2019; Singh et al., 2019), or transferring multi-step trajectory (Kim et al., 2021), SeqComm needs more rounds, but it only transmits hidden states for one time. For the rest communication with total (n - 1) broadcasts per agent, only a single intention value and an action will exchanged. Considering there are nd! permutations of different order choices for r agents, our method has greatly reduced computation overhead since each agent needs to calculate up to times to search for a satisfying order. Although SegComm is more suitable for latency-toleras MARL tasks, e.g., power dispatch (minutes) (Wang al., 2021a), inventory management (hours) (Feng et al., 2021), maritime transportation (days) (Li et al., 2019), it is possible for SeqComm to have a wider range of applications given the rapid development of the communication technology, e.g., 5G.
round
4.3 THEORETICAL ANALYSIS
As the priority of decision-making is determined by intention values, SeqComm is likely 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 are independent of the priority of decision-making of agents at each timestep.
Proof. The proof is given in Appendix A.
The priority of decision-making is chosen under the world model, thus the compounding errors in the world model can result in discrepancies between the predicted returns of the same order under the

---

Under review as a conference paper at ICLR 2023
-0
(a) PP
(b)
(c) KA
Figure 4: Learning curves in terms of the mean reward averaged over timesteps of SeqComm and
baselines on three MPE tasks: (a) predator-prey, (b) cooperative navigation, and (c) keep-away.
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 1.
Let the expected total variation between two transition distributions be bounded at each ()lll(s
timestep max, E.- (PrV (p(ss a) [(sl((((sss)))))))))). a})] Em and the policy divergences at level
a a=) S txp where Ty is the data collecting policy for the model and p(s'|s is, a) is the transition distribution under the model. Then the model return and true return 1, of the policy π are bounded as:
k be bounded as 1 Drv ( (a
maxmmax
( (cm + + (x.) 4rmax Ek=1 CTa
π n/TT]
(1 7)²
(1 1-7)
O(mm:frim))
Proof. The proof is given in Appendix B.
Remark Theorem 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 егrоr 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 order sequence is almost the same random one. Though random order sequence also has the theoretical guarantee of Proposition 2, we will show in Section 5.2 that a random order sequence leads poor local optimum empirically.
EXPERIMENTS
Sequential communication (SegComm) is currently instantiated based on MAPPO (Yu et al., 2021). We evaluate SeqComm on three tasks in multi-agent particle environment (MPE) (Lowe et al., 2017) and four maps in StarCraft multi-agent challenge (SMAC) (Samvelyan al., 2019).
For these experiments, we compare SeqComm against the following communication-Fn and communication based baselines: MAPPO (Yu al., 2021), QMIX (Rashid al., 2018), IS (Kim et al., 2021), TarMAC (Das et al., 2019), and I2C (Ding et al., 2020). In more detail, IS communicates predicted future trajectories (observations and actions), and predictions model. TarMAC uses the attention model to focus more on important incoming messages (the hidden states of observations). TarMAC is reproduced based MAPPO instead of A2C in the original paper for better performance. 12C infers one-to-one communication to reduce the redundancy of messages (also conditioning on observations).
made by the environment
In the experiments, all the methods are grrameter-sharigg for fast convergence. We have fine-tuned the baselines for a fair comparison. Please refer to Appendix E for experimental settings and Appendix for implementation details. All results are presented in terms of the mean and standard deviation of five runs with different random seeds.
5.1 RESULTS
MPE. We experiment predator- erecytor-prey prey (PP), cooperative navigation (CN), and keep-away (KA) in MPE. In PP, five predators (agents) try to capture three prey. In CN, five agents try to occupy five landmarks. In KA, three attackers (agents) try occupy three landmarks, however, there are three
7

---

Under review as a conference paper at ICLR 2023
0.40
GecComm gr1b
SegCamm
SecComm
0.33
SeaComm
STD
0.4
0.1
1.12
6.25
0.25
3:00
6.35
(2) 6b.
(b) MMM2
(c) vs. 1m
(d) vx.
Figure 5: Learning curves in terms of the win rate of SeqComm and baselines on four customized SMAC maps: (a) 6h vs 8z, (b) MMM2, (c) 10m vs 11m, and (d) 8m vs 9m.
-10
-14
$-4.0
-20
-35
-1.9
-3.0
35
022
04
15
-22
5.
33
32
5-1
60
0.0
(a) PP
(b) CN
(c) KA
0:40
SeaCover
0.33
SeaCorm
Rec
ferdem
C
Funders
0.5
3.12
6:25
5:50
(() 87
(c) MMM2
(9) vs
(g) vx 9m
Figure 6: Ablation studies on the priority of decision-making in all the tasks. Fix-C: the priority of mecision is fixed throughout one episode. Random-C: the priority of decision-making is determined randomly. TarMAC is also compared as reference without explicit action coordination.
defenders to push them away. In all three tasks, the size of agents is set to be larger than the original settings so that collisions occur more easily, following the settings in (Kim et al., 2021). In addition, agents cannot observe any other agents, and this makes the task more difficult and communication more important. We can observe similar modifications in previous works (Foerster et al., 2016; Ding et al., 2020). After all, we want to demonstrate the superior over communication-bant based baselines, and communication-basee methods are more suitable for scenarios with limited vision. More details about experimental settings are available in Appendix E.
Figure shows the learning curves of all the methods in terms of the mean reward averaged over timesteps in PP, CN, and KA. We can see that SeqComm converges to the highest mean reward compared with all the baselines. The results demonstrate the superiority of SeqComm. In more detail, all communication-basel methods outperform MAPPO, indicating the necessity of communication in these difficult tasks. Apart from MAPPO, IS performs the worst since may access inaccurate predicted information due the circular dependencies. The substantial improvement SeqComm over 12C and TarMAC is attributed to that SeqComm allows agents to get more valuable action information for explicit coordination. The agents learned by SeqComm show sophisticated coordination strategies induced by the priority of decision-making which can be witnessed by the visualization of agent behaviors. More details are given Appendix C. Note that QMIX is omitted in the comparison for clear presentation since Yu et al. (2021) have shown QMIX and MAPPO exhibit similar performance in various MPE tasks.
SMAC. We also evaluate SeqComm against the baselines on four customized maps in SMAC: 6h.vs_82, MMM2, 10m_vs.1 Im, and 8m_vs 9m, where we have made some minor changes to the observation part of agents make it more difficult. Specifically, the sight range of agents is reduced from 9 to 2, and agents cannot perceive any information about their allies even if they are within the sight range. NDQ (Wang al., 2020) adopts similar change to increase the difficulty of action coordination and demonstrates that the miscoordination problem is widespread in multi-agent learning. The rest settings remain the same as the default.
8

---

Under review as a conference paper at ICLR 2023
The learning curves of SeqComm and the baselines in terms of the win rate are illustrated in Figure 5. and I2C fail in this task and get a zero win rate because these two methods are built on MADDPG. However, MADDPG cannot work well in SMAC, especially when reduce the sight range of agents, which is also supported by other studies (Papoudakis et al., 2021). SeqComm and TarMAC converge to better performances than MAPPO and QMIX, which demonstrates the benefit of communication. Moreover, SeqComm outperforms TarMAC, which again verifies the gain of explicit action coordination.
5.2 ABLATION STUDIES
Priority of Decision-Making We compare SegComm with two ablation baselines with only difference in the priority of decision-making the priority of secision-making is fixed throughout one episode, denoted as Fix-C, and the priority of decision-making is determined randomly each timestep, denoted as Random-C. TarMAC is also compared as a reference without explicit action coordination.
As depicted in Figure 6, SeqComm achieves higher mean reward or win rate than Fix-C, Random-C, and TarMAC in all the tasks. These results verify the importance of the priority of decision-making and the necessity to continuously adjust it during one episode. It is also demonstrated that SeqComm As discussed in Section 4.3, although Fix-C
can provide a proper priority of and Random-C also have the theoretical guarantee, they converge to poor local optima in practice. Moreover, Fix-C and Random-C show better performance than TarMAC in most tasks. This result accords with the hypothesis that the SE is likely to be Pareto superior to the average NE in games with high cooperation level. Additionally, the learned policy of SeqComm can generalize well to the same task with different number of agents in MPE, which is detailed in Appendix C.
Communication Range. We also carry out ablation studies on communication range in MPE tasks. Note that communication range means how many nearest neighbors each agent is allowed to communicate with, following the setting in Ding et al. (2020). We reduce the communication range of SeqComm from 4 to 2 and O. As there only three agents in KA, it is omitted in this study. The results are shown in Figure 7. Communication- based agents perform better than communication-Fin agents, which accords with the results of many previous studies. More importantly, the superiority of SeqComm with communication range 2 over the corresponding TarMAC again demonstrates the effectiveness of sequential communication even in reduced communication ranges.
However, as the communication range decreases from 4 to 2, there is no perfor- mance reduction in these two MPE tasks, On the contrary, the agents with com- munication range 2 perform the best. It accords with the results in I2C (Ding et al., 2020) and ATOC (Jiang & Lu, 2018) that redundant information can impair the learning process sometimes. In other settings, this conclusion might not be true. Moreover, since under communication scheme agents can ob- tain more information, i.e., the actual actions of others, it is more reasonable that SeqComm can still outperform other methods in reduced communication ranges.
-10
-10
-12
-12
-14
-14
-18
-20
-22
Stop
107
-tpp
207
(n) PP
(b) CN
Figure 7: Ablation studies on reduced communication
range in (a) predator-prey and (b) cooperative navigation.
CONCLUSIONS
We have proposed SeqComm, which enables agents explicitly coordinate with each other. SeqComm from an asynchronous perspective allows agents to make decisions sequentially. two-phase communication scheme has been adopted for determining the priority of decision-making and communicating messages accordingly. Theoretically, we prove the policies learned by SeqComm are guaranteed to improve monotonically and converge. Empirically, it is demonstrated that SemComm outperforms baselines in a variety of cooperative multi-agent tasks and SeqComm can provide a proper priority of decision-making.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Raphen Becker, Shlomo Zilberstein, Victor R. Lesser, and Claudia V. Goldman, Solving transition independent decentralized markov decision processes. Artif. Intell. Res., 22:423 455, 2004.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning (ICML), 2020.
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. In Conference Theoretical Aspects of Rationality and Knowledge, 1996.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprchensive survey of multiagent reinforcement learning. JEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156-172 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.
Mingxiao Feng, Guozi Liu, Li Zhao, Lei Song, Jiang Bian, Tao Qin, Wengang Zhou, Houqiang Li, and Yin Liu. Multi-agent reinforcement learning with shared resource in inventory management. 2021.
Felix Fischer, Michael Rovatsos, and Gerhard Weiss. Hierarchical reinforcement learning in cattuuuiicatin-mmmitttt multiagent coordination. In International Joint Conference on Au- tonomous Agents and Multiagent Systems (AAMAS), 2004.
Jakob Foerster, Joannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Amy Greenwald, Keith Hall, and Roberto Serrano. Correlated q-learning. In A comprehensive survey of multiagent reinforcement learning, 2003.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In International Conference 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 Muiriagent Systems (AAMAS), 2017.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. In Advances 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 Machine Learning (ICMI., 2019.
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. In 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 multi-agent reinforcement learning. In International Conference Learning Representations (ICIR), 2019.
10

---

Under review as a conference paper at ICLR 2023
Woojun Kim, Jongeui Park, and Youngchul Sung. Communication in multi- reinforcement learning: Intention sharing. In International Conference on Learning Representations (ICLR), 2021.
Sachin Konan, Esmaeil Seraj, and Matthew Gombolay. Iterated reasoning with mutual information in cooperative and byzantine decentralized teaming. International Conference on Learning Representations (ICLR), 2022.
Ville Könönen. Asymmetric multiagent reinforcement learning. Web Intelligence and Agent Systems: An international journal, 2(2):105-121, 2004.
Xihan Li, Jia Zhang, Jiang Bian, Yunhai Tong, and Tie-Yan Liu. cooperative multi aulti-agent rein- forcement learning framework for resource balancing in complex logistics network. arXiv preprint arXiv: petp:/903000110 14, 2019.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent comppettiveeo environments. In Advances in Neural Information
actor-critic for mixed Processing Systems (NeurIPS), 2017.
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.
Ranjit Nair, Milind Tambe, Maayan Roth, and Makoto Yokoo. Communication for improving policy computation in distributed pomdps. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2004.
Frans A. Oliehoek, Matthijs T. J. Spaan, and Nikos A. Vlassis. Dec-pomdps with delayed communi- cation. In AAMAS Workshop on Mulli-agent Sequential Decision Making in Uncertain Domains, 2007.
Frans A Oliehoek, Christopher Amato, al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
J.M. Ooi and G.W. Wornell. Decentralized control of a multiple access broadcast channel: perfor- mance bounds. In IEEE Conference Decision and Control, 1996.
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks, 2021.
Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent pitirrectiinallycooddnaaaaa nets: Emergence of human-level coordination in learning to play starcraft combat games. arXiv preprini arXiv: 1703. 10069, 2017.
MV Nagendra Prasad, Victor R Lesser, and Susan Lander. Learning organizational roles for negotiated search in a multiagent system. International Journal of Human- Human-Computer Computer Studies, 48 (1):51-67, 1998.
Arn Pretorius, Scott Cameron. Andries Petrus Smit, Elan van Biljon, Lawrence Francis, Femi Azee7, Alexandre Laterre, and Karim Beguir. Learning to communicate through imagination with model-based deep multi-agent 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.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder de Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference Machine Learning (ICMI.), 2018.
11

---

Under review as a conference paper at ICLR 2023
Maayan Roth, Reid Simmons, and Manuela Veloso. Decentralized communication strategies for coordinated multi-agent policies. In Lynne E. Parker, Frank E. Schneider, and Alan C. Schultz (eds.), Multi-Robot Systems. From Swarms Intelligent Automata Volume III. Springer, 2005a.
Maayan Roth, Reid G. Simmons, and Manuela M. Veloso. Reasoning about joint beliefs for execution- time communication decisions. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2005b.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philiph H. S. Torr. Jakob Foerster, and Shimon Whiteson. The StarCraft Ageti-Agent Challenge. arXiv preprint arXiv: 090. 0902.00443, 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 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.
Matthijs T. Spaan, Geoffrey Gordon, and Nikos Vlassis. Decentralized planning under uncertainty for teams of communicating agents. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2006.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropagation. In Advances Neural Information Processing Systems (NeurIPS), 2016.
Jur P Van Den Berg and Mark H Overmars. Prioritized motion plamning for multiple robots. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2005.
Nikos Vlassis. A concise introduction multiagent systems and distributed artificial intelligence.
Synthesis Lectures on Artificial Intelligence and Machine Learning, 1(1):1-71, 2007.
Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010.
Jianhong Wang, Wangkun Xu, Yunjie Gu, Wenbin Song, and Tim C Green. Multi-agent reinforcement learning for active voltage control on power distribution networks. Advances in Neural Information Processing Systems (NeurIPS), 2021a.
Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decomposable value functions via communication minimization. International Conference on Learning Representation (ICLR), 2020.
Tonghan Wang, Liang Zeng, Weijun Dong, Qianlan Yang, Yang Yu, and Chongjie Zhang. Context- aware sparse deep coordination graphs. arXiv preprint arXiv:2/06.0288 028866 2021b.
Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. In AAAI Spring Symposium Seriex, 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, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.0199 2021.
Haifeng Zhang, Weizhe Chen, Zeren Huang, Minne Li, Yaodong Yang, Weinan Zhang, and Jun Wang. Bi-level actor-critic for multi-agent coordination. In AAAI Conference on Artificial Intelligence (AAAT), 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.
12

---

Under review as a conference paper at ICLR 2023
A PROOFS OF PROPOSITION 1 AND PROPOSITION 2
Lemma (Agent-by-Agent 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 's policies, then the joint policy will improve monotonically.
Proof. We consider the joint surrogate objective in TRPO TuT (Teww) where Vold the joint policy before updating and new is the joint policy after updating.
- Given that new oldd we have:
Lota (Tnew)
Eg Waww
[ (s,
new (a|s)
E aald
A ATooI (s, a)l
Told (a
new (a'ls)
Bawward wold
A Amara (8, a)]
Told (a*l
Fnew (a'ls)
E aua
18, a- -n-iiaa [Amoa Aaraaal,,aa (s,a',
Tnia (a*1s)
Fnow
Egg Ba
A (s)
Tota (a'ls)
Tiriin (Tnew):
where A = E [Amasa (s, a-) is the individual advantage of agent i, and the third equation is from the condition nhew Told"
With the result of TRPO, have the following conclusion:
J (enww) ) J ((Toa)) 2 L CDKL (Tnewl Tola)
(Tiew)
KL (# (Fee I (from Tnew oold
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 a new MDP M based on the original MDP. We keep the action space À A = x At, where A is the original action space of agent The new state space contains multiple layers. We define 5* S (x) for 1, state space. Then new state z S means that g* (s, at a2, a,.... ... ,a*). The total new state space defined as S up- 5t. Next we define the transition probability P as following:
n and S S, where S is the original
P( t+1 a -(++)) = 1 (3' -55 ())) k < n -
P( ht1 a ((41))) = 1 (3' E 55)) P( a ,2)) k n 1
This means that the state in the layer k can only transition the state in the layer i + 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:
7(5 a) 1 (3 50) a)).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, nh.
Then we claim that if all agents learn in multi-agent sequential decision-making by PPO, they actually taking agent-by-agent PPO in the new MDP M. To be precise, one update of multi-agent
13

---

Under review as a conference paper at ICLR 2023
sequential decision decision-making making in the original MDP M equals round of update from agent agent by agent-by-agont PPO in the new MDP M. Morcover, the total reward of round in the new MDP M is the same the reward in one timestep in the original MDP M. With this conclusion and Lemma 1, we complete the proof.
The proof of Proposition 2 can be seen corollary of the proof of Proposition 1.
Proof. From Lemma I we know that the monotonic improvement of the joint policy in the new MDP M is guaranteed for each update of one single agent's 's policy. So even if the different round of updates in the new MDP M is with different order of the recision-making the monotonic improvement of 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 the monotonic improvement in the original MDP M. These complete the proof.
B PROOFS OF THEOREM 1
Lemma 2 (TVD of the joint distributions). Suppose we have two distribution pı(2,y)
Pi (r()p (xly) and p2(2.,) (2()))2(x)1)) We can bound the total variation distance of the joint as:
(zv Wllp v)) z (rv(o((=))l><(=)) + max (
Proof. See (Janner et al., 2019) (Lemma B.I).
Lemma 3 (Markov chain TVD bound, time-varing). Suppose the expected KL-divergence between two transition is bounded as max, e(sp),(s)) DKL (P1(s')p (p2 S 6, and the initial state distributions are the same Ps))= = p2.==0(8) Then the distance the state marginal bounded
Drv (pI, t5
Proof. See (Janner et al., 2019) (Lemma B.2).
Lemma 4 (Branched Returns Bound). Suppose the expected Kl-ddvergence between two dynamics distributions is bounded as max, Ev-pr..s)|PVv( s, a) P2((') a))], and the policy diver-
gences at level & are bounded as max (T s, a lsk [a a (s, S Cn Then the returns are bounded as:
17 - 1-11 2mmax + Ei Cxs)
+ 2rmax Σi= Exe
7}2
where Tmax is the upper bound of the reward feward function.
Proof. Here, 7n denotes the returns of π under dynamics pr (s'1s, a), and n2 denotes the returns of n2 under dynamics pa(s'ls. (s, a). Then we have
Im 72 Σ (s) a) -=)(s,
r' (P),, (
Σ (lm,,(s, (s,((s)))r(ss0
Tuax ΣΣ Ml,,, a) p2, a)).
14

---

Under review as a conference paper at ICLR 2023
By Lemma 2, get
max max maxxDrv(n((aa)))cp((a))))) S max Drv (T (ma(aa"ls, "|s,a')) a)))
0,1
max
Drv (m))
( 1-k-1 ( (/ ls,aak 1)
max
Emaa
We then apply Lemma using 8 = cm + Ex==1 Eop (via Lemma 3 and 2) to get
Drv(on,())lla..
max Earp Drv (1))p
S max Exp Drv a als))
& tmmax E (ampLa(s) Drv (0n a) 122
+ max Eompials) max Dr
$ t(Em +
And also get (rv(pI,(ss, a)llp,,((ss0)) t(Em Ek=1 Cxx) E k== Cre by Lemma 2. Thus, by plugging this back, we get:
M1
72l
S T mmax
-P2,((,,))
5,a
2fmax Σ (tlem + Σ ExC Exc)
km
76m + +E Gre))
Σ k=
CTp
2mmax
+
(1-
7
Then we can show the proof of Theorem
1.
Proof. Let F denote the data collecting policy. We use Lemma 4 to bound the returns, but will require bounded model error under the new policy æ. Thus, we need introduce ny by adding and subtracting 7| 3, to get:
Í| n/m]] = -[[ n| + n| n|-]].
we can bound L1 and L2 both using Lemma 4 by using å = Σn ETT and 6 = cm + Σb ET respectively, and obtain:
L1 2 2yTmmax En CT max ΣR CTe
(1 7)
(1 717)
+ Em (TT)
2rmax Ek= CTa (1-7)
L2
7)-
Adding these two bounds together yields the conclusion.
15

---

Under review as a conference paper at ICLR 2023
Jevil
leve
lovel
apent g
agent
lesed
level
lesel
agent
agert
Iovel
losal
lsoal 1
lowl
lovel
level
level
Figure 8: Illustration of learned priority of decision making in PP (upper panel) and CN (lower panel). Preys (landmarks) are viewed in black and predators (agents) are viewed in grey PP (CN). From to e, shown is the priority order. The smaller the level index, the higher priority of decision-making is.
Table 1: Mean reward in different tasks, averaged over timesteps, with 200 test trials.
Fix-C
SeqComm
3-agent in CN
-0.83 +0.17
-0.76 #0.08
7-agent in CN
-1.79
#0.15
-1.57 #0.10
7-agent PP
-1.89 10.45
-1.31 10.60
C ADDITIONAL EXPERIMENTS
C.I ILLUSTRATION OF LEARNED PRIORITY OF DECISION-MAKING
Figure 8 (upper panel from e) shows the priority order of decision-making determined by SeqComm in PP. Agent 2 that is far away from other preys and predators is chosen to be the first- mover. If agents want to encircle and capture the preys, the agents (e.g., agent 2 and 5) that are on the periphery of the encireling circle should hold upper-level positions since they are able to decide how narrow the encirclement. addition, agent 3 makes decisions prior to agent that collision can be avoided after agent obtains the intention of agent 3.
For CN, as illustrated Figure 8 (lower panel from a to e), agent 2 far away from all the landmarks and all other agents are in a better position occupy landmarks. Therefore, agents 2 is chosen to be the first-mover, which is similar to the phenomenon observed in PP. Once it has determined the target to occupy, other agents (agent and 3) can adjust their actions accordingly and avoid conflict of goals. Otherwise, if agent makes a decision first and chooses to occupy the closest landmark, then agent has approach to a further landmark which would take more steps.
C.2 GENERALIZATION
Generalization to different numbers agents has always been key problem in MARL. For most algorithms in communication, once the model is trained in one scenario, it is unlikely for agents to maintain relatively competitive performance other scenarios with different numbers of agents. However, employ attention modules process communicated messages that agents can handle messages of different lengths. addition, the module used to determine the priority of decision-makin is also not restricted by the number of agents. Thus, investigate whether SeqComm generalizes well to different numbers of agents in CN and PP.
For both tasks, SeqComm is trained 5-agent settings. Then, test SeqComm in 3-agent and 7-agent settings of CN and 7-agent setting of PP. We use Fix-C trained directly on these test tasks to illustrate the performance of SeqComm. Note that the quantity of both landmarks and preys is
16

---

Under review as a conference paper at ICLR 2023
1.0
1.0
SeqComm
SeqComm
TarMAC
TarMAC
0.8
Random-C
0.8
Random-C
0.6
0.6
0.4
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.8
1.0
step
1e7
step
1e7
(a) vs. 42
(b) comidor
Learning curves in terms of the win rate of SeqComm and baselines on two customized SMAC maps: (a) 4z, (b) corridor.
Figure 9:
adjusted according to the number of agents in CN and PP. The test results are shown in Table 1. SeqComm exhibits the superiority in CN and PP, demonstrating that SeqComm may have good generalization to the number of agents. A thorough study of the generalization of SeqComm is left to future work.
C.3
MORE SMAC MAPS
We have evaluated our method two additional maps, i.e., 3s_vs_4z and corridor. As illustrated in Figure 9, we can find out the similar conclusions as section 5.1.
D ADDITIONAL RELATED WORK
Multi-Agent Path Finding (MAPF). MAPF aims to plan collision-free paths for multiple agents on given graph from their given start vertices target vertices. In MAPF, prioritized planning is deeply coupled with collision avoidance (Van Den Berg & Overmars, 2005; Ma et al., 2019), where collision is used design constraints heuristics for planning. Unlike MAPF, our method couples the priority of decision-make with the learning objective and thus is more general. In addition, the different motivations and problem settings may lead to the incompatibility of the methods in the two fields.
Reinforcement Learning Stackelherg Game Many studies (Könönen, 2004; Sodomka et al., 2013; Greenwald et al., 2003; Zhang et al., 2020) have investigated reinforcement learning in finding the Stackelberg equilibrium. Bi-AC (Zhang et al., 2020) a bi-level actor-critic method that allows agents to have different knowledge bases that the Stackelberg equilibrium (SE) is possible to find. The actions still can be executed simultaneously and distributedly. It empirically studies the relationship between the cooperation level and the superiority of the SE over the Nash equilibrium. AQL (Könönen, 2004) updates the Q-value by solving the SE in each iteration and can be regarded the value-based version of Bi-AC. Existing work mainly focuses on two-agent settings and their order is fixed in advance. However, the fixed order can hardly be optimal solution as we will show in the next section. To address this issue, we exploit agents' intentions dynamically determine the priority of maaiing along the way of interacting with each other.
E EXPERIMENTAL SETTINGS
In cooperative navigation, there are 5 agents and the size of each is 0.15. They need to occupy landmarks with the size of 0.05. The acceleration agents is 7. In predator-pre prey, the number of predators (agents) and prey is set
and 3, respectively, and their sizes are 0.15 and 0.05. The acceleration is 5 for predators and 7 for prey. keep away, the number attackers (agents) and defenders is set to 3, and their sizes respectively 0.15 and 0.05. Besides, the acceleration is
17

---

Under review as a conference paper at ICLR 2023
Table 2: Hyperparameters for predator-prey, cooperative navigation, keep-away
Hyperparameter
SeqComm Random-C Fix-C TarMAC
12C
IS
discount (r)
0.95,0.95.0.95
batch size
800
1024
huffer capacity
1e
number of processes
16,16,16 1e-5,
learning rale
1.5e
1e- le
1e
1e-
H
10,10,20
F
2,
for attackers and 4 for defenders. The three landmarks are located at (0.00, 0.30), (0.25,-0.15) 00115). and (-0.25, 0.15). Note that each agent is allowed to communicate with all other agents in all three tasks. The team reward is similar across tasks. At a timestep
can be written as r'smm Ei= di Coollliiion where dž is the distance of landmark/prey i to its nearest agent/predator, is the number of collisions (when the distance between two agents less than the sum of their sizes) occurred at timestep f, and Fcollision = -. In addition, agents act discretely and have 5 actions (stay and move up, down, left, right). The length of each episode is 20, 30, and 20 in cooperative navigation, predator-prey, and keep-away, respectively.
F IMPLEMENTATION DETAILS
F.1 ARCHITECTURE AND HYPERPARAMETERS
Our models, including SeqComm, Fix-C, and Random-C are trained based MAPPO. The critic and policy network are realized by two fully connected layers. As for the attention module, key, query, and value have one fully connected layer each. The size of hidden layers is 100. Tanh functions used as nonlinearity. For 12C, we use their official code with default settings of basic hyperparameters and networks. As there is released code of IS and TarMAC, we implement IS and TarMAC by ourselves, following the instructions mentioned in the original papers (Kim et al., 2021; 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 48, and the output size for the action encoder 16. Then the outputs of the encoder will be passed into the attention module with the same structure aforementioned. Finally, we use a fully connected layer to decode. these layers, Tanh is used as the nonlinearity.
Table 2 summarize the hyperparameters used by SeqComm and the baselines the MPE.
For SMAC, SeqComm, Random-C, Fix-C are based the same architecture, the hyperparameters stay the same, For MMM2, 6z_vs_8z, and 8m_vs_9m the learning rate is 5e 5e-5, while for 10m_vs. _s_ll Im, corridor, and 3s_vs_4z, learning rate is 7e The ppo_epoch is set to 10 for 6/_os_8z, and is 5 for rest maps. H and F is set to 5 and 1, respectively. However, 20 and 2 is a better value of and computing resources is sufficient.
For TarMAC, the learning rate is -5 5 for all maps. The ppo_epoch is set to 10 for _2_ and is 5 for rest maps.
For MAPPO, the learning rate is 5e for MMM2 and 6z vs 8z, and 7e 5 for 8m vs 9m and 10m vs. 1mm.
For these four methods, the mini batch set to 1. As for other hyperparameters, we follow the default settings of the official code (Yu al., 2021).
55-5, For QMIX, the learning rate is 5e 5 The e is 1 and the batch size 32. The buffer size is 5e?. For others, follow the default settings of link
18

---

Under review as a conference paper at ICLR 2023
F.2 ATTENTION MODULE
Attention module (AM) is applied to process messages in the world model, critic network, and policy network. AM consists of three components: query, key, and values. The output of AM is 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 in the world model denoted as AMw. agent gets messages m h,," from all other agents at timestep t in negotiation phase, and predicts query vector oj following AM (k.). The query used to compute a dot product with keys k = [k2
kr]. Note that ky is obtained by the message from agent following A (h4) for j * i, and ky is from AM n (ht). Besides, it is scaled by 1/vdg followed by softmax obtain attention weights a for each value vector:
q k d
kF
a2 = softmax
(1)
dg
dd
The output of attention module defined as: cf Σ}=1 Oisy of. where oy is obtained from messages or its hidden state of observation following (-).
As for AM the policy and critic network denoted as AM, agent 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,
apper = | upper aj upperr] and m = [h fower Oj, respectively. In addition, the query depends agent's own hidden state of observation hi, but keys and values only from messages of other agents.
F.3 TRAINING
The training SeqComm is an extension MAPPO. The observation encoder e, the critic V, and the policy are respectively parameterized by 0,, 6.. fz. Besides, the attention module AM, is parameterized by 9, 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:
V(AM,(c(0), (pper)) -Rll" APl??
C(O.. 0g. 0e)
Σ
KT
where R is the discount rewards-to-go
We update the policy by maximizing the PPO-Clip objective:
ग (M a upper))
0c)
min
A Axass g(e, Anaa))
(3)
KT
Tota AM, (c(o), a ()pper))
TED
(1+c)) c)A
A 2
where g(e, A)
and A (o, a upper a) is computed using the GAE method.
()
0
The world model M is parameterized by 0.n is trained as a regression model using the training data set S. It updated with the loss:
C(O
1
Σ
(ddr)) - M(AMM
(4)
S
o,a.
We trained our model on one GeForce GTX 1050 Ti and Intel(R) Core(TM) 19-9900K CPU @ 3.60GHz.
19


Reviews:
[{"review_id": "bwhMLuIRJc", "reviewer": "Reviewer_7QwV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies a multiagent POMDP and proposes a communication mechanism for the agents to exchange information about their decision-making. In the process, the agents have the same objective, aiming to find a joint policy that maximizes their utility. The authors introduced a communication mechanism for the agents, which consists of a negotiation phase and a lauching pahse. In the negotiation phase, the agents communicate their observations, and in the lauching pahse, they communicate their decision-making. The latter is further implemented according to a hierarchical structure, where the agent at each level k send information to the agent at level k+1. The paper prents both theoretical results about the convergence of the agents' strategies to an equilibrium and empirical results about the performance of the proposed approach.", "summary_of_the_review": "In summary, a well presented paper with an interesting key idea and comprehensive results. Though the advantages of the proposed approach are a bit unclear compared with centralized decision-making (see Weaknesses) and require more justifications. ", "strength_and_weaknesses": "Strengths: \n\nThe problem is well-motivated. The paper is overall clearly writen and well organized. The idea of introducing communication into the process is natural and the proposed approach of hierarchical communication is also novel and looks interesting.\n\nWeaknesses: \n\nThough the idea of hierarchical communication is interesting, it is unclear what are its advantages compared with letting one agent makes a centralized decision and broadcasting the decision (especially now that the agents' objectives are the same and their policy space is already broken down through factorization).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "N0BX5bYXqQx", "reviewer": "Reviewer_TanN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a novel communication scheme, Sequential Communication (SeqComm), for cooperative multi-agent reinforcement learning (MARL).\nIn communication for cooperation in MARL, circular dependencies can sometimes occur. This is caused by synchronization in communication. The proposed model assumes asynchronous communication. The upper-level agents make decisions before the lower-level ones.\nThey, theoretically, show that policies learned by SeqComm are\nguaranteed to improve performance monotonically and converge. Also, the empirical performance is shown by comparing the proposal with other existing methods.", "summary_of_the_review": "The paper proposes a new communication method, SeqComm, for multi-agent reinforcement learning.\nThey provide not only empirical results but also theoretical proof as well. \nThe paper is properly written. ", "strength_and_weaknesses": "Strength\n+ The theoretical proof is provided. \n+ The performance is empirically shown in the experiment.\n\nI think the title does not sufficiently represent this paper's main characteristics. \"Asynchronicity\" seems to be the keyword of the paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LxHdm5d5FU1", "reviewer": "Reviewer_emu3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "## Summary\nThe paper presents SeqComm, a multi-agent communication scheme allowing agents to condition on one another's actions by imposing ordering over the agents. The paper introduces multi-agent sequential decision and demonstrates that ordering in this paradigm can affect the optimality of the learnt policy. \n\nThe authors then present SeqComm. Each agent in SeqComm learns a policy which conditions on the joint hidden state and other agents' actions via an attention mechanism. The ordering is chosen by weighing the value of each agent's intention, which is the paper defines as the agent's future behaviour without considering the action of others. In the second phase of communication, the agents the produce a joint action. The authors then prove that monotonic improvement of the policy is independent of priority, and provide a bound on the performance loss associated with using a world model for the ordering.\n\nThe authors then evaluate SeqComm on MPE and SMAC tasks.", "summary_of_the_review": "Although some communication is no doubt useful in MARL, requiring that functions of the observation can be broadcast to all allies does not seem to be decentralised execution to me. Additionally, I remain unconvinced by the empirical results both in their breadth and performance difference. ", "strength_and_weaknesses": "## Strengths\n- The setting of adding some communication to CTDE is an interesting way to alleviate miscoordination and work in this area is welcome. \n- The paper is quite clearly written.\n- The authors include ablation studies to evaluate why their method works.\n- The matrix game in Figure 1 nicely illustrates why an order is theoretically useful. \n\n## Weaknesses\n\n- I'm not sure that I understand the setting. If agents can broadcast functions of their observations to all other agents, then how is that different from joint learning, where all agents can view the same joint observation? This seems to not be the CTDE setting at all to me, but instead joint learning. I understand that TarMAC [1] adopts a similar setting, but I would appreciate some clarification from the authors on how this differs from joint learning.\n- The communication-free baselines MAPPO and IPPO are not a fair comparison, and it is not clear that SeqComm's performance is better TarMAC or the random-priority ablation. The authors claim that their method clearly outperforms the ablations and TarMAC, but the gap is only slight and seems to be mostly within a standard deviation. \n- The authors do not compare with a centralised method such as PPO (but conditioning the policy on the joint observation and outputting the joint action). This seems strange given this is an obvious alternative to the method, and would require approximately the same communication.\n- The empirical evaluation is only over 4 SMAC maps, and no further results are included. This does not seem enough to provide convincing evidence of outperformance.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "37S6Z4sjRWD", "reviewer": "Reviewer_44Uf", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors present a sequential communication framework to address the relative overgeneralization problem in multi-agent reinforcement learning and test it against a number of communication-free and communication-based baselines. Performance figures drawn against the number of training steps show higher average rewards in the MPE and SMAC environments.", "summary_of_the_review": "Major concerns raised above render SeqComm borderline faulty. I find it unlikely that additional experiments, clarification, and/or proofs would make the paper suitable for this venue.", "strength_and_weaknesses": "Introducing sequential decision making may prove both a valuable and feasible approach to some MARL tasks.\n\nHowever, the domain on which the proposed algorithm would successfully operate seems largely exaggerated. The underlying game-theoretic construct of MARL tasks should most definitely considered as a given, and not as a control knob. Whether a game will play out sequentially or simultaneously is -- at least within the approach and scope of building a novel MARL algorithm -- the innate characteristic of the game and not a choice for the algorithm designer. SeqComm may function correctly in MARL tasks that naturally and inherently involve sequentiality, but such a demonstration is missing. This lack significantly undermines the applicability of the algorithm.\n\nEven if there is some justification as to the applicability of SeqComm on arbitrary MARL tasks, the performance gain comes at a huge cost of communicating n-1 rounds. Actual performance may deteriorate from this best case (n-1 rounds), as \"some agents are required to communicate intention values with others multiple times until the priority of decision-making is finally determined.\" Furthermore, each of those rounds involves Monte Carlo sampling. This means that every single tick in the x-axis (steps) actually involves, at best n-1 \"sub-steps\", each of which carries out Monte Carlo sampling. Since every figure in the paper is plotted against the number of training steps, not a single figure pictures a fair comparison between SeqComm and the baselines.\n\nMoreover, the paper needs a much better foundation in terms of its connection to game theory. Simultaneous games are prone to non-stationarity precisely because the players' information sets are limited. Making a distinction between the decision-making phase and the action execution phase does not change the fact SeqComm alters information sets. There is no discussion whatsoever in this regard (e.g., information sets, bounded rationality, non-stationarity), and SeqComm proceeds straight to interfere with the players' information sets, which are dictated by the nature of the game and not by the algorithm's working mechanism.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject