# Optimal Algorithms for Latent Bandits with Cluster Structure

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 17 Jan 2023.

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

- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Latent Bandits Revisited](https://mlsanity.com/paper/2006.08714/) (2020)
- [Field Study in Deploying Restless Multi-Armed Bandits: Assisting Non-Profits in Improving Maternal and Child Health](https://mlsanity.com/paper/2109.08075/) (2021)
- [Improved Algorithm on Online Clustering of Bandits](https://mlsanity.com/paper/1902.09162/) (2019)
- [Stochastic Low-Rank Bandits](https://mlsanity.com/paper/1712.04644/) (2017)
- [Contextual Bandits with Latent Confounders: An NMF Approach](https://mlsanity.com/paper/1606.00119/) (2016)
- [Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling](https://mlsanity.com/paper/1912.03074/) (2019)
- [Latent Contextual Bandits and their Application to Personalized Recommendations for New Users](https://mlsanity.com/paper/1604.06743/) (2016)
- [Universal Matrix Completion](https://mlsanity.com/paper/1402.2324/) (2014)
- [Regret Guarantees for Item-Item Collaborative Filtering](https://mlsanity.com/paper/1507.05371/) (2015)
- [Bernoulli Rank-1 Bandits for Click Feedback](https://mlsanity.com/paper/1703.06513/) (2017)
- [A Latent Source Model for Online Collaborative Filtering](https://mlsanity.com/paper/1411.6591/) (2014)
- [Learning User Preferences in Non-Stationary Environments](https://mlsanity.com/paper/2101.12506/) (2021)
- [The Sample Complexity of Online One-Class Collaborative Filtering](https://mlsanity.com/paper/1706.00061/) (2017)
- [Online Low Rank Matrix Completion](https://mlsanity.com/paper/2209.03997/) (2022)
- [Regret Bounds and Regimes of Optimality for User-User and Item-Item Collaborative Filtering](https://mlsanity.com/paper/1711.02198/) (2017)
- [Neural Collaborative Filtering Bandits via Meta Learning](https://mlsanity.com/paper/2201.13395/) (2022)
- [Alternating Linear Bandits for Online Matrix-Factorization Recommendation](https://mlsanity.com/paper/1810.09401/) (2018)

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

- [Pretraining Decision Transformers with Reward Prediction for In-Context Multi-task Structured Bandit Learning](https://mlsanity.com/paper/2406.05064/) (2024)
- [Context-lumpable stochastic bandits](https://mlsanity.com/paper/2306.13053/) (2023)
- [Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints](https://mlsanity.com/paper/2311.03376/) (2023)
- [Learning to Call: A Field Trial of a Collaborative Bandit Algorithm for Improved Message Delivery in Mobile Maternal Health](https://mlsanity.com/paper/2507.16356/) (2025)
- [Finite-Time Frequentist Regret Bounds of Multi-Agent Thompson Sampling on Sparse Hypergraphs](https://mlsanity.com/paper/2312.15549/) (2023)
- [A Classification View on Meta Learning Bandits](https://mlsanity.com/paper/2504.04505/) (2025)
- [Adversarial Online Collaborative Filtering](https://mlsanity.com/paper/2302.05765/) (2023)
- [Online Matrix Completion: A Collaborative Approach with Hott Items](https://mlsanity.com/paper/2408.05843/) (2024)
- [Near Optimal Best Arm Identification for Clustered Bandits](https://mlsanity.com/paper/2505.10147/) (2025)
- [Latent Preference Bandits](https://mlsanity.com/paper/2508.05367/) (2025)
- [Latent Order Bandits](https://mlsanity.com/paper/2605.07304/) (2026)
- [Optimal Online Regret for Context-Lumpable Bandits](https://mlsanity.com/paper/2610.18258/) (2026)

## Abstract (arXiv)

We consider the problem of latent bandits with cluster structure where there are multiple users, each with an associated multi-armed bandit problem. These users are grouped into latent clusters such that the mean reward vectors of users within the same cluster are identical. At each round, a user, selected uniformly at random, pulls an arm and observes a corresponding noisy reward. The goal of the users is to maximize their cumulative rewards. This problem is central to practical recommendation systems and has received wide attention of late citegentile2014online, maillard2014latent. Now, if each user acts independently, then they would have to explore each arm independently and a regret of Omega(√mathsfMNT) is unavoidable, where mathsfM, mathsfN are the number of arms and users, respectively. Instead, we propose LATTICE (Latent bAndiTs via maTrIx ComplEtion) which allows exploitation of the latent cluster structure to provide the minimax optimal regret of widetildeO(√(mathsfM+mathsfN)mathsfT), when the number of clusters is widetildeO(1). This is the first algorithm to guarantee such strong regret bound. LATTICE is based on a careful exploitation of arm information within a cluster while simultaneously clustering users. Furthermore, it is computationally efficient and requires only O(logmathsfT) calls to an offline matrix completion oracle across all mathsfT rounds.