第三章 强化学习 -- 多臂老虎机

一、多臂老虎机问题

1.1 问题形式化

多臂老虎机（Multi-Armed Bandit, MAB） 是强化学习最简单的设定：智能体每一步从 $K$ 个动作（“摇臂”）中选一个，环境返回一个奖励；不存在状态转移，每一步独立。

形式化地，模型由以下要素组成：

• 动作集合 $\mathcal{A}=\{1,2,\dots ,K\}$，每个动作 $a$ 对应一个未知的奖励分布 ${\nu }_a$。
• 在时刻 $t$，智能体选择动作 $A_t\in \mathcal{A}$，观测到奖励 $R_t\sim {\nu }_{A_t}$。
• 智能体的策略 $\pi$ 只依赖于历史 $(A_1,R_1,\dots ,A_{t-1},R_{t-1})$，不依赖于"状态"——因为老虎机没有状态。

每个动作 $a$ 的期望奖励定义为：

$${\mu }_a=\mathbb{E}[R\mid A=a]=\int rd{\nu }_a(r)$$

最优动作 $a^{\ast }=\arg {\max }_a{\mu }_a$ 对应的最大期望奖励为 ${\mu }^{\ast }={\max }_a{\mu }_a$。

MAB 的核心难题是奖励分布未知。智能体必须在"利用已知好的动作"和"探索未知可能更好的动作"之间权衡。表 3-1 展示了 MAB 与一般 RL 的关键区别：

表 3-1 MAB 与一般 RL 的关键区别

1.2 探索与利用权衡

利用（exploitation） 指选择当前估计最优的动作以获取最高即时奖励。

探索（exploration） 指选择估计不确定或次优的动作以获取新的信息，可能在未来获得更高奖励。

二者构成一对根本矛盾：只利用则永远不知道是否有更好的动作；只探索则短期回报很低。MAB 算法设计的核心就是在二者之间取得平衡。

直觉例子：一个 10 臂老虎机中，最优臂的期望奖励是 1.0，其他臂的期望奖励在 0 到 0.9 之间。初始时不知道哪个最优。如果一直贪心选择第一次看起来最好的臂，可能永远错过了真正的最优臂；如果一直随机探索，累积奖励远低于"早早识别最优臂"的策略。

形式化地，可以用"目标冲突"刻画探索-利用张力：

• 短期目标：每步选 $a_t$ 最大化 $R_t$。
• 长期目标：${\sum }_{t=1}^T{R}_t$ 最大化，要求总收益（不只是单步）最大。
• 任何 $a_t$ 的"是否最优"取决于"信息是否足够"——而信息来自被选中的动作。

MAB 算法通过不同方式处理这对冲突：朴素随机/贪心算法只利用或只探索，没有平衡；$\epsilon$-贪心以固定比例混合；UCB 系列"乐观面对不确定性"主动选不确定的动作；Thompson 采样"概率匹配"，按后验概率选动作。

1.3 累积遗憾与平均遗憾

累积遗憾（cumulative regret） 衡量算法在 $T$ 步内相对于"始终选最优动作"的总损失：

$$R(T)\triangleq \sum _{t=1}^T\left({\mu }^{\ast }-{\mu }_{A_t}\right)=\sum _{t=1}^T{\Delta }_{A_t}$$

其中 ${\mu }_{A_t}$ 是动作 $A_t$ 的真实期望奖励；这一形式是伪遗憾（pseudo-regret），与文献标准一致。

其中 ${\Delta }_a={\mu }^{\ast }-{\mu }_a$ 是动作 $a$ 的"次优差距"。最优算法目标是让 $\mathrm{Regret}(T)=o(T)$（次线性增长），即平均遗憾 $\mathrm{Regret}(T)/T\to 0$。

次线性遗憾有两种典型增长率：

• Gap-dependent：$O({\sum }_a\log T/{\Delta }_a)$，UCB1、Auer et al. 2002 Theorem 1 等。
• Gap-free / min-max：$\tilde{O}(\sqrt{KT})$，Auer et al. 2002 / 2003。

朴素策略如 $\epsilon$-贪心的遗憾是 $O(T)$，因为它持续以常数概率做次优探索，从不停下。

二、朴素策略

2.1 随机策略与贪心策略

