65 镜一次看完 · Ctrl+F 可搜全文 · Ctrl+P 可存成 PDF · 想看动画回放映厅
知识点 1 · 总结
核心结论
遗憾的基准是「从第一步起就最优、因而会走到的那些状态」——把「走错路落到坏地方」也算在账上。PAC 只比「你自己所在的状态下最好的动作」，不问你怎么来的。
底层机制
差别只在一种情况下显形：算法因早期的错落进坏区域且出不来。遗憾一直收费，PAC 不追究。
常见误解
误解：「PAC 能给更小的遗憾」。讲师说了这句并当场自我更正 —— 两个数不可直接比较，就像说「摄氏度比公里少」。
与你的考试
回合制（每回合重置到固定起点）下两者靠近，因为两个基准从同一处出发。这也解释了为什么老虎机主要用遗憾（只有一个状态，两者本就重合），MDP 里 PAC 更常见。
知识点 1 · 检验
PAC 和遗憾这两个判据最本质的区别是什么？
遗憾隐含地把「你走错路、落到一个糟糕的地方」也算在账上，因为它的基准是一条你没走的路；PAC 不问你怎么走到这里的，只问「在你所在的地方，你尽力了吗」。所以 PAC 明显更宽容，而两者在回合制（每回合重置到固定起点）下会靠近。「高概率 vs 期望」是表述差异，不是本质 —— 遗憾也有高概率版本。「有限/无限时域」两个判据在两种设定下都有定义。「数值总是更小」两者不可直接比较，讲师说了这句并当场自我更正。
知识点 2 · 总结
核心结论
按定义 V*(s) = max_a Q*(s,a)，所以 Q*(s,a) ≤ V*(s) 恒成立（3000 个随机 MDP 全部 (s,a)：max[Q*−V*] = 0.000e+00）。于是板上那条不等式不约束算法。
底层机制
正确写法：V^{A_t}(s_t) ≥ V*(s_t) − ε（Kakade 式）。判据：看左边那个量算法能不能改 —— Q* 改不动，V^{A_t} 由算法完全决定。
常见误解
误解：「某个动作特别好，Q* 会顶出 V*」。V* 就是所有 Q* 的最大值，没有余地。
与你的考试
全讲 V 与 Q 混用（第三集的「乐观」条件写 V_t 却带 s_t、a_t 两个下标 —— 那是 Q；字幕还把 V* 念成「B star」）。靠下标数目判断比靠字母可靠。另：样本复杂度分母是 ε(1−γ)² 不是 ε(1−γ²) —— γ=0.9 差 19 倍，0.99 差 199 倍，0.999 差 1999 倍。
知识点 2 · 检验
为什么「Q*(s_t,a_t) ≥ V*(s_t) − ε」不能当作 PAC 的定义？
V*(s) = max_a Q*(s,a)，所以 Q* 永远不超过 V*（3000 个随机 MDP 验证：max[Q*−V*] = 0.000e+00）。于是这条式子对最优动作自动成立，对次优动作则是 MDP 本身决定的固定差值 —— 和算法做了什么无关。正确的是 V^{A_t}(s_t) ≥ V*(s_t) − ε：左边换成算法自己策略的值。判断一条条件是不是真条件，看左边那个量算法能不能改。「连续空间没定义」无关。「ε 位置」移到左边等价。「没写 1−δ」那部分讲座是写了的，不是这里的问题。
知识点 3 · 总结
核心结论
乐观：算出来的值不低估。准确：攒够信息后值要接近混合 MDP 上 π_t 的值（不是真 MDP，也不是 V*）。学习复杂度：重跑乐观值迭代的次数有上限。
底层机制
乐观不够，一句话反例（讲师原话）：「setting our values super high and never updating」—— 乐观完美成立，而算法什么也学不到。
常见误解
误解：「乐观就够了，试遍了自然学会」。乐观里不含任何「要收敛」的内容。
与你的考试
分工：乐观 = 不会太早放弃；准确 = 不会太晚放弃；有界 = 折腾得完。第三条里「Q 更新的次数」指重跑值迭代的次数，不是一次值迭代内部的 Bellman 回退数。
知识点 3 · 检验
证 PAC 的三条充分条件里，为什么光有「乐观」不够？
讲师用一句话打掉它：「optimism would be easy to hold by just setting our values super high and never updating」。乐观是纯粹的「不要过早放弃」条件，不含任何收敛要求。所以要配上准确性（攒够信息后值要接近真值 —— 「if something really is bad, you don't want to be really optimistic forever」），以及学习复杂度有界（折腾得完）。三条分别对应：不会太早放弃 / 不会太晚放弃 / 有终点。「连续空间」这一段讨论的是表格 MDP。「只对确定性」事实错误。「需要知道 V*」V* 只出现在分析里，算法用不到。
知识点 4 · 总结
核心结论
并集界把每次估计的失败概率相加，所以更新次数必须有限。于是每个 (s,a) 封顶 m 次，总预算 |S|·|A|·m（10×4×100 = 4000）。
底层机制
m 在证明里出现三次且是同一个：算法里（用几个样本）、预算里（|S||A|m 次更新）、β 里（log(2|S||A|m/δ)）。字幕把它写成大写 M，容易读成「一个 MDP」。
常见误解
误解：「这肯定是笔误」。不是笔误 —— 但也不是优点。讲师自己引 Tom Mitchell：机器学习的要义是设计能随数据增多而持续改进的算法，而它到 m 就停。
与你的考试
对照 L11 第八集：那里不封顶，靠失败预算按 1/t² 衰减（Basel 和收敛）。这里要同时控转移与奖励两个模型，封顶更粗但更省事。判断法：去掉这一条算法会变差吗？不会 ⟹ 它不为性能服务。
知识点 4 · 检验
MBIE-EB 为什么规定每个 (s,a) 只用前 m 个样本？
证明需要所有 (s,a) 的所有估计同时落在置信范围内，而并集界把失败概率相加 —— 更新次数无穷则总上界无穷，等于什么都没说。封顶后总预算是 |S||A|m，有限，β 正是按它倒推的。这是证明技术的硬约束，不是算法优点：实践中当然该用上所有数据。判断法：去掉这一条算法只会变好。「内存」不是理由。「分布漂移」不成立 —— 这里的 (s,a) 的奖励与转移分布是固定的。「忘掉坏数据」模型估计与策略好坏无关，样本都是有效的。
知识点 5 · 总结
核心结论
取偏差 t = β/√n 代进 exp(−2nt²/R²)（R = 1/(1−γ)）：−2n·(β²/n)·(1−γ)² = −2β²(1−γ)²，n 精确约掉。实测 n 从 1 到 10⁵ 指数恒为 −0.1800000000。
底层机制
所以 1/√n 是唯一选择：换 1/n 指数随 n 趋零（界作废），换 1/n^0.25 会发散（界松到无意义）。只有它让失败概率与访问次数无关 —— 并集界正需要这一条。
常见误解
误解：「1/√n 是挑出来的，幂次可调」。它是 Hoeffding 唯一允许的幂次。β 也不是挑的，是从总预算 δ 倒推的。
与你的考试
讲座没念出的前提：奖励落在 [0,1]，于是 Bellman 目标的取值范围宽度是 1/(1−γ)。闭合验证：β=24.4775 → exp(−2β²(1−γ)²) = 6.25×10⁻⁶ = δ/(2|S||A|m)，×2×4000 = 0.050000 = δ。
知识点 5 · 检验
为什么 MBIE-EB 的奖励加成必须是 β/√n 这个形状？
把 t = β/√n 代进 exp(−2nt²/R²)：−2n·(β²/n)·(1−γ)² = −2β²(1−γ)²，n 消失（实测 n 从 1 到 10⁵ 指数恒为 −0.18）。这正是并集界需要的：每一次更新用同一个失败预算 δ/(2|S||A|m)，加起来才精确等于 δ。换 1/n 指数会随 n 趋零（失败概率趋于 1，界作废）；换 1/n^0.25 指数发散（界成立但松到无意义）。「最自然」方向对但不是理由 —— 理由是抵消。「计算便宜」不是考量。「等于 Beta 后验标准差」无关，这里是频率派论证。
知识点 6 · 总结
核心结论
M̂ = 经验模型（T̂, R̂）。M̃ = 经验模型 + 奖励加成（共用同一个 T̂，唯一差别在奖励）。M′ = 已知集上用真 R、T，其余用 M̃。
底层机制
准确性比的是「π_t 在 M′ 上的值」，不是 V*、不是真 MDP。这样构造才不与乐观冲突：熟悉处 M′ 是真模型（准确起作用），陌生处是乐观模型（允许高估）。
常见误解
误解：「跟真 MDP 比」。没探索过的地方你对真 MDP 一无所知，而且那里本来就该高估（乐观条件），要求准确会和乐观直接冲突。
与你的考试
M-hat 与 M-tilde 近乎同音，字幕调换过，课上有学生专门问。另：MBIE 与 MBIE-EB 被混用 —— 只有带 β/√n 的 MBIE-EB 是乐观证明的对象。连接 M′ 与真 MDP 靠 simulation lemma。这套机器 S&B 没有。
知识点 6 · 检验
M̂（M-hat）和 M̃（M-tilde）的区别是什么？
转移模型是同一个 T̂，差别只在奖励：M̂ 用 R̂，M̃ 用 R̂ + β/√n。这一处必须记牢，因为 M-hat 与 M-tilde 近乎同音、字幕调换过，课上有学生专门举手问。「M̃ 用真实转移」算法根本不知道真实转移。「已知集 / 未知集」那是第三个 MDP M′ 的构造 —— 它在已知集上用真模型、其余用 M̃。「规划 vs 评估」不是它们的区别。
知识点 7 · 总结
核心结论
把经验流切段，每段问「会不会走到未知 (s,a)」。概率小 ⟹ 待在已知区、估计准 ⟹ 近最优，不犯大错。概率大 ⟹ 会撞上未知 ⟹ 每次烧掉一格计数。
底层机制
预算 |S||A|m 有限 ⟹「概率大」的段数有限 ⟹ 大错总数有限，正是 PAC 定义里的 N。这就是鸽笼原理。
常见误解
误解：「得先证它会收敛」。这是一个穷尽式论证，不是收敛性论证 —— 两类覆盖所有时刻，各自成立就够。
与你的考试
第四集那条「故意扔数据」在这里第二次发挥作用：第一次让并集界加得起来，第二次给鸽笼一个有限的格子数。同一个 m 撑起证明的两根支柱。
知识点 7 · 检验
「学习复杂度有界」这一条是怎么证的？
这是一个穷尽式论证，完全不谈收敛：把所有时刻分成两类，证明第一类不犯大错、第二类次数有限，两类覆盖全部时刻即可。第二类靠鸽笼原理 —— 每次撞上未知 (s,a) 就消耗一格计数，而封顶规定让总格子数只有 |S||A|m。「先证收敛」不需要，也做不到（算法一直在探索）。「Hoeffding 求和」那是乐观那一条用的工具。「遍历 + 平稳分布」不需要这个假设。
知识点 8 · 总结
核心结论
共轭仍然管用：转移是多项式，配 Dirichlet；奖励是伯努利，配 Beta。Dirichlet 是 Beta 的多维推广，参数同样是伪计数，更新还是加一。
底层机制
四步：抽一个完整 MDP → 值迭代解它 → 按解出的策略走完整个回合 → 计数加一。代价在「解」那一步（每回合一次完整规划）。
常见误解
误解：「每一步重抽更及时」。标准答案是不行 —— 抽出来的是一个内部一致的世界假设，检验它需要一整段连贯行动（深度探索）。但本片三次尝试都没做出这个差别（比值 1.00 / 0.99 / 1.04）。当理由记，别当结论记。
与你的考试
三种获得乐观的方式：造一个奖励加成（MBIE-EB，要推常数、控并集界）；抽一个样本（后验采样，乐观自带）；设一个高初值（不带保证）。「时间一致性」是从老虎机到 MDP 真正新增的困难。
知识点 8 · 检验
MDP 的后验采样为什么要「抽一次、走完一个回合」，而不是每步重抽？
在抽出来的 MDP 上规划出的策略，是为了检验那个假设而生的 —— 检验可能要求「一直往一个方向走很多步去看看」。每步重抽 = 每步换一个假设。这叫深度探索：乐观不只要在数值上成立，还要在时间上保持一致。坦白一句：本片三次尝试都没能在一条链上把这个差别做出来（比值 1.00/0.99/1.04）—— 链允许来回走，对每步重抽太仁慈。这条当理由记，不当实测结论记。「计算代价」是次要理由。「后验不变」事实错误 —— 回合内每步都在观察。「无偏性」与此无关。
知识点 9 · 总结
核心结论
前八集全部挂在 N(s,a) 上（UCB 的 √(2log t/N)、MBIE-EB 的 β/√N、已知集 N≥m、鸽笼的 |S||A|m）。而连续空间里每个状态只到达一次。
底层机制
三条替代：密度模型/伪计数（Bellemare）、哈希计数（Berkeley）、学到的嵌入。共同形状是「先把相似状态归为一类，再恢复计数」；共同代价是所有保证都失效。
常见误解
误解：「把计数换成网络就行」。「见过多少次」没有监督信号 —— 连续空间里真实答案都是 0 或 1。要的其实是密度，不是计数。
与你的考试
选 MBIE-EB 讲的真正理由：奖励加成能直接塞进无模型更新，而深度网络上写不出置信集。讲师评 bootstrap DQN 「not incredibly effective」，而冻结嵌入 + 贝叶斯线性回归更简单却更有效。
知识点 9 · 检验
为什么这一讲花六集讲的是 MBIE-EB，而不是用置信集的 MBIE？
讲师直说了：「that's why I chose MBIE-EB... because those sort of reward bonuses are much easier to extend to the model-free case」。如果动态模型是深度网络，给它写置信集「really tricky」；而奖励加成只是在 Q 学习更新里加一项，不需要模型。经验上两者大体一样好。这六集的理论选择，是被「哪个能搬到深度学习里」倒推出来的。「复杂度更低」不是讲座给的理由。「置信集没有 PAC」事实错误，MBIE 也有。「不需要计数」反了 —— β/√N(s,a) 里就是计数，而这正是它跨不过函数逼近的原因。