Structure Learning for Sample Efficient Reinforcement Learning

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

Version 1 of 119 papers25 conceptsfrozen 2026-10-04

In traditional Reinforcement Learning (RL), agents often treat the world as a "flat" state space. If an environment has $n$ binary variables, the agent faces $2^n$ possible states. This exponential explosion—the curse of dimensionality—makes learning impossible for even moderately complex systems.

However, the physical world is rarely a dense web of total dependence. A robot’s battery level might depend on its motor activity, but it is likely independent of the color of the wall it is passing. This insight is the foundation of Factored Markov Decision Processes (Factored MDPs). By exploiting the modular structure of an environment, researchers aim to reduce the complexity of learning from exponential to polynomial.

The Power of Factorization

The core idea, as explored by Ian Osband and Benjamin Van Roy in Near-optimal Regret Bounds for Reinforcement Learning in Factored MDPs, is that the transition dynamics of a large system can often be decomposed. Instead of learning one massive transition matrix, the agent learns several small ones—one for each state variable.

If each variable only has a small number of "parents" (other variables that influence it), the agent only needs to observe enough data to fill these small local tables. Yi Tian, Jian Qian, and Suvrit Sra demonstrate in Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes that this modularity allows RL to scale to massive environments that would otherwise be intractable.

The Hidden Graph Problem

While the benefits of factorization are clear, most early theory relied on a significant assumption: the agent already knows the "dependency graph"—the map of which variables affect which. In practice, this is rarely true. An agent dropped into a new factory or a chemical plant doesn't know the underlying causal links.

This creates a "chicken and egg" problem. To learn the transitions efficiently, the agent needs the structure; but to find the structure, the agent must observe the transitions. Ambuj Tewari and Ziping Xu highlight this in Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting, noting that discovering the causal structure and the transition probabilities simultaneously is the primary hurdle for practical deployment.

Learning Structure from Scratch

To solve this, researchers have developed algorithms that treat the structure itself as something to be estimated. A landmark approach is LSE-RMax, introduced by Doran Chakraborty and Peter Stone in Structure Learning in Ergodic Factored MDPs without Knowledge of the Transition Function's In-Degree.

Unlike previous methods that required knowing the maximum number of parents for each variable, LSE-RMax discovers the structure by systematically testing dependencies. It balances exploration and exploitation not just over states, but over possible models of the world. This allows the agent to master high-dimensional environments without any prior structural knowledge, provided it has a sufficiently long planning horizon.

Generalization and Safety

Structure learning isn't just about speed; it's about safety and reliability. When an agent understands the independent factors of a system, it can generalize its experiences more effectively.

In Safe Policy Improvement with Baseline Bootstrapping in Factored Environments, Thiago D. Simão and Matthijs T. J. Spaan show that by exploiting factored dynamics, an agent can achieve safe performance gains with 10 to 20 times fewer samples than "flat" methods. By recognizing that a certain action only affects a specific subset of variables, the agent can confidently predict outcomes in new, unvisited states that share those same local factors.

Beyond Simple MDPs

The push toward structure learning extends into even more complex domains:

By moving from learning "what happens next" to learning "what causes what," this research direction provides the theoretical tools necessary for agents to operate in the high-dimensional, modular reality of the physical world.

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_structure_learning_for_sample_efficient__1782eb0d,
  title = {Structure Learning for Sample Efficient Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structure-learning-for-sample-efficient-reinforcement-learning/rdr_1782eb0de71846c28646c3834e591344},
  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_structure_learning_for_sample_efficient__1782eb0d_v1,
  title = {Structure Learning for Sample Efficient Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/structure-learning-for-sample-efficient-reinforcement-learning/rdr_1782eb0de71846c28646c3834e591344/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}