Sample complexity bounds for finding best options in uncertain settings
Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification
Computational ComplexityArtificial IntelligenceMachine Learning
Summary
The paper focuses on a problem where you want to pick the best choice among many options, each giving random rewards with unknown averages. The authors clarify how the difficulty of this task depends on the differences in these averages and introduce a measure called gap entropy. They prove both lower and upper limits on how many samples you need to be confident about the best choice. Their results resolve a previous open question and provide a single method that is almost optimal across all problem instances without needing to know details in advance.
What this means in practice
- •For machine learning engineers: Use precise sample complexity bounds to design efficient algorithms for adaptive decision-making under uncertainty.
- •For data scientists: Optimize testing procedures to identify best options quickly based on observed data variability with guaranteed confidence.
A theory result. No direct application yet.
Authors
Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou
Abstract
In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-δ$, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in $[0,1]$. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance $I$, let $Δ_{[i]}$ be the gap between the largest and the $i$-th largest mean, let $H(I)=\sum_{i=2}^{n}Δ_{[i]}^{-2}$, and let Ent$(I)$ denote the entropy of the normalized complexities of its dyadic gap groups. For every $0<δ<0.1$, we show that the order-oblivious instance-wise lower bound is $ Θ (H(I)[\log(1/δ)+Ent(I)]). $ We also give a single $δ$-correct algorithm with expected sample complexity $ O ( H(I)[\log(1/δ)+Ent(I)] +D\log(e+\log(e+D))),D=Δ_{[2]}^{-2}, $ without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.