# A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2017.

## Built on by (most cited first, 12 of 12)

- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Learning Multimodal Rewards from Rankings](https://mlsanity.com/paper/2109.12750/) (2021)
- [Lagrangian Inference for Ranking Problems](https://mlsanity.com/paper/2110.00151/) (2021)
- [Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits](https://mlsanity.com/paper/2202.11795/) (2022)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [Ranking Free RAG: Replacing Re-ranking with Selection in RAG for Sensitive Domains](https://mlsanity.com/paper/2505.16014/) (2025)
- [Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimization](https://mlsanity.com/paper/2402.18917/) (2024)
- [Ranking with Confidence for Large Scale Comparison Data](https://mlsanity.com/paper/2202.01670/) (2022)
- [Faster Convergence with Multiway Preferences](https://mlsanity.com/paper/2312.11788/) (2023)
- [Pure Exploration with Structured Preference Feedback](https://mlsanity.com/paper/2104.05294/) (2021)
- [BlitzRank: Principled Zero-shot Ranking Agents with Tournament Graphs](https://mlsanity.com/paper/2602.05448/) (2026)
- [Optimal Top-k Identification from Pairwise Comparisons](https://mlsanity.com/paper/2607.08979/) (2026)

## Abstract (arXiv)

We study the active learning problem of top-k ranking from multi-wise comparisons under the popular multinomial logit model. Our goal is to identify the top-k items with high probability by adaptively querying sets for comparisons and observing the noisy output of the most preferred item from each comparison. To achieve this goal, we design a new active ranking algorithm without using any information about the underlying items' preference scores. We also establish a matching lower bound on the sample complexity even when the set of preference scores is given to the algorithm. These two results together show that the proposed algorithm is nearly instance optimal (similar to instance optimal [FLN03], but up to polylog factors). Our work extends the existing literature on rank aggregation in three directions. First, instead of studying a static problem with fixed data, we investigate the top-k ranking problem in an active learning setting. Second, we show our algorithm is nearly instance optimal, which is a much stronger theoretical guarantee. Finally, we extend the pairwise comparison to the multi-wise comparison, which has not been fully explored in ranking literature.