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 exponential information-theoretic lower bounds in discounted infinite horizon MDPs with a linear function representation for the action value function even if 1) realizability holds, 2) the batch algorithm observes the exact reward and transition functions, and 3) the batch algorithm is given the best a priori data distribution for the problem class. Furthermore, if the dataset does not come from policy rollouts then the lower bounds hold even if all policies admit a linear representation. If the objective is to find a near-optimal policy, we discover that these hard instances are easily solved by an online algorithm, showing that there exist RL problems where batch RL is exponentially harder than online RL even under the most favorable batch data distribution. In other words, online exploration is critical to enable sample efficient RL with function approximation. A second corollary is the exponential separation between finite and infinite horizon batch problems under our assumptions. On a technical level, this work helps formalize the issue known as deadly triad and explains that the bootstrapping problem is potentially more severe than the extrapolation issue for RL because unlike the latter, bootstrapping cannot be mitigated by adding more samples.

本文介绍了在具有线性函数表示的情况下，在折扣无限时间M​​DPs中分别对策略和目标策略的价值进行估计时，即使存在实现性并观察到精确奖励和转移函数以及为问题类提供最佳先验数据分布，也派生出指数的信息论下限，并引入了一个新的“oracle+ batch algorithm”框架来证明适用于每个分布的底限。工作显示了批处理和在线强化学习之间的指数分离。

批量强化学习的指数下界：相比在线强化学习，批量强化学习可能更加困难