On-device research index

arXiv research

A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.

168,657 papers · 148 categories

Trend · papers per month

count % of corpus

11 results for “condorcet-winner”

The Sampling Complexity of Condorcet Winner Identification in Dueling Banditsstat.ML

New method identifies Condorcet winner in dueling bandits with improved sample complexity.

problem Identifying Condorcet winner in noisy pairwise comparisons.

method Exploits full gap matrix Δ to improve sample complexity.

result Improves sample complexity guarantees by leveraging informative comparisons.

Condorcet winner dueling bandits sample complexity stochastic comparisons

2026-03-16abs ↗pdf ↗

Combinatorial Pure Exploration of Dueling Banditcs.LG

This paper tackles combinatorial pure exploration for dueling bandits, aiming to find the best candidate-position match.

problem Finding the best candidate-position match in a dueling bandit setting.

method The paper adapts combinatorial pure exploration for multi-armed bandits to dueling bandits, considering both Borda winner and Condorcet winner cases. It designs PAC and exact algorithms for Borda winner and a fully polynomial time approximation scheme (FPTAS) for Condorcet winner.

result The paper introduces the first algorithm with polynomial running time per round for identifying the Condorcet winner in CPE-DB.

dueling bandits combinatorial pure exploration Borda winner Condorcet winner FPTAS

2020-06-23abs ↗pdf ↗

Non-Stationary Dueling Bandits Under a Weighted Borda Criterioncs.LG

New algorithm reduces dynamic regret in non-stationary dueling bandits using a weighted Borda score.

problem Designing algorithms with low dynamic regret in non-stationary dueling bandits.

method Introducing a novel weighted Borda score framework to analyze the Condorcet problem and establish improved bounds.

result First optimal and adaptive dynamic regret upper bound of

ilde{O}( ilde{L}^{1/3} K^{1/3} T^{2/3} )

dueling bandits non-stationary dynamic regret weighted Borda score Condorcet winner

2024-03-19abs ↗pdf ↗

Multi-Player Approaches for Dueling Banditscs.LG

New algorithms improve dueling bandit performance in multiplayer settings.

problem Challenges in collaborative exploration of non-informative arm pairs in multiplayer dueling bandits.

method Demonstrated Follow Your Leader approach and message-passing fully distributed protocol.

result Multiplayer algorithms outperform single-player benchmarks.

dueling bandits multiplayer exploration collaborative Follow Your Leader

2024-05-25abs ↗pdf ↗

ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Banditscs.LG

Improved algorithm for adaptive dueling bandits with near-optimal regret bound.

problem Non-stationary dueling bandits with unknown number of preference changes.

method Elimination-based rescheduling algorithm for adaptive dynamic regret.

result Near-optimal

ilde{O}(\sqrt{S^{ exttt{CW}} T})

dynamic regret bound.

dueling bandits non-stationary adaptive algorithms dynamic regret condorcet winner

2022-10-25abs ↗pdf ↗

Batched Dueling Banditscs.LG

New algorithms for batched dueling bandits with improved regret bounds.

problem Batched dueling bandits with noisy pairwise comparisons.

method Developed algorithms for two settings: Condorcet winner and strong stochastic transitivity.

result Regret bounds match sequential bounds using only a logarithmic number of batches.

dueling bandits batched regret Condorcet winner stochastic transitivity

2022-02-22abs ↗pdf ↗

Non-Stationary Dueling Banditscs.LG

Algorithm minimizes regret in non-stationary dueling bandits with unknown parameters.

problem Minimizing regret in dueling bandits with time-varying preferences.

method Proposes Beat the Winner Reset algorithm and meta-algorithms DETECT and Monitored Dueling Bandits.

result Proves bounds on expected weak and strong regret for non-stationary dueling bandits.

dueling bandits non-stationary regret minimization meta-algorithms Condorcet winner

2022-02-02abs ↗pdf ↗

Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Banditscs.LG

Unified framework for best arm identification and dueling bandits regret minimization.

problem Best arm identification and dueling bandits regret minimization.

method Tree-Guided Identify-Then-Exploit (TG-ITE) framework.

result Unified approach achieving optimal sample complexity and regret guarantees.

dueling bandits best arm identification regret minimization stochastic condorcet-winner

2026-06-01abs ↗pdf ↗

Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferencescs.LG

New algorithm optimizes dueling bandits for both stochastic and adversarial preferences.

problem Optimizing decision-making in environments where only relative preferences are observed.

method Proposed a reduction from dueling bandits to multi-armed bandits, achieving optimal regret bounds.

result First best-of-both-world result for dueling bandits, optimal regret bound for Condorcet-winner benchmark.

dueling bandits online learning regret minimization stochastic preferences adversarial preferences

2022-02-14abs ↗pdf ↗

Dueling Bandits with Team Comparisonscs.LG

New algorithm for identifying Condorcet team in noisy comparisons.

problem Online learning with noisy comparisons of teams.

method Formalized dueling teams problem, developed algorithms for stochastic and deterministic settings.

result Identifies Condorcet winning team with reduced number of duels.

online learning team comparisons Condorcet winner dueling bandits noisy feedback

2021-07-06abs ↗pdf ↗

Ranking-and-Selection with Multiple Correct Answers and Non-Answerable Estimatescs.LG

Unified framework for ranking-and-selection with multiple correct answers and non-answerable estimates

problem Fixed-precision ranking-and-selection in structured settings with non-unique answers and non-answerable estimates

method Unified framework based on answer-wise acceptance sets, restricted generalized likelihood ratio stopping, and answer-pitfall decomposition

result Unified recipe performs well across a broad range of pure-exploration problems

ranking-and-selection structured settings non-unique answers non-answerable estimates fixed-precision

2026-06-20abs ↗pdf ↗