In standard supervised learning, we rely on two intuitive pillars to guarantee that a model will learn successfully: realizability and coverage. Realizability means our function class is rich enough to contain the true target function. Coverage means our training dataset is diverse enough to span the input space. If you have both, a standard supervised learning model is guaranteed to generalize well.
It is highly tempting to assume this intuition carries over to offline Reinforcement Learning (RL). If our value function class can perfectly represent the optimal value function, and our logged dataset covers the state-action space of the optimal policy, shouldn't we be able to find the optimal policy efficiently?
A recent wave of theoretical insights has proven that this intuition is fundamentally wrong. In offline RL, even if you have perfect realizability and excellent data coverage, you can still hit an "exponential wall"—a requirement for a number of samples that scales exponentially with the time horizon.
The Exponential Wall
The breakdown of the supervised learning paradigm in offline RL was brought to light by several foundational hardness results. In What are the Statistical Limits of Offline RL with Linear Function Approximation?, Ruosong Wang et al. demonstrated that even when the optimal value functions are perfectly linear and the offline dataset covers all directions in the feature space, any learning algorithm can still face exponential sample complexity relative to the time horizon $H$.
This barrier is not an artifact of simple linear models. Akshay Krishnamurthy et al. extended this limitation to general function approximation in Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation. They proved that model realizability and good data coverage are fundamentally insufficient to prevent compounding errors from destabilizing the learning process.
The Mechanism of Failure: Compounding Errors
To understand why these two pillars fail, we have to look at how offline RL algorithms evaluate policies. Because the learner cannot interact with the environment to collect new data, it must evaluate a policy by bootstrapping—predicting the value of a state based on the predicted values of subsequent states.
This sequential dependency introduces a vulnerability that does not exist in standard supervised learning:
- The Bellman Projection Gap: Even if our function class contains the final optimal value function ($V^*$), it is usually not Bellman complete. This means that if you take a function from your class and apply the Bellman update operator to it, the resulting function might fall outside your class.
- The Projection Error: To keep the algorithm tractable, the algorithm must project this new function back into its function class. This projection introduces a tiny approximation error.
- Exponential Amplification: Because the data is fixed and the environment is sequential, these tiny projection errors propagate backward through the time horizon. Without environment interaction to correct the drift, the errors compound exponentially ($O(2^H)$), completely blinding the learner to the optimal policy.
State Indistinguishability and Coverage Degradation
Another way to visualize this failure mode is through the lens of state aggregation and feature resolution. If a function class is low-dimensional (like a linear model), it inherently groups different physical states together if they share similar features.
In Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data, Alexander Rakhlin et al. showed that if a function class cannot distinguish between critical state transitions, the effective coverage of the dataset degrades. Imagine a Markov Decision Process where two critical states look identical to your function class but lead to entirely different parts of the environment. Even if your dataset has high coverage globally, the function class's inability to resolve these distinct transitions allows errors to accumulate, hiding the optimal path in a cloud of statistical uncertainty.
The Problem Isn't Just Offline
This statistical barrier is so fundamental to sequential decision-making that it even bleeds into online learning. You might think that allowing an agent to explore would immediately dissolve this issue, but it turns out that linear representation alone still leaves agents vulnerable.
In An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap, Yuanhao Wang et al. demonstrated an exponential lower bound for online RL agents. Even when there is a clear "suboptimality gap"—meaning a distinct margin between the best action and the second-best action—and the optimal value function is perfectly linear, finding the policy can still take exponentially many samples. As emphasized by Nan Jiang et al. in A Few Expert Queries Suffices for Sample-Efficient RL with Resets and Linear Value Approximation, linear value approximation on its own is simply insufficient to guarantee efficient exploration in large state spaces.
How to Break the Wall
If realizability and coverage are insufficient, what actually works? The research community has identified several distinct strategies to bypass this exponential wall:
- Stronger Structural Assumptions: The most common theoretical escape hatch is assuming Bellman completeness, meaning the function class is entirely closed under the Bellman operator. This eliminates the projection error entirely, preventing the compounding error loop.
- Leveraging Trajectory Data: Rather than treating the offline dataset as a collection of isolated, independent transitions, algorithms can exploit the sequential structure of full trajectories. Volodymyr Tkachuk et al. demonstrated in Trajectory Data Suffices for Statistically Efficient Learning in Offline RL with Linear $q^\pi$-Realizability and Concentrability that trajectory data can provide enough structural constraint to achieve statistically efficient learning under weaker realizability conditions.
- State Revisiting and Resets: In online settings, giving the agent the ability to "save and reload" can break the complexity wall. Gen Li et al. showed in Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting that a limited state-revisiting mechanism allows the agent to clear up the ambiguity caused by linear approximations, turning an intractable problem into a polynomial one.
- Occupancy Constraints: Rather than modifying the data or assuming completeness, one can change the optimization framework. In Revisiting the Linear-Programming Framework for Offline RL with General Function Approximation, Asuman E. Ozdaglar et al. utilized a linear programming framework with clever occupancy constraints. By constraining the optimization based on the actual distribution of the offline data, they relaxed the need for full Bellman completeness while maintaining optimal sample complexity.
Key Foundational Work
What are the Statistical Limits of Offline RL with Linear Function Approximation? (2021) — contributed 4 concept elements to this direction.
Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation (2022) — contributed 4 concept elements to this direction.
An Exponential Lower Bound for Linearly Realizable MDP with Constant Suboptimality Gap (2021) — contributed 2 concept elements to this direction.