遗憾、赌博机与理论保证

第 12 章介绍了一系列采集函数，每一种都合理地回答了下一步该在哪里评估的问题。要在其中做出选择，或者提出新的采集函数，就需要有办法判断一个优化器优于另一个。通常的做法是绘制基准测试图：在若干测试函数上，画出已找到的最优值随评估次数的变化。后续章节也会使用这类图。本章要求更可靠的依据：一个对任何问题都有定义的分数，以及关于这个分数的结论，这些结论对某一明确类别中的每个问题都成立。

这个分数称为遗憾（regret）。遗憾的理论最初围绕一个比贝叶斯优化更简单的问题发展起来，即多臂赌博机：赌徒面对几台回报率未知的赌博机，反复选择拉动哪一台。赌博机问题只保留了第 11.3 节中探索与利用权衡的最基本结构。在这一设定下，可以统计算法做了多少探索，证明最好的算法的探索次数只按对数增长，并证明任何算法都无法探索得更少。随后再把这套分析推广回函数：高斯过程把无穷多条相关的臂化为复杂度可以度量的问题，GP-UCB 算法的界就用这一复杂度表示。

即使跳过证明，也建议读者阅读最后一节。遗憾界是关于理想化问题的精确论断，对实践有一些有用的启示，对另一些问题则无从回答；借助本章的图，读者可以看到界与算法的实际表现可能相差多远。

13.1 为优化器打分 #

设想两个优化器都在第 11 章中贯穿全书的示例目标函数上运行。第一个把大部分评估用在较高的峰附近；第二个在大部分预算内遍历整个定义域，最后推荐了同一个峰。哪一个更好？这取决于沿途的评估除了本身的花费之外是否还有其他代价，即关心的是整个旅程，还是只关心终点。两种遗憾分别把这两种回答精确化。

考虑在定义域 $\X$ 上最大化未知函数 $f$。与式（11.1）相同，记最优值为 $f^\star = \max_{\vx \in \X} f(\vx)$，取到最优值的某个输入为 $\vx^\star$。优化器依次在 $\vx_1, \vx_2, \dots$ 处评估 $f$（可能带噪声），$T$ 次评估后推荐一个输入 $\hat\vx_T$，通常取观测到的最好输入，或后验均值的最大值点。

遗憾按所选输入处的真实 $f$ 计算，而不是按带噪声的观测值计算。优化器不知道 $f^\star$，因此永远无法算出遗憾。遗憾是供分析者使用的分数：在最大值已知的基准问题上可以计算，定理所界定的也正是这个量。

每个 $r_t$ 都不超过 $f$ 的取值范围，所以累积遗憾至多随 $T$ 线性增长。从不学习的优化器，例如始终均匀随机查询的优化器，累积遗憾确实线性增长：每次评估的平均损失相同。若优化器的累积遗憾次线性（sublinearly）增长，即增长得比任何直线都慢，从而平均遗憾 $R_T / T$ 趋于零，则称该优化器是无遗憾（no-regret）的。形如 $R_T \le C\sqrt{T}$ 的界意味着平均遗憾按 $1/\sqrt{T}$ 下降；形如 $R_T \le C \log T$ 的界意味着后期几乎所有评估都用在接近最优的输入上。

累积遗憾的界同时界定了已访问的最好输入的简单遗憾。$T$ 个数中的最小值不超过它们的平均值，因此

累积遗憾的界正是通过这种方式转化为优化的收敛速率（Srinivas 等，2010）。这里有两点需要注意。第一，观测带噪声时，优化器不知道评估过的输入中哪一个的 $f$ 最大，因此访问过的最好输入不等于优化器能识别出的最好输入；最终报告什么，本身就是一个实际问题（第 14.2 节）。第二，反之不成立：均匀探索的优化器可以有很小的简单遗憾，同时累积遗憾线性增长。在下一节的赌博机问题中，这一差别十分明显。在固定的问题上，均匀探索的简单遗憾随预算呈指数下降；而保持累积遗憾较低的算法会尽早停止对接近最优的竞争者采样，其简单遗憾只按多项式速度下降（Bubeck 等，2009；Lattimore 与 Szepesvári，2020，第 33 章）。

选用哪个分数，取决于由谁承担评估的代价。为模型做超参数优化或搜索新材料时，只有最终推荐会被采用；沿途的评估只是以算力或实验时间计量的成本，此时简单遗憾是合适的分数。在线实验中，每次评估都是展示给真实用户的一个产品变体；偏好研究中，每个选项都需要一个人去看、去穿戴或去听；此时过程本身很重要，合适的分数是累积遗憾。第 19.6 节介绍了一种偏好方法，其最终答案更好，累积遗憾却是竞争方法的 2.5 倍以上（Xu 等，2024b）。

最后一个区别在于界针对的函数范围。频率派（frequentist）界对某一明确类别中的每个函数都成立，例如具有给定光滑度的全部函数。贝叶斯（Bayesian）界则对从先验中抽取的函数在平均意义下成立，或以高概率成立。两种界在第 13.4 节中都会出现。

13.2 多臂赌博机 #

要统计探索的次数，需要一个足够简单、便于计数的设定，多臂赌博机（multi-armed bandit）正是如此。设有 $K$ 个动作，因赌博机的拉杆而称为臂（arm）。拉动臂 $i$ 得到随机奖励，其分布固定但未知，均值为 $\theta_i$。玩家每轮拉动一条臂，共 $T$ 轮，目标是使总奖励最大。这类问题最早的规则由 Thompson 于 1933 年提出（Thompson，1933）；1952 年，Robbins 将其作为实验序贯设计中的一个问题正式表述，并引入了遗憾的概念（Robbins，1952；Lattimore 与 Szepesvári，2020，第 4 章）。

