RL 学习笔记（2）：赌博机问题 • Axi's Blog

引言#

本文主要介绍强化学习 (RL) 中的一个基础问题——赌博机问题 (Bandit Problems)，特别是 K 臂赌博机 (K-Armed Bandit, MAB) 问题。MAB 简化了 RL 问题，去除了“状态”的概念，专注于在单步决策中平衡探索 (Exploration) 与利用 (Exploitation) 的核心挑战。由于其无状态特性，本章状态价值 $V$ 以及动作价值 $Q$ 均不依赖于状态 $s$ 。

K 臂赌博机 (K-Armed Bandit, MAB) 问题#

问题定义#

场景: 存在 $K$ 个选项（“臂”或动作），选择每个臂 $a$ 会根据未知的概率分布 $P_a$ 产生一个奖励。
真实价值: 每个臂 $a$ 的真实期望奖励为 $q_*(a) \doteq \mathbb{E}[R_t | A_t = a]$ 。
过程: 在 $T$ 个时间步内，智能体在每一步 $t$ 选择一个臂 $A_t$ ，获得奖励 $R_{t+1}$ 。
目标: 最大化 $T$ 步内的累积总奖励 $\sum_{t=1}^T R_t$ ，等价于尽快找到并持续选择具有最高真实价值 $q_*(a)$ 的最优臂。
核心挑战: 智能体不知道 $q_*(a)$ ，必须通过尝试来估计。
特性: 无状态，当前选择不影响未来的奖励分布。

遗憾 (Regret)#

定义: 衡量算法性能与理想最优策略差距的指标。
最优价值: $v_* = \max_{a \in \mathcal{A}} q_*(a)$ 。
动作间隙: $\Delta_a = v_* - q_*(a) \ge 0$ 。
总遗憾 (Total/Cumulative Regret): $T$ 步内的总期望机会损失。 $L_T = \mathbb{E}[\sum_{t=1}^T (v_* - q_*(A_t))] = \sum_{a \in \mathcal{A}} \mathbb{E}[N_T(a)] \Delta_a$ 其中 $N_T(a)$ 是动作 $a$ 在 $T$ 步内被选择的总次数。
目标: 设计算法使总遗憾 $L_T$ 随 $T$ 亚线性增长（如 $O(\log T)$ ），而非线性增长 $O(T)$ 。

动作价值估计方法 (Action-Value Methods)#

估计 $q_*(a)$ 是解决 MAB 的基础。

采样平均法 (Sample-Average Method):
- 思想: 使用动作 $a$ 历史上获得的所有奖励的平均值作为其价值估计 $Q_t(a)$ 。 $Q_t(a) \doteq \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbf{1}(A_i=a)}{\sum_{i=1}^{t-1} \mathbf{1}(A_i=a)}$
- 收敛性: 根据大数定律，若每个动作被无限次选择， $Q_t(a)$ 会收敛到 $q_*(a)$ 。
增量式实现 (Incremental Implementation):
- 目的: 高效计算，无需存储所有历史奖励。
- 更新规则: 对于动作 $a$ 的第 $n$ 次选择获得的奖励 $R_n$ ： $Q_{n+1} = Q_n + \frac{1}{n} [R_n - Q_n]$
- 通用形式: NewEstimate <- OldEstimate + StepSize * [Target - OldEstimate]，其中 StepSize $\alpha_n = 1/n$ 。
处理非平稳问题 (Non-stationary Problems):
- 问题: 当 $q_*(a)$ 随时间变化时，采样平均法（步长 $1/n$ ）因给予所有历史奖励同等权重而效果不佳。
- 解决方案: 使用常数步长 (Constant Step-Size) $\alpha \in (0, 1]$ ： $Q_{n+1} = Q_n + \alpha [R_{n+1} - Q_n]$
- 效果: 实现指数近因加权平均，更重视近期奖励，能追踪变化的目标，但不会完全收敛。
步长参数选择 (Step-Size Parameter):
- 收敛条件 (平稳问题，随机逼近理论): $\sum_{n=1}^\infty \alpha_n(a) = \infty \quad \text{和} \quad \sum_{n=1}^\infty \alpha_n^2(a) < \infty$
- $\alpha_n = 1/n$ 满足条件，常数 $\alpha$ 不满足第二个条件。

探索与利用策略#

平衡尝试未知选项（探索）和选择当前最优选项（利用）是 MAB 的核心。

