# On Context-Dependent Clustering of Bandits

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2016.

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

- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Hierarchical Bayesian Bandits](https://mlsanity.com/paper/2111.06929/) (2021)
- [Local Clustering in Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2103.00063/) (2021)
- [Multi-facet Contextual Bandits: A Neural Network Perspective](https://mlsanity.com/paper/2106.03039/) (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)
- [Online Clustering of Bandits with Misspecified User Models](https://mlsanity.com/paper/2310.02717/) (2023)
- [Private and Byzantine-Proof Cooperative Decision-Making](https://mlsanity.com/paper/2205.14174/) (2022)
- [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)
- [Evaluating Online Bandit Exploration In Large-Scale Recommender System](https://mlsanity.com/paper/2304.02572/) (2023)
- [Optimal Multitask Linear Regression and Contextual Bandits under Sparse Heterogeneity](https://mlsanity.com/paper/2306.06291/) (2023)
- [GPT4Rec: Graph Prompt Tuning for Streaming Recommendation](https://mlsanity.com/paper/2406.08229/) (2024)
- [RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation](https://mlsanity.com/paper/2406.01389/) (2024)
- [Breaking the √T Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2205.09899/) (2022)
- [Linear Contextual Bandits with Hybrid Payoff: Revisited](https://mlsanity.com/paper/2406.10131/) (2024)
- [Adaptive Clustering and Personalization in Multi-Agent Stochastic Linear Bandits](https://mlsanity.com/paper/2106.08902/) (2021)
- [Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms](https://mlsanity.com/paper/2201.12700/) (2022)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Prospective Side Information for Latent MDPs](https://mlsanity.com/paper/2310.07596/) (2023)
- [Federated Linear Contextual Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2403.00116/) (2024)
- [Generalized Low-Rank Matrix Contextual Bandits with Graph Information](https://mlsanity.com/paper/2507.17528/) (2025)
- [Expert with Clustering: Hierarchical Online Preference Learning Framework](https://mlsanity.com/paper/2401.15062/) (2024)
- [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)

## Abstract (arXiv)

We investigate a novel cluster-of-bandit algorithm CAB for collaborative recommendation tasks that implements the underlying feedback sharing mechanism by estimating the neighborhood of users in a context-dependent manner. CAB makes sharp departures from the state of the art by incorporating collaborative effects into inference as well as learning processes in a manner that seamlessly interleaving explore-exploit tradeoffs and collaborative steps. We prove regret bounds under various assumptions on the data, which exhibit a crisp dependence on the expected number of clusters over the users, a natural measure of the statistical difficulty of the learning task. Experiments on production and real-world datasets show that CAB offers significantly increased prediction performance against a representative pool of state-of-the-art methods.