Factorization and Structure Learning in Reinforcement Learning

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 114 papers16 conceptsfrozen 2026-10-04

Standard Reinforcement Learning (RL) agents often struggle with the "curse of dimensionality." As the number of variables in an environment increases, the state space grows exponentially, making it impossible for an agent to explore every corner or learn a comprehensive value function.

To solve this, researchers have moved toward Factored Markov Decision Processes (FMDPs). The core intuition is simple: while the world is complex, most things don't affect everything else simultaneously. By decomposing a massive state space into smaller, interacting components, agents can learn faster, generalize better, and solve problems that are otherwise computationally intractable.

Decomposing the State Space

In a traditional MDP, the state is treated as a single "black box" identifier. In a Factored MDP, the state is represented as a vector of variables. The power of this approach lies in the transition dynamics. If you are playing a game, the position of a "key" might only change if the "player" interacts with it; it doesn't depend on the color of the background or the score.

Olivier Sigaud, Thomas Degris, and Pierre-Henri Wuillemin demonstrated in Learning the structure of Factored Markov Decision Processes in reinforcement learning problems that agents can learn these structural dependencies on the fly. Instead of assuming every variable depends on every other variable, the agent builds a model of which variables actually influence one another, allowing it to navigate massive state spaces that tabular methods cannot touch.

Beyond Perfect Independence

Early work in FMDPs often assumed that state variables transitioned independently or followed a strictly predefined structure. However, real-world environments are rarely so clean. Variables are often correlated, and the underlying "graph" of dependencies is unknown.

Recent theoretical work has pushed these boundaries. In Polynomial Time Reinforcement Learning in Correlated FMDPs with Linear Value Functions, Siddartha Devic, Zihao Deng, and Brendan Juba provided the first polynomial-time algorithm for RL in factored states where variables are correlated. This removes the need for an "oracle" to explain the world to the agent, moving us closer to agents that can autonomously discover how a complex system is wired.

Furthermore, Chenbei Lu and colleagues in Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization introduced the concept of Approximate Factorization. They showed that even if a system isn't perfectly decomposable, we can use graph-coloring-based sampling to treat it as such, achieving near-optimal sample complexity. This suggests that "good enough" decomposition is a powerful tool for scaling RL to high-dimensional tasks.

Object-Centric Models and Task Logic

The idea of factorization isn't limited to raw state variables; it also applies to how we define tasks and objects.

  1. Object-Centric Priors: Instead of looking at pixels, agents can look at "objects." Conor Heins and the team behind AXIOM: Learning to Play Games in Minutes with Expanding Object-Centric Models use Bayesian priors to build expanding world models. By focusing on objects and their interactions, AXIOM masters games in a fraction of the time required by deep RL models like DreamerV3.
  2. Reward Machines: Tasks themselves can be factored. Rodrigo Toro Icarte and Sheila A. McIlraith introduced Reward Machines in Using Reward Machines for High-Level Task Specification and Decomposition in Reinforcement Learning. These provide a structured, state-based representation of rewards, allowing agents to decompose a complex goal (like "make coffee") into a sequence of logical sub-steps.

Structural Efficiency in Recommendations

This structural lens also solves practical engineering problems in recommendation systems. When recommending a "slate" (a grid of items), the number of possible combinations is astronomical. David Arbour, Georgios Theocharous, and Nikos Vlassis developed SUnO in Distributional Off-Policy Evaluation for Slate Recommendations. By exploiting the underlying structure of how users interact with lists—rather than treating every possible slate as a unique action—they avoid combinatorial explosion and provide much more accurate risk assessments.

Summary

The transition from "black-box" RL to "structured" RL represents a shift toward efficiency and interpretability. By leveraging factorization—whether through state variables, object-centric models, or reward logic—agents can ignore irrelevant information and focus on the causal drivers of their environment. The current frontier lies in autonomous structure learning: moving away from human-designed factorizations toward agents that can look at a complex world and figure out for themselves how to break it apart.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_factorization_and_structure_learning_in__77ce06dd,
  title = {Factorization and Structure Learning in Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/factorization-and-structure-learning-in-reinforcement-learning/rdr_77ce06ddda4c40f895dea183ade10226},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_factorization_and_structure_learning_in__77ce06dd_v1,
  title = {Factorization and Structure Learning in Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/factorization-and-structure-learning-in-reinforcement-learning/rdr_77ce06ddda4c40f895dea183ade10226/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}