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 (5)
Cited by in corpus (44)
- Advances and Challenges in Conversational Recommender Systems: A Survey
- Deep reinforcement learning for search, recommendation, and online advertising: a survey
- Combinatorial Cascading Bandits
- Online Learning to Rank in Stochastic Click Models
- Efficient Learning in Large-Scale Combinatorial Semi-Bandits
- A Tutorial on Thompson Sampling
- Reinforcement Learning for Slate-based Recommender Systems: A Tractable Decomposition and Practical Methodology
- Multiple-Play Bandits in the Position-Based Model
- 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
- PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer
- Action-Manipulation Attacks Against Stochastic Bandits: Attacks and Defense
- Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
- Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
- Tight Lower Bounds for Combinatorial Multi-Armed Bandits
- Unbiased Learning to Rank: Online or Offline?
- Combinatorial Semi-Bandit in the Non-Stationary Environment
- 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
- The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation
- Meta-Learning Bandit Policies by Gradient Ascent
- Dynamic Learning of Sequential Choice Bandit Problem under Marketing Fatigue
- Online Learning to Rank with List-level Feedback for Image Filtering
- Stochastic Bandits with Delay-Dependent Payoffs
- BanditRank: Learning to Rank Using Contextual Bandits
- Hierarchical Bayesian Bandits
- Bandit Policies for Reliable Cellular Network Handovers in Extreme Mobility
- Position-Based Multiple-Play Bandits with Thompson Sampling
- Waterfall Bandits: Learning to Sell Ads Online
- Conservative Contextual Combinatorial Cascading Bandit
- 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
- Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
- Thompson Sampling Algorithms for Cascading Bandits
- Fatigue-aware Bandits for Dependent Click Models
- DART: aDaptive Accept RejecT for non-linear top-K subset identification
- Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
- Pessimistic Off-Policy Optimization for Learning to Rank
- Sequential Choice Bandits with Feedback for Personalizing users' experience
- Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems
- Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem