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

Details

Best-arm identification is a core problem in sequential decision-making: given n stochastic arms, identify the one with the highest mean using as few samples as possible, with confidence at least 1-delta. Despite decades of work, the exact instance-wise sample complexity — meaning a bound that depends on the specific gaps between arm means for a given problem instance — was not fully characterized. Chen and Li (2016) conjectured that the tight characterization involves gap entropy: a function of the normalized complexities of dyadic gap groups. This paper resolves their conjecture, removing the dyadic-gap and monotonicity restrictions of prior lower bounds and eliminating the polylogarithmic factors that prior upper bounds carried. The result: for independent Gaussian rewards with unit variance, a single algorithm achieves the order-oblivious instance-wise lower bound up to an additive two-arm correction term. The lower bound is Θ(H(I)[log(1/δ)+Ent(I)]) and the algorithm achieves O(H(I)[log(1/δ)+Ent(I)] + D·log(e+log(e+D))), where D is the complexity of the two-arm subproblem. A distinctive feature: the main theorems were formalized and proved in Lean 4, a proof assistant — meaning the result is machine-verified, not just peer-reviewed. This is increasingly common in theoretical CS but still relatively rare in ML theory.