New Gap Entropy Method Nears Instance-Wise Optimal Best-Arm Identification
Researchers introduce a quantity called gap entropy for the best-arm identification problem with independent Gaussian arms, where the goal is to find the highest-mean arm using as few samples as possible at a given confidence level. They show that an algorithm based on this measure comes close to the optimal sample complexity for each individual problem instance. The work is a theoretical contribution posted to arXiv and has not yet been peer reviewed.