Balancing Performance and Costs in Best Arm Identification¶

会议: NeurIPS 2025
arXiv: 2505.20583
代码: 待确认
领域: 多臂赌博机 / 最优臂识别
关键词: 最优臂识别, 代价-性能权衡, 相变现象, 动态预算, 风险泛函

一句话总结¶

提出将最优臂识别（BAI）从固定预算/固定置信度框架重新定义为"误识别概率/简单遗憾 + 采样成本"的风险泛函最小化问题，推导出含相变现象的下界（差距过小时最优策略是直接猜），设计 DBCARE 算法在动态预算下达到对数因子内最优。

研究背景与动机¶

领域现状：传统 BAI 有两种范式——固定预算（给定 \(T\) 次采样最小化错误率）和固定置信度（给定 \(\delta\) 最小化采样次数）。A/B 测试等实际场景需要同时权衡准确性和采样成本。
现有痛点：固定预算和固定置信度都需要预先指定约束（\(T\) 或 \(\delta\)），但实际中两者都未知且相互耦合。选错 \(T\) 浪费资源，选错 \(\delta\) 要么太松要么太紧。
核心矛盾：采样越多越准确但成本越高——需要一个统一框架在连续权衡中找到最优平衡点。
本文要解决什么？ 定义新的风险泛函 \(\mathcal{R} = \text{性能损失} + c \cdot E[\tau]\)，推导最优下界，设计匹配算法。
切入角度：两种风险泛函——\(\mathcal{R}_{MI}\)（误识别概率+成本）和 \(\mathcal{R}_{SR}\)（简单遗憾+成本），各自有不同的最优策略和相变行为。
核心 idea 一句话：将 BAI 统一为风险泛函最小化 → 推导含相变的下界 → DBCARE 动态预算消除算法匹配下界到对数因子。

方法详解¶

整体框架¶

风险泛函定义: \(\mathcal{R}_{MI} = P(\hat{I} \neq I^*) + c \cdot E[\tau]\)，或 \(\mathcal{R}_{SR} = E[\mu^* - \mu_{\hat{I}}] + c \cdot E[\tau]\)。下界推导: 对 2 臂和 K 臂分别给出依赖 \(\Delta\)（差距）和 \(H\)（复杂度）的下界，发现相变现象。DBCARE 算法: 动态预算消除法——按 epoch 拉所有存活臂，Hoeffding 置信边界消除，预算随存活集缩小自适应调整。

关键设计¶

相变现象的发现:
做什么：推导风险下界，发现当臂间差距小于临界值时最优策略是直接猜
核心思路：\(\mathcal{R}_{MI}\) 的 2 臂下界在 \(\Delta \geq \sqrt{\sigma^2 c}\) 时为 \(\frac{\sigma^2 c}{4\Delta^2}\log(\frac{e\Delta^2}{\sigma^2 c})\)，在 \(\Delta < \sqrt{\sigma^2 c}\) 时退化为 \(1/4\)（随机猜）。相变点 \(\Delta^* = \sqrt{\sigma^2 c}\) 取决于噪声和单位采样成本
设计动机：根本性的理论洞察——差距太小时采样成本超过精度收益
DBCARE 算法（动态预算消除）:
做什么：在不知道 \(\Delta\) 的情况下自适应地平衡采样和误差
核心思路：维护存活臂集 \(S\)，每 epoch 对 \(S\) 中每臂拉一次。当 \(\max_\ell \hat{\mu}_\ell - \hat{\mu}_k > e_n\) 时消除臂 \(k\)。动态预算：\(\mathcal{R}_{MI}\) → \(N^*(k) = (kec)^{-1}\)；\(\mathcal{R}_{SR}\) → \(N^*(k) = \frac{3}{2e}\sigma^{2/3}((k-1)c)^{-2/3}\)
设计动机：固定预算不知何时停止，DBCARE 根据存活臂数和成本参数动态调整
上界匹配（对数因子内最优）:
做什么：证明 DBCARE 风险与下界匹配到对数因子
核心思路：2 臂 \(\mathcal{R}_{MI}\) 上界 \(\leq 32\text{LB}(\Delta) + 2c\)；最坏情况 \(\mathcal{R}_{SR} \leq 9\text{LB}^* + 3c\)
设计动机：理论上不能本质上更好

损失函数 / 训练策略¶

纯理论 + 仿真验证 + 药物发现真实数据实验
\(\sigma\)-sub-Gaussian 分布假设

实验关键数据¶

主实验（2 臂高斯，\(\sigma^2=1, c=10^{-4}\)）¶

