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.

线性效用函数从成对比较查询中的可学习性研究。具体来说，我们考虑两个学习目标：首先是预测成对比较的样本外响应，其次是近似恢复效用函数的真实参数。我们证明在线性效用在被动学习设置下是高效可学习的，无论查询响应是否受到噪声干扰，并且在分布足够 “好” 的条件下，即使存在 Tsybakov 噪声。相比之下，我们证明对于一大类数据分布而言，在没有强建模假设的情况下，即使查询响应是无噪声的，效用参数也无法被学习。接下来，我们分析主动学习设置下的学习问题。在这种情况下，我们证明即使对于第二个目标，也可以高效学习，并提出了适用于无噪声和有噪声查询响应设置的算法。因此，我们的结果展示了成对偏好查询中被动学习和主动学习之间的质的可学习差距，展示了选择成对查询进行效用学习的价值。

从两两比较查询中学习线性效用函数

Learning Linear Utility Functions From Pairwise Comparison Queries

A recent line of work, starting with Beigman and Vohra (2006) and
Zadimoghaddam and Roth (2012), has addressed the problem of {\em learning} a
utility function from revealed preference data. The goal here is to make use of
past data describing the purchases of a utility maximizing agent when faced
with certain prices and budget constraints in order to produce a hypothesis
function that can accurately forecast the {\em future} behavior of the agent.
In this work we advance this line of work by providing sample complexity
guarantees and efficient algorithms for a number of important classes. By
drawing a connection to recent advances in multi-class learning, we provide a
computationally efficient algorithm with tight sample complexity guarantees
($\Theta(d/\epsilon)$ for the case of $d$ goods) for learning linear utility
functions under a linear price model. This solves an open question in
Zadimoghaddam and Roth (2012). Our technique yields numerous generalizations
including the ability to learn other well-studied classes of utility functions,
to deal with a misspecified model, and with non-linear prices.

本文探讨了如何从单调偏好数据中学习效用函数，提供了用于多种重要类别的样本复杂度保证和有效算法，并使用最近多类学习的进展和有关线性价格模型的紧密联系，提出了一种解决线性效用函数学习问题的高效算法。(Sample complexity guarantees and efficient algorithms are provided for learning utility function from revealed preference data, and a computationally efficient algorithm with tight sample complexity guarantees is proposed for learning linear utility functions under a linear price model).