Thompson Sampling for Infinite-Horizon Discounted Decision Processes

我们建立了一个马尔可夫决策过程模型，其参数由一个未知参数决定，并研究了一种基于采样的算法（称为汤普森抽样）的渐近行为。标准的遗憾定义并不总是适用于评估策略，特别是当底层链式结构是一般性的时候。我们表明，标准（期望）遗憾可以（超）线性增长，无法捕捉到在具有非平凡状态演化的实际情况下的学习概念。通过分解标准（期望）遗憾，我们提出了一个新的度量标准，称为期望剩余遗憾，它忘记了过去行动的不可变后果。相反，它衡量了从当前时期开始向前移动的最优奖励与遗憾之间的关系。我们表明，汤普森抽样算法的期望剩余遗憾上界由一个收敛速度指数级快的项上界，该项趋近于0。我们提出了汤普森抽样的后验采样误差几乎肯定收敛于0的条件。然后，我们引入了期望剩余遗憾的概率版本，并提出了它几乎肯定收敛于0的条件。因此，我们为采样算法提供了一个可行的学习概念，这将在比以前考虑的更广泛的情况下有用。

论文试图解决如何在非平凡状态演化的情况下，对采样算法进行评估的问题。该问题下标准的遗憾度量不适用于对策略的评估。

通过分解标准的遗憾度量，提出了一种新的度量方法——期望剩余遗憾，它能更好地衡量当前状态下采样算法的性能。

论文证明了Thompson采样算法的期望剩余遗憾上界收敛于0，同时提出了概率版本的期望剩余遗憾，并给出了其收敛于0的条件。

与该论文相关的研究包括：《A Survey of Monte Carlo Tree Search Methods》、《A Tutorial on Thompson Sampling》等。