![[2602.18186] Box Thirding: Anytime Best Arm Identification under Insufficient Sampling](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.18186] Box Thirding: Anytime Best Arm Identification under Insufficient Sampling
Summary
The paper introduces Box Thirding (B3), an innovative algorithm for Best Arm Identification (BAI) that operates efficiently under budget constraints, outperforming existing methods in limited-sampling scenarios.
Why It Matters
This research addresses the challenge of selecting the best option from a large set with limited resources, which is crucial in various applications such as machine learning and decision-making. B3's efficiency could lead to significant advancements in fields requiring optimal decision-making under uncertainty.
Key Takeaways
- B3 is designed for efficient Best Arm Identification under fixed-budget constraints.
- The algorithm uses iterative ternary comparisons to optimize decision-making.
- Empirical results demonstrate B3's superiority over existing methods like Successive Halving.
- B3 performs well even without prior knowledge of budget constraints.
- The approach is applicable in scenarios with large numbers of options.
Statistics > Machine Learning arXiv:2602.18186 (stat) [Submitted on 20 Feb 2026] Title:Box Thirding: Anytime Best Arm Identification under Insufficient Sampling Authors:Seohwa Hwang, Junyong Park View a PDF of the paper titled Box Thirding: Anytime Best Arm Identification under Insufficient Sampling, by Seohwa Hwang and Junyong Park View PDF HTML (experimental) Abstract: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. Comments: Subjects: Machine Learning (stat.ML); Machine Learning (cs.LG) MSC classes: 62L05 Cite as: arXiv:2602.18186 [stat.ML] (or arXiv:2602.18186v1 [stat.ML] for this...
