MASTARS: Multi-Agent Sequential Trajectory Augmentation with Return-Conditioned Subgoals

Jiwon Jeon, Myungsik Cho, Woojun Kim, Seongmin Kim, Woohyeon Byeon, Seungyul Han, Youngchul SungarXiv 2026 · arXiv

TL;DR

MASTARS is a novel diffusion-based framework designed to supercharge offline Multi-Agent Reinforcement Learning (MARL) by generating high-quality synthetic trajectories. By combining agent-wise sequential generation with diffusion inpainting and value-based subgoals, it successfully navigates the "diversity–coordination–coherence" trade-off, leading to performance boosts of up to 152% on complex benchmarks like SMAC-v2.

What Problem Does This Paper Address?

Offline Reinforcement Learning is a powerful paradigm: it allows agents to learn from pre-collected datasets without risky or expensive real-world exploration. However, the resulting policy is only as good as the data it's fed. If the dataset is narrow or lacks high-quality examples, the agent will struggle.

In multi-agent settings (MARL), fixing this via data augmentation is notoriously difficult due to a three-way trade-off:

  1. Diversity: Independent generation for each agent creates diverse behaviors but fails to coordinate them (agents collide or ignore each other).
  2. Coordination: Jointly generating all agents at once ensures they work together but often results in "mode collapse," where the model simply repeats the exact patterns found in the training data.
  3. Coherence: Naive sequential generation (agent A, then B, then C) often leads to global inconsistencies, like environmental landmarks appearing to "jump" or flicker because each agent's generation process has a slightly different "view" of the world.
Figure 1: Comparison of trajectory generation strategies: Existing strategies struggle to jointly achieve coordination, diversity, and global coherence, while MASTARS satisfies all three. X marks are landmark positions reconstructed from each agent’s observation.

Methods

The authors introduce MASTARS (Multi-Agent Sequential Trajectory Augmentation with Return-conditioned Subgoals). It treats trajectory generation as a constrained synthesis problem using three core pillars:

  • Inpainting-Based Sequential Generation: Instead of generating everything at once, MASTARS generates trajectories agent-by-agent. It uses a technique called RePaint (a training-free diffusion inpainting method). When generating the $i$-th agent, the trajectories of previously generated agents are treated as "known" regions. The diffusion model "inpaints" the new agent's path to be consistent and coordinated with the existing ones.
  • Subgoal-Based Partial Generation: To avoid the difficulty of synthesizing long trajectories from scratch, the model identifies "subgoals"—the highest-value timesteps in an existing trajectory. It keeps the original trajectory prefix (the "anchor") and only regenerates the continuation from that point. This significantly reduces the search space for the diffusion model.
  • Value-Based Ordering: The order in which agents are generated matters. MASTARS sorts agents based on their subgoal timing. Agents with later subgoals are generated first, while those with earlier subgoals (who have more of their trajectory to "fix") are generated later. This gives the agents with the most work to do the maximum flexibility to adapt to the others.

Datasets

The researchers evaluated MASTARS on three major MARL benchmarks:

  • MPE (Multi-Agent Particle Environment): Tasks like Tag, Spread, and World that require continuous coordination in 2D space.
  • SMAC (StarCraft Multi-Agent Challenge): A high-dimensional, discrete-action benchmark based on StarCraft II.
  • SMAC-v2: A significantly more difficult version of SMAC with randomized unit compositions and starting positions, designed to test robustness and generalization.

Key Insights and Ideas

  • Inpainting as Coordination: The "aha" moment is realizing that multi-agent coordination is essentially a temporal-spatial inpainting problem. If you know what Agent A is doing, Agent B’s path is just "missing data" that must be filled in to be consistent with Agent A.
  • Don't Fix What Isn't Broken: By using subgoals to preserve trajectory prefixes, the model leverages the "expert" parts of the original data while focusing its generative power only on the parts that need improvement or variation.
  • The Flexibility of Order: Generating agents with the most "regenerated" time steps last is counter-intuitive but brilliant—it ensures that the agents who need to make the biggest adjustments have the most "context" (the paths of other agents) to coordinate with.

Key Results

MASTARS was tested as a "plug-in" for several popular offline MARL algorithms, including CFCQL, OMAR, and MATD3+BC.

  • Performance Boosts: On the MPE benchmark, it improved average performance by 33% to 38% across different algorithms.
  • SMAC Dominance: In the standard SMAC environment, it achieved a 100% win rate on demanding tasks like 3m and 8m.
  • Robustness in SMAC-v2: In the highly stochastic SMAC-v2, MASTARS delivered a staggering 152.6% average performance boost compared to training on the original dataset alone.
  • Diversity & Coherence: Quantitative metrics (DIRE scores and t-SNE analysis) confirmed that MASTARS produces a broader distribution of behaviors than joint generation while maintaining much lower collision rates and landmark errors than independent or naive sequential methods.

Limitations and Future Work

  • Computational Cost: Because MASTARS performs a full inpainting pass for each agent, the sampling time scales linearly with the number of agents ($N$). For environments with dozens or hundreds of agents, this could become a bottleneck.
  • Subgoal Selection: Currently, subgoals are based on individual value functions. The authors suggest that exploring joint value functions or learning a distribution of subgoals could further improve the quality of the generated anchors.
  • Parallelism: A promising future direction is exploring how to generate "weakly interacting" agents in parallel to reduce the sequential overhead.

Summary updated

Abstract

The performance of offline Multi-Agent Reinforcement Learning (MARL) is limited by the quality of the fixed offline dataset, motivating trajectory augmentation. However, augmenting multi-agent trajectories presents a fundamental challenge of the diversity-coordination trade-off: independent generation improves diversity but lacks coordination, while joint generation induces coordination but lacks diversity, reproducing the training distribution. To address this challenge in multi-agent data augmentation, we introduce MASTARS, a novel diffusion-based framework that generates multi-agent trajectories sequentially across agents while enforcing cross-agent consistent coordination via the method of inpainting. MASTARS produces trajectories that are diverse, coordinated and globally coherent. Experiments on various benchmarks such as MPE, SMAC, and SMAC-v2 demonstrate significant performance gains across multiple offline MARL methods.
BibTeX
@misc{jeon2026mastars,
  author = {Jiwon Jeon and Myungsik Cho and Woojun Kim and Seongmin Kim and Woohyeon Byeon and Seungyul Han and Youngchul Sung},
  title = {{MASTARS: Multi-Agent Sequential Trajectory Augmentation with Return-Conditioned Subgoals}},
  year = {2026},
  eprint = {2611.17793},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17793},
}
Figure