Active Ranking via Minimizing the Sum of Top-$k$ Regrets

We consider the active ranking problem: a decision maker (DM) has a fixed budget of noisy evaluations to learn the unknown utilities of a set of items, to rank them. Existing work typically measures the quality of the DM's ranking with metrics based on its ordinal distance from the true ranking. We use a utility-based metric, simple regret, so that misordering two items is more costly when their utilities are farther apart. Our main result shows that this ranking simple regret equals the sum of top-$k$ selection simple regrets, which allows (some) methods developed for top-$k$ selection to be adapted to active ranking. We then extend simple regret to allow different rank positions to have different importance, which gives a unified framework for full ranking, top-$k$ selection, and "everything in between".