65 镜一次看完 · Ctrl+F 可搜全文 · Ctrl+P 可存成 PDF · 想看动画回放映厅
知识点 1 · 总结
核心结论
Regret = O(Σ_{Δ_a>0} log T / Δ_a)。UCB 的规则里只有经验均值和计数 —— 没有 Δ。界在描述算法，不在规定算法。
底层机制
断脚趾实例（0.95/0.90/0.10）：1/Δ = 20.000 与 1.176，占比 94.4% 对 5.6%。难的是区分 0.95 和 0.90，不是避开 0.10。
常见误解
误解：「界里有 Δ，算法总得先算它」。误读成这样会得出「这算法没法用」的错误结论。
与你的考试
两条界分工不同：不依赖差距（√T，对所有问题一致，但松）；依赖差距（log T，形状更好，但 Δ→0 时系数爆炸）。两条都对。
知识点 1 · 检验
在断脚趾实例（0.95 / 0.90 / 0.10）里，依赖差距的界主要由哪个臂贡献？
界是 Σ log T / Δ_a，差距在分母上：Δ=0.05 给出 1/Δ = 20.000，Δ=0.85 只给出 1.176，占比 94.4% 对 5.6%。那个明显糟糕的臂几次采样就能排除，几乎不贡献难度；难度几乎全部来自区分两个都不错的选项。这与 L11 的 Lai–Robbins 下界形状一致（那里是 Δ/KL，同样随差距变小而增大）。「各一半」差了 17 倍。「最优臂」它的 Δ=0，根本不在求和里。
知识点 2 · 总结
核心结论
开局各拉一次得 1,1,0，t=3：奖励项对三臂相同 √(2 log 3/1)=1.4823，于是上界 2.4823 / 2.4823 / 1.4823。第三个进不了 argmax。
底层机制
拉一次手术后 t=4、N=(2,1,1)：2.1774 / 2.6651 / 1.6651 —— 翻到并指。就算手术拿到 0 也一样（1.6774 仍远低于 2.6651）。
常见误解
误解：「探索就是给每个臂一点概率」。此刻 UCB 给坏臂 0，ε-贪心给它 ε/|A| = 0.0333 —— 跑一万步就是约 333 次，乘差距 0.85 ≈ 283 的损失，且买不到任何信息。
与你的考试
转录稿系统性丢根号：正确是 √(2 log t / N_t(a))，计数在根号里面。另：这里常数 2 是 Auer 等人的写法；S&B 写成 c·√(ln t/N)，c 可调，别混着引。
知识点 2 · 检验
开局各拉一次得到 1、1、0 后，UCB 选中第三个臂的概率是多少？
此刻三个臂的奖励项完全相同（都只拉过一次，√(2 log 3/1)=1.4823），所以上置信界的排序就是经验均值的排序：2.4823 / 2.4823 / 1.4823。argmax 是确定性的，第三个臂差了整整 1.0，概率精确为 0。「1/3」把 UCB 当成了均匀探索。「0.0333」那是 ε-贪心的 ε/|A|，正是这一集要对照的那个数。「取决于破平」破平只发生在前两个打平的臂之间，与第三个无关。
知识点 3 · 总结
核心结论
机制只有一句：没被拉的臂，n 冻住而 log t 在涨，半径变宽（t=10→10⁵ 时 2.146→4.799）。上界规则里它让分数上升（必然回头），下界规则里让分数下降（永不回头）。
底层机制
实测两臂 (0.55,0.45)、300 次重复：下界规则每千步遗憾 25.05→26.34→28.34→30.00（不降反升），同期 UCB 24.64→2.07。
常见误解
误解：「用下界更稳健，保守一点没错」。在已部署的系统里保守是美德；在需要学习的场合它自毁。
与你的考试
拆开看：30.0% 的运行锁死在次优臂且比例不随 T 衰减；锁死那部分每千步遗憾 99.999（= 1000×Δ，亏满额）。0.30×100 = 30.0，正好对上。讲师原话：「you're never gonna get information that allows us to disprove our hypothesis」。
知识点 3 · 检验
为什么「选下置信界最高的臂」会导致线性遗憾？
半径 √(2 log t / n) 对一个没被拉的臂会持续变宽（t=10→10⁵ 时 2.146→4.799）。在下界规则里这个量是减掉的，所以它的分数下降 —— 正反馈：越不选越不会选。实测两臂 (0.55,0.45) 时 30% 的运行永久锁死，且比例不随 T 衰减，锁死部分每千步亏满 99.999。「估计有偏」不对，样本均值无偏。「过度探索」正相反 —— 它探索得太少。「需要知道 Δ」与 UCB 一样不需要。
知识点 4 · 总结
核心结论
共轭：Beta 先验 + 伯努利观测 ⟹ 后验还是 Beta。更新退化成 α 加一（见到 1）或 β 加一（见到 0） —— 不需要积分或优化。
底层机制
Beta(1,1) = 均匀分布，即「假装见过一个 1 一个 0」。不确定性装在分布里：α+β 越大分布越尖，收缩不需要单独设计。
常见误解
误解：「α、β 要拟合」。它们是数出来的。转录稿有一字之差的坑：「we update the first parameter, also the second」—— 应是 otherwise，恰好一个递增。
与你的考试
代价是模型假设：共轭族不普遍存在，复杂似然要回到采样/变分。记号撞车：β 在前半讲是 Beta 的参数，在后半讲是 MBIE-EB 的加成常数，毫无关系。
知识点 4 · 检验
Beta-Bernoulli 共轭为什么让贝叶斯老虎机在计算上可行？
共轭的定义就是「先验与后验同族」：Beta(α,β) 观测到 1 变 Beta(α+1,β)，观测到 0 变 Beta(α,β+1)。更新是整数加一，没有积分、没有优化、没有重新拟合。α、β 就是见过多少个 1 / 多少个 0 的伪计数。「正态近似」不需要，且在小样本时正是它不可靠的地方。「方差有闭式」是事实但不是关键 —— 关键是更新的代价。「后验只有两种」是事实错误：后验是 [0,1] 上的连续分布。
知识点 5 · 总结
核心结论
P(选 a) = P(a 是最优臂 | 数据)。三种臂自动各得其所：明显最好的→概率≈1；没试过的→后验宽、概率不小；明显糟的→概率≈0 但非零（保留翻案可能）。
底层机制
对照：ε-贪心给坏臂固定的 ε/|A|；UCB 给它恰好 0；概率匹配给它一个随证据收缩的小数。
常见误解
误解：「按后验均值比例选」。那又把形状扔了 —— Beta(4,2) 与 Beta(40,20) 均值相同，集中程度却差很远。
与你的考试
正确 ≠ 可执行：这个概率是 m 维积分，三个臂就没有好用的闭式。想法从 1929 年左右就有（讲座把 Thompson 说成 1920 年代，论文实为 1933）。
知识点 5 · 检验
概率匹配这条规则的问题在哪里？
这条规则把整个后验都用上了，三类臂自动各得其所 —— 问题不在规则，在执行：P(a 是最优) 要对所有臂的参数做联合积分，被积函数是「θ_a 恰好最大」的指示函数，三个臂起就没有好用的闭式。「概率太大」反了 —— 它给坏臂的概率随证据收缩，比 ε-贪心那个固定的 ε/|A| 小得多。「需要真实均值」不对，只用后验。「只在两臂有定义」定义对任意 m 都成立，难的是算。
知识点 6 · 总结
核心结论
四步：从后验抽一组 θ → 假装是真的 → 贪心 argmax → 更新。没有置信区间、没有奖励加成、没有 δ、没有积分。
底层机制
为什么恰好相等：中选 ⟺ 它抽到的 θ 最大 ⟺ 它是最优臂 —— 同一个式子。抽样把「算出概率」换成了「按这个概率掷一次骰子」，而后者正是我们要的。
常见误解
误解：「抽样是在近似那个积分」。不是。40 万次验证：TS 频率 0.6979/0.2404/0.0617 vs 最优概率 0.6975/0.2398/0.0627，差异只是抽样噪声。
与你的考试
实测断脚趾（Beta(1,1) 先验）UCB/TS 遗憾比：2.73 → 4.08 → 6.91 → 11.14 倍。但这是这个实例、这个先验下的结果，不是普遍定理。转录稿：「select theta as 0.6」应为选那个臂 —— 参数是抽的，动作是选的。
知识点 6 · 检验
Thompson 采样与概率匹配是什么关系？
臂 a 中选 ⟺ 抽出来的 θ_a 最大 ⟺ 它是（后验意义下的）最优臂 —— 同一个事件，同一个概率。关键是：那个积分难算是因为要求出概率的数值，而 TS 只需要让这个事件按它本来的概率发生一次，抽样正好做到这件事。40 万次验证两行数字逐位吻合。「抽得越多越准」误解了 —— TS 每步只抽一次，且不估计任何概率。「更保守的变体」没有这层关系。「属于频率派」反了，它建立在后验之上。
知识点 7 · 总结
核心结论
以概率 1−δ，除了多项式多步之外，每一步选的动作都是 ε-最优的。三个部分分别对应 Probably / Approximately / Correct。且这个上限事先可算。
底层机制
同一组事实两把尺子：1000×0.01 与 10×1.0，遗憾都是 10；换成 ε=0.1 的大错计数，是 0 对 10。
常见误解
误解：「遗憾已经够用了」。遗憾内建了损失可互相抵偿的假设 —— 把伦理问题折算成了算术问题。
与你的考试
两者分工：损失能抵偿用遗憾（老虎机主流），不能抵偿用 PAC（MDP 更常用）。好消息：PAC 算法大多就建立在乐观或 Thompson 采样上。讲座举例时用了 0.9 vs 0.95 这个边界情形（ε 须 ≥ 0.05）。
知识点 7 · 检验
PAC 判据相对累积遗憾，多回答了什么问题？
1000 人各亏 0.01 与 10 人各亏 1.0，累积遗憾都是 10，完全分不开；换成 ε=0.1 的「非小错误计数」是 0 对 10。遗憾内建了「损失可加可抵偿」的假设，在严重副作用这类场景下不成立。PAC 还有一个实用性质：错误步数的上限事先可算。「更紧的上界」不是同一个量。「不需要知道最优策略」两者都只在分析里用到最优策略。「对随机性要求更弱」PAC 里同样有 1−δ 的高概率语句。
知识点 8 · 总结
核心结论
乐观初始化把 Q₀ 设成 R_max/(1−γ)，但它是一次性的：Q 值降下去再也不会自己回升。UCB 的奖励项会随 log t 重新变宽 —— 这才是能翻案的原因。
底层机制
Even-Dar & Mansour (2002)：PAC 需要 R_max/((1−γ)·Πα_i)。α=0.1 时倍数是 10^T：T=5→10⁵，T=10→10¹⁰，T=20→10²⁰。
常见误解
误解：「乐观初始化 = MDP 版的 UCB，有保证」。它是好用的启发式，不是定理 —— 同 L10「TRPO 不是那条定理的实现」。
与你的考试
口误方向错：讲座说「乘以学习率」，乘以 <1 的数只会变小；正确是除以学习率之积（讲座自己算的 (1/0.1)^T 就是证据）。记号混用：Jin 等人的结果是有限时域 episodic（参数 H），讲座通篇用折扣记号。
知识点 8 · 检验
为什么乐观初始化本身不足以给出 PAC 保证？
UCB 之所以必然回头，是因为它的奖励项对没被访问的对会随 log t 重新变宽（L11 第九集）。乐观初始化没有这个机制：降下去就回不来，几次不走运的采样就能把一个对永久压低 —— 正是 KP3 那个确认偏误换了个地方出现。要补上保证，Even-Dar & Mansour 需要的初始值含 10^T 量级的因子，写得出来用不了。「不是上界」它确实是折扣回报的上界。「不影响收敛点」是对的但答非所问 —— PAC 关心的是过程中犯多少大错，不是终点。「需要模型」Q 学习是无模型的。
知识点 9 · 总结
核心结论
四步：数 N(s,a) → MLE 拟合模型 → 奖励加 β/√N(s,a) → 当成真的去规划。乐观没消失，它从值的初始化搬到了奖励函数里，衰减率仍是 1/√N。
底层机制
β = (1/(1−γ))·√( ½·ln(2|S||A|m/δ) )。三块各有来历：1/(1−γ) 是有效时域，log 里的 |S||A| 是并集界（同 L11 第八集），½ 与根号来自 Hoeffding 反解（同 L11 第六集）。
常见误解
误解：「无模型更简单所以更好」。在探索的理论上反过来 —— 模型把「我对这里了解多少」显式记下来了，而 Q 值里看不出哪部分来自侥幸。
与你的考试
转录稿又丢根号：β 从 24.477 变成 119.829，差 4.9 倍。另一处：复杂度被说成「多项式于 γ」，实为 1/(1−γ) —— γ 有界而 1/(1−γ) 在 γ→1 时爆炸（10 / 100 / 1000）。
知识点 9 · 检验
MBIE-EB 的样本复杂度是哪些量的多项式？
讲座把它说成「多项式于 γ」，但真正的依赖是 1/(1−γ)（有效时域），以及 1/ε、1/δ。这个区别关键：γ 永远在 [0,1) 里有界，而 1/(1−γ) 在 γ→1 时爆炸 —— γ=0.9 是 10，γ=0.99 是 100，γ=0.999 是 1000。说成「多项式于 γ」会让人以为长时域是免费的。「指数」那是上一集 Even-Dar & Mansour 的 10^T，正是 MBIE-EB 要对照的反面。「与 γ 无关」β 里第一个因子就是 1/(1−γ)。