# Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 38 references that are in the map.
- First posted on arXiv 1 Jan 2025.

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

- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Misspecified Linear Bandits](https://mlsanity.com/paper/1704.06880/) (2017)
- [Improved Algorithm on Online Clustering of Bandits](https://mlsanity.com/paper/1902.09162/) (2019)
- [Conversational Contextual Bandit: Algorithm and Application](https://mlsanity.com/paper/1906.01219/) (2019)
- [Local Clustering in Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2103.00063/) (2021)
- [OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits](https://mlsanity.com/paper/1905.10040/) (2019)
- [Problem-Complexity Adaptive Model Selection for Stochastic Linear Bandits](https://mlsanity.com/paper/2006.02612/) (2020)
- [Online Clustering of Contextual Cascading Bandits](https://mlsanity.com/paper/1711.08594/) (2017)
- [Greedy Algorithm almost Dominates in Smoothed Contextual Bandits](https://mlsanity.com/paper/2005.10624/) (2020)
- [Laplacian-regularized graph bandits: Algorithms and theoretical analysis](https://mlsanity.com/paper/1907.05632/) (2019)
- [Stochastic Linear Contextual Bandits with Diverse Contexts](https://mlsanity.com/paper/2003.02681/) (2020)
- [Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis](https://mlsanity.com/paper/2002.11332/) (2020)
- [Online Clustering of Bandits with Misspecified User Models](https://mlsanity.com/paper/2310.02717/) (2023)
- [Federated Online Clustering of Bandits](https://mlsanity.com/paper/2208.14865/) (2022)
- [Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users](https://mlsanity.com/paper/2402.16312/) (2024)
- [FedConPE: Efficient Federated Conversational Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2405.02881/) (2024)
- [Breaking the √T Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2205.09899/) (2022)
- [Online Corrupted User Detection and Regret Minimization](https://mlsanity.com/paper/2310.04768/) (2023)

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

- [Leveraging the Power of Conversations: Optimal Key Term Selection in Conversational Contextual Bandits](https://mlsanity.com/paper/2505.21393/) (2025)
- [A Unified Online-Offline Framework for Co-Branding Campaign Recommendations](https://mlsanity.com/paper/2505.22254/) (2025)
- [Steering Frozen LLMs: Adaptive Social Alignment via Online Prompt Routing](https://mlsanity.com/paper/2603.15647/) (2026)

## Abstract (arXiv)

The contextual multi-armed bandit (MAB) problem is crucial in sequential decision-making. A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters, utilizing shared features to improve learning efficiency. However, existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters. As a result, their theoretical analyses require several strong assumptions about the "diversity" of contexts generated by the environment, leading to impractical settings, complicated analyses, and poor practical performance. Removing these assumptions has been a long-standing open problem in the clustering of bandits literature. In this paper, we provide two solutions to this open problem. First, following the i.i.d. context generation setting in existing studies, we propose two novel algorithms, UniCLUB and PhaseUniCLUB, which incorporate enhanced exploration mechanisms to accelerate cluster identification. Remarkably, our algorithms require substantially weaker assumptions while achieving regret bounds comparable to prior work. Second, inspired by the smoothed analysis framework, we propose a more practical setting that eliminates the requirement for i.i.d. context generation used in previous studies, thus enhancing the performance of existing algorithms for online clustering of bandits. Our technique can be applied to both graph-based and set-based clustering of bandits frameworks. Extensive evaluations on both synthetic and real-world datasets demonstrate that our proposed algorithms consistently outperform existing approaches.