Multi-Agent Decision S4: Leveraging State Space Models for Offline Multi-Agent Reinforcement Learning

We would like to thank the reviewer for their thorough technical review. We are glad that the reviewer finds our S4-based offline MARL approach novel and beneficial.

Comment 1

The choice of environments (RWARE and SMAC) does not sufficiently test the generalizability of MADS4. These benchmarks are widely used but do not fully capture the complexity of real-world multi-agent tasks. Testing in environments with higher-dimensional state spaces or dynamic agent interactions (e.g., more heterogeneous teams or real-time strategy games) would provide stronger evidence of scalability and robustness.

Response Thank you for this feedback. Offline MARL algorithms heavily rely on pre-collected offline datasets which are typically available and easy to collect in existing MARL benchmark environments, and therefore most (if not all) offline MARL algorithms are evaluated across these well-established environments. In our work, we therefore also compared our performance against state-of-the-art offline RL-based and transformer-based supervised-learning-based offline MARL algorithms across these domains. Additionally, we are working on experiments on the challenging Multi-Agent MuJoCo HalfCheetah-v2 domain to extend the scope of our evaluation and test our algorithm's effectiveness in continuous action control tasks. S4 models have been shown to outperform transformers in continuous control domains (e.g., single-agent Mujoco), and we anticipate that S4-based MADS4 would also outperform or perform on par with transformer-based models like MADT and MADTKD, even though their performance in continuous control tasks has also not been reported to our knowledge.

Comment 2

The paper mainly compares MADS4 to transformer-based models. However, given the growing body of work in MARL using other architectures like graph neural networks (GNNs) or attention mechanisms that directly model agent interactions, it would be valuable to include comparisons to such baselines.

Response Thank you for this suggestion. Our work focuses on developing an offline MARL algorithm within the sequence-to-sequence supervised learning paradigm. As a result, the most relevant benchmarks for comparison are transformer-based offline MARL algorithms, such as MADT and MADTKD, which also aim to learn policies in offline supervised learning settings. While graph-based algorithms are often employed in MARL to effectively model agent communication, they are primarily designed for online RL scenarios. Since no graph-based offline MARL baselines are currently available, we have not included them in our comparisons with MADS4.

Comment 2

Insufficient Analysis of Sequential Dependencies

Response In the SE-MDP framework used in this work, information sharing is needed only between consecutive agents, and each agent cooperates with its preceding agent in the sequence to take better cooperative actions. By sharing information based on the hidden state representation of the S4 model which essentially accumulates information about previous agents in the sequence, an agent does not need to communicate with all the previous agents, but just its immediate predecessor, thus allowing for a scalable communication mechanism. Thus, this communication mechanism can be performed in constant O(1) communication memory overhead, since any agent needs to communicate with only one other agent; and still achieve bi-directional cooperative behavior with the entire team since the memory representation holds information of all its preceding agents and gradients are backpropagated from the agents ahead of the agent in the sequence. This communication mechanism induces a recurrent sequential flow of information between agents, resulting in a linear worst-case complexity of $O(M)$ for the last agent in the sequence, where $M$ is the number of agents. However, by employing a simple adjustment—passing the previous agent's hidden state from the previous timestep instead of the current updated hidden state—we can enable fully decentralized policies across agents. This modification removes the need for sequential, recurrent communication, thereby eliminating the linear $O(M)$ time complexity. Furthermore, leveraging S4-based models enables per-agent inference to be performed in constant memory and time, offering a significant advantage over attention-based transformer models like MADT and MADTKD, which incur quadratic runtime relative to the sequence length.

As mentioned above, MADS4 can be adapted for fully decentralized settings with a minor adjustment to how memory information is shared. Instead of accessing the current timestep's memory from the previous agent in the sequence, each agent uses the memory information of the previous agent from the previous timestep. This approach allows all agents to take actions in parallel, as the required memory information from the previous timestep is already available when making decisions at the current timestep.

Comment 3

The focus on S4 models without considering the possible limitations of these models (such as their effectiveness in high-dimensional continuous action spaces) reduces the generality of the conclusions. Additionally, the paper does not explore whether there are settings where transformers might outperform S4, such as tasks that require more flexible attention mechanisms.

Response Thank you for this insightful comment. Our work builds on the demonstrated success of S4-based models over transformer-based Decision Transformers in single-agent tasks (Decision S4 by Shmuel et al, 2023). This motivated our decision to leverage S4-based models within the SE-MDP framework for scalable cooperative multi-agent tasks. S4 models have consistently outperformed transformers in continuous control domains (e.g., single-agent Mujoco), and we anticipate that S4-based MADS4 would either outperform or perform on par with transformer-based models like MADT and MADTKD, even though their performance in continuous control tasks has not been reported to our knowledge. The key advantage of S4-based models lies in their parameter efficiency and computational scalability. For example, our best-performing model achieves superior performance while using only 12% of the parameters of MADTKD. Moreover, S4 enables constant-time and memory-efficient inference, unlike transformers, which scale quadratically with sequence length. These strengths make S4 particularly suited for our focus on scalable and efficient multi-agent reinforcement learning.

