PaperlayerView exact revision on arXiv

Source-linked AI summary

What are the Statistical Limits of Offline RL with Linear Function Approximation?

Ruosong Wang, Dean P. Foster, Sham M. Kakade

arXiv:2010.11895v1cs.LGcs.AImath.OCstat.ML

TL;DR

Offline RL asks whether fixed observational data can support sample-efficient policy evaluation under realizability and good feature coverage. This paper constructs information-theoretic lower bounds showing that exponential horizon dependence remains, and identifies low distribution shift or stronger representation as necessary alternatives.

  • Problem

    It is unclear whether realizability and good feature coverage, which support sample-efficient supervised learning, suffice for sample-efficient offline RL.

  • Method

    The paper studies information-theoretic lower bounds and constructs hard offline-RL instances under linear Q-functions and feature-coverage assumptions.

  • Results

    Any algorithm requires an exponential number of samples in horizon H to non-trivially estimate a given policy’s value, even when every policy’s Q-function is linear.

  • Takeaways & Limitations

    Sample-efficient offline policy evaluation requires either sufficiently low distribution shift or representation conditions substantially stronger than realizability.

  • Takeaways & Limitations

    The construction allows flexible feature mappings when basis features are nearly orthogonal and gives sufficient upper-bound conditions involving low distribution shift or policy completeness.

Abstract

from arXiv · show

Offline reinforcement learning seeks to utilize offline (observational) data to guide the learning of (causal) sequential decision making strategies. The hope is that offline reinforcement learning coupled with function approximation methods (to deal with the curse of dimensionality) can provide a means to help alleviate the excessive sample complexity burden in modern sequential decision making problems. However, the extent to which this broader approach can be effective is not well understood, where the literature largely consists of sufficient conditions. This work focuses on the basic question of what are necessary representational and distributional conditions that permit provable sample-efficient offline reinforcement learning. Perhaps surprisingly, our main result shows that even if: i) we have realizability in that the true value function of \emph{every} policy is linear in a given set of features and 2) our off-policy data has good coverage over all features (under a strong spectral condition), then any algorithm still (information-theoretically) requires a number of offline samples that is exponential in the problem horizon in order to non-trivially estimate the value of \emph{any} given policy. Our results highlight that sample-efficient offline policy evaluation is simply not possible unless significantly stronger conditions hold; such conditions include either having low distribution shift (where the offline data distribution is close to the distribution of the policy to be evaluated) or significantly stronger representational conditions (beyond realizability).

1 Introduction

The paper asks whether realizability and strong feature coverage suffice for sample-efficient offline RL. It shows that policy evaluation can still require exponentially many samples, with stronger representation or milder distribution shift needed.

  • Motivation: Offline RL aims to reduce sample complexity by learning policy values from fixed transition and reward data with function approximation.The paper frames offline methods as off-policy or batch approaches for challenging reinforcement learning settings.
  • Problem: The central question is whether realizability and lower-bounded feature covariance suffice for sample-efficient offline policy evaluation.These assumptions analogize conditions that support sample-efficient supervised learning.
  • Main result: Any algorithm requires an exponential number of samples in horizon H to non-trivially estimate a given policy’s value, even when every policy’s Q-function is linear.The result holds with constant probability under polynomially lower-bounded data-distribution eigenvalues.
  • Mechanism: Geometric error amplification explains why realizability alone is insufficient, making sample-efficient evaluation require data distributions close to the evaluated policy’s distribution.The analysis specifically studies how errors propagate through LSPE.
  • Implication: Sample-efficient offline RL requires either sufficiently mild distribution shift or representation conditions substantially stronger than realizability.The conclusion applies to the paper’s information-theoretic setting rather than ruling out every possible offline-RL assumption.
  • Additional results: The lower bound creates an exponential sample-complexity separation from supervised learning, which corresponds to offline RL with H = 1.The hard instances use only O(d · H) states and two actions, while separately showing geometric amplification of reward and transition-estimation errors.

2 Related Work

