Variance Reduction in Gradient Exploration for Online Learning to Rank

Huazheng Wang, Sonwoo Kim, Eric McCord-Snook, Qingyun Wu, Hongning WangSIGIR 2019 · DOI · OpenReview

Abstract

Online Learning to Rank (OL2R) algorithms learn from implicit user feedback on the fly. The key to such algorithms is an unbiased estimate of gradients, which is often achieved by uniformly sampling from the entire parameter space. Unfortunately, this leads to high-variance in gradient estimation, resulting in high regret during model updates, especially when the dimension of the parameter space is large. In this work, we aim at reducing the variance of gradient estimation in OL2R algorithms. We project the selected updating direction (i.e., the winning direction) into a space spanned by the feature vectors from examined documents under the current query (termed the "document space"), after an interleaved test. Our key insight is that the result of an interleaved test is solely governed by a user's relevance evaluation over the examined documents. Hence, the true gradient introduced by this test is only reflected in the constructed document space, and components of the proposed gradient which are orthogonal to the document space can be safely removed for variance reduction. We prove that this projected gradient is still 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.

Introduction

Online Learning to Rank (OL2R) allows search engines to adapt to user preferences in real-time by learning directly from implicit feedback, such as clicks. The standard framework for this is Dueling Bandit Gradient Descent (DBGD). In DBGD, the system proposes a random "exploratory" change to its ranking model, duels it against the current model using an interleaved list, and updates the model if the user prefers the candidate.

However, modern search models face the Curse of Dimensionality. While feature spaces ($d$) can contain hundreds or thousands of dimensions, a user typically only examines a small subset of documents ($m$) per query. Because traditional DBGD samples update directions from the entire feature space, the resulting gradient estimates are plagued by high variance—most of the update vector consists of random noise unrelated to the documents the user actually saw. This leads to slow convergence and high regret, degrading the user experience during the learning phase.

Methodology: Document Space Projection (DSP)

To address this, the authors introduce Document Space Projection (DSP). The core intuition is that if a user only interacts with a small set of documents, the feedback provided can only contain information about the features of those specific documents. Any component of a gradient update orthogonal to these features is essentially "hallucinated" noise.

Visualization of the Document Space Projection (DSP) mechanism showing the projection of the update vector onto the subspace $S_t$.

The DBGD-DSP algorithm follows these steps:

  1. Exploration: A random direction $u_t$ is sampled to create a candidate ranker.
  2. Interleaving: An interleaved list of documents from the current and candidate rankers is presented to the user.
  3. Subspace Construction: The algorithm identifies "examined" documents (e.g., all documents up to the last click plus a small buffer). It constructs a subspace $S_t$ spanned by the feature vectors of these documents.
  4. Projection: If the candidate ranker wins the duel, the update vector $u_t$ is projected onto the document space $S_t$ before updating the model weights $w_t$.

Crucially, the authors use Stokes’ Theorem to prove that this projection remains an unbiased estimate of the true gradient. This allows for significant noise reduction without the risk of converging to a sub-optimal solution.

Experimental Evaluation

The researchers evaluated DSP across five public Learning to Rank benchmarks, including MQ2007, MSLR-WEB10K, and the Yahoo! L2R Challenge (which features 700 dimensions). They simulated user behavior using three standard click models: Perfect, Navigational, and Informational.

Key Results

Experimental results confirmed that DSP-enhanced algorithms consistently outperform their baselines. As shown in the performance plots, the projected versions (e.g., MGD-DSP, NSGD-DSP) achieve higher Normalized Discounted Cumulative Gain (NDCG) with fewer user impressions.

Comparison of NDCG performance across different click models: (a) Perfect, (b) Navigational, and (c) Informational.
  • Faster Convergence: On high-dimensional datasets like Yahoo!, the variance reduction allowed models to reach peak performance significantly faster.
  • Regret Reduction: By removing orthogonal noise, the cumulative regret was lowered across all tested user models.
  • Versatility: DSP proved to be a "plug-and-play" enhancement, successfully improving various OL2R variants including Multileave Gradient Descent (MGD) and Null Space Gradient Descent (NSGD).

Conclusion and Future Work

Document Space Projection offers a theoretically grounded and practically effective solution to the high-variance problem in OL2R. By restricting updates to the subspace of features actually observed by the user, the method improves learning efficiency and ranking quality.

Future work may involve refining the "examination" heuristic to better capture complex user behaviors and extending the projection logic to non-linear models, such as deep neural networks, where the feature space is even more complex.

Summary updated

Abstract

Online Learning to Rank (OL2R) algorithms learn from implicit user feedback on the fly. The key to such algorithms is an unbiased estimate of gradients, which is often (trivially) achieved by uniformly sampling from the entire parameter space. Unfortunately, this leads to high-variance in gradient estimation, resulting in high regret during model updates, especially when the dimension of the parameter space is large. In this work, we aim at reducing the variance of gradient estimation in OL2R algorithms. We project the selected updating direction (i.e., the winning direction) into a space spanned by the feature vectors from examined documents under the current query (termed the "document space" for short), after an interleaved test. Our key insight is that the result of an interleaved test is solely governed by a user's relevance evaluation over the examined documents. Hence, the true gradient introduced by this test is only reflected in the constructed document space, and components of the proposed gradient which are orthogonal to the document space can be safely removed, for variance reduction purpose. We prove that this projected gradient is still 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 ranking performance.
BibTeX
@inproceedings{wang2019variance,
  author = {Huazheng Wang and Sonwoo Kim and Eric McCord-Snook and Qingyun Wu and Hongning Wang},
  title = {{Variance Reduction in Gradient Exploration for Online Learning to Rank}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2019},
  doi = {10.1145/3331184.3331264},
}
Figure