多臂赌博机问题中的汤普森采样（Thompson Sampling）算法原理与计算过程
字数 2052 2025-12-13 05:53:12

多臂赌博机问题中的汤普森采样（Thompson Sampling）算法原理与计算过程

题目描述
在多臂赌博机（Multi-Armed Bandit, MAB）问题中，我们面临K个不同的选项（例如K台老虎机或广告位），每台“臂”在每次拉动时以某个未知的概率产生奖励。目标是设计一种策略，通过有限次尝试（如T轮）最大化累积奖励（或最小化累积遗憾）。汤普森采样是一种基于贝叶斯思想的随机化算法，它通过维护每个臂奖励分布的信念（后验分布），并在每轮从这些后验分布中采样来决定选择哪个臂。本题目要求详细解释汤普森采样的原理、计算步骤及其在多臂赌博机问题中的应用。

解题过程

1. 问题形式化
假设有K个臂，每个臂i在拉动时产生一个二元奖励（例如点击/不点击），奖励服从伯努利分布，其成功概率θ_i未知。在每轮t（t=1,...,T），算法选择臂a_t ∈ {1,...,K}，观察到奖励r_t ∈ {0,1}。目标是最大化累积奖励∑{t=1}^T r_t。等效地，最小化累积遗憾（regret）：R(T) = T·max_i θ_i - ∑{t=1}^T θ_{a_t}。

2. 贝叶斯建模
汤普森采样的核心是对每个臂的未知参数θ_i使用贝叶斯推断：

  • 先验分布：假设θ_i服从Beta(α_i, β_i)分布，其中α_i, β_i > 0是超参数。Beta分布是伯努利分布的共轭先验，便于后验更新。
  • 后验分布：在观察到臂i被拉动S_i次成功（奖励=1）和F_i次失败（奖励=0）后，θ_i的后验分布为Beta(α_i + S_i, β_i + F_i)。

3. 汤普森采样步骤
算法流程如下：

  • 初始化：为每个臂i设置先验参数α_i = 1, β_i = 1（即均匀先验Beta(1,1)），相当于对θ_i无偏好。令S_i = 0, F_i = 0。
  • 循环每一轮t=1,...,T：
    1. 采样：对每个臂i，从其当前后验分布Beta(α_i + S_i, β_i + F_i)中独立采样一个值θ̂_i。
    2. 选择臂：选择采样值最大的臂，即a_t = argmax_i θ̂_i。若有多个臂采样值相同，随机选择一个。
    3. 执行与观察：拉动臂a_t，观察到奖励r_t（0或1）。
    4. 更新后验：
      • 若r_t = 1，则S_{a_t} ← S_{a_t} + 1。
      • 若r_t = 0，则F_{a_t} ← F_{a_t} + 1。
        （注意：更新后，臂a_t的后验分布变为Beta(α_{a_t} + S_{a_t}, β_{a_t} + F_{a_t})，其他臂的后验保持不变。）

4. 算法原理解释
汤普森采样通过“采样”实现了探索（exploration）与利用（exploitation）的平衡：

  • 利用：从后验分布采样时，当前估计成功率较高的臂更可能被选中（因为其后验分布更集中于高值）。
  • 探索：由于采样具有随机性，即使某个臂当前估计成功率较低，其后验分布的尾部也可能被采样到，从而有机会被选择。随着数据积累，后验分布逐渐收敛到真实θ_i，探索自然减少。

5. 扩展到非伯努利奖励
汤普森采样可推广到其他奖励分布：

  • 高斯奖励：假设奖励服从N(μ_i, σ_i²)，未知参数μ_i。使用高斯-逆Gamma共轭先验，后验采样类似。
  • 上下文赌博机：每轮有特征向量x_t，奖励模型为θ_i^T x_t + 噪声。使用高斯先验，后验采样涉及线性回归的贝叶斯推断。

6. 计算示例
假设K=2，先验为Beta(1,1)。

  • 第1轮：从Beta(1,1)为两个臂各采样θ̂_1=0.3, θ̂_2=0.6 → 选择臂2，观察到r=1 → 更新臂2：S_2=1, F_2=0，后验为Beta(2,1)。
  • 第2轮：从臂1的Beta(1,1)采样θ̂_1=0.5，从臂2的Beta(2,1)采样θ̂_2=0.7 → 选择臂2，观察到r=0 → 更新臂2：S_2=1, F_2=1，后验为Beta(2,2)。
  • 第3轮：从臂1的Beta(1,1)采样θ̂_1=0.8，从臂2的Beta(2,2)采样θ̂_2=0.4 → 选择臂1，观察到r=1 → 更新臂1：S_1=1, F_1=0，后验为Beta(2,1)。
    如此持续，算法逐渐偏向真实成功率更高的臂。

7. 性能与特点

  • 理论保证：汤普森采样对累积遗憾有对数增长的上界（与UCB算法类似），且在实践中常优于确定性算法（如ε-greedy）。
  • 计算高效：每轮仅需K次采样和一次比较，适合大规模问题。
  • 自适应性：无需手动调节探索参数（如ε），完全由后验分布驱动。

通过以上步骤，汤普森采样以概率匹配（probability matching）的方式，优雅地解决了探索与利用的权衡问题，成为多臂赌博机领域最常用的算法之一。

