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:
- Factored MDPs: Ian Osband and Benjamin Van Roy demonstrated in Near-optimal Regret Bounds for Reinforcement Learning in Factored MDPs that if we model local interactions rather than global states, we can achieve near-optimal regret bounds. We can learn how a massive system works by only watching how its individual components interact.
- Object-Oriented Representations: Carlos Diuk and Michael L. Littman proposed Object-Oriented MDPs, allowing agents to perceive the world as objects (like "keys" and "doors") rather than raw variables. This "relational bias" allows for orders-of-magnitude faster learning.
- KWIK Learning: Alexander L. Strehl and Michael Littman formalized the "Knows What It Knows" (KWIK) framework in Online Linear Regression and Its Application to Model-Based Reinforcement Learning, proving that agents can systematically explore and learn linear dynamics with a polynomial number of samples.
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.