SOURCE-LINKED INTELLIGENCE

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

arXiv · AI, language, vision and robotics · article · Sep 12, 2026 · UTC

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]}

Read original source ↗ Open in workspace

recordType

paper

region

Global