DCM Bandits: Learning to Rank with Multiple Clicks

Abstract

A search engine recommends to the user a list of web pages. The user examines this list, from the first page to the last, and clicks on all attractive pages until the user is satisfied. This behavior of the user can be described by the dependent click model (DCM). We propose DCM bandits, an online learning variant of the DCM where the goal is to maximize the probability of recommending satisfactory items, such as web pages. The main challenge of our learning problem is that we do not observe which attractive item is satisfactory. We propose a computationally-efficient learning algorithm for solving our problem, dcmKL-UCB; derive gap-dependent upper bounds on its regret under reasonable assumptions; and also prove a matching lower bound up to logarithmic factors. We evaluate our algorithm on synthetic and real-world problems, and show that it performs well even when our model is misspecified. This work presents the first practical and regret-optimal online algorithm for learning to rank with multiple clicks in a cascade-like click model.

Proceedings of the 33rd International Conference on Machine Learning

References in corpus (2)

• Combinatorial Bandits Revisited
• Combinatorial Cascading Bandits

Cited by in corpus (18)

• Deep reinforcement learning for search, recommendation, and online advertising: a survey
• Online Learning to Rank in Stochastic Click Models
• Multiple-Play Bandits in the Position-Based Model
• PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer
• BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
• Stochastic Rank-1 Bandits
• Probabilistic Permutation Graph Search: Black-Box Optimization for Fairness in Ranking
• Unbiased Learning to Rank: Online or Offline?
• Revenue Maximization and Learning in Products Ranking
• Contextual User Browsing Bandits for Large-Scale Online Mobile Recommendation
• Online learning with feedback graphs and switching costs
• Hierarchical Bayesian Bandits
• Position-Based Multiple-Play Bandits with Thompson Sampling
• BanditRank: Learning to Rank Using Contextual Bandits
• Thompson Sampling Algorithms for Cascading Bandits
• Pessimistic Off-Policy Optimization for Learning to Rank
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Fatigue-aware Bandits for Dependent Click Models