Adaptive sampling method cuts experiments to confirm good designs faster
Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
Machine Learning
Summary
Sometimes, when trying to find a good choice among many options, it's enough to confirm one is good rather than find the absolute best. The authors study how to allocate limited tests to boost the chance of proving a chosen option meets a target. They introduce a smart way called Halve-Then-Greedy that starts broadly, narrows focus step by step, then samples where it counts most. Their method requires fewer tests than some existing approaches and comes with mathematical guarantees about its effectiveness.
What this means in practice
- •For product testing teams: Allocate testing resources efficiently to verify if a product design meets performance goals within limited trials.
- •For clinical trial designers: Plan experiments that quickly establish if a treatment surpasses a target effect size without needing to identify the absolute best treatment.
Tested on simulated data.
Authors
Yinan Li, Kwang-Sung Jun, Kapilan Balagopalan, Tuan Nguyen, Yao Zhao, Abbas Zaidi, Houssam Nassif
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.