Efficient Exploration of Gradient Space for Online Learning to Rank

Huazheng Wang, Ramsey Langley, Sonwoo Kim, Eric McCord-Snook, Hongning Wang

Abstract

Online learning to rank (OL2R) optimizes the utility of returned search results based on implicit feedback gathered directly from users. To improve the estimates, OL2R algorithms examine one or more exploratory gradient directions and update the current ranker if a proposed one is preferred by users via an interleaved test. In this paper, we accelerate the online learning process by efficient exploration in the gradient space. Our algorithm, named as Null Space Gradient Descent, reduces the exploration space to only the null space of recent poorly performing gradients. This prevents the algorithm from repeatedly exploring directions that have been discouraged by the most recent interactions with users. To improve sensitivity of the resulting interleaved test, we selectively construct candidate rankers to maximize the chance that they can be differentiated by candidate ranking documents in the current query; and we use historically difficult queries to identify the best ranker when tie occurs in comparing the rankers. Extensive experimental comparisons with the state-of-the-art OL2R algorithms on several public benchmarks confirmed the effectiveness of our proposal algorithm, especially in its fast learning convergence and promising ranking quality at an early stage.

Introduction

Online Learning to Rank (OL2R) allows search engines to learn directly from user interactions, such as clicks, bypassing the need for expensive and static manual labels. Most existing OL2R algorithms utilize a "dueling bandit" approach: the current ranker is perturbed in a random direction to create a candidate, and both are evaluated via an interleaved test to determine user preference.

However, this approach faces two significant challenges. First, the "Haystack Problem": in high-dimensional feature spaces, random perturbations are unlikely to yield improvements, often leading to redundant exploration of poor directions. Second, the "Tie Problem": rankers frequently produce identical document orderings for specific queries, rendering user feedback uninformative. This paper introduces Null Space Gradient Descent (NSGD) to address these inefficiencies by shrinking the search space and maximizing the utility of every user interaction.

The NSGD Algorithm

The core of NSGD lies in three novel strategies designed to streamline the exploration process and enhance the sensitivity of user feedback.

Overview of the three core strategies in Null Space Gradient Descent (NSGD).
  1. Null Space Exploration: The algorithm maintains a history of "bad" gradients—directions that failed to improve the ranker in recent iterations. It restricts future exploration to the null space of these gradients, focusing only on directions mathematically orthogonal to known failures.
  2. Context-Dependent Preselection (CDP): Rather than selecting an arbitrary direction in the null space, NSGD generates multiple candidates and selects the one most likely to produce a distinct ranking for the current query. This ensures that the subsequent interleaved test is capable of distinguishing between the two rankers.
  3. History-Dependent Tie Breaking: When an interleaved test results in a tie, NSGD utilizes "difficult" historical queries. By examining how rankers behaved on these queries and leveraging recorded historical clicks, the algorithm can break ties more effectively than random selection.

Experimental Setup

The effectiveness of NSGD was evaluated using the LETOR 3.0 and 4.0 benchmark collections, including MQ2007, MQ2008, and specialized datasets like TD2003, NP2003, and HP2003. User behavior was simulated using the Cascade Click Model with three distinct profiles:

  • Perfect: Users always click relevant results.
  • Navigational: Users stop after finding a single relevant result.
  • Informational: Users exhibit noisier behavior, potentially clicking irrelevant results.

Results and Discussion

Experimental results demonstrate that NSGD significantly outperforms state-of-the-art baselines in several key metrics.

Cumulative NDCG performance across different user click models (Perfect, Navigational, Informational).

Rapid Convergence and Quality

NSGD achieves high ranking performance (measured by NDCG) much faster than traditional methods. For instance, on the MQ2007 dataset under the noisy "informational" model, NSGD reached performance levels in 200 iterations that required 800 iterations for the previous state-of-the-art, Multidirectional Gradient Descent (MGD). This rapid convergence is critical for maintaining user satisfaction in live systems, as it provides higher quality results much earlier in the learning process.

Robustness to Noise

Beyond raw performance, NSGD exhibits lower standard deviation in its results compared to other methods. This suggests that the algorithm is more stable and less prone to the erratic updates often associated with stochastic gradient descent in online environments. By treating poorly performing gradients as constraints, the search space becomes more manageable, leading to more consistent improvements.

Conclusion

NSGD represents a significant step forward in OL2R by demonstrating that "negative knowledge"—knowing where not to look—is a powerful tool for optimization. While the algorithm shows impressive empirical success, future work includes investigating the theoretical bias of null space sampling and closing the performance gap between online methods and "offline" models trained on manual labels. Additionally, extending the model to be session-aware could further improve its utility in complex search scenarios.

Summary updated

Abstract

Online learning to rank (OL2R) optimizes the utility of returned search results based on implicit feedback gathered directly from users. To improve the estimates, OL2R algorithms examine one or more exploratory gradient directions and update the current ranker if a proposed one is preferred by users via an interleaved test. In this paper, we accelerate the online learning process by efficient exploration in the gradient space. Our algorithm, named as Null Space Gradient Descent, reduces the exploration space to only the \emph{null space} of recent poorly performing gradients. This prevents the algorithm from repeatedly exploring directions that have been discouraged by the most recent interactions with users. To improve sensitivity of the resulting interleaved test, we selectively construct candidate rankers to maximize the chance that they can be differentiated by candidate ranking documents in the current query; and we use historically difficult queries to identify the best ranker when tie occurs in comparing the rankers. Extensive experimental comparisons with the state-of-the-art OL2R algorithms on several public benchmarks confirmed the effectiveness of our proposal algorithm, especially in its fast learning convergence and promising ranking quality at an early stage.
BibTeX
@inproceedings{wang2018efficient,
  author = {Huazheng Wang and Ramsey Langley and Sonwoo Kim and Eric McCord-Snook and Hongning Wang},
  title = {{Efficient Exploration of Gradient Space for Online Learning to Rank}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2018},
  url = {https://openreview.net/forum?id=S1NVmUZ_-B},
}
Figure