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

Abstract

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).

References in corpus (20)

• Doubly Robust Policy Evaluation and Learning
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processes
• Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction
• Evaluating Reinforcement Learning Algorithms in Observational Health Settings
• Random design analysis of ridge regression
• Safe Policy Improvement with Baseline Bootstrapping
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Agnostic System Identification for Model-Based Reinforcement Learning
• Information-Theoretic Considerations in Batch Reinforcement Learning
• DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correction
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Batch Value-function Approximation with Only Realizability
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• Using Options and Covariance Testing for Long Horizon Off-Policy Policy Evaluation
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Minimax Value Interval for Off-Policy Evaluation and Policy Optimization
• Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Sampling
• Accountable Off-Policy Evaluation With Kernel Bellman Statistics
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization

Cited by in corpus (23)

• Alleviating Matthew Effect of Offline Reinforcement Learning in Interactive Recommendation
• Batch Value-function Approximation with Only Realizability
• Is Pessimism Provably Efficient for Offline RL?
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Offline RL Without Off-Policy Evaluation
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
• A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Representation Learning for Online and Offline RL in Low-rank MDPs
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Fast Rates for the Regret of Offline Reinforcement Learning
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
• Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics
• Safe Policy Improvement Approaches on Discrete Markov Decision Processes
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation
• The Difficulty of Passive Learning in Deep Reinforcement Learning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings
• Finding the Optimal Dynamic Treatment Regime Using Smooth Fisher Consistent Surrogate Loss