# Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms

arXiv: https://arxiv.org/abs/1405.5096 · HTML: https://mlsanity.com/paper/1405.5096/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2014.

## Built on by (most cited first, 30 of 37)

- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [Generalized non-stationary bandits](https://mlsanity.com/paper/2102.00725/) (2021)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [Tuning Particle Accelerators with Safety Constraints using Bayesian Optimization](https://mlsanity.com/paper/2203.13968/) (2022)
- [On Universally Optimal Algorithms for A/B Testing](https://mlsanity.com/paper/2308.12000/) (2023)
- [Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery](https://mlsanity.com/paper/2402.15739/) (2024)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Addressing the Long-term Impact of ML Decisions via Policy Regret](https://mlsanity.com/paper/2106.01325/) (2021)
- [Multi-armed Bandit Requiring Monotone Arm Sequences](https://mlsanity.com/paper/2106.03790/) (2021)
- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Adaptive Online Experimental Design for Causal Discovery](https://mlsanity.com/paper/2405.11548/) (2024)
- [Indexed Minimum Empirical Divergence for Unimodal Bandits](https://mlsanity.com/paper/2112.01452/) (2021)
- [Discounted Thompson Sampling for Non-Stationary Bandit Problems](https://mlsanity.com/paper/2305.10718/) (2023)
- [Adaptive Smooth Non-Stationary Bandits](https://mlsanity.com/paper/2407.08654/) (2024)
- [Pure Exploration with Feedback Graphs](https://mlsanity.com/paper/2503.07824/) (2025)
- [Black-box optimization of noisy functions with unknown smoothness](https://mlsanity.com/paper/2605.02462/) (2026)
- [Revealing graph bandits for maximizing local influence](https://mlsanity.com/paper/2605.00489/) (2026)
- [UB3: Best Beam Identification in Millimeter Wave Systems via Pure Exploration Unimodal Bandits](https://mlsanity.com/paper/2301.03456/) (2022)
- [Forced Exploration in Bandit Problems](https://mlsanity.com/paper/2312.07285/) (2023)
- [Multimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/2510.25811/) (2025)
- [Thompson Sampling for Unimodal Bandits](https://mlsanity.com/paper/2106.08187/) (2021)
- [Unimodal Mono-Partite Matching in a Bandit Setting](https://mlsanity.com/paper/2208.01511/) (2022)
- [UniRank: Unimodal Bandit Algorithm for Online Ranking](https://mlsanity.com/paper/2208.01515/) (2022)
- [Stochastic Direct Search Method for Blind Resource Allocation](https://mlsanity.com/paper/2210.05222/) (2022)
- [Clus-UCB: A Near-Optimal Algorithm for Clustered Bandits](https://mlsanity.com/paper/2508.02909/) (2025)
- [Threshold-Based Optimal Arm Selection in Monotonic Bandits: Regret Lower Bounds and Algorithms](https://mlsanity.com/paper/2509.02119/) (2025)
- [Physics-Informed Parametric Bandits for Beam Alignment in mmWave Communications](https://mlsanity.com/paper/2510.18299/) (2025)

## Abstract (arXiv)

We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investigated in (Cope 2009, Yu 2011). The set of arms is either discrete, in which case arms correspond to the vertices of a finite graph whose structure represents similarity in rewards, or continuous, in which case arms belong to a bounded interval. For discrete unimodal bandits, we derive asymptotic lower bounds for the regret achieved under any algorithm, and propose OSUB, an algorithm whose regret matches this lower bound. Our algorithm optimally exploits the unimodal structure of the problem, and surprisingly, its asymptotic regret does not depend on the number of arms. We also provide a regret upper bound for OSUB in non-stationary environments where the expected rewards smoothly evolve over time. The analytical results are supported by numerical experiments showing that OSUB performs significantly better than the state-of-the-art algorithms. For continuous sets of arms, we provide a brief discussion. We show that combining an appropriate discretization of the set of arms with the UCB algorithm yields an order-optimal regret, and in practice, outperforms recently proposed algorithms designed to exploit the unimodal structure.