Lecture 10: 数据高效强化学习（续）—— UCB 的遗憾界与从老虎机到 MDP（Data Efficient RL: UCB Regret Bounds and From Bandits to MDPs）

目录 · ← l9 · l11 →

Lecture 10: 数据高效强化学习（续）—— UCB 的遗憾界与从老虎机到 MDP（Data Efficient RL: UCB Regret Bounds and From Bandits to MDPs）

对应材料：官方 lecture10post.pdf 第 1–16 页（共 41 页，第 17 页起为第 16 讲的 Value Alignment 客座，本讲不涉及）；前置衔接见 lecture9post.pdf 第 33–44、51 页｜Week 6 周三（Feb 11, 2026）｜参考阅读 SB Chp 2；Lattimore & Szepesvári Bandit Algorithms §7.1（Theorem 7.1） 一句话定位：上一讲（L9）给出了 UCB 算法与「乐观面对不确定性」的物理直觉，本讲把直觉升级为可证明的遗憾界——完整走一遍 UCB 的 sublinear regret 证明 sketch，并用 Lai–Robbins 下界说明这个量级已经最优；最后指出为什么这套框架不能原样搬到 MDP，为 L11–L12 的 Fast RL 铺路。

10.1 概述

本讲要回答的核心问题是：UCB 到底有多好，这个「好」能好到什么程度，以及这个「好」为什么不能直接推广到 MDP？ 上一讲我们看到 UCB 在实践中表现优异，也看到 $\epsilon$-greedy 和 greedy 会因为「永远探索」或「永不探索」而陷入线性遗憾（linear regret）。本讲把这一观察变成定理：对奖励有界的随机 $K$ 臂老虎机，UCB 的遗憾是 $O(\log n)$ 量级（problem-dependent），并且可以进一步压成 $O(\sqrt{KT\log T})$（problem-independent），而 Lai–Robbins 下界告诉我们任何算法都不可能做得比 $\Theta(\log t)$ 更好——所以 UCB 在量级上已经最优。

本讲在课程知识链中的位置很特殊：它是唯一一讲以「证明」为主体的 Fast RL 课。L9 建立了评估框架（regret）与算法（greedy、$\epsilon$-greedy、UCB），本讲把 UCB 的证明补完（官方讲义在 L9 第 51 页明确说明「我在课堂上尝试了一个更短的证明，但发现其中有错误；Lecture 10 给出了修正后的证明」），然后用一条从 bandit 到 MDP 的桥梁收尾，指向 L11–L12 的贝叶斯 bandit、PSRL 与 PAC-MDP。因此本讲的主线是：记号复习 → 遗憾界定理的完整证明 sketch → 下界与最优性 → 桥接 MDP。

需要提前澄清一处易混点：L11 会讲贝叶斯老虎机与 Thompson 采样（Thompson Sampling, TS），那是本讲之后的独立内容。本讲全程停留在频率派（frequentist）视角——即存在一组真实但未知的参数 $\theta$，我们在固定实例上评估算法。L9 第 36 页的 “Today” 大纲里列出的 “Bayesian bandits / Probability matching” 属于后续讲次，本讲不展开。

10.2 核心概念的数学形式化

10.2.1 多臂老虎机（Multi-armed Bandit, MAB）记号复习

严格定义. 一个 $K$ 臂老虎机是一个二元组 $(\mathcal{A}, \mathcal{R})$：

其中 $R_a(r) = P[r \mid a]$ 是未知的奖励分布。

• $\vert \mathcal{A}\vert = m = K$：臂的数量；课程讲义用 $m$ 与 $K$ 混用，本笔记统一记为 $K$。
• 动作值（action-value）是期望奖励：$Q(a) = \mathbb{E}[r \mid a]$。
• 最优值：$V^* = Q(a^) = \max_{a \in \mathcal{A}} Q(a)$，其中 $a^ = \arg\max_a Q(a)$。
• 第 $t$ 步智能体选择 $a_t \in \mathcal{A}$，环境生成奖励 $r_t \sim R_{a_t}$。
• 目标：最大化累计奖励 $\sum_{\tau=1}^{t} r_\tau$。

单步遗憾（regret / opportunity loss） 与累计遗憾（total regret）：

期望取自选择 $a_t$ 的决策策略。由于 $\sum_\tau r_\tau = t\,V^* - \sum_\tau (V^* - Q(a_\tau)) + \text{噪声}$，所以

Gap 分解. 记 gap 为 $\Delta_a = V^* - Q(a)$，$N_t(a)$ 为到时刻 $t$ 为止臂 $a$ 被拉动的次数。则遗憾可以写成「gap $\times$ 计数」的和：

直观解释. 遗憾不是「我拿到的奖励少」，而是「与事后诸葛亮相比我损失了多少」。这是个反事实（counterfactual）量：每一时刻只能拉一个臂，但我们要为「没拉的臂本来能拿多少」付账。$L_t = \sum_a \mathbb{E}[N_t(a)]\Delta_a$ 说明遗憾完全由两件事决定：拉错臂的次数，以及拉错时错得有多离谱。好的算法让「gap 大的臂」被拉动次数少；但麻烦在于 gap 是未知的——这正是探索问题的全部难度所在。

具体示例（讲义第 10 页的「断脚趾」玩具例子，含数字）. 三种治疗方案，奖励是 6 周后 X 光显示愈合（$+1$）与否（$0$），建模为 3 臂 Bernoulli 老虎机：

（讲义原文特别注明：这是编造的例子，并非真实疗效。）若某算法每次都拉 $a_3$，则 $L_t = 0.85t$，线性遗憾——每多走一步就多亏 0.85。若每步均匀随机拉，则 $L_t = \frac{1}{3}(0+0.05+0.85)t \approx 0.30t$，同样是线性的。线性遗憾的定义（讲义第 31 页）：某算法若以常数比例的时间取到非最优动作，则它有线性遗憾。

与监督学习的对比. 监督学习假设数据分布固定且与我的预测无关，我只要拟合即可；老虎机里数据分布由我的决策决定——我拉哪个臂，就只观测到哪个臂的反馈。这个「数据是决策的函数」的耦合，加上「只看得到被选动作的反馈」这种反事实缺失，是 RL 区别于监督学习的第一道坎。

10.2.2 遗憾界的两种类型

讲义第 34 页明确区分了两类界，这是本讲全部技术内容的地图：

严格定义.

• Problem-independent（问题无关）界：把遗憾表示为时间步总数 $T$ 的函数，形式如 $R(T) \le C\sqrt{KT\log T}$，常数 $C$ 与具体 gap 无关。
• Problem-dependent（问题相关）界：把遗憾表示为每个臂的拉动次数 $\mathbb{E}[N_T(a)]$ 与 gap $\Delta_a$ 的函数，形式如 $R(T) \le 3\sum_i \Delta_i + \sum_{i:\Delta_i>0} \frac{16\log T}{\Delta_i}$。

直观解释. Problem-independent 界像「体检报告上的参考范围」：不管你的问题是什么形状，都能给你一个保证，但可能很松。Problem-dependent 界像「针对你这个病例的预测」：它抓住了问题的真实难度——gap 越小的臂越难分辨，就必然被拉动越多次。两者不可互相替代：problem-dependent 界里出现的 $1/\Delta_i$ 在 $\Delta_i \to 0$ 时发散，所以它不能对「所有实例」一致成立；而 problem-independent 界虽然一致，却丢掉了实例结构。

具体示例. 在 10.4 节的 10 臂实验中，gap 从 0.45 一路降到 0.05，$16\log T/\Delta_i^2$ 这一项从 $727.7$ 暴涨到 $58946.2$——几乎是平局的臂 $a_9$（gap 只有 0.05）单独贡献了问题相关界的主体。这就是 problem-dependent 界的软肋，也解释了为什么实际中它给出的数字（$8344.6$）会远大于经验遗憾（$726.8$），而 $\sqrt{KT\log T}$ 这类问题无关包络反而更贴近现实（$959.7$）。

10.2.3 置信界（confidence bound）与次高斯（sub-Gaussian）尾部

严格定义（Lattimore & Szepesvári Corollary 5.5）. 设 $X_i - \mu$ 是独立的、$\sigma$-次高斯随机变量，$\hat\mu = \frac{1}{n}\sum_{t=1}^n X_t$。则对任意 $\varepsilon \ge 0$：

因此对任意 $\delta \in (0,1]$，以至少 $1-\delta$ 的概率

