PaperlayerView exact revision on arXiv

Source-linked AI summary

Bellman-consistent Pessimism for Offline Reinforcement Learning

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

arXiv:2106.06926v6cs.LGcs.AIstat.ML

TL;DR

Offline RL must learn policies from historical data without reliable coverage, while excessive pessimism can block good-policy discovery. The paper introduces Bellman-consistent pessimism through Bellman-consistent version spaces, obtaining coverage-free guarantees and an O(d) linear-MDP sample-complexity improvement.

  • Problem

    Offline RL needs guarantees when historical data lack coverage, but popular pointwise or bonus-based pessimism can be overly conservative and lacks comprehensive theory for generic function approximation.

  • Method

    The method forms a version space of functions with small Bellman error for each policy and applies pessimism at the initial state over that Bellman-consistent set.

  • Results

    In finite-action linear MDPs, the sample complexity improves by O(d) over the compared result, while the guarantees require no dataset coverage assumptions.

  • Takeaways & Limitations

    Bellman-consistent pessimism supports sample-efficient offline RL with generic function approximation and adapts to the best bias-variance tradeoff in hindsight.

  • Takeaways & Limitations

    The general analysis has a conservative policy-class complexity bound yielding an overall O(n^-1/5) rate, and its estimator requires knowledge of εF.

Abstract

from arXiv · show

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 seeks improved policies from historical data without exhaustive coverage, but generic function approximation lacks comprehensive best-effort theory. This paper develops coverage-free algorithms with guarantees and improves linear-function-approximation sample complexity.

  • 1 Introduction: The paper provides algorithms that leverage arbitrary historical datasets to find policies with the largest guaranteed rewards among scenarios consistent with the data.The guarantees do not require coverage assumptions on the dataset.
  • 1 Introduction: Offline RL must extrapolate from historical datasets despite prohibitive coverage assumptions in large state or action spaces.Coverage assumptions require the dataset to include every possible state-action pair or trajectory with nontrivial probability.
  • 1 Introduction: Few prior best-effort methods provide comprehensive guarantees for generic function approximation.Existing approaches rely on uncertainty or density-estimation or use tabular, truncated-backup, or specialized linear-function-approximation analyses.
  • 1 Introduction: The proposed information-theoretic algorithm achieves small regret to comparator policies whose coverage approximately holds relative to the data-collection policy.The regret bound matches what is typically obtained when coverage holds for all policies.
  • 1 Introduction: In finite-action linear MDPs, the sample complexity improves by O(d) over the best known translated result.Here d is the dimension of the linear MDP.

2 Preliminaries

The paper formalizes MDPs, offline data, function approximation, expressivity, and distribution shift. Its distribution-shift measure evaluates how Bellman errors transfer between the dataset distribution and policy-induced distributions through the chosen function class.

  • Markov Decision Processes: An MDP is specified by state and action spaces, transitions, rewards, a discount factor, and a deterministic initial state.Policies map states to action distributions, and the state and action spaces are finite but may be arbitrarily large.
  • Markov Decision Processes: A policy’s value is its expected discounted return, while Qπ is the unique fixed point of the policy-specific Bellman operator Tπ.The learning objective is to find a policy maximizing its initial-state value.
  • Offline RL: Offline RL estimates from i.i.d. transition tuples drawn from a fixed data distribution µ without environment interaction.Each tuple contains a state, action, reward, and next state.
  • Function Approximation: Function approximation uses a value-function class F to model Qπ and generalize across large or complex state-action spaces.The paper allows generic finite policy and function classes, with statistical complexity measured through log-cardinality.
  • Expressivity Assumptions: Realizability requires each policy’s Q-function to be well approximated by some f in F, while completeness requires approximate closure of F under Tπ.The paper measures completeness violation under µ rather than all admissible distributions.
  • Distribution Shift: Distribution shift measures how Bellman errors transfer from the offline distribution µ to another distribution relative to F and π.This measure can be tighter than a bounded distribution ratio because differences undetected by the policy and function class may not impair transfer.

