Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence

Yinan Li; Kwang-Sung Jun; Kapilan Balagopalan; Tuan Nguyen; Yao Zhao; Abbas Zaidi; Houssam Nassif

cs.LGOct 14, 2026

Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence

Authors: Yinan Li, Kwang-Sung Jun, Kapilan Balagopalan, Tuan Nguyen, Yao Zhao, Abbas Zaidi, Houssam Nassif

Organizations: University of Arizona · POSTECH CSE/GSAI · Meta Inc.

Abstract

We study fixed-budget adaptive experimentation aimed at maximizing the probability of obtaining sufficient posterior evidence that a recommended design's mean performance exceeds a target. Unlike best-arm identification, this objective does not require finding the best design. For Gaussian bandits with a Gaussian prior, we propose Halve-Then-Greedy (HTG), which combines a large initial balanced allocation, successive halving, and posterior-greedy sampling. We prove instance-dependent, finite-budget exponential bounds on posterior-failure probability that capture both separation from unfavorable arms and the presence of multiple favorable arms. On one-positive-arm families, we establish an asymptotic sample-complexity lower bound that HTG matches up to a logarithmic factor. We further analyze uniform sampling and sequential halving, revealing regimes where they require more samples than HTG by linear and logarithmic factors, respectively. Simulations illustrate HTG's sample-efficiency advantages and their dependence on instance structure.

Figures & tables

q_{r}=\begin{cases}\mathinner{\!\left\lfloor T/(3K)\right\rfloor},&r=1,\\ \mathinner{\!\left\lfloor T/(3Qk_{r})\right\rfloor},&r\geq 2.\end{cases}

Algorithm 1 Halve-Then-Greedy (HTG)

Figure 1: Posterior success probability versus budget. Left column: one arm has mean

0.1

, and the remaining arms have mean

-b

, with

b=0.02

(top) and

b=1

(bottom). Right column:

m

arms have mean

0.1

, and the remaining arms have mean

-1

, with

m=4

(top) and

m=16

(bottom). Error bars show pointwise

95\%

Wilson Monte Carlo confidence intervals based on

10{,}000

repetitions.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 2: Full negative-competitor sweep. One arm has mean

0.1

, and the remaining

31

arms have mean

-b

, with the value of

b

indicated in each panel. Curves show terminal posterior success probability versus budget for HTG, uniform sampling, and SH. Error bars show pointwise

95\%

Wilson Monte Carlo confidence intervals based on

10{,}000

repetitions.

Figure 3: Full positive-arm-count sweep. Among

K=32

arms,

m

have mean

0.1

and the remaining

K-m

have mean

-1

, with

m

indicated in each panel. Curves show terminal posterior success probability versus budget. Error bars show pointwise

95\%

Wilson Monte Carlo confidence intervals based on

10{,}000

repetitions.

Figure 4: Scaling with the number of arms on

\mu^{(K)}=(1/K,-1,\ldots,-1)

. Left: first tested budget reaching

90\%

empirical terminal success for each method. Right: the same thresholds divided by

K^{2}

for HTG,

K^{2}\log K

for SH, and

K^{3}

for uniform sampling. The logarithm is natural. Error bars show

95\%

bootstrap intervals. Thresholds are computed on the tested budget grids.

Figure 5: Terminal posterior success probability versus budget for the

K

-scaling study. Each setting uses

\mu^{(K)}=(1/K,-1,\ldots,-1)

, with

K\in\{8,16,32,64\}

. Error bars show pointwise

95\%

Wilson Monte Carlo confidence intervals based on

10{,}000

repetitions per method and budget. These curves underlie the threshold summaries in Figure 4 .

Figure 6: Allocation to the single positive arm for

\mu=(0.1,-b,\ldots,-b)

, with

K=32

and

b\in\{0.02,1\}

. The two rows correspond to budgets

T=2{,}048

and

T=7{,}200

. Curves show mean allocation fractions across

10{,}000

repetitions, with pointwise

95\%

Monte Carlo confidence intervals. The dotted vertical line marks the end of HTG’s halving phase.

Figure 7: Total allocation to positive arms. Among

K=32

arms,

m\in\{4,16\}

have mean

0.1

and the remaining arms have mean

-1

. The two rows correspond to budgets

T=2{,}048

and

T=7{,}200

. Curves show mean total positive-arm allocation fractions across

10{,}000

repetitions, with pointwise

95\%

Monte Carlo confidence intervals. The dotted vertical line marks the end of HTG’s halving phase.

Figure 8: Largest individual positive-arm allocation. Settings and row organization match Figure 7 . The largest positive-arm allocation fraction is computed within each repetition and then averaged over

10{,}000

repetitions. Error bars show pointwise

95\%

Monte Carlo confidence intervals. The dotted vertical line marks the end of HTG’s halving phase.

Gaussian Process Bandits

See all 15 papers

Rethinking Successive Rejects Algorithms
Oct 15, 2026Mohamed Khair, Junpei KomiyamaBest-Arm Identification Multi-Armed Bandits
Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP
Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors
Sep 12, 2023Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya +1Thompson Sampling Multi-Armed Bandits
Department of Quantitative Methods, Daniels School of Business, Purdue University, West Lafayette, IN 47906, USA. · Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706, USA. · Department of Statistics, Texas A&M University, College Station, TX 77843, USA.
Sharp Characterization of Bias in Post-Bandit Inference
Aug 2, 2026Lisu Wang, Yilun Chen, Jiaqi LuMulti-Armed Bandits Algorithmic Bias
School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen

Oct 15, 2026J/K move · Enter open · S save

Rethinking Successive Rejects Algorithms

Mohamed Khair, Junpei Komiyama

Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP

Best-Arm Identification Multi-Armed Bandits

Open paper AskPDF arXiv

In the best-arm identification problem, an algorithm adaptively selects arms to find the arm of the largest mean reward. Successive Rejects (SR) is a simple fixed-budget best-arm identification algorithm that eliminates one candidate arm at each phase. At first glance, SR seems to have limited adaptivity, since it follows predetermined phase lengths. However, for Gaussian arms with common variance, SR's worst-instance error exponent normalized by the popular complexity measure

H_1(P)

is optimal up to a constant factor, which partly explains why SR's performance is competitive compared with state-of-the-art adaptive sampling algorithms. In this paper, we extend the framework of SR by optimizing its predefined schedule of phase lengths. We formulate phase-schedule design as an optimization problem for the normalized error exponent. Then, we introduce a version of SR with the optimized schedule, which we call

H_1

-balanced Successive Rejects (

H_1

-SR). This schedule is optimal within the class of SR-type algorithms with deterministic equal-count schedules. For Gaussian arms with common variance,

H_1

-SR achieves at least

11/12

of the optimal normalized rate over all adaptive algorithms for every

K\ge2

, and this approximation ratio converges to one as

1-O(1/\log K)

K\to\infty

. This is a significant improvement over original SR, whose corresponding fraction of the optimal normalized rate converges to

1/4

. Finally, experiments on ten synthetic instances and two dataset-derived Gaussian benchmarks compare the optimized schedule with original SR at finite horizons. They show substantial gains on many instances while also exposing a regime in which more aggressive early elimination is costly.

Abstract

Gaussian Process Bandits

Explore similar work

Rethinking Successive Rejects Algorithms

Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors

Sharp Characterization of Bias in Post-Bandit Inference