随机策略：每一步从 $K$ 个动作中等概率采样。设各臂真实期望为 ${\mu }_a$、最优 ${\mu }^{\ast }={\max }_a{\mu }_a$。则在 $T$ 步的累积期望奖励为：

$$\mathbb{E}\left[\sum _{t=1}^T{R}_t\right]=T\cdot \frac{1}{K}\sum _a{\mu }_a$$

累积遗憾为：

$$\mathrm{Regret}(T)=T\cdot \left({\mu }^{\ast }-\frac{1}{K}\sum _a{\mu }_a\right)=\Theta (T)$$

贪心策略：选历史平均奖励最大的动作。形式化：每步 $a_t=\arg {\max }_a{\hat{\mu }}_a$。问题在于初始几步采样不足以估计 ${\mu }_a$：当 ${\mu }_a$ 差异小、样本噪声相对较大时，贪心很容易"锁定"在第一个被随机选到的次优动作上。

反例：$K=2$，${\mu }_1=0.9,{\mu }_2=0.6$。若第一步随机选到 $a=2$（次优），样本平均 ${\hat{\mu }}_2=0.6$。即使 $a=1$ 估计为 0（一次都没选），贪心仍会持续选 $a=2$。此时 $\mathrm{Regret}(T)=0.3T=\Theta (T)$，与随机策略同量级。

# 贪心锁定反例
Q = [0.0, 0.6] # 历史平均：a=1 估计 0（未访问），a=2 估计 0.6
action = Q.index(max(Q)) # 选 a=2 锁定

反直觉之处：贪心策略在样本量极小时等价于"先入为主"。 $\epsilon$-贪心与 UCB 是常见的修复方式。

2.2 ε-贪心与衰减 ε-贪心

$\epsilon$-贪心 以概率 $1-\epsilon$ 选当前最优动作（利用），以概率 $\epsilon$ 在所有动作中均匀随机（探索）：

import random

def epsilon_greedy(Q, epsilon):
if random.random() < epsilon:
return random.randint(0, K – 1) # 探索：随机选
else:
return argmax(Q) # 利用：选历史最优

$\epsilon$ 固定时，$\epsilon$-贪心的遗憾是 $O(T)$——因为无论 $t$ 多大，每步都还有 $\epsilon$ 的概率选次优动作。

衰减 $\epsilon$-贪心 令 $\epsilon$ 随时间衰减，如 ${\epsilon }_t=\min (1,c/t)$。直觉是早期需要更多探索，后期信息积累后逐步转利用。这能让遗憾降到 $O(\log T)$，但需要预设衰减率，工程上不如 UCB 鲁棒。

def decaying_epsilon_greedy(Q, t, c=1.0):
epsilon = min(1.0, c / t)
return epsilon_greedy(Q, epsilon)

$\epsilon$-贪心类方法的工程优点是实现极简，因此在新算法研究的早期 baseline 中经常出现。但其在最优臂与次优臂差距很小时效率低（需要持续随机探索以拉平差距），这一点催生了更聪明的 UCB 与 Thompson 采样。

三、置信上界算法

3.1 Hoeffding 回顾

Hoeffding 不等式 是 UCB 算法的理论基石。设 $X_1,\dots ,X_n$ 是独立随机变量，$X_i\in [a,b]$，$\bar{X}=\frac{1}{n}\sum X_i$ 为样本均值，则对任意 $u>0$：

$$P(\mathbb{E}[X]-\bar{X}\ge u)\le \exp \left(-\frac{2n{u}^2}{(b-a{)}^2}\right)$$

直观：样本均值 $\bar{X}$ 与真实期望 $\mathbb{E}[X]$ 的偏差超过 $u$ 的概率随 $n$ 指数衰减。$n$ 越大，估计越可靠。

UCB 算法把这一不等式"反转"——给定样本均值 $\bar{X}$ 与步数 $n$，估计真值 $\mathbb{E}[X]$ 的上界：

$$\mathbb{E}[X]\le \bar{X}+(b-a)\sqrt{\frac{\log (1/\delta )}{2n}}$$

其中 $\delta$ 是置信水平（如 $\delta =1/t^2$）。这个上界越窄，估计越精确。

3.2 UCB1 算法

UCB1（Auer, Cesa-Bianchi, Fischer 2002）是 UCB 类的经典算法，对每个动作维护：

