Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem

2013/12/12 by Masrour Zoghi, Shimon Whiteson, Zoghi, Masrour +6 · 57 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Artificial intelligence #Auction Theory and Applications #Benchmark (surveying) #Class (philosophy) #Combinatorics #Computer science #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine learning #Mathematical optimization #Mathematics #Optimization and Search Problems #Pairwise comparison #Regret #Upper and lower bounds #cs.LG

paper · pdf · doi:10.48550/arxiv.1312.3393

published in arXiv (Cornell University) 32(32), 10-18 (Cornell University) · 13 pages, 6 figures

openalex publication_date 2013/12/12 · arxiv created 2013/12/17 · arxiv updated 2013/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08

Abstract

This paper proposes a new method for the K-armed dueling bandit problem, a variation on the regular K-armed bandit problem that offers only relative feedback about pairs of arms. Our approach extends the Upper Confidence Bound algorithm to the relative setting by using estimates of the pairwise probabilities to select a promising arm and applying Upper Confidence Bound with the winner as a benchmark. We prove a finite-time regret bound of order O(log t). In addition, our empirical results using real data from an information retrieval application show that it greatly outperforms the state of the art.

Cited by

• MergeDTS: A Method for Effective Large-Scale Online Ranker Evaluation
• Regret Minimization in Stochastic Contextual Dueling Bandits
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under\n Realizability
• Reinforcement Learning from Adversarial Preferences in Tabular MDPs
• Double Thompson Sampling for Dueling Bandits
• Decoy Bandits Dueling on a Poset
• Choice functions based multi-objective Bayesian optimisation
• Dueling Posterior Sampling for Preference-Based Reinforcement Learning
• Adversarial Dueling Bandits
• Dueling Bandits With Weak Regret
• Copeland Dueling Bandits
• Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm
• Human-in-the-loop: Real-time Preference Optimization
• Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds
• ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignment
• Sample Complexity of Identifying the Nonredundancy of Nontransitive Games in Dueling Bandits

Related

• Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem
• Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm
• Reducing Dueling Bandits to Cardinal Bandits
• An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem
• Batched Dueling Bandits