Reducing Dueling Bandits to Cardinal Bandits

Abstract

We present algorithms for reducing the Dueling Bandits problem to the conventional (stochastic) Multi-Armed Bandits problem. The Dueling Bandits problem is an online model of learning with ordinal feedback of the form "A is preferred to B" (as opposed to cardinal feedback like "A has value 2.5"), giving it wide applicability in learning from implicit user feedback and revealed and stated preferences. In contrast to existing algorithms for the Dueling Bandits problem, our reductions -- named $\Doubler$, $\MultiSbm$ and $\DoubleSbm$ -- provide a generic schema for translating the extensive body of known results about conventional Multi-Armed Bandit algorithms to the Dueling Bandits setting. For $\Doubler$ and $\MultiSbm$ we prove regret upper bounds in both finite and infinite settings, and conjecture about the performance of $\DoubleSbm$ which empirically outperforms the other two as well as previous algorithms in our experiments. In addition, we provide the first almost optimal regret bound in terms of second order terms, such as the differences between the values of the arms.

References in corpus (3)

• An Adaptive Algorithm for Finite Stochastic Partial Monitoring
• Decoupling Exploration and Exploitation in Multi-Armed Bandits
• Active Learning Using Smooth Relative Regret Approximations with Applications

Cited by in corpus (15)

• Online Stochastic Linear Optimization under One-bit Feedback
• Preference-based Online Learning with Dueling Bandits: A Survey
• Copeland Dueling Bandits
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• MergeDTS: A Method for Effective Large-Scale Online Ranker Evaluation
• Zeroth Order Non-convex optimization with Dueling-Choice Bandits
• Dueling RL: Reinforcement Learning with Trajectory Preferences
• Dueling Bandits with Adversarial Sleeping
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
• Best-item Learning in Random Utility Models with Subset Choices
• Combinatorial Bandits without Total Order for Arms
• KLUCB Approach to Copeland Bandits
• Simple Algorithms for Dueling Bandits
• Decoy Bandits Dueling on a Poset
• Adversarial Dueling Bandits