Fundamental Limitations of Fixed-Budget Best-Arm Identification

技术摘要：固定预算下最佳臂识别（Best-Arm Identification）的基础局限性

问题阐述
本文研究了固定预算下的最佳臂识别（Best-Arm Identification, BAI）问题，该问题也称为排序与选择（Ranking and Selection）。在这种设定下，决策者顺序地从 $K$ 个臂中进行采样，每个臂产生的奖励均来自一个均值 $\mu_k$ 未知的分布。目标是在固定的总采样预算 $T$ 内，识别出具有最大均值的臂 $i^*(\mu)$。性能指标是错误识别概率 $p_{\mu, T}$，具体为当 $T \to \infty$ 时其指数衰减率：
$$\liminf_{T \to \infty} \frac{1}{T} \log \frac{1}{p_{\mu, T}}$$

核心理论问题在于是否存在一个针对该问题的“复杂度”。复杂度被定义为一个满足以下两个条件的函数 $\Gamma^*(\mu)$：

1. 通用上界： 对于每一个算法和每一个实例 $\mu$，误差衰减率都被 $\Gamma^*(\mu)$ 所限制。
2. 一致可达性： 存在一个单一的算法，能够在所有问题实例 $\mu$ 上一致地达到该衰减率 $\Gamma^*(\mu)$。

本文研究了**静态预言机（static oracle）*速率 $\Gamma^*_{so}(\mu)$ 是否可以作为这一复杂度。静态预言机代表了一种非自适应策略所能达到的最优误差衰减率，该策略预先知道真实的均值 $\mu$，并分配固定的采样比例以最大化衰减率。虽然已有算法被设计为使其采样比例收敛*到这些最优的静态比例，但目前仍有一个悬而未决的问题：是否存在任何自适应算法能够一致地匹配静态预言机的误差衰减率。

方法论
作者采用反证法证明，当 $K \geq 3$ 时，不存在任何单一算法能一致地实现静态预言机速率。其方法论依赖于以下组成部分：

1. 难度比（Difficulty Ratios）： 遵循 Degenne (2023) 的研究，本文利用难度比 $R_{H, \infty}(A, \mu)$ 来衡量算法 $A$ 相对于基准难度函数 $H(\mu)$ 的性能。如果复杂度存在，则必须存在一个算法，使得该比值在所有实例上的上确界 $\leq 1$。
2. 定理 1 (Degenne 2023)： 本文利用了 Degenne (2023) 中的一个关键不等式，该不等式对任何一致的自适应算法族进行了界定。对于任何基准 $H$ 和一组备选实例 $D(\mu)$，逆难度比被一个关于采样比例 $\omega$ 的静态优化问题所界定：
   $$\left( \sup_{\lambda \in D(\mu)} R_{H, \infty}(A, \lambda) \right)^{-1} \leq \sup_{\omega \in \Delta_K} \inf_{\lambda \in D(\mu)} \left( H(\lambda) \sum_{k=1}^K \omega_k \text{KL}(\mu_k, \lambda_k) \right)$$
3. 实例构建： 为了证明复杂度的不存在性，作者构建了一个特定的“基准”实例 $x$ 以及一个备选实例族 $D(x) = \{\lambda_A, \lambda_{B,3}, \dots, \lambda_{B,K}\}$。
   • $\lambda_A$： 仅在臂 1 和臂 2 上与 $x$ 不同。区分 $x$ 与 $\lambda_A$ 需要对臂 1 和臂 2 进行大量采样。
   • $\lambda_{B,j}$（对于 $j \in \{3, \dots, K\}$）： 仅在臂 $j$ 上与 $x$ 不同，使得臂 $j$ 成为新的最佳臂。区分 $x$ 与 $\lambda_{B,j}$ 需要对臂 $j$ 进行大量采样。
     该构建确保了“最难”区分的臂在族群中是变化的。由于所需的信息集中在不相交的臂集上，单一的采样分配 $\omega$ 无法同时对区分 $x$ 与 $D(x)$ 中的所有成员达到最优。

主要结果
本文对固定预算下的 BAI 提出了一个根本性的否定结果：

• 高斯奖励： 对于具有高斯奖励（方差为 1）的 $K \geq 3$ 个臂，作者证明了对于任何一致算法族 $A$，都存在一个实例 $\mu$，使得相对于静态预言机的难度比超过 1。具体而言：
  $$\inf_{A \in \mathcal{C}_{cons}} \sup_{\mu} R_{H_{so}, \infty}(A, \mu) \geq 1 + \sum_{j=3}^K \frac{1}{(1 + \sqrt{j-1})^2} > 1 + \frac{1}{8} \log(K)$$
  该下界对于所有 $K \geq 3$ 都严格大于 1，从而证明了没有任何算法能一致地匹配静态预言机。

• 向自然指数族（NEF）的推广： 该结果被扩展到任何单参数自然指数族（NEF）。通过使用 Kullback-Leibler (KL) 散度的局部二次近似，作者表明高斯结果意味着对于所有正则单参数 NEF，同样存在这种局限性。

• 回答开放性问题： 本研究明确回答了 Qin (2022) 提出并由 Degenne (2023) 形式化的开放性问题：当 $K \geq 3$ 时，固定预算下的 BAI 不存在复杂度。虽然静态预言机提供了误差衰减率的一个下界，但没有任何单一的自适应算法能在所有问题实例上一致地达到该界。

意义与主张
本文声称解决了理解固定预算下 BAI 的一个基本理论空白。

• 自适应性的局限性： 它表明，采样比例向静态预言机收敛（这是许多自适应算法的设计目标）不足以保证匹配静态预言机的误差衰减率。在固定预算设定下的“自适应代价”在于，算法无法同时对所有实例都是最优的。
• 适用范围： 该结果填补了高斯奖励下 $3 \leq K < e^{80/3}$ 的文献空白，并将复杂度的不存在性扩展到了所有单参数 NEF。
• 理论边界： 该工作确立了当 $K \geq 3$ 时，静态预言机速率不是固定预算下 BAI 的通用复杂度。作者暗示，这表明需要寻找替代的理论目标或基准，因为静态预言机无法被一致地实现。

本文并未提出新的算法来克服这一局限性，也未在理论影响之外提出具体的应用建议。其贡献纯粹是一个关于定义该设定下可实现性的基本极限的否定性结果。