# Adversarial Multi-dueling Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 28 references that are in the map.
- First posted on arXiv 18 Jun 2024.

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

- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem](https://mlsanity.com/paper/1506.02550/) (2015)
- [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)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits](https://mlsanity.com/paper/1601.03855/) (2016)
- [Sparse Dueling Bandits](https://mlsanity.com/paper/1502.00133/) (2015)
- [PAC Battling Bandits in the Plackett-Luce Model](https://mlsanity.com/paper/1808.04008/) (2018)
- [Multi-Dueling Bandits and Their Application to Online Ranker Evaluation](https://mlsanity.com/paper/1608.06253/) (2016)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons](https://mlsanity.com/paper/1909.03194/) (2019)
- [Utility-based Dueling Bandits as a Partial Monitoring Game](https://mlsanity.com/paper/1507.02750/) (2015)
- [Dueling Bandits: From Two-dueling to Multi-dueling](https://mlsanity.com/paper/2211.10293/) (2022)

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

- [Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives](https://mlsanity.com/paper/2603.18972/) (2026)

## Abstract (arXiv)

We introduce the problem of regret minimization in adversarial multi-dueling bandits. While adversarial preferences have been studied in dueling bandits, they have not been explored in multi-dueling bandits. In this setting, the learner is required to select m ≥ 2 arms at each round and observes as feedback the identity of the most preferred arm which is based on an arbitrary preference matrix chosen obliviously. We introduce a novel algorithm, MiDEX (Multi Dueling EXP3), to learn from such preference feedback that is assumed to be generated from a pairwise-subset choice model. We prove that the expected cumulative T-round regret of MiDEX compared to a Borda-winner from a set of K arms is upper bounded by O((K log K)1/3 T2/3). Moreover, we prove a lower bound of Omega(K1/3 T2/3) for the expected regret in this setting which demonstrates that our proposed algorithm is near-optimal.