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.
- IPS-weighted SGD: Samples interactions uniformly and scales each gradient by $1/p_i$.
- 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.
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.
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