我在 L16 主线卡里提出过一条需求：自适应淘汰必须用「随时有效」的界，否则一边跑一边看、一达标就停，实际失败概率会远高于名义的 δ。这一讲就是那套机器，而且它给出的答案比我当时推荐的更好。

最该带走的一句话：「随时有效」几乎是免费的。 p8 的对照很干净——取 λ = √(2log(1/δ)/n) 之后，那条直线边界在 t ≤ n 上给出的右端是 √(2n·log(1/δ))，与固定时刻 Chernoff 一模一样；区别只在左边：Chernoff 只管 t = n 这一个时刻，而它管 t = 1…n 的最大值。不是近似相同，是同一个数。

⇒ 于是选哪条界成了一个三档的工程决定，而 p9 那两张排版图把它们画在了一起：
· ① 最省事：δ/(2ℓ²) 并集界 + Basel 求和（本课 L06/L07 一直在用，也是我先前推荐给你的）。⚠ 图 (b) 显示它就是那条「union bound 2t²」，一路在最上面，最松。
· ⭐ ② 最紧且几乎免费：直线边界，λ = √(2log(1/δ)/n_目标)。只要你大致知道会跑多少 query，它在那附近和固定样本量的 Hoeffding 一样紧。你的预算是事先定的，所以 n_目标 你知道 ⇒ 这多半是你的最佳选择。
· ③ 不想猜 n：混合法的弯曲边界（对 λ 取高斯先验再平均，有闭式）。形状是 √(t·log t)，比 ② 多一个 √(log t) —— t=1000 时约 2.6 倍的区间宽度，折算成样本量约 7 倍。不小，所以能猜就猜。

而「可预测」这个条件（p10–p12）解决了你一个一定会被问到的麻烦：自己挑的样本，置信界还成立吗？ 你的配置是自己挑的（一步偏离扫描、逐次淘汰都在挑），所以观测不是 i.i.d.。而这套界只要求 Σ_t = x_tx_tᵀ 可预测——「挑 x_t 时只用历史」，而在线算法天然满足（你不可能先看结果再选动作）。⇒ 你可以一边自适应地选配置、一边保持置信界有效，而这在固定设计的框架里做不到。

另外两样可以直接用上的。
· V_t 而不是 t（p10）：界按累计方差而不是步数增长。你的 Acc 是伯努利的、方差是 p(1−p)，而「全对/全错」的 query 方差接近零——⇒ 用 V_t 版的界，那些没信息的 query 自动几乎不加宽区间，不需要你显式去筛。（显式筛仍然要做，那是省真实的 API 调用；两件事不冲突。）
· 置信椭球与 LinUCB（p13）：UCB_t(x) = ⟨θ̂_t,x⟩ + β_t‖x‖_{(V_t+γI)^{-1}}。而 ‖x‖_{A^{-1}} 正是 L07 的 G-最优设计要最小化的那个量——两讲在这里合流：L07 问「怎么分配测量使它小」，本讲问「怎么用它算区间」。

⚠ 但别把 UCB 当成选测哪个的规则。 L09 p12 说过：UCB/Thompson 是为遗憾最小化设计的，它们把样本集中在「看起来好」的臂上；而你要的是识别，该按 CS234 L16 p47 的信息价值分配。同一个 ‖x‖_{A^{-1}}，一个拿去算区间（用），一个拿去选动作（不用）——别混。

CSE541 第 12–13 讲 · 鞅型置信界 · 混合法（续）