Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

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)[(1/δ)+Ent(I)]). We also give a single δ-correct algorithm with expected sample complexity O (H(I)[(1/δ)+Ent(I)] +D (e+ (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.