Robust Learning to Rank from Incomplete Rankings under Positional Censoring

In domains such as AI alignment, reward modeling, and recommender systems, learning from human-generated feedback presents a fundamental epistemic challenge: the provided information is fundamentally sparse and systematically incomplete. In this work, we address the problem of learning the top-$k$ items from incomplete rankings under severe uncertainty. Most existing models for incomplete rankings rely on rigid, overconfident assumptions regarding both the ranking model that generates the latent ranking and the censoring mechanism that dictates which comparisons remain unobserved. On the one hand, the ranking model is often assumed to follow a standard 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, effectively reframing missing data as an objective uncertainty problem. We consider the broad class of ranking models that satisfy the complete consensus property, which comprehends all widely adopted models. Furthermore, we present a new preference-based feedback model, named positional censoring, which formalizes the epistemic boundaries of our observations and generalizes winner and top-$h$ feedback. We show that it is possible to learn reliably in this highly uncertain setting by presenting the PIRATE algorithm and providing a near-optimal instance-dependent bound to the sample complexity.