DCM Bandits: Learning to Rank with Multiple Clicks
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.
Code (1)
Tasks
Learning-To-RankSimilar Papers 제목 키워드 기반
Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach
Online learning to rank (OLTR) studies how to recommend a short ranked list of items from a large pool and improves future rankings based on user clicks. This setting is commonly modeled as cascading bandits, where the o…
Cascading Non-Stationary Bandits: Online Learning to Rank in the Non-Stationary Cascade Model
Non-stationarity appears in many online applications such as web search and advertising. In this paper, we study the online learning to rank problem in a non-stationary environment where user preferences change abruptly …
Learning-To-RankCascading Hybrid Bandits: Online Learning to Rank for Relevance and Diversity
Relevance ranking and result diversification are two core areas in modern recommender systems. Relevance ranking aims at building a ranked list sorted in decreasing order of item relevance, while result diversification f…
DiversityLearning-To-RankRecommendation SystemsAdversarial Attacks on Online Learning to Rank with Click Feedback
Online learning to rank (OLTR) is a sequential decision-making problem where a learning agent selects an ordered list of items and receives feedback through user clicks. Although potential attacks against OLTR algorithms…
Decision MakingLearning-To-RankSequential Decision MakingOptimizing Ranking Systems Online as Bandits
Ranking system is the core part of modern retrieval and recommender systems, where the goal is to rank candidate items given user contexts. Optimizing ranking systems online means that the deployed system can serve user …
Learning-To-RankOnline Ranker EvaluationRecommendation SystemsRetrieval