Comparing Few to Rank Many: Optimal Design for Learning Preferences

We study learning of human or agent preferences from a limited comparison feedback. This task is ubiquitous in machine learning and its applications, such as reinforcement learning with human feedback, have been transformational. We can naturally formulate this problem as learning a Plackett-Luce model over a universe of N choices. In this work, we propose a statistically and computationally efficient algorithm for collecting a limited K-way comparison feedback to learn a high-quality Plackett-Luce model. The key idea is to extend the D-optimal design for efficient data collection in regression problems to learning to rank. Our design elicits comparison feedback from a small collection of \poly(N,K) optimally chosen subsets from all feasible {N choose K} subsets. Specifically, we propose an approximate Frank-Wolfe algorithm and design an efficient oracle for approximately solving linear maximization over the simplex of all possible subsets. We analyze our algorithm and evaluate it empirically on open-source datasets.