Best-Arm Identification in Unimodal Bandits
This addresses a specific problem in bandit theory for researchers, offering incremental improvements by leveraging unimodal structure.
The paper tackles the best-arm identification problem in unimodal bandits, deriving lower bounds on stopping time and proposing modified algorithms (Track-and-Stop and Top Two) that are asymptotically optimal or near-optimal, with competitive empirical performance.
We study the fixed-confidence best-arm identification problem in unimodal bandits, in which the means of the arms increase with the index of the arm up to their maximum, then decrease. We derive two lower bounds on the stopping time of any algorithm. The instance-dependent lower bound suggests that due to the unimodal structure, only three arms contribute to the leading confidence-dependent cost. However, a worst-case lower bound shows that a linear dependence on the number of arms is unavoidable in the confidence-independent cost. We propose modifications of Track-and-Stop and a Top Two algorithm that leverage the unimodal structure. Both versions of Track-and-Stop are asymptotically optimal for one-parameter exponential families. The Top Two algorithm is asymptotically near-optimal for Gaussian distributions and we prove a non-asymptotic guarantee matching the worse-case lower bound. The algorithms can be implemented efficiently and we demonstrate their competitive empirical performance.