Abstract
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.
Introduction
In the standard multi-armed bandit framework, an agent seeks to identify the best-performing option among $K$ choices. While typical research assumes these arms are unstructured, many real-world applications exhibit a unimodal structure: performance increases to a peak and then decreases. Examples include optimizing chemical reaction temperatures or determining the ideal price for a product to maximize revenue. In these cases, the relative performance of neighboring arms provides critical information about the location of the optimum.
This paper addresses the fixed-confidence best-arm identification (BAI) problem in unimodal bandits. The goal is to minimize the number of samples (empirical sample complexity) required to identify the best arm with a pre-specified confidence level $1-\delta$.
Theoretical Foundations: Lower Bounds and Local Rules
The authors provide a rigorous theoretical analysis through two primary lower bounds:
- Instance-Dependent Bound: This bound shows that asymptotically, only the best arm and its two immediate neighbors contribute significantly to the sampling cost. This "sparsity" implies that once the peak is located, the complexity becomes independent of the total number of arms $K$.
- Worst-Case Bound: Conversely, for moderate confidence levels, a cost proportional to $K$ is unavoidable. This represents the "search" phase required to find the vicinity of the peak.
To exploit the unimodal structure, the authors propose a Local Generalized Likelihood Ratio (GLR) stopping rule. Unlike standard rules that aggregate information from all arms, the local rule allows an algorithm to stop once an arm is confidently better than its immediate neighbors. In a unimodal setting, local optimality implies global optimality, allowing for more aggressive and efficient stopping.
Structured Algorithms
The paper introduces three algorithms designed to leverage unimodal structure:
- U-TaS & O-TaS (Track-and-Stop): These are variants of the Track-and-Stop algorithm. O-TaS incorporates optimism to focus exploration on promising regions. Both are proven to be asymptotically optimal for one-parameter exponential families.
- UniTT (Unimodal Top Two): A computationally efficient "Top Two" algorithm that selects a "leader" (current best guess) and a "challenger" (a neighbor) to sample. It is near-optimal for Gaussian distributions and matches the worst-case lower bound.
All proposed algorithms are implemented using Dynamic Programming, ensuring they run in $O(K)$ time and remain scalable for large arm sets.
Empirical Results
The algorithms were evaluated in synthetic Gaussian bandit environments, including random unimodal configurations and "flat" instances designed to test worst-case performance.
As illustrated in Figure 2, the unimodal-specific algorithms (U-TaS, UniTT, and O-TaS) significantly outperform standard unstructured baselines such as TaS, LMA, and FW. The "local" nature of the proposed methods allows them to quickly focus on the peak, whereas standard methods continue to sample sub-optimal arms in the tails.
In more challenging instances (Figure 1), the performance gap remains substantial. While U-TaS can exhibit higher variance in certain settings, UniTT and O-TaS consistently maintain low sample complexity. These results confirm that exploiting the "mountain-shaped" reward curve leads to dramatic improvements in efficiency, particularly as the number of arms $K$ grows.
Conclusion
This research provides the first comprehensive analysis of BAI in unimodal bandits, bridging the gap between theoretical lower bounds and practical, efficient algorithms. While the current work assumes a fixed linear ordering of arms, it sets the stage for future exploration into more complex unimodal structures on graphs or higher-dimensional grids.