State Space Reduction in Reinforcement Learning

415 concepts384 papers2 proposals

In tabular reinforcement learning (RL), the environment is treated as a discrete grid of possibilities. If you add a single binary variable to the environment, the state space doubles. Add thirty variables, and the state space expands by a factor of a billion. This exponential explosion—the curse of dimensionality—makes naive exploration and value estimation mathematically impossible. An agent attempting to learn an optimal policy by randomly wandering through a high-dimensional space will almost never encounter a meaningful reward signal, let alone map out the transitions between states.

To make RL practical for complex tasks like robotics, network optimization, or multi-agent coordination, we must reduce the effective size of the state space. Rather than forcing an agent to digest raw, high-dimensional inputs monolithically, modern approaches compress, factor, or localize the state space. They exploit a fundamental truth: while the nominal dimensionality of an environment may be massive, the intrinsic dimensionality required to make optimal decisions is usually remarkably small.

State Abstraction as Lossy Compression

The most direct way to combat state space explosion is to ignore information that does not impact the current decision. This process is known as state abstraction.

In hierarchical reinforcement learning, Tom Dietterich formalized this intuition within the MAXQ framework (State Abstraction in MAXQ Hierarchical Reinforcement Learning). Dietterich proved that if an environment can be broken down into a hierarchy of sub-tasks, each sub-task can safely ignore state variables that do not affect its specific transitions or rewards. For example, a navigation sub-task needs to know the robot's coordinates but can completely ignore the payload's temperature. By proving convergence under these conditions, the author demonstrated how to turn computationally intractable problems into manageable ones.

This process can be mathematically framed as an information-theoretic problem. In State Abstraction as Compression in Apprenticeship Learning, the authors demonstrate that grouping states together is equivalent to lossy compression. By maximizing the compression of the state space while preserving the information necessary to predict rewards and transitions, agents can learn optimal policies in highly simplified abstract spaces without losing performance.

Sometimes, a simple change of perspective achieves this compression directly. For instance, Bumgeun Park et al. showed that switching from an absolute coordinate system to a robot-centric relative coordinate system slashed the state space dimensionality by 60% for AI soccer robots. This simple geometric abstraction accelerated training by removing redundant spatial configurations from the agent's consideration.

Factoring and Decomposing State Spaces

When state variables cannot be entirely ignored, they can often be uncoupled. Monolithic RL algorithms attempt to learn a joint probability distribution over all state variables simultaneously. If an environment has $N$ variables, the agent must map transitions across an $N$-dimensional space.

Factored Markov Decision Processes (MDPs) break this joint distribution into a product of smaller, conditional distributions. Andres C. Rodriguez et al. applied this to Partially Observable MDPs (POMDPs) by utilizing factored, approximate belief states (Reinforcement Learning Using Approximate Belief States). By marginalizing out weak correlations between state variables, the authors prevented the function approximator from getting lost in a high-dimensional belief space, reducing training times from hours to minutes.

Monolithic State Space:  [X, Y, Theta, Velocity, Target_X, Target_Y] ---> Intractable Joint Distribution

Factored State Space:    [X, Y, Velocity] x [Theta] x [Target_X, Target_Y] ---> Independent Low-Dimensional Trackers

Similarly, Marc G Bellemare introduced recursively decomposable factorizations to scale model-based RL to complex visual environments like Atari 2600 games (Bayesian Learning of Recursively Factored Environments). Instead of modeling the entire screen at once, the environment is modeled as a tree of localized interactions. This allows the agent to predict future states without computing an intractable joint distribution over all pixels. This concept of internal knowledge reuse is echoed by Jaak Simm et al., who grouped similar objects into mixture components to share transition models within a single task, drastically reducing sample complexity in environments with numerous interacting entities.

Learning Low-Dimensional Latent Manifolds

In modern deep RL, inputs often arrive as raw pixels or dense point clouds. While these inputs contain thousands of dimensions, the underlying physical reality they represent is highly constrained. A robot arm moving through space might generate a high-resolution video stream, but its true physical state is fully described by a few joint angles.

To exploit this, researchers use representation learning to map high-dimensional observations into low-dimensional latent spaces. Niko Wilbert demonstrated that Hierarchical Slow Feature Analysis (SFA) can extract slowly varying signals from raw video streams (Reinforcement Learning on Slow Features of High-Dimensional Input Streams). Because physical properties (like an object's position) change slowly over time compared to individual pixel values, isolating these slow features provides the RL agent with a compact, low-dimensional state representation that performs as well as ground-truth coordinates.

For geometric data, Yoonyoung Cho et al. developed CORN (CORN: Contact-based Object Representation for Nonprehensile Manipulation of General Unseen Objects), which uses a lightweight transformer to map high-dimensional point clouds into a compact representation of potential contact surfaces. This bypasses the computational bottleneck of processing raw spatial data, enabling efficient closed-loop manipulation policies.

In goal-conditioned settings, Anders Jonsson et al. proposed learning a "Minimum Action Distance" (MAD) embedding from offline data. In this latent space, the Euclidean distance directly reflects the minimum number of actions needed to transition between states, simplifying planning by aligning the geometry of the latent space with the dynamics of the environment.

Localizing Search and Restricting Exploration

Another way to bypass the state space explosion is to change how and where the agent searches. Instead of trying to learn a global value function across the entire state space, algorithms can restrict their focus to critical regions.

Gregory Z. Grudic et al. introduced Boundary Localized Reinforcement Learning (BLRL) to exploit the fact that in many high-dimensional control systems, the optimal policy is relatively straightforward within a specific mode, and the real challenge lies at the boundaries between modes (Localizing Search in Reinforcement Learning). By restricting stochastic exploration strictly to these narrow boundaries, BLRL successfully scales to 128-dimensional spaces where global random exploration fails completely.

Alternatively, if prior knowledge is available, the agent can avoid exploring the state space altogether. Mohammad Gheshlaghi Azar et al. developed the Reinforcement Learning with Policy Advice (RLPA) framework, proving that an agent can achieve regret bounds completely independent of the size of the state and action spaces by dynamically selecting from a pre-defined set of heuristic policies (Regret Bounds for Reinforcement Learning with Policy Advice). By shifting the learning target from state-action values to policy selection, the complexity of the underlying environment becomes irrelevant to the agent's convergence rate.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 357 papers
  2. Version 1 · 2026-10-04 · 611 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_curse_of_dimensionality_state_space_expl_64187365,
  title = {curse of dimensionality (state space explosion)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-state-space-explosion/rdr_64187365717b41b09501e67e48edba53},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_curse_of_dimensionality_state_space_expl_64187365_v2,
  title = {curse of dimensionality (state space explosion)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/curse-of-dimensionality-state-space-explosion/rdr_64187365717b41b09501e67e48edba53/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake