SHPRR：约束遗憾下纯探索的新算法
SHPRR: An Algorithm for Pure Exploration under Constrained Regret
AI 导读
arXiv 论文提出 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