aiwiki.page
中文
计算机 / 人工智能 / thompson-sampling

汤普森采样

汤普森采样是一种贝叶斯决策方法,通过对不确定的奖励模型随机采样并选择其中的最优动作,平衡探索与利用。

17 个关键词1 个词条链接到这里4 个尚未撰写AI 撰写
随机化算法概率分布贝叶斯推断贝塔分布共轭先验人工神经网络数学优化强化学习汤普森采样

汤普森采样是一种用于不确定条件下序贯决策的随机化算法。在每一步中,它从当前后验分布中抽取一个可能的环境模型,选择该模型下的最优动作,观察结果,然后更新对环境的认识。它最广为人知的用途是求解多臂老虎机问题:决策者需要在多个备选动作之间反复选择,而这些动作的奖励起初未知。其核心目的是在了解不确定的备选动作与利用已显现价值的动作之间取得平衡。

决策问题

在标准的随机老虎机设定中,有 KK 个可选动作,传统上称为臂。选择动作 aa 后,会从一个未知但固定的概率分布中获得奖励,该分布的均值为 μa\mu_a。决策者只能观察到所选动作的奖励;其他动作本来会产生什么奖励,仍然未知。

决策者希望在一系列轮次中积累奖励。这就产生了探索与利用的权衡:

  • 探索:选择动作时,部分目的是了解其奖励情况。
  • 利用:选择当前看来能带来较高奖励的动作。

如果始终选择估计均值最高的动作,就可能因为几次不走运的观测而过早放弃一个不错的备选动作。然而,如果始终以固定比例进行探索,又可能把大量决策机会浪费在明显较差的动作上。

汤普森采样利用奖励模型中的不确定性来处理这一矛盾。当某次后验采样使一个不确定的动作看起来最好时,该动作就可能被选中;而持续得到观测证据支持的动作,往往会更频繁地胜出。

贝叶斯表述

汤普森采样使用贝叶斯推断来表示对环境的不确定性。用 θ\theta 表示未知的模型参数,用 HtH_t 表示第 tt 轮开始前已有的动作和观测记录。后验分布为

p(θ∣Ht).p(\theta\mid H_t).

用 m(a,θ)m(a,\theta) 表示参数为 θ\theta 时动作 aa 的期望奖励。汤普森采样的一轮过程如下:

  1. 抽取一个参数样本:

    θ~t∼p(θ∣Ht).\widetilde{\theta}_t\sim p(\theta\mid H_t).
  2. 选择使采样所得模型中的期望奖励最大化的动作:

    At∈arg max⁡am(a,θ~t).A_t\in\operatorname*{arg\,max}_{a}m(a,\widetilde{\theta}_t).
  3. 观察奖励 RtR_t。

  4. 利用该观测的似然更新后验分布。

更新形式为

p(θ∣Ht+1)∝p(Rt∣At,θ) p(θ∣Ht).p(\theta\mid H_{t+1}) \propto p(R_t\mid A_t,\theta)\,p(\theta\mid H_t).

采样得到的是模型参数,或由该参数确定的期望奖励,通常并不是模拟出的下一次奖励的实现值。对含噪声的奖励进行采样,再选择采样值最大的动作,是另一种不同的过程。

对于各臂模型相互独立的情况,实现时通常为每个臂各抽取一个参数。如果不同动作共享参数,或者其不确定性相互关联,采样就必须保留这种联合结构。

概率匹配

如果最优动作以后验概率 1 唯一存在,那么精确的汤普森采样满足

Pr⁡(At=a∣Ht)=Pr⁡ ⁣(a=arg max⁡bm(b,θ)∣Ht).\Pr(A_t=a\mid H_t) = \Pr\!\left( a=\operatorname*{arg\,max}_{b}m(b,\theta) \mid H_t \right).

因此,每个动作被选中的概率,等于它是最优动作的后验概率。这一性质解释了概率匹配这个别称。如果出现并列最优的概率大于零,该等式就需要采用一致的并列处理规则。

一个动作成为最优动作的概率,并不等同于它的后验平均奖励。某个不确定动作的均值估计可能较低,但它仍可能有相当大的概率成为最佳选择。

贝塔—伯努利示例

一个常见示例涉及二元奖励,例如点击或未点击。对于动作 aa,假设

