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

本文研究了纯探索问题中具有无限多臂的赌博机问题，提出了两种算法，分别以最小的期望和固定样本复杂度为目标，最终准确选择一个高质量臂，使其平均奖励与前 $η$ 的部分的奖励最大值的差别小于 $ε$，并给出了理论证明。