Scaling Decision Making via Factored State Representations

21 concepts18 papers1 proposal

When an autonomous agent navigates the world—whether it is a robot planning a path, a dialogue system conversing with a user, or an algorithm managing a power grid—it must track the state of its environment. In traditional Markov Decision Processes (MDPs), this state is treated as a single "flat" index. If your environment is described by $n$ binary variables (e.g., DoorOpen, HasKey, BatteryLow), the total number of possible states is $2^n$.

This exponential growth is known as the curse of dimensionality. As Michael Littman et al. demonstrated in Probabilistic Propositional Planning: Representations and Complexity, determining whether a successful plan exists in such propositional domains is fundamentally EXPTIME-complete. The complexity is a feature of the problem itself, not how we write it down. To make large-scale planning and learning computationally feasible, we must exploit the internal structure of the environment. This is achieved by shifting from flat state spaces to factored state representations, a foundational paradigm synthesized by Craig Boutilier et al. in Decision-Theoretic Planning: Structural Assumptions and Computational Leverage.

The Core Intuition: Local Dependencies

The core insight behind factored representations is that in the real world, everything does not interact with everything else all at once. If a robot moves to the left, its internal battery level and its coordinate position change, but the weather outside or the status of a door in another building remains completely unaffected.

In a Factored MDP (FMDP), the global state is decomposed into a vector of independent variables or factors: $S = \{X_1, X_2, \dots, X_n\}$. Instead of defining a massive $2^n \times 2^n$ transition matrix to capture how the entire state evolves, the transition dynamics are broken down into local conditional probability distributions. The next state of a single variable $X_i'$ depends only on a small subset of "parent" variables $\text{Parents}(X_i) \subseteq S$.

$$\mathbb{P}(S' \mid S, a) = \prod_{i=1}^n \mathbb{P}(X_i' \mid \text{Parents}(X_i), a)$$

If each variable is influenced by at most $k$ parents (where $k \ll n$), storing the transition dynamics requires only $n \cdot 2^k$ parameters rather than $2^{2n}$. This structural sparsity shifts the computational burden from global state enumeration to the manipulation of localized causal relationships.

Compacting the Value Function

Representing the transitions compactly is only half the battle; planning and control require computing a value function. If the value function requires enumerating every global state, the curse of dimensionality returns. Fortunately, local transition structures often imply local value structures. If the global reward function can be written as a sum of local rewards, the global value function can be closely approximated as a linear combination of local basis functions, each depending only on a small subset of variables.

Dale Schuurmans et al. leveraged this property in Direct value-approximation for factored MDPs by introducing an Approximate Linear Programming (ALP) framework. Instead of solving a massive optimization problem over the entire state space, they used an iterative constraint generation technique that computes high-quality policies in seconds for state spaces as large as $10^{12}$ states.

This principle is not restricted to discrete variables. In Linear Program Approximations for Factored Continuous-State Markov Decision Processes, Milos Hauskrecht et al. extended ALP to continuous domains. By pairing continuous Beta distributions for local transitions with polynomial basis functions, they derived closed-form solutions that bypass the need for grid-based discretization, ensuring that optimization complexity scales strictly with local variable interactions.

Sample-Efficient Reinforcement Learning

When an agent does not know the environment's transition dynamics beforehand, it must learn them through reinforcement learning (RL). In a flat environment, an agent must visit every state-action pair multiple times to guarantee convergence. In a factored environment, the agent can learn the transition model for each factor independently.

Benjamin Van Roy et al. proved in Near-optimal Reinforcement Learning in Factored MDPs that algorithms exploiting this structure (such as PSRL and UCRL-Factored) achieve near-optimal regret bounds scaling with the number of local parameters rather than the global state space. Similarly, Xiaoyu Chen et al. demonstrated in Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL that exploiting the independent evolution of state subspaces yields tighter regret bounds and allows complex constraints (like knapsack problems) to be solved efficiently.

This local parameter estimation drastically reduces the amount of data needed to act safely. Thiago D. Simão showed in Safe and Sample-Efficient Reinforcement Learning Algorithms for Factored Environments that a factored approach can safely improve a baseline policy using up to 20x fewer samples than traditional flat safe RL methods.

Flat Learning:     [ Total State Space (2^n) ]  --> Requires Exponential Samples

                      /---> [ Factor 1 (2^k) ]  ---\
Factored Learning:   ---->  [ Factor 2 (2^k) ]  ----> Requires Polynomial Samples
                      \---> [ Factor n (2^k) ]  ---/

Learning the Causal Structure

What if the underlying factored structure—the causal graph of which variable affects which—is unknown? Olivier Sigaud et al. addressed this in Learning the structure of Factored Markov Decision Processes in reinforcement learning problems, showing that agents can learn these structural dependencies on the fly, minimizing memory footprints. To accelerate this discovery, Mirco Mutti et al. developed a method in Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning that incorporates partial causal graphs as prior knowledge, hierarchically learning both the environment's structure and its transition parameters simultaneously.

Even when the agent only has access to high-dimensional, unstructured observations (like raw pixels), factoring remains possible. Dipendra Misra et al. introduced FactoRL in Provable Rich Observation Reinforcement Learning with Combinatorial Latent States. Their algorithm uses noise-contrastive learning to decode raw observation "atoms" into an underlying combinatorial latent state space, proving that sample complexity can scale polynomially with the number of latent factors rather than exponentially with the observation space.

Applications Across Domains

Because physical and logical systems are naturally modular, factored modeling provides significant computational leverage across a wide range of applications:

By recognizing and exploiting the fact that variables in complex systems interact locally rather than globally, factored state representations transform intractable exponential planning problems into structured, scalable computations.

Key Foundational Work

Direct value-approximation for factored MDPs (2001) — contributed 1 concept elements to this direction.
Probabilistic Propositional Planning: Representations and Complexity (1997) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_factored_state_representation_71eac482,
  title = {factored state representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/factored-state-representation/rdr_71eac482ab544c4fb342e62b77a6fb7f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_factored_state_representation_71eac482_v1,
  title = {factored state representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/factored-state-representation/rdr_71eac482ab544c4fb342e62b77a6fb7f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake