arXiv cs.AI· Georgina Nouli, Flore Sentenac, Maximilian Schiffer·· 13 小时前AI 评分20
SHPRR：带遗憾预算约束的纯探索最佳臂识别算法
SHPRR: An Algorithm for Pure Exploration under Constrained Regret
AI 导读
研究者提出 SHPRR（Sequential Halving with Proportional Regret Rationing），在固定采样预算与遗憾预算双重约束下做最佳臂识别，通过将遗憾预算前置以在臂数较多时投入更多探索。
正文 · AI 翻译
摘要：最佳臂识别（BAI）传统上以收集的样本数量来衡量实验成本。然而，在许多实际运营场景中，相对于已就位的可信基线而言，探索成本同样重要。我们在固定采样时域和遗憾预算两种设定下研究 BAI。与受限纯探索中考虑的一般资源不同，遗憾具有独特结构：相对于基线，采样更优臂的成本更低。我们从理论上证明，在广泛使用的纯探索算法 Sequential Halving 的各阶段中，探索的遗憾成本会逐渐降低。这一观察结果改善了对识别最佳臂概率的保证，并促使我们更有效地分配遗憾预算。我们提出按比例分配遗憾的 Sequential Halving（SHPRR），它将遗憾预算前置，以便在剩余臂较多时允许更多探索。在合成和真实实例上的实验表明，SHPRR 相比均匀遗憾分配和现有基线提升了最佳臂识别性能。
| 学科： | 机器学习（cs.LG）；人工智能（cs.AI） |
| 引用为： | arXiv:2610.39837 [cs.LG] |
| （或 arXiv:2610.39837v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.39837 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Georgina Nouli [查看邮箱]
[v1]
2026年10月29日 星期四 11:15:57 UTC（765 KB）
来源：arXiv cs.AI · arxiv.org