Lecture 9: 数据高效强化学习 —— 评估框架与多臂老虎机（Data Efficient RL: Evaluation Criteria and Bandits）

目录 · ← l8 · l10 →

Lecture 9: 数据高效强化学习 —— 评估框架与多臂老虎机（Data Efficient RL: Evaluation Criteria and Bandits）

对应材料：官方 lecture9pre.pdf（56 页）/ lecture9post.pdf（53 页，含课后修正说明与 UCB 证明骨架）｜Week 6 周一（Feb 9, 2026；Midterm 在 Week 5 周三 Feb 4）｜参考阅读：Sutton & Barto (2018, 2nd ed.) Chp 2、Lattimore & Szepesvári Bandit Algorithms §7.1 一句话定位：L1–L8 一直在问”怎么学“，本讲第一次反过来问”学得有多好“——它建立起整套算法评估标准（evaluation criteria），并选了一个最小、最干净的设定（多臂老虎机）把”探索”这件事从工程技巧变成可以证明的数学对象；L9 给出的 regret 语言，是 L10–L12 全部 fast RL 理论（Bayesian regret、PAC、PAC-MDP、RMax）的共同货币。

9.1 概述

本讲回答一个在本课程中第一次被正式提出的问题：怎样评价一个强化学习算法”好”？（讲义第 6 页 Evaluation Criteria：收敛吗？收敛到最优策略吗？多快收敛？过程中犯了多少错？）此前七讲我们只用了三类非正式标准——经验性能（empirical performance）、收敛性（convergence）、计算复杂度（computational complexity）；本讲引入第四类、也是 data efficient RL 的核心标准：遗憾（regret），即”相对于事后已知的最优决策，我们损失了多少”（讲义第 19 页）。

为了把 regret 讲清楚，Brunskill 选了多臂老虎机（multi-armed bandit, MAB）作为设定（setting）——它把 MDP 里的状态抽掉，只剩”反复做一个决定”，因此延迟后果与泛化暂时消失，只留下探索 vs 利用（exploration-exploitation）这一个难点被赤裸裸地暴露出来。本讲的算法谱系是：贪心（greedy）（第 13–17 页，会永久锁死在次优臂上）→ $\epsilon$-greedy（第 27–32 页，仍有线性 regret）→ 乐观原则（optimism in the face of uncertainty）（第 37–38 页）→ 置信上界算法 UCB（upper confidence bound）（第 39–50 页），最后给出 UCB 的 regret 界证明骨架（第 51–54 页）。

本讲的框架性贡献是讲义第 7 页那张”设定 / 框架 / 方法“三分表：设定（setting）是 Bandits 与 MDPs；框架（framework）是评估标准，用来形式化地度量算法质量；方法（approach）是在某设定下达到某框架的一类算法。这个三分法解释了为什么后面几讲会反复出现”同一个算法同时满足多个框架”（例如 L10 的 Thompson 采样同时给出 Bayesian regret 与频率派 regret 保证）。

9.2 核心概念的数学形式化

9.2.1 RL 的四大要素回顾，以及它们在本讲的位置

严格定义。讲义第 5 页把 RL 拆成四个一般性要素，此处逐条给出精确表述，并标明本讲处理哪一个：

直观解释。这四件事每一个单独看都是已解决的经典问题（优化→凸优化/随机梯度；延迟→动态规划；探索→统计实验设计；泛化→监督学习），RL 的困难在于四者同时存在。本讲的策略是”降维打击“：先在最简设定里把最难的探索问题彻底解决，再(L11–L12)把结论搬回 MDP。

与监督学习的对比。监督学习只有泛化 + 优化两个要素（且优化是凸的）；本讲把这两个都关掉，剩下的遗憾分析给出的下降速率在监督学习里没有对应物——监督学习问”泛化误差 $O(1/\sqrt{n})$”，bandit 问”累计遗憾 $O(\sqrt{AT\ln T})$”，后者是对在线决策损失的度量。

9.2.2 评估标准的完整清单

严格定义。讲义第 19–22 页与第 6、33–35 页给出的标准，逐一严格化如下。约定：$V^$ 或 $\rho^$ 是该环境下的最优可达性能（已知它才能算遗憾），$\hat V_t$ 是算法在第 $t$ 步的估计。

直观解释。把这八条想成考同一场考试的八种评分方式：经验性能是模拟考平均分；渐近收敛是“最终一定会做对”；regret 是“这么多次机会里白白浪费了多少分”；样本复杂度是“要考多少次才能保证及格”；计算复杂度是“每次答题要花多少时间”；PAC 是“以 95% 的把握保证分数不低于 90”；一致性是“长期平均浪费趋于零”。

具体示例（$A=3$ 的 broken-toe 问题，讲义第 14 页）。设三个臂的真实均值为 $Q(a_1)=0.95$（surgery）、$Q(a_2)=0.90$（buddy taping）、$Q(a_3)=0.10$（do nothing），则 $V^*=0.95$，缺口（gap）为

若某算法在第 $t$ 步选了 $a_3$，该步遗憾就是 $0.85$——选错得越离谱，罚得越重，这正是 regret 与”错误次数”两种标准的关键区别。

与监督学习的对比。监督学习只有一个标准（泛化误差 / 测试集精度）加一个约束（训练时间）；RL 有上表八个，且它们互相不可推导：一个算法可以经验性能极好但没有任何 regret 保证（DQN），也可以有漂亮的 $O(\sqrt{T})$ 界但常数大到实践中不可用（朴素的 UCB 在高斯 $A=1000$ 的推荐系统里前期代价很高——见 9.4 实验 A）。

9.2.3 多臂老虎机（MAB）的定义与 regret 的意义

严格定义（讲义第 9 页）。多臂老虎机（multi-armed bandit, MAB）是二元组 $(\mathcal{A},\mathcal{R})$：

每一步 $t$，agent 选 $a_t\in\mathcal{A}$，环境采样 $r_t\sim R_{a_t}$；目标是

记 $\mu_a=\mathbb{E}[r\mid a]=Q(a)$ 为臂 $a$ 的均值奖励，$V^=Q(a^)=\max_{a\in\mathcal{A}}Q(a)$ 为最优值。第 $t$ 步的遗憾（regret）是机会损失

其中期望对选择 $a_t$ 的决策策略取（讲义第 20–21 页）。于是有本讲的第一个核心等价关系：

Regret 分解（讲义第 22 页）。设 $N_t(a)=\sum_{\tau=1}^{t}\mathbb{1}[a_\tau=a]$ 为到 $t$ 为止臂 $a$ 被拉动的次数，缺口（gap） $\Delta_a=V^*-Q(a)$。则

这个分解是全讲的计算引擎：遗憾不再是逐时刻的历史，而变成”每个臂被多拉了几次 × 它的缺口“的加权和。讲义紧接着点出困难所在：好算法要让缺口大的臂被拉得少，但缺口本身是未知的——这正是探索问题。

直观解释。Regret 分解说明：遗憾取决于两件事——(i) 我们是否认得出哪个臂好（认知误差），(ii) 认出之后是否克制得住去试别的臂（实验代价）。贪心只顾后者，$\epsilon$-greedy 被后者限死，UCB 用置信区间同时压住两者。

与 MDP 的对比。MAB 是”单状态 MDP“（L10 第 2 页判断题第 5 条明确把 $k$-armed bandit 说成 single state MDP with $k$ actions）：$\mathcal{S}=\{s\}$，$P(s\vert s,a)=1$，$\gamma=1$。因此 MDP 的 regret 写成 $R(T)=T\rho^-\sum_t r_t$，其中 $\rho^$ 是最优平均奖励；bandit 的一切定义在 $\gamma=1$、单状态下自动退回。反向不成立：MDP 里”探索”还要处理状态泛化，所以 L11–L12 的界会多出 $\vert \mathcal{S}\vert ,\vert \mathcal{A}\vert $ 因子（如 $O(\sqrt{\vert \mathcal{S}\vert \vert \mathcal{A}\vert T})$）。

9.2.4 两种 regret 界的类型（讲义第 34 页）

问题无关界（problem independent）：只作为 $T$（总步数）的函数给出 regret 的增长界，例如 $O(\sqrt{AT\ln T})$。它对所有 bandit 问题一致成立。

问题相关界（problem dependent）：作为各臂被拉次数与缺口 $\Delta_a$ 的函数给出，例如 $\sum_{a:\Delta_a>0}\frac{4\ln T}{\Delta_a}+\Delta_a$ 与 $O(\sum_{a:\Delta_a>0}\frac{\ln T}{\Delta_a})$。它在”臂容易区分”（$\Delta_a$ 大）时更紧，但 $\Delta_a\to 0$ 时发散。

Lai–Robbins 下界（讲义第 35 页）。定理：任何算法的渐近总遗憾至少是对数增长的，