Comment 4 How does the sequential dependency between agents in SE-MDP affect performance in environments that require real-time parallel actions from all agents? Would MADS4 struggle in such settings, and if so, how could it be adapted?

Response Thank you for this comment. MADS4 can be adapted for fully decentralized settings with a minor adjustment to how memory information is shared. Instead of accessing the current timestep's memory from the previous agent in the sequence, each agent uses the memory information of the previous agent from the previous timestep. This approach allows all agents to take actions in parallel, as the required memory information from the previous timestep is already available when making decisions at the current timestep.

Comment 5 Have you considered testing MADS4 in environments with more dynamic interactions, such as continuous control tasks or real-world applications (e.g., autonomous driving, resource allocation)?

Response Thank you for this comment. S4 models have been shown to outperform transformers in continuous control domains (e.g., single-agent Mujoco), and we anticipate that S4-based MADS4 would also outperform or perform on par with transformer-based models like MADT and MADTKD, even though their performance in continuous control tasks has also not been reported to our knowledge.

Comment 6 How does MADS4 compare to architectures like graph neural networks, which are also designed for multi-agent cooperation? It would be beneficial to see a comparison with GNN-based approaches to understand the specific advantages of S4.

Response Thank you for this suggestion. Since our work focuses on developing an offline MARL algorithm within the sequence-to-sequence supervised learning paradigm, the most relevant benchmarks for comparison are transformer-based offline MARL algorithms, such as MADT and MADTKD, which also aim to learn policies in offline supervised learning settings. While graph-based algorithms are often employed in MARL to effectively model agent communication, they are primarily designed for online RL scenarios. Since no graph-based offline MARL baselines are currently available, we have not included them in our comparisons with MADS4.

Comment 7 Given that the S4 model relies on long-term dependencies, what are the trade-offs in using S4 over transformers in tasks with varying sequence lengths? Would transformers perform better in environments with shorter sequences or fewer agents?

Response Thank you for this insightful comment. Our findings indicate that S4-based MADS4 excels in handling longer contexts, as evidenced by its significantly better performance than transformer-based MADTKD on the RWARE environment, where trajectories span 500 timesteps. Notably, MADS4 achieves this superior performance while utilizing only 12% of the model size of MADTKD.

In the SMAC domain, where the longest trajectories (e.g., in the Corridor map) are limited to 100 timesteps, the performance gap between MADS4 and MADTKD narrows. We observed that reducing trajectory lengths leads to performance drops for both S4-based and transformer-based models. However, no consistent pattern emerged to suggest that MADS4 underperforms compared to MADT in shorter-context scenarios.

Comment 8 Can you provide more intuition or formal analysis regarding the gradient flow between agents in SE-MDP? How does this contribute to stability, and why does it improve learning compared to other methods?

Response Thank you for this helpful feedback. In response, we have shown a more formal analysis of information flow in our SE-MDP framework in manuscript lines 233-253. Each agent’s memory, represented by the hidden state of its S4 module, encodes information about all prior agents in the sequence. A projection of this latent state, $h^t_{i-1}$, is passed as input to the next agent along with other inputs $\hat{u}^t_i$, influencing its action $a_i^t$ and its memory $h_{i}^t$:

$a_i^t, h_i^t = \pi_i ( \hat{u}_i^t, h^t_j ; \theta_i)$

where $j=i-1$

During training, gradients flow backward through the shared latent states, enabling the entire system to learn cooperative strategies:
$\frac{\partial J}{\partial \theta_i} = \frac{\partial J}{\partial a_i^t} \cdot \frac{\partial a_i^t}{\partial \theta_i} + \frac{\partial J}{\partial a_{i+1}^t} \cdot \frac{\partial a_{i+1}^t}{\partial h_i^t} \cdot \frac{\partial h_i^t}{\partial \theta_i}.$

Here, $J$ represents the supervised loss function computed across all agents in the system. This sequential flow of information eliminates the need for an agent to communicate with more than one peer or identify useful collaborators, a challenge that grows with the number of agents.

We sincerely thank the reviewer for their valuable feedback. Following the clarifications and revisions made to address their comments and suggestions, we kindly request the reviewer to consider revising their score. We remain open and eager to address any further comments or feedback.

Dear Reviewer Ntod, Could you please read the authors' rebuttal and give them feedback at your earliest convenience? Thanks. AC

Comment 2

The paper introduces the setting of a Sequentially Expanded MDP, which implies a sequential structure in the decision-making process. Why limit the proposed algorithm to this setting? This requires justification. Additionally, how do you determine the order of agents? Is it done randomly, since your test cases do not have a predefined order?

