# Dueling Bandits with Team Comparisons

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 6 Jul 2021.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Multi-dueling Bandits with Dependent Arms](https://mlsanity.com/paper/1705.00253/) (2017)
- [Towards Instance Optimal Bounds for Best Arm Identification](https://mlsanity.com/paper/1608.06031/) (2016)
- [Top-k Combinatorial Bandits with Full-Bandit Feedback](https://mlsanity.com/paper/1905.12624/) (2019)
- [PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds](https://mlsanity.com/paper/1806.02970/) (2018)
- [Multi-Dueling Bandits and Their Application to Online Ranker Evaluation](https://mlsanity.com/paper/1608.06253/) (2016)
- [The Sample Complexity of Best-k Items Selection from Pairwise Comparisons](https://mlsanity.com/paper/2007.03133/) (2020)
- [Learning Combinatorial Functions from Pairwise Comparisons](https://mlsanity.com/paper/1605.09227/) (2016)

## Abstract (arXiv)

We introduce the dueling teams problem, a new online-learning setting in which the learner observes noisy comparisons of disjoint pairs of k-sized teams from a universe of n players. The goal of the learner is to minimize the number of duels required to identify, with high probability, a Condorcet winning team, i.e., a team which wins against any other disjoint team (with probability at least 1/2). Noisy comparisons are linked to a total order on the teams. We formalize our model by building upon the dueling bandits setting (Yue et al.2012) and provide several algorithms, both for stochastic and deterministic settings. For the stochastic setting, we provide a reduction to the classical dueling bandits setting, yielding an algorithm that identifies a Condorcet winning team within O((n + k log (k)) fracmax(loglog n, log k)Delta2) duels, where Delta is a gap parameter. For deterministic feedback, we additionally present a gap-independent algorithm that identifies a Condorcet winning team within O(nklog(k)+k5) duels.