这是整个证明的唯一引擎：它把一个未知的、不可观测的 $\mu$ 与可观测的 $\hat\mu$ 之间的差距，用 $n$ 和 $\delta$ 控制住。

直观解释. 数据越多（$n$ 大），置信半径越小；要求越可信（$\delta$ 小，即 $1-\delta$ 越接近 1），半径越大。半径按 $1/\sqrt{n}$ 收缩——这就是「不确定性收缩（uncertainty shrinkage）」的定量版本。

讲义第 43 页的课后补充还给出双边版本：用联合界（union bound）取 $\delta^{\prime} = \delta/2$，可以做到以 $1-\delta$ 的概率 $\vert \mu - \hat\mu\vert \le \sqrt{2\sigma^2\log(2/\delta)/n}$。为什么要双边？ 因为证明里既要「$\hat\mu_i$ 不会高估 $\mu_i$」（控制次优臂的乐观）又要「$\hat\mu_1$ 不会低估 $\mu_1$」（控制最优臂的悲观），而 UCB 算法本身只需要单边（上界）。

具体示例. 奖励有界于 $[0,1]$ 意味着 $\sigma^2 \le 1/4 \le 1$，所以讲义直接「假定奖励是 1-次高斯（$\sigma^2 = 1$）」来简化常数，这也正是 UCB1 里那个 $\sqrt{2\log(1/\delta)/N_t(a)}$ 的来历。

与监督学习的对比. 监督学习通常只关心期望风险，大数定律给的是 $n\to\infty$ 的渐近保证；这里需要的是有限样本、显式常数的高概率界，因为遗憾是逐步骤累积的，渐近保证对遗憾一事无补。

10.2.4 从 bandit 到 MDP：为什么不能直接搬

严格定义. 一个 MDP 是 $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$，策略在状态上取值 $\pi(a\mid s)$。MDP 的遗憾必须在 $(s,a)$ 对上分解：

直观解释. 老虎机是「单状态 MDP」（讲义第 2 页快速检查题第 5 条即考此点，答案为真）。一旦引入状态，(1) 「臂」的含义随状态变化——同一个动作在不同状态下价值天差地别；(2) 奖励是延迟的，当前动作改变的是未来状态的分布，所以「错」的后果会传播；(3) 计数不再是 $N_T(a)$ 而是 $N_T(s,a)$，需要的是状态相关的乐观。

具体示例（4×4 滑坡 GridWorld，含数字）. 状态 0–15 按行排列，目标为右下角状态 15，动作 4 个（0=上,1=右,2=下,3=左），每步以 $\mathrm{slip}=0.10$ 的概率滑向垂直方向，撞墙则原地不动，每步奖励 $-1$，目标态奖励 $0$，$\gamma = 0.95$。值迭代得到：

关键数字：同一个动作 $a_1$（向上）在起始状态 $s_0$ 的 gap 是 $0.68$，而在紧邻目标的状态 $s_{14}$ 的 gap 是 $1.83$。也就是说，一个「状态无关」的全局 gap 根本无法表达这个 MDP 的难度结构——这正是 10.4 实验 C 会验证的论点。

与老虎机的对比. 老虎机的遗憾分解 $\sum_a \Delta_a \mathbb{E}[N_T(a)]$ 建立在「动作价值不随历史状态变化」之上；MDP 中这个前提彻底失效，需要把 $\Delta_a$ 换成 $\Delta_{s,a}$，把计数换成 $N_T(s,a)$，并且还要额外处理转移概率的估计误差（这将是 L12 中 Simulation Lemma 的用途）。

10.3 算法伪代码与完整推导

10.3.1 UCB1 算法（衔接 L9）

Algorithm: UCB1 (Auer, Cesa-Bianchi, Fischer 2002)
输入: 臂数 K, 时域 n, 置信参数 delta_t
输出: 动作序列 a_1, a_2, ..., a_n
初始化: N(a) = 0, Q_hat(a) = 0  for all a in A
for t = 1, 2, ..., n do
    if t <= K then
        a_t = a_t                  # 每个臂先各拉一次, 保证 N(a) > 0
    else
        a_t = argmax_{a in A} [ Q_hat(a) + sqrt( 2 * log(1/delta_t) / N(a) ) ]
    end if
    r_t = pull(a_t)                # r_t ~ R_{a_t}
    N(a_t) = N(a_t) + 1
    Q_hat(a_t) = Q_hat(a_t) + (r_t - Q_hat(a_t)) / N(a_t)
end for
终止: t = n

算法逻辑解说. 两项的博弈：$Q_{\hat t}$ 是「利用（exploitation）」项，奖励项衡量臂当前看起来多好；$\sqrt{2\log(1/\delta_t)/N_t(a)}$ 是「探索（exploration）」项，奖励不确定但可能很好的臂。取 $\delta_t = 1/t^2$ 时

即教科书里的经典形式——这就是讲义第 9 页 UCB1 与第 44 页的形式所对应的调度。

与理论的对应. $N_t(a)$ 出现在分母是关键：一个臂被拉得越多，它的置信半径越小、它的「bonus」越弱，最终必然被淘汰。证明的核心正是把一个算法行为事实（「$a_i$ 只在它的 UCB 还能超过 $a_1$ 时被拉」）转成 $N_t(a_i)$ 的上界。

10.3.2 遗憾界定理的完整证明 sketch（讲义第 11–16 页，逐步骤转录）

定理 7.1（Lattimore & Szepesvári）. 考虑有界于 $[0,1]$ 的随机 $K$ 臂老虎机上的 UCB。对任意时域 $n$，若 $\delta = 1/n^2$，则

不失一般性设 $a^* = a_1$。回顾 $\Delta_i = Q(a^*) - Q(a_i)$，$\hat Q$ 为经验估计（无 hat 者为真值），且

第 1 步：定义「好事件（good event）」。 对每个次优臂 $i$，定义

其中 $u_i$ 是「稍后才会指定的、臂 $i$ 的某个拉动次数」。(注：讲义原文此处有一处笔误，$i \to 1$，即应为 $\mathrm{UCB}_1(t,\cdot)$。)

直观看两件事. $(*)$ 说「最优臂 $a_1$ 的真实值 $Q(a_1)$ 从未被它的置信上界低估过」（UCB 对最优臂是有效的乐观上界）；$()$ 说「次优臂 $i$ 拉了 $u_i$ 次之后，它的置信上界已经掉到 $Q(a_1)$ 以下」。这两件事同时成立时，臂 $i$ **不可能再被拉动。

第 2 步：把 $\mathbb{E}[N_t(a_i)]$ 拆成「好事件 / 坏事件」。

第二项用 $N_t(a_i) \le n$ 放缩。于是任务化为两部分：证明 $(***)$，再控制 $P(G_i^c)$。

第 3 步：反证法证明 $(*)$：$\mathbb{E}[\mathbb{1}(G_i=\top)N_t(a_i)] \le u_i$。** 假设不成立，则存在某个时刻 $t$，在臂 $a_i$ 被拉动时恰有 $N_{t-1}(a_i) = u_i$。那么

第一步是定义，第二步代入 $N_{t-1}(a_i) = u_i$，第三个不等号由好事件 $()$，第四个由好事件 $()$。但 $\mathrm{UCB}_i(t-1,\delta) < \mathrm{UCB}_1(t-1,\delta)$ 意味着**此时应该选 $a_1$ 而不是 $a_i$**，与「$a_i$ 被选中」矛盾。故 $()$ 成立。$\blacksquare$

这是全证明最漂亮的一步：它把「算法为什么好」翻译成「在好事件下，次优臂的拉动次数被一个纯代数式 $u_i$ 封顶」——不需要任何概率论。

第 4 步：控制 $P(G_i^c)$ 的第一项 $P\big(Q(a_1) \ge \min_t \mathrm{UCB}_1(t,\delta)\big)$。 先把「最小值 $\ge$」展开成并集：

再用联合界（union bound）与次高斯尾界：

第二行用联合界，第三行因为每一项都不超过 $\delta$（即每个 UCB 以 $1-\delta$ 成立）。

第 5 步：控制第二项。 先选定 $u_i$ 足够大，使得对某个 $c \in (0,1)$（稍后指定）

则

第一个等号用 $\mu_1 = \mu_i + \Delta_i$；第一个不等号用 (8)；最后一个不等号用上一讲的集中不等式。

第 6 步：合并。 由 (7) 与 (9)，

