Policy-Aware Unbiased Learning to Rank for Top-k Rankings

Harrie Oosterhuis, Maarten de RijkeSIGIR 2020 · DOI · OpenReview

TL;DR

This paper introduces the first "policy-aware" counterfactual estimator for Learning to Rank (LTR) that remains unbiased even when users only see the top-$k$ items. By accounting for the stochastic logging policy rather than just individual rankings, the authors solve the "item selection bias" problem, allowing ranking models to learn effectively from limited feedback without losing accuracy as $k$ gets smaller.

What Problem Does This Paper Address?

Most modern search engines and recommendation systems only show users a small subset of items (the top-$k$). When we try to learn from these interactions using Counterfactual LTR, we face two major hurdles:

  1. Position Bias: Users are more likely to click items at the top, regardless of relevance.
  2. Item Selection Bias: Items ranked below $k$ have a zero percent chance of being seen, and therefore a zero percent chance of being clicked.

Existing "policy-oblivious" methods (like standard Inverse Propensity Scoring) work well for position bias but fail fundamentally when items are hidden. They require every relevant item to have a non-zero chance of being seen in every displayed ranking. In a top-$k$ setting, this condition is almost never met, leading to biased models that perform poorly because they can't "see" the items the logging policy chose to hide.

Methods

The authors propose a shift from policy-oblivious to policy-aware propensity scoring.

  • The Policy-Aware Estimator: Instead of calculating the probability of an item being examined based on a single ranking, the authors calculate it based on the logging policy ($\pi$)—the probability distribution over all possible rankings the system might have shown. As long as the logging policy is stochastic (e.g., it occasionally swaps the $k$-th item with others), every relevant item eventually has a non-zero chance of appearing in the top-$k$.
  • Unbiased Top-$k$ Losses: The authors adapt state-of-the-art LTR frameworks, specifically LambdaLoss, to optimize top-$k$ metrics like DCG@k. They prove that by setting specific gain and discount functions, they can create a differentiable loss that serves as a proven lower bound on the actual ranking metric.
  • Unbiased Loss Selection: Since different loss functions (monotonic upper bounds vs. LambdaLoss variants) might perform differently depending on the data, the authors suggest using counterfactual evaluation on a validation set to choose the best-performing model in a principled, unbiased way.

Datasets

The study uses two large-scale, standard LTR benchmarks to perform semi-synthetic experiments:

  • MSLR-WEB30K: A massive dataset from a commercial search engine with 30,000 queries and roughly 125 documents per query.
  • Yahoo! Webscope (Set 1): Contains nearly 30,000 queries with an average of 24 documents per query.

The authors simulated user behavior by using a "production ranker" to generate rankings, applying a stochastic logging policy (randomizing the $k$-th position), and simulating clicks based on a position-bias model.

Key Insights and Ideas

  • The Logging Policy is the Key: The "aha moment" is realizing that we don't need every item to be visible in every interaction. We only need the logging policy as a whole to provide a non-zero probability for each item to appear in the top-$k$ at some point.
  • Randomization Requires Awareness: Simply adding randomization to a search engine isn't enough to fix bias. If your estimator is "policy-oblivious," it won't know how to weight those rare random occurrences correctly. The estimator must be explicitly aware of the policy's randomization strategy.
  • Robustness to $k$: A truly unbiased estimator should perform the same whether it sees the top-5, top-20, or the full ranking. The policy-aware estimator achieves this "flat" performance curve, whereas previous methods degrade rapidly as $k$ decreases.

Key Results

  • Bias Elimination: In experiments on both Yahoo and MSLR datasets, the policy-aware estimator reached the "Full-Info Skyline" (the performance of a model trained on perfect, unbiased data).
  • Failure of Baselines: Policy-oblivious baselines were significantly hampered by item selection bias. For example, on the Yahoo dataset, the oblivious approach needed $k > 60$ to approximate optimal performance, while the policy-aware version reached it even at $k=5$.
  • LambdaLoss Superiority: The "Truncated LambdaLoss" (a heuristic that ignores pairs outside the top-$k$) empirically provided the best performance for optimizing DCG@5, even though it lacks the strict theoretical bounds of the other proposed losses.

Limitations and Future Work

  • Knowledge of the Policy: The primary limitation is that the logging policy $\pi$ must be known exactly. In many legacy systems, the exact probability distribution used to generate historical logs might be lost. The authors suggest future work could investigate estimating the policy directly from the logs.
  • Variance: While unbiased, the policy-aware estimator can suffer from high variance if the logging policy rarely shows certain items (leading to very small propensity scores).
  • Recommendation Systems: The authors note that while this paper focuses on search, the framework is highly applicable to recommendation carousels, where position bias and selection bias are equally rampant but haven't been fully addressed together.

Summary updated

Abstract

Counterfactual Learning to Rank (LTR) methods optimize ranking systems using logged user interactions that contain interaction biases. Existing methods are only unbiased if users are presented with all relevant items in every ranking. There is currently no existing counterfactual unbiased LTR method for top-k rankings. We introduce a novel policy-aware counterfactual estimator for LTR metrics that can account for the effect of a stochastic logging policy. We prove that the policy-aware estimator is unbiased if every relevant item has a non-zero probability to appear in the top-k ranking. Our experimental results show that the performance of our estimator is not affected by the size of k: for any k, the policy-aware estimator reaches the same retrieval performance while learning from top-k feedback as when learning from feedback on the full ranking. Lastly, we introduce novel extensions of traditional LTR methods to perform counterfactual LTR and to optimize top-k metrics. Together, our contributions introduce the first policy-aware unbiased LTR approach that learns from top-k feedback and optimizes top-k metrics. As a result, counterfactual LTR is now applicable to the very prevalent top-k ranking setting in search and recommendation.
BibTeX
@inproceedings{oosterhuis2020policy,
  author = {Harrie Oosterhuis and Maarten de Rijke},
  title = {{Policy-Aware Unbiased Learning to Rank for Top-k Rankings}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2020},
  doi = {10.1145/3397271.3401102},
}
Figure