• $N_a$：动作 $a$ 被选的总次数
• ${\hat{\mu }}_a$：动作 $a$ 的平均奖励

每一步选：

$$A_t=\arg \underset{a}{\max }\left[{\hat{\mu }}_a+\sqrt{\frac{2\log t}{N_a}}\right]$$

直觉：

• 选得多的动作 $N_a$ 大，置信半径小，决策主要由 ${\hat{\mu }}_a$ 决定（利用）。
• 选得少的动作 $N_a$ 小，置信半径大，可能被选中（探索）。

实现中需要处理"某动作从未被选"的情况：通常用 $+\infty$ 表示其上界，保证每个动作至少被试一次。

import math

def ucb1(Q, N, t):
if any(N[a] == 0 for a in range(K)):
return argmin(N) # 优先选未访问过的
return argmax(
Q[a] + math.sqrt(2 * math.log(t) / N[a])
for a in range(K)
)

UCB1 的理论保证：累积遗憾 $\mathrm{Regret}(T)\le 8{\sum }_{a:{\Delta }_a>0}\frac{\log T}{{\Delta }_a}+O(K)$，即对数级遗憾。

3.3 UCB 变体

UCB-V（Audibert, Munos, Szepesvári 2009）在置信上界中引入奖励方差项：

At=arg⁡max⁡a[μ^a+2V^aζlog⁡tNa+3bζlog⁡tNa]
A_t = \\arg\\max_a \\left[ \\hat{\\mu}_a + \\sqrt{\\frac{2 \\hat V_a \\zeta \\log t}{N_a}} + \\frac{3 b \\zeta \\log t}{N_a} \\right]
At​=argamax​​μ^​a​+Na​2V^a​ζlogt​​+Na​3bζlogt​​

其中 ${\hat{V}}_a$ 是动作 $a$ 奖励的样本方差，$\zeta$ 与 $b$ 是论文中的参数（$b$ 是奖励范围上界，$\zeta$ 是控制项）。低方差动作的置信半径更小，更倾向于被利用。

UCB-Tuned（Auer, Cesa-Bianchi, Fischer 2002 第 4 节）在 UCB1 的基础上乘以一个依赖经验方差的修正项：

At=arg⁡max⁡a[μ^a+log⁡tNa⋅min⁡ ⁣{14,σ^a2+2log⁡tNa}]
A_t = \\arg\\max_a \\left[ \\hat{\\mu}_a + \\sqrt{\\frac{\\log t}{N_a} \\cdot \\min\\!\\left\\{\\frac{1}{4}, \\hat\\sigma_a^2 + \\sqrt{\\frac{2 \\log t}{N_a}}\\right\\}} \\right]
At​=argamax​​μ^​a​+Na​logt​⋅min{41​,σ^a2​+Na​2logt​​}​​

其中 ${\hat{\sigma }}_a^2$ 是经验方差。UCB-Tuned 在经验上常常优于 UCB1。

KL-UCB（Garivier, Cappé 2011）用 Kullback-Leibler 散度代替 Hoeffding 边界：

$$A_t=\arg \underset{a}{\max }\sup \left\{q:d({\hat{\mu }}_a,q)\le \frac{\log t+c\log \log t}{N_a}\right\}$$

其中 $d(p,q)$ 是 Bernoulli 分布参数 $p,q$ 间的 KL 散度。理论上 $c\ge 3$ 给出紧上界，实践中 $c=0$ 也常常足够（Pinsker 不等式下不差于 UCB1）。KL-UCB 利用了 KL 散度更紧的 Chernoff 界，在有界奖励下严格不弱于 UCB1。

四、贝叶斯老虎机

4.1 Thompson 采样

Thompson 采样 是贝叶斯框架下的"概率匹配"算法：每一步从动作价值的后验分布中采样一次，按样本值选动作。

for t in range(T):
for a in actions:
theta_a = sample_from_posterior(history, a) # 从后验采样
a_t = argmax(theta_a) # 选样本最大的动作
r_t = env.pull(a_t) # 观测奖励
update_posterior(a_t, r_t) # 更新后验

直觉：后验越分散（不确定性高）的动作，被采样到高值的概率越大，从而被选中的概率越大——这是"概率形式"的探索。Thompson 采样同时实现了利用（高均值动作被采样到高值的概率更高）和探索（不确定性高的动作偶尔会被采样到高值）。

