Research map / Bandits and online learning / Multi-armed bandits
On Weak Regret Analysis for Dueling Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies weak regret minimization for K-armed dueling bandits with only a Condorcet winner assumed; proposes WR-TINF (Tsallis-INF reduction with modified sampling) and WR-EXP3-IX, proves a matching lower bound in a special class, and compares them numerically.
Problem
Minimizing weak regret (loss incurred only when neither chosen arm is the Condorcet winner) in stochastic dueling bandits under only the existence of a Condorcet winner; the optimal dependence on K and the gap matrix was unknown.
Approach
Adapts the Tsallis-INF best-of-both-worlds reduction from strong regret to weak regret by modifying the sampling scheme (drawing the second arm from a flattened distribution p^{2/3} when both arms coincide) to induce extra exploration, and introduces WR-EXP3-IX which exploits sub-optimal-vs-sub-optimal duels to eliminate sub-optimal arms.
Key results
- WR-TINF achieves weak regret bound sqrt(K/Δ*) * sqrt(sum 1/Δ_{k*,k}), improving over prior K^2/min Δ^2 (WS-W) and K^2+K/Δ^4 (BTW) bounds.
- A lower bound of order K/Δ_cw on weak regret is proven over a class of instances with uniform Condorcet gaps, showing WR-TINF is optimal there.
- In simulations, WR-TINF has larger regret for small K but scales better with K than WS-W, and WR-EXP3-IX wins when sub-optimal gaps are large relative to Condorcet gaps.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use WR-TINF instead of prior weak-regret approaches | Weak-regret dueling bandits with a Condorcet winner · Condorcet-winner instances | weak regret upper bound: K/ mini̸=k∗∆k∗,i | Helped |
| explore duels between sub-optimal arms using WR-EXP3-IX | Weak-regret dueling bandits · Instances where sub-optimal-arm gaps are large relative to Condorcet-winner gaps | weak regret upper bound: K2(∆cw/∆2sub) | Helped |
| use WR-TINF rather than WR-EXP3-IX | Weak-regret dueling bandits · Instances where the Condorcet-winner gap is not negligible | weak regret upper bound: K/∆cw | Helped |
| explore the complete gap structure with WR-EXP3-IX rather than relying only on gaps to the Condorcet winner | Weak-regret dueling bandits · Instances with large gaps between sub-optimal arms | weak regret: K2∆cw/∆2sub | Helped |
| use WR-TINF with its increased exploration | Dueling bandits · Scenario 2, strong regret | strong regret | No clear effect |
| use WS-W on a large instance without strong stochastic transitivity | Weak-regret dueling bandits · Scenario 3 | weak regret | Hurt |
Surprising findings
- Algorithms optimal for strong regret (e.g., Versatile-DB) are not expected to be optimal for weak regret, and the paper shows the weak regret of WS-W has high variance due to Condorcet winner losing early duels.
Limitations
- WR-TINF is optimal only in certain regimes; no algorithm fully adapts to the problem parameters.
- The lower bound assumes uniform Condorcet gaps and a general identifiability assumption.
- WR-EXP3-IX has quadratic dependence on K.
Experimental setup
Benchmarks: simulated dueling bandit scenarios (K=30, 150, 400)
Metrics: weak regret strong regret
Baselines: WS-W Versatile-DB BTW
Builds on: Sparring (Ailon et al.) Tsallis-INF EXP3-IX Beat The Winner WS-W
Closest papers by meaning
- Dueling Bandits with Weak Regret (ICML 2017 · similarity 0.95)
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.93)
- Borda Regret Minimization for Generalized Linear Dueling Bandits (ICML 2024 · similarity 0.93)
- The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits (NeurIPS 2026 · similarity 0.90)
- Fusing Reward and Dueling Feedback in Stochastic Bandits (ICML 2025 · similarity 0.90)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.89)
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.