多臂老虎机模拟器

多臂老虎机是只有一个状态的强化学习问题：每一步从 $K$ 个臂中选一个拉动，得到随机奖励，目标是最大化累积奖励。它把“探索与利用”的矛盾剥离得最干净，是理解探索策略的最佳实验场。

三种算法

记 $Q_t(a)$ 为臂 $a$ 到第 $t$ 步为止的样本平均奖励，$N_t(a)$ 为拉动次数。

ε-贪心：以 $1-\epsilon$ 的概率选 $\arg \underset{a}{max}{Q}_t(a)$，以 $\epsilon$ 的概率均匀随机选一个臂。简单，但即使已经很确定哪个臂最好，也会一直以固定比例浪费在探索上，所以累积遗憾随时间线性增长。

UCB（上置信界）：先把每个臂各拉一次，之后选

$$A_t=\arg \underset{a}{max}[Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}]$$

第二项是不确定性奖励：拉得少的臂加分多。“面对不确定性保持乐观”，累积遗憾只按 $\ln t$ 增长。

Thompson 采样：为每个臂维护奖励均值的后验分布，每一步从各臂的后验中各采样一个值，选最大的那个。本工具中：

• 伯努利奖励：先验 $\mathrm{Beta}(1,1)$，后验 $\mathrm{Beta}(1+\text{成功次数},1+\text{失败次数})$；
• 高斯奖励（方差已知为 1）：先验 $\mathcal{N}(0,1)$，后验 $\mathcal{N}(\frac{\sum r}{n+1},\frac{1}{n+1})$。

累积遗憾（期望意义下）：${\text{Regret}}_T=\sum _{t=1}^T({\mu }^{\ast }-{\mu }_{A_t})$，其中 ${\mu }^{\ast }$ 是最优臂的真实均值。图中显示的是多次独立实验的平均值。

可以试试

下面的数字都是用本工具的算法模块在默认随机种子（1）下实测得到的，换种子会略有不同。

• 默认设置（高斯、10 臂、1000 步、200 次实验）：这正是 Sutton & Barto 第 2 章的“10 臂测试平台”。最终累积遗憾约为 ε-贪心 231、UCB 149、Thompson 采样 71。
• ε 的取舍：把 ε 改成 0（纯贪心），累积遗憾升到约 477，最后只有约 40% 的实验选中了最优臂——它常常过早锁定在次优臂上。ε = 0.01 在 1000 步时（约 329）还不如 ε = 0.1，但把步数加到 5000，ε = 0.01（约 690）就反超了 ε = 0.1（约 858）：探索少，前期学得慢，长期浪费也少。
• UCB 的 $c$ 要匹配奖励尺度：切换到伯努利奖励时，工具会把 $c$ 设为 1.41（即 UCB1 中的 $\sqrt{2}$），此时 UCB 的累积遗憾约 130，反而不如 ε-贪心（约 68）；改成 $c=2$ 更差（约 182），而 $c=0.5$ 时降到约 36。UCB1 的理论界对任意 [0,1] 奖励都成立，代价是常数偏保守，实践中往往需要调小 $c$。高斯设置下 $c=1$ 也比默认的 $c=2$ 好得多（约 57 对 149）。
• 臂数增加：把 $K$ 调到 30，累积遗憾变为 ε-贪心约 414、UCB 约 392、Thompson 采样约 164，所有算法都需要更多探索。
• 单次实验 vs 平均：把“重复实验”设为 1，曲线会非常嘈杂；这提醒我们，在比较 RL 算法时只看一次运行是不够的。
• 在上面这些设置中，Thompson 采样不需要调参就取得了最低或接近最低的遗憾；只有把 UCB 的 $c$ 仔细调小（例如伯努利奖励下 $c=0.2$，约 28），才能与它（约 29）持平。这也是 Thompson 采样在推荐系统、广告投放等实际场景中被广泛使用的原因之一。

相关教程

• 什么是强化学习：探索与利用。
• Q-learning 与 SARSA：ε-贪心在完整 MDP 中的应用。
• SAC：用熵正则化实现探索的另一种思路。

参考文献

• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.), Chapter 2. MIT Press.
• Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47, 235–256.
• Russo, D., Van Roy, B., Kazerouni, A., Osband, I., & Wen, Z. (2018). A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning. arXiv:1707.02038