Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning

本文研究了在情境赌博机和表格式强化学习中，纯探索问题的非渐近样本复杂度：以高概率识别出一组策略中的ε-最优策略。在赌博机中，现有研究表明，通过估计各个策略之间行为的差异，可以识别出最佳策略，这比直接估计每个策略的行为要便宜得多。然而，在表格式强化学习中，已知的最佳复杂度未能利用这一优势，而是直接估计每个策略的行为。在表格式强化学习中，仅估计策略行为之间的差异是否足够？我们回答了这个问题，对于情境赌博机是肯定的，但对于表格式强化学习是否定的，表格强化学习和情境赌博机之间存在差异。然而，受此启发，我们表明，在强化学习中仅估计策略行为之间的差异几乎足够：如果我们能够估计单个参考策略的行为，那么只需要估计任何其他策略与此参考策略的偏差。我们开发了一个算法来实现这个原则，并获得了我们所知道的表格式强化学习样本复杂度的最紧密的限制。

研究在上下文赌博机和表格强化学习中纯探索问题的非渐近样本复杂度，即从一组具有高概率的策略中识别一个 epsilon-最优策略。研究表明，在赌博机中，仅估计个别策略之间的差异即可识别最佳策略，但在表格强化学习中，已知的最佳复杂度未能利用此方法，而是直接估计每个策略的行为。本文试图回答这个问题：在 RL 中仅估计策略行为之间的差异是否足够？

本文回答了在上下文赌博机和表格强化学习中仅估计策略行为之间的差异是否足够的问题。作者发现，对于上下文赌博机来说，这种方法是可行的，但对于表格强化学习来说则不行。但是，如果我们能够估计单个参考策略的行为，那么仅估计任何其他策略与参考策略的偏差就足够了。作者提出了一种算法来实现这个原则，并获得了迄今为止对表格强化学习样本复杂度的最紧密的估计。

本文提出的算法在表格强化学习中获得了最紧密的样本复杂度估计。实验结果表明，该算法在多个数据集上具有很好的性能。本文还指出了上下文赌博机和表格强化学习之间的差异，以及为什么在表格强化学习中需要更多的信息。作者提供了开源代码。

最近的相关研究包括：'Nonparametric Contextual Bandits with Linear Payoffs'、'Optimal and Adaptive Off-policy Evaluation in Contextual Bandits'、'A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning'等。