Thompson Sampling for Infinite-Horizon Discounted Decision Processes

我们建立了一个马尔可夫决策过程模型，其参数由一个未知参数决定，并研究了一种基于采样的算法Thompson采样的渐进行为。标准的遗憾度量并不总是适用于评估一个策略，特别是当底层链式结构是普遍的时候。我们证明标准（期望）遗憾度量可以呈现（超）线性增长，并且无法捕捉到在具有非平凡状态演变的实际环境中的学习概念。通过分解标准（期望）遗憾度量，我们开发了一个新的度量标准，称为期望剩余遗憾度量，它忘记了过去行动的不可改变后果，而是从当前时期开始，测量对最优奖励的遗憾度量。我们证明了Thompson采样算法的期望剩余遗憾度量上界可以通过一个指数级收敛于0的项来界定。我们提出了Thompson采样的后验采样误差几乎肯定收敛于0的条件。然后，我们介绍了期望剩余遗憾度量的概率版本，并提出了几乎肯定收敛于0的条件。因此，我们为采样算法提供了一个可行的学习概念，在比以前考虑的更广泛的情况下发挥作用。

论文旨在解决在具有非平凡状态演变的现实环境中，标准遗憾度量不适用于评估策略的问题。作者提出了一种新的度量方法，即期望残余遗憾，并证明了Thompson采样算法的期望残余遗憾上界可以收敛到0。

论文提出了一种新的度量方法，即期望残余遗憾，它可以更好地评估策略在未来的表现。同时，作者证明了Thompson采样算法的期望残余遗憾上界可以收敛到0，这为采样算法提供了一种可行的学习概念。

论文使用了马尔可夫决策过程模型和Thompson采样算法，提出了一种新的度量方法，即期望残余遗憾，并证明了Thompson采样算法的期望残余遗憾上界可以收敛到0。作者还介绍了概率版本的期望残余遗憾，并证明了它可以几乎必然地收敛到0。这些结果为采样算法提供了一种可行的学习概念，并在更广泛的环境中具有重要的应用价值。

在相关研究方面，与本文相关的研究包括：'Regret analysis of stochastic and nonstochastic multi-armed bandit problems'、'Thompson Sampling for Contextual Bandits with Linear Payoffs'、'Concentration Inequalities for Sampling without Replacement'等。