Box Thirding: Anytime Best Arm Identification under Insufficient Sampling

摘要

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 a Remedian Estimation strategy: in each iteration, three arms are compared—the best-performing arm is explored further, the median is retained for future comparisons, and the weakest is discarded. Even without prior knowledge of $T$, B3 achieves an $\epsilon$ -best arm misidentification probability comparable to Sequential Halving, which requires $T$ as a prior, applied to a randomly selected subset of $c_0$ arms that fit within the budget. Empirical results show that B3 outperforms existing methods for the limited budget constraint in terms of simple regret, as demonstrated on the New Yorker Cartoon Caption Contest dataset.