Learning Linear Utility Functions From Pairwise Comparison Queries

arXiv:2405.02612v1 Announce Type: new
Abstract: 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 …

abstract arxiv comparison cs.ai cs.cy cs.lg function functions linear parameters queries responses sample show stat.ml study true type utility