Thompson 采样

Thompson 采样 (TS, 概率匹配) 是贝叶斯探索算法:为每个臂维护奖励的后验分布,每轮从后验中采样 $\theta_a \sim \text{Beta}(\alpha_a + w_a, \beta_a + l_a)$(Bernoulli 奖励下 Beta 先验是共轭先验,$w_a$/$l_a$ 为臂 $a$ 的累计胜/负次数),然后选择采样值最大的臂。以"当前后验下该臂是最优"的概率选臂 (probability matching):后验越宽(越不确定)的臂越可能被选,天然实现探索-利用权衡。

工业界在线决策的默认算法之一(广告、推荐、实验平台),因为实现简单、样本效率高、实际表现常优于 UCB;面试常考 Beta 后验更新公式与共轭原理。

UCB 的置信上界是频率派构造,对先验知识/奖励分布利用不足;TS 通过后验采样把不确定性直接编码进选择概率,regret 可达 $O(\ln T)$(最坏情形亦有良好保证),对非平稳奖励 (drifting) 更鲁棒,且能自然扩展到上下文特征 (Linear/Logistic TS)。

推导 Beta 后验:先验 $\text{Beta}(\alpha, \beta)$ + Bernoulli 观察 → 后验 $\text{Beta}(\alpha + w, \beta + l)$?

数值题:先验 $\text{Beta}(1,1)$, 臂1 赢 8 输 2、臂2 赢 3 输 7, 写出两个后验并说明下一次采样更可能选哪个臂?

TS 与 UCB 的 regret 对比?为什么工业界 TS 实际表现常更好?

非平稳环境 (奖励漂移) 下 TS 如何退化?有哪些修正?

probability matching 性质:选臂概率 = 该臂为最优的后验概率, 这对探索意味着什么?