Thompson 采样的理论保证分两类：

• Instance-dependent（依赖 gap ${\Delta }_a$）：UCB1 达到 $O({\sum }_a\log T/{\Delta }_a)$ 的对数级遗憾；Thompson 采样对 Bernoulli 老虎机达 $O(\sqrt{KT\log T})$（Kaufmann et al. 2012 / Agrawal-Goyal 2013）。
• Gap-free / min-max（最坏情况）：UCB1 与 Thompson 采样均达到 $\tilde{O}(\sqrt{KT})$。

工程上 Thompson 采样经验上常常比 UCB 更优，是工业界最常用的老虎机算法——它的"按后验采样"在分布式系统中容易并行化，且超参数少。

4.2 伯努利 Beta 先验

伯努利老虎机 每个动作的奖励 $R\in \{0,1\}$，参数 ${\theta }_a=P(R=1\mid a)$。Beta 分布 $\mathrm{Beta}(\alpha ,\beta )$ 是伯努利参数的共轭先验：

• 先验：${\theta }_a\sim \mathrm{Beta}(1,1)$（均匀分布）
• 观测 $s_a$ 次成功、$f_a$ 次失败后：${\theta }_a\mid \text{data}\sim \mathrm{Beta}(1+s_a,1+f_a)$

import numpy as np

def thompson_bernoulli(success, failure):
samples = [
np.random.beta(success[a] + 1, failure[a] + 1)
for a in range(K)
]
return int(np.argmax(samples))

Beta 分布的优良性质：

• 均值 = $\frac{\alpha }{\alpha +\beta }$，随观测更新。
• 方差 = $\frac{\alpha \beta }{(\alpha +\beta {)}^2(\alpha +\beta +1)}$，观测增多后减小——不确定性自然衰减。
• 后验更新只需"加一"，实现极简。

4.3 高斯老虎机的共轭先验

高斯老虎机 的奖励 $R\sim \mathcal{N}(\mu ,{\sigma }^2)$，方差已知或未知时使用不同的共轭先验：

• 已知方差 ${\sigma }^2$：$\mu$ 的共轭先验是正态分布 $\mathcal{N}({\mu }_0,{\tau }_0^2)$，观测 $n$ 个样本后均值为 $\bar{x}$：

$$\mu \mid \text{data}\sim \mathcal{N}\left(\frac{{\tau }_0^{-2}{\mu }_0+n{\sigma }^{-2}\bar{x}}{{\tau }_0^{-2}+n{\sigma }^{-2}},\frac{1}{{\tau }_0^{-2}+n{\sigma }^{-2}}\right)$$

• 未知方差：使用 Normal-Inverse-Gamma 共轭先验。给定观测数据，先验参数按以下形式更新（标准 NIG 形式）：

$$\mu \mid \text{data},{\sigma }^2\sim \mathcal{N}(m_N,{\sigma }^2/{\kappa }_N)$$

$${\sigma }^2\mid \text{data}\sim \mathrm{Inv}\text{–}\mathrm{Gamma}({\alpha }_N,{\beta }_N)$$

其中 $m_N,{\kappa }_N,{\alpha }_N,{\beta }_N$ 由先验与观测共同决定。工程实现中常直接采样 ${\sigma }^2$、再采样 $\mu$，二者结合给出 $r$ 的后验预测。

工程上高斯老虎机的 Thompson 采样只需：

def thompson_gaussian(sums, counts, prior_mean=0.0, prior_var=1.0, noise_var=1.0):
post_vars = 1.0 / (1.0 / prior_var + counts / noise_var)
post_means = post_vars * (prior_mean / prior_var + sums / noise_var)
samples = np.random.normal(post_means, np.sqrt(post_vars))
return int(np.argmax(samples))

实际推荐系统中经常使用高斯老虎机：CTR 场景下用 Beta-Bernoulli（点击是 Bernoulli 事件）；若奖励是连续近似（如点击深度、停留秒数），可用高斯-Inverse-Gamma。每种观测类型对应不同共轭族，不要混用。

五、上下文老虎机

5.1 问题定义

