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.
1. Introduction
Offline Reinforcement Learning (RL) aims to learn an optimal policy from a fixed, historical dataset without further environment interaction. The fundamental challenge is distribution shift: the learned policy might choose actions that are poorly represented in the dataset, leading to "over-optimistic" value estimates and catastrophic performance.
To counter this, researchers typically use pessimism. The standard approach is "bonus-based pessimism," where a penalty is subtracted from rewards in state-action regions with low data coverage. However, this method has significant drawbacks: it often requires strong expressivity assumptions (like linear models) and is highly sensitive to hyperparameters that are difficult to tune without online interaction.
2. Methodology
2.1 Bellman-consistent Version Spaces
The proposed algorithm maintains 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 a small Bellman error). By requiring consistency with the Bellman equation, the algorithm leverages the sequential structure of RL.
2.2 Initial State Pessimism
Instead of point-wise bonuses, the algorithm searches for a policy that maximizes the minimum value at the initial state $s_0$ across all functions in the version space. Formally: $$\widehat{\pi} = \text{argmax}_{\pi \in \Pi} \min_{f \in \mathcal{F}_{\pi,\epsilon}} f(s_0, \pi)$$ This ensures that the policy is only "optimistic" if all scenarios consistent with the data agree that the policy is good.
2.3 Pessimistic Soft Policy Iteration (PSPI)
Since the information-theoretic version is computationally hard, the authors develop Pessimistic Soft Policy Iteration (PSPI). It uses a Lagrangian relaxation to turn the constrained optimization into a regularized loss minimization problem. For linear function approximation, this results in a quadratic objective with a closed-form solution, generalizing the well-known Least-Squares Temporal Difference (LSTDQ) algorithm.
3. Key Results and Insights
- Milder Coverage Requirements: The theory doesn't require the dataset to cover all possible policies. It only needs coverage for the specific "comparator" policy you want to beat. If the data is good for a specific sub-optimal policy, the algorithm will at least find that one.
- Sample Complexity Improvement: In the case of linear function approximation, the proposed method improves the sample complexity by a factor of $O(d)$ (where $d$ is the feature dimension) compared to previous state-of-the-art bonus-based methods, provided the action space is finite.
- Automatic Bias-Variance Adaptation: The algorithm's regret bound automatically "chooses" the best split between on-support (data-rich) and off-support (data-poor) regions. It effectively performs a bias-variance tradeoff in hindsight, whereas prior methods required the user to commit to a specific tradeoff via hyperparameters.
4. Discussion
While this work establishes a rigorous theoretical foundation for Bellman-consistent pessimism, several avenues for future research remain. The practical PSPI algorithm has a theoretical sample complexity of $O(n^{-1/5})$, which is slower than the $O(n^{-1/2})$ rate achieved by the information-theoretic version. Additionally, empirical validation on large-scale deep RL benchmarks is necessary to assess the real-world performance of these principles.
Summary updated