注意此式仅在 (8) 成立时有效，所以接下来选 $u_i$ 以满足 (8)：

第 7 步：回代并平衡两项。 把 (11) 代回 (10)：

我们要平衡这两项（指数项与多项式项）。取 $c = 0.5$，则 $(1-c)^2 = 0.25$，于是 $u_i = \frac{2\log(1/\delta)}{0.25\,\Delta_i^2} = \frac{8\log(1/\delta)}{\Delta_i^2}$；再代入 $\delta = 1/n^2$（即 $\log(1/\delta) = 2\log n$），得 $u_i = \frac{16\log n}{\Delta_i^2}$，同时 $\frac{2c^2}{(1-c)^2} = 2$，所以 $n^{\,1-2} = n^{-1}$ 与 $n\delta = 1/n$ 都是低阶。于是

第 8 步：代入遗憾分解。 把 (13) 代入 (2)：

即定理 7.1 的 (1) 式。$\blacksquare$

指数别记错（本讲最易错的细节）：计数层的界 (13) 分母是 $\Delta_i^{\mathbf{2}}$，遗憾层的界 (14)/(1) 分母是 $\Delta_i^{\mathbf{1}}$——因为从计数到遗憾要再乘一个 $\Delta_i$。两者相差一个 $\Delta_i$ 因子，考试里非常常见。

10.3.3 从 problem-dependent 到 problem-independent

推导. 定理 7.1 的界对「所有实例」不一致成立，因为 $\Delta_i \to 0$ 时 $1/\Delta_i$ 发散。用按 gap 大小分桶的标准技巧可以换成问题无关形式。取阈值 $\Delta_0 = \sqrt{K\log T / T}$，把次优臂分两类：

• 大 gap 臂（$\Delta_i > \Delta_0$）：个数不超过 $K$，每个贡献 $\frac{16\log T}{\Delta_i} < \frac{16\log T}{\Delta_0} = 16\sqrt{\frac{T\log T}{K}}$，合计 $\le 16\sqrt{KT\log T}$。
• 小 gap 臂（$\Delta_i \le \Delta_0$）：每个的遗憾贡献不超过 $\Delta_i T \le \Delta_0 T = \sqrt{KT\log T}$，合计 $\le K\sqrt{KT\log T}$。

两桶相加得到问题无关包络：

直观解释. 大 gap 的臂很快被识别出来（$1/\Delta$ 型代价，随 $\log T$ 增长）；小 gap 的臂虽然认不出来，但它们错得也不多（每步只亏 $\Delta_0$），所以可以容忍被反复拉动。分桶正是「把无法分辨的臂的代价用一个可接受的常数盖住」这一思想的定量版本。

实验对照. 10.4 节实验 A 给出：$K=10, T=10000$ 时 $\sqrt{KT\log T} = 959.7$，而实测 UCB1 遗憾为 $726.8$——比值仅 $1.3\times$；相比之下问题相关界 $8344.6$ 是实测的 $11.5\times$。问题无关包络在这个实例上反而更紧，原因是它不像定理 7.1 那样被几乎平局的臂 $a_9$（$\Delta=0.05$）拖垮。

10.3.4 Sublinear regret 的含义与下界

Sublinear 的含义（讲义第 33 页）. 「好」的算法应有 sublinear 或更低的遗憾：

• 永远探索（explore forever）：线性遗憾。例：固定 $\epsilon$ 的 $\epsilon$-greedy 以 $\epsilon > 0$ 的恒定概率拉错臂，$L_t$ 随时间线性增长。
• 从不探索（explore never）：线性遗憾。例：greedy 一旦锁定次优动作就永不回头，讲义第 17 页原文为 “Greedy can lock onto suboptimal action, forever”。
• Sublinear 的推论：$\dfrac{L_T}{T} \to 0$。这就是「平均遗憾趋于零」——算法在长期几乎不再犯错。

Lai–Robbins 下界（讲义第 35 页）.

直观解释. 下界回答「这个老虎机问题本身有多难」。难度由两件事决定：gap $\Delta_a$ 与分布相似度 $\mathrm{KL}(R_a \vert R_{a^*})$。「难问题」= 最优臂与其他臂看起来很像但均值不同——分布几乎重叠，你必须拉很多次才能分辨。这个下界是渐近的（$t\to\infty$）且是对任意算法成立的，所以它告诉你 UCB 已经达到了最优量级 $\Theta(\log t)$，无法再改进到常数。另外它承诺下界本身是 sublinear 的——问题并非 hopeless。

具体示例（10.4 实验 B3，含数字）. 在 10 臂实例上计算 $C = \sum_a \Delta_a/\mathrm{KL}(R_a\vert R_{a^*}) = 26.78$；实测 UCB1 的 $L_t$ 分别为 $153.4\ (t{=}1000)$、$260.6\ (2000)$、$497.0\ (5000)$、$726.8\ (10000)$，而对应的 $\log t \cdot C$ 为 $184.96,\,203.52,\,228.05,\,246.61$。注意 $L_t/\log t$ 从 $22.21$ 上升到 $78.91$，说明 UCB 在 $T=10^4$ 时尚未进入渐近区；定理的断言是「极限至少是 $C$」，而不是「UCB 会达到 $C$」。两者都以 $\log t$ 速度增长，这才是「量级最优」的确切含义。

「难问题」的定量感受：取两臂实例 $0.60$ vs $\mu_2$，把 gap 从 $0.40$ 缩到 $0.05$（缩小 8 倍），下界常数 $\Delta/\mathrm{KL}$ 从 $1.19$ 涨到 $9.72$，放大约 8.1 倍。难度住在问题里，不在算法里。

10.3.5 从老虎机到 MDP：桥梁

为什么 bandit 框架不够. 老虎机是单状态 MDP，其遗憾分解 $\sum_a \Delta_a \mathbb{E}[N_T(a)]$ 隐含假设「动作价值与状态无关」。在 MDP 里这个假设崩塌，导致三重困难：

1. 状态相关的价值：同一动作在不同状态下价值相反（10.2.4 的 GridWorld 中动作 $a_1$ 的 gap 从 $0.68$ 变到 $1.83$）。
2. 延迟后果：奖励不即时，当前动作改变未来状态分布，误差会沿轨迹传播。
3. 计数爆炸：需要 $N_T(s,a)$ 而非 $N_T(a)$，乐观必须逐 $(s,a)$ 构造。

MDP 中的评估框架（预告）.

• Regret：与 bandit 同形，但按 $(s,a)$ 求和（见 10.2.4 公式）。
• PAC（Probably Approximately Correct，可能近似正确）：L12 的形式化定义为——对给定 $\epsilon, \delta$，若算法在除 $N$ 步之外的所有时间步上选择的动作满足 $Q(a) \ge Q(a^*) - \epsilon$ 的概率至少为 $1-\delta$，其中 $N$ 是 $\big(\vert \mathcal{S}\vert , \vert \mathcal{A}\vert , \frac{1}{1-\gamma}, \frac{1}{\epsilon}, \frac{1}{\delta}\big)$ 的多项式，则称该算法是 PAC 的。与 regret 的区别：regret 关心累计损失，PAC 关心大错的次数——「可以犯很多小错，但不能老犯大错」。
• Approaches：乐观（optimism）与概率匹配 / Thompson 采样（probability matching / Thompson sampling）。讲义第 47 页 “What You Should Understand” 要求学生「理解 MDP 与 multi-armed bandit 的关系」、「能实现 UCB」、「能证明 UCB 为何 sublinear」。

向 L11 的过渡. 本讲全程假设「存在固定的真实参数」。L11 会把未知参数本身视为随机变量、维护其后验分布，从而用一个先验（prior）换取更少的探索——即贝叶斯老虎机与 Thompson 采样；L12 再把同样的思想推到 MDP（Bayesian MDP、PSRL）并给出 PAC-MDP 界。本讲建立的「gap × 计数」分解与乐观原则，是这两讲的共同地基。

10.4 代码实现与实验分析

完整实验脚本：cs234/code/L10_ucb.py（输出 cs234/code/L10_output.txt，图 cs234/code/L10_ucb.png），运行时间约 31–37 秒，仅用 numpy / matplotlib / 标准库。

实验 A：UCB1 的实测遗憾曲线 vs 理论界

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

K, T, SEEDS = 10, 5000, 10
MEANS = np.round(np.arange(0.20, 0.70, 0.05), 2)   # 10 臂, 最优 = 0.65
STAR, GAPS = MEANS.max(), MEANS.max() - MEANS
SUB = GAPS > 0                                      # 只对次优臂求和


def run_ucb1(means, T, rng):
    """UCB1, delta_t = 1/t^2, 即 bonus = sqrt(4 log t / N_t(a))。"""
    K = len(means)
    n, q, out = np.zeros(K), np.zeros(K), np.empty(T)
    for t in range(T):
        if t < K:
            a = t                                   # 每个臂先各拉一次
        else:
            bonus = np.sqrt(2.0 * np.log((t + 1.0) ** 2) / n)
            a = int(np.argmax(q + bonus))
        r = 1.0 if rng.random() < means[a] else 0.0
        n[a] += 1
        q[a] += (r - q[a]) / n[a]                   # 增量式经验均值
        out[t] = means.max() - means[a]             # 该步遗憾 = Delta_{a_t}
    return out, n


def run_eps_greedy(means, T, rng, eps=0.1):
    K = len(means)
    n, q, out = np.zeros(K), np.zeros(K), np.empty(T)
    for t in range(T):
        if t < K:
            a = t
        elif rng.random() < eps:
            a = int(rng.integers(K))
        else:
            a = int(np.argmax(q))
        r = 1.0 if rng.random() < means[a] else 0.0
        n[a] += 1
        q[a] += (r - q[a]) / n[a]
        out[t] = means.max() - means[a]
    return out, n


# --- 多次重复, 记录累积遗憾曲线与各臂拉动计数 ---
curves, counts = {}, {}
for name, fn in [("UCB1", run_ucb1), ("eps-greedy(0.1)", run_eps_greedy)]:
    L, C = [], []
    for s in range(SEEDS):
        reg, n = fn(MEANS, T, np.random.default_rng(100 + s))
        L.append(np.cumsum(reg))
        C.append(n)
    curves[name], counts[name] = np.array(L), np.array(C)

print("Delta =", list(np.round(GAPS, 2)), "  sum Delta = %.2f" % GAPS.sum())
print("%-16s %14s %14s %10s" % ("algorithm", "L(1000)", "L(5000)", "L(5000)/L(1000)"))
for k, L in curves.items():
    print("%-16s %14.1f %14.1f %10.3f"
          % (k, L[:, 999].mean(), L[:, 4999].mean(), L[:, 4999].mean() / L[:, 999].mean()))

# --- 理论界: 注意计数层是 Delta^2、遗憾层是 Delta ---
logn = np.log(T)
thm71 = 3.0 * GAPS.sum() + np.sum(16.0 * logn / GAPS[SUB])          # 定理 7.1
indep = np.sqrt(K * T * logn)                                       # 问题无关包络
emp = curves["UCB1"][:, -1].mean()
print("\nThm 7.1  bound  3 sum D + sum 16 log T / D = %9.1f" % thm71)
print("sqrt(K T log T)                            = %9.1f" % indep)
print("empirical UCB1 L(T)                        = %9.1f" % emp)
print("count-level  sum 16 log T / D^2            = %9.1f" % np.sum(16.0 * logn / GAPS[SUB] ** 2))

# --- 验证计数界 E[N_T(a_i)] <= u_i + 3 ---
print("\ncount bound E[N_T(a_i)] <= u_i + 3 with u_i = 16 log T / Delta_i^2:")
print("%6s %8s %12s %14s %12s" % ("arm", "Delta", "u_i", "E[N_T]", "max excess"))
for i in np.where(SUB)[0]:
    ui = 16.0 * logn / GAPS[i] ** 2
    print("%6s %8.2f %12.1f %14.1f %12.0f"
          % ("a%d" % (i + 1), GAPS[i], ui, counts["UCB1"][:, i].mean(),
             max(np.max(counts["UCB1"][:, i] - ui), 0.0)))
recon = float(np.sum(counts["UCB1"].mean(axis=0)[SUB] * GAPS[SUB]))
print("regret rebuilt as sum_a Delta_a E[N_T(a)] = %.1f" % recon)

# --- 画图: 对数纵轴上对比经验遗憾与两条理论包络 ---
plt.figure(figsize=(5, 3.5))
tt = np.arange(1, T + 1)
for k, L in curves.items():
    plt.plot(L.mean(axis=0), label=k)
plt.plot(tt, 3.0 * GAPS.sum() + np.sum(16.0 * np.log(tt) / GAPS[SUB][:, None], axis=0),
         'k--', lw=1, label="Thm 7.1")
plt.plot(tt, np.sqrt(K * tt * np.log(tt)), 'k:', lw=1, label="sqrt(K T log T)")
plt.yscale("log")
plt.xlabel("t"); plt.ylabel("cumulative regret")
plt.legend(fontsize=7); plt.grid(alpha=0.3); plt.tight_layout()
plt.savefig("L10_block1.png", dpi=100)
print("\nfigure -> L10_block1.png")

代码做什么. 构造一个 10 臂 Bernoulli 老虎机，臂均值等差排在 $0.20$ 到 $0.65$（gap 从 $0.45$ 递减到 $0.05$，只有 $a_9$ 是几乎平局的难臂）。对 UCB1 与 $\epsilon$-greedy($\epsilon{=}0.1$) 各跑 10 个随机种子，记录逐步遗憾 $V^* - Q(a_t)$ 的累积曲线；然后把三条理论量画在同一张对数纵轴图上：定理 7.1 的问题相关界、$\sqrt{KT\log T}$ 问题无关包络、以及经验曲线。最后按 (13) 逐臂核对计数界 $u_i + 3$，并用 $\sum_a \Delta_a \mathbb{E}[N_T(a)]$ 反算遗憾，检验它与直接测量的 $L_T$ 是否一致。

RL 机制透视. 这段代码是「用实验给理论称重」的范例。三个层次值得注意：

1. 增量均值 $\hat Q \mathrel{+}= (r-\hat Q)/n$ 与 UCB 的 bonus $\propto 1/\sqrt{n}$ 是同一个 $N_t(a)$ 的两个用途——前者决定「利用」，后者决定「该探索多少」。$N_t(a)$ 是算法唯一的记忆装置。
2. 置信调度 $\delta_t = 1/t^2$ 不是装饰。它把 $\log(1/\delta_t)$ 变成 $2\log t$，使 bonus 缓慢增大——这正是证明第 7 步里 $n\delta = 1/n$ 那一项的来源。若换成固定 $\delta$，证明里 $n\delta$ 就会变成 $n\delta \to \infty$ 的线性项，界就崩了。「$\delta_t$ 必须随时间收紧」是 sublinear 的必要条件。
3. $\sum_a \Delta_a \mathbb{E}[N_T(a)]$ 的反算是本讲最重要的 sanity check：它把「遗憾」这个抽象指标翻译成「拉错次数的加权和」，只有当反算值与实测值吻合，才说明我们对遗憾分解的理解正确。

实验观察. 真实运行输出（python3 L10_ucb.py，块 1 为 T=5000、10 种子版本）：

• 臂均值 $\mu = [0.20, 0.25, \dots, 0.65]$，$\mu^* = 0.65$，gap $= [0.45, 0.40, 0.35, 0.30, 0.25, 0.20, 0.15, 0.10, 0.05, 0.00]$，$\sum \Delta_a = 2.25$。
• 累积遗憾：UCB1 $L(1000) = 154.0$、$L(5000) = 487.1$，$L(5000)/L(1000) = 3.164$；$\epsilon$-greedy(0.1) $L(1000) = 56.1$、$L(5000) = 184.9$，比值 $3.294$。注意这里 $\epsilon$-greedy 的绝对遗憾更低——因为固定 $\epsilon$ 在小 $T$ 上探索得很均匀，而这个实例的 gap 都不大；但它没有 sublinear 保证，$L_T/T$ 会稳定在约 $0.028$ 而不趋于 0（主脚本 T=10000、20 种子：$L(10000)=279.6$，$L(T)/T = 0.028$），而 UCB1 的 $L(T)/T = 0.073$ 且仍在下降（其 $L(2000)/L(1000) = 1.699$）。
• 理论界对比：定理 7.1 的问题相关界 $= 7717.1$，问题无关包络 $\sqrt{KT\log T} = 652.6$，经验 $L(5000) = 487.1$。计数层求和 $\sum 16\log T/\Delta_i^2 = 83932.8$（比遗憾层大一个 $\Delta$ 因子的量级）。
• 计数界逐臂验证：$a_1$：$u_1 = 673.0$，实测 $\mathbb{E}[N_T] = 100.0$，超出量 0；$a_9$（gap 0.05）：$u_9 = 54510.0$，实测 $\mathbb{E}[N_T] = 1006.8$，超出量 0。全部 9 个次优臂的超出量都是 0——正好对应证明第 3 步的 $(*)$ 反证结论：在好事件下 $N_T(a_i)$ 被 $u_i$ 硬性封顶。注意 $a_8, a_9$ 的 $u_i$ 已经大于 $T$，界在那里是空洞的（vacuous）**，这也解释了问题相关界为何如此松。
• 反算一致性：$\sum_a \Delta_a \mathbb{E}[N_T(a)] = 487.1$，与直接测得的 $L(5000) = 487.1$ 完全吻合——验证了遗憾分解 $L_T = \sum_a \Delta_a \mathbb{E}[N_T(a)]$ 的正确性。

