Thompson Sampling | Codeboy's Blog

形式陈述

后验采样原则

随机赌博机由未知参数 $\theta$ 决定各臂奖励分布。先验与奖励似然构成一个Bayesian 统计模型，并假定相关历史上的后验存在；给定历史后，算法用Bayes 更新计算它。预先固定可测的最优臂选择 $a^*(\theta)\in\arg\max_a\mu_a(\theta)$ ，包括并列时的选择规则。记

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

Thompson Sampling 在第 $t$ 轮执行：

从后验分布抽取 $\widetilde\theta_t\sim P(\theta\mid H_{t-1})$ ；
选择 $A_t=a^*(\widetilde\theta_t)$ ；
观察所选臂奖励并更新后验。

条件于历史， $\Pr(A_t=a\mid H_{t-1})=\Pr(a^*(\theta)=a\mid H_{t-1})$ 。右侧使用同一个平票规则；若后验对并列最优赋予正质量，不能把它换成“臂 $a$ 属于最优集合”的概率。这种 probability matching 不显式添加置信上界：不确定但可能优秀的臂会因后验样本偶尔偏高而获得探索，已有充分反证的臂则很少被选中。

Bayesian regret 与 frequentist regret

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

\operatorname{BayesRegret}(T) =\mathbb E_{\theta\sim P}\overline{\operatorname{Reg}}_T(\theta), \qquad \overline{\operatorname{Reg}}_T(\theta) =\mathbb E_\theta\sum_{t=1}^T[\mu^*(\theta)-\mu_{A_t}(\theta)].

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

Thompson Sampling 在多种正确指定模型下有 Bayesian 和 frequentist 的遗憾分析。例如固定 Bernoulli 实例、均值在 $(0,1)$ 、唯一最佳臂及各臂独立 Beta $(1,1)$ 先验下，Kaufmann–Korda–Munos 的定理 1 给出首项为 $\sum_{i:\Delta_i>0}\Delta_i\log T/\operatorname{kl}(\mu_i\|\mu^*)$ 的渐近最优界，其中 KL 使用自然对数。这也给出粗略的 $O(\sum_i(\log T)/\Delta_i)$ 量级。其他先验与奖励族需要各自的定理。

直觉

每轮抽取的参数样本可以看成一个仍与历史相容的可能世界。算法在该世界中贪心，因此某臂被探索的频率，正好匹配它当前仍有多大概率是真正最优；数据逐渐排除世界时，行动概率也随之后验收缩。

这种探索不是强制轮换，也不是每次都对均值做乐观修正。不确定性宽的臂偶尔会抽到高值而被选择，持续失败则同时压低后验均值与尾部；探索强度由完整后验形状决定。

Thompson Sampling：每个后验各抽一个参数，最大样本对应的臂被选择并更新 — 后验抽样与概率匹配

例子与边界

Bernoulli–Beta 实例

设臂 $i$ 的奖励为 Bernoulli $(\mu_i)$ ，并置独立先验

\mu_i\sim\operatorname{Beta}(\alpha_i,\beta_i),\qquad\alpha_i,\beta_i>0.

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

\mu_i\mid H_t \sim\operatorname{Beta}(\alpha_i+s_i,\beta_i+f_i).

每轮独立抽取

\widetilde\mu_i\sim\operatorname{Beta}(\alpha_i+s_i,\beta_i+f_i)

并选择最大者。实现维护每臂两个计数，占 $O(K)$ 空间；每轮需 $K$ 次 Beta 后验抽样和 $O(K)$ 次最大值比较，收到奖励后的所选计数更新为 $O(1)$ 。这里 $K$ 是臂数，抽样器本身的代价应另计；这份共轭实现的计数成本不能套到一般非共轭后验。算法可按给定轮数停止，也可持续在线更新；未选择臂的后验不变，因为本轮没有观察它的奖励。

起始采用 Beta $(1,1)$ 时，每臂的先验在 $[0,1]$ 上均匀。某臂连续成功会使其后验右移，但另一臂仍保留抽到较大值的机会。一次失败会降低该臂的后验均值，方差却不一定下降：Beta $(10,1)$ 更新为 Beta $(10,2)$ 时，均值从 $10/11$ 降到 $5/6$ ，方差从 $5/726$ 增至 $5/468$ 。探索概率取决于各臂完整后验之间的比较。

与 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% 错误保证。

推论与应用

Bernoulli–Beta 共轭模型把后验采样化为每臂维护成功与失败计数；更一般的线性、广义线性或组合 bandit 则通过抽取一个共享参数向量，保留动作收益之间的相关结构。这是逐臂独立置信区间不一定能直接表达的优势。

有限时保证必须区分精确后验、近似后验与模型错设。MCMC 或变分误差会改变实际行动分布，错误先验可能延迟最优臂被采样，非平稳环境则使“所有历史来自同一参数”的更新前提失效；这些影响需要各自的稳定性或遗憾分析。

参考资料

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.
Emilie Kaufmann, Nathaniel Korda, Rémi Munos, “Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis,” 2012，定理 1 与 §2 的独立均匀先验设置。
Daniel Russo et al., “A Tutorial on Thompson Sampling,” Foundations and Trends in Machine Learning, 2018.

形式陈述 ​

后验采样原则 ​

Bayesian regret 与 frequentist regret ​

Bernoulli–Beta 实例 ​

与 UCB 的几何差别 ​

先验与近似后验 ​

边界 ​