Unbiased Learning to Rank: Counterfactual and Online Approaches

Harrie Oosterhuis, Rolf Jagerman, Maarten de Rijke

Abstract

This paper provides a comprehensive overview of the two primary methodologies in unbiased Learning to Rank (LTR): Counterfactual LTR and Online LTR. While LTR from user interactions offers a scalable alternative to expensive manual labeling, implicit feedback is inherently biased. We contrast Counterfactual LTR, which corrects historical logs using explicit user models, with Online LTR, which utilizes randomized interactions to eliminate bias in real-time. By examining their theoretical guarantees, empirical performance, and impact on user experience, this guide aims to assist practitioners in selecting the appropriate methodology for search and recommendation systems.

The Challenge of Implicit Feedback

Traditional Learning to Rank (LTR) systems rely on "perfect" relevance annotations—human experts manually grading documents for specific queries. However, this approach is prohibitively expensive and often fails to reflect the nuanced preferences of actual users.

Implicit feedback, such as click data, provides a high-volume, cost-effective alternative. Unfortunately, clicks are heavily influenced by position bias: users are statistically more likely to click top-ranked results regardless of their actual relevance. Training models on raw click data without correction leads to a self-reinforcing feedback loop of mediocrity, where the system simply learns to favor whatever was previously displayed at the top. Unbiased LTR seeks to break this loop by mathematically isolating true relevance from behavioral bias.

Counterfactual LTR: Learning from the Past

Counterfactual LTR (CLTR) is an offline approach that treats historical interaction logs as a biased sample of the truth. The primary objective is to estimate what would have happened if a different ranking had been shown.

Inverse Propensity Scoring (IPS)

The cornerstone of CLTR is Inverse Propensity Scoring. This technique re-weights clicks based on the probability that a user actually observed the document. For example, a click on a document at rank 10 is a significantly stronger signal of relevance than a click at rank 1, as the "propensity" to observe rank 10 is much lower. By weighting these rare events more heavily, IPS allows the model to learn an unbiased objective function.

The Role of User Modeling

CLTR requires an explicit model of user behavior (e.g., the probability of examination at rank $k$). These models can be pre-defined based on eye-tracking studies or learned jointly with the ranker. While CLTR is advantageous because it does not require altering the live user experience, its accuracy is strictly limited by the quality of the underlying propensity model.

Online LTR: Learning through Interaction

Online LTR (OLTR) takes an interactive approach, learning in real-time by experimenting with live traffic. Instead of relying on a pre-defined user model, OLTR uses randomization to uncover true preferences.

From Dueling Bandits to Differentiable Gradients

Historically, Dueling Bandit Gradient Descent (DBGD) was the standard for OLTR. It functioned by "dueling" the current best model against a slightly perturbed candidate. However, recent research has exposed flaws in DBGD’s regret bounds, showing it often fails to converge efficiently.

This has led to the rise of Pairwise Differentiable Gradient Descent (PDGD). PDGD treats the ranking task as a differentiable probability distribution, allowing for more direct optimization. PDGD has proven to be more robust and significantly faster to converge than its predecessors, making it the current state-of-the-art for online systems.

Comparative Analysis

Feature Counterfactual LTR (CLTR) Online LTR (OLTR)
Data Source Historical logs (Offline) Live interactions (Online)
User Model Required (Explicit) Not required (Implicit)
User Impact None (Safe) Potential short-term degradation due to randomization
Convergence Limited by model bias Theoretically guaranteed to reach optimum
Variance High (requires clipping) Generally lower with modern methods like PDGD

The "Model vs. Randomization" Trade-off

Practitioners face a fundamental choice: CLTR offers safety by using existing logs but risks bias if the user model is incorrect. OLTR offers robustness and theoretical convergence but requires a willingness to show users randomized (and potentially sub-optimal) results during the learning phase.

Limitations and Future Directions

Despite the success of these frameworks, several challenges remain:

  • Trust Bias: Current models often ignore that users may click a result simply because they trust the search engine's brand, even if the snippet is irrelevant.
  • Selection Bias: If a document is never displayed in historical logs or during online exploration, the system can never learn its relevance.
  • Complex Interactions: Most models assume a simple "scan-and-click" behavior, failing to account for users who compare multiple results or return to the search page after a bounce.

The next frontier in the field involves hybrid approaches—using historical data to "warm-start" an online learner. This combines the safety of counterfactual methods with the dynamic adaptability of online randomization, providing a more stable path toward optimal ranking.

Summary updated

Abstract

This tutorial covers and contrasts the two main methodologies in unbiased Learning to Rank (LTR): Counterfactual LTR and Online LTR. There has long been an interest in LTR from user interactions, however, this form of implicit feedback is very biased. In recent years, unbiased LTR methods have been introduced to remove the effect of different types of bias caused by user-behavior in search. For instance, a well addressed type of bias is position bias: the rank at which a document is displayed heavily affects the interactions it receives. Counterfactual LTR methods deal with such types of bias by learning from historical interactions while correcting for the effect of the explicitly modelled biases. Online LTR does not use an explicit user model, in contrast, it learns through an interactive process where randomized results are displayed to the user. Through randomization the effect of different types of bias can be removed from the learning process. Though both methodologies lead to unbiased LTR, their approaches differ considerably, furthermore, so do their theoretical guarantees, empirical results, effects on the user experience during learning, and applicability. Consequently, for practitioners the choice between the two is very substantial. By providing an overview of both approaches and contrasting them, we aim to provide an essential guide to unbiased LTR so as to aid in understanding and choosing between methodologies.
BibTeX
@inproceedings{oosterhuis2020unbiased,
  author = {Harrie Oosterhuis and Rolf Jagerman and Maarten de Rijke},
  title = {{Unbiased Learning to Rank: Counterfactual and Online Approaches}},
  booktitle = {The Web Conference},
  year = {2020},
  doi = {10.1145/3366424.3383107},
}
Figure