This paper considers the task of learning users' preferences on a
combinatorial set of alternatives, as generally used by online configurators,
for example. In many settings, only a set of selected alternatives during past
interactions is available to the learner. Fargier et al. [2018] propose an
approach to learn, in such a setting, a model of the users' preferences that
ranks previously chosen alternatives as high as possible; and an algorithm to
learn, in this setting, a particular model of preferences: lexicographic
preferences trees (LP-trees). In this paper, we study complexity-theoretical
problems related to this approach. We give an upper bound on the sample
complexity of learning an LP-tree, which is logarithmic in the number of
attributes. We also prove that computing the LP tree that minimises the
empirical risk can be done in polynomial time when restricted to the class of
linear LP-trees.

该论文研究了基于过去互动中选择的备选方案，来学习用户偏好的任务，提出了一种基于 lexicographic preferences trees (LP-trees) 的偏好模型及学习算法，并研究了与该算法相关的复杂性问题，包括 LP-tree 的学习样本复杂度和在线性 LP-trees 类中计算最小经验风险的算法复杂度等。