The Planning Bottleneck in Structured 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 116 papers21 conceptsfrozen 2026-10-04

In the ideal vision of model-based reinforcement learning (RL), an agent acts like a scientist: it observes the world, builds a mathematical model of how things work, and then uses that model to calculate the best possible path forward. For years, research has focused on the first half of this equation—statistical efficiency. We have become remarkably good at learning complex environment dynamics with very few samples by exploiting structure.

However, a recurring theme across recent literature reveals a stark reality: even if an agent perfectly understands its environment, the act of "thinking" (planning) is often computationally impossible. This creates a "planning bottleneck" where our ability to learn a model far outpaces our ability to use it.

The Statistical Success: Learning with Structure

To avoid the "curse of dimensionality," researchers have developed representations that break the world into smaller, manageable pieces. Instead of treating every possible configuration of the universe as a unique state, we look for patterns:

These papers share a common victory: they prove that the sample complexity of learning a structured world is low.

The Computational Wall: Why Planning is Hard

The "bottleneck" appears once the model is learned. As Thomas J. Walsh notes in Exploring compact reinforcement-learning representations with linear regression, even when model learning is guaranteed to be efficient, the subsequent planning phase often remains a computational nightmare.

The reason is simple but devastating: finding an optimal policy in a factored or structured state space is generally NP-hard.

In Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting, Ziping Xu and Ambuj Tewari highlight this by designing "oracle-efficient" algorithms. These algorithms are "efficient" only if you assume the existence of a magical "planning oracle" that can solve the model. In reality, those oracles are often computationally intractable. This gap is even more pronounced in Bayesian settings; Mirco Mutti and Marcello Restelli point out in Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learning that an agent using posterior sampling must re-solve this NP-hard planning problem for every new model it samples.

The Phase Transition of Lookahead

One might assume that giving an agent more information about the future would make planning easier. However, Hugo Richard and Vianney Perchet recently discovered a startling "phase transition" in On the hardness of RL with Lookahead.

They found that while planning with a one-step lookahead (knowing where you'll land next) is solvable in polynomial time, planning with just two or more steps of lookahead immediately becomes NP-hard. This suggests that the difficulty isn't just about the size of the state space, but about the inherent complexity of multi-step reachability in structured graphs.

Bridging the Gap

The current frontier of this research area involves finding specific environmental structures that might "break" the NP-hardness of planning.

For instance, Tom Yan and Chicheng Zhang explore in Stackelberg Learning with Outcome-based Payment how incentive structures (like payments) can sometimes make learning statistically efficient in cooperative scenarios, even when the underlying reachability constraints in Directed Acyclic Graphs (DAGs) remain computationally difficult.

The takeaway for the field is clear: we have largely solved the problem of how to learn a structured world. The next great challenge is figuring out how to act in one without waiting an eternity for the plan to finish.

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_the_planning_bottleneck_in_structured_re_17c38a9a,
  title = {The Planning Bottleneck in Structured Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-planning-bottleneck-in-structured-reinforcement-learning/rdr_17c38a9a948842b2a6fcbb705116cfe8},
  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_the_planning_bottleneck_in_structured_re_17c38a9a_v1,
  title = {The Planning Bottleneck in Structured Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-planning-bottleneck-in-structured-reinforcement-learning/rdr_17c38a9a948842b2a6fcbb705116cfe8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}