mlsanityData to 7 Oct 2026

Double Thompson Sampling for Dueling Bandits

arXiv 1604.07101 ↗First posted 25 Apr 2016cs.LG stat.MLcited by 42

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 7; 2023: 7; 2024: 13; 2025: 3; 2026: 7.

42 papers.

Sort:

By area:

  1. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  2. 2024Efficient Exploration for LLMscited by 44
  3. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  4. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  5. 2023qEUBO: A Decision-Theoretic Acquisition Function for Preferential Bayesian Optimizationcited by 23
  6. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  7. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  8. 2024Scalable Reinforcement Post-Training Beyond Static Human Prompts: Evolving Alignment via Asymmetric Self-Playcited by 21
  9. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  10. 2024Sample-Efficient Alignment for LLMscited by 16
  11. 2022Batched Dueling Banditscited by 10
  12. 2022Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisonscited by 10
30 more
  1. 2021Preference learning along multiple criteria: A game-theoretic perspectivecited by 9
  2. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
  3. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  4. 2022ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscited by 8
  5. 2025LLM Prompt Duel Optimizer: Efficient Label-Free Prompt Optimizationcited by 8
  6. 2024Bandits with Preference Feedback: A Stackelberg Game Perspectivecited by 7
  7. 2024LASeR: Learning to Adaptively Select Reward Models with Multi-Armed Banditscited by 7
  8. 2024Online Bandit Learning with Offline Preference Data for Improved RLHFcited by 6
  9. 2021Dueling Bandits with Adversarial Sleepingcited by 5
  10. 2022Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescited by 5
  11. 2023When Can We Track Significant Preference Shifts in Dueling Bandits?cited by 5
  12. 2022One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Banditscited by 3
  13. 2022An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problemcited by 2
  14. 2023Faster Convergence with Multiway Preferencescited by 2
  15. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  16. 2024Beyond Numeric Rewards: In-Context Dueling Bandits with LLM Agentscited by 2
  17. 2024DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedbackcited by 2
  18. 2025Efficient Bayesian Inference from Noisy Pairwise Comparisonscited by 2
  19. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  20. 2026Duel-Evolve: Reward-Free Test-Time Scaling via LLM Self-Preferencescited by 2
  21. 2024Adversarial Multi-dueling Banditscited by 1
  22. 2026ActiveUltraFeedback: Efficient Preference Data Generation using Active Learningcited by 1
  23. 2021Statistical Consequences of Dueling Banditscited by 0
  24. 2023Identifying Copeland Winners in Dueling Bandits with Indifferencescited by 0
  25. 2023Direct Preference-Based Evolutionary Multi-Objective Optimization with Dueling Banditcited by 0
  26. 2026Learning in Context, Guided by Choice: A Reward-Free Paradigm for Reinforcement Learning with Transformerscited by 0
  27. 2026PARWiS: Winner determination under shoestring budgets using active pairwise comparisonscited by 0
  28. 2026A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedbackcited by 0
  29. 2026Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Banditscited by 0
  30. 2026On the Complexity of Preference-Based Banditscited by 0