Scaling Reinforcement Learning via Factored State Representations

This direction is merged into another direction: curse of dimensionality (state space explosion). Its last version stays readable and citable here.

Version 1 of 115 papers17 conceptsfrozen 2026-10-04

In traditional Reinforcement Learning (RL), we often treat the environment as a "black box" of states. If a robot has 10 binary sensors, it can be in $2^{10}$ (1,024) possible states. If it has 20 sensors, that number jumps to over a million. This exponential explosion is the "Curse of Dimensionality," and it makes standard RL algorithms—which try to learn something about every possible state—practically useless for complex, real-world systems.

However, the physical world is rarely a chaotic soup of independent states. Most of the time, the world is factored. If you move a robot's left arm, it usually doesn't affect the temperature sensor in its right leg. By exploiting this modularity, a growing body of research shows that we can learn to act optimally with a fraction of the data previously thought necessary.

The Intuition: Local Transitions

The core insight behind Factored Markov Decision Processes (FMDPs) is that the state of the world can be broken down into a set of variables, and each variable's next state depends only on a small subset of other variables (its "parents").

Instead of trying to learn a massive transition matrix $P(s' | s, a)$ that maps every global state to every other global state, we learn local transition models for each variable. As Chenbei Lu and colleagues explain in Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization, this shifts the sample complexity from scaling with the size of the entire state space to scaling with the size of the largest individual component.

From Exponential to Linear Regret

The primary metric for RL efficiency is "regret"—the difference between the reward an agent actually gets and the reward an optimal agent would have received. In a "flat" MDP, regret typically grows with the square root of the number of states. In high-dimensional spaces, this is catastrophic.

Ian Osband and Benjamin Van Roy demonstrated in Near-optimal Regret Bounds for Reinforcement Learning in Factored MDPs that if we exploit factored structure, regret scales linearly with the number of components and the complexity of their local interactions. This means that adding a new, independent sensor to a robot only adds a constant amount of learning time, rather than doubling it.

Recent work has pushed these bounds even further. Yi Tian and Suvrit Sra achieved Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes, effectively proving that agents can ignore the total size of the state space entirely, focusing only on the "density" of the interactions.

Learning the Structure on the Fly

A major hurdle in applying these ideas is that we don't always know the "dependency graph" of the world. We might know the robot has 20 sensors, but we don't know which ones influence each other.

Early work by Alexander L. Strehl and Michael L. Littman in Efficient Structure Learning in Factored-State MDPs introduced the SLF-Rmax algorithm. This approach treats structure discovery as an online prediction problem. The agent starts with no knowledge of the dependencies, but as it interacts with the environment, it uses "optimism under uncertainty" to simultaneously map out the structure and solve the task.

Safety and Practicality

Factoring isn't just about speed; it's also about safety. In many industrial applications, we cannot afford to let an agent "explore" randomly because it might break the system.

Thiago D. Simão has shown that factored representations are a powerful tool for Safe Policy Improvement (SPIBB). In Safe and Sample-Efficient Reinforcement Learning Algorithms for Factored Environments, Simão demonstrates that by exploiting independent structures, an agent can safely improve upon a baseline policy using 20x fewer samples than traditional methods. Because the agent understands that certain variables are independent, it can generalize its safety constraints from one part of the state space to another, avoiding the need to "test" every possible state-action pair.

Beyond Perfect Independence

The most recent frontier in this research involves Approximate Factorization. In the real world, variables are rarely perfectly independent; there is often some "leakage" or weak correlation between distant components.

The work by Chenbei Lu and Adam Wierman addresses this by allowing for "near-independence." Their framework uses graph-coloring strategies to sample the environment efficiently even when the factorization is only an approximation. This suggests that the benefits of factored RL—polynomial scaling and sample efficiency—can be maintained even in messy, real-world environments that don't fit into neat, modular boxes.

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_scaling_reinforcement_learning_via_facto_8633c406,
  title = {Scaling Reinforcement Learning via Factored State Representations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-reinforcement-learning-via-factored-state-representations/rdr_8633c406baa6410ea0d64c456c98e9da},
  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_scaling_reinforcement_learning_via_facto_8633c406_v1,
  title = {Scaling Reinforcement Learning via Factored State Representations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-reinforcement-learning-via-factored-state-representations/rdr_8633c406baa6410ea0d64c456c98e9da/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}