Response Thank you for this feedback and insightful questions. Our proposed algorithm MADS4 remains applicable under the setting of MADT, which is a transformer-based sequence-to-sequence offline MARL algorithm, where agents are trained independently. However, we have utilized the Sequentially Expanded MDP setting to incorporate scalable cooperation among the S4-based agents, where communication is limited to only consecutive agents in the sequence. This setting results in our model's better performance over the independent setting where the agents are trained independently. Utilizing the hidden state of the S4 module of the current agent, information on all its prior agents is efficiently passed down to the next agent, and gradients of the agents later in the sequence are also backpropagated during training. Even though this communication mechanism induces a sequential flow of information over the sequence of agents, it eliminates the need for an agent to communicate with more than one agent in the system or to identify useful peers, which becomes challenging as the number of agents grows. Typical communication-based MARL algorithms scale poorly with the number of agents; as the memory required during training and execution becomes exceedingly large and scales quadratically with the number of agents. On the other hand, the utilized communication mechanism in our work is relatively scalable requiring only constant memory since any agent only needs information of the previous agent in the sequence.

The order of the agents is decided randomly during training and execution. We have evaluated the effect of the order of agents on the performance by comparing two training settings of MADS4: 1) Random Order: where the order of the agents is randomly generated during training, and 2) Fixed Order: where the agents are trained in the fixed order in which the offline dataset is collected. The results in Figure 8 in Appendix Section C.4 show very little to no difference in performance between the two settings, which indicates MADS4 is robust to the order of agents in the SE-MDP framework.

Comment 3

Another major concern is the information sharing with limited communication. This assumes that an agent can communicate with the previous agent who just made a decision. This is already a strong form of coordination and should not be assumed to come freely. Could you provide real-world examples where this is applicable? And how the agents could acheieve this?

Response Thank you for this comment. MARL with limited communication typically assumes agents sharing information with their useful peers in the system. This poses significant scalability challenges since the identification of useful peers for each agent becomes challenging as the number of agents grows. Moreover, typical algorithms show both training and execution communication memory scaling poorly with the number of agents. In our work, utilizing the hidden state of the S4 module of the current agent in the proposed SE-MDP framework, information on all its prior agents is efficiently passed down to the next agent, and gradients of the agents later in the sequence are also backpropagated during training. Even though this communication mechanism induces a sequential flow of information over the sequence of agents (which can be eliminated by following a small modification as indicated below), it eliminates the need for an agent to communicate with more than one agent in the system or to identify useful peers. Thus, the utilized communication mechanism in our work is relatively scalable requiring only constant memory since any agent only needs information of the previous agent in the sequence.

MADS4 can also be adapted for fully decentralized settings with a minor adjustment to how memory information is shared. To achieve a fully decentralized MARL setting, instead of accessing the current timestep's updated memory from the previous agent in the sequence, each agent uses the memory information of the previous agent from the previous timestep. This approach allows all agents to take actions in parallel, as the required memory information from the previous timestep is already available when making decisions at the current timestep. Since memory accumulates over multiple timesteps, relying on the previous timestep's information does not compromise performance, as demonstrated in Figure 10 in Appendix C.6. This simple modification enables our algorithm to function effectively in decentralized policy settings without performance degradation.

We sincerely thank the reviewer for their critical feedback which helped us improve our paper. Below, we have provided our responses to the comments and suggestions.

Comment 1

The motivation for using S4 instead of a transformer does not fully convince me. The paper claims, “Existing transformer-based approaches for offline MARL either train agents independently, without fully considering them as a multi-agent system, or rely on a centralized transformer model, which suffers from scalability issues.” However, the proposed method also requires the global environment state, and it seems to require the global environment state even during execution (This is strong requirement!)! Then when does your method scale with respect to the number of agents? This needs further clarification.

Response Thank you for this comment. Let us clarify here how our proposed method compares against transformer-based methods in terms of scalability. The existing literature on offline MARL based on transformers typically involves training agents independently (MADT) where, each agent is trained independently on its own sequence of observations, actions and desired returns. Another transformer-based method MADTKD aims to incorporate cooperation among agents by learning a centralized teacher model which requires information from all the agents involved in the problem and distills individual agent policies from this teacher model using knowledge distillation. Learning the centralized teacher is not scalable with an increasing number of agents as it introduces a quadratic computational overhead in the attention mechanism due to inter-agent interactions during training. In both of these methods, global environment state variables are used as inputs to the transformer models. Moreover, the global environment state is a fixed-size input which may not pose scalability issues with respect to the number of agents. To analyze the effect of using the global state variable, we have run results without passing the global state variable as input, and the results do not show a significant drop in performance. We show this ablation in Figure 9 in the Appendix section C.5.

We also want to clarify why we chose S4-based models over traditional transformers, particularly within the SE-MDP framework. S4-based models offer several advantages over transformers, including parameter efficiency (as shown below), the ability to handle longer context lengths, and faster inference times. In contrast to the quadratic runtime of transformers with respect to sequence length, S4 models operate with asymptotic constant time and memory. In addition to these advantages, the S4 model is associated with inherently learning an internal (hidden) state or memory. In our SE-MDP framework, we uniquely leverage this memory to facilitate limited communication between agents, where each agent only needs to access information from its immediate predecessor, shared through its S4-based latent state.

Thank you to the authors for their detailed responses. However, the responses still do not fully address my concerns. My biggest concern remains the information sharing mechanism. While this mechanism is feasible in the SE-MDP setting, it may not be feasible for more general scenarios. The authors should propose a way to ensure that agents can (even approximately) obtain these hidden states from other agents. Passing a hidden state from the previous decision-making agent to the next should not come for free! Are there real-world examples where you could automatically achieve this sequential information sharing pattern?And your proposed decentralized version is not really fully decentralized, It still needs access to other agent's hidden states. I view the SE-MDP not as a setting but as a strong requirement of the algorithm. I think this is limiting, and I am not convinced by the proposed approach. With its current form, I think the paper should not be accepted to ICLR.

Response

We would like to clarify again that our proposed algorithm falls in the category of multi-agent learning with limited communication. Algorithms in this category enable some form of information sharing among agents, whether through observations, actions, memory, or other means. For example, many MARL works with communication (e.g., Sainbayar et al., 2016; Foerster et al., 2016; Ma et al., 2024; Guan et al., 2022; Wang et al., 2020) allow agents to access the observations of other agents. In the ACE paper (Li et al 2023), they allow the sharing of actions between agents. In a concurrent work (“Shared Memory for Multi-agent Lifelong Pathfinding”) also falling under this category, the agents are allowed to access a shared memory buffer containing the memory information of all the agents in the problem for making decisions.

In our work, we develop an offline MARL algorithm based on S4 under the paradigm of multi-agent learning with communication. Here, we focus on utilizing the concise S4 hidden state representation or memory of only one agent to be accessed by another agent in the system. Importantly, our work is not constrained to the sequential execution MDP (SE-MDP) framework. Agents can also access the memory information of a peer agent from the previous timestep, which is already available when making decisions at the current timestep. This mechanism supports decentralized decision-making, eliminating the need for a strictly sequential flow of information. As shown in Figure 10, accessing a peer agent’s memory from the previous timestep does not negatively impact performance. The S4 models’ ability to effectively capture long-context memory ensures that the memory from the previous timestep serves as a highly reliable proxy for the current timestep. This allows our framework to maintain its efficacy while facilitating decentralized decision-making while maintaining minimal communication overhead.

Our method remains largely applicable in practical settings where communication can be allowed while making decisions. Examples include traffic junction control [1], combat tasks [1], and infrastructure management planning [7], where the states of the agent components are almost always available and can be used for better system performance. MADS4 leverages the inference efficiency of S4-based models and utilizes a fixed-size, concise memory representation derived from S4 latent states. This design enables constant time and memory requirements per agent during the decision-making process, ensuring scalability and efficiency.

[1] Sukhbaatar, Sainbayar, and Rob Fergus. "Learning multiagent communication with backpropagation." Advances in neural information processing systems 29 (2016).

[2] Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, volume 29, 2016.

[3] Ma, Chengdong, et al. "Efficient and scalable reinforcement learning for large-scale network control." Nature Machine Intelligence (2024): 1-15.

[4] Guan, Cong, et al. "Efficient multi-agent communication via self-supervised information aggregation." Advances in Neural Information Processing Systems 35 (2022): 1020-1033.

[5] Tonghan Wang, Jianhao Wang, Chongyi Zheng, and Chongjie Zhang. Learning nearly decomposable value functions via communication minimization. In Proceedings of the International Conference on Learning Representations, 2020b.

[6] Li, Chuming, et al. "Ace: Cooperative multi-agent q-learning with bidirectional action-dependency." Proceedings of the AAAI conference on artificial intelligence. Vol. 37. No. 7. 2023.

[7] Leroy et al., "IMP-MARL: A Suite of Environments for Large-Scale Infrastructure Management Planning via MARL," Advances in Neural Information Processing Systems 36, 2024

We have revised the manuscript to better clarify the positioning of our algorithm within the existing literature. We hope this discussion addresses the reviewer's concern and convinces them to reconsider their evaluation. We would be happy to address any additional feedback.

We sincerely thank the reviewer for their thoughtful feedback and for acknowledging the originality of our work in implementing S4 for offline multi-agent tasks. Below, we have provided our responses to the comments and suggestions.

Comment 1

The reviewer has some concerns about the experimental results presented in the paper. Specifically, only one sequence-based baseline (MADT) is used, and the improvements demonstrated by the proposed method over this baseline are relatively small, with some falling within confidence intervals. To strengthen the experimental section, the reviewer suggests comparing the proposed method with more competitive baselines o, such as [a], which have been reported to achieve better results on SMAC than MADT. This would provide a more convincing demonstration of the effectiveness of the proposed method.

