# Combinatorial Pure Exploration of Dueling Bandit

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2020.

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

- [Thompson Sampling for Bandit Learning in Matching Markets](https://mlsanity.com/paper/2204.12048/) (2022)
- [Active Ranking of Experts Based on their Performances in Many Tasks](https://mlsanity.com/paper/2306.02628/) (2023)
- [Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget](https://mlsanity.com/paper/2202.04487/) (2022)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Clustering Items through Bandit Feedback: Finding the Right Feature out of Many](https://mlsanity.com/paper/2503.11209/) (2025)
- [Pure Exploration with Structured Preference Feedback](https://mlsanity.com/paper/2104.05294/) (2021)
- [A Fast Algorithm for PAC Combinatorial Pure Exploration](https://mlsanity.com/paper/2112.04197/) (2021)
- [Ranking-and-Selection with Multiple Correct Answers and Non-Answerable Estimates](https://mlsanity.com/paper/2606.21889/) (2026)

## Abstract (arXiv)

In this paper, we study combinatorial pure exploration for dueling bandits (CPE-DB): we have multiple candidates for multiple positions as modeled by a bipartite graph, and in each round we sample a duel of two candidates on one position and observe who wins in the duel, with the goal of finding the best candidate-position matching with high probability after multiple rounds of samples. CPE-DB is an adaptation of the original combinatorial pure exploration for multi-armed bandit (CPE-MAB) problem to the dueling bandit setting. We consider both the Borda winner and the Condorcet winner cases. For Borda winner, we establish a reduction of the problem to the original CPE-MAB setting and design PAC and exact algorithms that achieve both the sample complexity similar to that in the CPE-MAB setting (which is nearly optimal for a subclass of problems) and polynomial running time per round. For Condorcet winner, we first design a fully polynomial time approximation scheme (FPTAS) for the offline problem of finding the Condorcet winner with known winning probabilities, and then use the FPTAS as an oracle to design a novel pure exploration algorithm sf CAR-sf Cond with sample complexity analysis. sf CAR-sf Cond is the first algorithm with polynomial running time per round for identifying the Condorcet winner in CPE-DB.