Learning from Ranking Feedback: Improved Regret Bounds via Independence Preserving Rank Breaking

We study the sequential decision-making problem where at each time the learner selects an assortment of bounded size and receives a ranking of the selected items. Ranking feedback arises naturally when human evaluators or automated LLM judges compare multiple options simultaneously. It is often easier and more reliable than assigning absolute scores, which are typically poorly calibrated across evaluators, while yielding substantially more information than a single pairwise comparison. We focus on rankings that are constructed according to the random utility model with linear utilities, which includes the popular Plackett-Luce model as a special case. We show that improved regret minimisation is possible under full rank breaking with a refined analysis based on 1-factorisations and Baranyai's theorem that fully exploits independence in the pairwise comparisons. This gives a tighter confidence interval around the true utility parameter which is crucial in our analysis for regret that improves with maximum assortment size. Furthermore, it matches the regret lower bound for our model in case the learner is permitted to play multi-sets of the maximum bounded size. Our work gives a principled approach to learning from ranking feedback that shows consistent improvement with the maximum assortment size.