In this paper, we study the non-asymptotic sample complexity for the pure exploration problem in contextual bandits and tabular reinforcement learning (RL): identifying an epsilon-optimal policy from a set of policies with high probability. Existing work in bandits has shown that it is possible to identify the best policy by estimating only the difference between the behaviors of individual policies, which can be substantially cheaper than estimating the behavior of each policy directly. However, the best-known complexities in RL fail to take advantage of this and instead estimate the behavior of each policy directly. Does it suffice to estimate only the differences in the behaviors of policies in RL? We answer this question positively for contextual bandits but in the negative for tabular RL, showing a separation between contextual bandits and RL. However, inspired by this, we show that it almost suffices to estimate only the differences in RL: if we can estimate the behavior of a single reference policy, it suffices to only estimate how any other policy deviates from this reference policy. We develop an algorithm which instantiates this principle and obtains, to the best of our knowledge, the tightest known bound on the sample complexity of tabular RL.

本文研究了上下文赌博机和表格强化学习中纯探索问题的非渐进样本复杂度，通过识别高概率下一组策略的ε最优策略。我们发现在上下文赌博机中估计策略行为的差异可以识别出最佳策略，但是在表格强化学习中不成立，这表明上下文赌博机和强化学习之间存在差异。然而，受此启发，我们证明只需要估计强化学习策略与一个参考策略的差异几乎足够，并开发了一个算法，得到了迄今为止对表格强化学习的样本复杂性的最紧密已知界限。

通过策略差异估计在表格强化学习中减少样本复杂度