# Double Thompson Sampling for Dueling Bandits

arXiv: https://arxiv.org/abs/1604.07101 · HTML: https://mlsanity.com/paper/1604.07101/

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2016.

## Built on by (most cited first, 30 of 42)

- [Efficient Exploration for LLMs](https://mlsanity.com/paper/2402.00396/) (2024)
- [Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability](https://mlsanity.com/paper/2111.12306/) (2021)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [qEUBO: A Decision-Theoretic Acquisition Function for Preferential Bayesian Optimization](https://mlsanity.com/paper/2303.15746/) (2023)
- [Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2310.00968/) (2023)
- [Scalable Reinforcement Post-Training Beyond Static Human Prompts: Evolving Alignment via Asymmetric Self-Play](https://mlsanity.com/paper/2411.00062/) (2024)
- [Borda Regret Minimization for Generalized Linear Dueling Bandits](https://mlsanity.com/paper/2303.08816/) (2023)
- [Sample-Efficient Alignment for LLMs](https://mlsanity.com/paper/2411.01493/) (2024)
- [Batched Dueling Bandits](https://mlsanity.com/paper/2202.10660/) (2022)
- [Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisons](https://mlsanity.com/paper/2203.06063/) (2022)
- [Preference learning along multiple criteria: A game-theoretic perspective](https://mlsanity.com/paper/2105.01850/) (2021)
- [Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2111.03917/) (2021)
- [Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback](https://mlsanity.com/paper/2404.10776/) (2024)
- [ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits](https://mlsanity.com/paper/2210.14322/) (2022)
- [LLM Prompt Duel Optimizer: Efficient Label-Free Prompt Optimization](https://mlsanity.com/paper/2510.13907/) (2025)
- [Bandits with Preference Feedback: A Stackelberg Game Perspective](https://mlsanity.com/paper/2406.16745/) (2024)
- [LASeR: Learning to Adaptively Select Reward Models with Multi-Armed Bandits](https://mlsanity.com/paper/2410.01735/) (2024)
- [Online Bandit Learning with Offline Preference Data for Improved RLHF](https://mlsanity.com/paper/2406.09574/) (2024)
- [Dueling Bandits with Adversarial Sleeping](https://mlsanity.com/paper/2107.02274/) (2021)
- [Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences](https://mlsanity.com/paper/2202.06694/) (2022)
- [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023)
- [One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Bandits](https://mlsanity.com/paper/2210.14998/) (2022)
- [Faster Convergence with Multiway Preferences](https://mlsanity.com/paper/2312.11788/) (2023)
- [An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem](https://mlsanity.com/paper/2209.12108/) (2022)
- [Non-Stationary Dueling Bandits Under a Weighted Borda Criterion](https://mlsanity.com/paper/2403.12950/) (2024)
- [Beyond Numeric Rewards: In-Context Dueling Bandits with LLM Agents](https://mlsanity.com/paper/2407.01887/) (2024)
- [DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback](https://mlsanity.com/paper/2410.05527/) (2024)
- [Efficient Bayesian Inference from Noisy Pairwise Comparisons](https://mlsanity.com/paper/2510.09333/) (2025)

## Abstract (arXiv)

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(K2 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 + K2 log log T) regret. Simulation results based on both synthetic and real-world data demonstrate the efficiency of the proposed D-TS algorithm.