# Thompson Sampling for Unimodal Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 36 references that are in the map.
- First posted on arXiv 15 Jun 2021.

## Builds on (most cited first, 10 of 10)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.5096/) (2014)
- [Thompson Sampling Algorithms for Mean-Variance Bandits](https://mlsanity.com/paper/2002.00232/) (2020)
- [Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling](https://mlsanity.com/paper/1912.03074/) (2019)
- [Unimodal Thompson Sampling for Graph-Structured Arms](https://mlsanity.com/paper/1611.05724/) (2016)
- [Unimodal Bandits without Smoothness](https://mlsanity.com/paper/1406.7447/) (2014)

## Abstract (arXiv)

In this paper, we propose a Thompson Sampling algorithm for unimodal bandits, where the expected reward is unimodal over the partially ordered arms. To exploit the unimodal structure better, at each step, instead of exploration from the entire decision space, our algorithm makes decision according to posterior distribution only in the neighborhood of the arm that has the highest empirical mean estimate. We theoretically prove that, for Bernoulli rewards, the regret of our algorithm reaches the lower bound of unimodal bandits, thus it is asymptotically optimal. For Gaussian rewards, the regret of our algorithm is O(log T), which is far better than standard Thompson Sampling algorithms. Extensive experiments demonstrate the effectiveness of the proposed algorithm on both synthetic data sets and the real-world applications.