赌博机可以看作做了两处简化的贝叶斯优化：定义域是 $K$ 个输入组成的有限集合，且这些输入互不相关，拉动臂 3 不提供关于臂 4 的任何信息。其余要素全部保留，包括噪声、预算，以及两种做法之间的权衡：继续尝试看似最好的臂，或检查其他可能更好的臂。

本节中每次奖励都相当于抛一次硬币：拉动臂 $i$ 以概率 $\theta_i$ 得 1，否则得 0。记最优臂的均值为 $\theta^* = \max_i \theta_i$，臂 $i$ 的差距（gap）为 $\Delta_i = \theta^* - \theta_i$，即每次拉动该臂而非最优臂时的平均损失。（本节中 $\theta_i$ 表示臂的平均奖励；符号 $\mu$ 仍专用于高斯过程的后验均值。）

赌博机算法的遗憾，就是以各臂均值代替 $f$ 的累积遗憾：$R_T = \sum_{t} (\theta^* - \theta_{a_t})$，其中 $a_t$ 为第 $t$ 轮拉动的臂。这一定义使用的是均值，而非实际的抛硬币结果，因此有时也称为伪遗憾（pseudo-regret）。记 $N_i(T)$ 为前 $T$ 轮中臂 $i$ 的拉动次数，将求和按臂分组，得到

这一分解把问题化为记账：遗憾等于每条较差臂的拉动次数按其差距加权之和。算法要保持低遗憾，就应少拉坏臂；但只有拉动一条臂，才能知道它是坏臂。整个领域研究的就是一个问题：拉动多少次才够。

在介绍算法之前，读者可以先亲自尝试。下图隐藏了五条臂的回报率，共有 50 次拉动机会。

多数读者在每条臂拉动两三次之后，就已有了偏爱的臂。读者是否回头拉过一条开局连输两次的臂？回报率在 0.15 至 0.6 之间时，最优臂连输两次的概率为 16%，因此这么早放弃一条臂，无异于一场赌博。下面的每个算法，都是针对这一决定的一条规则。

13.2.1 贪心与 ε-贪心 #

最简单的规则是贪心（greedy）：每条臂先各拉一次，之后始终拉动当前平均奖励最高的臂。贪心规则的失败方式颇具启发性。若最优臂第一次拉动恰好得 0，其平均值便为 0；只要某条较差臂的平均值为正，贪心规则就可能再也不拉动最优臂。这种情况以某个固定的正概率发生，一旦发生，遗憾将永远线性增长。

ε-贪心（epsilon-greedy）通过强制探索弥补这一缺陷：每轮以概率 $\varepsilon$ 拉动一条均匀随机选取的臂，否则拉动贪心臂。这样每条臂都会被拉动无穷多次，每个平均值都收敛到相应的均值。但这一补救要付出永不终止的代价。$\varepsilon$ 为常数时，每轮都有概率 $\varepsilon$ 用在均匀随机的臂上，每轮的期望遗憾因此增加 $\frac{\varepsilon}{K} \sum_i \Delta_i$，遗憾随之线性增长，斜率至少为此值（习题 13.1）。Auer、Cesa-Bianchi 与 Fischer 证明，若在第 $n$ 轮令 $\varepsilon$ 按 $\varepsilon_n = \min\{1, cK/(\Delta_0^2 n)\}$ 衰减，可以得到对数遗憾；但前提是 $\Delta_0$（原论文记作 $d$）是最优臂与次优臂之间差距的下界，而玩家并不知道这个值。在他们的实验中，没有任何一个 $c$ 值能在所试的全部奖励分布上都表现良好（Auer 等，2002）。

13.2.2 置信界从何而来 #

以固定比率强制探索，会不断拉动已知很差的臂。更好的规则只在关于某条臂的证据仍然薄弱时才探索它，为此需要一个数：拉动 $n$ 次后，这条臂的平均奖励与其均值可能相差多远？答案来自集中不等式（concentration inequalities），即平均值偏离均值超过给定距离的概率的界。本章的每个遗憾上界都以某个集中不等式为基础；选用哪个不等式，决定了据此构造的算法中的常数与对数项。

固定一条均值为 $\theta$ 的臂，设 $Y_1, \dots, Y_n$ 是它的 $n$ 个奖励，相互独立且都在 $[0, 1]$ 中，平均值为 $\hat\theta_n = \frac1n \sum_{s=1}^{n} Y_s$。问题是：对偏差 $a > 0$，尾概率（tail probability）$\Prob(\hat\theta_n \ge \theta + a)$ 可能有多大。下尾 $\Prob(\hat\theta_n \le \theta - a)$ 的处理方式相同，因此下面只讨论上尾。

Markov 不等式（Markov's inequality）。一个非负且均值很小的量，不可能经常取大值：如果它不小于 $c$ 的时间比例超过 $\E[Z]/c$，仅这些情形就会使其均值超过 $\E[Z]$。对 $Z \ge 0$ 与 $c > 0$，

证明如下：$Z$ 不小于 $c$ 乘以事件 $Z \ge c$ 的指示函数（事件发生时为 1，否则为 0），对两边取期望即得。平均值 $\hat\theta_n$ 非负，均值为 $\theta$，因此 $\Prob(\hat\theta_n \ge \theta + a) \le \theta/(\theta + a)$。对均匀硬币且 $a = 0.1$，这个界为 $0.83$，而且无论对多少个奖励取平均，它始终是 $0.83$。Markov 不等式只利用均值，而平均值的均值不随 $n$ 变化。

