Research map / Bandits and online learning / Multi-armed bandits
Batched Dueling Bandits
Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan
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 |
|---|---|---|---|
| Use a seed set and eliminate active arms through seed comparisons instead of all-pairs comparisons initially | SCOMP · Batched dueling bandits, SST + STI | instance-dependent expected regret: 3KT^{1/B} \log\left(6TK^2B\right) \sum_{j: \epsilon_{j} > 0} \frac{1}{\epsilon_{j}} -> \sum_{j: \epsilon_{j} > 0}O\left( | Improved |
| Add a candidate-selection round among seed arms before eliminating active arms (ablation) | SCOMP2 · Batched dueling bandits, SST + STI | worst-case expected regret: O\left(\frac{K\sqrt{K}T^{1/B}\log(T)}{\epsilon_{\min}}\right) -> O\left(\frac{KBT^{1/B} \log(T)}{\epsilon_{\min}}\right) | Improved |
| Reduce seed inclusion probability from 1/√K to K^{-2/3} (ablation) | SCOMP · Batched dueling bandits, SST + STI | worst-case expected regret: O\left(\frac{K\sqrt{K}T^{1/B}\log(T)}{\epsilon_{\min}}\right) -> O\left(\frac{K^{4/3}T^{1/B}\log(T)}{\epsilon_{\min}}\ri | Improved |
| Add recursive rounds and use a seed set of size K^η (ablation) | Recursive seeded algorithm · Batched dueling bandits, SST + STI | instance-dependent expected regret: B+2: K^{0.39} \,\, T^{1/B} \,\, \log(T) \,\, E; B+3: K^{0.32} \,\, T^{1/B} \,\, \log(T) \,\, E; B+5: K^{0.25} \,\, T^{1/ | Improved |
| Increase the number of batches B (ablation) | SCOMP2 · Six rankers, Sushi, SYN-BTL, SYN-CD | cumulative regret | Improved |
| Use SCOMP2 rather than BTM | Batched dueling bandits · Six rankers, Sushi, SYN-BTL, SYN-CD | cumulative regret | Improved |
| Use SCOMP2 rather than RUCB | Batched dueling bandits · Six rankers, Sushi, SYN-BTL, SYN-CD | cumulative regret: 3 out of the 4 datasets | Mixed |
| Use PCOMP or SCOMP rather than BTM | Batched dueling bandits · Six rankers and Sushi | cumulative regret | Improved |
| Use PCOMP or SCOMP rather than BTM | Batched dueling bandits · Synthetic data | cumulative regret | Mixed |
| Increase the number of batches for SCOMP2 (ablation) | SCOMP2 · SYN-BTL | cumulative regret | Improved |
Closest papers by meaning
- On Weak Regret Analysis for Dueling Bandits (NeurIPS 2024 · similarity 0.92)
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.92)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.90)
- Fusing Reward and Dueling Feedback in Stochastic Bandits (ICML 2025 · similarity 0.90)
- Borda Regret Minimization for Generalized Linear Dueling Bandits (ICML 2024 · similarity 0.90)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.90)
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.
