Abstract
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)\}/\epsilon^2)\) episodes are necessary (and sufficient) to obtain an \(\epsilon\)-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 be