# Unimodal Thompson Sampling for Graph-Structured Arms

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2016.

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

- [Sliding-Window Thompson Sampling for Non-Stationary Settings](https://mlsanity.com/paper/2409.05181/) (2024)
- [Best-Arm Identification in Unimodal Bandits](https://mlsanity.com/paper/2411.01898/) (2024)
- [Problem Dependent View on Structured Thresholding Bandit Problems](https://mlsanity.com/paper/2106.10166/) (2021)
- [Link Adaptation Using Joint-Thompson Sampling](https://mlsanity.com/paper/2607.11075/) (2026)
- [Thompson Sampling for Unimodal Bandits](https://mlsanity.com/paper/2106.08187/) (2021)
- [A Minimalist Bayesian Framework for Stochastic Optimization](https://mlsanity.com/paper/2509.07030/) (2025)
- [Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Sampling](https://mlsanity.com/paper/2602.15972/) (2026)
- [MINTS: Minimalist Thompson Sampling](https://mlsanity.com/paper/2606.01655/) (2026)

## Abstract (arXiv)

We study, to the best of our knowledge, the first Bayesian algorithm for unimodal Multi-Armed Bandit (MAB) problems with graph structure. In this setting, each arm corresponds to a node of a graph and each edge provides a relationship, unknown to the learner, between two nodes in terms of expected reward. Furthermore, for any node of the graph there is a path leading to the unique node providing the maximum expected reward, along which the expected reward is monotonically increasing. Previous results on this setting describe the behavior of frequentist MAB algorithms. In our paper, we design a Thompson Sampling-based algorithm whose asymptotic pseudo-regret matches the lower bound for the considered setting. We show that -as it happens in a wide number of scenarios- Bayesian MAB algorithms dramatically outperform frequentist ones. In particular, we provide a thorough experimental evaluation of the performance of our and state-of-the-art algorithms as the properties of the graph vary.