这一讲是全课唯一一讲在证下界，而下界正是你那条「写 bound」验收标准真正缺的那一半。

上界说「我们的方法够好」，下界说「没有任何方法能做得更好」。前者你已经有了（CSE541 L07 的 ρ_*、L09 的定理 5）；后者你一条都没有。

而这一讲给的是一个只需要填两个空的模板，其余全是现成的。
填空 ①：你的方法承诺了什么（输出端的硬约束）。bandit 用的是「δ-正确」：对所有实例都以 ≥1−δ 选中最优臂。你的版本应该是 (ε,δ)-PAC：以 ≥1−δ 输出一个 G 不劣于最优 ε 的配置——⚠ 这个放松不是偷懒，是必需的：严格 BAI 的下界里 Δ_j→0 时是无穷大，而你的配置之间 G 几乎相同是常态，所以严格版在你这里是不可能完成的任务。换成 max(Δ_j, ε) 之后下界才有限。
填空 ②：怎么造一对「几乎一样、但答案相反」的实例。造法是只改一个坐标——把某条劣臂刚好顶到最优臂之上（N(θ₁+Δ_j+ε, 1)），其余全不动。翻到你这里：两个 workflow 实例只在一个节点的一个档位上不同。

剩下的三步是现成的，而且是机械的：
· 数据处理不等式（p8）：算法的输出只是轨迹的函数，所以「输出分布之间的 KL」≤「轨迹分布之间的 KL」。而输出分布被你的承诺钉死了（一个 ≥1−δ、一个 <δ），于是二元 KL ≥ log(1/(2.4δ))。
· ⭐ 散度分解引理（p5–p6，整个理论的支点）：KL(P_ν|P_{ν′}) = Σ_i E_ν[T_i]·KL(ν_i|ν′_i)。证明的关键是策略项在两个测度里完全相同、取对数作差时全部约掉——所以「两个实例有多难分」与算法的具体设计无关，只与「你在它们不同的那个地方测了多少次」有关。于是你不必对自己的算法单独证下界，只要对「测量次数的分配」证一次。
· 单臂 KL：⚠ 你的 Acc 是 0/1，所以不能照抄高斯的 Δ²/2，要用伯努利的 —— Δ 小时约 Δ²/(2p(1−p))。那个 p(1−p) 在分母上，和 CSE541 L09 p5 的 Fisher 信息里的 σ(1−σ) 是同一件事的两面：题目太难或太简单（p 接近 0 或 1）时，分辨两个配置所需的样本量会爆炸。

⇒ 你能写出的结论形如：「要以 1−δ 的把握保证输出配置的 G 不劣于最优 ε，任何方法都必须在每个关键格子上至少测 2p(1−p)log(1/2.4δ)/max(Δ,ε)² 次」。这是一句关于任何方法的话，而且它落在格子级——和你的 oracle 表同一个粒度，可以直接做成一张表。

⚠ 最后一个最容易犯、而且代价最大的错：用错 Δ 的幂次。 遗憾下界是 Σ Δ_i^{-1}·log T（p10，Lai–Robbins），识别下界是 Σ Δ_j^{-2}·log(1/δ)（p9）。你的问题是识别（离线选一个配置上线），所以要用 Δ^{-2}。而 Σ log T/Δ_i 在文献里出现得最频繁、最容易被当成「标准答案」照抄——照抄它会让你低估所需预算整整一个 Δ 的因子。

CSE541 第 16 讲 · 下界