Accelerated Convergence for Counterfactual Learning to Rank

Rolf Jagerman, Maarten de RijkeSIGIR 2020 · DOI · OpenReview

Abstract

Counterfactual Learning To Rank (LTR) algorithms learn ranking models from logged user interactions, which are often biased. Unbiased LTR typically employs Inverse Propensity Scoring (IPS) to mitigate this bias. However, applying Stochastic Gradient Descent (SGD) to IPS-weighted objectives is challenging due to the high variance introduced by propensity weights, leading to slow convergence. We propose CounterSample, a novel algorithm that replaces gradient weighting with importance sampling. We prove that CounterSample's convergence rate depends on the average propensity weight rather than the maximum, leading to significantly faster convergence. Empirical results across various optimizers and datasets confirm that CounterSample outperforms standard IPS-weighted methods in both speed and final performance.

Introduction

In search and recommendation systems, implicit feedback like clicks is abundant but biased. Users are more likely to click top-ranked items regardless of relevance (position bias). Counterfactual Learning to Rank (LTR) uses Inverse Propensity Scoring (IPS) to correct this. While IPS provides an unbiased estimate of the true loss, it introduces extreme variance. Items with low visibility have very small propensities ($p_i$), resulting in massive weights ($1/p_i$). In standard SGD, these weights cause "gradient spikes," necessitating very small learning rates and leading to slow, unstable convergence.

Methods: From Weighting to Sampling

The core innovation of CounterSample is a shift from weighting gradients to changing the data sampling strategy.

  1. IPS-weighted SGD: Samples interactions uniformly and scales each gradient by $1/p_i$.
  2. CounterSample: Samples interactions with a probability proportional to their IPS weight.

By incorporating the "importance" into the sampling frequency, the gradients themselves remain unscaled and stable. Mathematically, the convergence of standard IPS-weighted SGD is bounded by the maximum IPS weight ($M$), whereas CounterSample is bounded by the average IPS weight ($\bar{M}$). In practice, $M$ can be orders of magnitude larger than $\bar{M}$, especially under severe position bias.

Optimization paths of CounterSample vs IPS-SGD. CounterSample follows a more direct path to the optimum compared to the high-variance trajectories of IPS-SGD.

To maintain efficiency, CounterSample utilizes the Alias Method for $O(1)$ sampling, ensuring it is as computationally cheap as standard SGD after a one-time setup.

Experimental Evaluation

The authors evaluated CounterSample using the Yahoo LTR Challenge and Istella-s benchmarks. Biased click logs were simulated using a position-bias model to control bias severity. The performance was measured using nDCG@10 and average regret across three optimizers: SGD, Adam, and Adagrad.

Key Results

CounterSample demonstrated superior performance across all experimental settings.

  • Accelerated Convergence: As shown in the learning curves, CounterSample reaches high nDCG levels significantly faster than IPS-weighted SGD.
  • Optimizer Robustness: Standard IPS-weighted SGD often struggles with adaptive optimizers like Adam, sometimes plateauing at suboptimal solutions. CounterSample remains robust, converging to the correct optimum regardless of the optimizer used.
  • Bias Resilience: The performance gap between CounterSample and standard methods widens as position bias becomes more severe, highlighting its effectiveness in challenging, real-world scenarios.
Convergence of nDCG@10 over iterations across different optimizers. CounterSample consistently reaches peak performance faster than standard IPS-weighted SGD.

Conclusion

CounterSample addresses a fundamental bottleneck in counterfactual LTR by stabilizing the optimization process. By shifting the dependency of convergence from the maximum to the average propensity weight, it enables faster and more reliable learning from biased logs. Future work includes extending these theoretical guarantees to non-convex objectives and deep neural networks, as well as exploring scenarios where propensities must be estimated online.

Summary updated

Abstract

Counterfactual Learning to Rank (LTR) algorithms learn a ranking model from logged user interactions, often collected using a production system. Employing such an offline learning approach has many benefits compared to an online one, but it is challenging as user feedback often contains high levels of bias. Unbiased LTR uses Inverse Propensity Scoring (IPS) to enable unbiased learning from logged user interactions. One of the major difficulties in applying Stochastic Gradient Descent (SGD) approaches to counterfactual learning problems is the large variance introduced by the propensity weights. In this paper we show that the convergence rate of SGD approaches with IPS-weighted gradients suffers from the large variance introduced by the IPS weights: convergence is slow, especially when there are large IPS weights. To overcome this limitation, we propose a novel learning algorithm, called CounterSample, that has provably better convergence than standard IPS-weighted gradient descent methods. We prove that CounterSample converges faster and complement our theoretical findings with empirical results by performing extensive experimentation in a number of biased LTR scenarios -- across optimizers, batch sizes, and different degrees of position bias.
BibTeX
@inproceedings{jagerman2020accelerated,
  author = {Rolf Jagerman and Maarten de Rijke},
  title = {{Accelerated Convergence for Counterfactual Learning to Rank}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2020},
  doi = {10.1145/3397271.3401069},
}
Figure