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噪声。相比之下，我们证明对于一大类数据分布而言，在没有强建模假设的情况下，即使查询响应是无噪声的，效用参数也无法被学习。接下来，我们分析主动学习设置下的学习问题。在这种情况下，我们证明即使对于第二个目标，也可以高效学习，并提出了适用于无噪声和有噪声查询响应设置的算法。因此，我们的结果展示了成对偏好查询中被动学习和主动学习之间的质的可学习差距，展示了选择成对查询进行效用学习的价值。

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