Bellman-consistent Pessimism for Offline Reinforcement Learning

Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, Alekh Agarwal

TL;DR

This paper introduces Bellman-consistent pessimism, a novel framework for offline reinforcement learning that avoids the pitfalls of overly conservative "point-wise" bonuses. By restricting pessimistic value estimates to functions that are consistent with the Bellman equations, the authors provide strong theoretical guarantees for general function approximation and achieve a significant $O(d)$ sample complexity improvement in linear settings—all while automatically adapting to the optimal bias-variance tradeoff.

What Problem Does This Paper Address?

Offline Reinforcement Learning (RL) is the art of learning a high-performing policy from a fixed, historical dataset without any further environment interaction. The central challenge is distribution shift: the policy we want to learn might visit states and actions that are poorly represented in our static dataset.

Standard RL algorithms often fail here because they "over-extrapolate," mistakenly believing that unexplored actions lead to high rewards. To fix this, researchers use pessimism—intentionally underestimating the value of poorly covered state-action pairs. However, existing "bonus-based" methods often require "full coverage" assumptions (the dataset must contain everything) or are overly pessimistic, effectively "blinding" the agent to potentially good policies. Furthermore, extending these methods to general function approximation (like deep neural networks) has lacked a solid theoretical foundation.

Methods

The authors propose a shift from point-wise pessimism to Bellman-consistent pessimism.

  1. Version Space Construction: Instead of adding a penalty to every state-action pair, they define a "version space"—a set of all value functions $f$ that are consistent with the Bellman equations given the observed data (i.e., they have low empirical Bellman error).
  2. Global Pessimism: For any policy $\pi$, the algorithm estimates its value by finding the minimum possible value at the initial state $s_0$ among all functions in the version space. This ensures that the pessimism is globally consistent rather than locally arbitrary.
  3. Two Algorithmic Flavors:
  4. Information-Theoretic Algorithm: A conceptually pure but computationally expensive version that optimizes directly over the version space.
  5. Pessimistic Soft Policy Iteration (PSPI): A practical version that uses a Lagrangian relaxation (regularization) to find the pessimistic value function and updates the policy via mirror descent.

Datasets

As a theoretical contribution, the paper does not introduce new empirical benchmarks. Instead, it provides a rigorous analysis applicable to any dataset $D$ consisting of $n$ i.i.d. tuples $(s, a, r, s')$. The authors demonstrate how their results instantiate in the specific case of Linear MDPs, where they show a clear advantage over prior state-of-the-art methods.

Key Insights and Ideas

  • Physics-Constrained Pessimism: By requiring the value function to be "Bellman-consistent," the algorithm prevents the pessimism from becoming "unphysical." The value at one state is tied to its neighbors, which limits how much error can accumulate.
  • Adaptive Bias-Variance Tradeoff: One of the most striking features is that the algorithm automatically balances bias (from distribution shift) and variance (from finite samples).

    Figure 1: An example illustrating dif- ferent on-support and off-support split- tings (denoted by two different vertical lines). Different splitting has different C2 values, and further yields different bias-variance trade-offs.
  • Weaker Assumptions: Unlike previous work that required strong "concentrability" (full coverage) or complex density estimation, this approach only requires Bellman closedness—a standard assumption even in the easier "online" RL setting.

Key Results

  • Sample Complexity Improvement: In the case of linear function approximation with $d$ dimensions, the proposed method improves the sample complexity by a factor of $O(d)$ over previous bonus-based approaches when the action space is small.
  • Double Robustness: The authors prove that the regret (the gap between the learned policy and a comparator policy) is small if either the distribution shift is manageable or the functions in the version space are similar in the regions where data is missing.
  • Generic Guarantees: This is the first work to provide systematic, provable guarantees for offline RL using generic function approximation classes without requiring restrictive coverage assumptions.

Limitations and Future Work

  • Computational Gap: While the authors provide a "practical" algorithm (PSPI), its theoretical guarantees are slightly weaker than the information-theoretic version. Closing this gap is an open research question.
  • Empirical Validation: The paper is purely theoretical. While the math is robust, the authors note that empirical evaluation on standard benchmarks (like D4RL) is a necessary next step to see how these "Bellman-consistent" value functions behave in deep RL architectures.
  • Hyperparameter Sensitivity: Although the algorithm adapts to the bias-variance tradeoff, it still requires knowledge of the "realizability" error ($\epsilon_F$), which may be hard to estimate in practice.

Summary updated

Abstract

The use of pessimism, when reasoning about datasets lacking exhaustive exploration has recently gained prominence in offline reinforcement learning. Despite the robustness it adds to the algorithm, overly pessimistic reasoning can be equally damaging in precluding the discovery of good policies, which is an issue for the popular bonus-based pessimism. In this paper, we introduce the notion of Bellman-consistent pessimism for general function approximation: instead of calculating a point-wise lower bound for the value function, we implement pessimism at the initial state over the set of functions consistent with the Bellman equations. Our theoretical guarantees only require Bellman closedness as standard in the exploratory setting, in which case bonus-based pessimism fails to provide guarantees. Even in the special case of linear function approximation where stronger expressivity assumptions hold, our result improves upon a recent bonus-based approach by $\mathcal{O}(d)$ in its sample complexity when the action space is finite. Remarkably, our algorithms automatically adapt to the best bias-variance tradeoff in the hindsight, whereas most prior approaches require tuning extra hyperparameters a priori.
BibTeX
@inproceedings{xie2021bellman,
  author = {Tengyang Xie and Ching-An Cheng and Nan Jiang and Paul Mineiro and Alekh Agarwal},
  title = {{Bellman-consistent Pessimism for Offline Reinforcement Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=woj2N7U8Y9h},
}

Loading related content...

Figure