Abstract
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. If each user acts independently, then they would have to explore each arm independently and a regret of $\Omega(\sqrt{MNT})$ is unavoidable, where $M, N$ are the number of arms and users, respectively. Instead, we propose LATTICE (Latent bAndiTs via maTrIx ComplEtion) which allows exploration of the latent cluster structure to provide the minimax optimal regret of $\widetilde{O}(\sqrt{(M+N)T})$ when the number of clusters is $\tilde O(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(\log T)$ calls to an offline matrix completion oracle across all $T$ rounds.
Introduction
In modern recommendation systems, such as those used by streaming services and e-commerce platforms, the challenge is to provide personalized content to millions of users from a massive catalog of items. This scenario is often modeled as a multi-user multi-armed bandit (MAB) problem. However, the scale of these systems ($N$ users and $M$ items) makes independent learning for each user impractical, as the cumulative regret would scale as $\sqrt{MNT}$.
A key observation in these systems is that users often share similar preferences, forming latent clusters. If these clusters were known, users could share their exploration data, drastically reducing the regret. The challenge lies in the fact that cluster assignments and reward profiles are unknown a priori. This paper introduces LATTICE (LATent bAndiTs via maTrIx ComplEtion), the first algorithm to achieve minimax optimal regret in this setting by dynamically discovering the latent cluster structure.
The LATTICE Algorithm
LATTICE operates in phases of exponentially increasing length. It leverages the low-rank nature of the user-arm reward matrix—stemming from the small number of latent clusters—to facilitate collaborative learning. The algorithm consists of three primary components:
- Latent Cluster Discovery: In each phase, LATTICE uses an offline matrix completion oracle to estimate the reward matrix based on observed data. It then constructs a user graph where edges represent similarity in estimated rewards for high-value arms. The connected components of this graph define the current user clusters.
- Collaborative Arm Elimination: Once clusters are identified, users within each cluster pool their observations. This collective data allows the algorithm to identify and discard sub-optimal arms much faster than individual exploration would permit.
- Robustness and Fallback: To handle potential inaccuracies in clustering or cases with very few remaining arms, LATTICE incorporates a standard Upper Confidence Bound (UCB) mechanism. This ensures that the algorithm remains robust even when the latent structure is difficult to resolve.
Furthermore, the paper introduces the Relaxed Cluster Structure (RCS) model. Unlike strict clustering where users in a group are identical, RCS allows for slight variations in preferences among users in the same cluster, making the model more applicable to real-world scenarios.
Theoretical Results
The primary contribution of this work is the derivation of a minimax optimal regret bound. LATTICE achieves a regret of: $$\widetilde{O}(\sqrt{(M+N)T})$$ This bound assumes the number of clusters $C$ is small ($\tilde O(1)$). This result matches the theoretical lower bound, proving that LATTICE is as efficient as any algorithm can be in this setting. The success of the algorithm relies on "incoherence" assumptions, which imply that rewards are sufficiently spread across arms to allow the matrix completion oracle to function effectively.
Empirical Evaluation
The performance of LATTICE was evaluated against synthetic and real-world datasets:
- Synthetic Experiments: These tests confirmed that LATTICE effectively recovers the low-rank structure of reward matrices and achieves the predicted optimal regret.
- Real-World Benchmarks: The algorithm was tested on the MovieLens 10M, Netflix Prize, and Jester joke rating datasets. In all cases, LATTICE outperformed standard baselines, including independent UCB and the popular Alternating Minimization (AM) heuristic. Notably, LATTICE provides these gains while maintaining computational efficiency, requiring only $O(\log T)$ calls to the matrix completion oracle over the entire time horizon.
Conclusion
LATTICE represents a significant advancement in the field of multi-user bandits. By integrating matrix completion with online learning, it provides a principled way for users to "collaborate" in discovering optimal items. The algorithm's optimal regret guarantees and strong empirical performance make it a powerful tool for large-scale recommendation systems. Future work may explore relaxing the incoherence assumptions and further optimizing the algorithm's dependence on the number of clusters.
Summary updated