技术摘要：具有最小遗憾的最佳臂识别

问题表述

本文在随机多臂老虎机框架内，引入并研究了**具有最小遗憾的最佳臂识别（Best Arm Identification, BAI）**问题。该设定涉及一个固定置信度场景，智能体与 $K$ 个臂进行交互，每个臂都关联着一个已知的单参数指数族奖励分布。智能体必须以至少 $1-\delta$ 的概率识别出唯一的最佳臂（即均值最高的臂）。

不同于标准的固定置信度 BAI（仅关注最小化样本复杂度，即达到置信水平所需的拉动次数）或标准遗憾最小化（关注在固定时界内最大化累积奖励），本问题旨在最小化直到停止时间 $\tau_\delta$ 的期望累积遗憾，同时满足错误概率不超过 $\delta$ 的约束。作者认为，在临床试验等实际应用中，探索的成本并非均匀的；拉动一个次优臂会产生与其次优差距（suboptimality gap）成比例的“遗憾”。因此，一个“负责任”的实验过程应当在保证能正确识别最佳臂的同时，优先考虑最小化这种累积遗憾。

方法论与算法设计

为了解决这一问题，作者提出了 Double KL-UCB (DKL-UCB) 算法。该算法旨在平衡两个相互冲突的目标：识别最佳臂（需要对次优臂进行充分探索）和最小化遗憾（需要利用当前的最佳估计进行开发/利用）。

DKL-UCB 的核心组成部分包括：

1. 双重置信边界： 算法为每个臂 $i$ 在时刻 $t$ 维护两个不同的 Kullback-Leibler (KL) 上置信界 (UCB)：
   • $f$-UCB ($U^f_i(t)$)： 使用探索函数 $f(t) = 3 \log t$。该边界旨在积极地识别当前的最佳臂（“领导者”）。
   • $g$-UCB ($U^g_i(t)$)： 使用探索函数 $g(\delta, t) = \log(2Kt^2/\delta)$。该边界是为固定置信度需求量身定制的，有助于将最佳臂与次优臂区分开来。
2. 候选选择： 在每一步，算法识别两个候选臂：
   • $A^f_t$：具有最高 $f$-UCB 的臂。
   • $A^g_t$：具有最高 $g$-UCB 的臂（排除 $A^f_t$）。
3. 随机采样： 智能体根据偏置硬币投掷以概率 $\beta(\delta) = 1 - \min\{1/\log\log(1/\delta), 1/2\}$ 来决定拉动 $A^f_t$ 还是 $A^g_t$。随着 $\delta \to 0$，$\beta(\delta) \to 1$，这意味着算法会越来越多地倾向于由 $f$-UCB 识别的臂（可能的最佳臂）以最小化遗憾，同时仍会偶尔拉动 $g$-UCB 候选臂，以确保次优臂得到充分探索，从而满足置信度约束。
4. 停止规则： 当 $f$-UCB 领导者的下置信界（LCB）超过 $g$-UCB 的亚军时，算法终止，从而确保满足置信水平 $\delta$。

理论结果

1. 信息论下界

作者为任何 $\delta$-PAC（概率近似正确）算法建立了关于期望累积遗憾的基本实例相关下界。

• 遗憾下界： 对于任何 $\delta$-PAC 算法，期望累积遗憾满足：
  $$\liminf_{\delta \to 0} \frac{E_\mu[R(\tau_\delta)]}{\log(1/\delta)} \geq I^*(\mu)$$
  其中 $I^*(\mu) = \sum_{i=2}^K \frac{\Delta_i}{\text{kl}(\mu_i, \mu_1)}$。这里 $\Delta_i$ 是次优差距，$\text{kl}$ 是 KL 散度。
• 不可能结果（样本复杂度）： 本文证明，实现遗憾渐近最优性必须以超对数的样本复杂度为代价。具体而言，任何渐近最优的算法必须满足 $E_\mu[\tau_\delta] = \omega(\log(1/\delta))$。这凸显了一种根本性的张力：为了最小化遗憾，智能体拉动最佳臂的频率必须显著高于仅仅为了区分它所需的最小对数次数，从而导致总样本复杂度严格大于 $\Theta(\log(1/\delta))$。

2. 算法性能

作者证明了 DKL-UCB 实现了累积遗憾的渐近最优性：
$$\limsup_{\delta \to 0} \frac{E_\mu[R(\tau_\delta)]}{\log(1/\delta)} \leq I^*(\mu)$$
这与下界相匹配，证实了 DKL-UCB 在最小遗憾 BAI 问题上的最优性。

关于样本复杂度，该算法实现了：
$$E_\mu[\tau_\delta] = \omega(\log(1/\delta)) \cap o\left(\log(1/\delta) \cdot (\log\log(1/\delta))^2\right)$$
这表明虽然样本复杂度是超对数的（如前所述是必要的），但它是接近最优的，仅在乘性因子 $(\log\log(1/\delta))^2$ 上偏离了下界。

主要贡献与意义

本文对多臂老虎机文献做出了几项独特的贡献：

1. 问题表述： 它正式定义并阐述了具有最小遗憾的 BAI 问题，弥合了纯样本复杂度最小化与纯遗憾最小化之间的鸿沟。作者认为，在次优动作具有不同成本（遗憾）的现实世界设置中，最小化探索阶段的累积遗憾是一个在伦理和实践上更合理的客观目标。
2. 基本极限： 它建立了固定置信度 BAI 中期望累积遗憾的第一个实例相关下界。至关重要的是，它提供了一个不可能结果，表明在 BAI 中最小化遗憾本质上需要比标准 BAI 更高阶的样本复杂度，从而阐明了这两个目标之间的“张力”。
3. 算法创新： DKL-UCB 的设计利用了两个不同的置信边界和一个特定的随机选择策略，为在 BAI 背景下平衡探索与开发提供了一种新颖的方法。
4. 对比分析： 本文证明了针对最小样本复杂度优化的算法（如 Track-and-Stop）并不一定能最小化遗憾，反之亦然。通过理论分析和数值实验，论文展示了 DKL-UCB 在累积遗憾方面显著优于标准 BAI 算法，同时保持了近乎最优的样本复杂度。

实验验证

在伯努利老虎机实例上的数值实验证实了理论发现。DKL-UCB 在累积遗憾方面始终优于 Track-and-Stop 和 Top-Two Thompson Sampling (TTTS)，特别是在置信水平 $\delta$ 变得很小时。相反，正如预期，Track-and-Stop 和 TTTS 表现出更低的样本复杂度，这验证了文中识别出的理论权衡。

结论

本文得出结论，虽然 BAI 中的遗憾最小化和样本复杂度最小化是具有不同最优策略的不同目标，但它们是深度互连的。所提出的 DKL-UCB 算法成功地驾驭了这种权衡，在达到遗憾基本下界的同时，仅付出了微小的样本复杂度代价。作者指出，未来的工作可以探索非渐近界和最坏情况下的遗憾表现，以及在放宽遗憾约束下的样本复杂度的精确基本极限。