Response We would like to thank the reviewer for this comment and suggestion. While we would like to compare the performance of MADS4 against MADTKD, there is no public codebase/ reported performance available for MADTKD for us to evaluate MADTKD on some of these SMAC maps. However, we have compared our performance with MADTKD in the challenging RWARE domain in Table 1. This domain has been demonstrated in prior literature to be particularly challenging due to its longer context lengths of 500 timesteps (in contrast to the maximum trajectory length of 100 timesteps encountered in the SMAC Corridor domain) and higher-dimensional observations. In this setting, MADS4 significantly outperforms MADTKD.

Comment 2

The reviewer found some technical contents that need further clarification. Specifically, the mechanism for information sharing during the testing and inference phases remains unclear. The current configuration, which appears to involve a chain of information sharing, could potentially introduce dependencies between agents during inference. If the reviewer understands correctly, the authors use the S4 convolutional nature to address the issue.However, the precise methodology remains unclear. This is a crucial technical aspect of the paper and requires further elaboration.

Response Thank you for this comment. In the SE-MDP framework used in this work, information sharing is needed only between consecutive agents, and each agent cooperates with its preceding agent in the sequence to take better cooperative actions. By sharing information based on the hidden state representation of the S4 model which essentially accumulates information about previous agents in the sequence, an agent does not need to communicate with all the previous agents, but just its immediate predecessor, thus allowing for a scalable communication mechanism. This induces a sequential nature in the decision-making process (which can also be avoided by applying a small modification as detailed next), where each decision step takes linear O(m) time where m is the number of agents. However, this communication mechanism can be performed in constant O(1) communication memory overhead, since any agent needs to communicate with only one other agent; and still achieve bi-directional cooperative behavior with the entire team since the memory representation holds information of all its preceding agents and gradients are backpropagated from the agents ahead of the agent in the sequence. Moreover, by leveraging the convolutional view of the S4 model, the training is executed in an efficient and parallel manner over the time sequence length for each agent.

MADS4 can also be adapted for fully decentralized settings with a minor adjustment to how memory information is shared. To achieve a fully decentralized MARL setting, instead of accessing the current timestep's updated memory from the previous agent in the sequence, each agent uses the memory information of the previous agent from the previous timestep. This approach allows all agents to take actions in parallel, as the required memory information from the previous timestep is already available when making decisions at the current timestep.

Leveraging S4-based models enables per-agent inference to be performed in constant memory and time, offering a significant advantage over attention-based transformer models like MADT and MADTKD, which incur quadratic runtime relative to the sequence length. This algorithm is thus highly scalable and applicable in scenarios with limited communication budgets, as it achieves constant time and memory communication overhead with the number of agents.

Comment 3

The reviewer found some citations missing, which may lead to confusion. For example, the Methodology section discusses the concept of Sequentially Expanded MDPs without providing any accompanying citations. This omission could lead to confusion among readers regarding the original contributions of this work versus those of prior research.The reviewer recommends that add appropriate citations, such as [b], and explicitly differentiate between the elements that are drawn from existing literature and the novel contributions introduced in this work. This clarification will enhance the overall transparency and understanding of the research presented.

Response Thank you for this comment. We would like to point out that we had cited the mentioned paper in Lines 71-76 as follows: “To model cooperation among agents, we adopt a sequentially expanded MDP (SE-MDP) paradigm, where each decision-making step is divided into mini-steps. This approach has also been recently used in online MARL settings (Li et al., 2023), where each agent takes an action at a given mini-step based on the actions of all preceding agents in the sequence. In our work, we allow limited communication between the agents, with each agent receiving information only from its immediate predecessor in the sequence.”

In the SE-MDP framework proposed by Li et al. (2023), agents share information through their actions, with each agent's action depending on the actions of all preceding agents in the sequence. In contrast, our approach introduces sharing representations of the hidden state of the S4 model, which encapsulates the accumulated memory of an agent. By leveraging this hidden state, we enable the transfer of information about all preceding agents while limiting the information exchange to consecutive agents in the SE-MDP sequence. This approach ensures a more scalable communication mechanism, where each agent requires information only from its immediate predecessor. Consequently, the framework scales efficiently to a larger number of agents, maintaining a constant O(1) communication overhead per agent, compared to the linear O(m) overhead per agent, where m is the number of agents, in the original SE-MDP framework proposed by Li et al. (2023).

Comment 4

In a sequentially expanded MDP, how to decide the order of agents? Does the order have a significant impact on the overall performance?

Response Thank you for this insightful comment. We have evaluated the effect of the order of agents on the performance by comparing two training settings of MADS4: 1) Random Order: where the order of the agents is randomly generated during training, and 2) Fixed Order: where the agents are trained in the fixed order in which the offline dataset is collected. The results in Figure 8 in Appendix Section C.4 show very little to no difference in performance between the two settings, which indicates that MADS4 is robust to the order of agents in the SE-MDP framework. However, we would suggest training the agents in a random order to prevent introducing any bias in the learning process.

Comment 5