3 Information-Theoretic Results with Bellman-consistent Pessimism

The paper estimates policy values using Bellman-consistent pessimism over low-Bellman-error functions, then adapts the resulting regret bound to the best on-support/off-support split. The guarantees cover general function approximation without coverage assumptions and yield improved linear-function-approximation results.

  • Information-Theoretic Results: The algorithm forms a version space of functions with small empirical Bellman error and minimizes their predicted value at the initial state.This implements pessimism at the initial state while preserving Bellman consistency.
  • Information-Theoretic Results: If Qπ belongs to each version space, the estimator’s initial-state uncertainty bounds regret relative to any comparator policy.The threshold ε is chosen to ensure that Qπ, or its best approximation, is included in the version space.
  • Information-Theoretic Results: The regret analysis splits estimation error into on-support and off-support components, capturing a bias-variance tradeoff governed by the concentrability threshold C2.Smaller C2 improves the O(C2/n) transfer-estimation term but can increase bias from mismatch between dπ and ν; larger C2 permits lower bias but increases variance.
  • Information-Theoretic Results: The estimator automatically selects the best C2 in hindsight, avoiding the explicit density-ratio thresholds used as algorithmic hyperparameters by several prior methods.Here the bias-variance decomposition is a proof-level adaptation rather than a tuning knob in the algorithm.
  • Results for Linear Function Approximation: Under linear function approximation with realizability and completeness, the method improves prior finite-action sample complexity by O(d) and can compete with an optimal policy under a sufficiently large policy radius.The linear result uses the class FΦ and policy class ΠΦ; a large policy radius ensures that ΠΦ contains a sufficiently good policy.
  • Results for Linear Function Approximation: The linear setting identifies full-rank data covariance as sufficient for consistent offline RL, while the information-theoretic algorithm itself is not computationally efficient in its naïve form.The naïve implementation pessimistically evaluates each policy before selecting the best one.

4 Practical Algorithm — Regularized Offline Policy Optimization

The practical algorithm replaces constrained pessimistic evaluation with regularization and searches an implicitly induced policy class using mirror descent. Its guarantees decompose error into optimization, on-support, and off-support terms, adapt to a bias-variance tradeoff, and yield computational efficiency under linear function approximation.

  • Algorithmic design: The algorithm outputs a uniform mixture of the policies generated across T optimization rounds.The procedure initializes with a uniform policy, iterates pessimistic evaluation and policy improvement, then mixes π1 through πT at the trajectory level.
  • Algorithmic design: The practical algorithm uses regularized pessimistic evaluation, an implicitly induced policy class, and mirror descent policy updates.These changes avoid searching over an explicit policy space independently of the value-function class.
  • Theoretical guarantees: Theorem 4.1 decomposes the performance bound into optimization, on-support, and off-support error components.Distribution shift is measured through C(ν; µ, F, πt), which depends on the optimization trajectory.
  • Theoretical guarantees: O(n^-1/5) is the overall rate obtained by choosing T = O(n^2/5), balancing decreasing optimization error against increasing on-support error.The increasing term reflects the implicit policy class becoming exponentially more complex with T.
  • Computational implementation: O(n^-1/3) is the overall rate stated for linear function approximation when the function-class approximation errors vanish.The linear setting also avoids the general dependence of the implicit policy-class complexity on T, up to mild logarithmic norm dependence.
  • Theoretical guarantees: The guarantee can adapt to the best bias-variance decomposition through the concentrability threshold C2, and the off-support error vanishes under either of two stated conditions.The off-support term is zero when all relevant distribution-shift measures are below C2 or when ft − T^πtΔft is identically zero along the trajectory.
  • Computational implementation: In linear function approximation, the objective is quadratic in θ and can have a closed-form solution under matrix invertibility conditions.The resulting implementation generalizes LSTDQ.

5 Conclusions

