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

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.