实验 B：验证证明的两个零件

主脚本 L10_ucb.py 的 B1/B2/B3 三块分别检验证明中的三个关键事实。B1 检验次高斯尾界：

（Bernoulli($\mu{=}0.5$)，40000 次重复。经验尾部恒不超过界，界合法但相当松——因为 $\sigma^2 = 1$ 是把 $[0,1]$ 奖励统一当作 1-次高斯使用的保守取值，真实方差只有 $0.25$。）

B2 检验计数界（主脚本，$T=5000$，30 种子，仅列代表性的几行）：$a_1$（$\Delta=0.45$）$u_1 = 673.0$ vs 实测 $\mathbb{E}[N_T] = 99.2$；$a_5$（$\Delta=0.25$）$u_5 = 2180.4$ vs 实测 $227.9$；$a_9$（$\Delta=0.05$）$u_9 = 54510.0$ vs 实测 $1012.2$。所有次优臂的最大超出拉动次数均为 0，且反算遗憾 $493.5$ 与实测 $L(5000) = 497.0$ 吻合到 0.7%。

B3 检验 Lai–Robbins 下界：$C = \sum_a \Delta_a/\mathrm{KL}(R_a\vert R_{a^*}) = 26.78$。

$L_t/\log t$ 单调上升，说明 $T = 10^4$ 时 UCB 尚在渐近区之前；两者都是 $\Theta(\log t)$。

代码做什么（B 部分）. B1 直接蒙特卡洛估计 $\hat\mu_n$ 的尾部概率并与 Hoeffding 型界对比；B2 在 30 个种子上跑 UCB1 并记录每个臂的最终拉动次数，逐一核对 $u_i + 3$；B3 用二分法安全地实现 Bernoulli KL 散度（处理 $p \in \{0,1\}$ 的边界），计算 Lai–Robbins 常数并与实测 $L_t$ 对比。

RL 机制透视. B1 是整条证明链的源头：没有它就得不到 (7) 式的 $n\delta$。B2 检验的是证明中最巧妙的 $(*)$ 一步——它是纯组合/代数结论，所以经验验证必然严格成立（超出量精确为 0，而非「大约为 0」），这一点与 B1 的「界成立但松」形成鲜明对比。B3 则提醒我们：下界与上界是两种完全不同的陈述**，实测曲线高于下界是正常的（下界只保证「不可能更快」），把「实测 > 下界」误读成「界被违反」是初学者常见错误。

实验观察. B2 的另一个值得注意的现象是界的空洞性：$a_8$（$\Delta=0.10$）的 $u_8 = 13627.5$、$a_9$ 的 $u_9 = 54510.0$ 都远超 $T=5000$，此时 (13) 的界虽然为真但无信息（上限大于总步数）。这解释了定理 7.1 的界（$8344.6$）为何比实测（$726.8$）大一个数量级：界被最难分辨的那一个臂主导了。

实验 C：从老虎机到 MDP——bandit 方法为什么不能直接迁移

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

N, GAMMA, SLIP, LIVING = 4, 0.95, 0.10, -1.0
NS, GOAL, MV = N * N, N * N - 1, [(-1, 0), (0, 1), (1, 0), (0, -1)]

# --- 自写 4x4 滑坡 GridWorld: P[s,a,s'], R(s,a) ---
P = np.zeros((NS, 4, NS))
R = np.full((NS, 4), LIVING)
for r in range(N):
    for c in range(N):
        s = r * N + c
        if s == GOAL:
            P[s, :, s], R[s, :] = 1.0, 0.0            # 目标态吸收, 奖励 0
            continue
        for a in range(4):
            for aa, pr in [(a, 1 - SLIP)] + [((a - 1) % 4, SLIP / 2),
                                             ((a + 1) % 4, SLIP / 2)]:
                dr, dc = MV[aa]
                nr, nc = r + dr, c + dc
                sp = nr * N + nc if (0 <= nr < N and 0 <= nc < N) else s  # 撞墙原地
                P[s, a, sp] += pr


def value_iteration(P, R, gamma=GAMMA, tol=1e-12):
    V = np.zeros(NS)
    while True:
        Vn = (R + gamma * P @ V).max(axis=1)
        if np.max(np.abs(Vn - V)) < tol:
            return Vn
        V = Vn


V = value_iteration(P, R)           # 真实最优值函数
Q = R + GAMMA * P @ V               # 真实最优动作值
print("V* (start=%.2f), goal state %d has V*=%.2f" % (V[0], GOAL, V[GOAL]))
print(np.round(V.reshape(N, N), 2))


def regret(s, a):
    return V[s] - Q[s, a]           # MDP 单步遗憾 = V*(s) - Q*(s,a)


def bandit_ucb_on_mdp(T, rng):
    """朴素迁移: 一个全局 bandit 覆盖 4 个动作, 完全看不见状态。"""
    n, q, s, out = np.zeros(4), np.zeros(4), N - 1, np.empty(T)
    for t in range(T):
        a = t if t < 4 else int(np.argmax(q + np.sqrt(2.0 * np.log((t + 1.0) ** 2) / n)))
        out[t] = regret(s, a)
        r = R[s, a]
        n[a] += 1
        q[a] += (r - q[a]) / n[a]   # 用跨状态的混合奖励当"臂价值"
        s = int(rng.choice(NS, p=P[s, a]))
        if s == GOAL:
            s = N - 1               # 到目标后重启
    return out


def optimistic_mdp(T, rng, replan=25):
    """逐 (s,a) 乐观: 未访问的 (s,a) 给最大 bonus + 乐观自环转移。"""
    n_sa = np.zeros((NS, 4))
    n_sas = np.zeros((NS, 4, NS))
    r_sum = np.zeros((NS, 4))
    s, out, Q_opt = N - 1, np.empty(T), np.zeros((NS, 4))
    for t in range(T):
        if t % replan == 0:                       # 周期性重解 MDP
            R_hat = np.where(n_sa > 0, r_sum / np.maximum(n_sa, 1), 0.0)
            P_hat = np.zeros((NS, 4, NS))
            for a in range(4):
                vis = n_sa[:, a] > 0
                if vis.any():
                    P_hat[vis, a, :] = n_sas[vis, a, :] / n_sa[vis, a][:, None]
                unv = ~vis
                if unv.any():                     # 未访问 = 乐观自环
                    P_hat[unv, a, :] = 0.0
                    P_hat[unv, a, unv] = 1.0
            bonus = np.where(n_sa > 0,
                             np.sqrt(2.0 * np.log((t + 1.0) ** 2) / np.maximum(n_sa, 1)),
                             -LIVING)             # 未访问 bonus = Rmax - Rmin
            R_opt = R_hat + bonus
            Vv = np.zeros(NS)
            for _ in range(200):                  # 在乐观模型上值迭代
                Vn = (R_opt + GAMMA * P_hat @ Vv).max(axis=1)
                if np.max(np.abs(Vn - Vv)) < 1e-9:
                    Vv = Vn
                    break
                Vv = Vn
            Q_opt = R_opt + GAMMA * P_hat @ Vv
        a = int(np.argmax(Q_opt[s]))
        out[t] = regret(s, a)
        r = R[s, a]
        sp = int(rng.choice(NS, p=P[s, a]))
        n_sa[s, a] += 1
        n_sas[s, a, sp] += 1
        r_sum[s, a] += r
        s = sp if sp != GOAL else N - 1
    return out


