Collaborative Filtering Bandits

Shuai Li, Alexandros Karatzoglou, Claudio Gentile

TL;DR

COFIBA (COllaborative FIltering BAndit) is a novel algorithm that brings the power of collaborative filtering to the dynamic world of contextual bandits. By adaptively clustering both users and items based on real-time interaction data, it significantly improves recommendation accuracy (CTR) in "cold-start" and highly fluid environments like news feeds and digital advertising.

What Problem Does This Paper Address?

Traditional Collaborative Filtering (CF) relies on static historical data to find patterns (e.g., "users who liked X also liked Y"). However, in domains like news recommendation or online ads, the "universe" of items and users changes every minute. Standard CF models break down here because they can't handle this level of volatility or the "cold-start" problem (new users/items with no history).

On the other hand, Contextual Multi-Armed Bandits are great at balancing exploration (trying new things) and exploitation (picking winners) in dynamic settings. But most bandit algorithms treat users in isolation. They miss the "collaborative effect"—the fact that similar users likely have similar tastes. The challenge is: how do you leverage these group patterns dynamically without the massive computational overhead of traditional matrix factorization?

Methods

The authors introduce COFIBA, which performs adaptive two-sided clustering. Here’s how it works:

  1. User-Side Clustering: For every item, the algorithm maintains a graph of users. If two users react similarly to an item, they stay connected. If their predicted preferences diverge significantly (beyond a calculated "confidence bound"), the edge between them is deleted. This creates clusters of users who share tastes for specific types of content.
  2. Item-Side Clustering: Simultaneously, the algorithm groups items together if they induce the same clusters on the user side. If Item A and Item B both split the user base into the same two groups, they are considered "similar" in terms of how they appeal to the audience.
  3. Graph Sparsification: To avoid the $O(n^2)$ memory nightmare of maintaining full user-item graphs, the authors use Erdos-Renyi random graphs. They start with a sparse initial graph that is mathematically guaranteed to reveal the underlying clusters as edges are deleted, making the algorithm scalable to millions of users.
  4. Preference Estimation: It uses a linear least-squares approach (similar to LinUCB) to estimate user preferences within these dynamic clusters, allowing it to "borrow" information from similar users to make better guesses for new ones.

Datasets

The algorithm was evaluated on three large-scale, real-world datasets:

  • Yahoo! News: A standard benchmark for news recommendation (30M visits, ~18K users).
  • Telefonica: An advertising dataset from a major Spanish ISP (15M records, millions of users).
  • Avazu: A public mobile advertising dataset (40M impressions, millions of users).

Key Insights and Ideas

  • The "Two-Sided" Aha Moment: Most previous "clustering bandits" only grouped users. COFIBA recognizes that an item isn't just a static vector; it's a probe that reveals user structure. By clustering items based on the user-partitions they create, the model captures much more nuanced preference patterns.
  • Edge Deletion as Learning: Instead of trying to "find" clusters (like K-means), the algorithm starts with everyone connected and "cuts" ties as it gains evidence of differences. This is a much more natural fit for the exploration-exploitation trade-off.
  • Information Propagation: Because users are clustered, when the system learns something about User A, that knowledge immediately improves the recommendations for User B (their neighbor in the graph). This is why the algorithm excels at the "cold-start" problem.

Key Results

  • Superior CTR: COFIBA consistently outperformed state-of-the-art baselines like CLUB (user-side clustering only) and LinUCB (no clustering) across all datasets.
  • Cold-Start Performance: The gains were most dramatic in the early stages of the simulation. By grouping users quickly, COFIBA reached high click-through rates much faster than independent bandit models.
  • Theoretical Soundness: The authors provide a regret analysis showing that the algorithm achieves $O(\sqrt{T})$ cumulative regret, which is the theoretical gold standard for bandit efficiency.
  • Scalability: Despite the complexity of two-sided clustering, the graph sparsification techniques allowed the algorithm to run on datasets with millions of users and items.

Limitations and Future Work

  • Feature Inference: In this paper, the authors used "one-hot" encoding (treating items as unique IDs) because the datasets lacked rich metadata. They suggest that in the future, COFIBA could be combined with deep learning or matrix factorization to infer latent features first, then cluster on top of them.
  • Computational Latency: While scalable in terms of memory, the graph maintenance and connected-component calculations make it slightly slower than simpler, non-clustering algorithms.
  • Meta-Bandits: The authors propose exploring "meta-bandit" frameworks that could switch between different clustering strategies as the system matures from a cold start to a steady state.

Summary updated

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 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.
BibTeX
@inproceedings{li2016collaborative,
  author = {Shuai Li and Alexandros Karatzoglou and Claudio Gentile},
  title = {{Collaborative Filtering Bandits}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2016},
  doi = {10.1145/2911451.2911548},
}

Loading related content...

Figure