Online Ranking with Top-1 Feedback
This addresses the challenge of learning to rank with limited feedback in online systems, which is incremental as it extends existing ranking theory to a new feedback model.
The paper tackles the problem of online ranking with only top-1 feedback, where the system learns to rank items over multiple rounds but receives relevance scores only for the top-ranked item, while being evaluated on the full list. It proves minimax regret bounds of Θ(T^{2/3}) for PairwiseLoss and DCG, achievable efficiently, and shows that normalized measures like AUC, NDCG, and MAP cannot achieve sublinear regret.
We consider a setting where a system learns to rank a fixed set of $m$ items. The goal is produce good item rankings for users with diverse interests who interact online with the system for $T$ rounds. We consider a novel top-$1$ feedback model: at the end of each round, the relevance score for only the top ranked object is revealed. However, the performance of the system is judged on the entire ranked list. We provide a comprehensive set of results regarding learnability under this challenging setting. For PairwiseLoss and DCG, two popular ranking measures, we prove that the minimax regret is $Θ(T^{2/3})$. Moreover, the minimax regret is achievable using an efficient strategy that only spends $O(m \log m)$ time per round. The same efficient strategy achieves $O(T^{2/3})$ regret for Precision@$k$. Surprisingly, we show that for normalized versions of these ranking measures, i.e., AUC, NDCG \& MAP, no online ranking algorithm can have sublinear regret.