Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL

Abstract

Several practical applications of reinforcement learning involve an agent learning from past data without the possibility of further exploration. Often these applications require us to 1) identify a near optimal policy or to 2) estimate the value of a target policy. For both tasks we derive \emph{exponential} information-theoretic lower bounds in discounted infinite horizon MDPs with a linear function representation for the action value function even if 1) \emph{realizability} holds, 2) the batch algorithm observes the exact reward and transition \emph{functions}, and 3) the batch algorithm is given the \emph{best} a priori data distribution for the problem class. Our work introduces a new `oracle + batch algorithm' framework to prove lower bounds that hold for every distribution. The work shows an exponential separation between batch and online reinforcement learning.

arXiv commentAccepted to ICML 2021 as long talk

References in corpus (26)

• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling
• Learning Near Optimal Policies with Low Inherent Bellman Error
• Information-Theoretic Considerations in Batch Reinforcement Learning
• On the Sample Complexity of Reinforcement Learning with a Generative Model
• What are the Statistical Limits of Offline RL with Linear Function Approximation?
• Provably Good Batch Reinforcement Learning Without Great Exploration
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Batch Value-function Approximation with Only Realizability
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Learning with Good Feature Representations in Bandits and in RL with a Generative Model
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison
• Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes
• Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?
• Experimental Design for Regret Minimization in Linear Bandits

Cited by in corpus (12)

• Batch Value-function Approximation with Only Realizability
• Near-Optimal Offline Reinforcement Learning via Double Variance Reduction
• Offline RL Without Off-Policy Evaluation
• Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning
• Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coverage
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Instabilities of Offline RL with Pre-Trained Neural Representation
• On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings