Dual-Directed Algorithm Design for Efficient Pure Exploration
Chao Qin Wei You
We consider pure-exploration problems in the context of stochastic sequential
adaptive experiments with a finite set of alternative options. The goal of the
decision-maker is to accurately answer a query question regarding the
alternatives with high confidence with minimal measurement efforts. A typical
query question is to identify the alternative with the best performance,
leading to ranking and selection problems, or best-arm identification in the
machine learning literature. We focus on the fixed-precision setting and derive
a sufficient condition for optimality in terms of a notion of strong
convergence to the optimal allocation of samples. Using dual variables, we
characterize the necessary and sufficient conditions for an allocation to be
optimal. The use of dual variables allow us to bypass the combinatorial
structure of the optimality conditions that relies solely on primal variables.
Remarkably, these optimality conditions enable an extension of top-two
algorithm design principle, initially proposed for best-arm identification.
Furthermore, our optimality conditions give rise to a straightforward yet
efficient selection rule, termed information-directed selection, which
adaptively picks from a candidate set based on information gain of the
candidates. We outline the broad contexts where our algorithmic approach can be
implemented. We establish that, paired with information-directed selection,
top-two Thompson sampling is (asymptotically) optimal for Gaussian best-arm
identification, solving a glaring open problem in the pure exploration
literature. Our algorithm is optimal for $\epsilon$-best-arm identification and
thresholding bandit problems. Our analysis also leads to a general principle to
guide adaptations of Thompson sampling for pure-exploration problems. Numerical
experiments highlight the exceptional efficiency of our proposed algorithms
relative to existing ones.