When an artificial agent plans a route, plays a game, or manipulates an object, it represents the world as a "state." In complex environments, this state is composed of many variables: joint angles, object positions, velocities, and environmental conditions. The fundamental challenge of sequential decision-making is that the size of this state space grows exponentially with the number of variables—a phenomenon known as the curse of dimensionality. If every variable interacts with every other variable, finding an optimal policy quickly becomes computationally intractable.
However, real-world tasks possess an underlying structural property: locality. Most actions only affect a tiny fraction of the environment at any given time. Early cognitive insights by Luger et al. demonstrated that human problem solvers naturally navigate this by partitioning complex spaces into nested, localized subspaces representing distinct subgoals. Similarly, Sheridan et al. observed that human operators can reduce the searchable state space of robotic path planning by over 99% simply by decomposing tasks into discrete, bounded subgoals.
Modular state space decomposition is the formalization of this intuition: breaking a high-dimensional global state space into smaller, decoupled, or factored components to make planning and learning scalable.
Factoring States via Action Effects and Physical Dimensions
Why does state decomposition work? The core insight lies in analyzing the relationship between an agent's actions and the state variables. If an action changes only a specific subset of variables, those variables can be grouped into an independent factor.
Konidaris et al. formalized this by showing that continuous state spaces can be automatically decomposed into independent factors based on which variables are modified simultaneously by specific actions (or options). By constructing symbolic representations around these factored transitions, planning algorithms can bypass the exponential explosion of the state space, achieving massive speedups. To further simplify action definitions, Borgwardt et al. show that decoupling the observed state from the inferred state allows environmental logic to be shifted into an ontology, enabling planners to navigate using simplified actions.
This concept extends naturally to object- and entity-centric representations. Instead of treating an entire scene configuration as a single state, the environment can be treated as a collection of modular entities. For instance, Qi utilizes a subgoal-generating diffusion model to produce "factored" subgoals where only one or two objects change at a time. This sparsity drastically reduces control complexity because the low-level policy only needs to reason about a tiny, localized subset of the state space. Similarly, Zhang factorizes global states into object-centric representations guided by human visual attention, and James et al. demonstrate that grouping objects into types based on their transition dynamics allows agents to learn portable, high-level planning models.
Decomposition can also occur across distinct physical dimensions. For example, Cathomen et al. decompose a robot's state space into separate logical components, such as planar position versus orientation. This factorization isolates specific degrees of freedom, enabling independent skill discovery across different physical dimensions and yielding more granular control.
Task-Specific Abstractions and Local MDPs
Another way to achieve decomposition is to break a global Markov Decision Process (MDP) into a collection of smaller, self-contained sub-problems.
Boutilier et al. pioneered this by decomposing complex MDPs into prioritized, goal-specific sub-problems. The mathematical elegance of this approach is highlighted by Sprague et al., who show that when a global task is decomposed into multiple independent, goal-specific MDPs, the total state space drops from an exponential combination of all environment variables to a linear sum of smaller subspaces. When scaling to complex multitasking environments, Hadfield-Menell et al. note that incorporating these factored dynamics directly into value-bounding processes is essential for efficient planning.
To make this work, each subtask must maintain its own local state abstraction. As Nachum explains, hierarchical agents can fail if they focus on the wrong dynamics; they must distinguish between task-relevant features and irrelevant state information (such as isolating an agent's internal joint angles from the external position of a target object).
By filtering out environmental noise, an agent can ignore features that are globally relevant but locally irrelevant to the current subtask. Jonsson et al. demonstrate this by automating state abstraction for individual options. Similarly, Konidaris automatically segments demonstration trajectories into skill trees, where each skill is bound to a specific, low-dimensional state abstraction.
Global State Space (Exponential Combination)
[ Var A × Var B × Var C × Var D ] ──► Intractable Search
Factored State Space (Linear Sum of Subspaces)
├── Subtask 1 (Focuses only on Var A & B) ──► Local Policy 1
└── Subtask 2 (Focuses only on Var C & D) ──► Local Policy 2
When these localized regions are treated as modular blocks with defined entry and exit conditions—as explored by Winder et al., Silver et al., Jonsson et al., and Cipollone et al.—the agent can solve local regions independently and compose them into a global strategy. This task-specific modularity also enables composability; Simpkins et al. show that sub-modules utilizing localized state representations can be dynamically combined and arbitrated, even if they operate on entirely different reward scales.
A classic intuition for this is the 15-puzzle. Bischoff et al. show that by solving the puzzle tile-by-tile—treating it as a sequence of local subproblems where only a subset of elements is manipulated while others remain fixed—the effective state space shrinks from a staggering $10^{13}$ configurations to a maximum of just 10,080.
Decoupling Multi-Agent and Collaborative Spaces
State space explosion is particularly severe when multiple entities or agents interact. If an algorithm tracks the joint state of all agents simultaneously, the state space multiplies combinatorially.
To combat this, Motes et al. introduce a framework that decomposes a composite state space into independent components for individual agents and objects. These components are kept entirely separate during planning and are only coupled through specific interaction transitions, keeping the overall dimensionality low.
Joint Multi-Agent Space: [Agent 1 ⊗ Agent 2 ⊗ Object A] (Combustion Explosion)
Decoupled Space: [Agent 1] [Agent 2] [Object A]
│ │ │
└───► Coupled Only At ◄─┘
Interaction Transitions
This decoupling is equally powerful in human-agent collaboration. Oh et al. demonstrate that separating the state space of a human user from the state space of an assistant agent prevents exponential growth. By operating under the structural assumption that the assistant's actions do not directly modify user-controlled variables, the system can track independent variables separately. This architectural choice isolates the computational overhead, enabling real-time planning and prognostic reasoning without computational collapse.
Key Foundational Work
Problem Structure And Problem Solving Behavior (1975) — contributed 2 concept elements to this direction.
Human Control of Remote Computer-Manipulators (1969) — contributed 2 concept elements to this direction.
Human Control of Remote Computer-Manipulators (1969) — contributed 2 concept elements to this direction.