Learning to Rank from Incomplete Rankings

In domains such as recommender systems and information retrieval, learning from human-generated feedback is especially challenging because the information provided is often sparse and incomplete. In this work, we address the problem of learning the top-$k$ items from incomplete rankings. Most existing models for incomplete rankings rely on rigid assumptions regarding both the ranking model that generates the latent ranking and the censoring mechanism that determines which comparisons remain unobserved. On the one hand, the ranking model is often assumed to follow a Plackett-Luce (PL) or Mallows distribution. On the other hand, the censoring mechanism is typically assumed to be Missing Completely At Random (MCAR) or to exhibit well-behaved dependencies on the latent ranking, such as winner feedback or top-$h$ feedback. We introduce a new, general framework for learning from incomplete rankings that unifies and strictly generalizes the established frameworks in the literature. We consider the broad class of ranking models that satisfy the complete consensus property, which comprehends all widely adopted models, including PL and Mallows. Furthermore, we present a new preference-based feedback model, named positional censoring, which generalizes winner and top-$h$ feedback. We show that it is possible to learn in this general setting by presenting the PIRATE algorithm and providing a near-optimal instance-dependent bound to the sample complexity. Finally, we show that, under the PL ranking, PIRATE matches the sample complexity of state-of-the-art algorithms in the relevant scenarios of winner and top-$h$ feedback.

There is an abundance of datasets consisting of human preferences over an assortment of options. These preferences are often sparse, in the sense that a person rarely expresses a preference for every possible pair of options, but rather provides comparative feedback regarding only a few. In particular, users are more likely to provide feedback on items they strongly like or strongly dislike. This bias makes it difficult to reliably aggregate the information to learn their true underlying preferences. To this end, we introduce a mathematical model that accurately captures this specific sparseness in human feedback, alongside an algorithmic solution to aggregate this information effectively. Ultimately, our approach allows systems to uncover the true ranking of items even when the provided data is highly fragmented and biased. This ensures that real-world applications—from recommender systems to AI training—can make more reliable decisions based on how humans naturally express their choices.