Box Thirding: Anytime Best Arm Identification under Insufficient Sampling

Seohwa Hwang; Junyong Park

stat.MLFeb 20, 2026

Box Thirding: Anytime Best Arm Identification under Insufficient Sampling

Authors: Seohwa Hwang, Junyong Park

Organizations: Department of Statistics, Seoul National University, Seoul, Republic of Korea

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.

Figures & tables

Figure 1: Toy example of remedian estimation: partition the data into three blocks and take their within-block medians

(2.8,\,5.3,\,4.8)

; taking the median of these medians yields

4.8

. Repeating this hierarchical “median-of-medians” construction produces an estimator that converges in probability to the population median.

Figure 2: Illustration of ARRANGE_BOX ( $l,j;D$ ) when $\hat{\mu}_{i_{1}}>\hat{\mu}_{i_{2}}>\hat{\mu}_{i_{3}}$ . The DISCARD operation is omitted for clarity.

Figure 3: Fraction of arms that are lifted, shifted, and discarded at a fixed level

l

Panel of Figure 4 — Figure 4: Simulation results on the NYCCC 893 dataset under three reward noise regimes. Curves indicate mean performance and shaded regions denote the 25%–75% quantile range.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: Simulation results on the NYCCC 893 dataset under different reward distributions. Curves indicate the mean performance, and shaded regions correspond to the 25%–75% quantile range.

Algorithm	Knowledge of $T$	Average Simple Regret	25% Quantile	75% Quantile
B3 (Ours)	No (Anytime)	0.0490	0.0290	0.0682
SH ( $r_{0}=1.7$ )	Yes (Fixed)	0.0446	0.0281	0.0652
SH ( $r_{0}=2.0$ )	Yes (Fixed)	0.0516	0.0290	0.0682
UCB-E	Yes (Fixed)	0.0664	0.0502	0.0749
BSH	No (Anytime)	0.0992	0.0587	0.1569
BUCB	No (Anytime)	0.1252	0.0682	0.1769

Appendix

Table 1: Simple regret for

N=128

and

T=896

(

T=N\log_{2}N

Algorithm	Knowledge of $T$	Average Simple Regret	25% Quantile	75% Quantile
B3 (Ours)	No (Anytime)	0.0268	0.0000	0.0502
SH ( $r_{0}=1.7$ )	Yes (Fixed)	0.0195	0.0000	0.0290
SH ( $r_{0}=2.0$ )	Yes (Fixed)	0.0288	0.0000	0.0507
UCB-E	Yes (Fixed)	0.0403	0.0222	0.0588
BSH	No (Anytime)	0.1531	0.0661	0.2475
BUCB	No (Anytime)	0.2558	0.2374	0.3039

Appendix

Table 2: Simple regret for

N=1,024

and

T=10,240

(

T=N\log_{2}N

Best-Arm Identification

Best-arm identification studies how to select the highest-reward option with few noisy evaluations while controlling the chance of error.

See all 48 papers

Learning with a Budget: Identifying the Best Arm with Resource Constraints
Feb 27, 2026Zitian Li, Wang Chi CheungBest-Arm Identification Multi-Armed Bandits
Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore
Fundamental Limitations of Fixed-Budget Best-Arm Identification
Jul 13, 2026Motti GoldbergerMulti-Armed Bandits Best-Arm Identification
Yale University
Fixed-Budget Constrained Best Arm Identification in Grouped Bandits
Mar 4, 2026Raunak Mukherjee, Sharayu MoharirBest-Arm Identification Multi-Armed Bandits
Indian Institute of Technology, Bombay · Dept. of Electrical Engineering, IIT Bombay

Feb 27, 2026J/K move · Enter open · S save

Learning with a Budget: Identifying the Best Arm with Resource Constraints

Zitian Li, Wang Chi Cheung

Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore

Best-Arm Identification Multi-Armed Bandits

Open paper AskPDF arXiv

In many applications, evaluating the effectiveness of different alternatives comes with varying costs or resource usage. Motivated by such heterogeneity, we study the Best Arm Identification with Resource Constraints (BAIwRC) problem, where an agent seeks to identify the best alternative (aka arm) in the presence of resource constraints. Each arm pull consumes one or more types of limited resources. We make two key contributions. First, we propose the Successive Halving with Resource Rationing (SH-RR) algorithm, which integrates resource-aware allocation into the classical successive halving framework on best arm identification. The SH-RR algorithm unifies the theoretical analysis for both the stochastic and deterministic consumption settings, with a new \textit{effective consumption measure

Abstract

Best-Arm Identification

Explore similar work

Learning with a Budget: Identifying the Best Arm with Resource Constraints

Fundamental Limitations of Fixed-Budget Best-Arm Identification

Fixed-Budget Constrained Best Arm Identification in Grouped Bandits