方法	小 \(\Delta\)	中 \(\Delta\)	大 \(\Delta\)	全局一致
固定预算 \(T=10\)	差	中	好	✗
固定预算 \(T=500\)	好	好	差	✗
固定置信度 \(\delta=0.1\)	差	中	差	✗
DBCARE	好	好	好	✓

药物发现实验（5 臂，237 患者，二元和等级结局）¶

DBCARE 在所有成本 \(c \in [10^{-3}, 10^{-5}]\) 上最一致
无方法在所有 \(c\) 上主导，但 DBCARE 从不最差

关键发现¶

相变清晰可见——\(\Delta\) 过小时所有方法退化为随机猜测
DBCARE 是唯一全局竞争力的方法
匹配先知策略到常数倍

亮点与洞察¶

相变现象的发现深刻：存在临界差距，低于此差距采样不值得——直接指导 A/B 测试资源分配
统一 BAI 框架消除了固定预算 vs 固定置信度的人为选择
DBCARE 的动态预算极简——一个公式 \(N^*(k)\) 实现自适应

局限性 / 可改进方向¶

限于 \(\sigma\)-sub-Gaussian 分布
K 臂上下界有对数因子间隙
高复杂度 \(H \to \infty\) 时简单遗憾下界可改进

评分¶

新颖性: ⭐⭐⭐⭐⭐ 统一框架 + 相变是重要理论贡献
实验充分度: ⭐⭐⭐⭐ 仿真 + 真实药物数据
写作质量: ⭐⭐⭐⭐⭐ 定理结构清晰
价值: ⭐⭐⭐⭐ 为实际 A/B 测试提供理论最优框架
理论工作，无训练。DBCARE 的关键参数是预算函数 \(N^*\) 和淘汰阈值

实验关键数据¶

模拟实验¶

问题	DBCARE 风险	固定预算	固定置信度	说明
简单（大 gap）	最低	过度采样	接近	DBCARE 提前停止
困难（小 gap）	最低	预算不足	过度采样	DBCARE 自适应
极困难（极小 gap）	最低	大幅失败	大幅过采	DBCARE 选择"猜"

药物发现实验¶

在真实药物发现数据集上验证：DBCARE 在不同成本 \(c\) 下始终优于固定预算/置信度方法。

消融实验¶

配置	效果	说明
固定预算 + 最优 T	无法预知最优 T	需要知道 gap
固定置信度 + 最优 \(\delta\)	同上	需要知道 gap
DBCARE	自适应最优	不需要预知任何参数

关键发现¶

相变行为是该范式的独特现象：当 gap 太小时"猜"是最优的——这在固定预算/置信度中不存在
DBCARE 在简单和困难问题上都表现好：固定预算方法在简单问题上浪费采样，固定置信度在困难问题上过度采样
药物发现是天然应用场景：每次实验（arm pull）有真实成本
minimax 最优：DBCARE 的最坏情况风险匹配任何算法的最坏下界

亮点与洞察¶

"风险 = 惩罚 + 成本"是自然建模——类似于广告商的利润最大化，比固定预算/置信度更贴近实际
相变揭示了"知道何时放弃"的价值——gap 太小时最优策略是不采样直接猜
DBCARE 的自适应预算函数优雅地统一了固定预算和固定置信度的优点

局限性 / 可改进方向¶

\(\mathcal{R}_{SR}\) 在 \(H \to \infty\) 时上下界有加性 gap
假设 \(\sigma\)-sub-Gaussian 且已知 \(\sigma\) 和 \(B\)
仅考虑期望风险，未讨论高概率保证
成本 \(c\) 假设为常数且已知

评分¶

新颖性: ⭐⭐⭐⭐⭐ 全新的 BAI 范式 + 相变发现
实验充分度: ⭐⭐⭐⭐ 模拟+真实实验+与经典方法对比
写作质量: ⭐⭐⭐⭐⭐ 理论推导严谨，动机示例清晰
价值: ⭐⭐⭐⭐⭐ 对 BAI 理论和实践都有重要贡献

Balancing Performance and Costs in Best Arm Identification¶

一句话总结¶

研究背景与动机¶

方法详解¶

整体框架¶

关键设计¶

损失函数 / 训练策略¶

实验关键数据¶

主实验（2 臂高斯，\(\sigma^2=1, c=10^{-4}\)）¶

药物发现实验（5 臂，237 患者，二元和等级结局）¶

关键发现¶

亮点与洞察¶

局限性 / 可改进方向¶

相关工作与启发¶

评分¶

实验关键数据¶

模拟实验¶

药物发现实验¶

消融实验¶

关键发现¶

亮点与洞察¶

局限性 / 可改进方向¶

相关工作与启发¶

评分¶