汤普森抽样是针对背景盗贼最有效的方法之一，已被推广到某些MDP设置的后验抽样。然而，现有的用于强化学习的后验抽样方法由于基于模型或缺乏线性MDP之外的最坏情况理论保证而受到限制。本文提出了一种新的无模型后验抽样公式，该公式适用于具有理论保证的更一般的情景强化学习问题。我们引入了新的证明技术，以表明在适当的条件下，我们的后验采样方法的最坏情况遗憾与基于优化的方法的最佳已知结果相匹配。在具有维数的线性MDP设置中，与现有基于后验采样的探索算法的二次依赖性相比，我们的算法的遗憾随维数线性缩放。
强化学习问题的一个关键挑战是平衡开发和探索。目标是做出目前预期会产生高回报的决策，并帮助确定未知但可能更好的备选决策。在背景盗贼问题的特殊情况下，这种权衡是很好理解的，最有效和广泛使用的算法之一是汤普森采样[Thompson，1933]。汤普森抽样是一种贝叶斯方法，它保持每个臂的后验分布对于给定的环境是最优的。在每一轮，该算法从该分布中采样一个动作，并用新的观察更新后验。汤普森抽样的流行源于强大的经验表现[Li等人，2010]，以及贝叶斯形式的竞争性理论保证[Russo和Van Roy，2014]和频率后悔界限[Kaufmann等人，2012]。背景强盗设置中的结果促使汤普森抽样对更具挑战性的马尔可夫决策过程（MDP）设置进行了几次调整。最常见的是基于模型的自适应，如PSRL[Strens，2000，Osband等人，2013，Agrawal和Jia，2017]或BOSS[Asmuth等人，2012]，它们在MDP模型上保持后验分布。这些算法通过从后验模型中采样模型并计算其最优策略来确定其当前策略。在模型上维护后验而不是直接使用最优策略或最优值函数的好处是，可以更容易地导出后验更新，并且算法更容易分析。然而，基于模型的方法仅限于小规模问题，其中中等大小的可实现模型类是可用的，并且计算模型的最优策略是可计算的。这排除了观察结果丰富的许多实际问题，例如图像或文本。还有受汤普森采样启发的无模型后验采样算法。这些方法旨在克服基于模型的算法的局限性，只需要一个值函数类，并可能对MDP模型进行较弱的假设。已经提出了几种算法[例如Osband等人，2016a，Fortunato等人，2017，Osband et al.，2018]，具有良好的经验性能，但没有理论性能保证。一个值得注意的例外是Osband等人的随机最小二乘值迭代（RLSVI）算法。[2016b]，该算法允许表格[Russo，2019]和线性Markiov决策过程[Zanette等人，2020a]中的频率后悔界限。然而，据我们所知，除了线性设置之外，没有这样的结果可用。相比之下，最近在基于OFU（面对不确定性的乐观主义）原则开发和分析更一般问题类的可证明有效算法方面取得了令人印象深刻的进展。这些工作表明，只要值函数类和MDP满足一般的结构假设，基于OFU的算法可以以小样本复杂度或遗憾学习好的策略。这些假设包括有界Bellman秩[Jiang等人，2017]、低固有Bellman误差[Zanette等人，2020b]、小Eluder维数[Wang等人，2020]或Bellman Eluder维度[Jin等人，2021]。这提出了一个问题，即基于OFU的算法是否天生更适合这种设置，或者是否有可能使用无模型后验采样方法获得类似的结果。在这项工作中，我们通过分析一种后验抽样算法来回答这个问题，该算法适用于Q函数类，并在一般结构假设下允许最坏情况的遗憾保证。我们的主要贡献是：我们推导了一种无模型后验采样算法，用于一般马尔可夫决策过程和值函数类中的强化学习。我们引入了一种新的证明技术，用于分析具有乐观先验的后验抽样。我们证明了该算法实现了与基于OFU的算法的遗憾匹配的近似最优最坏情况遗憾边界，并改进了后验采样方法的最佳已知遗憾边界。
