Double Thompson Sampling for Dueling Bandits

Abstract

In this paper, we propose a Double Thompson Sampling (D-TS) algorithm for dueling bandit problems. As indicated by its name, D-TS selects both the first and the second candidates according to Thompson Sampling. Specifically, D-TS maintains a posterior distribution for the preference matrix, and chooses the pair of arms for comparison by sampling twice from the posterior distribution. This simple algorithm applies to general Copeland dueling bandits, including Condorcet dueling bandits as its special case. For general Copeland dueling bandits, we show that D-TS achieves $O(K^2\log T)$ regret. For Condorcet dueling bandits, we further simplify the D-TS algorithm and show that the simplified D-TS algorithm achieves $O(K\log T+K^2\log \log T)$ regret. Simulation results based on both synthetic and real-world data demonstrate the efficiency of the proposed D-TS algorithm.

27 pages, 5 figures, 9 tables; accepted by 30th Conference on Neural Information Processing Systems (NIPS), 2016

Cited by in corpus (16)

• Preferential Bayesian Optimization
• Preference-based Online Learning with Dueling Bandits: A Survey
• Combinatorial Pure Exploration of Dueling Bandit
• Correlational Dueling Bandits with Application to Clinical Treatment in Large Decision Spaces
• Asynchronous Parallel Empirical Variance Guided Algorithms for the Thresholding Bandit Problem
• MergeDTS: A Method for Effective Large-Scale Online Ranker Evaluation
• A Bayesian Choice Model for Eliminating Feedback Loops
• Preferential Batch Bayesian Optimization
• Regret Minimization in Stochastic Contextual Dueling Bandits
• Dueling Bandits with Qualitative Feedback
• Adversarial Dueling Bandits
• KLUCB Approach to Copeland Bandits
• Dueling Bandits with Adversarial Sleeping
• Statistical Consequences of Dueling Bandits
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
• Simple Algorithms for Dueling Bandits