Cascading Bandits: Learning to Rank in the Cascade Model
arXiv:1502.02763
Abstract
A search engine usually outputs a list of web pages. The user examines this list, from the first web page to the last, and chooses the first attractive page. This model of user behavior is known as the cascade model. In this paper, we propose cascading bandits, a learning variant of the cascade model where the objective is to identify most attractive items. We formulate our problem as a stochastic combinatorial partial monitoring problem. We propose two algorithms for solving it, CascadeUCB1 and CascadeKL-UCB. We also prove gap-dependent upper bounds on the regret of these algorithms and derive a lower bound on the regret in cascading bandits. The lower bound matches the upper bound of CascadeKL-UCB up to a logarithmic factor. We experiment with our algorithms on several problems. The algorithms perform surprisingly well even when our modeling assumptions are violated.
Proceedings of the 32nd International Conference on Machine Learning
References in corpus (2)
Cited by in corpus (21)
- Reinforcement Learning for Slate-based Recommender Systems: A Tractable Decomposition and Practical Methodology
- Unbiased Cascade Bandits: Mitigating Exposure Bias in Online Learning to Rank Recommendation
- Measuring Recommender System Effects with Simulated Users
- Online Influence Maximization under Linear Threshold Model
- Contextual User Browsing Bandits for Large-Scale Online Mobile Recommendation
- Online Learning of Optimally Diverse Rankings
- Learning from User Interactions with Rankings: A Unification of the Field
- Dynamic Learning of Sequential Choice Bandit Problem under Marketing Fatigue
- Stochastic Bandits with Delay-Dependent Payoffs
- Online Learning to Rank with List-level Feedback for Image Filtering
- Bandit Policies for Reliable Cellular Network Handovers in Extreme Mobility
- BanditRank: Learning to Rank Using Contextual Bandits
- Waterfall Bandits: Learning to Sell Ads Online
- Conservative Contextual Combinatorial Cascading Bandit
- Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
- Observe Before Play: Multi-armed Bandit with Pre-observations
- TopRank+: A Refinement of TopRank Algorithm
- Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect
- Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems
- Sequential Choice Bandits with Feedback for Personalizing users' experience
- Fatigue-aware Bandits for Dependent Click Models