这一讲是你昨天在 CS234 L16 p47 读到的那条直觉的严格版本。

p47 说：老虎机用乐观是因为你真的要承受坏决策的代价，而在离线筛选里「做坏决策不疼」，所以该按信息价值花预算、而不是按「谁现在看起来最好」。那一页给的是直觉和一个反例；这一讲给的是最优解——G-最优设计：选分配 λ 使 max_{x∈𝒳} xᵀA(λ)^{-1}x 最小，而 A(λ) = Σ_x λ_x x xᵀ 就是「每条臂占多少比例的预算」所决定的信息矩阵。两者并排写进论文很有力：一句直觉 + 一个有定理的解。

三个数决定了它对你有多大用。
① f_G(λ*) = d（Kiefer–Wolfowitz 1960）——最优值恰好等于维数，与臂数 n 无关。代回去，推荐臂的简单遗憾是 ≲ 2√(d·2log(2n/δ)/T)：臂数只进 log。
② support(λ*) = d(d+1)/2——最优设计只在至多 d(d+1)/2 条臂上放质量，不管 |𝒳| 有多大。这是对「2^H 个配置怎么办」最直接的回答：你不需要测遍，你需要测对。
③ λ* 的计算不需要任何真实奖励——它只依赖配置集合的几何。所以在花掉第一个 API 调用之前，你就能把「每个配置该占多少预算」算出来。这和 L16 p13 那条「λ 扫描免费」是同一类免费午餐：凡是只依赖已知结构、不依赖测量结果的，都可以离线算。

而它要成立，前提只有一条：G(x) = xᵀθ*，即 G 对配置是线性的。 把配置写成指示向量 x ∈ {0,1}^{H×k}（节点 i 选了档位 j 就置 1），那么「成本可加」字面上就是 Cost(x) = xᵀc——成本那一半精确地是线性 bandit，d = H×k 只有几十，而臂数是 2^H。准确率那一半不保证线性，但线性是一个可检验的一阶近似。而检验它的实验你已经有了：L16.a p18 那个「用 k=1 的数据预测 k=2 的 G，与真值比」——那个实验现在的分量比昨天更重了：它不只决定「该不该合并统计」，还决定「能不能用最优设计省掉绝大部分穷举」。

算法骨架（p6）可以直接照抄，它就是你那套「扫描 + 逐次淘汰」多加一步：① 在当前存活的配置集合上算 G-最优分配（免费）；② 按它把这一轮的 query 预算分下去；③ 用这一轮结果估 G；④ 砍掉劣于最优者超过 2ε_ℓ 的；⑤ ε 减半、预算翻四倍，下一轮。多出来的只有第 ① 步，而它不花钱。

CSE541 第 7 讲 · 线性 bandit 与实验设计