Multi-Agent Coordination via Multi-Level Communication

Authors: ziluo  ding
zeyuan  liu
zhirui  fang
kefan  su
liwen  zhu
zongqing  lu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 14:40:26

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.

Main paper: 
 introduction: 
 Centralized training with decentralized execution (CTDE) [Lowe et al., 2017] is a popular learning paradigm in cooperative 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 [Jiang et 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 et al., 2020] . It is impossible for an agent to acquire other'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 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 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 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, a coordination graph expresses a higherorder 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 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. 
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 are encouraged to create a 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 on a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem formulation: 
 Cost-Free Communication. The decentralized partially observable Markov decision process (Dec-POMDP) can be extended to 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 [a 1 , a 2 ] and [b 1 , b 2 ] that are equally optimal. Without any prior information, the individual policies π 1 and π 2 learned from the centralized critic can break the ties randomly and may choose a 1 and b 2 , 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 to as multi-agent sequential decision-making.At each timestep t, 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 o k t drawn from the state s t , and receives messages m -k t from all other agents, where m-k t ≜ {{o 1 t , a 1 t }, . . . , {o k-1 t , a k-1 t }, o k+1 t , . . . , o n t }. Equivalently, m -k t can be written as {o -k t , a 1:k-1 t },where o -k t denotes the joint observations of all agents except k (in practice, agents communicate the hidden states/encodings of observations), and a 1:k-1 t denotes the joint actions of agents 1 to k -1. For the agent at the first level (i.e., k = 1), a 1:k-1 t = ∅. Then, the agent determines its action a k t sampled from its policyπ k (•|o k t , m -k t ) or equivalently π k (•|o t , a 1:k-1 t) and sends it to the lower-level agents. After all, agents have determined their actions, they perform the joint actions A → 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.a t , which can be seen as sampled from the joint policy π(•|s t ) factorized asn k=1 π k (•|o t , a 1:k-1 t), in the environment and get a shared reward r(s t , a t ) and the state transitions to next state s ′ according to the transition probability p(s ′ |s t , a t ). All agents aim to maximize the expected return ∞ t=0 γ t r t , where γ is the discount factor. The state-value function and action-value function of the level-k agent are defined as follows:V π k (s, a 1:k-1 ) ≜ E s1:∞ a k:n 0 ∼π k:n a1:∞∼π [ ∞ t=0 γ t r t |s 0 = s, a 1:k-1 0 = a 1:k-1 ] Q π k (s, a 1:k ) ≜ E s1:∞ a k+1:n 0 ∼π k+1:n a1:∞∼π [ ∞ t=0 γ t r t |s 0 = s, a 1:k 0 = a 1:k ].For the setting of multi-agent sequential decision-making discussed above, we have the following proposition.Proposition 1. If all the agents update their policy with individual TRPO [Schulman et al., 2015] sequentially in multi-agent sequential decision-making, then the joint policy of all agents are 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-making in multi-agent sequential decision-making. However, the priority of decision-making indeed affects the optimality of the converged joint policy, and we have the following claim. Claim 1. The different priorities of decision-making affect the optimality of the convergence of the learning algorithm due to the relative overgeneralization problem.We use a one-step matrix game as an example, as illustrated in Figure 1 (a), to demonstrate the influence of the priority of decision-making on the learning process. Due to relative overgeneralization [Wei et al., 2018] , agent B tends to choose b 2 or b 3 . Specifically, b 2 or b 3 in the suboptimal equilibrium is a better choice than b 1 in the optimal equilibrium when matched with arbitrary actions from agent A. Therefore, 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 simultaneously and independently) are easily trapped into local optima. However, if agent A 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 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 In 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.EQUATIONguidance 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.Remark 1. The priority (i.e. order) of decision-making 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 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.Question: For each theoretical result, does the paper provide the full set of assumptions and a 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 crossreferenced. • 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 to provide a short proof sketch to provide intuition.• 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. 
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, 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 is designed based on this principle to determine the priority of decision-making via communication.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 explicit coordination via communication. The overview of SeqComm 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] .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 in 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, it shall have adequate information to estimate their actions since all agents are homogeneous and parameter-sharing. Therefore, the world model M(•) takes as input the joint hidden states h t = {h 1 t , . . . , h n t } and actions a t , and predicts the next joint observations and reward. In practice, before the inputs pass into the world model, the attention module AM w is utilized to process the input.ôt+1 , rt+1 = M i (AM w (h t , a t )).The reason that we adopt the attention module is to entitle the world model to be generalizable in the scenarios where additional agents are introduced or existing agents are removed.In the negotiation phase, the observation encoder first takes o t as input and outputs a hidden state h t 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 decision-making by intentions which is established and evaluated based on the world model.Priority of Decision-Making. Intention is the key element in determining the priority of decisionmaking. The notion of intention is described as an agent's future behavior in previous works [Rabinowitz et al., 2018 , Raileanu et al., 2018 , Kim et al., 2021] . However, we define the intention as an agent's future behavior without considering others.As mentioned before, an agent's intention considering 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. 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 it 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 i at timestep t to illustrate, it firstly considers itself as the first-mover and produces its action only based on the joint hidden states, âi t ∼ π i (•|AM a (h t , ∅), where we again use an attention module AM a to handle the input. For the order sequence of lower-level agents, we randomly sample a set of order sequences from unfixed agents. Assume agent j is the second-mover, agent i models j's action by considering the upper-level action following its own policy âj t ∼ π i (•|AM a (h t , âi t )). 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 ôt+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 τ t = {ô t+1 , ât+1 , . . . , ôt+H , ât+H } by repeating the procedure aforementioned.Then, the agent uses its critic (state-value function) to evaluate the future trajectory and output value v τ t . 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 communicate 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 is finally determined.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 a 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 can determine the upper-level and lower-level nearby agents. Unlike the previous version of SeqComm, agents cannot distinguish the detailed order sequence of the upper-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 it more suitable for many real applications.For more details of the algorithms, please refer to the Appendix D for the pseudo-code. a Policy o 3 t a 3 t a upper t = {a 1 t , a 2 t } Cri/c AM a Policy o 2 t a 2 t a upper t = {a 1 t } Cri/c AM a Policy o 1 t a 1 t a upper t = {} Cri/c r t+1 ô t+1 = { ô 1 t+1 , …, ô n t+1} a t = { a 1 t , …, a n t } h t = { h 1 t , …, h n t }First moverWorld ModelAM w h t = { h 1 t , …, h n t } ⋯ Figure 3: Architecture of SeqComm.The critic and policy of each agent take input as its own observation and received messages. The world model takes as input the joint hidden states and predicted joint actions.As for the launching phase, agents communicate 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 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 i make a decision following the policyπ i (•|AM a (h t , a upper t )), where a upper t means received actual actions from all upper-level agents. As long as the agent has decided on an action, it will send the action to all other lower-level agents through the communication channel. Note that the actions are executed simultaneously and distributedly in execution, though agents make decisions sequentially.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 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 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 timestep asmax t E s∼π β,t [D T V (p(s ′ |s, a)||p(s ′ |s, a))] ≤ ϵ m ,and the policy divergences at level k be bounded as max s,a1:k-1 D T V (π β,k (a k |s, a 1:k-1 )||π k (a k |s, a 1:k-1 )) ≤ ϵ π k ,where π β is the data collecting policy for the model and p(s ′ |s, a) is the transition distribution under the model. Then the model return η and true return η of the policy π are bounded as:η[π] ≥ η[π]- [ 2γr max (ϵ m + 2 n k=1 ϵ π k ) (1 -γ) 2 + 4r max n k=1 ϵ π k (1 -γ) ] C(ϵm,ϵπ 1:n ) .Proof. The proof is given in Appendix B.Remark 2. Theorem 1 provides a useful relationship between the compounding errors and the policy update. As long as we improve the return under the true dynamic by more than the gap, C(ϵ m , ϵ π1:n ), 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 will show in Section 5.2 that a random order sequence leads to a poor local optimum empirically. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it 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 to reproduce the main experimental 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 be 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 a 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 it 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 a 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 submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe 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 to have some path to reproducing or verifying the results. 
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 in the learning process. Therefore, no extra prior knowledge is provided. Please refer to the Appendix for the hyperparameter settings. All results are presented in terms of the mean and standard deviation of five runs with different random seeds.SMACv2. We have evaluated our method on the most representative and challenging multi-agent environment currently available. Compared with SMAC [Samvelyan et al., 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 if they are within the sight range. NDQ [Wang et al., 2020] adopts a similar change to increase the difficulty of action coordination. The rest of the settings remain the same as the default. In summary, we require the environment to be one where a high success rate cannot be achieved solely based on 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 of agents restrict the number of nearby agents. As the task progresses, the number of nearby agents is from 2 to 4.Analysis. The learning curves of SeqComm and the baselines in terms of the win rate are illustrated in Figure 4 . All communication-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 et al., 2019] , which holds a similar position in communication settings to that of MAPPO in communication-free settings. SeqComm outperforms TarMAC in all maps, which verifies the gain of explicit action coordination. Moreover, the full-communication version performs better than the local-communication version because the former can access more information. However, it also costs more communication overhead.Priority of Decision-Making. We primarily want to contribute a 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 to finding a good order is 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 as 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-making and the necessity to adjust it continuously during one episode. It is also demonstrated that SeqComm can provide a proper priority of decision-making. 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. It again verifies that a bad order may fail to improve coordination or even impair it. Communication Range. We also conduct experiments to demonstrate the impact of different communication ranges. We set communication ranges to {1, 3, 9}, in addition to the default range of 6. We notice a steady improvement in performance as the communication range increases. Therefore, the choice of communication range is a trade-off between communication overhead and agent performance. In our previous experiments, we choose a compromise value of 3 for the local version to validate the effectiveness of our method. Results refer to Figure 5 . Network Mechanisum. We replaced the attention mechanism for local communication with an 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 on the terran 10v10 map. The results refer to Figure 6 .Question: Does the paper provide open access to the data and code, with sufficient instructions 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 NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details.• While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 a 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 (e.g., deployment of technologies 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 not 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, it 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• Researchers should communicate the details of the dataset/code/model 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. • 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. 
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 a variety of cooperative multi-agent scenarios.Limitations. The assumption of accessing the local observation of any other agent could be strong since it is unsuitable for all applications. Thus, we provide a local communication version of SeqComm for assumption relaxation in the experiment.  
 
 Appendix: Lemma 1 (Agent-by-Agent PPO). If we update the policy of each agent i 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 L π old (π new ) where π old is the joint policy before updating and π new is the joint policy after updating.Given that π -i new = π -i old , we have:L π old (π new ) = E a∼πnew [A π old (s, a)] = E a∼π old [ π new (a|s) π old (a|s) A π old (s, a)] = E a∼π old [ π i new (a i |s) π i old (a i |s) A π old (s, a)] = E a i ∼π i old π i new (a i |s) π i old (a i |s) E a -i ∼π -i old [A π old (s, a i , a -i )] = E a i ∼π i old π i new (a i |s) π i old (a i |s) A i π old (s, a i ) = L π i old (π i new ),whereA i π old (s, a i ) = E a -i ∼π -i old [A π old (s, a i , a -i )]is the individual advantage of agent i, and the third equation is from the condition π -i new = π -i old . With the result of TRPO, we have the following conclusion:J(π new ) -J(π old ) ≥ L π old (π new ) -CD max KL (π new ||π old ) = L π i old (π i new ) -CD max KL (π i new ||π i old ) (from π -i new = π -i old )This means the individual objective is the same as the joint objective so the monotonic improvement is 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 = × n i=1 A i , where A i is the original action space of agent i. The new state space contains multiple layers. We define Sk = S × (× k i=1 A i ) for k = 1, 2, • • • , n -1 and S0 = S, where S is the original state space. Then a new state sk ∈ Sk means that sk = (s, a 1 , a 2 , • • • , a k ). The total new state space is defined as S = ∪ n-1 i=0 Si . Next we define the transition probability P as following:P (s ′ |s k , a k+1 , a -(k+1) ) = 1 s′ = (s k , a k+1 ) , k < n -1 P (s ′ |s k , a k+1 , a -(k+1) ) = 1 s′ ∈ S0 P (s ′ |s k , a k+1 ), k = n -1.This means that the state in the layer k can only transition to the state in the layer k + 1 with the corresponding action, and the state in the layer n -1 will transition to the layer 0 with the probability P in the original MDP. The reward function r is defined as following:r(s, a) = 1 s ∈ S0 r(s, 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 = { S, Ã, P , r, γ}.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 sequential decision-making in the original MDP M equals to a round of update from agent 1 to agent n by agent-by-agent PPO in the new MDP M . Moreover, the total reward of a 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 1, we complete the proof.The proof of Proposition 2 can be seen as a corollary of the proof of Proposition 1.Proof. From Lemma 1 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 policy. So even if the different round of updates in the new MDP M is with different order of the decision-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 to the monotonic improvement in the original MDP M . These complete the proof.Lemma 2 (TVD of the joint distributions). Suppose we have two distribution p 1 (x, y) = p 1 (x)p 1 (x|y) and p 2 (x, y) = p 2 (x)p 2 (x|y). We can bound the total variation distance of the joint as:D T V (p 1 (x, y)||p 2 (x, y)) ≤ D T V (p 1 (x)||p 2 (x)) + max x D T V (p 1 (y|x)||p 2 (y|x))Proof. See [Janner et al., 2019] (Lemma B.1).Lemma 3 (Markov chain TVD bound, time-varing). Suppose the expected KL-divergence between two transition is bounded as max t E s∼p1,t(s) D KL (p 1 (s ′ |s)||p 2 (s ′ |s)) ≤ δ, and the initial state distributions are the same p 1,t=0 (s) = p 2,t=0 (s). Then the distance in the state marginal is bounded as:D T V (p 1,t (s)||p 2,t (s)) ≤ tδProof. See [Janner et al., 2019] (Lemma B.2).Lemma 4 (Branched Returns Bound). Suppose the expected KL-divergence between two dynamics distributions is bounded as max t E s∼p1,t(s) [D T V (p 1 (s ′ |s, a)||p 2 (s ′ |s, a))], and the policy divergences at level k are bounded as max s,a 1:k-1 D T V (π 1 (a k |s, a 1:k-1 )||π 2 (a k |s, a 1:k-1 )) ≤ ϵ π k . Then the returns are bounded as:|η 1 -η 2 | ≤ 2r max γ(ϵ m + n k=1 ϵ π k ) (1 -γ) 2 + 2r max n k=1 ϵ π k 1 -γ ,where r max is the upper bound of the reward function.Proof. Here, η 1 denotes the returns of π 1 under dynamics p 1 (s ′ |s, a), and η 2 denotes the returns of π 2 under dynamics p 2 (s ′ |s, a). Then we have |η 1 -η 2 | = | s,a (p 1 (s, a) -p 2 (s, a))r(s, a)| = | t sD T V (π 1 (a -1 |s, a 1 )||π 2 (a -1 |s, a 1 )) + max s D T V (π 1 (a 1 |s)||π 2 (a 1 |s)) ≤ • • • ≤ n k=1 max s,a 1:k-1 D T V (π 1 (a k |s, a 1:k-1 )||π 2 (a k |s, a 1:k-1 )) ≤ n k=1 ϵ π k .We then apply Lemma 3, using δ = ϵ m + n k=1 ϵ π k (via Lemma 3 and 2) to getD T V (p 1,t (s)||p 2,t (s)) ≤ t max t E s∼p1,t(s) D T V (p 1,t (s ′ |s)||p 2,t (s ′ |s)) ≤ t max t E s∼p1,t(s) D T V (p 1,t (s ′ , a|s)||p 2,t (s ′ , a|s)) ≤ t(max t E s∼p1,t(s) D T V (p 1,t (s ′ |s, a)||p 2,t (s ′ |s, a)) + max t E s∼p1,t(s) max s D T V (π 1,t (a|s)||π 2,t (a|s))) ≤ t(ϵ m + n k=1 ϵ π k )And we also getD T V (p 1,t (s, a)||p 2,t (s, a)) ≤ t(ϵ m + n k=1 ϵ π k ) + n k=1 ϵ π kby Lemma 2. Thus, by plugging this back, we get:|η 1 -η 2 | ≤ r max t s,a γ t |p 1,t (s, a) -p 2,t (s, a)| ≤ 2r max t γ t (t(ϵ m + n k=1 ϵ π k ) + n k=1 ϵ π k ) ≤ 2r max ( γ(ϵ m + n k=1 ϵ π k )) (1 -γ) 2 + n k=1 ϵ π k 1 -γ )Then we can show the proof of Theorem 1.Proof. Let π β denote the data collecting policy. We use Lemma 4 to bound the returns, but it will require bounded model error under the new policy π. Thus, we need to introduce π β by adding and subtracting η[π β ], to get:η[π] -η[π] = η[π] -η[π β ] + η[π β ] -η[π].we can bound L 1 and L 2 both using Lemma 4 by using δ = n k=1 ϵ π k and δ = ϵ m + n k=1 ϵ π k respectively, and obtain:L 1 ≥ - 2γr max n k=1 ϵ π k (1 -γ) 2 - 2r max n k=1 ϵ π k (1 -γ) L 2 ≥ - 2γr max (ϵ πm + n k=1 ϵ π k ) (1 -γ) 2 - 2r max n k=1 ϵ π k (1 -γ).Adding these two bounds together yields the conclusion.Reinforcement Learning in Stackelberg Game Many previous studies [Könönen, 2004 , Sodomka et al., 2013 , Greenwald et al., 2003 , Zhang et al., 2020] have investigated reinforcement learning in finding Stackelberg equilibrium. Bi-AC [Zhang et 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 as the value-based 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 to dynamically determine the priority of decisionmaking 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 a given graph from their given start vertices to their given target vertices. However, we aim to find a communicationbased solution for any Markov decision process with interests aligned. MDP covers lots of possible coordination-needed scenarios, not just avoiding collisions. Besides, each agent has no specific given target.Motivation: In MAPF, prioritized planning does not offer completeness or optimality guarantees. It is nevertheless popular because of its efficiency. In addition, the order is mainly used for avoiding collision. Unlike MAPF, our main contribution is to introduce prioritized decision-making to MARL and a method to determine the priority of decision-making. To the best of our knowledge, determining the priority of decision-making for learning algorithms has not been investigated. Moreover, combining with learning algorithms will make prioritized decision-making more general (solving MDPs), not just motion planning.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 so 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.In this part, we provide the pseudo-code of SeqComm as below:Algorithm i = t+H t ′ =t+1 γ t ′ -t-1 rt ′ via the critic end for Compute the average return v = 1 F F i=1 v i Algorithm 3= {i | v i > v a , i ∈ N } Set lower-level neighbouring agents N lower = {i | v i < v a , i ∈ N } Algorithm 5v i = t+H t ′ =t+1 γ t ′ -t-1 rt ′ end for Compute the average return v = 1 F F i=1 v i viaOur models, including SeqComm and its ablations, are implemented based on 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 are 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, we use a fully connected layer to decode. In these layers, Tanh is used as the nonlinearity.SeqComm and its ablation baseline share the same hyperparameters. For Protoss, the learning rate is 1e -5 , while for Terran and Zerg, the learning rate is 2.5e -5 . 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] .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 AM w , agent i gets messages m -i t = h -i t from all other agents at timestep t in negotiation phase, and predicts a query vector q i t following AM i w,q (h i t ). The query is used to compute a dot product with keysk t = [k 1 t , • • • , k n t ].Note that k j t is obtained by the message from agent j following AM i a,k (h j t ) for j ̸ = i, andk i t is from AM i neg,k (h i t ). Besides, it is scaled by 1/ √ d k followed by a softmax to obtain attention weights α for each value vector:EQUATIONThe output of attention module is defined as:c i t = n j=1 α ij v j t, where v j t is obtained from messages or its own hidden state of observation following AM i w,v (•). As for AM in the policy and critic network denoted as AM a , 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 upper , 0], respectively. In addition, the query depends on agent's own hidden state of observation h i t , but keys and values are only from messages of other agents.• 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: 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”.

