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:
- Real-Time Strategy: In Episodic Exploration for Deep Deterministic Policies, Nicolas Usunier and the FAIR team used sequential action decomposition to manage the combinatorial complexity of StarCraft micromanagement, allowing armies of 15 units to coordinate their fire and movement effectively.
- Generative AI: Dong-Ki Kim applied this to prompt engineering in MultiPrompter, where multiple agents take turns building a prompt. This breaks a massive search space into smaller, manageable segments.
- World Modeling: Yang Zhang and Xinran Li introduced DIMA in Revisiting Multi-Agent World Modeling from a Diffusion-Inspired Perspective, which treats state transitions as a sequential denoising process. By revealing agent actions one by one, they maintain global consistency without the exponential cost of joint modeling.
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.