$\epsilon$ -贪心策略 ( $\epsilon$ -Greedy):
- 机制: 以 $1-\epsilon$ 概率选择当前估计值 $Q_t(a)$ 最高的动作（利用），以 $\epsilon$ 概率从所有动作中随机均匀选择一个（探索）。
- 优缺点: 简单，保证持续探索；但探索是随机的，可能导致长期性能损失（线性遗憾）。
乐观初始值 (Optimistic Initial Values):
- 机制: 将所有 $Q_1(a)$ 初始化为一个很高的值，然后始终采取纯贪心策略（选择 $A_t = \arg\max_a Q_t(a)$ ），使用采样平均法（步长 $1/n$ ）更新。
- 效果: 高初始值鼓励智能体尝试所有动作至少一次，实现早期系统性探索。
- 优缺点: 实现简单；但对初始值敏感，随机环境下可能过早锁定次优动作。
置信度上界 (Upper Confidence Bound, UCB):
- 思想: “在不确定性面前保持乐观”。选择潜力大的动作，潜力=高估计值 + 高不确定性。
- 选择规则: $A_t \doteq \arg\max_{a \in \mathcal{A}} \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]$ 其中 $Q_t(a)$ 是利用项， $c \sqrt{\frac{\ln t}{N_t(a)}}$ 是探索项（ $N_t(a)$ 为动作 $a$ 被选次数， $t$ 为总步数， $c$ 为控制探索的参数）。若 $N_t(a)=0$ ，则该项为无穷大。
- 优缺点: 基于 Hoeffding 不等式，有较好的理论遗憾界 ( $O(\log T)$ ) 和实践性能。
- 算法流程(UCB1)
  - 初始化 Q，并且将全部臂都拉取一次，获得更新
  - 每步 $t$ ，根据当前估计值 $Q_t(a)$ 和探索项 $c \sqrt{\frac{\ln t}{N_t(a)}}$ 选择动作 $A_t$ 。
  - 观察奖励 $R_{t+1}$ ，更新 $Q_t(a)$ 和 $N_t(a)$ 。

汤普森采样 (Thompson Sampling / Posterior Sampling):

思想: 贝叶斯方法。维护每个动作价值 $q_*(a)$ 的后验概率分布 $P(q_*(a) | \text{History})$ 。
算法流程:
1. 每步 $t$ ，为每个动作 $a$ 从其后验分布中采样一个价值 $\tilde{q}_a$ 。
2. 选择采样值最大的动作 $A_t = \arg\max_a \tilde{q}_a$ 。
3. 观察奖励 $R_{t+1}$ 。
4. 使用贝叶斯更新规则更新动作 $A_t$ 的后验分布。
探索机制: 后验分布越宽（不确定性高），越有可能采样到高值而被选中。
贝叶斯更新与共轭先验: (以伯努利赌博机为例)
- 奖励为 0/1。似然为伯努利分布。
- 使用 Beta 分布 $Beta(\alpha, \beta)$ 作为共轭先验。
- 更新规则：观察到 1 次成功 (奖励=1) 则 $\alpha \leftarrow \alpha+1$ ，观察到 1 次失败 (奖励=0) 则 $\beta \leftarrow \beta+1$ 。后验仍为 Beta 分布。
优缺点: 实现简单（尤其使用共轭先验时），经验性能通常非常好。

与 Greedy 对比 (伯努利场景):

步骤	BernGreedy (贪心)	BernThompson (汤普森采样)
值计算/采样	计算期望值 $\theta_k = \alpha_k / (\alpha_k + \beta_k)$	从 $Beta(\alpha_k, \beta_k)$ 分布中采样 $\theta_k$
动作选择	选择使 $\theta_k$ 最大的臂 $k$	选择使采样值 $\theta_k$ 最大的臂 $k$
参数更新	根据奖励 $r_t$ 更新 $(\alpha_{x_t}, \beta_{x_t})$	根据奖励 $r_t$ 更新 $(\alpha_{x_t}, \beta_{x_t})$
(循环和应用/观察步骤相同)

梯度赌博机算法 (Gradient Bandit Algorithms)#

这类算法不估计动作价值，而是直接学习动作的偏好 (Preference) $H_t(a)$ 。

动作选择 (Softmax Policy): $\pi_t(a) = P(A_t=a) = \frac{e^{H_t(a)}}{\sum_{b=1}^K e^{H_t(b)}}$
学习规则 (Stochastic Gradient Ascent):
- 更新选中动作 $A_t$ 的偏好： $H_{t+1}(A_t) = H_t(A_t) + \alpha (R_t - \bar{R}_t) (1 - \pi_t(A_t))$
- 更新未选中动作 $a \neq A_t$ 的偏好： $H_{t+1}(a) = H_t(a) - \alpha (R_t - \bar{R}_t) \pi_t(a)$
- $\alpha$ 是学习率， $\bar{R}_t$ 是奖励基线（如历史平均奖励），用于减小方差。 $(R_t - \bar{R}_t)$ 衡量当前奖励的好坏。
- 优缺点: 可处理非平稳环境；对学习率和基线敏感。