TopRank: A practical algorithm for online stochastic ranking
arXiv:1806.02248
Abstract
Online learning to rank is a sequential decision-making problem where in each round the learning agent chooses a list of items and receives feedback in the form of clicks from the user. Many sample-efficient algorithms have been proposed for this problem that assume a specific click model connecting rankings and user behavior. We propose a generalized click model that encompasses many existing models, including the position-based and cascade models. Our generalization motivates a novel online learning algorithm based on topological sort, which we call TopRank. TopRank is (a) more natural than existing algorithms, (b) has stronger regret guarantees than existing algorithms with comparable generality, (c) has a more insightful proof that leaves the door open to many generalizations, (d) outperforms existing algorithms empirically.
Cited by in corpus (12)
- PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer
- Multi-Agent Multi-Armed Bandits with Limited Communication
- BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
- Unbiased Learning to Rank: Online or Offline?
- Meta-Learning Bandit Policies by Gradient Ascent
- TopRank+: A Refinement of TopRank Algorithm
- CORe: Capitalizing On Rewards in Bandit Exploration
- A Bayesian Choice Model for Eliminating Feedback Loops
- DART: aDaptive Accept RejecT for non-linear top-K subset identification
- Influence Diagram Bandits: Variational Thompson Sampling for Structured Bandit Problems
- Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
- Learning to Rank under Multinomial Logit Choice