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 theoretical framework for offline reinforcement learning (RL) that avoids the "over-pessimism" trap of traditional methods. By enforcing pessimism only on value functions that are consistent with the Bellman equations, the authors achieve state-of-the-art theoretical guarantees and propose a practical algorithm that automatically balances the trade-off between data coverage and policy performance.

The Challenge: Distribution Shift in Offline RL

In offline RL, an agent learns a policy entirely from a fixed, pre-collected dataset without any further interaction with the environment. The primary hurdle in this setting is distribution shift: the agent may want to evaluate an action that is poorly represented in the dataset, leaving it uncertain whether that action leads to a high reward or a catastrophic failure.

Illustration of distribution shift

To mitigate this risk, most algorithms employ pessimism. Traditional "bonus-based" pessimism operates by subtracting a penalty (a "bonus") from the estimated value of state-action pairs that lack representation in the data. However, this point-wise approach has two major flaws:

  1. Over-pessimism: It can be excessively conservative, causing the agent to ignore potentially optimal policies simply because of a single uncertain state-action pair along the trajectory.
  2. Strong Assumptions: It often requires unrealistic assumptions, such as knowing the exact density of the data distribution or relying on highly specific function approximators (like linear models).

The authors seek to provide a systematic treatment of offline RL using general function approximation (e.g., neural networks) while requiring only the standard assumptions typically used in exploratory (online) RL.

The Solution: Bellman-Consistent Pessimism

The core innovation of this paper is Bellman-consistent pessimism. Instead of penalizing every uncertain point individually, the authors evaluate a version space—a set of all possible value functions that remain consistent with the Bellman equations on the observed dataset.

An Information-Theoretic Approach

The algorithm discovers a policy by solving a "max-min" optimization problem:

  1. Consistency: Identify all value functions $f$ that exhibit a small Bellman error on the dataset.
  2. Pessimism: For each candidate policy $\pi$, find the minimum value that any consistent function $f$ predicts at the initial state $s_0$.
  3. Optimization: Select the policy $\pi$ that maximizes this minimum initial value.

This global approach ensures the agent is only pessimistic about the total expected value of a policy, rather than being overly penalized for individual unseen states.

Practical Implementation: PSPI

Because searching over all possible policies and functions is computationally intractable, the authors propose Pessimistic Soft Policy Iteration (PSPI).

  • PSPI utilizes Lagrangian relaxation to convert the strict consistency constraint into a regularized loss function.
  • It then updates the policy using Mirror Descent, a standard and efficient optimization technique in RL.

Key Insights and Theoretical Results

This paper is primarily a theoretical contribution, providing rigorous mathematical proofs that the algorithm functions effectively on any historical dataset given an expressive enough function class.

  • Global vs. Local Pessimism: By applying pessimism at the initial state $s_0$ rather than at every $(s, a)$ pair, the algorithm successfully avoids discarding good policies due to isolated local uncertainty.
  • Adaptive Bias-Variance Tradeoff: Remarkably, the algorithm automatically adapts to the optimal split between "on-support" data (well-sampled regions) and "off-support" data (unseen regions). While prior methods require manual hyperparameter tuning to find this balance, here it emerges naturally from the optimization.
  • Weaker Assumptions: The framework only requires Bellman completeness (the assumption that the function class is closed under the Bellman operator). This is a standard assumption in online RL, making the theory broadly applicable.
  • Linear Improvement: In the specific case of linear function approximation, the authors demonstrate a sample complexity improvement of $\mathcal{O}(d)$ (where $d$ is the feature dimension) over previous state-of-the-art methods.
  • Theoretical Convergence: The authors prove that their practical algorithm (PSPI) converges to a near-optimal policy with a rate of $\mathcal{O}(n^{-1/5})$. While slower than the information-theoretic version's $\mathcal{O}(n^{-1/2})$, it represents a significant milestone for a computationally tractable method.

Limitations and Future Work

While the theoretical guarantees are strong, the authors note a few limitations to address in future work:

  • Sample Complexity Gap: There remains a gap between the sample complexity of the information-theoretic algorithm and the practical PSPI method.
  • Hyperparameter Knowledge: The theoretical proofs assume knowledge of the "completeness error" (how well the function approximator can represent the Bellman update). In practice, this value is unknown and must be estimated.
  • Empirical Validation: The paper focuses on theoretical bounds and lacks experiments on standard empirical benchmarks (like D4RL). Testing PSPI against established baselines, such as Conservative Q-Learning (CQL), is the logical next step for the community.

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},
}
Figure