cs.LGOct 29, 2026

SHPRR: An Algorithm for Pure Exploration under Constrained Regret

Authors: Georgina Nouli, Flore Sentenac, Maximilian Schiffer

Organizations: School of Management, Technical University of Munich, Munich, Germany · HEC Paris, Jouy-en-Josas, France

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Figure 1: SP and NSR across synthetic ( top ) and real-world ( bottom ) environments.
Figure 2: SP across the four synthetic environments as δ\delta varies from 0.3 to 0.
Figure 3: Performance analysis across three baseline arm selection criteria (from left to right): best arm, top 1%, and top 5%, evaluated under varying budget levels.
Figure 4: Phase-wise arm quality under a Poly reward configuration. Boxplots show the mean reward distribution among surviving arms at each phase, for four SHPRR variants with α∈{0.0,0.2,0.8,1.0}\alpha\in\{0.0,0.2,0.8,1.0\} . Significance brackets indicate tt -tests paired across seeds against the α=0.0\alpha=0.0 reference ( SH-RR ); a star ( ⋆\star ) marks the highest mean at each phase. Phase 9 is the final recommended arm.
Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 1: Reward distributions in the four baseline configurations of the synthetic environments.
Figure 2: Arm reward distributions in the four real-world environments: the three New Yorker Caption Contests (c511, c538, c780) and Criteo. Arms are sorted by mean reward in descending order.
Figure 3: Phase-wise arm quality under a polynomial reward family, for β∈{0.25,0.5,0.75,1.0}\beta\in\{0.25,0.5,0.75,1.0\} .
More in this topic

Best-Arm Identification

Best-arm identification studies how to select the highest-reward option with few noisy evaluations while controlling the chance of error.

See all 50 papers

Explore similar work

CardsList

  1. Learning with a Budget: Identifying the Best Arm with Resource Constraints

    Feb 27, 2026Zitian Li, Wang Chi CheungBest-Arm IdentificationMulti-Armed Bandits

    Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore

  2. Box Thirding: Anytime Best Arm Identification under Insufficient Sampling

    Feb 20, 2026Seohwa Hwang, Junyong ParkBest-Arm IdentificationMulti-Armed Bandits

    Department of Statistics, Seoul National University, Seoul, Republic of Korea

  3. Fundamental Limitations of Fixed-Budget Best-Arm Identification

    Jul 13, 2026Motti GoldbergerMulti-Armed BanditsBest-Arm Identification

    Yale University