PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Pessimism Provably Efficient for Offline RL?

Ying Jin, Zhuoran Yang, Zhaoran Wang

arXiv:2012.15085v3cs.LGcs.AImath.OCmath.STstat.ML

TL;DR

Offline RL asks whether an optimal policy can be learned from a pre-collected dataset despite insufficient coverage and limited theory. The paper introduces pessimistic value iteration, PEVI, and proves that it eliminates spurious correlation while achieving minimax-optimal guarantees for linear MDPs up to dimension and horizon factors.

  • Problem

    Offline RL must learn an optimal policy from a dataset collected a priori, but insufficient dataset coverage eludes much existing theory.

  • Method

    PEVI adds an uncertainty-quantifying penalty to value iteration by flipping the sign of the exploration bonus used in online RL.

  • Results

    PEVI eliminates spurious correlation for general MDPs and is minimax optimal for linear MDPs up to multiplicative factors of dimension and horizon.

  • Takeaways & Limitations

    PEVI’s learned policy has an oracle property: its suboptimality depends on coverage of the optimal-policy trajectory rather than unrelated trajectories.

  • Takeaways & Limitations

    The theory assumes dataset compliance with the underlying MDP, while imposing no sufficient-coverage or policy-affinity assumptions.

Abstract

from arXiv · show

We study offline reinforcement learning (RL), which aims to learn an optimal policy based on a dataset collected a priori. Due to the lack of further interactions with the environment, offline RL suffers from the insufficient coverage of the dataset, which eludes most existing theoretical analysis. In this paper, we propose a pessimistic variant of the value iteration algorithm (PEVI), which incorporates an uncertainty quantifier as the penalty function. Such a penalty function simply flips the sign of the bonus function for promoting exploration in online RL, which makes it easily implementable and compatible with general function approximators. Without assuming the sufficient coverage of the dataset, we establish a data-dependent upper bound on the suboptimality of PEVI for general Markov decision processes (MDPs). When specialized to linear MDPs, it matches the information-theoretic lower bound up to multiplicative factors of the dimension and horizon. In other words, pessimism is not only provably efficient but also minimax optimal. In particular, given the dataset, the learned policy serves as the "best effort" among all policies, as no other policies can do better. Our theoretical analysis identifies the critical role of pessimism in eliminating a notion of spurious correlation, which emerges from the "irrelevant" trajectories that are less covered by the dataset and not informative for the optimal policy.

1 Introduction

Offline RL must learn from a pre-collected dataset without further exploration, making insufficient coverage a central theoretical challenge. The paper proposes PEVI and shows that pessimism can remove spurious correlation while achieving near-minimax guarantees for linear MDPs.

  • Motivation: Offline RL lacks continuing exploration, so datasets may insufficiently cover the optimal policy’s trajectory or misleadingly cover unrelated trajectories.The latter can induce a large cumulative reward by chance and mislead the learned policy.
  • Approach: PEVI incorporates a penalty into value iteration by flipping the sign of the exploration bonus used in online RL.The paper presents this as a straightforward implementation of pessimism.
  • Theory: PEVI’s suboptimality analysis decomposes error into intrinsic uncertainty, spurious correlation, and optimization error.The paper identifies spurious correlation as important even in multi-armed bandits.
  • Theory: For general MDPs, an uncertainty-quantifying penalty enables PEVI to eliminate spurious correlation from suboptimality.This is established under a sufficient condition on the penalty function.
  • Theory: For linear MDPs, PEVI is minimax optimal up to multiplicative factors of the dimension and horizon.Its suboptimality depends on coverage of the optimal-policy trajectory rather than unrelated trajectories, yielding an oracle property.
  • Assumptions: The analysis requires dataset compliance with the underlying MDP but no sufficient-coverage or learned-policy–behavior-policy affinity assumptions.The paper notes that common coverage assumptions often fail in practice.

2 Preliminaries