上下文老虎机（Contextual Bandit, CB） 在 MAB 基础上加入"上下文"信息 $x_t\in {\mathbb{R}}^d$（用户特征、内容特征、时段等），每步智能体观察到 $x_t$，然后选动作 $a_t$ 收到奖励 $r_t$。其与一般 RL 的区别仍然是没有状态转移——每步独立。

形式化：per-round 协议：

• 在时刻 $t$，环境给出上下文 $x_t\in \mathcal{X}\subseteq {\mathbb{R}}^d$。
• 智能体根据历史 $(x_1,a_1,r_1,\dots ,x_{t-1},a_{t-1},r_{t-1})$ 选动作 $a_t$。
• 环境反馈即时奖励 $r_t\in \mathbb{R}$。
• 进入下一轮，无状态转移到 $x_{t+1}$。

未知的奖励函数 $f(x,a)=\mathbb{E}[r\mid x,a]$，目标是学习一个策略 $\pi (a\mid x)$ 最大化累积奖励 ${\sum }_{t=1}^T{r}_t$。

CB 与 MAB、一般 RL 的关键区别：

CB 在工业推荐中非常普遍：每条内容曝光是独立事件，没有跨条目的状态转移，但需要根据用户和内容特征（上下文）做选择。

边界与坑：CB 不处理状态转移不等于"反馈延迟可忽略"。如果决策影响后续上下文分布（如选了某类内容后用户偏好改变），仍然需要进入完整的 MDP/POMDP 框架。

5.2 LinUCB 算法

LinUCB（Li et al. 2010）假设奖励对上下文是线性的：

$$\mathbb{E}[r\mid x,a]=x^{\top }{\theta }_a^{\ast }$$

其中 ${\theta }_a^{\ast }$ 是动作 $a$ 的未知参数向量。算法对每个动作 $a$ 维护：

• $A_a=\lambda I+{\sum }_{t:A_t=a}{x}_t{x}_t^{\top }$（设计矩阵，$\lambda$ 是岭回归正则）
• $b_a={\sum }_{t:A_t=a}{r}_t{x}_t$（奖励加权和）

参数估计 ${\hat{\theta }}_a=A_a^{-1}{b}_a$。每一步的决策：

$$A_t=\arg \underset{a}{\max }\left(x_t^{\top }{\hat{\theta }}_a+\alpha \sqrt{x_t^{\top }{A}_a^{-1}{x}_t}\right)$$

其中第二项是置信上界（类似 UCB1），$\alpha$ 控制探索强度。

LinUCB 的优点：

• 实现相对简单，$A_a$ 可用 Sherman-Morrison 公式增量更新（$d$ 维下复杂度 $O(d^2)$），$A_a^{-1}$ 定期缓存或用 Cholesky 分解。
• 理论遗憾上界 $\tilde{O}(\sqrt{KdT})$（Li et al. 2010 / Abbasi-Yadkori et al. 2011），其中 $K$ 为臂数、$d$ 为上下文维度。

工程上 $\lambda$（岭正则项）原论文取 1；调参时可作为"探索-数值稳定"权衡的旋钮——$\lambda$ 越大，$A_a^{-1}$ 越接近 ${\lambda }^{-1}I$，置信上界 $x_t^{\top }{A}_a^{-1}{x}_t$ 越大、探索越激进。

LinUCB 的局限是线性假设。当真实的 $f(x,a)$ 是非线性时，需要：

• 核化 UCB：把 $x$ 映射到高维核空间（如 RBF 核）。
• 神经网络 UCB：用神经网络拟合 $\hat{f}(x,a)$，并用 ensemble 或 MC Dropout 估计不确定性（详见第十五章）。

Thompson 采样同样可以扩展到上下文场景：对每个动作，从 $P({\theta }_a\mid \text{data})$ 采样再选动作。

Thompson 采样同样可以扩展到上下文场景：对每个动作，从 $P({\theta }_a\mid \text{data})$ 采样再选动作。

何时用 CB、何时升级到完整 RL：对于无状态转移、单步独立反馈的曝光/点击决策（如广告 CTR 优化、内容推荐），CB 已足够；当决策影响后续上下文分布（如选了某类内容后用户偏好改变），则必须进入 MDP/POMDP 框架。

MAB 子集（contextual bandit、贝叶斯老虎机）已经能满足大量业务需求，未必需要进入完整的 MDP 框架——但何时该升级，需要结合任务的"决策对未来的影响"做判断。