Abstract
We generalize the setting of online clustering of bandits by allowing non-uniform distribution over user frequencies. A more efficient algorithm is proposed with simple set structures to represent clusters. We prove a regret bound for the new algorithm which is free of the minimal frequency over users. The experiments on both synthetic and real datasets consistently show the advantage of the new algorithm over existing methods.
Introduction
In recommendation systems, stochastic multi-armed bandits (MABs) are essential for balancing exploration and exploitation. To scale these systems, "online clustering of bandits" groups users with similar preferences, allowing them to share data—a form of collaborative filtering. However, traditional algorithms like CLUB face two significant hurdles. First, they assume uniform user visit frequencies, whereas real-world data typically follows a long-tail distribution. Infrequent users often "pollute" the clusters of frequent users, degrading performance. Second, they rely on complex graph-based structures where clusters are defined by connected components. This makes them slow to adapt, as separating dissimilar users requires cutting every path between them.
This paper introduces SCLUB (Set-based CLUstering of Bandits), a novel algorithm designed to overcome these limitations. By replacing graph-based representations with simple set structures and incorporating user frequency into the clustering logic, SCLUB achieves superior performance and a more robust theoretical regret bound.
Methodology: Set-Based Clustering
SCLUB models the recommendation task using stochastic linear bandits but fundamentally changes how user clusters are managed. Instead of maintaining a similarity graph, it uses simple sets to represent clusters. This shift enables two core operations:
- Split Operation: If a user's estimated preference vector or appearance frequency deviates significantly from their cluster's average,
SCLUBimmediately splits that user into a new cluster. This is significantly faster than waiting for graph edges to be severed. The Split Operation in SCLUB Source, p. 3
- Merge Operation: To prevent over-segmentation from aggressive splitting,
SCLUBincludes a reconciliation step. If two clusters exhibit highly similar estimated vectors and frequencies, they are merged back together. The Merge Operation in SCLUB Source, p. 3
By tracking both preference weights and appearance frequencies, SCLUB ensures that clustering is driven by comprehensive user behavior signals.
Empirical Evaluation and Results
The authors evaluated SCLUB against standard benchmarks like CLUB, LinUCB-One (global model), and LinUCB-Ind (individual models).
Datasets
- Synthetic: 1,000 users across 10 clusters with both uniform and long-tail frequency distributions.
- MovieLens (20M): Top 1,000 users and items from the standard movie recommendation dataset.
- Yelp: A sparse dataset of restaurant ratings, processed similarly to MovieLens.
Key Results
SCLUB consistently outperformed existing methods across all tests. On synthetic data with uniform distributions, it improved over CLUB by 5.94%. This advantage grew to 14.69% on long-tail distributions, highlighting its robustness to non-uniform user activity. On real-world datasets, SCLUB reduced regret by up to 14.84% on MovieLens and 16.24% on Yelp compared to CLUB.
Theoretically, SCLUB achieves a cumulative regret bound of $O(d\sqrt{mT \ln(T)})$, where $d$ is the feature dimension, $m$ is the number of clusters, and $T$ is time. Crucially, this bound is independent of $1/p_{min}$ (the inverse of the minimum user frequency), a term that often makes the theoretical bounds of previous algorithms practically useless in real-world "long-tail" scenarios.
Discussion and Insights
The success of SCLUB stems from treating user frequency as a primary clustering signal. This prevents low-frequency users from negatively impacting the models of high-frequency users. Furthermore, the set-based approach offers better agility than graph-based methods and provides a subtle privacy benefit: the system only needs aggregate cluster statistics and the current user's data, rather than a full peer-to-peer similarity graph.
While the current model assumes users in the same cluster share similar frequencies, future work could explore asymmetric relationships where infrequent users benefit from the data of frequent users without the reverse being true. Additionally, extending this set-based approach to simultaneous user-item co-clustering remains a promising direction.
Summary updated