The paper formalizes episodic MDP performance and an offline dataset collected a priori. Its compliance assumption permits arbitrary, adaptive, or interdependent action choices while requiring data generated by the underlying MDP.

  • Episodic MDP and Performance Metric: The setting is an episodic MDP with state and action spaces, horizon H, transition kernel P, and bounded rewards in [0, 1].Policies induce trajectories through action selection and state transitions.
  • Episodic MDP and Performance Metric: The optimal policy, Q-function, and value function define the target, while performance is measured by policy suboptimality from the initial state.The goal is to maximize expected cumulative reward.
  • Offline Data Collecting Process: Offline learning uses K trajectories collected a priori, with no subsequent environment interaction available to the learner.The dataset is the learner’s only source of information.
  • Offline Data Collecting Process: Dataset compliance requires rewards and transitions to be generated by an underlying MDP while preserving the relevant Markov dependence conditions.The collecting process may involve interdependent trajectories, provided the data remain compliant.
  • Offline Data Collecting Process: The compliance assumption allows fixed, adaptive, adversarial, or sequentially improved behavior and does not require exploration of the state-action space.Actions may be arbitrarily chosen across trajectories.

3 What Causes Suboptimality?

The paper decomposes policy suboptimality into spurious correlation, intrinsic uncertainty, and optimization error, then illustrates how dataset-dependent estimation errors can mislead greedy policies, especially in bandits.

  • 3 What Causes Suboptimality?: Policy suboptimality is decomposed into spurious correlation, intrinsic uncertainty, and optimization error.The decomposition is stated for a general MDP and is illustrated through the multi-armed bandit special case.
  • 3.1 Spurious Correlation Versus Intrinsic Uncertainty: Spurious correlation is difficult to control because the learned policy and model evaluation error depend on the same dataset.If they were independent and the error were mean-zero, the corresponding term would have mean zero; their dependence can instead make it large.
  • 3.1 Spurious Correlation Versus Intrinsic Uncertainty: Intrinsic uncertainty arises from estimating the Bellman operator from the dataset and is impossible to eliminate because it reflects an information-theoretic lower bound.The optimization error is nonpositive when the learned policy is greedy with respect to the estimated Q-function.
  • 3.2 Illustration via a Special Case: MAB: This spurious correlation can produce significant suboptimality even when the selected action has low true reward, while the optimal policy selects the highest-mean action.The effect becomes more pronounced in longer-horizon MDPs because sufficient visitation of every state-action pair is harder to ensure.

4 Pessimism is Provably Efficient

PEVI uses pessimistic uncertainty penalties to remove spurious correlation in offline RL and obtains data-dependent suboptimality guarantees for general and linear MDPs. For linear MDPs, its guarantee matches an information-theoretic lower bound up to dimension and horizon factors, while depending on coverage of the optimal-policy trajectory.

  • Algorithm and general theory: PEVI flips the online exploration bonus sign to construct a pessimistic value-iteration algorithm with an uncertainty-quantifying penalty.The approach is presented for episodic MDPs and extends to kernel function approximation with data splitting.
  • Algorithm and general theory: A ξ-uncertainty quantifier makes the penalty eliminate spurious correlation from PEVI’s suboptimality in general MDPs.The resulting bound retains the intrinsic uncertainty term rather than the dataset-dependent spurious-correlation term.
  • Linear MDP guarantees: The linear-MDP specialization establishes a suboptimality guarantee under the linear-MDP assumption, with the uncertainty quantifier verified for Algorithm 2.The theorem is stated with confidence parameter ξ and applies under the paper’s linear-MDP assumption.
  • Oracle property: The oracle property makes suboptimality depend on dataset coverage along the optimal-policy trajectory, not on unrelated trajectories.This adapts automatically to the support of the unknown optimal-policy trajectory and excludes spurious correlation from off-trajectory coverage.
  • Oracle property: When the optimal-policy trajectory is sufficiently covered, the linear-MDP suboptimality decays at rate K^-1/2 and tends to zero as K increases.The corresponding bound scales as H^2K^-1/2 and is tied to an information-theoretic lower bound.
  • Linear MDP guarantees: PEVI is minimax optimal for linear MDPs up to multiplicative factors of dimension and horizon.The information-theoretic lower bound matches Theorem 4.4 up to β and absolute constants.

