Research map / Bandits and online learning / Multi-armed bandits
Combinatorial Pure Exploration for Dueling Bandit
Wei Chen, Yihan Du, Longbo Huang, Haoyu Zhao
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce Borda winner identification to conventional CPE-MAB using edge rewards defined by average preference against a uniformly sampled matching | CPE-DB Borda winner identification · CPE-DB Borda winner | sample complexity: O \left ( H^B_{\varepsilon} \ln \left ( \frac{H^B_{\varepsilon}}{\delta} \right) \right) | Improved |
| Use almost-uniform matching sampling and adjust confidence bounds for sampler bias | CLUCB-Borda-PAC · CPE-DB Borda winner | sample complexity: O \left ( H^B_{\varepsilon} \ln \left ( \frac{H^B_{\varepsilon}}{\delta} \right) \right) | Improved |
| Use the PAC algorithm in shrinking-accuracy epochs to identify the exact Borda winner | CLUCB-Borda-Exact · CPE-DB Borda winner | sample complexity: O \Bigg( \textup{width}(G)^2 H^B \cdot \ln \left(\frac{\ell}{\Delta^B_{\textup{min}}} \right) \cdot\Bigg(\ln \left ( \fr | Mixed |
| Classify edges by comparing constrained optimization values under upper and lower confidence matrices | CAR-Cond · CPE-DB Condorcet winner | sample complexity: O\left(\sum_{j=1}^{\ell}\sum_{ e\neq e',e,e'\in E_j}\frac{1}{(\Delta^C_{e,e'})^2}\ln\left(\frac{K}{\delta(\Delta^C_{e,e' | Improved |
| Add verification and parallel simulation to the CAR-Cond-based procedure | CAR-Parallel · CPE-DB Condorcet winner | expected sample complexity: O\left(\sum_{j=1}^{\ell}\sum_{\begin{subarray}{c} e\neq e' \\ e,e'\in E_j\end{subarray}}\frac{\ln\left(K/(\Delta^C_{e,e' | Improved |
Closest papers by meaning
- Identification of the Generalized Condorcet Winner in Multi-dueling Bandits (NeurIPS 2021 · similarity 0.90)
- The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits (NeurIPS 2026 · similarity 0.90)
- Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit (AAAI 2024 · similarity 0.90)
- On Weak Regret Analysis for Dueling Bandits (NeurIPS 2024 · similarity 0.87)
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.87)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
