Efficient Exploration of Gradient Space for Online Learning to Rank

Learning to rank is an optimization problem to update the ranking function to score each document to rank them. As opposed to offline learning to rank, which used annotated data, online learning to rank utilized the abundant click data users create. While vector spaced exploration based online learning to rank algorithm has shown improvements in recent works, they are still limited to uniform exploration, and ineffective comparison of candidate rankers' performance. A new algorithm, Null Space Gradient Descent is presented. Its contributions are in three parts: 1) null space exploration to prevent historically bad gradient direction, 2) candidate preselection to choose candidates that produce different ranking order in a given query, 3) effective tie breaking technique to use historically difficult queries. Extensive experiments show that NSGD's NDCG performance is stronger than most of baselines and converges much faster.