L52 - L53. Please provide citations for the mentioned regularization methods. It is unclear to the reviewer what ‘these regularization techniques’ are referring to and why it is challenging.

Response Thank you for this comment. In response, we have added appropriate citations for the regularization methods used in single-agent offline RL and revised manuscript lines 47-53 to better articulate the challenges of extending these methods to multi-agent settings. Specifically, in single-agent offline RL, distribution shift is mitigated by enforcing explicit or implicit constraints on the learned policy to ensure it remains within the support of the offline dataset. However, applying such constraints to the global joint policy space in multi-agent settings is significantly more challenging. The exponential growth of the joint action space with the number of agents can lead to sparse and ineffective constraints, making it difficult to prevent out-of-distribution actions at the global level.

Comment 6

Could you elaborate on the potential communication cost and delay by sharing the information among all agents? Would it be scalable to hundreds of agents?

Response We provide a detailed analysis of the communication costs, including memory and time requirements for information sharing between agents, and how these scale with the number of agents. We have also revised the manuscript to incorporate these details.

Computational Requirements During Training

The training process unfolds over two sequences: 1. Timesteps for each agent: Training over timesteps is efficiently parallelized using the convolutional view of the S4 model. 2. Agents: Training over the number of agents may occur sequentially or in a parallel manner depending on the memory information being shared. Sharing current and updated memory information induces a linear flow of information from one agent to the next. However, if the previous timestep’s memory information is used as a surrogate for the current memory information; the agents can take parallel actions as the required memory information from the previous timestep is already available when making decisions at the current timestep. Each agent shares its hidden state representation from the S4 model, encapsulating information about all preceding agents in the sequence. This eliminates the need for direct communication between non-adjacent agents. As a result:

• Memory: Only the hidden state of the previous agent is required, resulting in constant memory usage $O(1)$.
• Computation time: Decisions can be made in constant time, simultaneously across all agents if previous timestep’s memory information is used. If however decisions are made sequentially, it can lead to worst-case linear time complexity $O(m)$ for the last agent, where $m$ is the number of agents.
  During training, the parallelized training over timesteps for each agent (typically larger than the number of agents) ensures training efficiency.

Computational Requirements During Inference

The same communication mechanism remains valid during inference. This maintains constant memory and constant time decisions at each timestep. This communication avoids the quadratic or near-quadratic communication overheads often encountered in MARL settings with limited communication. Moreover, S4-based MADS4 offers constant memory and constant time inference relative to the sequence length for each agent at any time, compared to the quadratic runtime relative to the sequence length for attention-based transformer architecture like MADT and MADTKD, thus offering a scalable and efficient solution for multi-agent coordination.

Comment 7

There are some inconsistencies between figure 2 and Algo 1. In Figure 2, the agent doesn’t take observations as input, but in Algo 1 it does.

Response Thank you for pointing this out. We have mentioned in Lines 266-267 that the state of each agent at each time step is composed of the global environment state and its local observation. We have also clarified this in the caption of Figure 2.

Comment 8

Algo 1, what is $d_i^t$? Please provide a formal definition.

Response Thank you for pointing this out as well. $d_i^t$ denotes the done or termination signal of an episode. We have now defined this formally in Algorithm 1.

We sincerely thank the reviewer once again for their valuable feedback. In light of the clarifications and revisions made to address their comments and suggestions, we kindly request the reviewer to reconsider their score. We are happy to address any further comments or feedback.

Dear Reviewer R7cj, Could you please read the authors' rebuttal and give them feedback at your earliest convenience? Thanks. AC

Thanks the authors for the response. The response addressed most of my questions including agent's order and the computation time overhead. However, I still have concerns about the experimental results presented in the paper. The improvements of the proposed method are relatively small, with some falling within confidence intervals.

Response

We appreciate the reviewer’s additional comment and are glad that our responses addressed most of their concerns. Our proposed algorithm, MADS4, is designed to compete with transformers as a sequence-to-sequence learning-based offline MARL framework. As such, the most relevant baselines for comparison are transformer-based offline MARL algorithms like MADT and MADTKD. We selected S4-based models due to their strong performance—comparable to or exceeding MADT and MADTKD—particularly in the RWARE domain while offering their other distinct advantages over transformers:

1. Parameter Efficiency: S4-based MADS4 requires only about 12% of the model size of MADTKD, making it significantly more resource-efficient.
2. Handling Longer Context Lengths: S4-based models excel in scenarios with longer trajectories, as observed in the RWARE domain (typically 500 timesteps). This allows MADS4 to outperform MADTKD in such environments.
3. Faster Inference Times: Unlike transformers, which require quadratic runtime relative to sequence length, S4-based models offer constant time and memory inference.

Moreover, the S4-based model inherently learns an internal (hidden) state or memory. In our framework, this memory property of an agent is uniquely leveraged to foster cooperation among agents, further enhancing the effectiveness of MADS4 in multi-agent learning tasks.

We again thank the reviewer for their comments and suggestions that helped us improve our manuscript. We hope this discussion adequately addresses the reviewer's comment above.

