B3算法在有限预算下高效识别最优选项，无需预知总次数。
Box Thirding: Anytime Best Arm Identification under Insufficient Sampling
- 每轮比较三支候选，优者继续、中者留待、劣者淘汰。
- 在新纽约客漫画标题竞赛数据集上，简单后悔值低于现有方法。
- 适合大规模选项中快速找最优，尤其预算紧张时。
我们提出Box Thirding（B3），一种灵活高效的固定预算最佳臂识别（BAI）算法。适用于任意时间点输出结果及大规模臂数场景（N过大无法在有限预算T内穷举评估）。算法采用迭代三元比较：每轮比较三支臂，表现最优者继续探索，中等者延后比较，最差者剔除。即使未预先知晓预算T，B3的ε-最优臂误判概率仍可媲美需预设T的逐次减半法（SH），后者仅在随机选取的c0支臂子集中应用。实验表明，在新纽约客漫画标题竞赛数据集上，B3在有限预算下显著降低简单后悔值，优于现有方法。
原文摘要 · Abstract (English)
We introduce Box Thirding (B3), a flexible and efficient algorithm for Best Arm Identification (BAI) under fixed-budget constraints. It is designed for both anytime BAI and scenarios with large N, where the number of arms is too large for exhaustive evaluation within a limited budget T. The algorithm employs an iterative ternary comparison: in each iteration, three arms are compared--the best-performing arm is explored further, the median is deferred for future comparisons, and the weakest is discarded. Even without prior knowledge of T, B3 achieves an epsilon-best arm misidentification probability comparable to Successive Halving (SH), which requires T as a predefined parameter, applied to a randomly selected subset of c0 arms that fit within the budget. Empirical results show that B3 outperforms existing methods under limited-budget constraints in terms of simple regret, as demonstrated on the New Yorker Cartoon Caption Contest dataset.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。