arXiv cs.AI· Georgina Nouli, Flore Sentenac, Maximilian Schiffer·· 14 小时前AI 评分20
SHPRR：带遗憾预算约束的纯探索最佳臂识别算法
SHPRR: An Algorithm for Pure Exploration under Constrained Regret
AI 导读
研究者提出 SHPRR（Sequential Halving with Proportional Regret Rationing），在固定采样预算与遗憾预算双重约束下做最佳臂识别，通过将遗憾预算前置以在臂数较多时投入更多探索。
正文 · 原文
Abstract:Best Arm Identification (BAI) conventionally measures the cost of experimentation by the number of samples collected. In many operational settings, however, the cost of exploration relative to a trusted baseline already in place is equally important. We study BAI under both a fixed sampling horizon and a regret budget. Unlike generic resources considered in constrained pure exploration, regret has a distinctive structure: sampling better arms is less costly relative to the baseline. We theoretically show that the regret cost of exploration decreases across the phases of Sequential Halving, a widely used pure-exploration algorithm. This observation yields improved guarantees on the probability of identifying the best arm and motivates a more effective allocation of the regret budget. We propose Sequential Halving with Proportional Regret Rationing (SHPRR), which front-loads the regret budget to allow more exploration when many arms remain. Experiments on synthetic and real-world instances show that SHPRR improves best-arm identification performance over uniform regret allocation and existing baselines.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2610.39837 [cs.LG] |
| (or arXiv:2610.39837v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.39837 arXiv-issued DOI via DataCite |
Submission history
From: Georgina Nouli [view email]
[v1]
Thu, 29 Oct 2026 11:15:57 UTC (765 KB)
来源：arXiv cs.AI · arxiv.org