Thank you for your valuable feedback, which has helped us enhance the quality and clarity of our work. We are pleased that our rebuttal addressed most of your concerns. Based on your suggestions, we have revised the manuscript and believe our responses effectively address your remaining comments. In light of these revisions and clarifications, we sincerely hope you will reconsider your evaluation. As the discussion period is closing soon, please let us know if you have any remaining questions or need further clarification; we are more than willing to provide additional clarification.

Comment 4

What does the sequential decision-making process bring to the cooperation in MARL, particularly in environments with limited communication or delayed feedback?

Response Thank you for this question. The sequential decision-making process formulation as an SE-MDP with communication limited to only consecutive agents in the sequence is beneficial, evidenced by our model's better performance over the independent setting where the agents are trained independently. Utilizing the hidden state of the S4 module of the current agent, information on all its prior agents is efficiently passed down to the next agent, and gradients of the agents later in the sequence are also backpropagated during training. Even though this communication mechanism induces a sequential flow of information over the sequence of agents, it eliminates the need for an agent to communicate with more than one agent in the system or to identify useful peers, which becomes challenging as the number of agents grows. Typical communication-based MARL algorithms scale poorly with the number of agents; as the memory required during training and execution becomes exceedingly large and scales quadratically with the number of agents. On the other hand, the utilized communication mechanism in our work is relatively scalable requiring only constant memory since any agent only needs information of the previous agent in the sequence.

MADS4 can also be adapted for fully decentralized settings with a minor adjustment to how memory information is shared. To achieve a fully decentralized MARL setting, instead of accessing the current timestep's updated memory from the previous agent in the sequence, each agent uses the memory information of the previous agent from the previous timestep. This approach allows all agents to take actions in parallel, as the required memory information from the previous timestep is already available when making decisions at the current timestep.

Comment 5

Could you provide a detailed computational comparison between the MADS4 and MADT methods, particularly in terms of training time, scalability, and computational complexity?

Response Thank you for this question. We have provided a detailed comparison of the computational complexity and model size (number of parameters) between MADS4 and MADTKD, the state-of-the-art MADT architecture.

Computational Complexity During Training

MADS4 leverages the convolutional view of S4 modules, enabling parallelizable training across timesteps. Specifically, S4 modules use a parallel scan operation, achieving a training complexity of $O(log(N))$ for a sequence of length $N$ with $N$ parallel processors. In contrast, the transformer-based MADT architecture has a quadratic complexity of $O(N^2)$, which, while parallelizable, is significantly higher.
MADT trains agents independently, resulting in suboptimal performance compared to MADTKD, which uses a centralized transformer to model agent interactions. However, MADTKD's centralized approach introduces a quadratic computational overhead in the attention mechanism due to inter-agent interactions during training. In MADS4, cooperation among agents is achieved by limiting communication to consecutive agents in the sequence. This design requires only constant memory, as each agent only accesses the latent state of its predecessor. This communication mechanism induces a recurrent sequential flow of information between agents, resulting in a linear worst-case complexity of $O(M)$ for the last agent in the sequence, where $M$ is the number of agents, which is typically smaller than the number of timesteps $N$ involved in decision-making. However, by employing a simple adjustment—passing the previous agent's hidden state from the previous timestep instead of the current updated hidden state—we can enable fully decentralized policies across agents. This modification removes the need for sequential, recurrent communication, thereby eliminating the linear $O(M)$ time complexity.

Computational Complexity During Inference

MADS4 offers highly scalable runtime performance, with constant memory and time per timestep, irrespective of the sequence length. In contrast, MADT's inference complexity scales quadratically with the sequence length for each agent due to its attention mechanism.

Model Size and Performance Comparison

MADS4 achieves superior performance compared to MADT and MADTKD while being far more parameter-efficient. For example, on the RWARE small map, the best-performing MADS4 model (input channels $H = 96$ and hidden state size $N = 96$) requires only about 12% of the parameters used by MADTKD. Despite this, MADS4 delivers better results, as demonstrated in the experiments.
We hope this addresses your query and highlights the computational and performance benefits of MADS4 over MADT and MADTKD.

We sincerely thank the reviewer for their detailed feedback. Below, we provide our responses to the comments and concerns raised.

Comment 1

First of all, the writing in the paper lacks clarity, and the logical flow is sometimes hard to follow. There are several instances of grammatical errors and awkward phrasing that undermine the overall readability of the paper.

Response We sincerely appreciate the reviewer’s feedback and have made substantial revisions to enhance the paper's clarity and readability, incorporating the provided comments and suggestions.

Comment 2