Prior offline-RL theory generally relies on stronger representation or distribution-shift assumptions than realizability and spectral feature coverage. This paper places its lower bound within work on approximate dynamic programming, importance sampling, and error amplification.

  • Existing theory: Existing provable offline-RL methods typically assume either strong representation conditions or strong distribution-shift conditions.Examples include approximate Bellman closedness and stringent concentrability requirements.
  • Coverage assumptions: This work measures coverage through the spectrum of feature covariance matrices, which is presented as natural for linear function approximation.Prior work often measures state-action coverage using a concentrability coefficient.
  • Policy evaluation: Importance-sampling approaches address offline policy evaluation, while bypassing exponential horizon dependence requires non-trivial function-approximation assumptions.The supplied related-work discussion connects these approaches to the broader horizon-dependence problem.
  • Hardness results: Earlier information-theoretic exponential lower bounds often use exponentially large state spaces or only approximately linear optimal Q-functions.The paper contrasts these constructions with its own setting involving linear Q-functions for every policy.
  • Error amplification: The paper provides an information-theoretic lower bound showing that geometric error amplification is real in offline RL.This extends a concern previously studied in theoretical and empirical RL analyses.

3 The Offline Policy Evaluation Problem

The paper studies offline policy evaluation for finite-horizon MDPs when value functions are represented with linear features. Given offline transition and reward datasets, the goal is to estimate a policy’s value accurately using as few samples as possible.

  • A finite-horizon MDP contains states, actions, transition and reward distributions, a planning horizon H, and a fixed initial state.Policies induce trajectories through states, actions, rewards, and transitions across the H levels.
  • Linear function approximation maps each state-action pair to a d-dimensional feature vector and predicts Q-functions as linear functions of those features.
  • The realizability assumption requires every policy’s Q-functions to be representable linearly in the given features, making it stronger than realizability for only one target policy.
  • Offline reinforcement learning provides datasets of state-action-reward-next-state transitions sampled from distributions at each horizon level.The agent does not directly access the MDP or its transition and reward operators.
  • The offline policy evaluation problem asks for an accurate estimate of a given policy’s value V^π using collected datasets.

4 The Lower Bound: Realizability and Coverage are Insufficient

The paper constructs hard offline-RL instances showing that realizability and strong feature coverage do not ensure sample-efficient policy evaluation. Any algorithm may require exponentially many samples in the horizon, because estimation error can be geometrically amplified through the planning levels.

  • Assumptions: Feature coverage bounds feature norms and requires each data distribution’s feature covariance matrix to have a sufficiently large minimum eigenvalue.The strongest possible coverage condition is used for the lower bound, while 1/d is the largest possible minimum eigenvalue under the bounded-feature condition.
  • Assumptions: Even with realizability and feature coverage, these assumptions are insufficient for sample-efficient offline policy evaluation when H is large.
  • Main lower bound: Ω((d/2)^H) samples are required to estimate any given policy’s value up to constant additive error with probability at least 0.9.The lower bound holds for a deterministic MDP satisfying realizability and feature coverage.
  • Consequences: The hardness also transfers to finding near-optimal policies, while on-policy rollouts can yield polynomial sample complexity in the related LSVI comparison.Under data induced by a fixed policy, a weaker lower bound remains possible, but evaluating that inducing policy is not necessarily hard.
  • Hard instance: The construction supports both deterministic dynamics with stochastic rewards and stochastic transitions with deterministic sparse rewards.Together, the instances show that reward-estimation and transition-estimation errors can both be geometrically amplified.
  • Hard instance: The hard construction uses only two actions and O(d · H) states, avoiding an exponentially large state space.
  • Proof idea: The construction amplifies estimation error from the last level exponentially because the relevant state is absent from the data distribution’s support.

5 Upper Bounds: Low Distribution Shift or Policy Completeness are Sufficient

Under realizability, LSPE can suffer geometric error amplification across the horizon. Sample-efficient evaluation is recovered under sufficiently low distribution shift or stronger representation conditions such as policy completeness.

  • LSPE analysis: LSPE estimates value parameters backward from level H to level 1 using ordinary least squares and plug-in estimates from later levels.The analysis assumes linear Q-functions for the evaluated policy and characterizes the resulting estimation error.
  • Low Distribution Shift: Low distribution shift is formalized by requiring the policy-induced feature covariance to be dominated by the data covariance at every level.The condition is Λh ⪯ ChΛh for each h, with the cumulative product of the Ch terms governing amplification in the theorem.
  • Error amplification: Geometric error amplification can multiply estimation errors across levels, producing an overall amplification factor of roughly ˆd^H/2.In the hard instance, errors grow from roughly N^-1/2 at the final level to a factor associated with ˆd^H/2 as the algorithm proceeds backward.
  • Policy Completeness: Policy completeness is a stronger representation condition than realizability and, with lower-bounded feature covariance eigenvalues, prior work gives polynomial-sample guarantees.Under these assumptions, prior work establishes N = poly(H, d, 1/ε, 1/λ0) for squared value-estimation error at most ε.
  • Conclusion: The section concludes that sample-efficient offline evaluation requires bounded cumulative distribution shift or representation conditions stronger than realizability.The relevant stronger condition highlighted here is policy completeness.

