# Forced-exploration free Strategies for Unimodal Bandits

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

## Built on by (most cited first, 2 of 2)

- [Tuning Particle Accelerators with Safety Constraints using Bayesian Optimization](https://mlsanity.com/paper/2203.13968/) (2022)
- [UB3: Best Beam Identification in Millimeter Wave Systems via Pure Exploration Unimodal Bandits](https://mlsanity.com/paper/2301.03456/) (2022)

## Abstract (arXiv)

We consider a multi-armed bandit problem specified by a set of Gaussian or Bernoulli distributions endowed with a unimodal structure. Although this problem has been addressed in the literature (Combes and Proutiere, 2014), the state-of-the-art algorithms for such structure make appear a forced-exploration mechanism. We introduce IMED-UB, the first forced-exploration free strategy that exploits the unimodal-structure, by adapting to this setting the Indexed Minimum Empirical Divergence (IMED) strategy introduced by Honda and Takemura (2015). This strategy is proven optimal. We then derive KLUCB-UB, a KLUCB version of IMED-UB, which is also proven optimal. Owing to our proof technique, we are further able to provide a concise finite-time analysis of both strategies in an unified way. Numerical experiments show that both IMED-UB and KLUCB-UB perform similarly in practice and outperform the state-of-the-art algorithms.