mlsanityData to 7 Oct 2026

Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem

arXiv 1506.02550 ↗First posted 8 Jun 2015stat.ML cs.LGcited by 51

Not on the map. Why?

Abstract (arXiv)

We study the K-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. We introduce a tight asymptotic regret lower bound that is based on the information divergence. An algorithm that is inspired by the Deterministic Minimum Empirical Divergence algorithm (Honda and Takemura, 2010) is proposed, and its regret is analyzed. The proposed algorithm is found to be the first one with a regret upper bound that matches the lower bound. Experimental comparisons of dueling bandit algorithms show that the proposed algorithm significantly outperforms existing ones.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Jun 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

51 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 244
  2. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  3. 2024Iterative Data Smoothing: Mitigating Reward Overfitting and Overoptimization in RLHFcited by 57
  4. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  5. 2024Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferencescited by 27
  6. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  7. 2024Optimal Design for Reward Modeling in RLHFcited by 23
  8. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  9. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  10. 2022Batched Dueling Banditscited by 10
  11. 2022Active Evaluation: Efficient NLG Evaluation with Few Pairwise Comparisonscited by 10
  12. 2021Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary Dueling Banditscited by 9
38 more
  1. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  2. 2025Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedbackcited by 9
  3. 2025ActiveDPO: Active Direct Preference Optimization for Sample-Efficient Alignmentcited 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. 2022Non-Stationary Dueling Banditscited by 7
  7. 2023Dueling Optimization with a Monotone Adversarycited by 7
  8. 2024Neural Dueling Bandits: Preference-Based Optimization with Human Feedbackcited by 7
  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. 2025Active Human Feedback Collection via Neural Contextual Dueling Banditscited by 4
  13. 2021Learning the Optimal Recommendation from Explorative Userscited by 3
  14. 2022One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Banditscited by 3
  15. 2024Biased Dueling Bandits with Stochastic Delayed Feedbackcited by 3
  16. 2025Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Designcited by 3
  17. 2022An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problemcited by 2
  18. 2024Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncited by 2
  19. 2024Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Duelingcited by 2
  20. 2024Multi-Player Approaches for Dueling Banditscited by 2
  21. 2024DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedbackcited by 2
  22. 2025Federated Linear Dueling Banditscited by 2
  23. 2025Online Clustering of Dueling Banditscited by 2
  24. 2025Reinforcement Learning from Adversarial Preferences in Tabular MDPscited by 2
  25. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  26. 2026Duel-Evolve: Reward-Free Test-Time Scaling via LLM Self-Preferencescited by 2
  27. 2024The Power of Active Multi-Task Learning in Reinforcement Learning from Human Feedbackcited by 1
  28. 2024Adversarial Multi-dueling Banditscited by 1
  29. 2025Fusing Reward and Dueling Feedback in Stochastic Banditscited by 1
  30. 2026Lipschitz Dueling Bandits over Continuous Action Spacescited by 1
  31. 2022Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamicscited by 0
  32. 2023Identifying Copeland Winners in Dueling Bandits with Indifferencescited by 0
  33. 2023Direct Preference-Based Evolutionary Multi-Objective Optimization with Dueling Banditcited by 0
  34. 2025Multimodal Bandits: Regret Lower Bounds and Optimal Algorithmscited by 0
  35. 2026Learning in Context, Guided by Choice: A Reward-Free Paradigm for Reinforcement Learning with Transformerscited by 0
  36. 2026Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectivescited by 0
  37. 2026Multi-User Dueling Bandits: A Fair Approach using Nash Social Welfarecited by 0
  38. 2026Linear and Neural Dueling Bandits with Delayed Feedbackcited by 0

50 most cited of 51 All 51 (JSON)