直观解释：分母是臂 $a$ 与最优臂分布的相似度。硬问题 = 两个臂看起来极像但均值不同（$D_{\mathrm{KL}}$ 小），此时你不得不反复试才能分辨，遗憾必然大。这条下界是乐观的（下界只是 $\ln t$，次线性），说明”存在次线性算法”在理论上是有希望的；它同时告诉我们：$O(\ln T)$ 是问题相关的最优速率，而 $O(\sqrt{T})$ 是问题无关的最优速率，二者不矛盾。

9.3 算法伪代码与完整推导

9.3.1 贪心算法（Greedy）

算法 Greedy
输入: 臂集合 A = {a_1,...,a_A}, 时间步数 T
输出: 动作序列 a_1,...,a_T
初始化: N_0(a) = 0, Q̂_0(a) = 0  (∀a ∈ A)
for t = 1, 2, ..., T do
    if t <= A then                        # 每个臂先各采一次
        a_t ← a_t                          # 按顺序初始化
    else
        a_t ← arg max_{a ∈ A} Q̂_{t-1}(a)   # 平局按均匀分配
    end if
    观测奖励 r_t; N_t(a_t) ← N_{t-1}(a_t) + 1
    Q̂_t(a_t) ← Q̂_{t-1}(a_t) + (1/N_t(a_t))·(r_t - Q̂_{t-1}(a_t))
end for

算法逻辑解说。$\hat Q_t(a)=\frac{1}{N_t(a)}\sum_{i=1}^{t} r_i\mathbb{1}[a_i=a]$ 是蒙特卡洛评估（Monte-Carlo evaluation）的均值估计（讲义第 13 页），第 $t$ 步选择 $a_t^*=\arg\max_{a\in\mathcal{A}}\hat Q_{t-1}(a)$。贪心的致命缺陷是零探索：一旦某个次优臂因为一次幸运的采样被推上首位，只要它之后不再被拉动，它的估计就冻结在偏高的值上，最优臂永远翻不了身——讲义第 17 页原话：“Greedy can lock onto suboptimal action, forever.”

具体数值（讲义第 15–16 页，用 9.2.2 的 broken-toe 数据）。先各拉一次：$a_1\to$ 0，$a_2\to+1$，$a_3\to 0$，于是 $\hat Q(a_1)=0,\hat Q(a_2)=1,\hat Q(a_3)=0$。此时 $a_2$ 是唯一最大值，贪心下一次必然选 $a_2$，而真正最优的 $a_1$ 估计值停留在 0——贪心再也不会去检验 surgery 了。发生这一锁定的概率是

若还要求 $a_3$ 也拿到 0（使得 $a_2$ 成为唯一最大），概率为 $0.05\times0.90\times0.90=0.0405$。

与理论的对应。贪心的遗憾是线性的：一旦锁死，每步都付 $\Delta_{a_2}=0.05$（或更糟），$L_T=\Theta(T)$。它不是一致的。

9.3.2 $\epsilon$-greedy 算法与其线性 regret

算法 ε-Greedy
输入: A, T, ε ∈ (0,1]
输出: 动作序列
初始化: N_0(a)=0, Q̂_0(a)=0 (∀a)
for t = 1, 2, ..., T do
    if t <= A then  a_t ← a_t                   # 先各采一次
    else
        以概率 1-ε:  a_t ← arg max_a Q̂_{t-1}(a)  # 利用 (exploit)
        以概率 ε:    a_t ← 从 A 中均匀随机          # 探索 (explore)
    end if
    观测 r_t; 更新 N_t, Q̂_t  (同 Greedy 的增量式均值)
end for

算法逻辑解说（讲义第 27 页）。$\epsilon$-greedy 保证”永远以 $\epsilon$ 的比例做次优决策“。设 $\hat a=\arg\max_a\hat Q(a)$，则对任意非最优臂的期望拉动比例至少是 $\epsilon/A$：

具体数值（讲义第 28 页）。同样的三臂问题，这次首轮采样是 $a_1\to+1,a_2\to+1,a_3\to 0$，于是 $\hat Q(a_1)=\hat Q(a_2)=1,\hat Q(a_3)=0$，置 $\epsilon=0.1$。平局按均匀分配：

线性 regret 的结论。由分解 $L_t=\sum_a\mathbb{E}[N_t(a)]\Delta_a$，若算法以恒定比例选择非最优动作，则 $\mathbb{E}[N_t(a)]=\Theta(t)$，故 $L_t=\Theta(t)$。讲义第 31–32 页的 Check Your Understanding 给出的答案是两条都真：

• 当 $\epsilon=0.1$（固定）时：探索永不停，$L_t\ge \epsilon\cdot t\cdot\frac{1}{A}\sum_a\Delta_a=\Theta(t)$，线性 regret；
• 当 $\epsilon=0$（即纯贪心）时：只要存在某个 $\Delta_a>0$，贪心就可能锁死（9.3.1 的概率 $0.0405$），此时同样 $\Theta(t)$，也是线性 regret。

结论（讲义第 33 页）：“永远探索”和”从不探索”都有线性总遗憾，因此 $\epsilon$-greedy 不是数据高效算法。要次线性，探索量必须随 $t$ 递减。

9.3.3 乐观原则与 UCB：置信界、Hoeffding 到半径

乐观原则（optimism in the face of uncertainty）（讲义第 37–38 页）：选择”有可能价值很高”的动作。理由是两个结果都不亏：

1. 拿到高奖励 —— 如果该臂均值真的高；
2. 学到东西 —— 如果该臂均值其实低，拉它会（在期望上）把它的平均奖励压低、把它的价值不确定性缩小。

严格定义。为每个动作估计一个上置信界 $U_t(a)$，使得 $Q(a)\le U_t(a)$ 以高概率成立；该界依赖于 $N_t(a)$（拉得越多，界越窄）。选择

从 sub-Gaussian 到 UCB1（讲义第 40–44 页，引自 Lattimore & Szepesvári Bandit Algorithms Corollary 5.5）。若 $X_i-\mu$ 独立且 $\sigma$-sub-Gaussian，$\hat\mu=\frac1n\sum_{t=1}^n X_t$，则对任意 $\varepsilon\ge 0$：

令右侧 $=\delta$ 反解 $\varepsilon$：以概率至少 $1-\delta$，

（课后补充讲义第 43 页：若要同时控制上下两侧，取 $\delta^{\prime}=\delta/2$ 并用并集界（union bound） $P(\cup_i E_i)\le\sum_i P(E_i)$，得 $\vert \mu-\hat\mu\vert \le\sqrt{2\sigma^2\ln(2/\delta)/n}$。）

假设奖励是 1-sub-Gaussian（$\sigma^2=1$），代入即得讲义第 44 页的 UCB1：

Hoeffding 不等式的等价格式（本讲任务的指定形式）。对 $[0,1]$ 有界奖励，Hoeffding 给

具体数值（讲义第 45–50 页的 toy 例子）。三个臂同前；先各拉一次得 $\hat Q(a_1)=1,\hat Q(a_2)=1,\hat Q(a_3)=0$。取 UCB1 形式 $\sqrt{2\ln(1/\delta)/N_t(a)}$ 并令 $\delta=1/t^2$（讲义第 54 页选定的调度），则等价于 $\sqrt{4\ln t/N_t(a)}$。当 $t=3$：$\ln(3)=1.0986$，半径 $=\sqrt{4\times1.0986/1}=2.0963$，于是

$t=3$ 时选 $\arg\max$ 在 $a_1,a_2$ 之间并列（讲义幻灯片只写”选择 $\arg\max_a\mathrm{UCB}(a)$”，实际需要平局规则），但关键点是：$a_3$ 虽然经验均值最低，仍被”高估的乐观值”保持在候选集中，只要它的不确定性还没消除。随着 $\ln t/N_t(a)$ 收缩，$a_3$ 的上界会掉到 $a_1$ 之下；反之，只要某臂的界仍高，它就一直有机会被检验——乐观自动带来了”按需探索”。

9.3.4 UCB 的 regret 界：结论与证明骨架（讲义第 51–54 页）

注意：讲义第 51 页（post 第 51 页）Brunskill 明确说明她课上想给的”更短版本”证明在讲课时发现了一个错误，修正版在 Lecture 10 给出，并遵循 Bandit Algorithms Theorem 7.1。因此本节只给骨架与关键中间不等式；完整的技术细节（good event 的完整展开、$n_t(a)$ 界的逐项求和计算）留待 L10。

第一步：遗憾分解。记 $\Delta_i=\mu^\star-\mu_i$，$N_i(n)$ 为臂 $i$ 到时刻 $n$ 被拉动的次数。由 9.2.3 的分解，

于是问题化为：证明非最优臂被拉动的次数只有 $O(\ln n/\Delta_i^2)$ 那么多。

第二步：定义 good event 并用并集界控制它。定义臂 $i$ 的”好事件”为真实均值始终不超过它的 UCB：

由 9.3.3 的单侧界，每个 $(\text{臂},\text{时刻})$ 对的失败概率是 $\delta$；对所有臂与所有 $t\le n$ 取并集界（讲义第 50/51 页强调的 “Subtle: $P(\cup_i E_i)\le\sum_i P(E_i)$”）得到

