CSE 541 交互式学习 · 中文学习站

华盛顿大学 Spring 2025（Kevin Jamieson）。学习清单条目 1 的主体 —— 纯探索 bandit 是当前论文最硬的缺口。Jamieson 是 Hyperband 的作者之一，把 successive halving 用到超参搜索，和你的 multi-fidelity 框架同源。

⚠ 这门课的讲义是累积快照：一个主题跨两次课时，老师第一次课后发一版、第二次课后发完整版，后者包含前者。实测三对：L08⊂L09、L11⊂L12、L17⊂L18 —— 三讲都不必单独做。⚠ 比对要看内容不能只看像素：同一页加了板书，像素就不同，但内容是被包含的。做精读之前先查这一条，否则会重复劳动。

精读左讲义右讲解，一次一页，带自测与错题本 讲义原始讲义（排版骨架 + 手写推导）
L01 课程概览 · 在线学习导论 · 指数权重20 条讲解 精读讲义
  1. 这门课的地图：四条线，和一本书
  2. 标准范式，和那个把全课问出来的问号
  3. 可实现情形的设定：两个风险，一个 argmin
  4. 可实现情形的定理：log(|ℋ|/δ)/n，以及 PAC 这三个字
  5. 证明：并集界 + 一个指数不等式，两件工具而已
  6. 从「高概率」到「期望」：一个积分技巧
  7. 不可知情形：去掉完美假设，快率掉成慢率
  8. 干净版与期望推论：√(8log|ℋ|/n)
  9. 插值：用 Bernstein 换 Hoeffding，把两档界统一起来
  10. 无限类：三条出路，和它们共同的那件事
  11. 转折点：把独立同分布这条假设摘掉
  12. 独立同分布下：跟随领先者就够了，犯错数只按 log(T)·log(|ℋ|) 长
  13. 对抗下：同一个策略会犯 min{|ℋ|, T} 次错
  14. 减半算法：每错一次砍掉一半
  15. 小结，然后换一个目标：从犯错数到遗憾
  16. 两条遗憾界并排：不作假设的那条，常数反而更小
  17. 专家预测：把「跟谁学」变成一个在线决策问题
  18. 指数权重：势函数两头夹，六行出一个 √(T log d)
  19. 为什么要换成凸的：前面那两个算法都算不动
  20. 在线梯度下降：一步更新，一个定理，两项取舍
L03 在线梯度下降 · 通用投资组合17 条讲解 精读讲义
  1. 前 8 页是上一讲的原样重放：这里只有两笔新的手写
  2. 一个把后半门课撑起来的问题：什么时候优化是容易的？
  3. 凸集：一句话定义，和讲者当场画弦的那六个例子
  4. 凸函数：弦永远在函数上方，和六条曲线的当场判定
  5. 上图：把「函数凸不凸」整个翻译成「集合凸不凸」
  6. 一阶定义：站在一点只看一个梯度，就得到对全空间的下界
  7. 为什么关心凸性：两条理由，和非凸时那三种可能
  8. 两条路都堵死了：不改算法，改目标
  9. 在线梯度下降：一行更新，一个定理，和讲者补写的投影定义
  10. 证明：四行，三件工具，凸性只进场一次
  11. 把钱分到 d 只股票上：一个内积，和 Markowitz 那个 1952 年的答案
  12. 一张真实的价格图，和图上那支指着关税的红箭头
  13. 连乘变连加：取一次对数，整套在线学习的机器就能开动
  14. VOO 与 RSP：同样 500 只股票，两种权重，基准不是抽象的
  15. 算法原样搬来，定理里却没有 T：log(d)，与玩多久无关
  16. 证明：和 p8 逐行对照，差别只有中间那一步——而那一步从不等式变成了等式
  17. 自曝其短：两只股票就能说明「最好的单只股」是个弱基准
