Abstract
Classical collaborative filtering and content-based filtering methods try to learn a static recommendation model given training data. These approaches are far from ideal in highly dynamic recommendation domains such as news recommendation and computational advertisement, where the set of items and users is very fluid. In this work, we investigate an adaptive clustering technique for content recommendation based on exploration-exploitation strategies in contextual multi-armed bandit settings. Our algorithm, COFIBA, takes into account the collaborative effects that arise due to the interaction of the users with the items, by dynamically grouping users based on the items under consideration and, at the same time, grouping items based on the similarity of the clusterings induced over the users. The resulting algorithm thus takes advantage of preference patterns in the data in a way akin to collaborative filtering methods. We provide an empirical analysis on medium-size real-world datasets, showing scalability and increased prediction performance (as measured by click-through rate) over state-of-the-art methods for clustering bandits. We also provide a regret analysis within a standard linear stochastic noise setting.
Introduction
Traditional recommendation systems often rely on Collaborative Filtering (CF) to identify patterns based on historical interactions. While effective in static environments, CF struggles in highly volatile domains like news feeds or digital advertising, where new users and items appear constantly—the "cold-start" problem. Conversely, Contextual Multi-Armed Bandits excel at balancing exploration and exploitation in dynamic settings but often treat users in isolation, failing to leverage the "collaborative effect" where similar users share preferences.
The challenge lies in dynamically capturing these group patterns without the prohibitive computational costs of traditional matrix factorization. COFIBA addresses this by bringing collaborative filtering principles into the bandit framework through adaptive clustering.
Methodology
COFIBA (COllaborative FIltering BAndit) implements an adaptive two-sided clustering mechanism that evolves as real-time interaction data is collected. Unlike previous clustering bandits that only group users, COFIBA recognizes that an item acts as a probe revealing user structure.
Adaptive Two-Sided Clustering
The algorithm maintains a dual-graph structure to capture dependencies:
- User-Side Clustering: For each item cluster, the algorithm maintains a graph of users. Users remain connected if their predicted preferences are similar. If their reactions diverge beyond a calculated confidence bound, the edge between them is deleted, eventually forming clusters of users with shared tastes for specific content types.
- Item-Side Clustering: Simultaneously, items are grouped if they induce identical partitions on the user side. If two items appeal to the same audience segments, they are considered similar.
Scalability and Estimation
To maintain efficiency with millions of users, COFIBA utilizes Erdos-Renyi random graphs for sparsification. Starting with a sparse initial graph, the algorithm is mathematically guaranteed to reveal underlying clusters through edge deletion. Preference estimation is performed using a linear least-squares approach (similar to LinUCB), allowing the model to "borrow" information from neighbors in a cluster to improve predictions for new or infrequent users.
Experimental Evaluation
The algorithm was evaluated against three large-scale real-world datasets: Yahoo! News (30M visits), Telefonica (15M records), and Avazu (40M impressions).
Key Results
COFIBA consistently outperformed state-of-the-art baselines, including CLUB (user-side clustering only) and LinUCB (no clustering). The performance gains were particularly notable in the early stages of simulation, demonstrating superior handling of the cold-start problem through rapid information propagation across user clusters.
The algorithm also demonstrated theoretical efficiency, achieving $O(\sqrt{T})$ cumulative regret, the gold standard for bandit algorithms. Despite the complexity of two-sided clustering, graph sparsification ensured the method remained scalable to large industrial datasets.
Conclusion
COFIBA bridges the gap between collaborative filtering and contextual bandits by treating items as probes that reveal user structure. By adaptively "cutting" ties between dissimilar users and items, it propagates information across clusters to accelerate learning. Future work includes integrating deep learning for latent feature inference and exploring meta-bandit frameworks to adapt clustering strategies as systems mature from a cold start to a steady state.
Summary updated