第三步：好事件下非最优臂的拉动次数上界。令

断言：若 $\mathcal{G}$ 成立，则非最优臂 $i\neq a^\star$ 在”它的 UC 界由至少 $U_i$ 次观测算出”之后，至多再被拉 $U_i$ 次（等价地，$\mathcal{G}$ 下 $N_n(i)$ 被 $U_i$ 加一个常数控制）。证明（反证）：设 $\mathcal{G}$ 成立，并考虑某个时刻 $t$，此时臂 $i$ 已有 $N_{t-1}(i)\ge U_i$ 次观测。于是

第一个不等号用了 $\mathcal{G}$（即 $\hat\mu_i\le\mu_i+$ 半径）与 $N_{t-1}(i)\ge U_i$（使半径不超过 $\sqrt{2\ln(1/\delta)/U_i}$），第二个等号是把 $U_i$ 的定义代回。另一方面由 $\mathcal{G}$ 的定义，$\mu^\star<\mathrm{UCB}_{a^\star}(t,\delta)$。于是

即 $a^\star$ 的界严格大于 $i$ 的界，$i$ 在时刻 $t$ 不可能被选。由于该论证对任何满足 $N_{t-1}(i)\ge U_i$ 的 $t$ 都成立，臂 $i$ 一旦积累到 $U_i$ 次观测就被永久排除，故 $\mathcal{G}$ 下 $N_n(i)\le U_i+1$（$+1$ 来自触发排除的那一次）。

第四步：合起来，选 $\delta=1/n^2$。用”好事件 / 坏事件”分解 $\mathbb{E}[N_n(i)]\le U_i+1+P(\mathcal{G}^c)\,n$，并取 $\delta=1/n^2$ 使 $P(\mathcal{G}^c)\le An\cdot n^{-2}=A/n$，于是坏事件贡献 $\le\frac{A}{n}\cdot n=A$：

代回第一步的分解（并由 $\Delta_{a^\star}=0$ 略去最优臂项），得到讲义第 54 页的问题相关界：

（后一项 $\sum_i\Delta_i$ 是初始化阶段每臂各拉一次、以及坏事件贡献 $A$ 带来的常数级代价。）

第五步：化成问题无关界。问题相关界 $\sum_i\frac{4\ln n}{\Delta_i}$ 在某个 $\Delta_i\to0$ 时发散，必须转成只依赖 $A,T$ 的形式。起点是把上一步的计数界写成”截断”形式：

分组（threshold split）：取阈值 $\delta:=2\sqrt{\ln T/T}$，把所有次优臂分成”大缺口组” $\Delta_i>\delta$ 与”小缺口组” $\Delta_i\le\delta$。

• 大缺口组用第二项（计数界）：$\sum_i\Delta_i\cdot\frac{4\ln T}{\Delta_i^2}=\sum_i\frac{4\ln T}{\Delta_i}\le A\cdot\frac{4\ln T}{\delta}=A\cdot\frac{4\ln T}{2\sqrt{\ln T/T}}=2A\sqrt{T\ln T}$。
• 小缺口组用第一项（$T$）：$\sum_i\Delta_i T\le A\,\delta\,T=2A\sqrt{T\ln T}$。

两组相加给出

而更精细的分组与逐臂计数（把上式中的 $A$ 吸收进 $\sqrt{\cdot}$，或改用按臂分组、利用 $\sum_i\Delta_i$ 项）给出标准教科书形式

这里必须诚实：从”问题相关界 + 一次阈值分组”到 $\sqrt{AT\ln T}$ 这一步不是一行代数——上式的 $A$ 与 $\sqrt{A}$ 之差取决于如何把 $\sum_i\min(T,4\ln T/\Delta_i^2)\Delta_i$ 重新组织。完整、无 gap 的推导在 L10（对应 Bandit Algorithms Theorem 7.1）。本讲只需要记住形状：$R(T)$ 是 $\sqrt{T}$ 与 $\sqrt{\ln T}$ 的乘积，因此 $R(T)/T\to0$。

结论的意义。因为 $\sqrt{AT\ln T}/T=\sqrt{A\ln T/T}\to 0$，UCB1 的平均遗憾趋于 0——它是一致的、次线性的。对比 9.3.2：$\epsilon$-greedy 的 $R(T)=\Theta(T)$，而 UCB1 是 $O(\sqrt{T\ln T})$，在 $T$ 上相差约 $\sqrt{T}$ 倍（$T=10^6$ 时是 1000 倍量级）——这就是”数据高效”与”数据低效”的定量区别。与 Lai–Robbins 的 $\Omega(\ln T)$ 下界相比，UCB1 的问题无关界仍差一个 $\sqrt{T}$ 因子，但问题相关界 $\sum 4\ln T/\Delta_i$ 与之只差常数与 $\Delta$ 依赖——在”臂易区分”的问题上 UCB1 已接近最优速率。

9.4 代码实现与实验分析

代码文件：cs234/code/L09_bandits.py（完整脚本，单次运行约 20–25 秒；实验 A/A2/A3/B/C/D 的真实输出另存于 cs234/code/cs234_L09_output.txt）。以下两个代码块均可独立运行（实测分别约 6 秒与 9 秒），核心实现（算法、average_curves、各 experiment_* 主体）与脚本逐字一致，仅删去少量重复的打印语句以控制篇幅；两者的输出数值完全相同。

9.4.1 十个臂上的六种算法：regret 曲线、分解与 UCB 计数界

"""10-armed Bernoulli bandit: greedy / eps-greedy / UCB1 / Thompson / LCB."""
import math
import random

import numpy as np
import matplotlib
matplotlib.use("Agg")          # 无显示环境
import matplotlib.pyplot as plt

np.random.seed(0)


class BernoulliBandit:
    """K arms; arm a pays reward 1 with probability mu[a], else 0."""

    def __init__(self, means, rng):
        self.means = list(map(float, means))
        self.K = len(self.means)
        self.mu_star = max(self.means)
        self.opt_arm = int(np.argmax(self.means))
        self.gaps = [self.mu_star - m for m in self.means]
        self.rng = rng

    def pull(self, a):
        return 1.0 if self.rng.random() < self.means[a] else 0.0


def _argmax_tie(vals, rng):
    """arg max with ties split uniformly."""
    best = max(vals)
    ties = [i for i, v in enumerate(vals) if v == best]
    return ties[0] if len(ties) == 1 else ties[rng.randrange(len(ties))]


def _argmin_tie(vals, rng):
    best = min(vals)
    ties = [i for i, v in enumerate(vals) if v == best]
    return ties[0] if len(ties) == 1 else ties[rng.randrange(len(ties))]


def run_greedy(bandit, T, rng, init_each=True):
    K, n, q = bandit.K, [0] * bandit.K, [0.0] * bandit.K
    out = []
    for t in range(T):
        if init_each and t < K:
            a = t
        else:
            a = _argmax_tie(q, rng)
        r = bandit.pull(a)
        n[a] += 1
        q[a] += (r - q[a]) / n[a]
        out.append(bandit.gaps[a])
    return out, n


def run_eps_greedy(bandit, T, rng, eps=0.1, init_each=True):
    K, n, q = bandit.K, [0] * bandit.K, [0.0] * bandit.K
    out = []
    for t in range(T):
        if init_each and t < K:
            a = t
        elif rng.random() < eps:
            a = rng.randrange(K)                    # forced exploration
        else:
            a = _argmax_tie(q, rng)
        r = bandit.pull(a)
        n[a] += 1
        q[a] += (r - q[a]) / n[a]
        out.append(bandit.gaps[a])
    return out, n


def run_ucb1(bandit, T, rng, c=2.0, init_each=True):
    """a_t = argmax_a [ Q_hat(a) + sqrt(c * log(t) / N_t(a)) ];  c = 2 -> UCB1."""
    K, n, q = bandit.K, [0] * bandit.K, [0.0] * bandit.K
    out = []
    for t in range(1, T + 1):
        if init_each and t <= K:
            a = t - 1
        else:
            lt = math.log(t)
            ucb = [q[i] + math.sqrt(c * lt / n[i]) if n[i] > 0 else float("inf")
                   for i in range(K)]
            a = _argmax_tie(ucb, rng)
        r = bandit.pull(a)
        n[a] += 1
        q[a] += (r - q[a]) / n[a]
        out.append(bandit.gaps[a])
    return out, n


def run_lcb(bandit, T, rng, c=2.0, init_each=True):
    """Pessimism control: select the arm with the *lowest* upper bound."""
    K, n, q = bandit.K, [0] * bandit.K, [0.0] * bandit.K
    out = []
    for t in range(1, T + 1):
        if init_each and t <= K:
            a = t - 1
        else:
            lt = math.log(t)
            lcb = [q[i] - math.sqrt(c * lt / n[i]) if n[i] > 0 else float("-inf")
                   for i in range(K)]
            a = _argmin_tie(lcb, rng)
        r = bandit.pull(a)
        n[a] += 1
        q[a] += (r - q[a]) / n[a]
        out.append(bandit.gaps[a])
    return out, n


