# Improved Algorithm on Online Clustering of Bandits

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2019.

## Built on by (most cited first, 30 of 38)

- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [Local Clustering in Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2103.00063/) (2021)
- [Graph Neural Bandits](https://mlsanity.com/paper/2308.10808/) (2023)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [Efficient Explorative Key-term Selection Strategies for Conversational Contextual Bandits](https://mlsanity.com/paper/2303.00315/) (2023)
- [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)
- [Neural Contextual Bandits for Personalized Recommendation](https://mlsanity.com/paper/2312.14037/) (2023)
- [Neural Bandit with Arm Group Graph](https://mlsanity.com/paper/2206.03644/) (2022)
- [Neural Collaborative Filtering Bandits via Meta Learning](https://mlsanity.com/paper/2201.13395/) (2022)
- [GPT4Rec: Graph Prompt Tuning for Streaming Recommendation](https://mlsanity.com/paper/2406.08229/) (2024)
- [Meta Clustering of Neural Bandits](https://mlsanity.com/paper/2408.05586/) (2024)
- [Combinatorial Bandits under Strategic Manipulations](https://mlsanity.com/paper/2102.12722/) (2021)
- [Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users](https://mlsanity.com/paper/2402.16312/) (2024)
- [Reward Imputation with Sketching for Contextual Batched Bandits](https://mlsanity.com/paper/2210.06719/) (2022)
- [Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Bandits](https://mlsanity.com/paper/2106.08902/) (2021)
- [Semi-Parametric Contextual Bandits with Graph-Laplacian Regularization](https://mlsanity.com/paper/2205.08295/) (2022)
- [Federated Linear Contextual Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2403.00116/) (2024)
- [AxiomVision: Accuracy-Guaranteed Adaptive Visual Model Selection for Perspective-Aware Video Analytics](https://mlsanity.com/paper/2407.20124/) (2024)
- [Online Corrupted User Detection and Regret Minimization](https://mlsanity.com/paper/2310.04768/) (2023)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [Online Clustering of Dueling Bandits](https://mlsanity.com/paper/2502.02079/) (2025)
- [Leveraging heterogeneous spillover in maximizing contextual bandit rewards](https://mlsanity.com/paper/2310.10259/) (2023)
- [Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints](https://mlsanity.com/paper/2311.03376/) (2023)
- [Adaptive Sample Sharing for Multi Agent Linear Bandits](https://mlsanity.com/paper/2309.08710/) (2023)
- [Comparative Performance of Collaborative Bandit Algorithms: Effect of Sparsity and Exploration Intensity](https://mlsanity.com/paper/2410.12086/) (2024)
- [Revisiting Clustering of Neural Bandits: Selective Reinitialization for Mitigating Loss of Plasticity](https://mlsanity.com/paper/2506.12389/) (2025)
- [When and Whom to Collaborate with in a Changing Environment: A Collaborative Dynamic Bandit Solution](https://mlsanity.com/paper/2104.07150/) (2021)
- [Bayesian Non-stationary Linear Bandits for Large-Scale Recommender Systems](https://mlsanity.com/paper/2202.03167/) (2022)

## Abstract (arXiv)

We generalize the setting of online clustering of bandits by allowing non-uniform distribution over user frequencies. A more efficient algorithm is proposed with simple set structures to represent clusters. We prove a regret bound for the new algorithm which is free of the minimal frequency over users. The experiments on both synthetic and real datasets consistently show the advantage of the new algorithm over existing methods.