# Blocked Collaborative Bandits: Online Collaborative Filtering with Per-Item Budget Constraints

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 31 Oct 2023.

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

- [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)
- [On Context-Dependent Clustering of Bandits](https://mlsanity.com/paper/1608.03544/) (2016)
- [Improved Algorithm on Online Clustering of Bandits](https://mlsanity.com/paper/1902.09162/) (2019)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [Optimal Algorithms for Latent Bandits with Cluster Structure](https://mlsanity.com/paper/2301.07040/) (2023)
- [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)
- [Bayesian regression and Bitcoin](https://mlsanity.com/paper/1410.1231/) (2014)
- [Regret in Online Recommendation Systems](https://mlsanity.com/paper/2010.12363/) (2020)

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

- [Heterogeneous Multi-agent Multi-armed Bandits on Stochastic Block Models](https://mlsanity.com/paper/2502.08003/) (2025)
- [Sparse Linear Bandits with Blocking Constraints](https://mlsanity.com/paper/2410.20041/) (2024)

## Abstract (arXiv)

We consider the problem of blocked collaborative bandits 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. Our goal is to design algorithms that maximize the cumulative reward accrued by all the users over time, under the constraint that no arm of a user is pulled more than mathsfB times. This problem has been originally considered by citeBresler:2014, and designing regret-optimal algorithms for it has since remained an open problem. In this work, we propose an algorithm called textttB-LATTICE (Blocked Latent bAndiTs via maTrIx ComplEtion) that collaborates across users, while simultaneously satisfying the budget constraints, to maximize their cumulative rewards. Theoretically, under certain reasonable assumptions on the latent structure, with mathsfM users, mathsfN arms, mathsfT rounds per user, and mathsfC=O(1) latent clusters, textttB-LATTICE achieves a per-user regret of widetildeO(√mathsfT(1 + mathsfNmathsfM-1) under a budget constraint of mathsfB=Theta(log mathsfT). These are the first sub-linear regret bounds for this problem, and match the minimax regret bounds when mathsfB=mathsfT. Empirically, we demonstrate that our algorithm has superior performance over baselines even when mathsfB=1. textttB-LATTICE runs in phases where in each phase it clusters users into groups and collaborates across users within a group to quickly learn their reward models.