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.

Best arm identification algorithms often assume that every option can be sampled at least once. However, in many real-world applications, the available budget is too limited to evaluate all candidates. We propose Box Thirding (B3), a new anytime algorithm designed for this insufficient-sampling setting. B3 repeatedly compares groups of three candidates, promoting strong candidates, discarding weak ones, and deferring uncertain ones for future evaluation. This hierarchical strategy balances exploration and screening without requiring prior knowledge of the total budget. We further introduce a theoretical framework that decomposes errors into failures of candidate inclusion and failures of identification after inclusion. Under this framework, B3 achieves near-optimal screening efficiency and strong theoretical guarantees. Experiments on large-scale benchmark datasets show that B3 consistently outperforms existing anytime methods under limited-budget conditions.