Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
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 \emph{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.
Related
- Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling
- Instance-Optimal Adaptive Location Estimation via Multiscale Mid-Summaries
- Finite-Mask Gaussian-Process Reconstruction on a Periodic Sensor Ring: Mask-Geometry Dependence, Fourier-Mode Coupling, and Posterior Trace
- Accelerating posterior sampling in Bayesian inverse problems with diffusion models: an online-offline perspective
- Learning to Replace MCMC in Split-Gibbs Diffusion Posterior Sampling via Deep Unfolding
BibTeX
@misc{li2026halvethengreedy,
title = {{Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence}},
author = {Yinan Li and Kwang-Sung Jun and Kapilan Balagopalan and Tuan Nguyen and Yao Zhao and Abbas Zaidi and Houssam Nassif},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20997},
eprint = {2610.20997},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20997},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
AU - Yinan Li
AU - Kwang-Sung Jun
AU - Kapilan Balagopalan
AU - Tuan Nguyen
AU - Yao Zhao
AU - Abbas Zaidi
AU - Houssam Nassif
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20997
UR - https://arxiv.org/abs/2610.20997
AB - 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 \emph{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.
ER -