Unbiased Counterfactual Estimation of Ranking Metrics

Haining YuCSR-Sim4IR @ SIGIR 2021

Abstract

This paper presents a novel, unbiased estimator for the offline evaluation of ranking policies using implicit feedback (e.g., clicks). By substituting high-variance Inverse Propensity Scoring (IPS) with a ratio based on positional bias, the proposed method provides a mathematically sound framework to predict the performance of new ranking models without the need for expensive live A/B testing. The approach focuses on variance reduction and practical applicability to deterministic ranking systems common in industry.

Introduction

In search engines and e-commerce platforms, evaluating whether a new ranking algorithm (the target policy) outperforms the current one (the behavioral policy) is a critical task. While live A/B tests are the gold standard, they are often slow, costly, and limited in scope.

Counterfactual Learning to Rank (LTR) offers an alternative by using logs from the behavioral policy to evaluate the target policy. However, user logs are inherently affected by positional bias: users are significantly more likely to interact with top-ranked results regardless of their actual relevance. Traditional methods to mitigate this bias, such as Inverse Propensity Scoring (IPS), often suffer from extreme statistical variance because they rely on the probability of an entire ranking sequence—a value that can be infinitesimally small in large-scale systems.

Methodology

The proposed estimator shifts the focus from the "cause" (document relevancy) to the "effect" (the behavioral signal/click). The framework relies on several key components:

  • Linearly Decomposable Metrics: The method is designed for standard metrics like Precision@k or Discounted Cumulative Gain (DCG), which can be expressed as a sum over individual documents.
  • Position-Based Click Model (PBM): It assumes a standard model where a click occurs only if a user examines a document (determined by its rank) and the document is relevant.
  • The Estimator: Instead of using the ratio of the probability of the entire ranking, the author utilizes the ratio of positional biases ($\eta$). If the target policy moves a document to a position where it is more likely to be seen than it was under the logging policy, the estimator weights that click accordingly.

Causal Framework

The relationship between the variables is formalized through a causal lens, distinguishing the proposed method from earlier work that attempted to estimate relevancy directly. By modeling the effect (clicks) on the target policy, the estimator uses two positional bias terms to cancel out the systematic bias introduced by the behavioral policy.

Causal graph representing the relationships between query, document, policy, and observed metrics.

Illustrative Data and Mathematical Proof

The core of the paper is a formal proof (Theorem 3.1) demonstrating that the proposed estimator is unbiased. This means that, given sufficient data, the estimator will converge to the true performance of the target policy.

To demonstrate the practical application of the math, the paper utilizes a hypothetical data sample. This sample illustrates how clicks observed under a behavioral policy $C$ can be re-weighted to estimate performance for a target policy $T$, even when the ranks differ significantly.

Hypothetical data sample comparing ranks under behavioral policy C and target policy T.

Key Insights

  • Variance Reduction: The ratio of positional biases (e.g., the probability of looking at rank 1 vs. rank 5) is much more stable than the ratio of ranking probabilities. This stability makes the estimates far more useful in industrial settings where ranking probabilities can be astronomically small.
  • Deterministic Policy Support: Many production systems use deterministic rankers, which typically break standard IPS methods. This new approach bypasses that hurdle by focusing on positional bias rather than policy probability.
  • Model Validation: The estimator can also be used to validate positional bias models themselves by comparing offline estimates against small-scale A/B test results.

Limitations and Future Work

While promising, the framework relies on the assumption of policy independence (Assumption 3.4), which may be violated if one ranker's output feeds into another. Furthermore, the current mathematical proof is tied to the Position-Based Model (PBM). While the author suggests the framework can generalize to more complex models like the Cascade Model, empirical validation on large-scale public benchmarks (like LETOR) remains a subject for future research.

Summary updated

BibTeX
@inproceedings{yu2021unbiased,
  author = {Haining Yu},
  title = {{Unbiased Counterfactual Estimation of Ranking Metrics}},
  booktitle = {CSR-Sim4IR @ SIGIR},
  year = {2021},
}
Figure