# Learning Linear Utility Functions From Pairwise Comparison Queries

arXiv: https://arxiv.org/abs/2405.02612 · HTML: https://mlsanity.com/paper/2405.02612/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 45 references that are in the map.
- First posted on arXiv 4 May 2024.

## Builds on (most cited first, 15 of 15)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Learning with Feature-Dependent Label Noise: A Progressive Approach](https://mlsanity.com/paper/2103.07756/) (2021)
- [Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence](https://mlsanity.com/paper/1505.01462/) (2015)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [A Voting-Based System for Ethical Decision Making](https://mlsanity.com/paper/1709.06692/) (2017)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Adapting a Kidney Exchange Algorithm to Align with Human Values](https://mlsanity.com/paper/2005.09755/) (2020)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [Learning from Comparisons and Choices](https://mlsanity.com/paper/1704.07228/) (2017)
- [Noise in Classification](https://mlsanity.com/paper/2010.05080/) (2020)
- [Learning Mixtures of Plackett-Luce Models from Structured Partial Orders](https://mlsanity.com/paper/1910.11721/) (2019)
- [Learning Mixtures of Random Utility Models with Features from Incomplete Preferences](https://mlsanity.com/paper/2006.03869/) (2020)

## Built on by (most cited first, 8 of 8)

- [Axioms for AI Alignment from Human Feedback](https://mlsanity.com/paper/2405.14758/) (2024)
- [Theoretical Tensions in RLHF: Reconciling Empirical Success with Inconsistencies in Social Choice Theory](https://mlsanity.com/paper/2506.12350/) (2025)
- [Learning Parametric Distributions from Samples and Preferences](https://mlsanity.com/paper/2505.23557/) (2025)
- [Linear Social Choice with Few Queries: A Moment-Based Approach](https://mlsanity.com/paper/2603.19510/) (2026)
- [From Weights to Words: Expressing and Editing Preference Model Inferences in Natural Language](https://mlsanity.com/paper/2607.16232/) (2026)
- [Preference Elicitation for Policy Optimization and Application to Aligning Heart Transplantation with Human Values](https://mlsanity.com/paper/2608.28620/) (2026)
- [Internal Pluralism and the Limits of Pairwise Comparisons](https://mlsanity.com/paper/2607.02672/) (2026)
- [Learning Distributions from Samples and Qualities](https://mlsanity.com/paper/2610.17956/) (2026)

## Abstract (arXiv)

We study learnability of linear utility functions from pairwise comparison queries. In particular, we consider two learning objectives. The first objective is to predict out-of-sample responses to pairwise comparisons, whereas the second is to approximately recover the true parameters of the utility function. We show that in the passive learning setting, linear utilities are efficiently learnable with respect to the first objective, both when query responses are uncorrupted by noise, and under Tsybakov noise when the distributions are sufficiently "nice". In contrast, we show that utility parameters are not learnable for a large set of data distributions without strong modeling assumptions, even when query responses are noise-free. Next, we proceed to analyze the learning problem in an active learning setting. In this case, we show that even the second objective is efficiently learnable, and present algorithms for both the noise-free and noisy query response settings. Our results thus exhibit a qualitative learnability gap between passive and active learning from pairwise preference queries, demonstrating the value of the ability to select pairwise queries for utility learning.