Towards Efficient Collaboration via Graph Modeling in Reinforcement Learning

Wenzhe Fan, Zishun Yu, Chengdong Ma, Changye Li, Yaodong Yang, Xinhua Zhang

Abstract

In multi-agent reinforcement learning (MARL), centralized training with decentralized execution (CTDE) is a standard paradigm, yet it often limits coordination due to agents' restricted local observations during execution. This paper introduces the Factor-based Multi-Agent Transformer (f-MAT), a novel encoder-decoder architecture that models agent interactions as a bipartite graph. By organizing agents into overlapping "factors" (hypernodes) and utilizing factor-based attention layers, f-MAT achieves efficient message passing and parallel action generation. Empirical evaluations in networked systems, including traffic scheduling and power control, demonstrate that f-MAT significantly outperforms existing baselines in both performance and inference speed, offering a scalable solution for complex collaborative tasks.

Introduction

Cooperation in large-scale multi-agent systems is a fundamental challenge in reinforcement learning. While Centralized Training with Decentralized Execution (CTDE) provides a stable training framework, the lack of communication during execution often leads to sub-optimal coordinated policies. Existing solutions involving Graph Neural Networks (GNNs) or standard Transformers face two primary bottlenecks: the $O(n^2)$ computational complexity of global attention and the high inference latency of autoregressive action generation.

To address these issues, we propose f-MAT, which leverages a factor-based interaction model to enable efficient, real-time communication among neighboring agents.

Methodology

The core innovation of f-MAT lies in its bipartite graph representation of agent interactions and its non-autoregressive decoding scheme.

Factor-based Representation and Attention

Rather than allowing all-to-all communication, f-MAT organizes agents into overlapping groups called factors. Each factor acts as a virtual hub that aggregates information from its constituent agents and broadcasts refined messages back. This bipartite structure reduces the attention complexity from $O(n^2)$ to $O(m \cdot S_f \cdot L)$, where $m$ is the number of factors and $S_f$ is the maximum factor size.

The Factor-based Multi-Head Attention (f-MHA) mechanism uses specific masks to ensure information only flows between agents and their assigned factors. Through overlapping factor memberships, information can propagate across the entire graph over multiple layers.

Factor graph representation (a) and attention details during factor updates (b).

Parallel Decoding

Standard Transformer-based MARL models typically generate actions autoregressively, which is prohibitively slow for real-time control in large systems. f-MAT introduces a parallel inference scheme inspired by Gibbs sampling. By alternating between node-to-factor and factor-to-node updates, the model generates all agent actions simultaneously. This approach treats action generation as a synchronized message-passing task, drastically reducing latency.

The parallel update scheme for factor-based multi-head attention.

Experiments and Results

We evaluated f-MAT on three distinct networked environments: GridSim (traffic gate synchronization), SUMO (real-world traffic light control in Monaco), and PowerGrid (voltage control in microgrids).

Key Findings

  • Scalability: In a 144-agent GridSim task, f-MAT outperformed MAPPO and MAT-dec by 35% and 25%, respectively.
  • Inference Speed: f-MAT achieved an 18x speedup over the original Multi-Agent Transformer (MAT) in large-scale grids, reducing inference time from 0.269s to 0.014s.
  • Training Efficiency: The model reached optimal performance in approximately half the training time required by standard baselines.
  • Heterogeneity: In the Monaco traffic scenario, f-MAT successfully coordinated agents with diverse observation and action spaces, demonstrating robustness to complex topologies.

Discussion and Conclusion

f-MAT demonstrates that modeling agent interactions through factors provides a powerful abstraction for group-level semantics. By breaking the "autoregressive curse" of Transformers, it makes high-frequency coordinated control viable for large-scale networked systems.

A current limitation is the reliance on a static, pre-defined factor graph. Future research will focus on learnable factors, allowing the model to dynamically discover and evolve its communication structure as the environment changes. This evolution will be crucial for applying f-MAT to dynamic systems like autonomous swarms or mobile sensor networks.

Summary updated

Abstract

In multi-agent reinforcement learning, a commonly considered paradigm is centralized training with decentralized execution. However, in this framework, decentralized execution restricts the development of coordinated policies due to the local observation limitation. In this paper, we consider the cooperation among neighboring agents during execution and formulate their interactions as a graph. Thus, we introduce a novel encoder-decoder architecture named Factor-based Multi-Agent Transformer ($f$-MAT) that utilizes a transformer to enable communication between neighboring agents during both training and execution. By dividing agents into different overlapping groups and representing each group with a factor, $f$-MAT achieves efficient message passing and parallel action generation through factor-based attention layers. Empirical results in networked systems such as traffic scheduling and power control demonstrate that $f$-MAT achieves superior performance compared to strong baselines, thereby paving the way for handling complex collaborative problems.
BibTeX
@inproceedings{fan2025towards,
  author = {Wenzhe Fan and Zishun Yu and Chengdong Ma and Changye Li and Yaodong Yang and Xinhua Zhang},
  title = {{Towards Efficient Collaboration via Graph Modeling in Reinforcement Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=SmqtRADMhH},
}
Figure