Box Thirding: Anytime Best Arm Identification under Insufficient Sampling
This addresses the challenge of efficient arm selection in multi-armed bandit problems for scenarios with insufficient sampling, though it appears incremental as it builds on existing BAI methods.
The paper tackles the problem of Best Arm Identification (BAI) under fixed-budget constraints, particularly for large numbers of arms, by introducing Box Thirding (B3), an algorithm that achieves misidentification probability comparable to Successive Halving without requiring prior knowledge of the budget and outperforms existing methods in simple regret on a dataset.
We introduce Box Thirding (B3), a flexible and efficient algorithm for Best Arm Identification (BAI) under fixed-budget constraints. It is designed for both anytime BAI and scenarios with large N, where the number of arms is too large for exhaustive evaluation within a limited budget T. The algorithm employs an iterative ternary comparison: in each iteration, three arms are compared--the best-performing arm is explored further, the median is deferred for future comparisons, and the weakest is discarded. Even without prior knowledge of T, B3 achieves an epsilon-best arm misidentification probability comparable to Successive Halving (SH), which requires T as a predefined parameter, applied to a randomly selected subset of c0 arms that fit within the budget. Empirical results show that B3 outperforms existing methods under limited-budget constraints in terms of simple regret, as demonstrated on the New Yorker Cartoon Caption Contest dataset.