# Variance Reduction in Gradient Exploration for Online Learning to Rank

arXiv: https://arxiv.org/abs/1906.03766 · HTML: https://mlsanity.com/paper/1906.03766/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2019.

## Built on by (most cited first, 9 of 9)

- [PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer](https://mlsanity.com/paper/2103.00368/) (2021)
- [Adversarial Attacks on Online Learning to Rank with Stochastic Click Models](https://mlsanity.com/paper/2305.19218/) (2023)
- [Set2setRank: Collaborative Set to Set Ranking for Implicit Feedback based Recommendation](https://mlsanity.com/paper/2105.07377/) (2021)
- [How to Forget Clients in Federated Online Learning to Rank?](https://mlsanity.com/paper/2401.13410/) (2024)
- [Calibrating Explore-Exploit Trade-off for Fair Online Learning to Rank](https://mlsanity.com/paper/2111.00735/) (2021)
- [Learning Neural Ranking Models Online from Implicit User Feedback](https://mlsanity.com/paper/2201.06658/) (2022)
- [Investigating the Robustness of Counterfactual Learning to Rank Models: A Reproducibility Study](https://mlsanity.com/paper/2404.03707/) (2024)
- [RS-DGC: Exploring Neighborhood Statistics for Dynamic Gradient Compression on Remote Sensing Image Interpretation](https://mlsanity.com/paper/2312.17530/) (2023)
- [Learning to Retrieve via Reinforcement Learning in Embedding Space](https://mlsanity.com/paper/2610.07731/) (2026)

## Abstract (arXiv)

Online Learning to Rank (OL2R) algorithms learn from implicit user feedback on the fly. The key of such algorithms is an unbiased estimation of gradients, which is often (trivially) achieved by uniformly sampling from the entire parameter space. This unfortunately introduces high-variance in gradient estimation, and leads to a worse regret of model estimation, especially when the dimension of parameter space is large. In this paper, we aim at reducing the variance of gradient estimation in OL2R algorithms. We project the selected updating direction into a space spanned by the feature vectors from examined documents under the current query (termed the "document space" for short), after interleaved test. Our key insight is that the result of interleaved test solely is governed by a user's relevance evaluation over the examined documents. Hence, the true gradient introduced by this test result should lie in the constructed document space, and components orthogonal to the document space in the proposed gradient can be safely removed for variance reduction. We prove that the projected gradient is an unbiased estimation of the true gradient, and show that this lower-variance gradient estimation results in significant regret reduction. Our proposed method is compatible with all existing OL2R algorithms which rank documents using a linear model. Extensive experimental comparisons with several state-of-the-art OL2R algorithms have confirmed the effectiveness of our proposed method in reducing the variance of gradient estimation and improving overall performance.