The Curse of Passive Data Collection in Batch Reinforcement Learning
Not on the map. Why?
Abstract (arXiv)
In high stake applications, active experimentation may be considered too risky and thus data are often collected passively. While in simple cases, such as in bandits, passive and active data collection are similarly effective, the price of passive sampling can be much higher when collecting data from a system with controlled states. The main focus of the current paper is the characterization of this price. For example, when learning in episodic finite state-action Markov decision processes (MDPs) with S states and A actions, we show that even with the best (but passively chosen) logging policy, Omega(Amin(S-1, H)/varepsilon2) episodes are necessary (and sufficient) to obtain an ε-optimal policy, where H is the length of episodes. Note that this shows that the sample complexity blows up exponentially compared to the case of active data collection, a result which is not unexpected, but, as far as we know, have not been published beforehand and perhaps the form of the exact expression is a little surprising. We also extend these results in various directions, such as other criteria or learning in the presence of function approximation, with similar conclusions. A remarkable feature of our result is the sharp characterization of the exponent that appears, which is critical for understanding what makes passive learning hard.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 43 of its 58 references that are in the map. First posted on arXiv 18 Jun 2021.
Builds on
43 of 58 references.
References · 43
- 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
- 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,809
- 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learningcited by 1,427
- 2019Stabilizing Off-Policy Q-Learning via Bootstrapping Error Reductioncited by 840
- 2019Behavior Regularized Offline Reinforcement Learningcited by 662
- 2020MOPO: Model-based Offline Policy Optimizationcited by 636
- 2020MOReL : Model-Based Offline Reinforcement Learningcited by 590
- 2021COMBO: Conservative Offline Model-Based Policy Optimizationcited by 370
- 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
- 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 339
- 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
- 2019Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialogcited by 284
31 more
- 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
- 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
- 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 227
- 2020Reward-Free Exploration for Reinforcement Learningcited by 177
- 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
- 2021Offline RL Without Off-Policy Evaluationcited by 151
- 2017Safe Policy Improvement with Baseline Bootstrappingcited by 144
- 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 136
- 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
- 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
- 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
- 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
- 2020Batch Value-function Approximation with Only Realizabilitycited by 104
- 2020The Importance of Pessimism in Fixed-Dataset Policy Optimizationcited by 99
- 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
- 2020Adaptive Reward-Free Explorationcited by 77
- 2020Batch Policy Learning in Average Reward Markov Decision Processescited by 69
- 2021NeoRL: A Near Real-World Benchmark for Offline Reinforcement Learningcited by 63
- 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
- 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reductioncited by 56
- 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiencycited by 56
- 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
- 2019Off-Policy Policy Gradient with State Distribution Correctioncited by 43
- 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
- 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
- 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28
- 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learningcited by 26
- 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 25
- 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
- 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10
- 2020Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?cited by 9
Built on by
Citing papers per year: 2023: 2.
2 papers.