Cascading Bandits for Large-Scale Recommendation Problems

Abstract

Most recommender systems recommend a list of items. The user examines the list, from the first item to the last, and often chooses the first attractive item and does not examine the rest. This type of user behavior can be modeled by the cascade model. In this work, we study cascading bandits, an online learning variant of the cascade model where the goal is to recommend $K$ most attractive items from a large set of $L$ candidate items. We propose two algorithms for solving this problem, which are based on the idea of linear generalization. The key idea in our solutions is that we learn a predictor of the attraction probabilities of items from their features, as opposing to learning the attraction probability of each item independently as in the existing work. This results in practical learning algorithms whose regret does not depend on the number of items $L$. We bound the regret of one algorithm and comprehensively evaluate the other on a range of recommendation problems. The algorithm performs well and outperforms all baselines.

arXiv commentAccepted to UAI 2016

References in corpus (3)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Matroid Bandits: Fast Combinatorial Optimization with Learning

Cited by in corpus (13)

• Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
• Reinforcement Learning to Rank in E-Commerce Search Engine: Formalization, Analysis, and Application
• BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
• Empirical Bayes Regret Minimization
• Contextual User Browsing Bandits for Large-Scale Online Mobile Recommendation
• Revenue Maximization and Learning in Products Ranking
• Bernoulli Rank-$1$ Bandits for Click Feedback
• Cost-aware Cascading Bandits
• Online learning with feedback graphs and switching costs
• Position-Based Multiple-Play Bandits with Thompson Sampling
• Neural Combinatorial Clustered Bandits for Recommendation Systems
• On Learning to Rank Long Sequences with Contextual Bandits
• Online Diverse Learning to Rank from Partial-Click Feedback