65 镜一次看完 · Ctrl+F 可搜全文 · Ctrl+P 可存成 PDF · 想看动画回放映厅
知识点 1 · 总结
核心结论
前十讲的保证全是渐近的：迭代次数 / 回合数 / 步数趋于无穷。没有一条回答「我只有 200 个病人能做到什么」。
底层机制
理由是应用上的：每一个数据点是一个人（病人、学生、广告受众）。Pong 要几百万帧没关系 —— 帧不要钱。
常见误解
误解：「能学到就行，收敛性我们已经有了」。这在前十讲是对的；判据一换，贪心、固定 ε-贪心、均匀随机会当场出局。
与你的考试
工具：多臂老虎机 —— 一个状态、无转移、m 个臂、独立同分布。对照 L01 四轴：优化在、探索在、延迟后果与泛化都关掉了。这是隔离「探索」的最小装置。
知识点 1 · 检验
为什么这一讲要把 RL 缩成「一个状态、没有转移」的多臂老虎机？
对照 L01 的四个轴：优化和探索留下，延迟后果（没有转移，这次动作不影响下次处境）和泛化（只有一个状态）都被关掉。这样「要多少数据才能学到」这个问题第一次能写出干净的答案。「闭式解」不对 —— 分布未知，本来就没有可直接算的最优臂。「真实应用只有一个状态」恰恰相反，所以 L12–L13 要把这一套搬回 MDP。「多状态下遗憾没定义」是事实错误，MDP 的遗憾有标准定义。
知识点 2 · 总结
核心结论
差距 Δ_a = Q(a*) − Q(a)；遗憾 Regret(T) = Σ_{t=1}^T Δ_{a_t}。相对「一直拉最优臂」这个不可能的基准，一共亏了多少。
底层机制
为什么必须求和而不是平均：平均会把早期的错除掉；而如果那些步里每一步是一个病人，那个代价不该被除掉。
常见误解
误解：「看平均奖励就行」。两个毛病：不减基准就无法跨问题比较；且后期的好表现会冲淡早期的代价。
与你的考试
判据：遗憾要次线性。实测均匀随机的每千步遗憾 50.06/49.98/50.03/50.01 —— 平不下来，手算基准 (0+0.05+0.10)/3×1000 = 50.0 对上。
知识点 2 · 检验
为什么用「累积遗憾」而不是「平均奖励」来衡量算法？
一个算法前 1000 步全在乱试、之后 99000 步全对，它的平均奖励几乎等于最优 —— 那 1000 步的代价被除掉了。而如果那 1000 步里每一步是一个病人，代价不该被除掉。求和不会冲淡。平均奖励还有第二个毛病：不减去 Q(a*) 这个基准就无法跨问题比较。「难以计算」不是理由，两者都好算。「不是无偏估计」与此无关。「遗憾总是有界」恰恰相反 —— 线性遗憾正是无界增长的，这一讲的全部努力就是把它压到次线性。
知识点 3 · 总结
核心结论
固定 ε 的每步遗憾收敛到 (ε/m)·Σ_a Δ_a > 0，不是收敛到 0。三臂 (0.5,0.45,0.4)、ε=0.1 时 = 0.005/步 = 每千步 5.00。
底层机制
实测每千步遗憾 6.588 → 5.318 → 5.070 → 5.034（T 到 5×10⁵，40 次重复）：停住了，正好停在手算值上。
常见误解
误解：「ε-贪心已经在探索了，够了」。它确实收敛到最优臂 —— 毛病是学到之后仍按同样力度乱拉，第一百万步和第十步一模一样。
与你的考试
三者犯的是同一个错：探索力度是与把握无关的常数（0 / ε / 1）。贪心还会锁死：2000 次重复里 45.0% 停在次优臂，且比例不随 T 衰减。陷阱：只跑到 T=10⁴ 会看到 6.588 仍在降，误以为次线性。
知识点 3 · 检验
固定 ε 的 ε-贪心为什么是线性遗憾？
ε-贪心确实收敛到最优臂 —— 毛病不在这里。等均值估准后，损失全部来自那 ε 份随机探索：每步 (ε/m)·ΣΔ_a，三臂 (0.5,0.45,0.4)、ε=0.1 时是 0.005/步。这是个正数且不随 T 变，累积起来就是直线。实测每千步遗憾 6.588→5.318→5.070→5.034，停在手算的 5.00。「收敛不到」是事实错误。「调小 ε」只改直线的斜率，不改它是直线 —— 而且 ε 越小锁死风险越大。「均值有偏」不对，样本均值是无偏的。
知识点 4 · 总结
核心结论
liminf Regret(T)/log T ≥ Σ_{Δ_a>0} Δ_a / KL(R_a‖R_{a*})。分子 = 拉错一次亏多少，分母 = 两个分布有多好区分。
底层机制
差距减半系数就翻倍：Δ=.20/.10/.05/.02 → 2.43/4.97/9.98/24.99。因为 KL ≈ Δ²/(2p(1−p))，所以 Δ/KL ≈ 2p(1−p)/Δ。
常见误解
误解：「前期探索完就一直贪心 = 常数遗憾」。给定任何固定预算，总有一对臂区分不开；一旦选错，之后每步都线性地亏。
与你的考试
下界真正的价值是它没禁止 log T。实测：三臂下界系数 14.95，T=5×10⁵ 时下界 196、UCB 362（1.85 倍）。T=10⁴ 时实测 129.8 低于下界 137.7 并不矛盾 —— Lai–Robbins 是 T→∞ 的下极限。
知识点 4 · 检验
Lai–Robbins 下界里 Δ_a / KL(R_a‖R_{a*}) 这一项，为什么差距越小反而越大？
分子 Δ_a 确实随差距变小，但分母 KL 是二阶小量（KL ≈ Δ²/(2p(1−p))），掉得更快，所以比值 ≈ 2p(1−p)/Δ 反而涨。代 p=0.5：Δ=.20/.10/.05/.02 给出 2.43/4.97/9.98/24.99，与近似值 2.50/5.00/10.00/25.00 几乎重合。直觉：亏得少不等于好办，因为你也更难发现自己亏了。「每次亏得更多」反了 —— Δ 小就是每次亏得少。「KL 趋于无穷」反了 —— 分布接近时 KL 趋于 0。「常数次」正相反，需要的次数随 1/Δ² 增长。
知识点 5 · 总结
核心结论
a_t = argmax_a [ Q̂_t(a) + u_t(a) ]。探索和利用被合并进同一个数 —— 均值高（利用）和没怎么试过（探索）都会把它抬高。
底层机制
两难都赢：乐观的拉动要么真的好（不亏），要么不好（但均值被拉下、半径收缩，错误自限）。这就是后面那个证明的直觉版本。
常见误解
误解：「拉均值最高的才理性」。两个臂均值都 0.6，一个拉过 1000 次一个拉过 3 次 —— 贪心看它们完全一样，而它们显然不一样。
与你的考试
一次解决两个毛病：贪心错误不自限（45% 锁死），固定 ε 探索不收缩。乐观的探索是内生、定向、自动收缩的，不是外挂的随机扰动。
知识点 5 · 检验
「乐观面对不确定」为什么能同时解决贪心和固定 ε-贪心的毛病？
UCB 没有分阶段，也没有两个模式：只有一个判据 Q̂+u，均值高（利用）和没怎么试过（探索）都会把它抬高。对贪心的错误不自限：被高估的臂上置信界最高，一定会被拉到，拉到就被修正。对固定 ε 的探索不收缩：半径随 n 增加而缩，把握大了探索自动停。「分两个阶段」是 explore-then-commit，那正是 KP4 排除掉的做法。「更准的估计量」不对 —— 用的就是样本均值。「需要真实方差」恰恰相反，下一集用 Hoeffding 正是因为不知道方差。
知识点 6 · 总结
核心结论
P(Q > Q̂ + u) ≤ exp(−2nu²)，只要奖励有界、对任意 n 成立。反着用：令它等于失败预算 δ/t²，解出 u。数值回代已验（n=t=100, δ=.05 → u=0.2470 → 5.0×10⁻⁶ = δ/t²）。
底层机制
不能用 ±1.96σ/√n：σ 未知（它就是要学的东西），且 1.96 来自 CLT 是渐近的，n=3 时没保证。
常见误解
误解：「用标准 95% 置信区间」。Hoeffding 宽 2.5 倍（n=100 时 0.2470 vs 0.0980）—— 那是保证的价格。
与你的考试
记号陷阱三连：① 转录稿的 μ/ν 是半径 u，不是均值（文献里 μ 才是均值，本讲用 Q(a)）；② 根号盖住整个表达式；③ exp(−2nu²) 整体在指数上（n=100,u=.247 时 5.0×10⁻⁶ vs 8.4×10⁻⁸⁹）。
知识点 6 · 检验
为什么用 Hoeffding 不等式而不是 ±1.96σ/√n 来定置信半径？
σ 就是我们要学的分布的方差，当然不知道；而 1.96 来自中心极限定理，是 n→∞ 的渐近结果，在 n=3 时没有保证 —— 而 n=3 正是半径最要紧的时刻。Hoeffding 只要奖励有界，对每一个 n 成立。「更窄」反了：n=100 时 Hoeffding 是 0.2470，正态近似 0.0980，宽 2.5 倍，这是保证的价格。「完全无效」太强 —— 正态近似在 n 大时是好的，问题是这里需要小 n 也成立。「不需要知道 n」是事实错误，公式里 n 就在分母上。
知识点 7 · 总结
核心结论
引理 U_t(a_t) ≥ Q(a*)（置信区间不失效时）。情形一 a_t=a*：直接用区间。情形二 a_t≠a*：argmax 给 U_t(a_t) ≥ U_t(a*)，再用区间。
底层机制
加减同一项：Regret = Σ[U_t(a_t) − Q(a_t)] + Σ[Q(a*) − U_t(a_t)]，第二块由引理 ≤ 0，丢掉只让界更松。讲座：「now we don't have any a stars anymore」。
常见误解
误解：「a* 不知道就没法算」。证上界不需要知道确切值 —— 只要把它替换成已知量，并证明替换方向安全。
与你的考试
结构观察：情形二那条链本身覆盖了情形一（argmax 对所有臂成立，包括 a* 自己），分两情形是为了讲清楚。全部挂在一个前提上：置信区间不失效 —— 那是下一集。
知识点 7 · 检验
证明里是怎么处理不可观测的 Q(a*) 的？
手法是加减同一项：Regret = Σ[U_t(a_t) − Q(a_t)] + Σ[Q(a*) − U_t(a_t)]。核心引理说第二块每一项 ≤ 0（置信区间不失效时 U_t(a_t) ≥ Q(a*)），所以丢掉它只让上界更松，方向安全 —— 讲座原话「now we don't have any a stars anymore」。这是证上界的通用手法：把不知道的换成知道的，且往安全方向换。「用经验均值估计」没有保证，且经验最大值是有偏的（见 L04 最大化偏差）。「当作输入」那就不是算法了。「对所有 a* 取最坏」会得到平凡的线性界。
知识点 8 · 总结
核心结论
失败概率相加。固定 δ → T·m·δ（δ=.05,m=3,T=10⁴ 时是 1500，等于没说）。改成 δ/t² → Σ1/t² = π²/6 = 1.644934 < 2 → 总失败 < 2mδ，与 T 无关。
底层机制
为什么是 1/t²：1/t 的和发散（调和级数），1/t³ 收敛但更保守。1/t² 是让总和收敛的最省的一档。半径里的 t² 就是从这来的。
常见误解
误解：「每个 95%，合起来还是 95%」。这是多重比较里最常见的事故 —— 失败概率是相加的。
与你的考试
三处口误/笔误：① 字幕的 t^(−t) 应为 t^(−2)；② 失败事件写成 Q̂ > U，应为真均值 Q > U；③ 「they don't hold is at least 1−2mδ」应为它们确实成立。另：并集界取到 t=∞（区间永远成立）与定理对有限 T 陈述，是两个不同的「时域」。
知识点 8 · 检验
为什么第 t 步的失败预算要取 δ/t² 而不是固定的 δ？
并集界让失败概率相加：固定 δ 时 m 个臂 T 个时刻累成 Tmδ（δ=.05, m=3, T=10⁴ → 1500，毫无意义），而且随 T 增长。取 δ/t² 后 Σ_{t≥1} 1/t² = π²/6 = 1.644934 < 2，总失败 < 2mδ，不含 T —— 定理里「1 − 2mδ」的那个 2 就是这么来的。「更窄更激进」反了：预算变小 ⟹ 区间必须更宽。「Hoeffding 要求」不对 —— Hoeffding 对任何失败概率都成立，衰减是我们选的。「半径收缩更快」反了：log(t²/δ) 随 t 增大，是让半径涨的那一项。
知识点 9 · 总结
核心结论
n_t(a) 在分母让半径按 1/√n 缩；t 在 log 里让半径涨。所以不拉的臂半径会慢慢变宽，一定会被重新选中 —— 混淆二者这个机制就消失了。
底层机制
三步：① 把 log(t²/δ) 放大成 log(T²/δ)（t≤T，安全）；② Σ_{n≤N} 1/√n ≤ 2√N（N=10⁴ 时 198.54 vs 200）；③ Σ√N_a 在均分时最大 = √(mT)（223.61 vs 独大 103.98，因 √ 是凹的）。
常见误解
误解：「n 和 t 差不多」。也别把「次线性」读成遗憾在减少 —— 遗憾一直在涨（225→802→2794），掉的是占比（22.5%→8.0%→2.8%）。
与你的考试
常数没被追踪：学生当场补了漏掉的 1/2，讲师回「I'll be a little loose with constants but definitely catch me on them」。记形状不记常数：√T、√m、√log。
知识点 9 · 检验
UCB 的半径 √(log(t²/δ)/(2n)) 里，n 和 t 各起什么作用？
n_t(a) 在分母，每多拉一次这个臂半径就按 1/√n 缩；t 在分子的 log 里，每走一步（拉任何臂）都让它涨。这个对立正是 UCB 永不彻底放弃任何臂的机制：长期不拉的臂 n 不动而 t 在涨，半径慢慢变宽，最终一定会被重新选中。讲师专门预先点名了这处混淆，因为混了它整个算法就看不懂了。「都收缩」「n 涨 t 缩」方向搞反。「t 只影响失败概率」不对 —— 失败预算 δ/t² 正是通过 log(t²/δ) 进入半径的。