5 Proof Sketch

The proofs first establish pessimism for general MDPs, then specialize the argument to linear MDPs and prove minimax optimality through an information-theoretic lower bound.

  • General MDP: The proof’s key step is showing that PEVI’s constructed Q-functions are pessimistic estimators of the optimal Q-functions.This follows by bounding the model evaluation error pointwise between zero and twice the uncertainty quantifier.
  • General MDP: 0 ≤ιh(x, a) ≤2Γh(x, a) holds pointwise for every state-action pair and stage with probability at least 1 −ξ.The event E has probability at least 1 −ξ, and the uncertainty quantifiers provide the required bounds.
  • Linear MDP: For linear MDPs, properly chosen regularization and scaling parameters make the constructed uncertainty quantifiers valid, allowing Theorem 4.2 to specialize to Theorem 4.4.The specialization assumes the data-compliance condition and a linear MDP structure.
  • Minimax lower bound: The hard-instance lower bound uses hypothesis testing and a Le Cam-style argument to establish minimax optimality of the linear-MDP upper bound.The construction uses a class of linear MDPs and a worst-case compliant dataset.
  • Hard instance: The hard instance has three states, with the initial action determining transition probabilities into two absorbing states and only one absorbing state yielding reward.The class uses p1, p2, p3 ∈[1/4, 3/4], with p3 = min{p1, p2}.

A Proofs of Suboptimality Decomposition

The suboptimality proof decomposes value differences into estimation-related terms and uses an extended value-difference lemma to connect them to trajectories under the optimal and learned policies.

  • Value decomposition: The proof decomposes the difference between the estimated value and the optimal value, and between the estimated value and the learned policy’s value.These correspond to the two value comparisons used to analyze suboptimality.
  • Value decomposition: The extended value-difference lemma characterizes the difference between an estimated value function and a policy value through Bellman-operator discrepancies along policy-generated trajectories.The expectation is taken with respect to the trajectory generated by the relevant policy.
  • Application: Applying the lemma with the learned policy and the optimal policy isolates dataset-dependent estimation terms and trajectory-dependent uncertainty terms.The proof applies the lemma with the learned policy as the estimated-policy argument and the optimal policy as the comparison trajectory.

B.1 Proof of Lemma 5.1

Lemma 5.1 proves that the uncertainty penalty makes PEVI’s estimated Q-functions pessimistic while controlling their model evaluation error on a high-probability event.

  • Error bounds: On the event E, the model evaluation error is nonnegative and bounded above by twice the uncertainty quantifier pointwise.This is the central uncertainty-quantifier property required by the general-MDP analysis.
  • Error bounds: The clipped construction of Qh ensures nonnegativity of the model evaluation error when the unpenalized estimate is negative or nonnegative.The proof handles the two cases separately using nonnegative rewards and the definition of the uncertainty event.
  • Value control: The penalized estimate remains bounded by the Bellman target, which is at most H −h + 1 under rewards in [0, 1].This establishes the upper range needed for the recursive value analysis.
  • Conclusion: Combining the pointwise error bounds with the high-probability event completes the proof of Lemma 5.1.The event E satisfies PD(E) ≥1 −ξ.

B.2 Proof of Lemma 5.2

The linear-MDP proof verifies the uncertainty quantifier using self-normalized concentration, function-class covering, and bounded feature and weight properties.

  • Conclusion: The resulting uncertainty quantifiers satisfy the event required by Theorem 4.2, yielding the linear-MDP suboptimality guarantee.The proof concludes by specializing the general-MDP theorem under the linear-MDP assumptions.
  • Linear representation: The linear-MDP proof reduces Bellman evaluation to a linear form in the feature map, (Bh bVh+1)(x, a) = φ(x, a)⊤wh.This representation enables matrix-based uncertainty control.
  • Parameter control: Bounded-weight and regularization properties control the norms of the true and estimated Bellman parameters.The argument uses Λh ⪰λ · I together with bounded features.
  • Concentration: Uniform concentration handles the dependence of the estimated value function on the offline dataset.The proof places estimated value functions in a controlled function class and applies an ε-cover.
  • Concentration: Self-normalized concentration bounds the fixed-function stochastic process, after which a union bound extends the result across stages and the function cover.The proof sets ε = dH/K and λ = 1 when bounding the covering-number contribution.