def run_thompson(bandit, T, rng, init_each=True):
    """Bernoulli Thompson sampling: Beta(1,1) prior, probability matching."""
    K, alpha, beta = bandit.K, [1.0] * bandit.K, [1.0] * bandit.K
    out, n = [], [0] * bandit.K
    for t in range(T):
        theta = [rng.betavariate(alpha[i], beta[i]) for i in range(K)]
        a = _argmax_tie(theta, rng)
        r = bandit.pull(a)
        alpha[a] += r
        beta[a] += 1.0 - r
        n[a] += 1
        out.append(bandit.gaps[a])
    return out, n


def average_curves(runner, means, T, n_seeds, base_seed=12345, **kw):
    curves = np.empty((n_seeds, T))
    counts = np.zeros(len(means))
    for s in range(n_seeds):
        rng = random.Random(base_seed + s)
        bandit = BernoulliBandit(means, rng)
        path, n = runner(bandit, T, rng, **kw)
        curves[s] = np.asarray(path)
        counts += np.asarray(n, dtype=float)
    return curves.cumsum(axis=1).mean(axis=0), curves, counts / n_seeds


def experiment_A():
    print("=" * 80)
    print("EXPERIMENT A: 10-armed Bernoulli bandit, T = 10000, 15 seeds")
    print("=" * 80)
    means = [0.10, 0.25, 0.20, 0.45, 0.30, 0.55, 0.15, 0.35, 0.40, 0.50]
    T, n_seeds = 10000, 15
    print("true means mu_a :", [round(m, 2) for m in means])
    print("optimal arm     : a%d with mu* = %.2f" % (int(np.argmax(means)) + 1, max(means)))
    print("gaps Delta_a    :", [round(max(means) - m, 2) for m in means])
    specs = [
        ("greedy (eps=0)", run_greedy, {}),
        ("eps-greedy 0.01", run_eps_greedy, dict(eps=0.01)),
        ("eps-greedy 0.10", run_eps_greedy, dict(eps=0.10)),
        ("UCB1 (c=2)", run_ucb1, {}),
        ("Thompson", run_thompson, {}),
        ("LCB pessimism", run_lcb, {}),
    ]
    results, counts, raws = {}, {}, {}
    print("%-16s %10s %10s %10s %10s %10s" %
          ("algorithm", "R(500)", "R(1000)", "R(2500)", "R(5000)", "R(10000)"))
    for name, runner, kw in specs:
        curve, raw, cnt = average_curves(runner, means, T, n_seeds, **kw)
        results[name], counts[name], raws[name] = curve, cnt, raw
        print("%-16s %10.1f %10.1f %10.1f %10.1f %10.1f"
              % (name, curve[499], curve[999], curve[2499], curve[4999], curve[-1]))
    print("  decomposition check: sum_a N_T(a)*Delta_a should equal R(T)")
    print("%-16s %12s %12s %12s %14s %12s" %
          ("algorithm", "R(T)/R(T/2)", "R(T)/T", "sum N*Delta", "sub-opt frac", "N(a*)"))
    opt = int(np.argmax(means))
    gaps_arr = np.asarray([max(means) - m for m in means])
    for name, _r, _k in specs:
        decomp = float(np.dot(counts[name], gaps_arr))
        print("%-16s %12.3f %12.5f %12.1f %14.4f %12.0f"
              % (name, results[name][-1] / results[name][T // 2 - 1],
                 results[name][-1] / T, decomp,
                 float((raws[name] > 1e-12).mean()), counts[name][opt]))
    print("UCB1 regret-bound check: predicted N_T(a) <= 4 log(T)/Delta_a^2 + 1")
    for i in range(len(means)):
        d = max(means) - means[i]
        if d <= 0:
            continue
        print("  a%-3d Delta=%.2f bound=%7.0f actual=%6.0f ok=%s"
              % (i + 1, d, 4.0 * math.log(T) / d ** 2 + 1.0,
                 counts["UCB1 (c=2)"][i], counts["UCB1 (c=2)"][i] <= 4.0 * math.log(T) / d ** 2 + 1.0))
    return results, specs


if __name__ == "__main__":
    experiment_A()

代码做什么。实现一个 $A=10$ 的伯努利老虎机（均值 $0.10\sim0.55$，最优臂是 $a_6$），并实现五个策略：纯贪心、固定 $\epsilon\in\{0.01,0.10\}$ 的 $\epsilon$-greedy、UCB1（$c=2$，等价于 $\sqrt{2\ln t/N_t(a)}$ 的常见 “$2\ln t$” 版本）、Beta(1,1) 先验的 Thompson 采样，外加一个悲观对照（lower confidence bound, LCB）——它总是选”下界最高”的臂。每个策略在 15 个独立种子上跑 $T=10000$ 步，逐时刻累加实现遗憾（realised regret） $\mu^\star-\mu_{a_t}$ 后对种子求平均；同时统计每臂拉动次数 N_T(a)，用来验证 regret 分解等式与 UCB 的计数上界。

RL 机制透视。这段代码把 9.2.3 的三条公式全部变成可观测量：(i) out.append(bandit.gaps[a]) 直接产生 $l_t$，cumsum 就是 $R(t)$；(ii) np.dot(counts, gaps) 就是分解式 $\sum_a N_T(a)\Delta_a$，它应逐位等于 $R(T)$，是检验实现是否正确的内生校验；(iii) UCB 的 bonus $\sqrt{c\ln t/N_t(a)}$ 与计数 n[a] 反向耦合——这正是 9.3.4 第四步的”$N_i(n)\le 4\ln n/\Delta_i^2$”在代码里的样子。LCB 对照实验则直接回应讲义第 52 页的 Optional Check Your Understanding：“总选下界最高的臂”能否低遗憾？答案是不能——它系统性地避开好臂。

实验观察（cs234/code/cs234_L09_output.txt 真实输出，$T=10^4$，15 个种子）：

四点观察，全部可被 9.3 的理论解释：

1. 贪心的 ratio 是 1.986 ≈ 2，即严格线性。$R(10^4)/R(5000)=1.986$，斜率稳定在 $0.074$/步。原因正如 9.3.1：它的拉动次数分布是 $[1,7,668,1331,1,3326,2,11,1332,3321]$——它在 $a_4$（gap 0.10）和 $a_{10}$（gap 0.05）上各待了约 1/3 的时间，从未回到真正的 $a_6$（只有 3326 次，约 1/3）。这就是”锁死”。
2. 分解等式精确成立：六行的 sum N*Delta 与 R(T) 完全相同（738.5、355.9、266.7、508.2、142.0、3997.5）。这说明 $\sum_a\mathbb{E}[N_T(a)]\Delta_a$ 不是近似——在单条轨迹上它就是 $R(T)$ 本身。
3. UCB1 的计数上界全部满足：$a_{10}$（$\Delta=0.05$，最难的臂）的界是 $4\ln(10^4)/0.05^2+1=14738$，实际只拉了 1622 次；$a_1$（$\Delta=0.45$）界 183、实际 73。九个臂的 ok=True 全为真，这是 9.3.4 第三步断言的直接经验支持。
4. LCB（悲观）的 ratio = 2.114 > 2，比贪心更糟，$N(a^*)$ 只有 78。它回答了讲义第 52 页的问题：“总选下界最高”保证低遗憾吗？不保证——下意识里它把”不确定性大”当成”价值低”的证据，于是永久放弃没试过的臂。

一个必须诚实指出的现象：在 $T=10^4$ 时 UCB1（508.2）反而比 $\epsilon$-greedy 0.10（266.7）差。这不是理论的错误，而是渐近界的常数问题——UCB1 前期为建立置信区间付出了大量探索成本，而 $\epsilon$-greedy 一开局就在利用。实验 A2 把视界拉长到 $T=6\times10^4$ 后交叉出现了：

$T=3\times10^4$ 时两者还胶着（UCB1 的 $R/T=0.02514$ vs $\epsilon$-greedy 0.10 的 $0.02383$，UCB1 仍略差）；到 $T=6\times10^4$，UCB1 的 $R=899.6$ 已经明确低于 $\epsilon$-greedy 0.10 的 $1392.1$（$R/T$ 为 $0.01499$ vs $0.02320$）。决定性证据是 ratio：$\epsilon$-greedy 0.10 的 $R(2T)/R(T)=1.947$，仍在线性区；UCB1 是 1.193。代码同时打印了理论下界：固定 $\epsilon$ 的 $\epsilon$-greedy 有一个不可消除的线性斜率 $\epsilon\cdot\frac1A\sum_a\Delta_a$，$\epsilon=0.10$ 时为 $0.0225$/步，即 $T=3\times10^4$ 时至少 675、$T=6\times10^4$ 时至少 1350（实测 715.0 与 1392.1，均吻合）。结论：$\epsilon$-greedy 的斜率下限不随 $T$ 消失（它的 $R(T)/T$ 收敛到一个正的常数 $0.0225$），UCB1 的 $R(T)/T$ 则在持续下降。

9.4.2 单条贪心轨迹：锁死就是一条直线（实验 A3）

实验 A/9.4.1 的期望曲线是不同斜率直线的混合，容易看不清机制。实验 A3（完整脚本中的 experiment_A3()）直接打印四条种子各自的贪心轨迹：

这张表是 9.3.1 “Greedy can lock onto suboptimal action, forever” 的直接可视化：seed 32 锁死在 $a_2$（$\Delta=0.30$），$T$ 从 $10^4$ 翻倍到 $2\times10^4$，遗憾精确地从 3001.8 翻倍到 6001.8，斜率 $0.3000$ 与 $\Delta(a_2)=0.30$ 完全相等；seed 33 同理（$0.1000$ vs $0.10$）。而 seed 31/34 侥幸锁在最优臂上，$R(T)$ 冻结在 5.1 与 4.3，一个常数。$R(T)/T$ 一列最能说明问题：锁定在次优臂的运行，$R(T)/T$ 收敛到 $\Delta$ 本身（$0.30018\to0.30009$、$0.10018\to0.10009$），这正是”线性 regret ⟺ $R(T)/T\not\to0$”的确切含义。

也正因为如此，实验 A 里贪心的期望曲线 $R(10^4)=738.5$ 及其 ratio $1.986$ 并不等于 $\Delta(a_2)$ 或 $\Delta(a_4)$——它是”15 个种子里约 1/3 锁在最优臂（斜率 0）、约 2/3 锁在某个次优臂（斜率 $0.05\sim0.45$）”的加权平均。用期望曲线去反推单个算法的渐近斜率会失真；要么看 ratio 的极限，要么看单条轨迹。

9.4.3 UCB 置信半径、集中不等式验证与 broken-toe 玩具例

"""UCB radius, concentration-bound check, lecture toy example."""
import math
import random

import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

np.random.seed(0)


class BernoulliBandit:
    def __init__(self, means, rng):
        self.means = list(map(float, means))
        self.K = len(self.means)
        self.mu_star = max(self.means)
        self.gaps = [self.mu_star - m for m in self.means]
        self.rng = rng

    def pull(self, a):
        return 1.0 if self.rng.random() < self.means[a] else 0.0


def _argmax_tie(vals, rng):
    best = max(vals)
    ties = [i for i, v in enumerate(vals) if v == best]
    return ties[0] if len(ties) == 1 else ties[rng.randrange(len(ties))]


def run_greedy(bandit, T, rng, init_each=True):
    K, n, q = bandit.K, [0] * bandit.K, [0.0] * bandit.K
    out = []
    for t in range(T):
        a = t if (init_each and t < K) else _argmax_tie(q, rng)
        r = bandit.pull(a)
        n[a] += 1
        q[a] += (r - q[a]) / n[a]
        out.append(bandit.gaps[a])
    return out, n


def run_eps_greedy(bandit, T, rng, eps=0.1, init_each=True):
    K, n, q = bandit.K, [0] * bandit.K, [0.0] * bandit.K
    out = []
    for t in range(T):
        if init_each and t < K:
            a = t
        elif rng.random() < eps:
            a = rng.randrange(K)
        else:
            a = _argmax_tie(q, rng)
        r = bandit.pull(a)
        n[a] += 1
        q[a] += (r - q[a]) / n[a]
        out.append(bandit.gaps[a])
    return out, n


def experiment_B():
    print("=" * 80)
    print("EXPERIMENT B: UCB confidence radius  sqrt(2 log(1/delta) / n)")
    print("=" * 80)
    ts, ns = [100, 1000, 10000, 100000], [1, 5, 20, 100, 500]
    print("delta = 1/t^2 union-bound schedule  ->  radius sqrt(4 log t / n)")
    print("%-12s" % "t \\ n", end="")
    for n in ns:
        print("%12s" % ("n=%d" % n), end="")
    print()
    for t in ts:
        delta = 1.0 / t ** 2
        print("%-12d" % t, end="")
        for n in ns:
            print("%12.4f" % math.sqrt(2.0 * math.log(1.0 / delta) / n), end="")
        print()
    print("Radius decay in n at t = 10000 (delta = 1e-8)")
    delta = 1.0 / 10000 ** 2
    prev = None
    for n in ns:
        val = math.sqrt(2.0 * math.log(1.0 / delta) / n)
        ratio = "-" if prev is None else "%.3f" % (val / prev)
        print("   n=%5d  radius=%.4f   ratio to prev n=%-7s" % (n, val, ratio))
        prev = val
    for t, n in [(4, 1), (100, 3), (10000, 100)]:
        a = math.sqrt(2 * math.log(t ** 2) / n)
        b = math.sqrt(4 * math.log(t) / n)
        print("   t=%6d n=%4d : delta-form=%.4f  4log t-form=%.4f  match=%s"
              % (t, n, a, b, abs(a - b) < 1e-12))


def experiment_C():
    print("=" * 80)
    print("EXPERIMENT C: empirical concentration bounds, 80000 trials")
    print("=" * 80)
    rng = np.random.default_rng(2026)
    trials, chunk = 80000, 20000

    def tail_prob(mu, n, eps, one_sided):
        hits, done = 0, 0
        while done < trials:
            b = min(chunk, trials - done)
            muhat = (rng.random((b, n)) < mu).mean(axis=1)
            d = muhat - mu if one_sided else np.abs(muhat - mu)
            hits += int(np.count_nonzero(d >= eps))
            done += b
        return hits / trials

    print("%6s %6s %8s %12s %16s %16s" %
          ("mu", "n", "eps", "empirical", "2exp(-2ne^2)", "2exp(-ne^2/2)"))
    for mu, n, eps in [(0.30, 20, 0.20), (0.30, 100, 0.10), (0.50, 50, 0.15),
                       (0.80, 500, 0.05), (0.50, 1000, 0.05)]:
        emp = tail_prob(mu, n, eps, one_sided=False)
        print("%6.2f %6d %8.2f %12.5f %16.6f %16.6f"
              % (mu, n, eps, emp, 2.0 * math.exp(-2.0 * n * eps ** 2),
                 2.0 * math.exp(-n * eps ** 2 / 2.0)))


def experiment_D():
    print("=" * 80)
    print("EXPERIMENT D: broken toe toy example (.95 / .90 / .10)")
    print("=" * 80)
    means = [0.95, 0.90, 0.10]
    gaps = [max(means) - m for m in means]
    print("gaps Delta_a = (V* - Q(a)) :", [round(g, 2) for g in gaps])
    trace = [("a1", 0, 0.00), ("a2", 1, 0.05), ("a3", 0, 0.85),
             ("a2", 1, 0.05), ("a2", 0, 0.05)]
    tot = 0.0
    for a, r, reg in trace:
        tot += reg
        print("   Action=%s Reward=%d Regret=%.2f Cumulative=%.2f" % (a, r, reg, tot))
    print("cumulative regret after 5 pulls = %.2f" % tot)
    print("P(a1->0 and a2->1) = %.4f" % ((1 - means[0]) * means[1]))
    print("P(a2 becomes the unique argmax) = %.4f"
          % ((1 - means[0]) * means[1] * (1 - means[2])))
    T, n_seeds = 2000, 200
    stuck, frac_bad = 0, 0.0
    for s in range(n_seeds):
        rng = random.Random(7000 + s)
        bandit = BernoulliBandit(means, rng)
        n, q = [0, 0, 0], [0.0, 0.0, 0.0]
        for t in range(T):
            a = t if t < 3 else _argmax_tie(q, rng)
            r = bandit.pull(a)
            n[a] += 1
            q[a] += (r - q[a]) / n[a]
            if t >= 3 and a != 0:
                frac_bad += 1
        if q[0] <= q[1]:
            stuck += 1
    print("greedy %d seeds x %d steps:" % (n_seeds, T))
    print("   P(Q_hat(a1) <= Q_hat(a2) at the end)  = %.4f" % (stuck / n_seeds))
    print("   average fraction of sub-optimal pulls = %.4f"
          % (frac_bad / (n_seeds * (T - 3))))
    print("eps-greedy: slope theory vs simulated (150 seeds x 2000 steps)")
    for eps in [0.0, 0.01, 0.05, 0.10, 0.20]:
        theo = (1 - eps) * gaps[1] + eps * sum(gaps) / 3.0
        slopes, finals = [], []
        for s in range(150):
            rng = random.Random(31 + s)
            bandit = BernoulliBandit(means, rng)
            path, n = run_eps_greedy(bandit, T, rng, eps=eps)
            slopes.append(np.asarray(path).mean())
            finals.append(np.asarray(path).sum())
        print("   eps=%.2f theory=%.4f sim=%.4f R(2000)=%.1f"
              % (eps, theo, float(np.mean(slopes)), float(np.mean(finals))))
    # (5) plain greedy over the same seeds: the mean is dragged up by locked runs
    finals, counts_g = [], np.zeros(3)
    for s in range(150):
        rng = random.Random(31 + s)
        bandit = BernoulliBandit(means, rng)
        path, n = run_greedy(bandit, T, rng)
        finals.append(float(np.asarray(path).sum()))
        counts_g += np.asarray(n, dtype=float)
    print("greedy over the same 150 seeds x %d steps:" % T)
    print("   mean R(2000) = %.2f  (median %.2f, max %.2f)"
          % (float(np.mean(finals)), float(np.median(finals)), float(np.max(finals))))
    print("   mean pull counts = %s" % np.round(counts_g / 150.0, 1).tolist())


if __name__ == "__main__":
    experiment_B()
    experiment_C()
    experiment_D()

代码做什么。三件事：(B) 直接计算并打印 UCB 半径 $\sqrt{2\ln(1/\delta)/n}$ 在 $\delta=1/t^2$ 调度下随 $t,n$ 的数值表，并验证它与讲义 UCB1 形式 $\sqrt{4\ln t/N_t(a)}$ 恒等；(C) 用 8 万次蒙特卡洛估计 $P(\vert \hat\mu-\mu\vert \ge\varepsilon)$，与 Hoeffding 界 $2e^{-2n\varepsilon^2}$、sub-Gaussian 界 $2e^{-n\varepsilon^2/2}$ 并列；(D) 复现讲义第 15–16、23–24、28–29 页的 broken-toe 例子：精确遗憾表、贪心锁定概率、以及固定 $\epsilon$ 下的实际斜率。

RL 机制透视。实验 B 是 9.3.3 的”把 $\delta$ 与 $t$ 解耦”那一步的验算：讲义写的是带 $\delta$ 的 UCB，但实际算法里没有可调的 $\delta$——必须选一个随 $t$ 变的调度（$\delta=1/t^2$）才能让并集界在无穷多时刻上求和收敛。$\delta=1/t^2$ 恰好把 $\sqrt{2\ln(1/\delta)/n}$ 变成 $\sqrt{4\ln t/n}$，这就是 UCB1 里那个”$2$”的来历。实验 C 检验的是整条推导的统计地基：如果 sub-Gaussian 界不成立，9.3.4 的 good event 就无从谈起。实验 D 检验 9.3.1–9.3.2 的两个具体结论：贪心的锁定概率与 $\epsilon$-greedy 的线性斜率。

实验观察（真实输出）：

UCB 半径表（$\delta=1/t^2$，即 $\sqrt{4\ln t/n}$）：

关键读数：(i) 沿 $n$ 方向 $n\to 5n$ 时半径按 $1/\sqrt{n}$ 收缩——$t=10^4$ 时 $6.0697\to2.7145\to1.3572\to0.6070\to0.2714$，相邻比值稳定在 $0.447$，与理论 $1/\sqrt5=0.4472$ 完全一致；(ii) 沿 $t$ 方向只按 $\sqrt{\ln t}$ 缓慢增长——$t$ 扩大 1000 倍（$10^2\to10^5$），半径从 4.2919 才涨到 6.7861，只涨了 1.58 倍。这正是次线性遗憾的来源：分母的 $\sqrt{n}$ 增长快于分子的 $\sqrt{\ln t}$；(iii) 恒等式验证：$t=100,n=3$ 时两式都得 2.4779，match=True。

集中不等式（两万次分块、共 8 万次蒙特卡洛）：

两条界都成立但松紧差别巨大：Hoeffding 界在中小区间上至少比经验值大一个数量级（如 $n=20$ 时 0.4038 vs 0.0555），sub-Gaussian 界在参数小时甚至超过 1（作为概率上界无信息）。这解释了 9.4.1 观察到的现象：UCB1 前期”过度悲观地乐观”正是因为这些界本身很松——理论保证的是 $O(\sqrt{AT\ln T})$ 的形状，不是小的常数。同时注意经验值随 $n$ 的衰减：$(n,\varepsilon)=(500,0.05)$ 时 0.00486，$(1000,0.05)$ 时 0.00186，比值约 2.6，接近指数衰减而非多项式——界抓住了正确的定性形状。

Broken-toe 玩具例：

与讲义第 24 页的表格逐格一致：5 步累计遗憾恰为 1.00，其中 $a_3$ 那一步独自贡献 0.85。锁定概率：$P(a_1\to0\wedge a_2\to1)=0.0450$，$P(a_2\text{ 成为唯一最大})=0.0405$。200 个种子 × 2000 步的模拟给出 $P(\hat Q(a_1)\le\hat Q(a_2))=0.2300$（远高于 0.0405，因为锁定也可能在后续几轮以别的路径发生）、贪心在 $t\ge3$ 的次优拉动比例 0.2355。$\epsilon$-greedy 的斜率对照：$\epsilon=0.01$ 时理论 $0.0525$ vs 模拟 $0.0174$（模拟更低，因为 150 个种子里有一部分真的找到了 $a_1$，而理论式条件在”已锁死在 $a_2$”上）；$\epsilon=0.10$ 时 $0.0750$ vs $0.0345$；$\epsilon=0.20$ 时 $0.1000$ vs $0.0633$。$\epsilon=0$ 那一行（纯贪心）150 个种子的 $R(2000)$ 均值 31.22，但中位数只有 1.70、最大值 100.75——均值被少数锁死的轨迹拖高，这是”期望遗憾”与”典型轨迹”分离的经典例子，也是为什么必须用 regret 而不仅看中位数经验回报。

9.5 评估指标与理论保证

指标汇总（与 9.2.2 的表对应，这里给出本讲算法的具体形式，并附 9.4 的实测斜率）：

收敛速度对比。次线性中的两个速率等级要分清：

而 $\epsilon$-greedy 的 $R(T)/T$ 收敛到正的常数 $\epsilon\cdot\frac1A\sum_a\Delta_a$（$A=10$、$\epsilon=0.1$ 时为 $0.0225$），贪心收敛到 $\mathbb{E}[\Delta_{\hat a}]>0$——“趋于 0”与”趋于正常数”就是次线性与线性的分水岭。

条件依赖分析（谁在什么条件下成立）：

经验性能作为兜底指标。讲义第 19 页把”computational complexity, convergence, convergence to a fixed point, & empirical performance”列为此前已用的标准——本讲不是替换它们，而是补充。9.4 的实践恰好说明原因：UCB1 在 $T=10^4$ 时经验性能不如 $\epsilon$-greedy（508.2 vs 266.7），只有把 $T$ 拉长到 $6\times10^4$、并看 $R(T)/T$ 的趋势（0.01499 且仍在下降，对比 $\epsilon$-greedy 的 0.02320 已钉住）而非单点值，理论的优势才会显现。只看单点经验性能会得出错误的算法排序。

9.6 与其他讲次的关联

前向关联（本讲依赖谁）：

• L1：四大要素（优化/延迟后果/探索/泛化）在 L1 被提出，本讲第一次单独研究探索这一个要素，并把其余三个暂时关闭。L1 提到的”RL 与监督学习的差别”在本讲具化为”regret vs 泛化误差”两套度量。
• L3/L4：TD 与 Q-learning 的收敛条件 $\sum_t\alpha_t=\infty,\sum_t\alpha_t^2<\infty$ 就是 9.2.2 表中”渐近收敛”标准的原型；本讲指出这类标准的局限（不告诉你多少样本），从而引出 regret 与样本复杂度。
• L8：讲义第 2–3 页的 Refresh Your Understanding 回顾 RLHF/DPO（答案：三条全真——RLHF 与 DPO 都从偏好数据学到奖励模型的显式表示；两者都受限于偏好数据中最优样本；DPO 不使用参考策略的说法是错的，DPO 通过 $\log\frac{\pi_\theta}{\pi_{\text{ref}}}$ 隐式使用参考策略）。这说明 L8 的偏好学习可以看成离线 bandit：只有被记录的动作有反馈，与 MAB 的”反事实不可得”同源。

后向关联（谁依赖本讲）：

• L10：同一批 slide 的续篇，负责 (i) UCB 证明的技术细节（讲义第 51 页说明修正版证明在 Lecture 10 给出，遵循 Bandit Algorithms Theorem 7.1）；(ii) 贝叶斯 regret 框架；(iii) Thompson 采样 / 概率匹配（probability matching）——本讲第 45 页已预告；(iv) PAC bandit；(v) 上下文老虎机在实际问题中的应用（Bastani et al., Nature 2021 的 Covid 检测分配：非平稳、上下文、批量、延迟反馈、带约束）。本讲的 UCB 骨架与 L10 的完整证明构成一对。
• L11–L12：把 bandit 的结论搬回 MDP——PAC-MDP、RMax、乐观初始化（optimistic initialization）、PSRL、Bayesian MDP。MDP 版的 regret 界会带上 $\vert \mathcal{S}\vert ,\vert \mathcal{A}\vert $（如 $O(\sqrt{\vert \mathcal{S}\vert \vert \mathcal{A}\vert T})$），其推导骨架与本讲 9.3.4 完全平行：good event → 计数界 → 求和。
• L13–L14：MCTS 的 UCT 选择规则 $a=\arg\max_a\big(Q(s,a)+c\sqrt{\ln N(s)/N(s,a)}\big)$ 就是本讲 UCB1 公式在树搜索中的直接移植——把”臂”换成”动作”、把”$t$”换成”父节点访问数 $N(s)$”。

9.7 关键要点

1. 评估 RL 算法有八个不可互相推导的标准：经验性能、渐近收敛、regret、次线性 regret、样本复杂度、计算复杂度、PAC、一致性。没有一个算法能同时最优；报告结果时必须说明用的是哪一个。
2. Regret 是 data efficient RL 的中心度量，$R(T)=\sum_a \mathbb{E}[N_T(a)]\Delta_a$ 是本讲的”万能公式”：遗憾 = 逐臂拉动次数 × 缺口。它的困难在于缺口 $\Delta_a$ 未知，所以真实问题里只能证明上界（讲义第 25 页）。
3. 探索太少与太多都是线性遗憾：贪心（$\epsilon=0$）会锁死，固定 $\epsilon$ 的 $\epsilon$-greedy 永远有 $\epsilon/A$ 的次优比例。要次线性，探索必须随 $t$ 衰减。
4. 乐观原则的两个保险：拉”可能高”的臂，若真高则拿奖励，若其实低则压低其均值并缩小其不确定性——无论哪种结果都不亏，这是 UCB 的直觉内核。
5. UCB1 的半径 $\sqrt{2\ln(1/\delta)/N_t(a)}$ 里的 $\delta$ 必须随 $t$ 调度（$\delta=1/t^2$），否则对无穷多时刻做并集界不收敛；这一调度把它等价地变成 $\sqrt{4\ln t/N_t(a)}$。
6. UCB 的证明三步走：regret 分解 → good event（真实均值不超上界）+ 并集界 → 好事件下非最优臂至多 $2\ln(1/\delta)/\Delta_i^2$ 次（反证：否则它的 UCB 会掉到 $\mu^\star$ 以下）。最终 $R(T)=O(\sqrt{AT\ln T})$，平均遗憾 $\to0$。
7. Lai–Robbins 下界说明对数遗憾是问题相关意义下的极限，且硬问题 = “看起来像但均值不同”的臂（$D_{\mathrm{KL}}$ 小）。

9.8 常见误区与注意事项

误区 1：认为”regret 小”就等于”经验回报高”，可以用一个指标替代另一个。 改正后的正确认识：二者数学上等价（讲义第 21 页：”Maximize cumulative reward $\iff$ minimize total regret”，因为 $R(T)=T\mu^-$\ 实际累积奖励，$\mu^$ 是常数），但在评估实践中不等价。累积奖励的绝对数值依赖环境的奖励尺度（换个环境就不可比），而 regret 是相对最优的归一化损失，跨环境可比。9.4 还给出了更尖锐的例子：UCB1 在 $T=10^4$ 时累积奖励低于 $\epsilon$-greedy，因为探索前期必然少拿奖励——只看短视界的回报会误杀正确算法。

误区 2：认为 $\epsilon$-greedy 加了探索就一定比贪心好，所以”$\epsilon$-greedy 解决了探索问题”。 改正后的正确认识：讲义第 31–32 页的 Check Your Understanding 答案是“① 和 ② 都对”——$\epsilon=0.1$ 会有线性 regret，而 $\epsilon=0$（即纯贪心）同样会有线性 regret。$\epsilon$-greedy 只是把”可能锁死”换成”一定持续犯错”，两者都是 $\Theta(T)$。真正解决探索的是让探索量随信息积累而衰减的机制（UCB 的 $1/\sqrt{N_t(a)}$、Thompson 的贝叶斯后验收缩）。判据是 $R(T)/T\to0$，而非”有没有随机性”。

误区 3：认为把 $\epsilon$ 调小（甚至取 $\epsilon=0$）就能减少 regret。 改正后的正确认识：这里有个硬币的两面。固定 $\epsilon$ 的不可消除斜率是 $\epsilon\cdot\frac1A\sum_a\Delta_a$，表面上看 $\epsilon\to0$ 就趋向 0——但 $\epsilon\to0$ 会拖慢”识别最优臂”的速度，在有限 $T$ 内可能根本还没找对臂（$\epsilon=0.01$ 在 9.4.1 的 $T=10^4$ 时 $N(a^*)=5252$，仍有约一半时间在次优臂上）。更极端地取 $\epsilon=0$ 就退化成贪心，讲义已证明它会锁死。正确做法不是调小常数，而是让 $\epsilon_t\to0$ 但仍满足 $\sum_t\epsilon_t=\infty$（与 Robbins–Monro 条件同构），或者直接用 UCB/Thompson。9.4.3 的 $\epsilon=0$ 一行给出了代价：150 个种子里 $R(2000)$ 均值 31.22，但中位数仅 1.70、最大 100.75——期望被少数锁死轨迹支配。

误区 4：认为 UCB 总是比 $\epsilon$-greedy 好，因此实践中应该无脑用它。 改正后的正确认识：$O(\sqrt{AT\ln T})$ 是渐近、问题无关的界，它没有承诺常数。9.4.1 的实测：$T=10^4$ 时 UCB1 的 $R=508.2$ 劣于 $\epsilon$-greedy 0.10 的 $266.7$；$T=3\times10^4$ 时两者胶着（$754.3$ vs $715.0$，$R/T$ 为 $0.02514$ vs $0.02383$，UCB1 仍略差），但 UCB1 的 ratio 1.193 远小于 $\epsilon$-greedy 的 1.947；到 $T=6\times10^4$ 才明确反转：$899.6$ vs $1392.1$，且 $\epsilon$-greedy 的 $R/T$ 钉在 $0.0225$ 附近不再下降。结论：短视界/小规模问题用 $\epsilon$-greedy 完全合理；UCB 的价值在长视界与需要理论保证的场合。（9.4.1 中 Thompson 采样在两个视界上都最好——这是因为伯努利共轭先验恰好很强，属于”先验匹配问题”的幸运，不是普遍结论。）

误区 5：认为”总选下界最高的臂”（悲观）也是安全的保守策略。 改正后的正确认识：讲义第 52 页的 Optional Check Your Understanding 专门问这个问题，答案是不保证低遗憾。9.4.1 的 LCB 对照实测 $R(10^4)=3997.5$，$R(T)/R(T/2)=2.114>2$（比贪心还糟），$N(a^*)=78$——它把”不确定性大”误读为”价值低”，于是系统性放弃没试过的臂，等价于反向的探索。乐观与悲观在这里不对称：未知既可能是好也可能是坏，乐观者至少会去查，悲观者永远不会。

误区 6：在真实问题里计算 regret 来评估算法。 改正后的正确认识：讲义第 25 页明确警告：”in real settings we cannot evaluate the regret because it requires knowledge of the expected reward of the true best action.” 真实部署中 $\mu^*$ 未知，所以 regret 的用法是双向的：(i) 在已知最优的合成环境上测量，用来比较算法（这正是 9.4 做的事）；(ii) 在真实问题上证明上界，作为一种事前保证。真实问题里能直接测的代理指标是累积奖励（可测但跨环境不可比）或离线评估（off-policy evaluation）。

误区 7：把 UCB 的 $\delta$ 当成可以随手取的超参数。 改正后的正确认识：$\delta$ 是置信水平的失败概率，而算法运行在无穷多时刻上，因此必须对所有 $(\text{臂},t)$ 对做并集界（讲义第 50 页：”Subtle, Union bound: $P(\cup E_i)\le\sum_i P(E_i)$”）。固定 $\delta$ 会让 $\sum_{t=1}^{\infty}A\delta$ 发散，理论保证失效；只有 $\delta_t=1/t^2$（使 $An\delta\to A/n$ 可求和）才给出 9.3.4 的界。这解释了为什么工程实现里写的是 $\sqrt{2\ln t/N_t(a)}$ 而不是带 $\delta$ 的形式。

9.9 思考题（带答案）

思考题 1（手算 regret 分解与 $\epsilon$-greedy 的线性）

考虑讲义第 22 页的三臂 broken-toe bandit，$\mu=(0.95,0.90,0.10)$，故 $V^*=0.95$，$\Delta=(0,0.05,0.85)$。某算法在前 1000 步中的拉动次数为 $N(a_1)=400,\ N(a_2)=500,\ N(a_3)=100$（这是期望拉动次数）。

1. 用 regret 分解计算 $L_{1000}$。
2. 若改用 $\epsilon=0.2$ 的 $\epsilon$-greedy，并设它始终把 $a_2$ 当作贪心臂（即 $1-\epsilon$ 的时间选 $a_2$，其余均匀随机），求每步期望遗憾的解析式与 $L_{1000}$ 的期望值。

答案。

(1) 直接代入恒等式 $L_t=\sum_a \mathbb{E}[N_t(a)]\Delta_a$：

注意 $a_1$ 虽然被拉了 400 次，贡献恰好为 0——最优臂上的任何拉动都不产生遗憾，这是分解式最重要的结构。

(2) 以概率 $1-\epsilon$ 选 $a_2$（遗憾 0.05，但注意当 $\hat a=a_2$ 时这一步本来就是次优），以概率 $\epsilon$ 从三臂均匀选（每臂 $1/3$）：

于是 $L_{1000}=0.10\times1000=\mathbf{100}$，且斜率恒为 $0.10$/步——与 $t$ 无关，即 $\Theta(T)$ 线性。若要 $L_{1000}\le110$ 却保持次线性，必须让这个斜率随 $t$ 衰减：UCB 的机制是当 $N_t(a_3)$ 增大、其上界低于 $a_1$ 后就不再拉 $a_3$，于是 $\Delta$ 的加权和收敛。

思考题 2（UCB 的 last-iterate 判断、置信半径与并集界）

某 3 臂伯努利 bandit，$t=10000$ 时某臂 $a$ 被拉了 $N_t(a)=100$ 次，经验均值 $\hat Q(a)=0.52$；最优臂 $a^\star$ 的真实均值已知为 $\mu^\star=0.60$（用于分析，算法并不知道）。取 UCB1 形式 $\hat Q(a)+\sqrt{4\ln t/N_t(a)}$。

1. 计算 $a$ 的 UCB 值。
2. 若 $a^\star$ 的经验均值恰好等于真值（$\hat Q(a^\star)=0.60$），且 $N_t(a^\star)=4000$，判断 $a^\star$ 的 UCB 是否大于 $a$ 的 UCB；由此说明 $a$ 此时是否还可能被选中。
3. 现在换一种 $\delta$：若错误地取固定 $\delta=0.05$（即半径 $\sqrt{2\ln(1/0.05)/N_t(a)}=\sqrt{5.9915/N_t(a)}$），对该臂 $a$ 半径是多少？并与 1 中半径比较，说明为什么固定 $\delta$ 破坏理论保证。

答案。

(1) $\ln(10000)=9.2103$，故 $\sqrt{4\times9.2103/100}=0.6070$，$\mathrm{UCB}(a)=0.52+0.6070=\mathbf{1.1270}$。

(2) $\sqrt{4\times9.2103/4000}=0.0960$，$\mathrm{UCB}(a^\star)=0.60+0.0960=0.6960$。因为 $0.6960<1.1270$，$a$ 的 UCB 仍然更大，$a$ 依然可能被选中。这不是矛盾——注意 $a$ 的 UCB 是 $1.1270>1$，早已超出伯努利奖励的上界 1，说明当 $N_t(a)$ 很小时置信界本身很松（9.4.3 实测 $n=1,t=10^4$ 时半径达 6.0697）。UCB 允许”尚未充分探索的臂”暂时压过最优臂，这正是它把 $a$ 的拉动次数限制在 $4\ln t/\Delta_a^2$ 以内而非立即归零的原因：当 $N_t(a)$ 涨到 $\ge 4\ln t/\Delta_a^2$ 时，由 9.3.4 第三步的反证，$\mathrm{UCB}(a)\le\mu_a+\Delta_a=\mu^\star<\mathrm{UCB}(a^\star)$ 必然成立，$a$ 从此出局。

(3) 固定 $\delta=0.05$：半径 $=\sqrt{5.9915/100}=\mathbf{0.2448}$，远小于 1 中的 $0.6070$。这看起来”界更紧、算法更好”，但在理论上是灾难：good event 要求”对所有臂、所有时刻”成立，其失败概率是 $\sum_{t=1}^{\infty}A\delta=\infty$。换句话说，跑得足够久，某个时刻某个臂的真实均值一定会冲出它的名义 UCB，那时 9.3.4 第三步的反证前提 $\mathcal{G}$ 失效，$N_t(a)\le U_i$ 不再成立，$R(T)=O(\ln T)$ 的结论整条垮掉。取 $\delta=1/t^2$ 使 $\sum_t A/t^2=A\pi^2/6<\infty$，是让”永远正确”这件事付得起代价的最小牺牲；其代价就是半径里多出一个 $\sqrt{4\ln t}$ 而非 $\sqrt{2\ln(1/\delta)}$ 的缓慢增长项。

思考题 3（推导：从问题相关界到 $O(\sqrt{AT\ln T})$，以及为什么不能直接比较两个界）

1. 由 9.3.4 的问题相关界 $R_T\lesssim\sum_{i:\Delta_i>0}\frac{4\ln T}{\Delta_i}+\sum_i\Delta_i$，解释为什么这个界在 $\Delta_i\to0$ 时会发散，并说明这是否意味着 UCB 真的会有无穷遗憾。
2. 设 $A=10$，只有一个次优臂且 $\Delta=0.05$，$T=10^6$。用问题相关界估计该臂的拉动次数上界与它对 $R_T$ 的贡献；再用 9.4.1 的实测数据说明界有多松。
3. 给出把问题相关界转成问题无关界的分组思路（阈值分组 + 截断计数），并说明问题无关界在什么问题上是紧的、为什么”化到 $\sqrt{AT\ln T}$”需要比一次分组更细的处理。

答案。

(1) $U_i=4\ln T/\Delta_i^2$ 是拉动次数的界，贡献是 $U_i\Delta_i=4\ln T/\Delta_i$，当两个臂的分布几乎相同（$\Delta_i\to0$）时这一项无界。但这不代表 UCB 真的有无限遗憾：$\Delta_i\to0$ 意味着”这对臂本来就无法区分”，Lai–Robbins 下界 $\frac{\Delta_a}{D_{\mathrm{KL}}(R_a\vert R_{a^*})}$ 此时同样发散——任何算法在这个问题上都必须付无穷的（问题相关的）代价，因为”最优臂”这个概念本身在这个极限下没有意义。两边同时发散，说明问题相关界在这个角落里是紧的、不可改进的，而不是算法缺陷。这也解释了为什么需要第二种（问题无关的）界来提供统一的比较基准。

(2) 拉动次数上界 $U_i=4\ln(10^6)/0.05^2=4\times13.8155/0.0025=\mathbf{22105}$，对遗憾的贡献上界是 $22105\times0.05=\mathbf{1105}$。而 9.4.1 在 $T=10^4$ 时实测（$\Delta=0.05$ 的 $a_{10}$，$T=10^4$）：界为 $4\ln(10^4)/0.05^2+1=14738$、实际只拉了 1622 次。也就是说，界比现实松了将近一个数量级——因为 $\Delta_i$ 出现在分母的平方上，而界是通过”最坏情况的反证”得到的，没有利用”臂一旦被排除就再也不会回来”这一实际的快速收敛。理论界的作用是保证增长率，不是预测常数。

(3) 分组思路：把上一步的计数界写成截断形式 $R_T\le\sum_{i:\Delta_i>0}\Delta_i\min(T,\ 4\ln T/\Delta_i^2)$，取阈值 $\delta=2\sqrt{\ln T/T}$ 分两组。”大缺口组” $\Delta_i>\delta$ 用第二项：$\sum_i 4\ln T/\Delta_i\le A\cdot 4\ln T/\delta=2A\sqrt{T\ln T}$；”小缺口组” $\Delta_i\le\delta$ 用第一项：$\sum_i\Delta_i T\le A\delta T=2A\sqrt{T\ln T}$。两组相加得 $O(A\sqrt{T\ln T})$。要把 $A$ 收进根号变成 $O(\sqrt{AT\ln T})$，需要更细致的逐臂组织（例如按 $\Delta_i$ 分层求和、利用 $\sum_i\Delta_i$ 常数项），这一步不是一行代数，完整推导见 L10。问题无关界在”所有臂几乎一样、缺口都约为 $\sqrt{A\ln T/T}$”这一最坏配置下是紧的——这正是 Lai–Robbins 所说的”hard problems have similar looking arms with different means”（讲义第 35 页）。反之，如果某个臂的缺口很大（$\Delta=O(1)$），问题相关界 $\sum 4\ln T/\Delta_i=O(\ln T)$ 远小于 $\sqrt{AT\ln T}$，此时用问题无关界会严重高估。

衔接说明：本讲给出的是 UCB regret 界的结论与证明骨架——regret 分解、good event 与并集界、反证得到的计数上界 $N_t(i)\le 2\ln(1/\delta)/\Delta_i^2+O(1)$ 三块拼图，以及 $\delta=1/t^2$ 调度下 $R(T)=O(\sqrt{AT\ln T})$ 的结论（如 9.3.4 所述，从问题相关界到这一形式的最后一步分组需要比一次阈值切分更细的处理）。完整的技术细节（good event 的完整展开、$n_t(a)$ 界的逐步推导与求和计算）见第 10 讲；讲义第 51 页也明确说明修正后的完整证明在 Lecture 10 给出，并遵循 Lattimore & Szepesvári Bandit Algorithms Theorem 7.1。第 10 讲还将从贝叶斯 regret 的角度重做同一问题，并给出 Thompson 采样 / 概率匹配 这一本讲第 45 页已预告的、实践中常常比 UCB 更好的方法。