# Batched Dueling Bandits

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 44 references that are in the map.
- First posted on arXiv 22 Feb 2022.

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

- [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)
- [Parallelizing greedy for submodular set function maximization in matroids and beyond](https://mlsanity.com/paper/1811.12568/) (2018)
- [Stochastic Submodular Cover with Limited Adaptivity](https://mlsanity.com/paper/1810.13351/) (2018)
- [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)
- [Stochastic Matching with Few Queries: (1-varepsilon) Approximation](https://mlsanity.com/paper/2002.11880/) (2020)

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

- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [A Lipschitz Bandits Approach for Continuous Hyperparameter Optimization](https://mlsanity.com/paper/2302.01539/) (2023)
- [When Can We Track Significant Preference Shifts in Dueling Bandits?](https://mlsanity.com/paper/2302.06595/) (2023)
- [An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem](https://mlsanity.com/paper/2209.12108/) (2022)
- [Batched Stochastic Bandit for Nondegenerate Functions](https://mlsanity.com/paper/2405.05733/) (2024)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [From Random Search to Bandit Learning in Metric Measure Spaces](https://mlsanity.com/paper/2305.11509/) (2023)
- [Batched Bandits with Heavy-Tailed Rewards](https://mlsanity.com/paper/2510.03798/) (2025)
- [Consecutive Preferential Bayesian Optimization](https://mlsanity.com/paper/2511.05163/) (2025)
- [Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits](https://mlsanity.com/paper/2606.01799/) (2026)

## Abstract (arXiv)

The K-armed dueling bandit problem, where the feedback is in the form of noisy pairwise comparisons, has been widely studied. Previous works have only focused on the sequential setting where the policy adapts after every comparison. However, in many applications such as search ranking and recommendation systems, it is preferable to perform comparisons in a limited number of parallel batches. We study the batched K-armed dueling bandit problem under two standard settings: (i) existence of a Condorcet winner, and (ii) strong stochastic transitivity and stochastic triangle inequality. For both settings, we obtain algorithms with a smooth trade-off between the number of batches and regret. Our regret bounds match the best known sequential regret bounds (up to poly-logarithmic factors), using only a logarithmic number of batches. We complement our regret analysis with a nearly-matching lower bound. Finally, we also validate our theoretical results via experiments on synthetic and real data.