多臂赌博机问题中的汤普森采样（Thompson Sampling）算法原理与计算过程 题目描述 在多臂赌博机（Multi-Armed Bandit, MAB）问题中，我们面临K个不同的选项（例如K台老虎机或广告位），每台“臂”在每次拉动时以某个未知的概率产生奖励。目标是设计一种策略，通过有限次尝试（如T轮）最大化累积奖励（或最小化累积遗憾）。汤普森采样是一种基于贝叶斯思想的随机化算法，它通过维护每个臂奖励分布的信念（后验分布），并在每轮从这些后验分布中采样来决定选择哪个臂。本题目要求详细解释汤普森采样的原理、计算步骤及其在多臂赌博机问题中的应用。 解题过程 1. 问题形式化 假设有K个臂，每个臂i在拉动时产生一个二元奖励（例如点击/不点击），奖励服从伯努利分布，其成功概率θ_ i未知。在每轮t（t=1,...,T），算法选择臂a_ t ∈ {1,...,K}，观察到奖励r_ t ∈ {0,1}。目标是最大化累积奖励∑ {t=1}^T r_ t。等效地，最小化累积遗憾（regret）：R(T) = T·max_ i θ_ i - ∑ {t=1}^T θ_ {a_ t}。 2. 贝叶斯建模 汤普森采样的核心是对每个臂的未知参数θ_ i使用贝叶斯推断： 先验分布：假设θ_ i服从Beta(α_ i, β_ i)分布，其中α_ i, β_ i > 0是超参数。Beta分布是伯努利分布的共轭先验，便于后验更新。 后验分布：在观察到臂i被拉动S_ i次成功（奖励=1）和F_ i次失败（奖励=0）后，θ_ i的后验分布为Beta(α_ i + S_ i, β_ i + F_ i)。 3. 汤普森采样步骤 算法流程如下： 初始化 ：为每个臂i设置先验参数α_ i = 1, β_ i = 1（即均匀先验Beta(1,1)），相当于对θ_ i无偏好。令S_ i = 0, F_ i = 0。 循环每一轮t=1,...,T ： 采样 ：对每个臂i，从其当前后验分布Beta(α_ i + S_ i, β_ i + F_ i)中独立采样一个值θ̂_ i。 选择臂 ：选择采样值最大的臂，即a_ t = argmax_ i θ̂_ i。若有多个臂采样值相同，随机选择一个。 执行与观察 ：拉动臂a_ t，观察到奖励r_ t（0或1）。 更新后验 ： 若r_ t = 1，则S_ {a_ t} ← S_ {a_ t} + 1。 若r_ t = 0，则F_ {a_ t} ← F_ {a_ t} + 1。 （注意：更新后，臂a_ t的后验分布变为Beta(α_ {a_ t} + S_ {a_ t}, β_ {a_ t} + F_ {a_ t})，其他臂的后验保持不变。） 4. 算法原理解释 汤普森采样通过“采样”实现了探索（exploration）与利用（exploitation）的平衡： 利用 ：从后验分布采样时，当前估计成功率较高的臂更可能被选中（因为其后验分布更集中于高值）。 探索 ：由于采样具有随机性，即使某个臂当前估计成功率较低，其后验分布的尾部也可能被采样到，从而有机会被选择。随着数据积累，后验分布逐渐收敛到真实θ_ i，探索自然减少。 5. 扩展到非伯努利奖励 汤普森采样可推广到其他奖励分布： 高斯奖励 ：假设奖励服从N(μ_ i, σ_ i²)，未知参数μ_ i。使用高斯-逆Gamma共轭先验，后验采样类似。 上下文赌博机 ：每轮有特征向量x_ t，奖励模型为θ_ i^T x_ t + 噪声。使用高斯先验，后验采样涉及线性回归的贝叶斯推断。 6. 计算示例 假设K=2，先验为Beta(1,1)。 第1轮：从Beta(1,1)为两个臂各采样θ̂_ 1=0.3, θ̂_ 2=0.6 → 选择臂2，观察到r=1 → 更新臂2：S_ 2=1, F_ 2=0，后验为Beta(2,1)。 第2轮：从臂1的Beta(1,1)采样θ̂_ 1=0.5，从臂2的Beta(2,1)采样θ̂_ 2=0.7 → 选择臂2，观察到r=0 → 更新臂2：S_ 2=1, F_ 2=1，后验为Beta(2,2)。 第3轮：从臂1的Beta(1,1)采样θ̂_ 1=0.8，从臂2的Beta(2,2)采样θ̂_ 2=0.4 → 选择臂1，观察到r=1 → 更新臂1：S_ 1=1, F_ 1=0，后验为Beta(2,1)。 如此持续，算法逐渐偏向真实成功率更高的臂。 7. 性能与特点 理论保证 ：汤普森采样对累积遗憾有对数增长的上界（与UCB算法类似），且在实践中常优于确定性算法（如ε-greedy）。 计算高效 ：每轮仅需K次采样和一次比较，适合大规模问题。 自适应性 ：无需手动调节探索参数（如ε），完全由后验分布驱动。 通过以上步骤，汤普森采样以概率匹配（probability matching）的方式，优雅地解决了探索与利用的权衡问题，成为多臂赌博机领域最常用的算法之一。