Online Learning to Rank in Stochastic Click Models

Abstract

Online learning to rank is a core problem in information retrieval and machine learning. Many provably efficient algorithms have been recently proposed for this problem in specific click models. The click model is a model of how the user interacts with a list of documents. Though these results are significant, their impact on practice is limited, because all proposed algorithms are designed for specific click models and lack convergence guarantees in other models. In this work, we propose BatchRank, the first online learning to rank algorithm for a broad class of click models. The class encompasses two most fundamental click models, the cascade and position-based models. We derive a gap-dependent upper bound on the $T$-step regret of BatchRank and evaluate it on a range of web search queries. We observe that BatchRank outperforms ranked bandits and is more robust than CascadeKL-UCB, an existing algorithm for the cascade model.

Proceedings of the 34th International Conference on Machine Learning

References in corpus (1)

• Cascading Bandits: Learning to Rank in the Cascade Model

Cited by in corpus (16)

• Controlling Fairness and Bias in Dynamic Learning-to-Rank
• Online Learning: A Comprehensive Survey
• Reinforcement Learning to Rank in E-Commerce Search Engine: Formalization, Analysis, and Application
• PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer
• BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
• Solving Bernoulli Rank-One Bandits with Unimodal Thompson Sampling
• Unbiased Learning to Rank: Online or Offline?
• Contextual User Browsing Bandits for Large-Scale Online Mobile Recommendation
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• Learning from User Interactions with Rankings: A Unification of the Field
• Online Learning to Rank with List-level Feedback for Image Filtering
• Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network
• Conservative Exploration using Interleaving
• Thompson Sampling Algorithms for Cascading Bandits
• Online Newton Step Algorithm with Estimated Gradient
• TopRank+: A Refinement of TopRank Algorithm