TopRank: A practical algorithm for online stochastic ranking

Tor Lattimore, Branislav Kveton, Shuai Li, Csaba Szepesvári

Introduction

In online learning to rank (OL2R), an agent must present an ordered list of $K$ items to a user and learn from their clicks to improve future rankings. The primary challenge in this domain is the "click model"—the mathematical description of how users interact with a list.

Most existing algorithms are "specialists." They are designed for specific models like the Cascade Model (where users scan top-to-bottom and stop at the first click) or the Position-Based Model (where click probability depends only on item appeal and its rank). However, real-world user behavior is often a messy hybrid. If a specialist algorithm is deployed on the wrong user population, its performance tanks. While "generalist" algorithms exist (like BatchRank), they are often mathematically complex, computationally heavy, or suffer from high theoretical regret.

TopRank is a new algorithm for OL2R that breaks free from the rigid assumptions of traditional click models. By maintaining a partial ordering of items via topological sort, it achieves state-of-the-art regret guarantees and demonstrates superior robustness across diverse user behaviors.

The TopRank Algorithm

TopRank avoids assuming a specific factorization of click probabilities. Instead, it relies on a few uncontroversial assumptions—primarily that an underlying "attractiveness" exists for each item, and that the optimal list is simply a sorted version of the most attractive items.

The algorithm operates through a clever combination of graph theory and randomized exploration:

  1. Topological Sort: TopRank maintains a directed graph where an edge from item $j$ to item $i$ means the algorithm has gathered statistical evidence that $i$ is more attractive than $j$.
  2. Block Partitioning: In each round, the algorithm partitions items into "blocks" based on this graph. Items within the same block are those whose relative order is still uncertain.
Illustration of TopRank's block partitioning and topological sort mechanism.
  1. Randomized Exploration: Within each block, the algorithm randomizes the order of items. This ensures that every item in a block has a fair chance to be compared against others in the same block.
  2. Statistical Updating: It tracks the difference in clicks between pairs of items when they appear in the same block. Once the "gap" is large enough to be statistically significant, a new edge is added to the graph, refining the partial order.

Empirical Performance and Insights

The researchers evaluated TopRank using the Yandex dataset, a massive open-source collection of 167 million search queries. They selected 60 frequent queries and used the PyClick library to learn parameters for both Cascade and Position-Based models, which served as the "ground truth" environments for their simulations.

Key Results

  • Theoretical Superiority: TopRank achieves a regret bound of $O(\sqrt{K^3 L n \log n})$. Crucially, this is a factor of $K^2$ better than BatchRank, the previous state-of-the-art generalist algorithm.
  • The Specialist vs. Generalist Trade-off: In simulations, TopRank consistently outperformed BatchRank. While specialist algorithms (like CascadeKL-UCB) still beat TopRank when the environment was a perfect match for their specific assumptions, TopRank proved significantly more robust. For example, in Position-Based Models, specialist cascade algorithms often suffered linear regret (failing to learn entirely), while TopRank successfully converged to the optimal policy.
Regret comparisons across different click models, demonstrating TopRank's robustness compared to other baselines.

The "Aha" Moment

TopRank’s beauty lies in its simplicity: it doesn't try to estimate the exact probability of a click; it only tries to learn the relative order of items. The authors prove that if the algorithm is suffering "regret" (i.e., showing a sub-optimal list), it is mathematically guaranteed to be gaining information about the relative ordering of items. This "information gain vs. regret" trade-off is the engine that drives the algorithm toward the optimal ranking.

Limitations and Future Work

While highly effective, TopRank has a few limitations that pave the way for future research:

  • The Sorting Assumption: TopRank assumes that the optimal ranking is a simple sort by attractiveness. This covers most standard click models but might struggle in scenarios where item diversity is the goal (e.g., showing a mix of news and sports to cover varied user intents).
  • Contextual Information: The current version of TopRank is "unstructured"—it treats every query/item pair as a fresh problem. A natural next step is to incorporate context (user features, item metadata) so the algorithm can generalize across different queries.
  • Scaling to Large Item Sets: As the total number of items ($L$) grows, the time to learn the full partial order increases. Future work could exploit structure between items, such as item embeddings, to speed up learning in high-dimensional spaces.

Summary updated

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.
BibTeX
@inproceedings{lattimore2018toprank,
  author = {Tor Lattimore and Branislav Kveton and Shuai Li and Csaba Szepesvári},
  title = {{TopRank: A practical algorithm for online stochastic ranking}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=SkVaC_bO-H},
}
Figure