Chebyshev 不等式（Chebyshev's inequality）。补救的办法是把 Markov 不等式用于确实随 $n$ 缩小的量。偏差的平方 $(\hat\theta_n - \theta)^2$ 的均值为 $\Var[\hat\theta_n] = \Var[Y]/n$，因为独立项之和的方差等于各项方差之和（第 2.7 节），而和除以 $n$ 会使方差除以 $n^2$。事件 $\hat\theta_n \ge \theta + a$ 蕴含 $(\hat\theta_n - \theta)^2 \ge a^2$，因此

（Chebyshev 不等式同时界定两侧的尾部，因此也界定了每一侧。）对硬币，$\Var[Y] = \theta(1 - \theta)$，至多为 $\tfrac14$（第 2.6.2 节）。这个界现在按 $1/n$ 下降，但反过来用时代价很高。令右边等于目标失效概率 $\delta$，得宽度 $a = \sqrt{\Var[Y]/(n\delta)}$，它按 $1/\sqrt{\delta}$ 增长。赌博机算法需要非常小的失效概率，下一小节的算法在第 $t$ 轮要求小到 $t^{-4}$；宽度若按 $t^2$ 增长，每条臂都会永远留在考虑范围之内。实际情况要好得多。由中心极限定理，许多独立项的平均值近似服从高斯分布（第 4.1.2 节），而高斯分布的尾部随标准差个数 $c$ 按 $e^{-c^2/2}$ 下降，而不是按 $1/c^2$ 下降。

Chernoff 方法。把 Markov 不等式用于指数函数，就能体现这种行为（Lattimore 与 Szepesvári，2020，第 5 章）。对任意 $\lambda > 0$，事件 $\hat\theta_n - \theta \ge a$ 与事件 $e^{\lambda n(\hat\theta_n - \theta)} \ge e^{\lambda n a}$ 相同，而指数函数把平均值中的和变成积：$e^{\lambda n(\hat\theta_n - \theta)} = \prod_{s=1}^{n} e^{\lambda(Y_s - \theta)}$。独立因子之积的期望等于各因子期望之积，因为它们的联合分布可以分解（定义 2.8）。剩下的是对单个因子的界，提供这个界的条件有专门的名称。

均值为零、标准差为 $R$ 的高斯变量使上式取等号，因此这一条件的含义是：$Z$ 的尾部不比该高斯分布的尾部更重。有界变量也满足这一条件。由 Hoeffding 引理（Hoeffding's lemma），均值为零且始终落在区间 $[l, u]$ 中的变量是 $\tfrac12(u - l)$-次高斯的（Lattimore 与 Szepesvári，2020，第 5 章）。因此，$[0, 1]$ 中的奖励减去其均值是 $\tfrac12$-次高斯的；均值为零、绝对值从不超过 $\sigma$ 的噪声是 $\sigma$-次高斯的。（字母 $R$ 沿用下文所引论文的记法，与遗憾 $R_T$ 无关。）

在这一条件下，Chernoff 方法给出 Hoeffding 不等式（Hoeffding's inequality），这是 Hoeffding 针对有界随机变量之和证明的结果（Hoeffding，1963）：对 $[0, 1]$ 中的奖励，

反过来看，Hoeffding 不等式表明：以至少 $1 - \delta$ 的概率，平均值低于 $\theta + \sqrt{\ln(1/\delta)/(2n)}$。失效概率现在通过其对数进入宽度。把 $\delta$ 从 0.05 缩小到 $10^{-6}$，Hoeffding 区间的宽度变为原来的 2.1 倍，Chebyshev 区间则变为 224 倍。把同样的方法用于标准差为 1 的高斯变量 $Z$，得 $\Prob(Z \ge c) \le e^{-c^2/2}$；直接计算可将这个界减半（Srinivas 等，2010，引理 5.1），因此两侧尾部的总概率至多为 $e^{-c^2/2}$。这就是第 13.4.3 节中 GP-UCB 证明第 1 步所用的高斯界。

联合界（union bound）。算法用到的不止一个区间：每一轮、每条臂各有一个，其分析需要所有区间同时成立，至少需要统计区间失效的次数。所需的工具是初等的：若干事件中至少有一个发生的概率，不超过各事件概率之和，

因为任何一个事件发生的结果，在右边至少被计入一次。联合界对事件之间如何相互依赖没有任何要求。要使 $m$ 个区间以至少 $1 - \delta$ 的概率同时成立，只需给每个区间分配失效概率 $\delta/m$。利用 Hoeffding 不等式，宽度变为

因此区间的个数以加性的 $\ln m$ 出现在根号下。若用 Chebyshev 不等式，宽度会按 $\sqrt{m}$ 增长。正是指数型的尾部，使同时维持许多区间的代价可以承受。

赌博机算法中的对数正是由此而来。一个区间若要在时域 $T$ 内的每一轮都成立，需要 $m = T$，代价为 $\ln T$；每一轮为 $K$ 条臂各设一个区间，代价为 $\ln(KT)$。事先不知道时域时，可以把预算 $\delta$ 不均匀地分配，给第 $t$ 轮分配 $6\delta/(\pi^2 t^2)$。由于 $\sum_{t \ge 1} 1/t^2 = \pi^2/6$，各轮份额之和恰为 $\delta$；第 $t$ 轮的宽度中以 $\ln(\pi^2 t^2/(6\delta))$ 代替 $\ln(m/\delta)$，因此宽度按 $\sqrt{\ln t}$ 增长。GP-UCB 的 $\beta_t$ 就是这一构造，再对 $|\X|$ 个输入多取一次联合界（第 13.4.3 节）。下一小节的 UCB1 在第 $t$ 轮把每个区间的失效概率设为 $t^{-4}$。由 $e^{-2na^2} = t^{-4}$ 解出 $a$，得 $a = \sqrt{2\ln t / n}$，即式（13.9）中的加成项。指数 4 用于支付另一次联合：在第 $t$ 轮，参与比较的两条臂各自的拉动次数可以是不超过 $t$ 的任意值，次数组合约有 $t^2$ 种，而 $t^2 \cdot t^{-4} = t^{-2}$ 对所有轮次求和仍然有限。

样本量由数据决定时。Hoeffding 不等式讨论的是 $n$ 个奖励的平均值，其中 $n$ 在看到奖励之前就已固定。赌博机算法则根据已看到的奖励决定一条臂拉动多少次，开局不利的臂被拉动得更少。读者也许会问：每个奖励仍是如实抽取的，这是否有影响？确实有影响。抛一枚均匀硬币，一旦正面次数超过反面次数就停止。停止时的平均值总是大于二分之一，而且停止的可能性很大：100 次之内停止的概率为 0.92，1000 次之内为 0.97。对每个固定的 $n$，Hoeffding 不等式对前 $n$ 次的平均值依然成立；但对于看过抛掷结果之后才选定的 $n$，它不提供任何结论。

赌博机分析用联合界来弥补这一点。设想每条臂的奖励是开局之前就已抽好的一个列表，算法只决定每个列表读到第几项；这一模型赋予算法所见一切的概率与原问题相同（Lattimore 与 Szepesvári，2020，第 4.6 节）。对每个固定的 $n$，列表的前 $n$ 项是 $n$ 个独立的奖励，因此 Hoeffding 不等式对每个 $n$ 分别成立，再对 $n = 1, \dots, t$ 取联合界，就覆盖了算法实际达到的任何次数。这次联合就是上文的 $t^2$。它并非形式上的手续。若在每个次数上都使用单轮宽度 $\sqrt{\ln(1/\delta)/(2n)}$，取 $\delta = 0.05$，均匀硬币的区间在 1000 次拉动内至少失效一次的概率为 0.11，超过 $\delta$ 的两倍；在 10,000 次拉动内为 0.15，因为累计平均值的最大摆动缩小得比 $1/\sqrt{n}$ 稍慢（参见 Lattimore 与 Szepesvári，2020，习题 20.9）。若改用上文不均匀分配所得的宽度，1000 次拉动内的同一概率为 $8.5 \times 10^{-6}$：联合界是安全的，在这里还相当保守。（这些概率与上文均匀硬币的概率一样，都是逐次跟踪正面次数的分布精确算出的。）高斯过程的情形更难，因为每次评估都会改变各处的估计，权重又取决于算法选择在哪里观测；第 13.4.5 节给出处理这种情形的工具。

下图以硬币为例，把三个不等式并列比较。

可以尝试以下几点。

查看默认设置。对均匀硬币且 $a = 0.1$，抛 100 次平均值不小于 0.6 的概率为 0.028。Hoeffding 不等式给出的上界为 0.14，Chebyshev 不等式为 0.25，Markov 不等式为 0.83。读数给出每条曲线从多少次抛掷起保持在 0.05 以下：精确概率为 76 次，Hoeffding 界为 150 次，Chebyshev 界为 500 次，Markov 界则始终不能。

把标记移到 $n = 1000$。精确概率为 $1.4 \times 10^{-10}$，Hoeffding 界为 $2.1 \times 10^{-9}$，Chebyshev 界仍为 0.025。精确曲线与 Hoeffding 曲线以几乎相同的指数速率下降，两者之间的差距增长缓慢，从 $n = 100$ 时的约 5 倍增至 $n = 1000$ 时的 15 倍；Chebyshev 曲线在这样的坐标轴上是一条直线，只按 $1/n$ 下降。

把“对 T 个平均值取联合界”设为 1000。每个界都乘以 1000。Hoeffding 界现在从 496 次而不是 150 次起保持在 0.05 以下，多出 $\ln 1000/(2a^2) \approx 345$ 次；Chebyshev 界则从 500,000 次而不是 500 次起，是原来的一千倍。对 1000 个独立的平均值，精确概率需要 381 次。这就是式（13.8）中的 $\ln m$，只是从样本量的角度来看。

把“硬币的均值 θ”调到 0.1，并把“对 T 个平均值取联合界”恢复为 1。很少得奖的硬币方差为 0.09 而不是 0.25，其精确概率从 36 次起保持在 0.05 以下。利用方差的 Chebyshev 界改善到 180 次；Hoeffding 界只知道奖励落在 $[0, 1]$ 中，仍为 150 次，在 $n = 100$ 处给出 0.14，而精确值只有 0.002。同时利用方差的不等式（如 Bernstein 不等式）能弥补这一差距的大部分（Lattimore 与 Szepesvári，2020，习题 5.14）。

13.2.3 乐观：UCB1 #

更好的规则来自第 12.4 节中所说的面对不确定性时的乐观原则。对每条臂，根据其迄今为止的奖励，算出均值的合理上限，然后拉动合理上限最大的臂。经常被拉动的臂区间窄，合理上限接近其平均奖励。很少被拉动的臂区间宽，合理上限较为宽松，因此还会得到尝试。明显较差的臂，一旦区间收缩到最优臂的均值以下，就不再被拉动。

区间应取多宽？对取值于 $[0, 1]$ 的奖励，由 Hoeffding 不等式（式（13.6）），$n$ 个独立奖励的平均值 $\hat\theta_{i}$ 高估均值超过 $a$ 的概率至多为 $e^{-2na^2}$，低估的概率同样如此。在第 $t$ 轮选取宽度，使该概率等于 $t^{-4}$（理由见第 13.2.2 节），便得到 Auer 等人（2002）的 UCB1 规则：每条臂各拉一次之后，拉动

其中 $N_i$ 为臂 $i$ 迄今的拉动次数，$\hat\theta_i$ 为其平均奖励。一条臂每被拉动一次，加成项按 $1/\sqrt{N_i}$ 缩小；臂被搁置时，加成项按 $\sqrt{\ln t}$ 增长。因此没有哪条臂会被永久放弃，而坏臂只会偶尔被重新拉动。

这一证明的梗概值得一读，因为同样的三个步骤还会在第 13.4 节的高斯过程界中出现：一是以高概率成立的置信区间，二是论证乐观的代价至多为区间宽度，三是统计区间较宽的情形最多出现多少次。

这个界通过各臂的差距依赖于具体问题。远差于最优臂的臂很快被淘汰，贡献很小；与最优臂几乎一样好的臂各贡献 $\ln T / \Delta_i$，$\Delta_i$ 很小时这个量很大。第 12.4 节的上置信界规则基于同一思路，只是以高斯过程的后验标准差代替 Hoeffding 宽度。

13.2.4 Thompson 采样 #

最古老的规则是贝叶斯式的：把每个未知均值 $\theta_i$ 视为带先验的随机量，随时更新其后验，每轮以某条臂为最优臂的概率拉动该臂。Thompson 的巧妙之处在于，这个概率无须计算：只要从每条臂的后验中各抽取一个合理的均值，再拉动抽取值最大的臂即可（Thompson，1933）。

对抛硬币式的奖励，后验是 Beta 分布。从均匀先验出发，若一条臂赢了 $S_i$ 次、输了 $F_i$ 次，其后验为 $\mathrm{Beta}(1 + S_i, 1 + F_i)$，即第 5.2 节中的共轭更新。后验均值接近该臂的平均奖励，离散程度随拉动次数增加而缩小。

探索来自随机抽取。拉动次数少的臂后验很宽，有时会抽出很高的值；拉动次数多且平均奖励低的臂则几乎不会。Thompson 的规则起初流传不广。2010 年前后，几个研究组重新发现了它，并在实验中发现其表现很强，它才流行起来，而当时还没有任何证明（Lattimore 与 Szepesvári，2020，第 36 章）。此后，Agrawal 与 Goyal（2012）首次证明其期望遗憾按对数增长；Kaufmann 等人（2012）与 Agrawal 与 Goyal（2013）证明，对 Bernoulli 奖励，其首项常数达到最优，即下一节下界中的常数。这条规则的高斯过程版本从后验中抽取整个函数，在抽取的函数取最大值处评估，也就是第 12.5 节中的 Thompson 采样。

13.2.5 观察算法的表现 #

下图在同一组臂上将三个算法各运行多次，画出各算法的平均累积遗憾，区间带覆盖居中 80% 的运行。每次运行中，三个算法面对相同的回报序列，因此差异来自规则本身，而非运气。

可以尝试以下操作。

打开“对数时间轴”。在对数时间轴上，按 $\ln t$ 增长的遗憾是一条直线，线性增长的遗憾则急剧向上弯曲。Thompson 采样在几百轮后就稳定在一条直线上，ε-贪心则向上翘起。在这一时域内，UCB1 仍介于两者之间：差距为 0.1 时，其加成项较为保守，次优臂在数千轮内都仍在考虑范围之内，曲线要到更晚才变直。

把“ε-贪心的 ε”设为 0。此时即为贪心规则。区间带变宽：多数运行稳定在最优臂上，少数运行锁定在某条较差的臂上，不再离开。把“运行次数”设为 1，再按几次“换一组臂”，可以看到单次运行的结果。

在默认时域下比较 UCB1 与 ε-贪心。对这组臂，1,000 轮后 $\varepsilon = 0.1$ 的 ε-贪心遗憾低于 UCB1：UCB1 的加成项偏于保守，用额外的探索换取理论保证。把“差距 Δ”提高到 0.3，“轮数 T”提高到 5,000，ε-贪心的直线最终会超过 UCB1 的对数曲线。

打开“显示 UCB1 保证”。坐标轴会随之拉伸。默认设置下，$T = 1000$ 时定理 13.1 的界约为 1,100，是最差玩法（始终拉动最差的臂）损失量 450 的两倍多。这一保证成立，但在这一时域内不提供任何信息。

观察 Thompson 采样。Thompson 采样在此处遗憾最低，且在多数设置下，其曲线位于 Lai-Robbins 虚线下方。下一节解释为何这并不矛盾。

13.3 下界 #

UCB1 与 Thompson 采样的遗憾都按 $\ln T$ 增长。更聪明的算法能否做得更好，使遗憾以常数为界？Lai 与 Robbins（1985）给出了否定的回答。

直观的解释与证据有关。算法要停止拉动一条较差的臂，必须确信这条臂并非暗中的最优臂。误弃最优臂会在剩余轮次中造成 $\Delta T$ 量级的损失，因此犯这种错误的概率必须控制在 $1/T$ 量级。要在这一水平上排除备择假设，所需证据量按 $\ln T$ 增长；而臂 $i$ 每被拉动一次，平均提供固定量的证据，即 Kullback-Leibler 散度 $\mathrm{kl}(\theta_i, \theta^*)$。它是每次拉动在两个假设之间的平均对数似然比，两个假设分别为该臂回报率为 $\theta_i$ 和回报率为 $\theta^*$。对硬币而言，

当 $p = q$ 时其值为零；两枚硬币越容易区分，其值越大（第 6.2 节讨论一般情形下的散度）。所需证据量除以每次拉动提供的证据量，得到臂 $i$ 约需拉动 $\ln T / \mathrm{kl}(\theta_i, \theta^*)$ 次。

要把这一直觉变成定理，必须排除这样一类算法：它们在某个问题上碰巧表现很好，代价是在其他问题上表现极差。例如始终拉动臂 1 的规则，只要臂 1 是最优臂，其遗憾就为零。若一个算法在该类的每个赌博机上，遗憾都比 $T$ 的任何幂次增长得慢，即对每个 $a > 0$ 都有 $\E[R_T] / T^a \to 0$，则称该算法是一致的（consistent）。

这是奖励分布属于参数族时一般结果的特例；Lattimore 与 Szepesvári 给出了其现代形式的陈述与证明（Lai 与 Robbins，1985；Lattimore 与 Szepesvári，2020，定理 16.2）。

以下三点说明这一定理与前述算法的关系。第一，UCB1 的遗憾是对数级的，但并非最优。由 Pinsker 不等式，$\mathrm{kl}(p, q) \ge 2(p - q)^2$，因此 $c^*$ 的每一项至多为 $1/(2\Delta_i)$，而定理 13.1 中对应的项为 $8/\Delta_i$，至少大 16 倍。采用 Beta 后验的 Thompson 采样在极限意义下恰好达到 $c^*$（Kaufmann 等，2012；Agrawal 与 Goyal，2013）。

第二，定理讨论的是极限，其中的 $\liminf$ 至关重要。定理断言遗憾与 $\ln T$ 之比不可能始终低于 $c^*$，并未断言对每个有限的 $T$ 都有 $\E[R_T] \ge c^* \ln T$；低阶项为负的算法可以在很长时间内位于这条曲线下方。图 13.3 中的 Thompson 采样正是如此。依据这一定理，可以比较的是 $t$ 增大时对数时间轴上的斜率。

第三，这个界通过差距依赖于具体实例，差距缩小时界趋于无穷。但这并不意味着各臂几乎相等时遗憾会变大，因为拉动一条几乎同样好的臂代价很小。对所有实例取最坏情况（worst case）则是另一个量：对任意算法和任意 $T \ge K - 1$，都存在一个奖励服从高斯分布的 $K$ 臂赌博机，使该算法在其上的遗憾至少为 $\frac{1}{27}\sqrt{(K - 1)T}$（Lattimore 与 Szepesvári，2020，定理 15.2）。造成损失的差距随 $T$ 按 $\sqrt{K/T}$ 缩小：既大到足以产生影响，又小到难以察觉。实例相关的界按 $\ln T$ 增长，系数是依赖于问题的常数；最坏情况的界按 $\sqrt{T}$ 增长。两种视角在函数情形中都会再次出现。

13.4 从臂到函数 #

在贝叶斯优化中，每个输入都是一条臂，连续定义域上有无穷多条。上述赌博机界都随臂数增长，或通过对差距的求和，或通过最坏情况中的 $\sqrt{K}$；$K$ 为无穷时，这些界不能说明任何问题。分析得以延续的关键在于，这些臂不再相互独立。按照高斯过程先验，相近的输入取值相近，因此评估一个输入也能获得其邻近输入的信息。于是需要用另一个量代替臂数，以度量实质上不同的臂有多少条，最大信息增益就是这样的量。

13.4.1 设定 #

本节沿用 Srinivas 等人（2010）的分析。该分析假定第 8.3 节的模型完全成立：函数是从高斯过程中抽取的样本，$f \sim \GP(0, k)$，且 $k(\vx, \vx) \le 1$，从而先验标准差处处不超过 1。每次评估返回 $y_t = f(\vx_t) + \varepsilon_t$，噪声 $\varepsilon_t \sim \N(0, \sigma_n^2)$ 相互独立，方差已知。暂设定义域 $\X$ 为有限集，例如一个精细的网格（原论文将该集合记作 $D$），第 13.4.4 节将放宽这一假设。奖励服从高斯分布的 $K$ 臂赌博机，就是核函数在对角线上为 1、其余位置为 0 的特例。

经过 $t - 1$ 次评估，后验均值为 $\mu_{t-1}(\vx)$，标准差为 $\sigma_{t-1}(\vx)$，按式（8.6）计算。GP-UCB 规则沿用 UCB1 的乐观原则，只是以后验代替 Hoeffding 区间：

其中后验均值相当于经验平均值，后验标准差相当于加成项，$\beta_t$ 决定允许乐观到几个标准差。这正是式（11.3）的规则，只是权重可以逐轮变化。与该式及 Srinivas 等人（2010）一致，$\beta_t$ 乘在方差上，因此其平方根乘在标准差上；有些教材和软件库则把标准差本身的乘子称为 $\beta$。

13.4.2 最大信息增益 #

$T$ 次带噪声的评估能提供多少关于 $f$ 的信息？第 6.5 节已回答了这个问题，这里的界需要用到其中的三个事实。第一，在输入集合 $A$ 上的观测 $\vy_A$ 与函数之间的互信息（mutual information），即观测的不确定性中反映 $f$ 而非噪声的部分，为

其中 $\mK_A$ 是 $A$ 的核矩阵（式（6.15））。互信息只取决于在哪里评估，与观测到的值无关，因为高斯过程的后验方差不依赖于观测值（第 8.1 节）。第二，任意 $T$ 次评估所能提供的信息，上限就是这个量所能取到的最大值。

$\gamma_T$ 由核函数、定义域和噪声水平决定，在获得任何数据之前就已确定。

两个极端情形给出了它的范围。若全部 $T$ 次评估都位于同一输入，获得的信息为 $\tfrac12 \log(1 + T/\sigma_n^2)$，只按对数增长：如习题 8.2 所示，重复评估提供的信息越来越少。若核函数是对角的，如 $K$ 臂赌博机，则把评估均匀分配到各臂上最好，$\gamma_T$ 按 $\tfrac{K}{2}\log(1 + T/(K\sigma_n^2))$ 增长（习题 13.3）。光滑的核函数介于两者之间：相近输入处的观测大多是冗余的，因此信息的增长比 $T$ 条独立的臂慢得多。较短的长度尺度、粗糙的核函数、较高的维度、较低的噪声，都会使定义域中更多的部分变得可以区分，从而增大 $\gamma_T$。

第三，这个最大值虽然无法精确计算，却很容易近似。在 $\vx$ 处新做一次评估，信息恰好增加 $\tfrac12 \log(1 + \sigma_n^{-2}\sigma_{t-1}^2(\vx))$（式（6.16））。因此，贪心规则每次都在后验方差最大处评估（即不确定性采样，第 6.5.1 节），所得信息至少为 $\gamma_T$ 的 $1 - 1/e \approx 0.63$（Srinivas 等，2010）。第 13.5 节中的图正是用这种方法估计 $\gamma_T$ 的。

13.4.3 GP-UCB 的界 #

借助 $\gamma_T$，这个界的形式与赌博机界相仿，只是替换了其中的 $K$。

证明沿用 UCB1 证明梗概中的三个步骤，每一步都是初等的。

这一结果可以这样理解：$\beta_T$ 按 $\log T$（以及 $\log |\X|$）增长，而对实践中使用的核函数，$\gamma_T$ 次线性增长，因此 $R_T$ 按 $\sqrt{T}$ 乘以若干缓慢增长的因子增长。可见 GP-UCB 是无遗憾的；再由式（13.2），以至少 $1 - \delta$ 的概率，GP-UCB 评估过的最好输入与最大值之差不超过 $\sqrt{C_1 \beta_T \gamma_T / T}$。

有限定义域并不只是为了数学上的方便。在 Srinivas 等人（2010）的实验中，输入是 Intel Research Berkeley 某传感器网络中的 46 个温度传感器；第二项测试的输入是加利福尼亚州 I-880 高速公路某路段上的 357 个交通传感器，目标是找出最拥堵的位置。核矩阵并非由公式给出，而是传感器读数在记录数据前三分之二上的经验协方差；待优化的函数则取自其余三分之一数据中的快照。在温度数据上，GP-UCB 与期望改进都明显优于其他启发式方法，两者之间无显著差异；作者总结认为，GP-UCB 的表现至少不逊于那些没有遗憾界的现有方法。这个界还把两个研究传统联系起来。第 4 步表明，GP-UCB 的某一步只有在能提供信息时才可能代价高昂，因此优化器的遗憾受制于关于 $f$ 还有多少内容可学，而这正是实验设计中通用的度量（第 6.4 节）。

这个界的好坏取决于 $\gamma_T$ 增长的快慢。表 13.1 汇总了 $d$ 维定义域上的已知速率，这些速率由核函数特征值衰减的快慢决定（第 10.5 节）；其中 $\nu$ 是 Matérn 核的光滑度参数（第 9.1 节）。

对径向基函数核，维度只出现在 $\log T$ 的指数上，因此界按 $\sqrt{T}(\log T)^{(d+2)/2}$ 增长（其中因子 $(\log T)^{(d+1)/2}$ 来自 $\gamma_T$，另一个因子 $(\log T)^{1/2}$ 来自 $\beta_T$）：即使在多维情形下，非常光滑的函数也能很快学到（Srinivas 等，2010）。对 Matérn 核，最初的速率并不紧；Vakili 等人（2021a）于 2021 年给出的速率在相差对数因子的意义下与已知下界一致。

13.4.4 其他设定 #

有限定义域上的定理可以向三个方向推广，每个方向各有其假设。本小节概览相关结果，供日后在论文中遇到它们的读者参考。初读时可以跳过；后文唯一用到的概念是再生核 Hilbert 空间，第 21.3 节会再作解释，第 10 章则有深入的讨论。

连续定义域。对 $d$ 维的紧凸定义域（例如箱形区域），Srinivas 等人（2010）证明了同样形式的界：$\beta_t$ 增加一个 $d \log t$ 量级的项，界本身增加一个加性常数。证明中随着 $t$ 增大把定义域离散得越来越细，这要求样本路径足够光滑，使相邻网格点上的函数值彼此接近。径向基函数核和 $\nu > 2$ 的 Matérn 核满足这一条件。粗糙的 Matérn 1/2 核不满足这一假设，作者猜想对它不存在这种形式的结果。

固定函数。上述定理是贝叶斯式的：对从先验中抽取的函数以高概率成立。频率派版本则要求对函数类中任意一个固定的函数给出保证。自然的函数类是该核函数的再生核 Hilbert 空间（reproducing kernel Hilbert space，RKHS）。这一函数空间由形如式（8.4）的核函数鼓包之和构成，其范数 $\lVert f \rVert_k$ 衡量 $f$ 相对于该核函数的粗糙程度（第 10.2 节构造了这一空间及其范数）。（高斯过程本身的样本路径比这更粗糙，范数为无穷大，因此两种设定互不包含。）若 $\lVert f \rVert_k^2 \le B$ 且噪声有界，则采用 $\beta_t = 2B + 300\gamma_t \log^3(t/\delta)$ 的 GP-UCB，其遗憾在相差对数因子的意义下为 $\sqrt{T}(\sqrt{B\gamma_T} + \gamma_T)$ 量级（Srinivas 等，2010）。Chowdhury 与 Gopalan（2017）改进了这一分析，并证明了 Thompson 采样的一种高斯过程版本的遗憾界。这类宽度从何而来，见第 13.4.5 节。

下界。在 RKHS 设定下，Scarlett 等人（2017）证明，对任何算法，Matérn 函数类中都存在某个函数，使该算法的累积遗憾至少为 $T^{(\nu + d)/(2\nu + d)}$ 量级。对径向基函数核，他们证明累积遗憾至少为 $\sqrt{T(\log T)^{d/2}}$ 量级；这与上界相符，差别仅在于上界中根号下 $\log T$ 的指数为 $2d + O(1)$ 而非 $d/2$。这些下界之于函数，正如 Lai 与 Robbins 的结果之于赌博机：它们表明该函数类迫使任何算法做多少探索。

把评估换成比较，同样的工具可以得出第 21.3 节中核化对决赌博机的界，以及第 29 章的理论；后者的一些基本下界目前仍然缺失（第 29.7 节）。

13.4.5 固定函数的置信界 #

定理 13.3 的置信步骤用到了第 13.2.2 节中的两个工具。高斯变量偏离均值超过 $\beta^{1/2}$ 个标准差的概率至多为 $e^{-\beta/2}$；对 $|\X|$ 个输入和各轮取联合界，并给第 $t$ 轮分配 $\delta$ 中的 $6\delta/(\pi^2 t^2)$，就要求 $|\X|\, e^{-\beta_t/2} = 6\delta/(\pi^2 t^2)$。解出 $\beta_t$，即得定理中的 $\beta_t = 2 \log\!\big(|\X|\, t^2 \pi^2/(6\delta)\big)$。在那里，自适应地选择输入并无妨碍：给定已有的观测，据此选出的输入就是固定的，无论用什么规则选择，$f(\vx)$ 都服从均值为 $\mu_{t-1}(\vx)$、标准差为 $\sigma_{t-1}(\vx)$ 的高斯分布（Srinivas 等，2010，引理 5.1）。

第 13.4.4 节中的频率派结果失去了这一支撑。在那里，$f$ 是满足 $\lVert f \rVert_k^2 \le B$ 的一个固定函数，唯一的随机性来自噪声。误差 $\mu_t(\vx) - f(\vx)$ 由两部分组成：先验把估计拉向零所造成的偏差，以及噪声项 $\varepsilon_1, \dots, \varepsilon_t$ 的加权和；而权重取决于算法选择在哪里观测，这又取决于先前的噪声。这不是权重事先固定的独立项之和，因此 Hoeffding 不等式不适用；在连续定义域上，也没有有限的输入列表可供取联合界。本小节介绍替代这两者的工具，并说明它如何给出随 $\gamma_t$ 与 $\log(1/\delta)$ 增长的宽度。与上面的概览一样，本小节初读时可以跳过。

鞅（martingale）。考虑累加和 $M_t = \sum_{s \le t} g_s \varepsilon_s$：每个权重 $g_s$ 可以依赖于第 $s$ 轮之前观测到的一切，但在抽取 $\varepsilon_s$ 之前就已确定；给定之前的一切，每个 $\varepsilon_s$ 的均值为零。这样的和称为鞅，好比赌徒在公平赌局中的资产，他根据历史决定每次下注的数额。下注是自适应的，赌局依然公平。Chernoff 方法在自适应的情形下依然有效。给定过去，$g_t$ 是一个固定的数，$\varepsilon_t$ 是 $R$-次高斯的（定义 13.2），因此 $\E\big[e^{\lambda g_t \varepsilon_t} \given \text{past}\big] \le e^{\lambda^2 g_t^2 R^2/2}$。从最后一轮开始逐轮剥离，可以证明

对每个 $t$ 的期望都至多为 1。式（13.6）的推导把期望按独立项分解，这里则按轮次分解，每一轮都以之前各轮为条件。结论还可以更强：$Z_t$ 始终非负，平均而言也不会逐轮向上漂移；对这样的过程，Markov 不等式有更强的形式，即极大不等式（maximal inequality）：$Z_t$ 在某一轮达到 $1/\delta$ 的概率至多为 $\delta$（Lattimore 与 Szepesvári，2020，定理 3.9）。于是，对所有轮次同时成立的界不再需要对轮次取联合界。

还剩两个问题。一是最佳的 $\lambda$ 依赖于随机的 $V_t$。二是高斯过程的估计不具有 $M_t$ 的形式：它赋予观测 $y_s$ 的权重依赖于第 $s$ 轮之后选择的输入。第一个问题的解决办法是不再选定 $\lambda$，而是对它求 $Z_t$ 的平均，这称为混合方法（method of mixtures）。

这一结果可以用标准差来解读。$R^2 V_t$ 相当于 $M_t$ 的方差，因此这个和保持在约一个标准差 $R\sqrt{V_t + c}$ 乘以 $\sqrt{2\log(1/\delta) + \log(1 + V_t/c)}$ 的范围之内。$2\log(1/\delta)$ 是每个 Chernoff 界都要支付的置信代价。$\log(1 + V_t/c)$ 是事先不知道方差会有多大的代价，它只按方差的对数增长。这类界称为自归一化（self-normalized）界：和以其自身累积的方差为尺度来度量。

第二个问题的解决办法是改用向量。用特征表示核函数，$k(\vx, \vx') = \boldsymbol{\phi}(\vx)^\T\boldsymbol{\phi}(\vx')$，即第 5.4.2 节的权重空间观点，并把权重的先验协方差取为 $\mI$。前 $t$ 轮可以用两个量概括：权重的后验精度，以及沿接收噪声的输入的特征方向累加的噪声：

$\mathbf{s}_t$ 每一项的权重向量 $\boldsymbol{\phi}(\vx_s)$ 都在抽取对应的噪声之前确定，因此 $\mathbf{s}_t$ 是取向量值的鞅。用方向上的高斯分布代替上面推导中 $\lambda$ 的高斯分布求平均，就得到下面的界。