The paper primarily combines the S4 model with the SE MDP framework, which does not represent a significant departure from existing methods. While the S4 model itself is innovative, its application to SE MDP does not present a new solution that clearly advances the field. The motivation for the proposed method is not fully convincing. The paper asserts that the introduction of the S4 model to the SE MDP framework provides an advantage over MADT; however, MADT is also compatible with SE MDP, and the paper does not sufficiently clarify the comparative benefits of S4. The paper should provide a more detailed analysis comparing S4 with other multi-agent methods (such as MADT, QMIX, etc.) in the same experimental settings, particularly focusing on key aspects like cooperation, information sharing, and stability. A thorough comparison would help determine whether S4 offers substantial improvements over current approaches.

Response We appreciate the reviewer’s comment and the general recognition of our novel implementation of S4-based models in offline MARL. We want to clarify why we chose S4-based models over traditional transformers, particularly within the SE-MDP framework. S4-based models offer several advantages over transformers, including parameter efficiency (as shown below), the ability to handle longer context lengths, and faster inference times. In contrast to the quadratic runtime of transformers with respect to sequence length, S4 models operate with asymptotic constant time and memory. In addition to these advantages, the S4 model is associated with inherently learning an internal (hidden) state or memory. In our SE-MDP framework, we uniquely leverage this memory to facilitate limited communication between agents, where each agent only needs to access information from its immediate predecessor, shared through its S4-based latent state. Utilizing this hidden state of the S4 module of the current agent, information on all its prior agents is efficiently passed down to the next agent, and gradients flow backward from the current agent through this shared memory to the previous agents during training. This sequential flow of information eliminates the need for an agent to communicate with more than one peer or identify useful collaborators, a challenge that grows with the number of agents. In contrast to typical communication-based MARL algorithms, which scale poorly due to the quadratic growth in memory requirements during training and execution, our mechanism is highly efficient, requiring only constant memory per agent. This sharing of information helps the learning process become more stable resulting in better performance as evidenced in Figure; where the agents are trained independently vs trained with information sharing between them.

Comment 3

It is easy to see that using s4 model improves the ability of representation, and thus the results are not surprising. The experimental evaluation is insufficient, and the paper would benefit from comparisons across a broader range of SMAC maps. Additionally, the paper mentions that online fine-tuning has limited effectiveness, with some cases showing performance degradation. However, the authors do not provide a clear explanation of why this occurs, nor do they offer potential solutions to mitigate this issue. It is worth noting that in the SMAC 2c vs 64zg task, the proposed MADS4 method shows lower average returns with on-policy training without offline pretraining compared to MAPPO (which achieves a 100% win rate and an average return of 20.0), raising concerns about the practical effectiveness of the method.

Response We thank the reviewer for their thoughtful comments, which we address point-by-point below. To validate our algorithm, we selected two environments with distinct characteristics. The first is the RWARE domain, which features high-dimensional observations and challenging learning patterns with long context lengths (up to 500 timesteps) in offline datasets. While MADT typically trains with truncated context lengths to reduce computational costs, MADS4 efficiently processes full trajectory lengths with significantly fewer parameters than MADT. The second environment is SMAC, where we evaluated performance on two hard and two super-hard maps. These maps used offline datasets provided by OMIGA, the current state-of-the-art across these scenarios. The longest trajectory encountered was 100 timesteps in the challenging Corridor map. MADS4 demonstrated comparable or superior performance to OMIGA on these maps, showcasing its robustness and effectiveness in handling diverse tasks.

The offline training of MADS4 takes place using convolution over entire trajectories in the offline datasets. For online finetuning, the MADS4 is trained using recurrence on the online-collected transition tuples. Recurrent training, however, is prone to error accumulation, which can degrade performance. To mitigate this effect, we propose freezing the offline pre-trained S4 kernel parameter $A$ during online fine-tuning and updating only parameters $B$ and $C$, ensuring stability and improved adaptation in the fine-tuning phase. To clarify this point, we have added lines 473–478 to the manuscript and Figure 7 in the Appendix.

The comparison between the online-trained version of MADS4 without pretraining and MAPPO may not be entirely fair for two key reasons. First, MADS4's online training relies on the recurrent view of the S4 modules, which inherently results in lower performance. Second, MADS4 is designed as a sequence learning-based offline reinforcement learning algorithm, capable of achieving an average return of 20.0 on the SMAC map 2c vs 64zg using just 1,000 offline trajectories (equivalent to 50,000–100,000 environment steps). In contrast, online MARL algorithms like QMIX and MAPPO typically require significantly more interactions—on the order of 10 million environment steps—to achieve comparable performance. Importantly, offline pre-trained MADS4 provides a strong starting point for further fine-tuning with any online MARL algorithm, combining the strengths of both approaches.

Dear Reviewer zdmt, Could you please read the authors' rebuttal and give them feedback at your earliest convenience? Thanks. AC

Thank you for your valuable feedback. We are glad our rebuttal addressed most of your concerns and improved the quality and clarity of our work. We have revised the manuscript based on your suggestions and believe our responses effectively address your additional comments. In light of these revisions and clarifications, we sincerely hope you will reconsider your evaluation. As the discussion period is closing soon, please let us know if you have any remaining questions or need further clarification; we are more than willing to provide additional clarification.