Thompson Sampling

后验采样原则 ​

随机赌博机由未知参数 $\theta$ 决定各臂奖励分布。给定历史

$$H_{t-1}=(A_1,Y_1,\dots ,A_{t-1},Y_{t-1}),$$

Thompson Sampling 在第 $t$ 轮执行：

1. 从后验分布抽取 ${\tilde{\theta }}_t\sim P(\theta \mid H_{t-1})$；
2. 选择 $A_t\in \arg \underset{a}{max}{\mu }_a({\tilde{\theta }}_t)$；
3. 观察所选臂奖励并更新后验。

条件于历史，某臂被选择的概率等于它在后验中成为最优臂的概率。这种 probability matching 不显式添加置信上界：不确定但可能优秀的臂会因后验样本偶尔偏高而获得探索，已有充分反证的臂则很少被选中。

Bernoulli–Beta 实例 ​

设臂 $i$ 的奖励为 Bernoulli$({\mu }_i)$，并置独立先验

$${\mu }_i\sim \mathrm{Beta}({\alpha }_i,{\beta }_i).$$

若截至当前臂 $i$ 得到 $s_i$ 次成功、$f_i$ 次失败，则共轭后验为

$${\mu }_i\mid H_t\sim \mathrm{Beta}({\alpha }_i+s_i,{\beta }_i+f_i).$$

每轮独立抽取

$${\tilde{\mu }}_i\sim \mathrm{Beta}({\alpha }_i+s_i,{\beta }_i+f_i)$$

并选择最大者。实现只需维护每臂两个计数；未选择臂的后验不变，因为本轮没有观察它的奖励。

起始采用 Beta$(1,1)$ 时，两臂都完全不确定。某臂连续成功会使其后验右移，但另一臂只要仍宽，就保留抽到较大值的机会。随着失败累积，宽度和均值共同下降，探索概率自然减少。

Bayesian regret 与 frequentist regret ​

Bayesian regret 先假定真实参数 $\theta$ 从所给先验抽取，再对参数、奖励和算法随机性共同取期望：

$$\mathrm{BayesRegret}(T)={\mathbb{E}}_{\theta \sim P}\mathbb{E}[R_T\mid \theta ].$$

它评价一个先验平均问题。Frequentist regret 则固定任意真实参数 $\theta$，只对奖励与算法随机性取期望，要求对每个实例给界。

Thompson Sampling 在多种正确指定模型下同时有 Bayesian 和 frequentist 分析，例如 Bernoulli 多臂情形可得到与 $\sum _{i:{\mathrm{\Delta }}_i>0}(\log T)/{\mathrm{\Delta }}_i$ 同阶的 gap-dependent regret。结论依赖具体先验支持和奖励族；“算法使用后验”本身只定义行为，不自动给任意模型的保证。

与 UCB 的几何差别 ​

UCB 为每个臂构造乐观上界，选择上界最大者；Thompson Sampling 抽取整个可能世界，再在该世界中贪心。前者的探索由确定的置信半径触发，后者由最优事件的后验概率触发。在线性或组合动作中，抽一个参数向量还能保留各动作收益的相关结构，而逐动作置信上界可能需要额外优化。

两者都会把不确定性转成探索，但 Thompson 抽样本身并不要求每次样本都乐观，不能解释为“随机 UCB 常数”。后验尾部来自完整似然和先验，置信上界通常针对 frequentist coverage 设计；二者校准标准不同。

先验的实际作用 ​

一个有信息但正确的先验能减少早期探索；一个过度自信且错误的先验可能长期压制最佳臂。只要先验对真实参数附近仍有足够质量，数据通常能逐渐纠正它，但纠正速度会进入有限时域表现。把先验设为数据拟合后的尖峰、却仍按预先指定先验分析，会重复使用证据。

非共轭模型需要近似后验采样。MCMC、Laplace 或变分近似引入新的计算误差，实际动作分布不再是精确 posterior sampling。此时既要评估奖励模型错设，也要评估后验近似对探索概率的影响。

边界 ​

对抗 bandit 没有固定参数后验可学，朴素 Thompson Sampling 不具备 EXP3 的最坏序列保证。非平稳奖励也会让全部历史的标准 Bayes 更新过度自信，需要遗忘、滑窗或动态模型；这些是模型改变，不是调大先验方差即可完全解决。

Thompson Sampling 最小化的是累计遗憾时的动作选择。若目标是固定置信最佳臂识别，后验停止规则和错误校准需要单独设计，普通 posterior probability 超过 $0.95$ 不自动是 frequentist 5% 错误保证。

参考资料

• William R. Thompson, “On the Likelihood That One Unknown Probability Exceeds Another,” Biometrika, 1933.
• Shipra Agrawal and Navin Goyal, “Analysis of Thompson Sampling for the Multi-armed Bandit Problem,” COLT, 2012.
• Daniel Russo et al., “A Tutorial on Thompson Sampling,” Foundations and Trends in Machine Learning, 2018.