def uniform_random_on_mdp(T, rng):
    """基线: 均匀随机动作, 天然状态盲。"""
    s, out = N - 1, np.empty(T)
    for t in range(T):
        a = int(rng.integers(4))
        out[t] = regret(s, a)
        s = int(rng.choice(NS, p=P[s, a]))
        if s == GOAL:
            s = N - 1
    return out


T, SEEDS = 3000, 10
res = {}
for name, fn in [("bandit-UCB (state-blind)", bandit_ucb_on_mdp),
                 ("uniform random", uniform_random_on_mdp),
                 ("optimistic model-based", optimistic_mdp)]:
    res[name] = np.array([np.cumsum(fn(T, np.random.default_rng(500 + s)))
                          for s in range(SEEDS)])

print("\nT=%d, seeds=%d, MDP regret = sum_t [V*(s_t) - Q*(s_t,a_t)]" % (T, SEEDS))
print("%-26s %12s %12s %10s" % ("controller", "R(1500)", "R(3000)", "R(3000)/R(1500)"))
for k, C in res.items():
    print("%-26s %12.2f %12.2f %10.3f" % (k, C[:, 1499].mean(), C[:, 2999].mean(),
                                          C[:, 2999].mean() / C[:, 1499].mean()))
gaps_sa = V[:, None] - Q
print("\nper-(s,a) gaps V*(s)-Q*(s,a): max = %.2f, mean over suboptimal = %.2f"
      % (gaps_sa.max(), gaps_sa[gaps_sa > 1e-9].mean()))
print("a *single global* gap per action cannot represent this: the same action")
print("has gap %.2f at the start state and %.2f at the goal-adjacent state."
      % (gaps_sa[0, 0], gaps_sa[14, 0]))

plt.figure(figsize=(5, 3.5))
for k, C in res.items():
    plt.plot(C.mean(axis=0), label=k)
plt.xlabel("t (steps)"); plt.ylabel("MDP regret R(t)")
plt.legend(fontsize=7); plt.grid(alpha=0.3); plt.tight_layout()
plt.savefig("L10_block2.png", dpi=100)
print("figure -> L10_block2.png")

代码做什么. 先用值迭代解出 4×4 滑坡 GridWorld 的 $V^$ 与 $Q^$，作为计算遗憾的真值基准。然后对比两种控制器：(1) 朴素迁移的 bandit-UCB——把 4 个动作当成 4 个臂，用跨状态混合的奖励维护一个全局 $\hat Q(a)$，完全忽略 $s_t$；(2) 逐 $(s,a)$ 乐观的 model-based——维护 $\hat R(s,a)$ 与 $\hat P(s^{\prime}\vert s,a)$ 的计数，未访问的 $(s,a)$ 给最大 bonus（$R_{\max} - R_{\min}$）与乐观自环转移，周期性在「乐观模型」上重跑值迭代，再用得到的 $\tilde Q$ 选动作。遗憾统一测为 $V^(s_t) - Q^(s_t, a_t)$。

RL 机制透视. 这段代码演示了 bandit → MDP 的三个断裂点：

1. 状态盲（state-blindness）。bandit-UCB 的 $\hat Q(a)$ 是「臂 $a$ 在所有状态下的平均奖励」，这是个语义错误的估计量：同一个动作在起始格是好的、在目标附近是坏的，平均之后两个信息都被抹平。它仍然在做「乐观探索」，但乐观看错了对象。
2. 乐观必须逐 $(s,a)$。model-based 版本把未访问的 $(s,a)$ 的奖励设为 $R_{\max}$、转移设为自环（假装「待在这里能拿最高奖励」），于是在规划阶段这些 $(s,a)$ 显得极端有吸引力，智能体主动去覆盖它们。注意这里乐观不是加在 $\hat Q$ 上的 bonus 那么简单，而是同时注入到 $\hat R$ 和 $\hat P$ 中——这是 MDP 与 bandit 的本质差别（bandit 没有 $\hat P$ 需要乐观）。
3. 规划（planning）成为新成本。bandit 每步只需 $O(K)$ 的比较，MDP 每个决策周期要做一次值迭代 $O(\vert \mathcal{S}\vert ^2\vert \mathcal{A}\vert )$。这是「用计算换样本」的典型权衡，也是 L13 MCTS 的伏笔。

实验观察. 真实运行输出（T=3000，10 种子）：

• $V^*$（起始格 $s_0 = -5.73$）：$\begin{pmatrix}-5.73 & -4.94 & -4.11 & -3.27\\ -4.94 & -4.11 & -3.18 & -2.25\\ -4.11 & -3.18 & -2.20 & -1.16\\ -3.27 & -2.25 & -1.16 & 0.00\end{pmatrix}$，$\gamma = 0.95$ 下每远离目标一格约衰减 $0.82$ 倍。
• MDP 遗憾对比：

• bandit-UCB 迁移后的遗憾比值 $1.994 \approx 2$，与均匀随机（$2.001$）几乎相同——即它沦落为线性遗憾，和「什么都不学」没有区别。这正是「永远探索 / 从不探索」之外第三种线性遗憾的来源：探索对了，但学错了对象。（主脚本 L10_ucb.py 用 15 个种子得到同样的结论：$1.994$ vs 随机 $1.997$。）
• 逐 $(s,a)$ 乐观的版本比值仅 $1.029$，遗憾在 $R(1500)$ 之后基本停止增长（$794.74 \to 817.96$，增量仅 $23.22$）——这是 sublinear 的清晰信号。
• 结构原因：per-$(s,a)$ gap 的 max 为 $1.92$、次优平均为 $1.14$，而同一个动作 $a_1$（向上）在 $s_0$ 的 gap 是 $0.68$、在 $s_{14}$ 的 gap 是 $1.83$，相差 $2.7$ 倍。用单一全局 gap 描述这个动作必然失真。

10.5 评估指标与理论保证

评估指标.

理论保证（全部写出具体形式）.

1. 定理 7.1（problem-dependent 上界）：$\delta = 1/n^2$ 时 $\text{Regret}n \le 3\sum_i \Delta_i + \sum{i:\Delta_i>0}\frac{16\log n}{\Delta_i}$。
2. 计数界（证明中介）：$\mathbb{E}[N_n(a_i)] \le 3 + \frac{16\log n}{\Delta_i^2}$（注意 $\Delta^2$）。
3. Problem-independent 推论：$\text{Regret}_T = O(\sqrt{KT\log T})$（由按 $\Delta_0 = \sqrt{K\log T/T}$ 分桶得到）。
4. Lai–Robbins 下界：$\lim_{t\to\infty}L_t \ge \log t\sum_{a:\Delta_a>0}\frac{\Delta_a}{\mathrm{KL}(R_a\vert R_{a^*})}$，对任意算法成立。
5. 最优性：上界与下界都是 $\Theta(\log T)$，故 UCB 在量级上最优（渐近最优，up to constant）。
6. 置信保证：以 $\ge 1-\delta$ 概率 $\mu \le \hat\mu + \sqrt{2\sigma^2\log(1/\delta)/n}$；双边版本用 $\delta/2$ 得 $\vert \mu - \hat\mu\vert \le \sqrt{2\sigma^2\log(2/\delta)/n}$。
7. MDP 侧（预告，L12）：PAC-MDP 的样本复杂度为 $\big(\vert \mathcal{S}\vert ,\vert \mathcal{A}\vert ,\frac{1}{1-\gamma},\frac{1}{\epsilon},\frac{1}{\delta}\big)$ 的多项式；model-based 乐观算法的间隔项 $\beta = \frac{1}{1-\gamma}\sqrt{\frac{1}{2}\ln\frac{2\vert \mathcal{S}\vert \vert \mathcal{A}\vert m}{\delta}}$。

条件依赖分析.

• 依赖 $\delta$ 的调度：$\delta$ 必须随 $t$ 收紧（$\delta_t = 1/t^2$）。固定 $\delta$ 会让 (7) 式的 $n\delta$ 成为线性项，界失效。
• 依赖奖励有界 / 次高斯：整个证明只用到「$X_i - \mu$ 独立且 $\sigma$-次高斯」这一条集中不等式。一旦奖励重尾或非平稳（如讲义第 5–6 页的 Covid 检测问题：非平稳、上下文相关、批量、反馈延迟且带约束），这套分析框架需要重做。
• 依赖「gap 固定」：定理 7.1 假设 gap 是常量。$\Delta_i \to 0$ 时界发散，必须切换到 problem-independent 形式。
• 依赖「单状态」：MDP 中 $N_T(a) \to N_T(s,a)$，且还需控制转移模型误差（Simulation Lemma：$\Delta \le \frac{\alpha + \gamma V_{\max}\beta}{1-\gamma}$，其中 $\alpha$ 是奖励模型误差、$\beta$ 是转移的 $L_1$ 误差）。
• 在线 vs 离线：本讲全程在线（online），策略与数据收集耦合；离线 bandit（只有固定日志数据）的遗憾分析完全不同。