B.3 Proof of Corollary 4.5

The proof combines high-probability events and spectral properties of covariance matrices to derive Corollary 4.5’s bound. It uses rank and eigenvalue constraints together with the chosen scaling parameter.

  • B.3 Proof of Corollary 4.5: The proof establishes the required event intersection with probability at least 1 −ξ by combining two events, each holding with probability at least 1 −ξ/2.The union bound is applied to E† and E‡.
  • B.3 Proof of Corollary 4.5: Rank(Σh(x)) ≤r and eigenvalues λh,j(x) ∈[0, 1] control the covariance terms used in the bound.These properties hold for all x, h, and j in the stated ranges.
  • B.3 Proof of Corollary 4.5: The choice of β in Corollary 4.5 supplies the final scaling needed to obtain Equation (4.11).The proof explicitly invokes β after applying the eigenvalue and rank conditions.

B.4 Proof of Corollary 4.6

The proof of Corollary 4.6 constructs concentration events for the dataset covariance quantities and combines them through union bounds. Under a sufficiently large K, the relevant events hold jointly with probability at least 1 −ξ.

  • B.4 Proof of Corollary 4.6: The proof uses independent, centered trajectory variables and concentration inequalities to control the random matrices Zh.The dataset trajectories are i.i.d., and Lemma E.1 is applied for fixed h.
  • B.4 Proof of Corollary 4.6: K ≥40d/c · log(4dH/ξ) ensures one covariance event holds with probability at least 1 −ξ/2.This condition follows from the operator-norm bound involving Σh.
  • B.4 Proof of Corollary 4.6: K ≥40/c · log(4dH/ξ) ensures a second event holds with probability at least 1 −ξ/2.The proof obtains this event using Equation (B.33).
  • B.4 Proof of Corollary 4.6: The union bound combines the two events into E* with probability at least 1 −ξ.The resulting conclusion uses c′ = 2c · c′′.

C.1 Proof of Lemma 5.3

The proof analyzes two linear MDPs whose optimal first actions differ, then bounds the PEVI policy’s suboptimality using concentration of Bernoulli counts and high-probability events.

  • C.1 Proof of Lemma 5.3: M1 and M2 differ in which first-step action is optimal: M1 selects b1, whereas M2 selects b2.The optimal policies choose these actions deterministically at h = 1.
  • C.1 Proof of Lemma 5.3: The relevant dataset statistics are sums of independent Bernoulli variables, so Hoeffding’s inequality controls their deviations.The success probabilities lie in [1/4, 3/4].
  • C.1 Proof of Lemma 5.3: K ≥32 · log(8/ξ) yields an event with probability at least 1 −ξ/2 for the count estimates.This event is obtained by combining the concentration bounds with a union bound.
  • C.1 Proof of Lemma 5.3: Combining the count event with the PEVI confidence event gives a final probability of at least 1 −ξ.The proof uses the theorem’s event with confidence parameter ξ/2.

C.3 Proof of Theorem 4.7

The proof establishes Theorem 4.7 by reducing distinguishability between two linear MDPs to a hypothesis-testing argument. Concentration and total-variation bounds then yield the lower bound for arbitrary offline RL algorithms.

  • C.3 Proof of Theorem 4.7: The construction uses M1 and M2, where the optimal first-step actions are b1 and b2, respectively.The dataset is compliant with either MDP, while the action-count ratio is bounded by an absolute constant.
  • C.3 Proof of Theorem 4.7: A hypothesis test based on the algorithm’s first action connects the policy output to the two MDPs’ distinguishability.The test function is defined from the actions produced by any offline RL algorithm.
  • C.3 Proof of Theorem 4.7: The reduced dataset D1 contains the information relevant to distinguishing M1 from M2 because later states are absorbing.Thus the full dataset distributions equal the reduced-data distributions under both MDPs.
  • C.3 Proof of Theorem 4.7: KL- and total-variation bounds limit how reliably any algorithm can distinguish the two MDPs.The argument uses Pinsker’s inequality and the chosen parameter constraints on p and p∗.
  • C.3 Proof of Theorem 4.7: The resulting lower bound applies to the linear-MDP class because the constructed family is a subclass of linear MDPs.The conclusion holds for sufficiently large K under the stated logarithmic conditions.

