# On the Minimax Regret in Online Ranking with Top-k Feedback

arXiv: https://arxiv.org/abs/2309.02425 · HTML: https://mlsanity.com/paper/2309.02425/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 17 references that are in the map.
- First posted on arXiv 5 Sep 2023.

## Builds on (most cited first, 7 of 7)

- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [Exploration by Optimisation in Partial Monitoring](https://mlsanity.com/paper/1907.05772/) (2019)
- [Cleaning up the neighborhood: A full classification for adversarial partial monitoring](https://mlsanity.com/paper/1805.09247/) (2018)
- [Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret](https://mlsanity.com/paper/2202.10997/) (2022)
- [Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring](https://mlsanity.com/paper/2006.09668/) (2020)
- [Online Learning to Rank with Top-k Feedback](https://mlsanity.com/paper/1608.06408/) (2016)

## 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.