Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Variance-aware Regret Bounds for Stochastic Contextual 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.
Proposes VACDB, a computationally efficient SupLinUCB-style layered elimination algorithm for contextual dueling bandits with GLM (Bernoulli) feedback, achieving a variance-aware regret bound Õ(d√(Σσ_t²)+d).
Problem
Regret minimization in contextual dueling bandits with binary preference feedback from a GLM, where the regret should depend on the variance of pairwise comparisons rather than only worst-case bounds.
Approach
Combines a multi-layer elimination structure with a regularized MLE, Freedman-type concentration with per-layer weights, a variance-aware adaptive confidence radius estimated from the fitted model, and a symmetric arm-pair selection rule, so that deterministic comparisons yield Õ(d) regret.
Key results
- Theoretical regret Õ(d√(Σσ_t²)+d); reduces to Õ(d√T) in worst case, matching Ω(d√T) lower bound up to logs.
- In deterministic comparisons the regret is Õ(d), versus worst-case bounds for variance-agnostic methods.
- On synthetic experiments (128 runs, d=5, T=4000), VACDB achieves lower average regret than MaxInP, MaxPairUCB and CoLSTIM, and regret decreases as the variance decreases when θ* is scaled.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use VACDB instead of the compared baselines | Contextual dueling bandit algorithms · Synthetic data | average cumulative regret | Helped |
| Use MaxPairUCB or CoLSTIM instead of MaxInP | Contextual dueling bandit algorithms · Synthetic data | average cumulative regret | Helped |
| Increase the scale of the unknown parameter, reducing comparison variance | VACDB · Synthetic data with varying variance | cumulative regret | Helped |
| Use VACDB instead of MaxInP | Contextual dueling bandit algorithms · EventTime | cumulative regret | Helped |
| Use VACDB in the deterministic-comparison setting | Contextual dueling bandits · Deterministic comparisons | cumulative average regret upper bound | Helped |
Surprising findings
- An unrigorous argument in prior GLM bandit MLE analysis was identified and fixed via Brouwer's invariance of domain theorem.
Limitations
- Assumes a generalized linear (linear stochastic transitivity) preference model, which may be restrictive in practice.
- Experiments limited to synthetic data (plus an appendix real-data experiment); algorithm only outperforms baselines after about 2500 rounds on EventTime.
- Tuning the confidence radius per algorithm was needed to showcase best performance.
Experimental setup
Datasets: EventTime
Benchmarks: synthetic contextual dueling bandit simulation EventTime (appendix)
Metrics: cumulative average regret
Baselines: MaxInP MaxPairUCB CoLSTIM Sta'D SupCoLSTIM
Builds on: SupLinUCB Sta'D SupCoLSTIM MaxInP Weighted OFUL
Closest papers by meaning
- Borda Regret Minimization for Generalized Linear Dueling Bandits (ICML 2024 · similarity 0.93)
- Feel-Good Thompson Sampling for Contextual Dueling Bandits (ICML 2024 · similarity 0.93)
- On Weak Regret Analysis for Dueling Bandits (NeurIPS 2024 · similarity 0.93)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.93)
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback (ICML 2025 · similarity 0.92)
- Fusing Reward and Dueling Feedback in Stochastic Bandits (ICML 2025 · similarity 0.91)
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.