Introduction
Online recommendation systems are fundamentally defined by the Exploration-Exploitation (EE) dilemma: a system must decide whether to recommend items it knows a user likes (exploitation) or present new items to learn more about the user's evolving preferences (exploration). While clustering-based bandits have emerged as a popular solution to this problem by grouping similar users to share data, they often suffer from the "bad neighbor" problem. These systems frequently rely on static attributes or rigid graphs that fail to adapt to changing tastes, leading to poor recommendations for users who do not fit neatly into predefined clusters.
This paper introduces CoCoB (Adaptive Collaborative Combinatorial Bandits), a framework designed to solve these limitations through a two-sided bandit architecture and a Bayesian similarity threshold. By dynamically deciding when to trust group preferences versus individual data, CoCoB achieves superior recommendation accuracy and adaptability.
The CoCoB Framework
CoCoB decouples the recommendation process into two distinct but interconnected tasks: identifying the right neighbors and selecting the optimal items.
1. The User-Bandit: Dynamic Neighbor Selection
Instead of relying on static profiles (e.g., age or location), the User-Bandit utilizes an enhanced Bayesian model based on Thompson Sampling. It treats every other user in the system as a potential "arm." For every pair of users, the system calculates a similarity probability.
Collaboration is only triggered if this probability exceeds a specific threshold ($\gamma$). If no other users meet this statistical requirement, the system intelligently defaults to using only the target user’s individual interaction history. This acts as a safety valve, preventing "polluted" data from dissimilar neighbors from degrading the recommendation quality.
2. The Item-Bandit: Combinatorial List Generation
Once the neighbor set is established, the Item-Bandit—a combinatorial bandit—treats individual items as arms to generate a diverse list of $K$ recommendations. It employs an Upper Confidence Bound (UCB) approach to balance the selection of historically popular items with new items that require further exploration. By separating neighbor selection from item selection, CoCoB can adaptively combine collaborative "group wisdom" with personal taste on the fly.
Experimental Methodology
The researchers evaluated CoCoB using the replayer method, simulating online learning environments using historical logs from three real-world e-commerce datasets:
- IJCAI-15: A large-scale dataset of user-item interactions.
- Retailrocket: Data from a real-world e-commerce personalization platform.
- Yoochoose: Click and purchase sequences from a retail website.
To ensure a fair assessment of learning speed and adaptability, user interaction sequences were standardized to between 10 and 20 items.
Key Insights and Results
Performance and Accuracy
CoCoB demonstrated a significant performance boost over state-of-the-art models such as CAB and DynUCB, achieving an average 2.4% improvement in F1 score across all tested datasets. The authors identified that a similarity threshold ($\gamma$) of 0.8 served as the optimal "sweet spot," providing the best balance between group collaboration and individual personalization.
The "Warm-up" Trade-off
An analysis of the learning curves revealed an important characteristic of the algorithm: CoCoB initially performs worse than some baselines in the first few hundred rounds. This is because the model is cautiously building its internal representation of user similarity from scratch rather than forcing users into immediate, potentially inaccurate clusters. However, after approximately 2,000 rounds, CoCoB consistently outperforms competitive models as its similarity mappings become more robust.
Computational Efficiency
Despite the complexity of its two-sided architecture, CoCoB remains computationally efficient. By utilizing the Sherman-Morrison formula for matrix updates, the framework achieves faster processing speeds than more intricate clustering algorithms like CAB, making it viable for real-time applications.
Conclusion and Future Work
CoCoB represents a shift from proximity-based clustering to probability-based collaboration. By identifying neighbors purely through interaction behavior rather than demographic metadata, it offers a more privacy-preserving and adaptive approach to personalization.
While the initial "warm-up" period remains a challenge for systems requiring instantaneous high accuracy, future work will focus on refining the similarity probability model to reduce learning time and exploring "sharp regret boundaries" to provide stronger theoretical guarantees on system performance during the exploration phase.
Summary updated