The Function Approximation Dilemma
When scaling reinforcement learning (RL) to complex, real-world environments, we must abandon tabular representations in favor of function approximation, such as linear models or deep neural networks. By choosing a specific function class $\mathcal{F}$, we restrict the set of value functions or policies our algorithm can represent.
To guarantee that an algorithm can successfully learn, theorists traditionally rely on structural assumptions about how well this chosen class $\mathcal{F}$ interacts with the underlying environment. Two central concepts define this landscape: realizability and Bellman completeness. Understanding the distinction between them—and why the latter is both powerful and deeply restrictive—is key to modern theoretical RL.
Realizability vs. Bellman Completeness: An Intuitive Contrast
To build intuition, think of a function class $\mathcal{F}$ as a geometric space (a surface or a subspace) and the true environment dynamics as a set of rules that transform functions.
- Realizability is a static property. It asserts that the ultimate target function we want to find—such as the optimal action-value function $Q^*$—lives inside our function class $\mathcal{F}$. If our class is rich enough to contain the truth, it is realizable. As noted by Alekh Agarwal et al. in Design Considerations in Offline Preference-based RL, while this assumption is standard in theoretical frameworks, limited model capacity in practice frequently violates it, leading to model misspecification.
- Bellman Completeness (often called Bellman closure) is a dynamic property. It requires that for any function $f$ inside our class $\mathcal{F}$, applying the environment's Bellman operator $\mathcal{T}$ results in a function $\mathcal{T}f$ that also lies entirely within $\mathcal{F}$. In other words, the function class is perfectly closed under the transition and reward dynamics of the environment.
Realizability:
[ Function Class F ]
o (Optimal Q*)
Bellman Completeness:
[ Function Class F ]
f --------(Bellman Update T)-------> Tf (Still inside F)
Why is Bellman completeness so much stronger? In value iteration algorithms (like Q-learning or Least-Squares Value Iteration), the agent updates its value estimates by repeatedly applying the Bellman operator. If $\mathcal{F}$ is not Bellman complete, the updated function $\mathcal{T}f$ will escape the boundaries of $\mathcal{F}$. The algorithm must then project $\mathcal{T}f$ back into $\mathcal{F}$ to represent it.
Each projection step introduces a small approximation error. Without completeness, these projection errors can compound exponentially over the decision horizon, causing the learning process to diverge completely.
The Real-World Mismatch
Despite its mathematical convenience for proving convergence, Bellman completeness is an exceptionally fragile assumption. As emphasized by Haque Ishfaq et al. in Randomized Exploration in Reinforcement Learning with General Value Function Approximation and Yaqi Duan et al. in Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces, deep neural networks are virtually never closed under Bellman updates in practice. Even simple linear function classes fail to satisfy completeness if the environment's transitions do not perfectly align with the predefined features.
This stark divergence between theory and reality has catalyzed a major research direction: designing algorithms that can learn efficiently under weaker, more realistic assumptions.
Bypassing Completeness with Realizability Alone
Can we achieve sample-efficient learning if we only assume that the optimal function is representable (realizability), without assuming the class is closed under updates?
For years, this was considered a major open problem in batch (offline) RL, with many theorists conjecturing it was information-theoretically impossible. However, Tengyang Xie et al. in Batch Value-function Approximation with Only Realizability shattered this barrier by introducing the Batch Value-Function Tournament (BVFT) algorithm. The authors proved that polynomial sample complexity is indeed achievable under value-function realizability alone, bypassing the need for Bellman completeness.
Another way to bridge this gap is by leveraging environmental margins. Jinglin Chen et al. in Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps demonstrated that if the environment exhibits an "action gap"—a clear separation in value between the optimal action and sub-optimal ones—pessimistic offline RL algorithms can successfully find near-optimal policies under value and density-ratio realizability, even when Bellman completeness is entirely absent.
Managing Function Class Misspecification
In practical applications, even pure realizability is a luxury. True reward structures and transition dynamics are often far more intricate than our models assume. When function classes are misspecified, algorithms must be robust enough to degrade gracefully rather than fail catastrophically.
In the context of contextual bandits and resource-constrained settings, Yuxuan Han et al. in Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles and Mengxiao Zhang et al. in Efficient Contextual Bandits with Uninformed Feedback Graphs have analyzed how reduction-to-regression frameworks behave when the true mapping from context to rewards lies outside the hypothesis space, highlighting the ongoing need for algorithms that tolerate approximation errors. To combat this in full RL settings, Fei Feng et al. in Provably Correct Optimization and Exploration with Non-linear Policies developed frameworks that maintain strong performance guarantees even when the underlying value function cannot be perfectly captured by the approximation architecture.
Algorithmic Engineering within Completeness
While relaxing these assumptions is a primary goal, understanding how to computationally exploit Bellman completeness when it does hold (or is closely approximated) remains highly valuable. For instance, in environments with large action spaces, standard exploration can cause exponential error amplification. Runzhe Wu et al. in Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics resolved this for deterministic dynamics under linear Bellman completeness by designing an algorithm that strategically injects exploration noise only into the null space of the gathered data, ensuring both statistical and computational efficiency.
By mapping out the boundaries between realizability, completeness, and misspecification, this body of research provides the theoretical foundation necessary to make value-based reinforcement learning robust, efficient, and applicable to deep architectures.