On the Minimax Regret in Online Ranking with Top-k Feedback
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 7 of its 17 references that are in the map. First posted on arXiv 5 Sep 2023.
Builds on
7 of 17 references.
References · 7
- 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 41
- 2020Mirror Descent and the Information Ratiocited by 39
- 2019Exploration by Optimisation in Partial Monitoringcited by 20
- 2018Cleaning up the neighborhood: A full classification for adversarial partial monitoringcited by 16
- 2022Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regretcited by 13
- 2020Analysis and Design of Thompson Sampling for Stochastic Partial Monitoringcited by 9
- 2016Online Learning to Rank with Top-k Feedbackcited by 7
Built on by
Not cited yet.