6 Conclusion

The paper studies necessary conditions for sample-efficient offline RL rather than only sufficient conditions. It shows that realizability and feature coverage alone do not prevent exponential sample requirements, so mild distribution shift or stronger representations are needed.

  • Conclusion: The paper asks which representational and distributional conditions are necessary for provably sample-efficient offline RL.This focus complements prior work that largely establishes sufficient conditions.
  • Conclusion: Even perfect representation of a target policy’s value function and good feature coverage can still require exponentially many samples for non-trivial value estimation.The conclusion states this impossibility for off-policy evaluation under the stated assumptions.
  • Conclusion: Sample-efficient offline RL requires sufficiently mild distribution shift or representation conditions substantially stronger than realizability.The paper identifies these as the two supported routes beyond the basic assumptions.

A Another Hard Instance

This hard instance uses deterministic sparse rewards and a stochastic transition construction whose hidden parameter changes a policy value while remaining difficult to identify from offline data. Distinguishing the cases requires exponentially many samples in the horizon.

  • Construction: The hard instance uses deterministic rewards that can be nonzero only at the last level, with data distributions induced by a fixed policy.The construction also specifies linear features with bounded norm and a realizability assumption for the evaluated policy.
  • Construction: The feature map uses orthonormal vectors, while the data distributions are uniform over selected state-action pairs and omit critical actions from their support.These support gaps make the parameter-dependent transitions difficult to observe offline.
  • Hardness argument: The two cases r0 = 0 and r0 = ˆd^-(H−2)/2 share the observed data distributions, feature map, policy, and rewards, but differ in hidden transition behavior.The only distinguishing information comes from querying transition operators through samples from the data distributions.
  • Hardness argument: When r0 = 0 the evaluated policy has value zero, whereas when r0 = ˆd^-(H−2)/2 it has value 1, so 1/2-accurate estimation distinguishes the cases.Thus, non-trivial value estimation entails distinguishing the two transition distributions.
  • Lower bound: Distinguishing the two transition distributions with probability at least 0.9 requires Ω(ˆd^(H−2)) samples, yielding an Ω((d/2 −1)^(H/2)) lower bound in the theorem.The theorem applies to an algorithm given both the policy and feature mapping and targets constant additive accuracy.

B.1 Proof of Lemma 5.1

The proof expands the LSPE estimation error recursively across levels. Each level contributes a propagated term involving the feature matrices and regularized covariance inverses, exposing the source of geometric amplification.

  • Recursive error decomposition: The proof begins with the level-1 estimation error and separates its direct noise term from the propagated error inherited from level 2.This recursive decomposition is the basis for analyzing LSPE under linear realizability.
  • Recursive error decomposition: Repeated substitution expands the propagated term into a product of feature-matrix factors and regularized inverse covariance matrices across later levels.The expansion continues through levels 2, 3, and onward toward level H.

B.2 Proof of Theorem 5.2

The proof derives high-probability bounds using matrix concentration and related concentration results. These bounds contain products of stage-wise factors, together with horizon-, dimension-, confidence-, and regularization-dependent terms.

  • B.2 Proof of Theorem 5.2: Matrix concentration is used to establish a high-probability lemma for each level h.The lemma holds with probability 1 − δ/(4H) for each h.
  • B.2 Proof of Theorem 5.2: The proof propagates stage-wise matrix terms through products involving Φ_h and estimated covariance inverses.The displayed expressions repeatedly combine Φ_h, Φ_{h+1}, and estimated inverse covariance matrices across levels.
  • B.2 Proof of Theorem 5.2: Additional concentration results are invoked to control the final expressions with probability 1 − δ/(4H).The proof cites Theorem 1.2 of Hsu et al. for a final probabilistic bound.
  • B.2 Proof of Theorem 5.2: The resulting bounds include multiplicative factors C_1 × C_2 × ··· × C_h and horizon-, dimension-, confidence-, and regularization-dependent terms.The displayed bounds include terms such as C′H^2d log(H/δ) and λH^2d.
Loading 2010.11895v1…