🤖 machine learning

A Broader View of Thompson Sampling

本文通过将汤普森采样重构为一种模仿平稳贝尔曼最优策略的在线优化算法，阐明了其成功背后的机制，其中贪婪性由残差不确定性进行正则化，从而为理解其动态特性及改进策略提供了新框架。

原作者： Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

发布于 2026-05-28

📖 1 分钟阅读☕ 轻松阅读

原作者： Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是论文《Thompson 采样的更广阔视角》的解释，已转化为通俗易懂的语言并辅以日常类比。

全局概览：解开著名算法的“谜团”

想象你是一位厨师，试图为新菜寻找最佳食谱。你有两种食材（不妨称之为“手臂 1"和“手臂 2"），但你不知道哪一种味道更好。你必须不断烹饪来学习，但同时也希望立刻为顾客提供最好的菜肴。这就是经典的“多臂老虎机”问题：在探索（尝试新事物以学习）和利用（使用已知最佳方案）之间取得平衡。

几十年来，一种名为Thompson 采样的特定方法一直是黄金标准。它之所以闻名，是因为在实践中表现极其出色。然而，与其他规则明确的方法（例如“总是选择置信度最高的选项”）不同，Thompson 采样感觉有点像魔法。它确实有效，但没人能完全解释它为何能如此完美地平衡学习与获利。

这篇论文揭开了谜底。作者表明，Thompson 采样不仅仅是一个幸运的猜测；它实际上是一种复杂的在线优化算法。他们发现，它的工作原理是试图最小化一种特定类型的“遗憾”（即你实际得到的与本可以得到的之间的差异），同时受到不确定性度量的“正则化”（引导）。

核心思想：衡量“遗憾”的新方法

要理解这篇论文，我们需要看看他们如何衡量成功。

旧方法（折扣奖励）：
想象你在玩电子游戏，现在获得的分数价值 100%，但稍后获得的分数只值 90%，然后是 81%，依此类推。这被称为“折扣”。著名的Gittins 指数策略就使用这种方法。它非常适合这个游戏，但有一个缺陷：它可能会过早停止探索一个潜在更好的选项，因为未来的分数看起来不值得冒险。在现实生活中，如果我们希望在很长一段时间内尽可能多地学习，这可能是一个错误。

论文的新方法（平方遗憾）：
作者提出了一种看待问题的新方法。他们不是对未来的收益进行折扣，而是关注遗憾的平方。

类比： 想象你在开车。
- 线性遗憾： 如果你偏离路线 1 英里，你就偏离了 1 英里。如果你偏离了 10 英里，你就偏离了 10 英里。
- 平方遗憾： 如果你偏离路线 1 英里，你就偏离了 1 英里。但如果你偏离了 10 英里，你现在就偏离了100个“糟糕驾驶单位”。
- 这为何重要： 通过平方误差，算法对大错误变得非常敏感。它迫使系统避免巨大的错误，这自然导致了一种策略：既进行足够的探索以避免陷入糟糕的路径，又不会多到浪费时间。

作者将这种方法称为“忠实平稳化”（Faithful Stationarization）。这是一种花哨的说法，意思是：“我们发现了一个随时间保持不变（平稳）的数学规则，但它仍然完美地捕捉到了最小化长期错误的目标（忠实）。”

“秘密配方”：不确定性与张力

论文揭示，Thompson 采样通过解决一个看似如下的数学问题来工作：

最小化（错误）+（不确定性惩罚）

作者将这一过程分解为两种相互竞争的力量：

贪婪（利用）： 你希望选择当前看起来最好的手臂，以获得最大奖励。
正则化（探索）： 你需要一个“惩罚”来阻止你过于贪婪。这种惩罚基于你不知道多少。

发现：
作者发现，Thompson 采样使用了一种特定类型的惩罚，称为双列协方差（Biserial Covariance）。

