Sequential Decomposition of Multi-Agent Action Spaces

This direction is merged into another direction: sequential action decomposition. Its last version stays readable and citable here.

Version 1 of 119 papers28 conceptsfrozen 2026-10-04

In multi-agent systems, the "curse of dimensionality" is not just a theoretical hurdle—it is a mathematical wall. If a single robot has 10 possible actions, a team of 10 robots has $10^{10}$ possible joint actions. This exponential explosion makes centralized coordination nearly impossible for large teams, as the search space for the optimal joint move grows too wide to explore.

To bypass this, a recurring strategy across reinforcement learning, pathfinding, and robotics is to transform this "wide" simultaneous problem into a "deep" sequential one. By having agents select their actions one-by-one within a single timestep—each conditioning its choice on the decisions of those before it—researchers have found they can reduce computational complexity from exponential to linear without sacrificing coordination.

The Geometry of Coordination

The core intuition behind this shift is a change in how we view the decision space. In a standard joint action model, we treat the team as a single "super-agent" picking one point in a massive high-dimensional grid. Trevor Scott Standley famously addressed this in Finding Optimal Solutions to Cooperative Pathfinding Problems through Operator Decomposition (OD).

Instead of moving all agents at once, OD introduces intermediate states. Agent 1 moves, then Agent 2 moves based on Agent 1's new position, and so on. Only after the last agent has moved does the environment clock tick forward. This reduces the branching factor of the search tree from $A^N$ (where $A$ is actions and $N$ is agents) to a constant $A$. While the tree becomes deeper, the drastic reduction in width makes it far more tractable for search algorithms.

Linearizing the Policy Space

This sequential framing is not limited to pathfinding; it has become a cornerstone of modern Multi-Agent Reinforcement Learning (MARL). Muning Wen and colleagues demonstrated in Multi-Agent Reinforcement Learning is a Sequence Modeling Problem that the joint policy search can be mathematically decomposed. Their Multi-Agent Transformer (MAT) uses an encoder-decoder architecture to process agents as a sequence, ensuring that each agent’s action is informed by the actions already "committed" by its predecessors.

The power of this approach lies in the Multi-Agent Advantage Decomposition Theorem. It proves that as long as each agent improves its action relative to the choices of the preceding agents, the joint team policy is guaranteed to improve. This principle allowed Sushmita Bhattacharya and Dimitri P. Bertsekas to coordinate up to 10 robots in state spaces as large as $10^{37}$ using a "one-agent-at-a-time" rollout algorithm in Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems.

From StarCraft to Language Models

The versatility of sequential decomposition is evident in its application to vastly different domains:

Why It Works: Context as Coordination

The reason sequential decomposition works so well is that it replaces explicit coordination protocols with context. In a simultaneous system, agents must predict what others will do to avoid collisions or redundant tasks. In a sequential system, Agent $k$ simply looks at what Agents $1$ through $k-1$ have already decided.

As Aaron Walsman and Stephanie Gil show in Data-Efficient Multi-Agent Spatial Planning with LLMs, this makes the problem highly compatible with Large Language Models. By feeding the decisions of previous agents into the prompt context for the next agent, the LLM can resolve complex resource allocation (like taxi routing) with linear complexity.

By transforming the multi-agent problem from a "simultaneous guess" into a "sequential conversation," these researchers have turned an intractable exponential search into a scalable linear process, enabling coordination in environments that were previously too complex to model.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_sequential_decomposition_of_multi_agent__274571e1,
  title = {Sequential Decomposition of Multi-Agent Action Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-decomposition-of-multi-agent-action-spaces/rdr_274571e107e2444e9fe02fd7b1293257},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_sequential_decomposition_of_multi_agent__274571e1_v1,
  title = {Sequential Decomposition of Multi-Agent Action Spaces},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sequential-decomposition-of-multi-agent-action-spaces/rdr_274571e107e2444e9fe02fd7b1293257/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}