mlsanityData to 7 Oct 2026

Best-Arm Identification in Unimodal Bandits

arXiv 2411.01898 ↗First posted 4 Nov 2024cs.LG cs.AIcited by 6

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 26 of its 37 references that are in the map. First posted on arXiv 4 Nov 2024.

Builds on

26 of 37 references.

References · 26

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  3. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  4. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  5. 2020Optimal Best-arm Identification in Linear Banditscited by 70
  6. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  7. 2019Pure Exploration with Multiple Correct Answerscited by 60
  8. 2017Improving the Expected Improvement Algorithmcited by 54
  9. 2019Fixed-Confidence Guarantees for Bayesian Best-Arm Identificationcited by 38
  10. 2014Unimodal Bandits: Regret Lower Bounds and Optimal Algorithmscited by 36
  11. 2022Top Two Algorithms Revisitedcited by 34
  12. 2017The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regimecited by 31
14 more
  1. 2019Solving Bernoulli Rank-One Bandits with Unimodal Thompson Samplingcited by 23
  2. 2020Structure Adaptive Algorithms for Stochastic Banditscited by 19
  3. 2021A/B/n Testing with Control in the Presence of Subpopulationscited by 17
  4. 2019Gradient Ascent for Active Exploration in Bandit Problemscited by 15
  5. 2022Information-Directed Selection for Top-Two Algorithmscited by 15
  6. 2018Sequential Test for the Lowest Mean: From Thompson to Murphy Samplingcited by 14
  7. 2019Optimal Best Markovian Arm Identification with Fixed Confidencecited by 12
  8. 2020The Influence of Shape Constraints on the Thresholding Bandit Problemcited by 11
  9. 2022Non-Asymptotic Analysis of a UCB-based Top Two Algorithmcited by 11
  10. 2016Unimodal Thompson Sampling for Graph-Structured Armscited by 8
  11. 2024Optimal Multi-Fidelity Best-Arm Identificationcited by 8
  12. 2022On the complexity of All varepsilon-Best Arms Identificationcited by 6
  13. 2023An Anytime Algorithm for Good Arm Identificationcited by 6
  14. 2021Indexed Minimum Empirical Divergence for Unimodal Banditscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 3.

6 papers.

  1. 2026Two-Fidelity Best-Action Identification for Stochastic Minimax Treecited by 1
  2. 2025Pure Exploration with Infinite Answerscited by 0
  3. 2025Non-Asymptotic Analysis of (Sticky) Track-and-Stopcited by 0
  4. 2025Intelligent Channel Allocation for IEEE 802.11be Multi-Link Operation: When MAB Meets LLMcited by 0
  5. 2026Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factorscited by 0
  6. 2026Cost-Aware Best-LLM Identification using Dueling Feedbackcited by 0