Algorithm improves best choice finding under budget limits
SHPRR: An Algorithm for Pure Exploration under Constrained Regret
Machine LearningArtificial Intelligence
Summary
Sometimes it's important to find the best option in a group quickly while keeping the cost of trying options low compared to a trusted choice. The authors studied how to balance exploring many options without exceeding a set regret budget, which accounts for how much worse exploration is compared to the trusted baseline. They improved an existing method by assigning more 'regret budget' early on, allowing better identification of the best option. Tests on both fake and real problems showed this new method works better than others.
What this means in practice
- •For online advertising teams: Optimize ad selection by efficiently identifying the best-performing campaigns while limiting performance loss compared to current ads.
- •For clinical trial designers: Plan trials to identify the most effective treatments with controlled patient risk relative to standard care.
Authors
Georgina Nouli, Flore Sentenac, Maximilian Schiffer
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.