10.6 与其他讲次的关联

• L9（Data Efficient RL: Bandits）→ 本讲：L9 给出 UCB 算法、乐观原则、regret 框架、$\epsilon$-greedy/greedy 的线性遗憾反例，以及 Lai–Robbins 下界与两类界的分类。本讲把 UCB 的证明补完（L9 第 51 页明确说明「课堂上的短证明有错误，Lecture 10 给出修正版本」）。
• 本讲 → L11（Bayesian bandits / Thompson Sampling）：本讲全程频率派（存在固定真实 $\theta$）；L11 把 $\theta$ 视为随机变量、维护后验 $P(\theta\mid h_t)$，用先验换取更少探索。L11 第 46–49 页把 “posterior sampling 与 UCB 有相同（忽略常数）的遗憾界” 与 $\mathrm{Regret}(\mathrm{UCB},T)$ 并列，正是对本讲 UCB 界的直接引用。
• 本讲 → L12（Bayesian MDP、PSRL、PAC-MDP、RMax、乐观初始化）：本讲 10.3.5 的桥梁（为什么 bandit 框架不够、$(s,a)$ 分解、PAC 的定义预告、乐观需要注入 $\hat R$ 与 $\hat P$）正是 L12 的起点。L12 会给出 MBIE-EB、Simulation Lemma、RMax 与 PAC-MDP 的样本复杂度。
• 本讲 → L13（MCTS）：实验 C 中「每 $25$ 步重跑一次值迭代」暴露了 model-based 方法的规划成本；L13 的 UCB 树搜索正是把「用计算换样本」做到极致，而 UCB 的 bonus 项会原样出现在树的每个节点上。
• L2–L4（规划与 model-free 控制）：值迭代、$V^$/$Q^$ 的定义是实验 C 真值基准的来源；本讲的乐观原则与 L4 的 $\epsilon$-greedy 探索形成对照。
• L16（Value Alignment 客座）：与本讲的遗憾/界无关，仅共享 lecture10post.pdf 这一个文件（第 17 页起）。本讲不涉及。

10.7 关键要点

• 遗憾是「gap × 计数」的双线性形式：$L_T = \sum_a \Delta_a \mathbb{E}[N_T(a)]$。一切界都是对这个式子的两项分别下手——证明的实质就是把 $\mathbb{E}[N_T(a)]$ 压到 $u_i + 3$。
• 证明可以压缩成两条支柱：①「好事件」（最优臂的置信上界从不低估它、次优臂充分拉动后置信上界必低于最优臂）；②「反证法」把「算法行为」变成「计数上界」——这是纯代数，不需要概率。剩余工作只是用联合界与次高斯尾界把坏事件概率压到 $n\delta + \exp(-u_ic^2\Delta_i^2/2)$。
• $\delta_t = 1/t^2$ 与 $c = 0.5$ 是定数选择：前者把 $n\delta$ 压成 $1/n$，后者把 $u_i$ 化简成 $16\log n/\Delta_i^2$。常数（$3$、$16$）来自这两次「平衡」，不要死记，要会重推。
• 指数陷阱：计数层 $\Delta^2$、遗憾层 $\Delta^1$。跨层时乘一个 $\Delta$。
• 问题相关界在近僵局时会失效：tiny-gap 臂让 $u_i > T$，界变成空洞。这正是需要 problem-independent $O(\sqrt{KT\log T})$ 的原因。
• 下界说明「难度住在问题里」：$\log t\sum_a\Delta_a/\mathrm{KL}(R_a\vert R_{a^*})$。gap 缩小 8 倍让常数放大约 8.1 倍，任何算法都躲不掉；因此 $\Theta(\log t)$ 已是终点。
• MDP 不是「状态更多的一臂老虎机」：必须把 gap 换成 $\Delta_{s,a}$、计数换成 $N_T(s,a)$、乐观注入到 $(\hat R, \hat P)$ 两者。实验 C 里状态盲的 bandit-UCB 遗憾比值 $1.994 \approx$ 随机的 $2.001$，是最直接的证据。

10.8 常见误区与注意事项

误区 1：把「好的算法」等同于「看起来奖励高」。 教训：遗憾是反事实量 $V^* - Q(a_t)$，基准是事后最优，不是「平均表现」。$\epsilon$-greedy 在实验 A 中 $L(5000) = 184.9$ 低于 UCB1 的 $487.1$，但这不意味着它更好：它的 $L_T/T$ 稳定在 $0.028$ 不下降（线性遗憾），而 UCB1 的 $L(2000)/L(1000) = 1.699 < 2$ 且持续下降（sublinear）。比较算法必须看清 $L_T$ 的增长阶，而不只是某个 $T$ 上的数值。

误区 2：认为 UCB1 的 bonus 是 $\sqrt{2\log(1/\delta)/N_t(a)}$ 且 $\delta$ 固定。 教训：固定 $\delta$ 会让证明里的联合界项 $n\delta$ 变成随 $n$ 线性增长，界彻底失效。必须用 $\delta_t = 1/t^2$（于是 $\sqrt{2\log(1/\delta_t)/N_t(a)} = \sqrt{4\log t/N_t(a)}$），让 $n\delta = 1/n$ 衰减。「$\delta$ 必须随时间收紧」是 sublinear 的机制性要求，不是工程细节。

误区 3：把计数界的 $\Delta_i^2$ 与遗憾界的 $\Delta_i$ 记混。 教训：定理 7.1 的遗憾界分母是 $\Delta_i$，而中间量 $\mathbb{E}[N_T(a_i)] \le 3 + 16\log n/\Delta_i^2$ 的分母是 $\Delta_i^2$。二者相差一个 $\Delta_i$（从计数到遗憾要乘 $\Delta_i$）。实验数据可以直接看出量级差：$T=5000$ 时计数层求和为 $83932.8$，遗憾层为 $7717.1$（块 1 数据）——同一个证明的两层不要混用。

误区 4：把 Lai–Robbins 下界当成「UCB 应该达到的目标值」，看到实测 $L_t > \log t\cdot C$ 就以为界被违反。 教训：下界是「任何算法都不可能比这更快」的陈述，$\liminf L_t/L_t \ge C$ 完全允许实测值高于 $C$。实验 B3 中 $t=10000$ 时实测 $L_t = 726.8$、下界 $246.61$，这是正常且必须的（而且 $L_t/\log t = 78.91$ 仍在从 $22.21$ 上升，说明渐近区还没到）。此外该下界是渐近的，不要在有限 $t$ 上当作硬约束。

误区 5：以为「UCB 有很好的界」就意味着它在每个实例上都优于 $\epsilon$-greedy。 教训：界是最坏情况/渐近陈述。实验 A 在 $T=5000$ 上 $\epsilon$-greedy 反而更低。UCB 的价值在于保证（$L_T/T\to 0$，而固定 $\epsilon$-greedy 不会），而不是每个有限 $T$ 上的数值优势。反过来，如果先验知识可靠，贝叶斯方法（L11 TS）可能更好——这正是 L11 的动机。

误区 6：把 bandit 算法直接套到 MDP 上。 教训：实验 C 中状态盲的 bandit-UCB 遗憾比值 $1.994$（几乎等于随机策略的 $2.001$），因为它用跨状态混合奖励估计「臂价值」，把同一个动作在不同状态下的好坏平均掉了。MDP 必须 (1) 逐 $(s,a)$ 计数、(2) 逐 $(s,a)$ 乐观、(3) 同时对 $\hat R$ 和 $\hat P$ 注入乐观。「单状态 MDP」这一等价性只是形式上的，算法层面并不迁移。

误区 7：以为遗憾界的常数（$3$、$16$）有本质意义。 教训：$3$ 与 $16$ 来自 $c = 0.5$ 与 $\delta = 1/n^2$ 的特定选择，是「为了平衡两项」的便利取值；换 $c$ 或换 $\delta$ 调度会得到不同常数，但 $O(\log n)$ 的量级不变。要掌握的是推导路径（好事件 → 反证 → 联合界 + 尾界 → 平衡），而不是常数。

