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