隐喻： 想象你在赌赛马。
- Thompson 采样的逻辑： “我不确定哪匹马会赢。我越不确定（马匹看起来越相似），我就越应该押注那匹不被看好的马，看看它们是否能赢。”它衡量的是不确定性。
- “贝尔曼最优”逻辑（理想情况）： 作者计算了完美算法会做什么。他们发现，完美算法不仅仅看不确定性；它还看张力。
- 隐喻： “我不确定，但切换值得冒险吗？如果领先的马实际上很强，而黑马很弱，即使我有点不确定，我也不应该切换。但如果领先的马摇摇欲坠，而黑马很强，张力就很高，我必须切换。”

问题：
Thompson 采样有时变得“过于好奇”。它仅仅因为存在一些不确定性，就继续探索一个表现不佳的选项，即使“张力”（切换的好处）实际上很低。这就像因为紧张而每 30 秒检查一次烤箱，尽管食谱说蛋糕没问题。

解决方案：“一步”修复

这篇论文不仅仅批评 Thompson 采样；它还提供了一种利用驱动“完美”算法的相同逻辑来修复它的方法。

他们提出了一个策略改进步骤。

类比： 想象你是一名正在参加考试的学生。
- Thompson 采样： 你根据当前的直觉回答问题。
- 改进： 在交卷之前，你花点时间看看你的答案，并问自己：“如果我在回答这个问题之后知道了我现在所知道的一切，我会改变我的答案吗？”
- 结果： 作者表明，进行这单次“向前看”的步骤，几乎修复了 Thompson 采样的所有缺陷。它将算法从纯粹由“不确定性”驱动转变为由“张力”驱动。

在他们的实验中，这一微小的调整缩小了著名的 Thompson 采样与其理论上的“完美”算法之间90% 的性能差距。

关键要点总结

Thompson 采样是一个优化器： 它不仅仅是一个启发式方法；它是一个最小化特定类型平方误差的算法。
缺陷： 它依赖“不确定性”（我有多困惑），而不是“张力”（切换是否值得努力）。这导致它有时探索过多。
修复： 通过应用标准的“策略改进”步骤（向前看一步），我们可以改变算法，使其专注于“张力”。
结果： 这种简单的调整使算法几乎变得完美，其表现几乎与理论上最佳策略一样好，而无需复杂的数学。

这篇论文本质上是在说：“我们搞清楚了 Thompson 采样的秘密配方。它很棒，但如果你稍微调整一下香料（正则化），使其专注于正确类型的张力，它就会变得更好。”

技术摘要：对汤普森采样的更广泛视角

问题陈述
汤普森采样（TS）是用于多臂老虎机（MAB）问题的广泛使用的启发式方法，以其经验成功和理论 regret 界限而闻名。然而，与上置信界（UCB）或吉廷斯（Gittins）指数策略不同，支配 TS 在探索与利用之间平衡的显式优化原则仍然不透明。虽然吉廷斯（1979）将贝叶斯 MAB 表述为马尔可夫决策过程（MDP）以推导最优策略，但该方法依赖于无限时域折扣奖励。这种表述导致了“不完全学习”（即无限次地未能识别最优臂），这与 MAB 文献中核心的有限时域 regret 最小化目标相矛盾（Robbins 1952；Lai and Robbins 1985）。本文通过寻求一种与有限时域 regret 最小化一致且保留动态规划可处理性的“忠实”（faithful）平稳化表述，来填补对 TS 理解的空白。

方法论
作者提出了一个忠实平稳化框架，将非平稳的有限时域 regret 最小化问题重构为平稳的在线优化问题。

