# Thompson Sampling for Bandits with Clustered Arms

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 39 references that are in the map.
- First posted on arXiv 6 Sep 2021.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Latent Bandits Revisited](https://mlsanity.com/paper/2006.08714/) (2020)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Multi-Armed Bandits with Correlated Arms](https://mlsanity.com/paper/1911.03959/) (2019)
- [Bounded Regret for Finite-Armed Structured Bandits](https://mlsanity.com/paper/1411.2919/) (2014)
- [Optimal Exploitation of Clustering and History Information in Multi-Armed Bandit](https://mlsanity.com/paper/1906.03979/) (2019)
- [Multi-Armed Bandits with Dependent Arms](https://mlsanity.com/paper/2010.09478/) (2020)
- [Regional Multi-Armed Bandits](https://mlsanity.com/paper/1802.07917/) (2018)
- [Categorized Bandits](https://mlsanity.com/paper/2005.01656/) (2020)
- [A Unified Approach to Translate Classical Bandit Algorithms to the Structured Bandit Setting](https://mlsanity.com/paper/1810.08164/) (2018)

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

- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Bilevel Multi-Armed Bandit-Based Hierarchical Reinforcement Learning for Interaction-Aware Self-Driving at Unsignalized Intersections](https://mlsanity.com/paper/2502.03960/) (2025)
- [LNUCB-TA: Linear-nonlinear Hybrid Bandit Learning with Temporal Attention](https://mlsanity.com/paper/2503.00387/) (2025)
- [ULTHO: Ultra-Lightweight yet Efficient Hyperparameter Optimization in Deep Reinforcement Learning](https://mlsanity.com/paper/2503.06101/) (2025)
- [Clustered Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/2308.10722/) (2023)
- [Latent Order Bandits](https://mlsanity.com/paper/2605.07304/) (2026)

## Abstract (arXiv)

We propose algorithms based on a multi-level Thompson sampling scheme, for the stochastic multi-armed bandit and its contextual variant with linear expected rewards, in the setting where arms are clustered. We show, both theoretically and empirically, how exploiting a given cluster structure can significantly improve the regret and computational cost compared to using standard Thompson sampling. In the case of the stochastic multi-armed bandit we give upper bounds on the expected cumulative regret showing how it depends on the quality of the clustering. Finally, we perform an empirical evaluation showing that our algorithms perform well compared to previously proposed algorithms for bandits with clustered arms.