SHPRR：一种受约束遗憾下的纯探索算法

最佳臂识别（BAI）通常以收集的样本数量来衡量实验成本。然而，在许多实际运行场景中，相对于现有的可信基线，探索成本同样重要。我们研究了同时受固定采样时域和遗憾预算约束的 BAI。不同于受约束纯探索中考虑的一般资源，遗憾具有独特的结构：相对于基线，采样表现更好的臂的成本更低。我们从理论上证明，在广泛使用的纯探索算法 Sequential Halving 的各个阶段中，探索的遗憾成本会逐渐降低。这一观察带来了对识别最佳臂概率的更优保证，并促使我们更有效地分配遗憾预算。我们提出 Sequential Halving with Proportional Regret Rationing（SHPRR），将更多遗憾预算预先分配，以便在剩余臂较多时进行更多探索。在合成数据和真实世界实例上的实验表明，与均匀遗憾分配和现有基线方法相比，SHPRR 能够提升最佳臂识别性能。