Statistical Limits of Offline Reinforcement Learning

This direction is merged into another direction: Bellman completeness, realizability-coverage insufficiency. Its last version stays readable and citable here.

Version 1 of 112 papers25 conceptsfrozen 2026-10-04

In supervised learning, the recipe for success is well-understood: if your model is expressive enough to contain the true solution (realizability) and your training data covers the distribution you care about (coverage), you can learn effectively. It is tempting to assume that offline Reinforcement Learning (RL) follows the same rules. If we have a dataset of transitions and a function class that can represent the optimal value function, shouldn't we be able to find it?

Recent theoretical work has revealed a sobering reality: in offline RL, these two conditions are fundamentally insufficient. Even with perfect coverage and a realizable model, the sequential nature of the decision process can force the sample complexity to scale exponentially with the planning horizon.

The Failure of the Supervised Intuition

The core difficulty in offline RL is that we must evaluate policies without the ability to interact with the environment. We rely on a static dataset to "stitch together" a path to high rewards.

In a landmark study, Ruosong Wang, Dean Foster, and Sham M. Kakade demonstrated that standard linear function approximation—where the value function is a linear combination of known features—does not guarantee efficiency. They showed that even if the true value function is linear and the data spans the entire feature space, the number of samples required to find a good policy can still grow exponentially with the horizon $H$ (Wang et al., 2020).

This happens because, unlike in regression, errors in RL propagate through time. A small mismatch in value estimation at step $t+1$ can lead to a catastrophic miscalculation of the optimal action at step $t$.

The Barrier of Over-Coverage

One might assume that the problem lies in "holes" in the data. However, Dylan J. Foster, Akshay Krishnamurthy, and David Simchi-Levi identified a more counterintuitive barrier: "over-coverage."

In their analysis, they proved that if a dataset contains information about states that are reachable but irrelevant to the optimal path, it can actually confuse the learner (Foster et al., 2021). If the function class is not powerful enough to distinguish between critical state transitions and these "distractor" states, the learner may fail to generalize. This forces the sample complexity to scale with the total size of the state space rather than the complexity of the function class, defeating the purpose of using function approximation in the first place.

Why Trajectories Don't Save Us

A common hypothesis was that the "broken" nature of transition-based datasets (i.i.d. state-action-reward-next_state tuples) was the culprit. If we instead had access to full trajectories—complete sequences of actions and rewards—perhaps the temporal structure would resolve the ambiguity.

Alexander Rakhlin, Zeyu Jia, and Ayush Sekhari recently settled this question with a definitive "no." They proved that even with full trajectory data, value function realizability and bounded coverage are still insufficient for polynomial sample complexity (Rakhlin et al., 2024).

The researchers introduced the aggregated concentrability coefficient to explain this. The problem is not just whether the data covers the states, but whether the function class can distinguish the transitions between those states. If the function class "aggregates" states in a way that blurs the distinction between a good transition and a bad one, the learner faces an exponential wall.

Moving Toward Stronger Assumptions

If realizability and coverage are not enough, what is? The research community is currently converging on two main paths to bypass these barriers:

  1. Bellman Completeness: This is a much stronger condition than realizability. While realizability only requires the optimal value function to be in our class, Bellman completeness requires that applying the Bellman operator to any function in our class results in another function within that same class. This prevents the "error compounding" that leads to exponential complexity.
  2. Clever Constraints: Some researchers are looking for algorithmic ways to relax these assumptions. Asuman E. Ozdaglar and Kaiqing Zhang have revisited the Linear Programming (LP) framework for RL. By using occupancy constraints instead of standard regularization, they show it is possible to achieve optimal sample complexity while relaxing some of the more restrictive completeness requirements (Ozdaglar et al., 2023).

The shift in the field is clear: we can no longer treat offline RL as a simple extension of supervised learning. Success requires a delicate balance between the structure of the environment, the expressivity of the model, and the specific way the data covers the state space.

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_statistical_limits_of_offline_reinforcem_2aa05f89,
  title = {Statistical Limits of Offline Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/statistical-limits-of-offline-reinforcement-learning/rdr_2aa05f89231044a781e125d66b39fb0b},
  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_statistical_limits_of_offline_reinforcem_2aa05f89_v1,
  title = {Statistical Limits of Offline Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/statistical-limits-of-offline-reinforcement-learning/rdr_2aa05f89231044a781e125d66b39fb0b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}