技术摘要：缩小 1-识别样本复杂度的差距

问题表述

本文探讨了1-识别问题，这是多臂老虎机（MAB）框架中的一种纯探索变体。其目标是确定在 $K$ 个臂的集合中，是否存在至少一个臂 $a$，其平均奖励 $r_a$ 超过已知阈值 $\mu_0$。

• 正例：$\max_a r_a > \mu_0$。算法必须识别出（至少）一个这样的臂。
• 负例：$\max_a r_a < \mu_0$。算法必须输出“无”。
• 保证：算法必须是 $\delta$-概率近似正确（PAC）的，确保做出正确决策的概率至少为 $1-\delta$。主要关注的指标是期望样本复杂度 $E[\tau]$。

该问题不同于标准的最佳臂识别（BAI），因为它不需要对所有臂进行排序或识别出唯一的最佳臂，而是寻找任何超过阈值的臂。虽然负例的样本复杂度已得到充分理解（与 BAI 密切相关），但正例的复杂度，特别是那些具有多个合格臂（$m > 1$）的情况，一直是一个未解决的问题，且现有的界限较为宽松。

方法论

1. 下界分析

作者利用一种新颖的优化公式推导出了正例的新下界，摒弃了传统上常为复杂实例产生宽松界限的“模拟器”框架。

• 对称性简化：证明首先表明，为了下界的目的，可以将注意力限制在对称算法上（即对臂标签置换保持不变的算法）。
• 凸优化：下界证明的核心涉及构建一个凸优化问题。期望样本复杂度 $E[\tau]$ 被证明由该问题的最优值下界限定。
• 对偶解：通过构建一个特定的可行对偶解，作者推导出了一个紧的下界，该下界同时依赖于置信参数 $\delta$ 和实例相关的间隙。该界限表示为：
  $$\Omega\left( \min_{1 \le j \le m} \left\{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + \frac{H(j)}{\log^2(m+1)} \right\} \right)$$
  其中 $\Delta_{j,0} = \mu_j - \mu_0$，$H(j)$ 是一个涉及臂之间间隙的复杂度项。

2. 算法设计：PSEEB

为了匹配下界，本文提出了**基于括号并行顺序探索 - 利用（PSEEB）**算法。

• 括号机制：该算法基于臂的单个随机排列，生成一个嵌套的“括号”（臂的子集）族 $\{B_b\}$。$B_1 \subset B_2 \subset \dots \subset B_{\lceil \log_2 K \rceil + 1} = [K]$，其中 $|B_b| \approx 2^b$。
• 并行执行：算法并行运行 $\lceil \log_2 K \rceil + 1$ 个独立的基于顺序探索 - 利用（SEE）的副本（改编自 Li 和 Cheung, 2025）。每个副本仅在一个括号 $B_b$ 上操作。
• 轮询调度：副本以轮询方式执行。一旦任何副本输出一个有效臂或“无”，全局算法即终止。
• 停止规则：
  • 仅允许在完整臂集（$B_{\lceil \log_2 K \rceil + 1}$）上操作的副本输出“无”。
  • 在较小括号上操作的副本即使怀疑其子集中不存在合格臂，也会继续采样，以确保它们不会过早终止而错过可能存在于更大括号中的合格臂。

主要贡献与结果

1. 紧下界

本文建立了一个针对正例的新下界，该下界在 $\delta$ 相关项（$\log(1/\delta)$）和 $\delta$ 无关项上均达到联合最优。

• 先前的工作（例如 Degenne 和 Koolen, 2019；Li 和 Cheung, 2025）仅在单个合格臂（$m=1$）的情况或受限设置下实现了近最优性。
• 新下界解决了关于多个合格臂（$m > 1$）实例复杂度的未解决问题，确定了 $\min_{1 \le j \le m} \{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + H(j) \}$ 为正确的实例相关复杂度度量。

2. 近最优上界

提出的 PSEEB 算法在期望样本复杂度上达到的上界，与新的下界在 $K$ 和间隙的多项式对数因子范围内相匹配。

• 正例：$E[\tau] \le O\left( \log K \cdot \min_{1 \le j \le m} \left\{ \frac{\log(1/\delta)}{\Delta_{j,0}^2} + \text{poly}(\log K, \log(1/\Delta)) \cdot H(j) \right\} \right)$。
• 负例：该算法保持了针对负例的已知最优界限，$O(H_1^{neg} \log(1/\delta))$。
• 强 $\delta$-PAC：算法被证明是强 $\delta$-PAC 的，意味着对于所有实例，期望样本复杂度都是有限的，从而排除了 $E[\tau] = \infty$ 的病态行为。

意义与主张

本文声称首次在多个合格臂的一般情况下，缩小了1-识别样本复杂度的差距。

• 解决未解决问题：它明确解决了 Li 和 Cheung (2025) 留下的关于 $m > 1$ 时 $\delta$ 无关项可改进性的未解决问题。
• 方法论进步：将下界推导简化为凸优化问题，被视为对先前“模拟器”框架的重大简化，从而产生了更紧且更通用的结果。
• 算法效率：通过利用并行括号策略，PSEEB 有效地处理了哪个臂合格的的不确定性，而无需识别具体的“最佳”合格臂，从而避免了将 1-识别简化为标准 BAI 所伴随的不必要采样成本。

作者指出，虽然界限几乎是紧的，但细化对数因子仍然是未来研究的一个方向。这项工作为 1-识别在正例和负例情况下的样本复杂度景观提供了完整的刻画。