Reviews: review: paper_summary: paper_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:

1. A new asynchronous perspective on MARL, allowing agents to make decisions sequentially.
2. A two-phase communication scheme: negotiation phase for determining decision priorities, and launching phase for explicit coordination.
3. Theoretical guarantees of monotonic improvement and convergence for the learned policies.
4. Empirical evaluation on SMACv2 demonstrating superior performance over existing methods.
strength_weakness: strength_weakness: (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.
(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).
(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.
questions: 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?
(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?
(3) Can you provide an analysis of the computational complexity of SeqComm compared to existing methods, especially for large-scale multi-agent systems?
(4) How sensitive is SeqComm to the choice of hyperparameters, particularly F and H? Are there any guidelines for selecting these values?
limitations: 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.
However, there are several areas where the discussion of limitations could be expanded:

Scalability: The authors could further discuss how SeqComm's performance and computational requirements might change as the number of agents increases.
Generalizability: While SMACv2 is a valuable benchmark, the authors could address how well they expect their results to generalize to other MARL environments.
Potential 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.
Hyperparameter sensitivity: The authors could elaborate on how sensitive their method is to the choice of hyperparameters, particularly F and H.

Regarding 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The assumptions regarding local observations and communications might not be realistic for all applications.
questions: questions: None
limitations: limitations: refer to the "weaknesses" part.
paper_summary: paper_summary: This paper introduces SeqComm, a novel multi-level communication scheme for multi-agent coordination in reinforcement learning. The key contributions are:

1. A new approach treating agents asynchronously with two communication phases: negotiation and launching.
2. Theoretical analysis proving monotonic improvement and convergence of learned policies.
3. Empirical evaluation on StarCraft multi-agent challenge v2 (SMACv2) showing superior performance over existing methods.

The paper addresses the coordination problem in multi-agent settings by allowing agents to communicate actual actions and determine decision-making priorities dynamically.
strength_weakness: strength_weakness: - 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.
- 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.
- 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.
- While the paper addresses local communication, there's limited discussion on the trade-offs between communication frequency, accuracy, and overall system performance.
- 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.
- While TarMAC is a strong baseline, the paper could benefit from comparisons with more recent state-of-the-art methods in multi-agent communication.
questions: 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?
2. Have you explored the performance of SeqComm in heterogeneous agent scenarios where parameter sharing may not be applicable? 
3. How might the method be adapted for such settings?
4. 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?
5. 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?
6. 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?
7. How does the attention mechanism perform compared to simpler aggregation methods? An ablation study could illuminate this.
8. Does the attention mechanism learn meaningful patterns of inter-agent importance? Visualizing attention weights could provide insights into learned coordination strategies.
9. How does the computational cost of the attention mechanism scale with the number of agents, especially in the full communication scenario?
10. Could more advanced attention mechanisms (e.g., multi-head attention) provide further improvements?
11. How is the attention mechanism modified to handle the local communication scenario effectively?
limitations: 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.
- The heavy dependence on a world model could be a significant limitation in environments where accurate modeling is challenging or computationally expensive.
- While the paper addresses local communication, there's limited discussion on the trade-offs between communication frequency, accuracy, and overall system performance.
- 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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?
3. There is no code available in this submission, the details of the models' structures could not be seen. The reproducibility remains unsure.
4. 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.
questions: questions: See the weakness section above.
limitations: limitations: Yes.

Comments: comment: As stated in the authors' rebuttal, they formed a new MDP, and the formation of this new MDP necessitates the proof of the new alternative policy gradient theorem, which is currently absent in the manuscript. This proof is essential as it forms the foundational support for the proposed theorem. 

Additionally, the NeurIPS submission guidelines strongly recommend including code at the time of paper submission. The absence of accompanying code not only deviates from these guidelines but also undermines fairness, especially when compared to other submissions that included their codes. Therefore, I believe that my evaluation is justified and fair for this submission.
Thank you for your approval, we will revise the text in conjunction with the rebuttal.
Thank you for your approval, we will revise the text in conjunction with the rebuttal.
Thank you for your rebuttal that eliminates my concerns. I will increase my score to 7.
Thank you for your comprehensive rebuttal. Your explanations have effectively addressed my concerns and substantially improved my assessment of the paper. As a result, I have decided to increase my score to 7.

This decision is based on several key strengths of your work:

Your SeqComm approach offers an innovative solution to multi-agent coordination through multi-level communication, firmly grounded in Stackelberg Equilibrium theory. The method's robust performance on SMACv2, coupled with a clear analysis of its communication efficiency, demonstrates its practical value in complex MARL scenarios.

I am confident that your contribution has the potential to make a significant impact on the MARL field.
This paper aims to demonstrate SE is better than NE. In nature, under SE where agent makes decisions sequentially, parts of agents can obtain the extra information (actions of upper-level agents). Intuitively, if the agent has more valuable information, it will help make the decision. 

For other potential equilibrium, if it allows the agent to get extra valuable information and does not break the fundamental dynamic of the environment, it also can benefit the performance. 

Assumption issues. 
1. If information asymmetry which means communication is not allowed, then the SeqComm is degraded to MAPPO.

     If only parts of the information are asymmetrical, it will degrade to the local-communication version. 

2. In our view, we will recompute the decision-making order based on the current situation during the execution phase. It will ensure stability. 

3. When perfect information about other agents' strategies is not available, we can do the opponent modeling, in more detail, we can train a policy that predicts the actions of other agents. Since we can get the observations of others via communication, the opponent modeling can be precise.
Thank you for your suggestion. We will include the discussions about the new MDP in the main body of the paper and release the code. If you find our clarifications satisfactory, we kindly ask for your consideration in adjusting your scores accordingly.
I thank the authors for addressing my concerns, I like the idea that the code will be released. I suggest that the authors should include the discussions about the new MDP in the main body of the paper.
Thank you for the authors' comprehensive rebuttal and additional results. The response has indeed improved my view of the paper. However, I still have some concerns regarding the Stackelberg Equilibrium (SE) as the foundational assumption for agent coordination in the proposed SeqComm scheme.

Specific Points for Further Consideration:

Rationale for SE in MARL: While the authors have addressed the application of SE in SeqComm, I would appreciate a more rigorous justification for choosing SE over other potential equilibrium concepts. It would be beneficial to explore how SE compares to alternative concepts that may be more naturally aligned with the decentralized and dynamic nature of MARL environments. A comparative analysis highlighting the specific advantages of SE in this context would strengthen the paper's theoretical foundation.
Assumptions of SE: The paper assumes that agents can achieve and maintain an SE, which may not always be realistic in scenarios where agents have limited or imperfect information about others' strategies. I encourage the authors to discuss the robustness of their approach when these assumptions are violated. Specifically: a) How does the SeqComm scheme perform under conditions of information asymmetry?
b) What mechanisms, if any, are in place to ensure the stability of the SE in dynamic MARL environments?
c) How does the approach handle scenarios where perfect information about other agents' strategies is not available?
Thank you for the comment. We are willing to add a more extensive wall-clock comparison for the camera-ready version. We also guarantee that we will open-source the code upon acceptance, enabling reproducibility.
Thank you for the quick turn-around. If the authors are willing to add a more extensive wall-clock comparison for the camera-ready version, I'd be happy to improve my score to a 7.

A 7 expects a high impact on the community. I think this is justified as the authors provide convincing empirical and theoretical results that their proposed communication scheme is a valid research direction to pursue. The authors also claim to open-source the code upon acceptance, enabling reproducibility. Furthermore, the conceptual simplicity of the method in combination with the improved empirical results is usually a good indicator of impact. I think the 2x-3x wall-clock time is justifiable, especially with increasing computational efficiency of MARL environments. For example, SMAX provides a 40000x efficiency improvement over Smacv2 (33mins vs 44h) when training IPPO, which would make the 2x-3x slow down negligible [1]

[1] Rutherford, Alexander, et al. "Jaxmarl: Multi-agent rl environments in jax." arXiv preprint arXiv:2311.10090 (2023).
Thank you for your feedback. 

We are sorry we missed this important question. Since the training speed between protoss, terran, and zerg are very small within the same method, we take the results in protoss maps to illustrate the difference. 

SeqComm (full comm) fps (frame per second during training):

protoss 5v5: 64.32 10v10: 32.75 10v11: 29.82

SeqComm (local comm) fps:

protoss 5v5: 108.38 10v10: 64.03 10v11: 59.55

MAPPO fps:

protoss 5v5: 166\~167 10v10: 146\~147 10v11: 136\~137

Note that all results are tested on NVIDIA A100. 

Compared with MAPPO, we only need 2x to 3x the compute to achieve better results.
I thank the authors for the extensive rebuttal and running additional results. Your replies certainly improved my outlook on the paper.

One more weakness that I'd like your comment on is:
> 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.

I do not expect the wall-clock plots for each experiment, given that time is limited. However, I do believe it's an insightful comparison with baselines, as different communication techniques come with different computational costs. In the extreme, your method could take 100x the compute to achieve slightly better results. Alternatively, your method could be 100x faster, which would make the paper that much stronger. I agree that the ultimate metric is final training performance and wall-clock time is secondary, so this would not be a dealbreaker.