On the Minimax Regret in Online Ranking with Top-k Feedback
This work addresses the problem of reducing feedback costs in online ranking for applications like search engines, though it is incremental as it builds on prior frameworks.
The paper solves open problems in online ranking with top-k feedback by fully characterizing minimax regret rates for Pairwise Loss, Discounted Cumulative Gain, and Precision@n, and provides an efficient algorithm achieving the minimax regret for Precision@n.
In online ranking, a learning algorithm sequentially ranks a set of items and receives feedback on its ranking in the form of relevance scores. Since obtaining relevance scores typically involves human annotation, it is of great interest to consider a partial feedback setting where feedback is restricted to the top-$k$ items in the rankings. Chaudhuri and Tewari [2017] developed a framework to analyze online ranking algorithms with top $k$ feedback. A key element in their work was the use of techniques from partial monitoring. In this paper, we further investigate online ranking with top $k$ feedback and solve some open problems posed by Chaudhuri and Tewari [2017]. We provide a full characterization of minimax regret rates with the top $k$ feedback model for all $k$ and for the following ranking performance measures: Pairwise Loss, Discounted Cumulative Gain, and Precision@n. In addition, we give an efficient algorithm that achieves the minimax regret rate for Precision@n.