Statistical Limits of Bellman Completeness in Reinforcement Learning

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2184 papers268 conceptsfrozen 2026-10-04

In reinforcement learning (RL), we often assume that if our model is "big enough" to represent the truth, we should eventually find it. This property is called realizability: the assumption that the optimal value function $Q^*$ resides within our chosen function class $\mathcal{F}$.

However, a growing body of theoretical research suggests that for many RL problems—especially in the offline setting—realizability is a dangerously weak guarantee. To ensure an algorithm actually converges without requiring an astronomical amount of data, researchers often have to invoke a much stricter condition: Bellman completeness.

The Iterative Error Trap

To understand the difference, we have to look at how RL algorithms actually "think." Most value-based methods don't find $Q^*$ in one giant leap. Instead, they use the Bellman operator $\mathcal{T}$ to iteratively improve their estimates. If you have a current guess $f$, your next guess is $\mathcal{T}f$.

The problem is that even if your function class $\mathcal{F}$ contains the final answer ($Q^* \in \mathcal{F}$), it might not contain the intermediate steps. If $\mathcal{T}f$ falls outside of $\mathcal{F}$, the algorithm must "project" that result back into the class. This projection introduces a tiny approximation error.

In supervised learning, small errors usually stay small. But in RL, we "bootstrap"—we use our own noisy guesses to update our future guesses. As Ruosong Wang and Sham M. Kakade demonstrate in What are the Statistical Limits of Offline RL with Linear Function Approximation?, without stronger assumptions, these projection errors can grow exponentially. The algorithm "diverges," spiraling away from the truth even though the truth was technically representable by the model.

Why Completeness is the Standard (and the Problem)

To stop this spiral, theorists use Bellman completeness (or Bellman closure). This assumption requires that for any function $f$ in our class $\mathcal{F}$, the updated function $\mathcal{T}f$ must also be in $\mathcal{F}$. If this holds, there is no projection error during the update, and the "deadly triad" of bootstrapping, function approximation, and off-policy learning is tamed.

The catch is that Bellman completeness is incredibly restrictive. As Masatoshi Uehara and Wen Sun point out in Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage, it is almost impossible to verify if a deep neural network satisfies this condition in a complex environment. If the environment's physics are slightly more complex than the network's architecture, completeness is violated.

Bridging the Gap

The current frontier of RL theory is finding ways to survive without full completeness. Researchers are attacking this from several angles:

  1. Relaxed Completeness: Andrea Zanette has proposed an "incompleteness factor" ($\beta$) in When is Realizability Sufficient for Off-Policy Reinforcement Learning?. This work suggests that as long as the misalignment between the function class and the Bellman operator is bounded, we can still achieve zero error, though learning might be slower.
  2. Algorithmic Stability: Some methods try to bypass the Bellman update entirely. Zhaoyi Zhou and Abhishek Gupta introduced MBRCSL, which uses model-based "trajectory stitching" to avoid the instabilities of iterative Q-learning.
  3. Information-Theoretic Limits: For a long time, it was conjectured that learning with only realizability was impossible. However, Tengyang Xie and Nan Jiang proved in Batch Value-function Approximation with Only Realizability that sample-efficient learning is possible under minimal assumptions, though the resulting algorithms (like BVFT) are often computationally daunting.
  4. Hybrid Learning: Another strategy is to supplement "brittle" offline data with active online exploration. Yifei Zhou and Wen Sun show in Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient that even a small amount of online interaction can compensate for the lack of Bellman completeness in the offline dataset.

Summary of the Hierarchy

To build intuition, we can view the assumptions on a spectrum of "strength":

  • Realizability (Weakest): "The answer is in my search space." (Often leads to exponential sample complexity).
  • Exploration/Coverage: "I have seen enough of the world to distinguish the answer from the noise."
  • Bellman Completeness (Strongest): "My search space is perfectly aligned with the environment's logic." (Ensures polynomial sample complexity and stability).

The goal of modern research is to move the "provably efficient" line as far toward the "Realizability" end of the spectrum as possible, making RL more robust to the imperfect models we use in the real world.

Papers in this version

Showing 60 of 184 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 277 papers
  2. Version 1 · 2026-10-04 · 184 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_bellman_completeness_5dc6b82a,
  title = {Bellman completeness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bellman-completeness/rdr_5dc6b82a57264164b94a538687610a3c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_statistical_limits_of_bellman_completene_5dc6b82a_v1,
  title = {Statistical Limits of Bellman Completeness in Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/statistical-limits-of-bellman-completeness-in-reinforcement-learning/rdr_5dc6b82a57264164b94a538687610a3c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}