  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.
