# An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 59 references that are in the map.
- First posted on arXiv 25 Sep 2022.

## Builds on (most cited first, 26 of 26)

- [Introducing LETOR 4.0 Datasets](https://mlsanity.com/paper/1306.2597/) (2013)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Double Thompson Sampling for Dueling Bandits](https://mlsanity.com/paper/1604.07101/) (2016)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [Multi-dueling Bandits with Dependent Arms](https://mlsanity.com/paper/1705.00253/) (2017)
- [Sparse Dueling Bandits](https://mlsanity.com/paper/1502.00133/) (2015)
- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Combinatorial Bandits with Relative Feedback](https://mlsanity.com/paper/1903.00543/) (2019)
- [Copeland Dueling Bandit Problem: Regret Lower Bound, Optimal Algorithm, and Computationally Efficient Algorithm](https://mlsanity.com/paper/1605.01677/) (2016)
- [Dueling Bandits With Weak Regret](https://mlsanity.com/paper/1706.04304/) (2017)
- [An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation](https://mlsanity.com/paper/1804.06355/) (2018)
- [A Stochastic Probing Problem with Applications](https://mlsanity.com/paper/1302.5913/) (2013)
- [Non-monotone Submodular Maximization in Exponentially Fewer Iterations](https://mlsanity.com/paper/1807.11462/) (2018)
- [Batched Dueling Bandits](https://mlsanity.com/paper/2202.10660/) (2022)
- [Parallelizing greedy for submodular set function maximization in matroids and beyond](https://mlsanity.com/paper/1811.12568/) (2018)
- [Parallel Algorithms for Select and Partition with Noisy Comparisons](https://mlsanity.com/paper/1603.04941/) (2016)
- [Stochastic Submodular Cover with Limited Adaptivity](https://mlsanity.com/paper/1810.13351/) (2018)
- [Sorted Top-k in Rounds](https://mlsanity.com/paper/1906.05208/) (2019)
- [The Power of Adaptivity for Stochastic Submodular Cover](https://mlsanity.com/paper/2106.16115/) (2021)
- [On the Adaptivity Gap of Stochastic Orienteering](https://mlsanity.com/paper/1311.3623/) (2013)
- [Instance-Optimality in the Noisy Value-and Comparison-Model --- Accept, Accept, Strong Accept: Which Papers get in?](https://mlsanity.com/paper/1806.08182/) (2018)
- [Stochastic Matching with Few Queries: (1-varepsilon) Approximation](https://mlsanity.com/paper/2002.11880/) (2020)

## Built on by (most cited first, 2 of 2)

- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [Continuum-armed Bandit Optimization with Batch Pairwise Comparison Oracles](https://mlsanity.com/paper/2505.22361/) (2025)

## Abstract (arXiv)

We study the K-armed dueling bandit problem, a variation of the traditional multi-armed bandit problem in which feedback is obtained in the form of pairwise comparisons. Previous learning algorithms have focused on the textitfully adaptive setting, where the algorithm can make updates after every comparison. The "batched" dueling bandit problem is motivated by large-scale applications like web search ranking and recommendation systems, where performing sequential updates may be infeasible. In this work, we ask: textitis there a solution using only a few adaptive rounds that matches the asymptotic regret bounds of the best sequential algorithms for K-armed dueling bandits? We answer this in the affirmative textitunder the Condorcet condition, a standard setting of the K-armed dueling bandit problem. We obtain asymptotic regret of O(K2log2(K)) + O(Klog(T)) in O(log(T)) rounds, where T is the time horizon. Our regret bounds nearly match the best regret bounds known in the fully sequential setting under the Condorcet condition. Finally, in computational experiments over a variety of real-world datasets, we observe that our algorithm using O(log(T)) rounds achieves almost the same performance as fully sequential algorithms (that use T rounds).