Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification
Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou
cs.CC
Sep 12, 2026 · v1
cs.AI cs.LG
TL;DR
The main theorems on gap-entropy lower and upper bounds for best-arm identification were formalized and machine-verified in Lean 4.
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.
Problem
Best-arm identification asks to identify the arm with the largest mean among n stochastic arms with probability at least 1-δ using few samples. Chen and Li (2016) conjectured that instance-wise sample complexity is characterized by the gap entropy up to an additive two-arm term.
Approach
For Gaussian arms with unit variance and means in [0,1], the order-oblivious instance-wise lower bound is derived via a change of distribution to instances with two best arms, bounding KL divergence using expected sample counts on the original instance. A single δ-correct algorithm is constructed using elimination that retains arms with largest empirical means, without prior knowledge of the gaps. The main theorems were formalized and proved in Lean 4.
Results
The order-oblivious instance-wise lower bound is Θ(H(I)[log(1/δ)+Ent(I)]), and a single algorithm attains it up to an additive two-arm term O(D log(e+log(e+D))), resolving both the gap-entropy and almost instance-wise optimality conjectures.