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. If each user acts independently, a regret of $\Omega(\sqrt{MNT})$ is unavoidable, where $M$ and $N$ 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 $\widetilde{O}(\sqrt{(M+N)T})$, when the number of clusters is $\widetilde{O}(1)$. LATTICE is based on a careful exploitation of arm information within a cluster while simultaneously clustering users. 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 Netflix or YouTube, platforms must navigate the preferences of millions of users ($N$) across millions of potential items or "arms" ($M$). Traditional Multi-Armed Bandit (MAB) algorithms typically follow one of two suboptimal paths: treating every user as an independent entity, which leads to slow learning and high regret, or relying on observed demographic features, which are often noisy proxies for actual taste.
This paper addresses the Multi-User Multi-Armed Bandits with Latent Clusters (MAB-LC) problem. In this setting, users belong to hidden clusters with identical or highly similar preferences. The challenge lies in the fact that neither the cluster assignments nor the reward distributions are known a priori. The proposed solution, LATTICE, bridges this gap by treating the reward table as a low-rank matrix and using matrix completion to allow users to collaboratively learn optimal strategies.
The LATTICE Algorithm
LATTICE (Latent bAndiTs via maTrIx ComplEtion) operates in discrete phases of exponentially increasing length. The algorithm's efficiency stems from two core mechanisms:
1. Low-Rank Matrix Completion
LATTICE views the user-arm reward space as a large, low-rank matrix $P$. In each phase, the algorithm collects random observations and utilizes an offline matrix completion oracle. This allows the system to estimate rewards for arms a user has never pulled by leveraging data from "similar" users across the network. This "de-noising" process is the key to breaking the linear dependence on the number of users and arms.
2. Recursive Clustering and Arm Elimination
Using the estimates derived from matrix completion, LATTICE performs a two-step refinement process:
- User Clustering: The algorithm constructs a graph where users are connected if their estimated reward vectors are sufficiently similar. It then partitions users into "nice" subsets based on these connected components.
- Arm Elimination: Within these identified subsets, LATTICE identifies and discards sub-optimal arms. As the phases progress, the set of active arms for each cluster shrinks, focusing exploration only on the most promising candidates.
Crucially, LATTICE is computationally efficient, requiring only $O(\log T)$ calls to the matrix completion oracle over the entire time horizon $T$.
Theoretical Significance
The primary breakthrough of LATTICE is its achievement of the theoretical lower bound for regret. While independent learning scales with $\sqrt{MNT}$, LATTICE scales with $\sqrt{(M+N)T}$. In a large-scale system with a million users and a million arms, this reduces the scaling factor from $10^6$ to approximately $10^3$, representing a massive gain in efficiency. Furthermore, the algorithm is robust to Relaxed Cluster Structures (RCS), where users in a cluster have rewards that are "close enough" rather than strictly identical.
Empirical Evaluation
The authors evaluated LATTICE using synthetic simulations and three real-world recommendation datasets:
- MovieLens 10M: Restricted to the top 200 users and 200 movies.
- Netflix Prize: Restricted to 200 users and 200 movies.
- Jester (Joke Recommendations): Restricted to 100 users and 100 jokes.
In these tests, LATTICE significantly outperformed standard benchmarks such as UCB (Upper Confidence Bound) and Alternating Minimization (AM) heuristics. The algorithm demonstrated a unique ability to "prune" large chunks of suboptimal items for entire groups of users simultaneously, resulting in a much flatter regret curve in later rounds.
Limitations and Future Work
While LATTICE provides a significant leap forward, its theoretical guarantees rely on "incoherence" assumptions—the requirement that reward information is spread across the matrix rather than concentrated in a few entries. Additionally, while the algorithm is efficient, the initial phases still require a period of pure exploration. Future research could focus on integrating prior side-information (hybrid contextual/latent models) to mitigate this "cold start" period and further optimize regret scaling as the number of clusters $C$ grows.
Summary updated