Online Learning to Rank with Feedback at the Top
This addresses the challenge of learning ranking functions from restricted feedback in online settings, which is incremental as it adapts existing methods to a specific feedback constraint.
The paper tackles the problem of online learning to rank with feedback limited to the top-k ranked documents, developing efficient algorithms for pointwise, pairwise, and listwise losses and proving impossibility results for sublinear regret with top-1 feedback calibrated to NDCG, achieving efficient learning on benchmark datasets.
We consider an online learning to rank setting in which, at each round, an oblivious adversary generates a list of $m$ documents, pertaining to a query, and the learner produces scores to rank the documents. The adversary then generates a relevance vector and the learner updates its ranker according to the feedback received. We consider the setting where the feedback is restricted to be the relevance levels of only the top $k$ documents in the ranked list for $k \ll m$. However, the performance of learner is judged based on the unrevealed full relevance vectors, using an appropriate learning to rank loss function. We develop efficient algorithms for well known losses in the pointwise, pairwise and listwise families. We also prove that no online algorithm can have sublinear regret, with top-1 feedback, for any loss that is calibrated with respect to NDCG. We apply our algorithms on benchmark datasets demonstrating efficient online learning of a ranking function from highly restricted feedback.