Preference based learning matches direct reward learning efficiency

On the Complexity of Preference-Based Bandits

Artificial IntelligenceMachine Learning

Summary

This paper looks at how computers can learn preferences by comparing pairs instead of scoring options directly. The authors introduce a new way to measure the difficulty of this learning problem that fits better with how preferences work. They also create an algorithm that smartly picks pairs to learn from, balancing exploring new pairs and using known information. Their math shows this method can learn just as well as if the computer saw exact scores instead of just preferences. They test their algorithm and show it performs well compared to others.

What this means in practice

Authors

Ahmed Ben Yahmed, Marc Abeille, Clément Calauzènes

Abstract

We study preference-based bandits with general reward function classes, where a learner sequentially selects pairs of arms and observes binary preference feedback governed by the Bradley--Terry model. This setting naturally arises in applications such as recommender systems, tournament ranking, and learning from human feedback, where relative preferences are easier to elicit than absolute rewards. The observation model inherits the logistic bandit challenge of handling the problem-dependent constant $κ$, which accounts for the non-linearity of the link function and can grow arbitrarily large. Moreover, prior work has predominantly focused on linear or kernelized reward models, precluding the use of richer function classes. To address these limitations, we consider general reward function classes and introduce the \emph{locally sensitive eluder dimension}, a novel complexity measure tailored to the logistic structure of preference feedback that yields fine-grained regret guarantees without unfavorable dependence on $κ$. Building on this notion, we propose \textbf{GINOP} (Generic INformative OPtimism), an algorithm that constructs log-loss confidence sets and jointly selects arm pairs to balance optimism and informative exploration. We establish a first-order regret bound that, in contrast with what previous results suggest, demonstrates that learning with preference feedback is as statistically efficient as learning from direct reward observation. Finally, we corroborate our theoretical findings with empirical evaluations against competitive baselines.