Towards Efficient Collaboration via Graph Modeling in Reinforcement Learning

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

TL;DR

Standard multi-agent reinforcement learning (MARL) either isolates agents during execution or incurs massive computational overhead and noise by aggregating global information. Factor-based Multi-Agent Transformer (f-MAT) introduces a bipartite factor-graph attention mechanism that enables localized, group-level communication during both training and execution. Combined with a novel parallel decoding scheme, f-MAT matches centralized performance upper bounds while reducing attention complexity to $O(m \cdot S_f \cdot L)$ and cutting inference latency down to decentralized baseline speeds.

What Problem Does This Paper Address?

Multi-Agent Reinforcement Learning often relies on Centralized Training with Decentralized Execution (CTDE). While CTDE stabilizes value estimation during training, agents act independently during execution based strictly on local observations—often failing tasks requiring close coordination (like synchronizing neighboring traffic lights or power grids).

Conversely, fully centralized execution methods (such as the original Multi-Agent Transformer, MAT) model the joint action space as a causal sequence. However, MAT has critical drawbacks:

  1. Quadratic Complexity: Attention across $n$ agents scales at $O(n^2)$, becoming intractable for large networks.
  2. Autoregressive Bottleneck: Inference requires token-by-token action generation across an artificially imposed ordering of agents.
  3. Information Overload: Forcing every agent to attend to all others injects irrelevant distant noise into decisions that are fundamentally localized.

Methods

To bridge the gap between rigid independence and expensive centralized attention, f-MAT introduces:

  • Factor Graph Coordination: Agents are organized into overlapping groups, each represented by a virtual hypernode called a factor. An agent can belong to multiple factors, enabling information to ripple across the network without full all-to-all connectivity.
  • Factor-based Multi-Head Attention (f-MHA): Instead of standard dense attention, f-MAT alternates message passing:
  • Nodes to Factors: Factors query their constituent member agents.
  • Factors to Nodes: Agents update their representations by querying the factors they belong to.
    Sparse mask matrices enforce this bipartite communication, slashing time/space complexity from $O(n^2)$ to $O(m \cdot S_f \cdot L)$, where $m$ is the factor count, $S_f$ is maximum factor size, and $L$ is layer depth (typically $L \le 3$).

  • Parallel Action Decoding: Rather than autoregressively generating actions one-by-one, f-MAT decodes actions in parallel. Decoders alternate node-to-factor and factor-to-node updates in a synchronized manner resembling Gibbs sampling, initialized via linear action heads to bypass slow mixing.

  • Localized Actor-Critic Objective: Value functions and PPO policy updates are formulated locally over each agent's receptive field (the neighborhood reachable within $2L$ hops on the factor graph).
[Agent Nodes] <====(Masked Attention)====> [Hypernode Factors]
                      (f-MHA Layers)

Datasets

The authors evaluated f-MAT across three networked cooperative domains:

  1. GridSim (Grid Alignment): An $s \times s$ simulated traffic flow grid ($8 \times 8$, $10 \times 10$, $12 \times 12$; up to 144 agents) requiring immediate neighbors along rows and columns to align gates horizontally or vertically.
  2. Traffic Signal Control (SUMO): A realistic 28-intersection network modeled after Monaco, featuring heterogeneous observation and action spaces where agents must balance broader regional traffic queues.
  3. Voltage Control (PowerNet): Distributed generator (DG) benchmark on power networks under local physical constraints, evaluated on microgrid-6 (6 DGs) and microgrid-20 (20 DGs).

Key Insights and Ideas

  • Centralization Can Harm Performance: In the large-scale microgrid-20 benchmark, fully centralized MAT achieved the worst performance among baselines. Broadcasting global observations into localized control problems introduces disruptive, task-irrelevant information. f-MAT's factor boundaries provide natural inductive bias against this noise.
  • Parallel Inference Eliminates Order Sensitivity: Standard transformers impose an artificial agent permutation order to generate actions sequentially. f-MAT’s parallel factor updates generate all agent actions simultaneously without sacrificing coordination.
  • The Depth Sweet Spot: Ablations on layer depth ($L$) show an "over-smoothing" effect akin to graph neural networks (GNNs). While performance improves as $L$ increases from 1 to 3, going up to 4 or 5 degrades policy quality as representations across factors become too homogeneous.

Key Results

  • Task Performance: On the $12 \times 12$ GridSim grid, f-MAT closely approached centralized MAT's optimal reward, whereas decentralized baselines (MAPPO and MAT-dec) lagged significantly, reaching only 65% and 75% of f-MAT’s score.
  • Training Efficiency: f-MAT achieved target performance in half the training time required by MAPPO and MAT-dec on GridSim, and used only 3/5 of the time on the Monaco SUMO task.
  • Inference Speed: Thanks to parallel decoding, f-MAT matches the inference speed of non-autoregressive MAPPO, while running orders of magnitude faster than autoregressive MAT and MAT-dec.

Limitations and Future Work

  • Static Factor Definition: Factors currently rely on fixed heuristic groupings (e.g., spatial lines, connected components, or $k$-hop neighborhoods).
  • Graph Dynamics: The current formulation assumes a fixed graph topology during execution, which may not translate directly to ad-hoc or mobile multi-agent setups.
  • Future Directions: The authors highlight learning dynamic, adaptive factor assignments and expanding to time-varying topologies as key next steps.

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},
}

Loading related content...

Figure