pipette
ESEspañol

On the Complexity of Preference-Based Bandits

Ahmed Ben Yahmed, Marc Abeille, Cl\'ement Calauz\`enes

Preprint with a published version

In the authors' words

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 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 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.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 1. arXiv. Preprint with a published version.

Published version: NeurIPS 2026 - Fortieth Annual Conference on Neural Information Processing Systems, Dec 2026, Sydney (AUSTRALIA), Australia