Abstract
Offline reinforcement learning (RL) aims to derive optimal policies from fixed datasets without further environment interaction. A central challenge in this field is distribution shift, which is typically addressed by assuming "Bellman closure"—a restrictive condition requiring the Bellman operator to map within a chosen function class. This paper introduces Bellman Residual Orthogonalization (BRO), a framework that relaxes these requirements by enforcing Bellman equations in a "weak" form through orthogonality to a set of test functions. We provide the first computationally tractable algorithm for linear offline RL that achieves provable efficiency without Bellman closure, supported by new oracle inequalities and a novel complexity metric: the Off-Policy Cost (OPC) coefficient.
1. Introduction
Offline RL is inherently difficult because the data-generating policy (the behavior policy) often differs significantly from the target policy being evaluated or optimized. This mismatch, known as distribution shift, can lead to catastrophic error propagation. To maintain stability, most existing theoretical frameworks rely on Bellman closure (or completeness). This assumption posits that the Bellman operator, when applied to any function in the hypothesis class, results in another function within that same class.
In practice, Bellman closure is rarely satisfied, especially when using simple models like linear function approximators to represent complex environments. When this assumption fails, standard algorithms like Least-Squares Temporal Difference (LSTD) or Fitted Q-Iteration (FQI) can become unstable or yield biased results. This work proposes a model-free approach that remains statistically sound and computationally efficient even in the absence of Bellman closure.
2. The Bellman Residual Orthogonalization (BRO) Framework
The core innovation of this work is the transition from "strong" Bellman equations to "weak" forms, a concept borrowed from numerical analysis and the study of partial differential equations (e.g., Galerkin methods).
2.1 Weak Bellman Equations
Instead of requiring the Bellman residual (the difference between the current Q-function and its Bellman update) to be zero everywhere, BRO requires the residual to be orthogonal to a predefined space of test functions. If the Bellman residual is orthogonal to a sufficiently descriptive set of test functions, the resulting Q-function serves as a robust approximation of the true value function.
2.2 Empirical Constraints and Self-Normalization
To implement this principle on finite datasets, the authors construct empirical constraint sets. These sets contain candidate Q-functions that satisfy the orthogonality conditions on the observed transitions. To handle regions of the state-action space with poor data coverage, the framework employs a self-normalizing technique. This regularization ensures that test functions associated with scarce data do not exert disproportionate influence, thereby preventing overfitting to rare transitions and stabilizing the learning process.
3. Pessimistic Policy Optimization
For policy optimization, the framework adopts an algorithmic strategy of pessimism. Given the uncertainty inherent in offline data, the algorithm seeks a policy that performs well under the worst-case valid Q-function within the empirical constraint set. This "max-min" optimization effectively penalizes policies that lead to regions of the state space where the data is insufficient to provide reliable value estimates.
For linear function approximation, the authors demonstrate that this optimization problem can be reduced to a Quadratic Program (QP). This is a significant result, as it proves that the proposed method is computationally tractable and can be solved in polynomial time.
4. Theoretical Contributions
As a purely theoretical contribution, the paper establishes several key results that advance the mathematical understanding of offline RL:
- The Off-Policy Cost (OPC) Coefficient: The authors introduce the OPC, a new metric to quantify the difficulty of off-policy learning. Unlike traditional "concentrability coefficients," the OPC is more flexible because it is tied to the specific choice of test functions, allowing for a more nuanced analysis of how well the data supports a particular model class.
- Oracle Inequality: The paper provides a bound showing that the BRO policy optimization procedure competes effectively with the best possible policy in the class. The error is bounded by an "evaluation uncertainty" term that accounts for the coverage of the offline data relative to the target policy's trajectory.
- Multiple Robustness: The framework allows for the use of a union of different test function classes. If multiple assumptions are plausible (e.g., either Bellman closure holds or importance weights are accurate), the algorithm automatically inherits the performance guarantees of the best-performing class.
5. Discussion and Limitations
While this work provides a breakthrough for linear offline RL, several challenges remain for future research. The computational tractability demonstrated for linear models does not immediately extend to non-linear function classes, such as deep neural networks, where the max-min optimization remains computationally intensive. Additionally, the current error bounds involve a supremum over the entire policy class, which may lead to conservative estimates if the policy class is excessively large. Future work may explore second-order optimization methods to further tighten these guarantees and improve the practical scalability of the BRO framework.
Summary updated