平方 Regret 目标：作者引入最小化累积平方 regret $R_2$ ，而不是直接最小化累积 regret $R_T$ 或使用折扣奖励。他们建立了界限 $R_T \leq \sqrt{R_2 \cdot T}$ 。最小化无限时域的平方 regret 之和 $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ 可确保策略实现最优的 $O(\sqrt{T})$ regret 速率，同时提供平稳目标。
平稳贝尔曼方程：这一新目标导出了价值函数 $V(\pi_t)$ （最小未来平方 regret）的平稳贝尔曼方程：
$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$
与吉廷斯指数（最大化线性折扣奖励）不同，该最小化在动作概率上是二次的，从而导致随机化最优策略，而非确定性策略。
在线优化形式：通过关注期望下一轮奖励 $x_t$ 的变量变换，作者推导出 $R_2$ 最优策略（ $Q_{R2}$ ）采取在线优化问题的形式：
$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$
在此，第一项代表即时利用（贪婪性），第二项是代表探索的线性正则化项。正则化项 $\nu_{R2}(\pi_t)$ 源自贝尔曼方程，衡量了探索与利用之间的张力（即拉动不同臂的未来价值之差）。
重新解读汤普森采样：作者证明，汤普森采样具有完全相同的在线优化形式：
$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$
然而，其正则化项 $\nu_{TS}(\pi_t)$ 是奖励差距（ $\theta_1 - \theta_2$ ）与最优臂身份（ $\text{sign}(\theta_1 - \theta_2)$ ）之间的双列相关系数（biserial covariance）。该正则化项衡量的是关于哪个臂更优的不确定性，而不是即时奖励与未来价值之间的张力。

主要贡献

忠实平稳化：本文引入了一种平稳化表述（最小化平方 regret），保留了有限时域 regret 最小化的本质，弥合了启发式采样与基于原理的动态规划之间的差距。
结构统一：它揭示了汤普森采样和贝尔曼最优策略（ $Q_{R2}$ ）都是在贪婪性与正则化项之间进行权衡的在线优化算法的实例。
机制识别：本文确定了驱动 TS 的具体机制：它基于不确定性（双列相关系数）对贪婪性进行正则化，而最优策略则基于张力（未来价值差异）进行正则化。
策略改进：利用贝尔曼框架，作者为 TS 提出了标准的策略改进步骤。通过评估 TS 的价值函数并将其代回贝尔曼方程，他们推导出了一个改进策略（ $Q_{TS'}$ ），该策略使用基于张力的正则化项。

结果

性能差距：在 Gaussian 和 Bernoulli 老虎机上的数值实验表明， $R_2$ 最优策略（ $Q_{R2}$ ）实现的累积 regret 显著低于汤普森采样。这种差距归因于 TS 的正则化项是一种不确定性度量，当领先臂存在不确定性但次优臂被过度探索时，它无法捕捉到“张力”。
信息导向采样（IDS）：本文发现，另一种启发式方法 IDS 具有与 $Q_{R2}$ 相同的基于张力的正则化项结构，并且其表现与贝尔曼最优策略几乎相同，从而弥合了信息论视角与动态规划视角。
单步改进：对汤普森采样应用单步策略改进，可消除 TS 与贝尔曼最优基准之间约 90% 的性能差距。这一改进有效地将 TS 的正则化项从不确定性度量转变为张力度量。
K 臂情况下的结构属性：在 K 臂设置中，贝尔曼最优策略（以及改进后的 TS）在任何轮次中最多仅对两个臂赋予正概率，而标准 TS 可能对所有臂赋予正概率。策略改进步骤赋予了 TS 这种结构稀疏性。

意义
本文通过将汤普森采样重构为在线优化算法，声称提供了对汤普森采样的“更广泛视角”。这一视角：

解释启发式方法：它阐明了 TS 通过用残余不确定性度量对贪婪性进行正则化，来平衡探索与利用。
识别局限性：它指出，TS 依赖不确定性而非张力，导致其在特定情形下表现次优（例如，当最优臂存在不确定性但次优臂明显被过度探索时）。
实现基于原理的改进：它为改进后验采样算法提供了严谨的框架。通过将正则化项与贝尔曼最优张力度量对齐，作者证明 TS 可以在最小计算开销（单次策略迭代步骤）下得到显著增强，使其在保持基于采样的本质的同时，更接近理论最优。