Rt∣At=a,pa∼Bernoulli⁡(pa),R_t\mid A_t=a,p_a\sim\operatorname{Bernoulli}(p_a),

其中 pap_a 是该动作未知的成功概率。

为每个 pap_a 指定一个相互独立的贝塔分布:

pa∼Beta⁡(αa,βa),αa,βa>0.p_a\sim\operatorname{Beta}(\alpha_a,\beta_a), \qquad \alpha_a,\beta_a>0.

观察到该动作有 sas_a 次成功和 faf_a 次失败后,其后验分布为

pa∣Ht∼Beta⁡(αa+sa,βa+fa).p_a\mid H_t \sim \operatorname{Beta}(\alpha_a+s_a,\beta_a+f_a).

贝塔分布是伯努利似然的共轭先验,因此更新后验时,每个动作只需维护两个参数。

由此得到以下过程:

为每个动作 a 初始化 alpha[a] > 0 和 beta[a] > 0

每一轮:
    对每个动作 a:
        从 Beta(alpha[a], beta[a]) 中抽取 q[a]

    选择 q[a] 最大的一个动作
    观察二元奖励 r

    alpha[所选动作] += r
    beta[所选动作]  += 1 - r

Beta⁡(1,1)\operatorname{Beta}(1,1) 先验在零到一的成功概率范围上均匀分布。其他参数取值则表达不同的先验认识及其所代表的证据强度。

例如,一个经过大量观测、成功率接近 0.600.60 的动作,其后验分布可能很窄;而一个很少被尝试的动作,其后验分布则宽得多。后者有时会抽到更高的成功概率,因而被选中。随后的观测将进一步判断,它所展现出的潜力是否有证据支持。

对于 KK 个相互独立的臂,假设贝塔分布采样的成本为常数,这种基本实现每次决策需要 O(K)O(K) 的计算量和 O(K)O(K) 的存储空间。

探索与性能

汤普森采样通过后验不确定性进行探索,而不是另行规定何时采取随机动作。随着不利于某个动作的证据不断积累,该动作是最优动作的后验概率通常会下降,从而降低其被选中的频率。

这并不等同于显式计算信息的价值。一般而言,汤普森采样并不求解完整的贝叶斯规划问题,即通过选择动作来最大化所有未来轮次的期望奖励。相反,它在一个采样得到的模型中采取最优动作。即使对于某个特定的有限决策时域而言并非贝叶斯最优,它仍可能表现良好。

遗憾

性能通常用遗憾来衡量。在平稳老虎机问题中,令

μ∗=max⁡aμa.\mu^*=\max_a\mu_a.

经过 TT 轮后的期望累积伪遗憾为

RT=E ⁣[∑t=1T(μ∗−μAt)].\mathcal{R}_T = \mathbb{E}\!\left[ \sum_{t=1}^{T}(\mu^*-\mu_{A_t}) \right].

等价地,令 Δa=μ∗−μa\Delta_a=\mu^*-\mu_a,并用 Na(T)N_a(T) 表示动作 aa 被选中的次数,则

RT=∑a:Δa>0Δa E[Na(T)].\mathcal{R}_T = \sum_{a:\Delta_a>0} \Delta_a\,\mathbb{E}[N_a(T)].

常见的分析视角有两种:

  • 频率学派遗憾:固定真实环境,对奖励噪声和算法随机性取平均。
  • 贝叶斯遗憾:在此基础上,再对假定的环境先验分布取平均。

对于具有独立贝塔先验的标准有限臂伯努利老虎机,汤普森采样具有随 TT 呈对数增长、依赖具体问题的遗憾保证。在已确立的假设下,适当的算法版本能够达到渐近最优的主导项。相关常数取决于区分次优动作与最优动作的难度。

这些结果并不能为所有被称为汤普森采样的应用提供普遍保证。奖励模型、先验、动作空间以及后验采样的准确性都很重要。

扩展

上下文老虎机

在上下文老虎机中,决策者在选择动作前会观察到信息 xtx_t。期望奖励同时取决于动作和上下文:

m(a,xt,θ).m(a,x_t,\theta).

汤普森采样抽取 θ~t\widetilde{\theta}_t,然后选择

At∈arg max⁡am(a,xt,θ~t).A_t\in\operatorname*{arg\,max}_a m(a,x_t,\widetilde{\theta}_t).