L04 通用投资组合 · 连续指数权重 · 极小极大分析11 条讲解 精读讲义
  1. 整段重放在线梯度下降：这次要带着一个具体的问题读
  2. 整段重放通用投资组合：这次盯住那个还没兑现的 max
  3. 半页手写的预告：两个比 √T 更会说话的遗憾界
  4. 给上一讲的定理加三笔批注：凸性、顶点、以及它的乘法形式
  5. 重放证明与那个反例：这次是为了紧接着回答它
  6. 整讲最硬的一页：同一批损失，两套算法，d 与 log d 的差别从何而来
  7. 连续指数权重：把 d 个权重换成一整片测度
  8. 证明：把基准周围缩出一小片体积，log(体积比) 就是那个 d log T
  9. 特化到投资组合：1 + d log T，终于兑现了那个 max_{p∈Δ_d}
  10. 极小极大分析开场：先要把「同时出手」这件事写进式子里
  11. 收尾：在线学习的极限，就是这个假设类的 Rademacher 复杂度
L05 集中不等式 · 多臂老虎机开篇9 条讲解 精读讲义
  1. 两枚硬币：整门课最小的那个问题
  2. 推广到 K 条臂，以及真正要回答的那个问题
  3. Markov 不等式：一行证明，但它是所有尾界的祖先
  4. Chebyshev 与 Chernoff：把 X 换成增长更快的东西
  5. Chernoff 的证明：六行，每一行都值得认一遍
  6. 算一个具体的 ψ：高斯，然后对 λ 取最优
  7. 反解出半径：√(2log(1/δ)/n)，你一直在用的那个数
  8. sub-Gaussian：不是高斯，但被高斯压得住
  9. 合起来用一次：两臂的遗憾界，以及它的两种读法
L06 逐次淘汰：遗憾分解、好事件、以及两个配套下界6 条讲解 精读讲义
  1. 遗憾分解：把「后悔多少」拆成「每条臂差多少 × 拉了多少次」
  2. 逐次淘汰：拉够次数，再砍掉明显差的
  3. 好事件 ℰ：让估计对所有轮同时成立，于是最优臂永不被淘汰
  4. 差距大于 4ε_ℓ 的臂，这一轮就会被砍掉
  5. 遗憾上界的证明：把存活轮数换算成拉臂次数
  6. 从高概率界到期望界，以及两个配套下界
L07 线性 bandit 与实验设计6 条讲解 精读讲义
  1. 把「拉臂」换成「测量」
  2. 误差就是一个加权的噪声和
  3. 单臂的界，和推荐臂的两步夹逼
  4. A(λ)：把「拉了哪些臂」变成一个分配
  5. 四种最优性，与 Kiefer–Wolfowitz
  6. 把最优设计塞进逐次淘汰
L08 有限臂的线性 bandit7 页课件 精读讲义
还没有中文讲解。
L09 淘汰算法的遗憾界 · <b>纯探索</b> · Thompson 采样11 条讲解 精读讲义
  1. 换一个问法：不问「一路亏多少」，问「最后选得对不对」
  2. 误差长什么样：θ̂ − θ* 是噪声的一个线性函数
  3. simple regret 的界：两次「加减同一项」，一次 G-最优
  4. 设计测度 λ：把「拉哪些臂」变成一个凸优化的变量
  5. Kiefer-Wolfowitz：G-最优设计的最优值恰好是 d
  6. 取整那一步的代价，以及又一次 Basel
  7. 线性版的逐次淘汰，以及随机集合带来的新麻烦
  8. 线性版的遗憾界：√(dT) 而不是 √(nT)
  9. BAI 的判据：要控的是<b>差方向</b>上的不确定度
  10. 那张三条臂的图：该测的东西，不等于该用的东西
  11. ρ*：上界与下界在同一个量上对齐
L10 线性 UCB4 条讲解 精读讲义
  1. Lin-UCB：乐观主义搬到线性模型上
  2. 乐观性链条与单步遗憾：Cauchy-Schwarz 把误差拆成两半
  3. 把单步界加起来：先 Cauchy-Schwarz，再看多臂特例
  4. 椭圆势引理：行列式只能涨这么多，所以信息只有这么多
L11 鞅型置信界 · 混合法5 页课件 精读讲义
还没有中文讲解。
L12 鞅型置信界 · 混合法（续）13 条讲解 精读讲义
  1. 承上：臂集无限时，用覆盖把 sup 换成有限个点
  2. 覆盖论证收尾，然后从零搭概率空间
  3. 条件期望：为什么要绕这么大一个圈子定义它
  4. 滤流与鞅：把「信息随时间增加」写成数学
  5. 指数鞅：减掉 λ²/2 把下鞅压成上鞅
  6. 停时、可选停止、极大不等式
  7. ★ 随时有效的界：一条直线罩住整条轨迹
  8. 和固定时刻的 Chernoff 对照，然后混合法登场
  9. 混合法算出来：弯曲的边界，和那两张对照图
  10. 可预测的方差：把 t 换成 V_t
  11. 向量版：自归一化界与白化图
  12. 在线线性回归：把那套机器接到岭回归上
  13. 置信椭球与 LinUCB
