Title: A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model,
Abstract: 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.