C.4 Locally Refined Upper Bounds

PEVI’s locally tailored uncertainty quantifiers yield refined suboptimality guarantees for linear MDPs, improving over the general pessimistic construction while retaining minimax optimality.

  • Theorem 4.4 gives Pess(D) a minimax-optimal suboptimality bound up to β and an absolute constant for linear MDPs.
  • PEVI instantiates pessimistic value iteration through empirical Bellman updates and uncertainty quantifiers, producing the policy Pess∗(D).The construction defines estimated value functions and Bellman updates across all horizons, with special handling for unobserved actions.
  • Proposition C.2 establishes the local-optimality result for datasets compliant with M and covering the optimal action at least once.
  • e O(H^2A/√nj∗) is the bound from directly applying Theorem 4.4 to this setting.
  • e O(H/√nj∗) is achieved by Pess∗(D) using uncertainty quantifiers tailored to the linear-MDP class.
  • Pess∗(D) improves over Pess(D) by a factor of HA and remains minimax optimal up to a factor of H.

D.1 Proof of Theorem 4.9

The proof of Theorem 4.9 constructs kernel-based uncertainty quantifiers and combines concentration, operator, and martingale arguments to control empirical Bellman-update error.

  • Algorithm 3 constructs fitted value functions and empirical Bellman updates using kernel ridge regression and the penalty Γh.
  • Theorem 4.9 then follows by applying the general pessimistic-RL conclusion to these uncertainty quantifiers.
  • The fitted function lies in the span of the feature map, reducing the RKHS regression problem to a finite-dimensional representation.
  • The proof bounds |bBh bVh+1(x,a)−Bh bVh+1(x,a)| using the feature representation, boundedness assumptions, and Cauchy–Schwarz inequalities.
  • Inverse-order sample splitting makes the relevant martingale sequence adapted to a filtration, enabling concentration bounds for each horizon step.
  • Combining the concentration inequalities across horizons shows that {Γh} is a ξ-uncertainty quantifier with probability at least 1−ξ.

D.2 Proof of Proposition 4.11

The proof of Proposition 4.11 specializes Theorem 4.9 under eigenvalue-decay assumptions by selecting a sufficiently large penalty parameter B.

  • Theorem 4.9’s condition on B is reduced to bounds involving G(K/H,1+1/K), logarithmic confidence terms, and the RKHS norm parameters.
  • Finite-spectrum, exponential-decay, and polynomial-decay cases are handled separately through corresponding bounds on the effective-dimension terms.
  • B = c · H · (log(KH/ξ))^(1/2+1/(2γ)) is sufficient under the stated eigenvalue-decay analysis.

D.3 Proof of Corollary 4.13

The proof of Corollary 4.13 controls effective dimensions under eigenvalue-decay conditions by combining spectral truncation, concentration, and carefully chosen regularization parameters.

  • The proof relates sample and population effective dimensions through projected covariance operators on the leading eigenspace.
  • The analysis decomposes the feature map using the orthogonal basis {√σj · ψj} and studies sample and population operators through spectral projections.
  • The selected parameters establish the required high-probability inequalities and produce effective-dimension exponents κ∗ and ν∗.
  • For finite-spectrum decay, choosing m = γ and Rm = 0 yields concentration bounds after setting λ and ε as functions of γ, n, and δ.
  • For exponential decay, the truncation remainder Rm is bounded separately for γ ≥ 1 and γ ∈ (0,1), leading to parameter choices that satisfy the concentration conditions.
  • For polynomial decay, Rm decreases polynomially with m, and λ is chosen proportional to n^(1/Cγ,τ) log(n/δ).
Loading 2012.15085v3…