使用贝叶斯方法的随机算法 Thompson Sampling 在多臂赌博问题中表现显著，本文提供了一种新的悔恨分析方法，同时证明了该算法在期望后悔上的问题特定界限和问题独立界限，方法简单且可适用于更广泛的 contestual bandits 设置。

Sep, 2012

Thompson sampling (TS) is a popular algorithm for solving multi-armed bandit problems; this paper introduces a variant called $\alpha$-TS with tempered likelihoods in the posterior distribution, and provides regret bounds for both instance-dependent and instance-independent scenarios.

Sep, 2023

在随机线性赌博机问题中，我们为 Thompson 采样的后悔证明提供了一种替代证明方法。我们展示了后悔与目标函数的敏感性有关，并且选取与乐观参数相关的最优臂可以控制后悔，在具有固定概率为乐观的采样分布下来看，Thompson 采样可以作为一种通用的随机化算法。我们还证明了这个理论可以轻松应用到正则化线性优化和广义线性模型问题中。

Nov, 2016

本研究针对时间敏感的黑盒优化问题，提出了满足条件的基于 Thompson 抽样的并行贝叶斯优化（STS-PBO）方法，引入了速率失真理论构建平衡学习所需信息量和次优性的损失函数，并采用 Blahut-Arimoto 算法在每一步计算达到最小信息速率的目标解，实验证明我们的 STS-PBO 方法在同步和异步设置中均优于串行方法和传统 Thompson 抽样的并行贝叶斯优化方法。

Oct, 2023

本文提出了多次试验下的 Thompson sampling 方法（MP-TS）并对其进行了后效分析，证明了其具有与 Anantharam 等人提供的最佳后悔下界相匹配的最优后悔上界，并通过计算机模拟进行了验证。我们还提出了 MP-TS 的改进版本，并表明其具有更好的实际效果。

Jun, 2015

我们通过建立一个马尔可夫决策过程模型，研究一种名为汤普森采样的采样算法的渐近行为。我们展示了标准（期望）遗憾可能呈超线性增长，并且不能很好地捕捉到在具有非平凡状态演进的现实情况下的学习概念。通过分解标准（期望）遗憾，我们提出了一种新的指标，称为期望剩余遗憾，它忽略了过去动作的不可变后果，而是测量了当前时期后的最优奖励的遗憾。我们表明，汤普森采样算法的期望剩余遗憾上界由一个指数级快速收敛于 0 的项给定。我们给出了汤普森采样的后验采样误差收敛于 0 的条件，并且引入了期望剩余遗憾的概率版本并给出了其收敛于 0 的条件。因此，我们提供了一个适用于采样算法的学习概念，在比以前考虑的更广泛的情况下将非常有用。

May, 2024

我们研究了基于 Thompson Sampling 的有界奖励随机赌博算法。为了解决现有的与高斯先验的 Thompson Sampling 相关的问题相关后悔界限在 T≤288e^64 时是虚无的问题，我们导出了一个更实用的界限，将主要项的系数从 288e^64 缩小到 1270。此外，我们提出了两种参数化的 Thompson Sampling 算法：带有模型聚合的 TS-MA-α 和带有时间战斗的 TS-TD-α，其中 α∈[0,1] 控制效用与计算之间的权衡。这两种算法都可以实现 O (Kln^(α+1)(T)/Δ) 的后悔界限，其中 K 是臂数量，T 是有限学习时段，Δ 表示拉动次优臂时的单轮性能损失。

May, 2024

本文基于高斯过程置信上界算法（Gaussian process upper confidence bound）和汤普森抽样方法（Thompson sampling）提出了两个贝叶斯优化算法，同时给出了频率学派的遗憾保证和数值结果。

Nov, 2019

本文研究了 Thompson 采样方法在随机组合多臂赌博机框架中的应用，分析了多种算法的累积遗憾，并给出了上限界以及其他算法之间的比较结果。

Mar, 2018

本研究证明了在多种环境设置下，Thompson 采样在强化学习中的贝叶斯后悔限与性能上界，通过使用一组离散的替代环境简化学习问题，并使用后验一致性对信息比例进行了精细分析，从而导出了时间不均匀强化学习问题中的上界，其中 $H$ 是回合长度，$d_{l_1}$ 是环境空间的 Kolmogorov $l_1$ 维度。接着，我们在各种设置中找到了 $d_{l_1}$ 的具体限制，并讨论了我们的结果是首次出现还是改进了现有技术。

Oct, 2023