TopRank: A practical algorithm for online stochastic ranking

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

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.

Introduction

In online learning to rank, an agent presents a list of $K$ items to a user and learns from clicks to improve future rankings. The goal is to minimize "regret"—the cumulative difference between the clicks received and those an optimal agent would have achieved.

Traditional approaches face a "curse of dimensionality" due to the factorial number of possible rankings. To mitigate this, researchers often rely on specific click models, such as the Cascade Model (CM) or Position-Based Model (PBM). However, real-world user behavior rarely adheres strictly to these rigid mathematical assumptions. If the underlying model is misspecified, the algorithm's performance degrades significantly. This work introduces a generalized click model and a robust algorithm, TopRank, designed to perform efficiently across a broad class of user behaviors.

The TopRank Algorithm

TopRank moves beyond standard factorization assumptions (where click probability is simply attractiveness times position examination probability). Instead, it relies on weaker, more natural assumptions, such as the principle that swapping a more attractive item into a higher position should increase click probability.

The algorithm operates through four main stages:

  1. Topological Sorting: It maintains a directed graph $G_t$ where edges represent confident preferences (item $i$ is more attractive than item $j$).
  2. Block Partitioning: Items are partitioned into "blocks" based on the current graph. Items within a block are those for which the relative order is not yet certain.
  3. Randomized Exploration: Within each block, items are shuffled and placed in available slots, allowing the algorithm to gather data on relative performance in similar contexts.
  4. Confidence Bounds: By tracking click differences between pairs within the same block, TopRank uses concentration inequalities to add new edges to the graph as evidence mounts.
Illustration of the block partitioning and topological sorting in TopRank.

Empirical Evaluation

The researchers evaluated TopRank using the Yandex dataset, comprising 167 million search queries. They simulated users following both CM and PBM behaviors for 60 frequent queries, aiming to rerank the top $L=10$ items for the first $K=5$ positions.

Key Results

  • Theoretical Superiority: TopRank achieves a regret bound of $O(\sqrt{K^3 L n \log n})$, a significant improvement over previous general-purpose algorithms like BatchRank.
  • Robustness and Performance: TopRank consistently outperformed BatchRank. While specialized algorithms like CascadeKL-UCB may excel when their specific model assumptions hold, they often suffer "linear regret" (failing to learn) when the model is misspecified. TopRank, by contrast, remains robust across different models.
Regret performance of TopRank compared to baselines across different queries and click models.

Conclusion

TopRank offers a powerful abstraction for online ranking by treating it as a dynamic topological sorting problem. While highly effective, future work could address scaling to millions of items by integrating feature-based models and further tightening the theoretical regret bounds to meet the minimax lower bound of $\sqrt{KLn}$.

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