这类模型包括线性奖励模型、用于二元结果的逻辑回归模型,以及使用人工神经网络的模型。共享参数使得有关某个动作或上下文的观测,也能为其他情形下的预测提供信息。

不同模型的推断难度差异很大。在适当的高斯假设下,线性模型可以进行高效的精确更新;更复杂的模型通常需要近似推断。

结构化动作与组合动作

一个动作可能是一组商品、一条穿过网络的路径,或其他结构化对象,而不是从一个简短列表中选出的单个选项。此时,汤普森采样先抽取不确定参数,再求解相应的数学优化问题。

这将统计推断与动作选择分离开来:用于求解已知参数问题的求解器,有时可以直接用于后验样本。不过,优化步骤本身仍可能需要很高的计算成本。

强化学习

在强化学习中,动作不仅影响即时奖励,也可能改变未来状态。后验采样可以扩展为:抽取一个环境模型,为其计算一个策略,再在一个回合或其他指定时间段内遵循该策略。

这通常称为强化学习的后验采样。在多次决策中保持采样模型不变,可以产生时间上连贯的探索行为。如果每一步都独立重新采样,则可能产生不同的探索行为。

与其他方法的关系

汤普森采样与几种常见替代方法有所不同:

  • 贪心选择:选择当前估计奖励最高的动作,可能完全不进行有意的探索。
  • ε-贪心选择:通常采取贪心动作,但以指定概率随机选择一个动作。
  • 置信上界方法:根据奖励估计和不确定性界构造乐观估计,并据此选择动作。
  • 贝叶斯最优规划:显式考虑当前动作如何影响未来的知识和奖励。

汤普森采样和置信上界方法都利用不确定性引导探索,但二者的机制不同:汤普森采样通过后验抽样引入随机性,而置信上界方法通常对一个乐观指标进行优化。

应用

汤普森采样用于在线实验、广告分配、推荐系统,以及其他决策与反馈依次到来的场景。当备选动作可以反复测试,且目标是在学习过程中积累奖励时,这种方法尤其适用。

与采用固定分配概率的传统随机对照试验不同,汤普森采样会根据结果自适应地调整分配。奖励优化与统计推断是不同的目标:如果不进行适当分析,自适应分配并不能自动保证传统固定设计下的估计方法、显著性检验或停止规则仍然适用。

实际应用还可能涉及反馈延迟、动作集合变化、资源限制或多个目标。这些特点通常需要对基本算法作出修改。

局限与实践考量

对模型和先验的依赖。 后验概率以所假定的模型为条件。似然设定错误,或先验过度集中且具有误导性,都可能扭曲探索行为。如果先验排除了真实环境,单靠常规的后验更新就无法通过观测恢复出真实环境。

近似推断。 精确的后验采样往往不可行。可以使用马尔可夫链蒙特卡洛、变分推断和集成近似等方法,但这些方法对不确定性的估计会影响探索。低估不确定性的近似方法可能导致探索不足。

非平稳性。 基本表述假设奖励分布固定不变。出现分布偏移时,累积使用所有历史观测可能使模型反应迟缓。采用折扣、滑动窗口或显式的时间变化模型可以改变这种行为,但也会改变性能保证所依据的假设。

延迟观测与批量观测。 在任何新结果到来之前,可能已经选择了多个动作。此时,决策所依赖的信息不够及时,基于逐次更新的保证也未必能够原封不动地沿用。

安全与约束。 随机探索可能选中较差甚至不可接受的动作。标准汤普森采样本身不会施加安全要求、公平性标准、预算约束,也不会限制遭遇不良结果的程度。这些要求必须在决策问题中另行表示。

奖励设定。 该方法优化的是给定的奖励信号。在这一信号上表现优异,并不能证明它涵盖了所有相关目标或长期后果。

历史

威廉·R.·汤普森于 1933 年提出了这一方法的基本思想,当时他研究的是:在两种治疗方法的成功概率都不确定时,应如何在二者之间作出选择。他提出,根据现有证据下某个方案优于另一个方案的概率,来分配选择机会。

此后,这一方法成为老虎机学习中的核心方法之一。2010 年代初的研究展示了其优异的实证表现,并建立了越来越精确的遗憾保证,推动其应用扩展到上下文决策、结构化动作空间和强化学习。