The paper develops Bellman-consistent pessimism for offline reinforcement learning without data coverage assumptions and provides a tractable implementation. It reports adaptive bias-variance guarantees and an O(d) sample-complexity improvement in a finite, small-action linear setting, while noting a remaining practical limitation.

  • Contributions: Bellman-consistent pessimism supports sample-efficient offline reinforcement learning without data coverage assumptions.The approach requires only Bellman-completeness in the stated theoretical setting, rather than the stronger assumptions commonly associated with point-wise or bonus-based pessimism.
  • Contributions: The method infers a policy-value lower bound through a Bellman-consistent version space and provides a tractable implementation.The version space contains functions with small Bellman error, and pessimism is applied at the initial state.
  • Results: O(d) is the reported sample-complexity improvement over the best-known recent offline-RL work in linear MDPs when the action space is finite and small.The comparison is stated specifically for the linear function approximation setting.
  • Results: The algorithms adapt to the best bias-variance tradeoff in hindsight, which the paper states prior algorithms do not achieve.This adaptation is part of the paper’s reported contribution.
  • Limitations: The practical algorithm’s sample complexity is identified as a limitation and future-work direction, though the supplied passage does not provide its complete statement.The conclusion passage begins the limitation discussion but is truncated before specifying the full boundary.

A.1 Results for General Function Approximation

The appendix establishes how the error functional E(f, π; D) relates to Bellman error under general function approximation. Its results use empirical concentration and approximation assumptions to control this relation and derive the stated bounds.

  • Theorem A.1: Theorem A.1 characterizes E(fπ, π; D) for the best estimation fπ of Qπ in the function class.The theorem statement is supplied without the displayed bound.
  • Theorem A.2: E(f, π; D) can effectively estimate the L2,µ distance between f and Tπf.This is the central estimation property established before Theorem A.2.
  • Theorem A.2: Theorem A.2 states that sufficiently small E(f, π; D) implies a bound on the Bellman-error norm of f.The supplied theorem statement omits the displayed bound.
  • Proof strategy: The proofs use Bernstein concentration with union bounds over function classes, together with algebraic identities and Cauchy–Schwarz inequalities.The appendix repeatedly invokes these tools to control empirical and population quantities.

A.2 Results for Linear Function Approximation

This section presents concentration-based linear-function-approximation results, distinguishing them from general approximation through well-specifiedness and more precise uniform convergence.

  • Linear function approximation is analyzed through concentration inequalities.
  • Well-specifiedness gives εFΦ = εFΦ,FΦ = 0 and ensures Qπ ∈ F for every π ∈ ΠΦ.
  • The linear results use a defined εr based on the right-hand side of Eq.(A.18).
  • The section also defines √εb from Eq.(A.19) after setting ε = εr.

A.2.1 Detailed Proofs for Linear Function Approximation Results

The detailed linear-function-approximation proofs establish concentration using covering numbers for value and policy classes, then combine the resulting bounds.

  • The concentration analysis uses covering numbers with separate metrics for the value-function and policy classes.
  • An ε-cover is the smallest finite subset whose elements approximate every class member within ε under metric ρ.
  • Applying covering-number bounds yields a uniform result for functions in FΦ and policies in ΠΦ.
  • Corollary 8 supplies a high-probability bound for pairs of functions in FΦ and policies in ΠΦ.
  • The proof of Theorem A.6 combines Corollaries 8 and 7.
  • This version replaces the NeurIPS analysis's L1 covering number and greedy-policy class with L∞ covering numbers and the softmax policy class to address a possible additional |A| factor.

B.1 Detailed Proofs for General Function Approximation

The general-function-approximation proofs relate pessimistic value bounds to Bellman residuals through telescoping, distribution-shift decompositions, and concentrability control.

  • The proof defines εr through Eq.(A.2) and selects residual-minimizing functions within the admissible sets.
  • The optimization objective is shown to be a valid lower bound of J(π), with a symmetric upper-bound relation also established.
  • A telescoping argument expresses the gap between extremal initial-state values through Bellman residuals under the policy occupancy distribution.
  • The residual expression is decomposed into a data-distribution term and a distribution-shift term involving an arbitrary on-support distribution ν.
  • Cauchy–Schwarz and triangle-inequality bounds control the decomposed terms using weighted residuals and absolute residual magnitudes.
  • Minimizing over on-support distributions satisfying the L2 concentrability threshold yields the final bound after substituting εb.