L14 对抗式 bandit · EXP35 条讲解 精读讲义
  1. 对抗设定：把「分布」这个假设整个拿掉
  2. 重要性加权：无偏是免费的，方差不是
  3. EXP3：指数权重 + 重要性加权 + 强制探索
  4. 调参：三项配平，得 √(12 nT log n)
  5. 势函数：把 log(W_{T+1}/W_1) 夹在两边
L16 <b>下界</b>10 条讲解 精读讲义
  1. 一切下界的原型：两点之间要几个样本才分得开
  2. Pinsker 与似然比检验
  3. SPRT 与 Wald 恒等式：T ≈ log(1/δ) / KL
  4. 极小极大下界：造一对「几乎一样、但答案相反」的实例
  5. 收尾：Pinsker 上场，以及散度分解引理
  6. 散度分解的证明：策略项约掉了
  7. 最优臂识别：δ-正确，和为它定制的对手实例
  8. 数据处理不等式：把「答对答错」挤进 KL
  9. BAI 下界定理，与重对数律
  10. 渐近的实例相关遗憾下界
L17 非随机线性 bandit · 上下文 bandit 导论5 页课件 精读讲义
还没有中文讲解。
L18 一般策略类的上下文 bandit（model-free）16 条讲解 精读讲义
  1. 把 EXP3 从「n 条臂」搬到「指数多个组合对象」，缺的只有一个损失估计量
  2. 线性情形的损失估计量：用 A(q)⁻¹ 把一次观测摊回到所有臂上
  3. 两条臂的例子说清 LS 与 IPS 的差别；再用 G-最优设计把 −ηℓ̂ 压到 1 以下
  4. γ = ηd：一个让两条假设同时成立的取法，以及方差项为什么是 dT/(1−γ)
  5. 上下文 bandit 的两个极端：每个上下文各学各的，还是干脆不看上下文
  6. 策略遗憾：把「基准」从一条臂换成一整个策略类，于是 |Π| 只进 log
  7. 同一份定理第二次使用：把 EXP3 开在策略上，估计量的分母换成「混合倾向」
  8. 无偏性：分母逐字就是 P(a_t = j)，于是全概率公式把它整块约掉
  9. 策略版的 Kiefer–Wolfowitz：min_λ max_i Σ_j p_{i,j}/(Σ_k λ_k p_{k,j}) 恰好等于动作数 d
  10. 把命题收口（取 λ = e_i），以及第二矩项又一次塌成 dT/(1−γ)
  11. 换成离线：日志里必须当场记下倾向 p_t，否则这一整段全都做不了
  12. 方差由 E[1/μ(π(c)|c)] 掌管，而重尾让「方差小」不等于「集中」——所以要 Bernstein
  13. C_T(π)：一个逐策略的置信宽度；以及「离线挑策略」原来是一个加权分类问题
  14. 归约到分类：用现成的 softmax 交叉熵去解它；再把 MLE 的保证推一遍
  15. 悲观原则：把置信宽度减进目标里，代价就从「最坏策略」变成「最优策略」
  16. 优化者的诅咒：argmax 一个有噪声的估计，估计值会系统性虚高
L20 一般函数类的上下文 bandit（model-based）5 条讲解 精读讲义
  1. 两种范式的真正差别不在遗憾的形状，在「拿什么当基准」和「要不要假设可实现」
  2. 线性情形：LinUCB，一个「置信椭球 + 乐观」的标准件，d√T 而不带 |𝔉|
  3. 把 UCB 推广到一般函数类 —— 构造是自然的，但页末那一行说它被证明不行
  4. 反例：把答案藏在「索引的比特串」里，UCB 会去逐个试 2^m 个索引
  5. SquareCB：不要置信集，只要一个平方损失的在线回归器；概率与「差距」成反比