Why Realizability and Coverage Fail in Offline Reinforcement Learning

16 concepts8 papers1 proposal

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:

  1. 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.
  2. 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.
  3. 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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_realizability_coverage_insufficiency_0f948ac3,
  title = {realizability-coverage insufficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/realizability-coverage-insufficiency/rdr_0f948ac3148c487f8c01db13e820f72c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_realizability_coverage_insufficiency_0f948ac3_v1,
  title = {realizability-coverage insufficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/realizability-coverage-insufficiency/rdr_0f948ac3148c487f8c01db13e820f72c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake