多臂老虎机问题及其解法

中文精读

原文约 2,526 词 · 15 节

1. 多臂老虎机问题及其解法（总览）

   • 全文目录依次为：利用与探索的权衡、多臂老虎机是什么（定义与策略）、ε-贪心算法、置信上界（Hoeffding 不等式、UCB1、贝叶斯 UCB）、Thompson 采样、案例研究、总结、参考文献。
   • 配套代码在 GitHub 仓库 lilianweng/multi-armed-bandit 中，针对伯努利老虎机（Bernoulli bandit）实现了文中各算法。

2. 利用与探索（Exploitation vs Exploration）

   • 利用与探索的两难出现在生活各方面：每天去熟悉的餐厅能确定吃到什么，却错失发现更好选择的机会；总试新店则免不了时不时吃到难吃的。
   • 在线广告场景类似，需要在已知最有吸引力的广告与可能更成功的新广告之间权衡。
   • 若已完全掌握环境信息，穷举模拟都能找到最优策略，甚至不需要其他聪明方法；难题来自信息不完整。
   • 需要在把风险控制住的同时收集足够信息以做出整体最优决策：利用是采取已知最好的选项，探索是冒风险去了解未知选项。
   • 最优长期策略可能包含短期牺牲，例如一次探索彻底失败，但它提醒我们今后不要过多采取该动作。

3. 什么是多臂老虎机

   • 多臂老虎机是体现利用与探索两难的经典问题：赌场里有多台老虎机，每台单次给奖的概率未知，问题是什么样的策略能获得最高长期回报。
   • 文中只讨论试验次数无限的情形；试验次数有限会引入另一类探索问题，例如当试验次数少于机器数量时，连每台机器都试一遍以估计概率都做不到。
   • 朴素做法是一直玩同一台机器很多轮，依大数定律估计其"真实"回报概率，但这很浪费，也不能保证长期回报最优。
   • 文中配图展示了伯努利多臂老虎机的工作方式：各机器的回报概率对玩家是未知的。

4. 定义（Definition）

   • 伯努利多臂老虎机可表示成元组 ⟨A, R⟩：共 K 台机器，回报概率为 {θ1, …, θK}。
   • 每个时间步 t 对某台老虎机采取动作 a 并得到回报 r；动作集合 A 中每个动作对应与一台机器的交互，动作价值即期望回报 Q(a)=E[r|a]=θ；若 t 时刻动作作用于第 i 台机器，则 Q(a_t)=θ_i。
   • 回报函数 R 是随机的：t 时刻 r_t=R(a_t) 以概率 Q(a_t) 返回 1，否则返回 0。
   • 它是不含状态 S 的马尔可夫决策过程（Markov decision process）的简化版本。
   • 目标是最大化累积回报 Σr_t；若已知最优动作，目标等价于最小化未选最优动作带来的悔值（regret）。
   • 最优动作 a* 的最优回报概率为 θ*=Q(a*)=max_a Q(a)=max_{1≤i≤K} θ_i；损失函数是到时间步 T 为止未选最优动作的总悔值 L_T=E[Σ(θ*−Q(a_t))]。

5. 老虎机策略（Bandit Strategies）

   • 按探索方式划分，求解多臂老虎机有若干类做法。
   • 第一类是不探索，这是最朴素也最差的做法；第二类是随机探索；第三类是聪明地探索，即偏向不确定性高的选项。

6. ε-贪心算法（ε-Greedy Algorithm）

   • ε-贪心大部分时间采取最佳动作，偶尔进行随机探索。
   • 动作价值按过去经验估计：对截至当前时间步 t 观察到的、与目标动作 a 相关的回报取平均，Q̂_t(a) = (1/N_t(a)) Σ r_τ·1[a_τ=a]，其中 1 为二值指示函数，N_t(a) 是动作 a 迄今被选中的次数。
   • 算法以较小概率 ε 采取随机动作，其余（概率 1−ε，即多数时间）选择目前学到的最佳动作 â*_t = argmax_a Q̂_t(a)。
   • 文中给出了作者玩具实现（solvers.py）的链接。
   text

   Q̂_t(a) = (1/N_t(a)) Σ_{τ=1}^{t} r_τ · 1[a_τ = a]
   N_t(a) = Σ_{τ=1}^{t} 1[a_τ = a]
   â*_t = argmax_{a ∈ A} Q̂_t(a)

7. 置信上界（Upper Confidence Bounds）

   • 随机探索让我们有机会尝试了解不多的选项，但可能因运气不好而去探索一个过去已确认很差的动作。
   • 避免这种低效探索有两种思路：一是随时间减小参数 ε；二是对不确定性高的选项保持乐观，优先选择价值估计还不确定的动作，即倾向于探索有较大概率具有最优价值的动作。
   • UCB 算法用回报值的置信上界 Û_t(a) 度量这种潜力，使得真实值以高概率满足 Q(a) ≤ Q̂_t(a)+Û_t(a)；上界 Û_t(a) 是 N_t(a) 的函数，试验次数越多上界越小。
   • UCB 总是选择使置信上界最大的动作：a^UCB_t = argmax_a Q̂_t(a)+Û_t(a)。接下来的问题是怎样估计置信上界。

8. Hoeffding 不等式（Hoeffding's Inequality）

   • 若不想对分布形状作任何先验假设，可借助 Hoeffding 不等式——一个适用于任意有界分布的定理。
   • 设 X1,…,Xt 为独立同分布（i.i.d.）且都落在 [0,1] 区间的随机变量，样本均值 X̄_t=(1/t)ΣX_τ，则对 u>0 有 P[E[X] > X̄_t+u] ≤ e^(−2tu²)。
   • 对某个目标动作 a，把 r_t(a) 视为随机变量、Q(a) 视为真实均值、Q̂_t(a) 视为样本均值、u 视为置信上界 U_t(a)，则 P[Q(a) > Q̂_t(a)+U_t(a)] ≤ e^(−2tU_t(a)²)。
   • 希望以高概率让真实均值低于样本均值加上界，即让 e^(−2tU_t(a)²) 是一个很小的概率；设定该概率等于阈值 p，可解出 U_t(a)=√(−log p / (2N_t(a)))。

9. UCB1

   • 一种启发式做法是让阈值 p 随时间减小，因为观察到的回报越多，越希望上界估计更有把握。
   • 取 p=t^(−4) 即得到 UCB1 算法：U_t(a)=√(2 log t / N_t(a))，动作选择为 a^UCB1_t = argmax_a Q(a)+√(2 log t / N_t(a))。

10. 贝叶斯 UCB（Bayesian UCB）

    • UCB1 等方法不对回报分布作先验假设，只能依赖 Hoeffding 不等式做很通用的估计；若能事先知道分布，就能得到更好的上界。
    • 例如若预期每台机器的平均回报服从高斯分布，可把置信上界设为标准差的若干倍，从而得到 95% 置信区间；图中 c·σ(a_i) 即上界，常数 c 是可调的（tunable）超参数。
    • 文中给出 UCB1 与对 θ 使用 Beta 先验的贝叶斯 UCB 的玩具实现链接。

11. Thompson 采样

    • Thompson 采样思路简单，但在多臂老虎机上效果很好。
    • 每个时间步按动作 a 为最优的概率来选择它：π(a|h_t)=P[Q(a)>Q(a'), ∀a'≠a | h_t]=E_{R|h_t}[1(a=argmax_a Q(a))]，即在给定历史 h_t 下采取动作 a 的概率。
    • 对伯努利老虎机，Q(a) 本质上是伯努利分布的成功概率 θ，因此自然地假定它服从 Beta 分布；Beta(α,β) 取值在 [0,1]，α 与 β 分别对应拿到奖励（成功）与没拿到奖励（失败）的计数。
    • α、β 可依先验知识初始化，例如 α=1、β=1 表示预期成功率 50% 但把握不大；α=1000、β=9000 表示强烈相信成功率是 10%。
    • 每个时间步从各动作的 Beta(α_i, β_i) 中采样一个期望回报 Q̃(a)，选采样值最大的动作 a^TS_t=argmax_a Q̃(a)；观察到真实回报后更新：α_i ← α_i+r_t·1[a^TS_t=a_i]，β_i ← β_i+(1−r_t)·1[a^TS_t=a_i]，这相当于用已知先验与似然做贝叶斯推断求后验。
    • Thompson 采样体现了概率匹配（probability matching）：由于 Q̃ 从后验分布采样，每个概率都等价于在给定历史下该动作最优的概率。

12. Thompson 采样（续）

    • 许多实际复杂问题中，用贝叶斯推断从观测回报估计后验在计算上不可行；若能用 Gibbs 采样、拉普拉斯近似（Laplace approximation）、自助法（bootstrap）等近似后验，Thompson 采样仍可工作。

13. 案例研究（Case Study）

    • 上述算法实现在 lilianweng/multi-armed-bandit 仓库中：BernoulliBandit 对象可用一组随机或预先设定的回报概率构造，各算法实现为 Solver 的子类并以 Bandit 对象为目标问题，随时间记录累积悔值。
    • 小实验设置 K=10 台老虎机，回报概率为 {0.0, 0.1, 0.2, …, 0.9}，每个求解器运行 10000 步。
    • 结果图包括三部分：左图为时间步与累积悔值的关系；中图为真实回报概率与估计概率的对比；右图为 10000 步中各动作被选中的比例。

14. 总结（Summary）

    • 我们需要探索，因为信息是有价值的。
    • 探索策略上可以完全不探索、只关注短期回报；也可以偶尔随机探索；还可以更进一步，对探索哪些选项有所挑剔——更偏好不确定性高的动作，因为它们能带来更高的信息增益。

15. 参考文献（References）

    • CS229 补充讲义：Hoeffding 不等式。
    • David Silver 的强化学习课程第 9 讲：探索与利用。
    • Olivier Chapelle 与 Lihong Li 的 "An empirical evaluation of Thompson sampling"（NIPS 2011）。
    • Russo 等人的 "A Tutorial on Thompson Sampling"（arXiv:1707.02038, 2017）。