# TopRank: A practical algorithm for online stochastic ranking

arXiv: https://arxiv.org/abs/1806.02248 · HTML: https://mlsanity.com/paper/1806.02248/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2018.

## Built on by (most cited first, 30 of 30)

- [Multi-Agent Multi-Armed Bandits with Limited Communication](https://mlsanity.com/paper/2102.08462/) (2021)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Minimax Regret for Cascading Bandits](https://mlsanity.com/paper/2203.12577/) (2022)
- [PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer](https://mlsanity.com/paper/2103.00368/) (2021)
- [Adversarial Attacks on Online Learning to Rank with Click Feedback](https://mlsanity.com/paper/2305.17071/) (2023)
- [Adversarial Attacks on Online Learning to Rank with Stochastic Click Models](https://mlsanity.com/paper/2305.19218/) (2023)
- [Learning How to Optimize Black-Box Functions With Extreme Limits on the Number of Function Evaluations](https://mlsanity.com/paper/2103.10321/) (2021)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Unified Off-Policy Learning to Rank: a Reinforcement Learning Perspective](https://mlsanity.com/paper/2306.07528/) (2023)
- [From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards](https://mlsanity.com/paper/2502.09257/) (2025)
- [Sum-max Submodular Bandits](https://mlsanity.com/paper/2311.05975/) (2023)
- [Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes](https://mlsanity.com/paper/2110.02248/) (2021)
- [Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Model](https://mlsanity.com/paper/2207.05437/) (2022)
- [Bandit Learning to Rank with Position-Based Click Models: Personalized and Equal Treatments](https://mlsanity.com/paper/2311.04528/) (2023)
- [Regret Minimization via Saddle Point Optimization](https://mlsanity.com/paper/2403.10379/) (2024)
- [CORe: Capitalizing On Rewards in Bandit Exploration](https://mlsanity.com/paper/2103.04387/) (2021)
- [Calibrating Explore-Exploit Trade-off for Fair Online Learning to Rank](https://mlsanity.com/paper/2111.00735/) (2021)
- [Learning Neural Ranking Models Online from Implicit User Feedback](https://mlsanity.com/paper/2201.06658/) (2022)
- [Overcoming Prior Misspecification in Online Learning to Rank](https://mlsanity.com/paper/2301.10651/) (2023)
- [Misalignment, Learning, and Ranking: Harnessing Users Limited Attention](https://mlsanity.com/paper/2402.14013/) (2024)
- [Adversarial Combinatorial Semi-bandits with Graph Feedback](https://mlsanity.com/paper/2502.18826/) (2025)
- [The Sample Complexity of Multiclass and Sparse Contextual Bandits](https://mlsanity.com/paper/2605.29645/) (2026)
- [On Learning to Rank Long Sequences with Contextual Bandits](https://mlsanity.com/paper/2106.03546/) (2021)
- [UniRank: Unimodal Bandit Algorithm for Online Ranking](https://mlsanity.com/paper/2208.01515/) (2022)
- [Exploration of Unranked Items in Safe Online Learning to Re-Rank](https://mlsanity.com/paper/2305.01202/) (2023)
- [Adaptive Policy Learning to Additional Tasks](https://mlsanity.com/paper/2305.15193/) (2023)
- [Adaptively Learning to Select-Rank in Online Platforms](https://mlsanity.com/paper/2406.05017/) (2024)
- [Observation-Free Attacks on Online Learning to Rank](https://mlsanity.com/paper/2509.22855/) (2025)
- [A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming](https://mlsanity.com/paper/2606.29221/) (2026)

## Abstract (arXiv)

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.