Introduction
Standard contextual bandits assume that after choosing an action (like showing an ad or recommending a product), the learner receives a numerical reward. However, in many real-world scenarios—such as recommender systems, search engines, or clinical trials—it is much easier to elicit relative feedback (e.g., "the user clicked item A over item B") than an absolute score.
This paper introduces the first optimal algorithms for stochastic contextual preference bandits, a setting where a learner must choose the best item from a set based only on these relative preferences. Existing "dueling bandit" algorithms often struggle in this domain because they scale with the total number of items ($K$), making them impractical for the massive or infinite item catalogs found in modern web services. Furthermore, many fail to effectively use item features (context) to generalize learning across different rounds. By leveraging $d$-dimensional feature vectors, the authors bridge this gap, proving that learning from preferences can be just as efficient as learning from absolute scores, even with infinitely large sets of possible items.
Algorithmic Framework
The authors model preferences using the Plackett-Luce (PL) model, where the probability of an item being chosen from a subset is proportional to its underlying "utility score." This utility is modeled as a linear function of its features: $x^\top \theta^*$.
For the standard pairwise comparison case ($q=2$), the paper proposes two primary algorithms:
- MaxInP (Maximum-Informative-Pair): A computationally efficient approach that maintains a "promising set" of candidate arms. At each step, it selects the pair with the highest variance (the most uncertain pair) to maximize information gain.
- StaD (Stagewise-Adaptive-Duel): A phased algorithm that eliminates "weak" arms over time. By utilizing a more sophisticated concentration analysis, StaD achieves a tighter, optimal regret bound.
For the general case where the learner can present a subset of size $q > 2$, the authors introduce StaD++. This extension uses a technique called "rank-breaking" to decompose subset wins into pairwise comparisons, allowing the framework to handle broader multi-item choice scenarios.
Theoretical Insights
Bridging Linear and Preference Bandits
A major theoretical contribution of this work is a novel reduction showing that any contextual linear bandit problem can be transformed into a preference bandit problem using Gumbel noise.
This reduction allows the authors to port established lower bounds from the well-studied linear bandit literature directly into this newer preference-based setting, establishing a rigorous performance floor.
The "Subset Size" Paradox
Surprisingly, the authors prove that having access to subsetwise preferences ($q > 2$) does not help the learner aggregate information faster than simple pairwise comparisons ($q=2$). The fundamental lower bound remains $\Omega(\sqrt{dT})$ regardless of the subset size $q$. Furthermore, unlike previous work where regret grew with the number of items ($K$), the performance of these new algorithms depends only on the feature dimension ($d$) and time ($T$), making them highly practical for massive catalogs.
Empirical Evaluation
The algorithms were evaluated using synthetic problem instances designed to test different difficulty levels. For linear score instances, the authors created "Easy," "Intermediate," and "Extreme" environments by varying the norm of the hidden parameter $\theta^*$ and the distribution of feature vectors.
Key Results: * Optimal Regret: The StaD algorithm achieves a regret of $\tilde{O}(\sqrt{dT})$, perfectly matching the theoretical lower bound. This is a significant improvement over the $O(d\sqrt{T})$ bound of the simpler MaxInP algorithm. * Superior Performance: In simulations across all difficulty levels, both MaxInP and StaD significantly outperformed existing baselines like Dueling Thompson Sampling (DTS) and Relative Upper Confidence Bound (RUCB). * Robustness to Non-Linearity: To test robustness, the authors also evaluated the algorithms on standard non-linear optimization benchmark functions (Quadratic, Six-Hump Camel, and Gold Stein). By adapting the algorithms to use Gaussian Processes (GPs) instead of linear Maximum Likelihood Estimation (MLE), the proposed framework remained superior to existing preference-learning baselines.
Limitations and Future Work
While theoretically optimal, the algorithms rely on Maximum Likelihood Estimation (MLE) at each step, which can become computationally expensive as the number of rounds $T$ grows. Additionally, the current work focuses on the Sigmoid/Logit link (Plackett-Luce). Future work could explore other link functions, like Probit or Nested Logit, to better model different types of human decision-making. Finally, extending this stochastic framework to "adversarial" settings—where preferences might change over time or be manipulated—remains an open and exciting challenge.
Summary updated