The Curse of Passive Data Collection in Batch Reinforcement Learning
This work addresses the challenge of learning from passively collected data in high-stakes RL applications where active experimentation is risky, though it is incremental as it formalizes an expected but previously unquantified limitation.
The paper characterizes the sample complexity gap between passive and active data collection in batch reinforcement learning, showing that passive collection requires Ω(A^min(S-1, H)/ε²) episodes to find an ε-optimal policy in episodic finite MDPs—an exponential blowup compared to active methods.
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 $\mathrm{S}$ states and $\mathrm{A}$ actions, we show that even with the best (but passively chosen) logging policy, $Ω(\mathrm{A}^{\min(\mathrm{S}-1, H)}/\varepsilon^2)$ 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.