10.9 思考题（带答案）

题 1（计算：gap 分解与线性遗憾） 讲义第 10 页的「断脚趾」实例：$\theta_1 = 0.95$（手术）、$\theta_2 = 0.90$（绑扎）、$\theta_3 = 0.10$（不做）。某算法以概率 $0.6, 0.3, 0.1$ 分别选择 $a_1, a_2, a_3$，且选择与历史独立。 (a) 写出每个臂的 gap $\Delta_a$；(b) 求 $t$ 步后的期望累计遗憾 $L_t$；(c) 该算法是线性遗憾还是 sublinear 遗憾？(d) 若改用 $\epsilon = 0.1$ 的 $\epsilon$-greedy 且它已收敛到「以 $1-\epsilon$ 概率拉 $a_1$、$\epsilon$ 概率在三个臂中均匀随机」，求 $L_t/t$ 的极限。

答案. (a) $V^* = \max_a \theta_a = 0.95$，故 $\Delta_1 = 0,\ \Delta_2 = 0.05,\ \Delta_3 = 0.85$。 (b) 由 $L_t = t\sum_a P(a)\Delta_a = t\,(0.6 \cdot 0 + 0.3 \cdot 0.05 + 0.1 \cdot 0.85) = t(0 + 0.015 + 0.085) = 0.1t$。 (c) 线性遗憾。$L_t = 0.1t$，$L_t/t = 0.1 \not\to 0$。它以常数比例 $0.1$ 的时间取到最差的臂 $a_3$，符合讲义第 31 页对线性遗憾的定义。（注意：这与 $\epsilon$-greedy 的第 2 题不同——这里 $a_3$ 被拉的概率恒定，永远不衰减。） (d) 收敛后每步取非最优动作的概率为 $\epsilon = 0.1$（其中 $a_3$ 贡献 $0.1/3$、$a_2$ 贡献 $0.1/3$），故 \(\frac{L_t}{t} \to 0.1\cdot\frac{0.05 + 0.85}{3} = 0.1 \cdot 0.3 = 0.03 .\) 仍是线性遗憾（极限为正），这与讲义第 29 页追问「若 $\epsilon$ 固定，$a_3$ 还会被选多少次？」的结论一致：$a_3$ 会被选中无穷多次。

题 2（推导：从计数界到遗憾界） 已知按讲义证明得到 $\mathbb{E}[N_n(a_i)] \le 3 + \frac{16\log n}{\Delta_i^2}$。请推导定理 7.1 的遗憾界 (1) 式，并明确说明为什么分母从 $\Delta_i^2$ 变成 $\Delta_i$。

答案. 从 $L_n = \sum_{i=1}^{K}\Delta_i\mathbb{E}[N_n(a_i)]$ 出发。最优臂 $i=1$ 的 $\Delta_1 = 0$，对和没有贡献（这也是界里那个 $3\sum_i\Delta_i$ 项只对次优臂有效的道理，讲义 (14) 式写作 $3\sum_{i:\Delta_i>0}\Delta_i$）。对次优臂代入计数界：

分母的变化来自乘上去的那个 $\Delta_i$：计数层每一项是 $\Delta_i \cdot \frac{16\log n}{\Delta_i^2} = \frac{16\log n}{\Delta_i}$，$1/\Delta_i^2$ 中的一个 $\Delta_i$ 被遗憾分解的系数 $\Delta_i$ 约掉了。这正是「计数层 $\Delta^2$、遗憾层 $\Delta^1$」的来源。量级上：$\Theta(\log n)$。$\blacksquare$

题 3（理解：为什么 $\delta$ 必须随时间收紧） 假设我们改用固定 $\delta$（即 $\mathrm{UCB}(a) = \hat Q(a) + \sqrt{2\log(1/\delta)/N_t(a)}$，$\delta$ 与 $t$ 无关）。指出证明的哪一步会失效，并说明后果。

答案. 失效的是证明第 4 步（讲义 (13)–(14)）。那里用联合界对 $s = 1,\dots,n$ 求和：

每一项都是 $\delta$（与 $s$ 无关），于是 $n$ 项求和给出 $n\delta$。当 $\delta = 1/n^2$ 时 $n\delta = 1/n$，随 $n$ 衰减，是好项。若 $\delta$ 固定，$n\delta = \Theta(n)$ 线性增长，代入 (10)–(12) 后 $\mathbb{E}[N_t(a_i)] \le u_i + n(n\delta + \cdots)$ 中的 $n^2\delta$ 项变成 $\Theta(n^2)$，界彻底失去意义（大于总步数的平方）。

结论：$\delta_t = 1/t^2$ 不是技术性装饰，而是让「联合界带来的 $n$ 倍放大」被「每个置信区间的 $1/n^2$」刚好抵消的唯一机制。这也解释了为什么 UCB 的 bonus 必然包含一个缓慢增长的 $\log t$ 因子——它正是 $\log(1/\delta_t)$ 的化身。

题 4（迁移：从 bandit 到 MDP） 在 10.4 实验 C 的 4×4 滑坡 GridWorld 中，把 bandit-UCB 直接迁移过来得到遗憾比值 $R(3000)/R(1500) = 1.994$，与均匀随机的 $1.997$ 几乎相同。请解释原因，并写出 MDP 中正确的遗憾分解；再说明「逐 $(s,a)$ 乐观」为什么能把这个比值降到 $1.029$。

答案. 原因：bandit-UCB 维护的是 $\hat Q(a)$，即「动作 $a$ 在所有状态下观测到的平均奖励」。在 GridWorld 中，向上（$a_1$）在起始格 $s_0$ 的 gap 是 $0.68$（不错），但在 $s_{14}$ 的 gap 是 $1.83$（很糟）；横向平均之后这些结构被抹平，$\hat Q(a)$ 对所有动作都趋于同一个值（因为除目标外每步奖励都是 $-1$）。于是 $\arg\max_a$ 长期是噪声驱动的近似随机选择，遗憾自然与均匀随机相同，$R(T) = \Theta(T)$。

正确的分解：

即把 gap 换成状态相关的 $\Delta_{s,a} = V^(s) - Q^(s,a)$，计数换成 $N_T(s,a)$。

逐 $(s,a)$ 乐观奏效的原因：它把「乐观」注入到模型本身——未访问的 $(s,a)$ 得到 $R_{\max}$ 的奖励与自环转移，使这些 $(s,a)$ 在规划中显得极有价值，从而被主动覆盖；一旦某 $(s,a)$ 被访问多次，bonus $\sqrt{2\log(1/\delta)/N(s,a)}$ 收缩，估计的 $Q^*$ 逼近真实，动作选择稳定到最优。于是遗憾不再是 $\Theta(T)$：实测 $R(1500) = 794.74 \to R(3000) = 817.96$，后半段增量仅 $23.22$，比值 $1.029$——收敛后几乎不再有新遗憾。这与 bandit 中「$N_T(a_i)$ 被 $u_i$ 封顶」是同一个思想在 $(s,a)$ 维度上的推广。

题 5（辨析：上界、下界与实测） 实验 B3 在 $t = 10000$ 处测得 UCB1 的 $L_t = 726.8$，而 Lai–Robbins 下界给出 $\log t \cdot C = 246.61$。某同学据此断言「UCB1 比理论最优差了 $2.9$ 倍，所以 UCB 的界是错的」。请指出其中的三处概念错误。

答案.

1. 混淆下界的语义：Lai–Robbins 是「$\liminf \ge C$」，即任何算法都不可能渐近快于 $\log t \cdot C$。实测高于下界不是矛盾，而是必然——下界描述的是「困难程度的地板」，不是「算法的目标值」。要证伪它，需要找到一个低于下界的算法，而不是观察到高出。
2. 忽略渐近性：定理取 $t\to\infty$ 的极限。实测 $L_t/\log t$ 从 $22.21$（$t{=}1000$）单调升到 $78.91$（$t{=}10000$），说明 UCB 尚未进入渐近区，用有限 $t$ 的比值去比较渐近常数没有意义。
3. 拿「量级」与「常数」混谈：正确的结论是「UCB 与下界同为 $\Theta(\log t)$，故量级最优（up to constant）」。$2.9$ 倍是常数因子差异，而界（无论上下）本来就允许常数不可比。想改进的是常数（例如利用先验知识，见 L11 的贝叶斯方法与 Thompson 采样），而不是量级。