  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.
