RL笔记（2）：多臂老虎机

引言（Introduction）#

在上一章中，我们提到了 RL 的核心矛盾：探索与利用 (Exploration vs. Exploitation)。 为了研究这个问题，我们先暂时把“状态转移”拿掉，看一个最简化的场景——多臂老虎机 (Multi-Armed Bandit, MAB)。

这个问题来源于赌场： 假设你面前有 $K$ 台老虎机。每台老虎机吐钱的概率分布不一样（有的容易赢，有的容易输），但你事先不知道。你的目标是：在有限的操作次数 $T$ 内，获得最大的累积奖励。

这不仅是赌博问题，它在现实中无处不在：

• 推荐系统：把哪部电影推给用户？（探索新电影 vs 利用已知的高分电影）
• 临床试验：给病人用哪种药？（试新药 vs 用疗效确定的旧药）

---

问题定义#

形式化描述#

多臂老虎机问题是一个元组 $\langle \mathcal{A}, \mathcal{R} \rangle$：

• $\mathcal{A}$：动作集合，即 $K$ 个拉杆，$\{a_1, \dots, a_K\}$。
• $\mathcal{R}$：奖励概率分布。对于每个动作 $a$，奖励 $r \sim \mathcal{R}(r|a)$。

累积懊悔 (Cumulative Regret)#

怎么衡量一个算法好不好？我们引入懊悔 (Regret) 的概念。 假设我们开了上帝视角，知道哪台机器最好，那台机器的期望奖励是 $Q^*$。 如果我们选了差的机器，我们就会“后悔”。在 $T$ 步内的总懊悔定义为：

$$R_T = \sum_{t=1}^T (Q^* - q_*(a_t))$$

• $Q^*$：全局最优拉杆的期望奖励。
• $q_*(a_t)$：我们第 $t$ 步实际选的那个拉杆的期望奖励。

我们的目标：设计一个算法，让累积懊悔 $R_T$ 增长得越慢越好（最好是亚线性的，即 $\lim_{T \to \infty} \frac{R_T}{T} = 0$）。这意味着随着时间推移，我们几乎总是选中最好的那台机器。

---

基础：估计期望奖励#

不论用什么算法，我们都需要估计每个拉杆的价值。最简单的方法是增量式蒙特卡洛更新。

假设第 $k$ 个拉杆被选中了 $n$ 次，每次的奖励是 $r_1, \dots, r_n$。 当前的估计值 $Q_n$ 是平均值。当有新的奖励 $r_{n+1}$ 进来时，更新公式为：

$$Q_{n+1} = Q_n + \frac{1}{n+1} (r_{n+1} - Q_n)$$

💡 直觉： $\text{新估计值} = \text{旧估计值} + \text{步长} \times \text{误差}$ 这个公式非常重要，它是后续所有强化学习价值更新的雏形。

---

算法 1：$\epsilon$-Greedy 算法#

这是最直观的平衡策略。

规则#

每次选择动作时，生成一个 $[0, 1]$ 的随机数：

• 以 $1-\epsilon$ 的概率（利用）：选择当前估计值 $Q(a)$ 最高的那个拉杆。
• 以 $\epsilon$ 的概率（探索）：随机选择任意一个拉杆。

衰减的 $\epsilon$#

普通的 $\epsilon$-Greedy 有个缺点：即使已经玩了一万次，明明知道哪个最好，它还是会以固定的 $\epsilon$ 概率去乱选，导致懊悔线性增长。 改进：让 $\epsilon$ 随时间减小，例如 $\epsilon_t = \frac{1}{t}$。

• 初期 $\epsilon$ 大：疯狂探索。
• 后期 $\epsilon$ 小：主要利用，趋近于最优策略。

---

算法 2：上置信界 (UCB)#

$\epsilon$-Greedy 的探索是盲目的。UCB (Upper Confidence Bound) 提出了一种“面对不确定性保持乐观 (Optimism in the Face of Uncertainty)”的原则。

核心思想#

我们给每个拉杆的价值算一个上界。

• 如果一个拉杆估计值高，上界就高。
• 如果一个拉杆被选的次数很少（不确定性大），它的波动范围就大，上界也会很高。 我们每次都选上界最高的那个拉杆。

UCB 公式#

在时刻 $t$，对于动作 $a$，我们计算它的 UCB 分数：

$$\text{Score}_t(a) = \hat{Q}_t(a) + c \sqrt{\frac{\ln t}{N_t(a) + 1}}$$

• $\hat{Q}_t(a)$：当前的平均收益（利用项）。
• $\sqrt{\dots}$：不确定性红利（探索项）。
  • $N_t(a)$ 是动作 $a$ 被选中的次数。分母越小（玩得少），这一项越大。
  • $t$ 是总步数。随着时间推移，如果某个动作一直没被选，分子 $\ln t$ 变大，也会强行把它的分数拉高。
• $c$：超参数，控制探索的权重。

💡 效果： 那些“潜力股”（玩得少）和“绩优股”（均值高）都会被选中，而那些“玩了很多次且证明了很烂”的拉杆会被逐渐抛弃。

---

算法 3：汤普森采样 (Thompson Sampling)#

汤普森采样 (Thompson Sampling)基于贝叶斯 (Bayesian) 思想，比 UCB 更具统计学美感。

核心思想#

我们不维护一个具体的数值 $Q(a)$，而是维护每个拉杆奖励的概率分布。 假设每台老虎机只有“赢”和“输”两种结果（伯努利分布）。我们可以用 Beta 分布 来描述这种不确定性。

流程#

1. 初始化：为每个拉杆 $k$ 维护两个数：$Win_k$（赢的次数）和 $Lose_k$（输的次数）。初始都为 1。
2. 采样：在每一步，对于每个拉杆，从它的 Beta 分布中随机采样一个数： $$\theta_k \sim \text{Beta}(Win_k + 1, Lose_k + 1)$$

   注意：不是选 Beta 分布的均值，而是采样产生一个随机数。如果一个拉杆尝试少，Beta 分布很宽，采样出来的数可能很高也可能很低（探索）。如果尝试多且赢得多，Beta 分布很尖且靠右，采样出来的数大概率很高（利用）。

3. 决策：选择采样值 $\theta_k$ 最大的那个拉杆 $a_t$。
4. 更新：观察实际奖励 $r_t$，如果赢了则 $Win_{a_t} += 1$，输了则 $Lose_{a_t} += 1$。

优势#

汤普森采样在很多实际应用中表现比 UCB 更好，因为它引入了随机性，能更平滑地处理探索与利用，而且对非平稳环境适应性较强。

---

总结#

多臂老虎机是强化学习的“单状态”特例，它教会了我们处理 RL 核心难题的几种范式：

1. 盲目探索：$\epsilon$-Greedy（简单粗暴，但有效）。
2. 乐观探索：UCB（基于不确定性的确定性策略，数学理论完备）。
3. 后验采样：Thompson Sampling（基于概率分布的随机策略，贝叶斯流派）。

解决了怎么选动作的问题，下一章我们将引入状态转移，去面对真正复杂的序列决策问题——马尔可夫决策过程 (MDP)。