B.2 Detailed Proofs for Linear Function Approximation Results

The linear-function-approximation proofs establish policy suboptimality and no-regret bounds, using parameter-space version sets and an MDP interpretation of estimated Q-functions.

  • Choosing L2 = log |A|√n for ΠΦ yields suboptimality O(Vmax/((1−γ)√n)).
  • The no-regret argument gives total regret bounded by Vmax(1−γ)√n, implying that one iterated policy is near-optimal.
  • The proof ensures all iterated policies lie in ΠΦ by selecting L2 according to L1, log |A|, n, and Vmax.
  • The parameter-space proof optimizes initial-state values over the version space Θπ,εr and uses linear completeness.
  • The remaining proof combines intermediate inequalities and substitutes the definitions of εr and εb.
  • For every iteration, the estimated function ft can be interpreted as the Q-function of policy πt in an MDP Mt.
  • The constructed MDPs preserve the true dynamics, while their reward differences are controlled.

C.2 Proof of Theorem 4.1

The proof bounds the policy-value difference by decomposing it into Bellman-residual and distribution-shift terms, then controls each using concentration and concentrability arguments.

  • Proof strategy: The proof analyzes J(π) − J_Mt(π) through a standard telescoping argument for the MDP induced by f_t.The constructed MDP shares the relevant dynamics with the true MDP, allowing distributions under π to be compared directly.
  • Bounding the terms: Cauchy–Schwarz bounds control the residual contributions in L2 norms under the chosen distributions.The argument applies the inequality to the terms arising in the decomposition and uses ν as an arbitrary on-support state-action distribution.
  • Proof strategy: The decomposition separates terms associated with on-support residuals from the portion of d_π not covered by an arbitrary on-support distribution ν.The proof defines (d_π \ ν)(s,a) as the positive excess of d_π(s,a) over ν(s,a).
  • Bounding the terms: Theorem A.2 transfers the empirical error bound E(f_t, π_t; D) into a bound on the Bellman residual ∥T^π_t f_t − f_t∥_2,µ.This connects the algorithm’s empirical objective to the residual quantity used in the value bound.
  • Final bound: Minimizing over ν with C(ν; µ, F, π_t) ≤ C2,t yields the final bound, with C2,t chosen arbitrarily for each t.The proof also bounds the algorithmic complexity of Π_SPI by |F|^T.

D Linear Implementation of PSPI

The paper implements PSPI with linear value functions by reducing its inner optimization to linear regression and expressing the resulting objective as a quadratic function of the parameter vector.

  • Linear function approximation: Linear PSPI uses the value-function class F = {ϕ(·,·)^Tθ : θ ∈ R^d} with a given feature map ϕ.This specializes the general function-approximation framework to d-dimensional linear features.
  • Closed-form optimization: The inner minimization over θ′ is a linear regression objective whose minimum can be written using the sample covariance matrix Σ and its pseudoinverse Σ†.Invertibility of Σ is unnecessary because the derivation uses the minimum value rather than an argmin.
  • Closed-form optimization: After substituting the inner minimum, Eq.(4.1) becomes quadratic in θ, with a positive semidefinite Hessian.The objective is therefore amenable to quadratic optimization even without assuming positive definiteness.
  • Connection to LSTDQ: Under invertibility of Σ and Σ − γB, the closed-form solution connects the objective to LSTDQ.The paper then shows that removing the pessimistic term recovers the LSTDQ solution, while its more general result does not require invertibility.
  • Matrix identities: The derivation establishes ΣΣ†B = B by representing the empirical matrices through feature matrices and applying a singular-value decomposition.This identity supports the simplification of the quadratic expression.
Loading 2106.06926v6…