  We study dueling bandits with weak utility-based regret when preferences over
arms have a total order and carry observable feature vectors. The order is
assumed to be determined by these feature vectors, an unknown preference
vector, and a known utility function. This structure introduces dependence
between preferences for pairs of arms, and allows learning about the preference
over one pair of arms from the preference over another pair of arms. We propose
an algorithm for this setting called Comparing The Best (CTB), which we show
has constant expected cumulative weak utility-based regret. We provide a
Bayesian interpretation for CTB, an implementation appropriate for a small
number of arms, and an alternate implementation for many arms that can be used
when the input parameters satisfy a decomposability condition. We demonstrate
through numerical experiments that CTB with appropriate input parameters
outperforms all benchmarks considered.
