Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Feel-Good Thompson Sampling for 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 FGTS.CDB, a Feel-Good Thompson sampling algorithm for linear contextual dueling bandits with a feel-good term over the adversarial arm, achieving near-minimax regret O~(d√T) and outperforming UCB baselines on synthetic data.
Problem
Contextual dueling bandits (preference feedback over two arms per round) lack a posterior-sampling algorithm with minimax-optimal frequentist regret; existing methods are UCB-based and restricted to finite action sets.
Approach
A Feel-Good exploration term tailored to pairwise comparisons: the likelihood for each sampled parameter includes a bonus on the max reward under the other (adversarial) arm, so the two arms are conditionally independent and the cross term in the regret analysis vanishes; arm selection is pure greedy maximization, no bonus needed.
Key results
- FGTS.CDB achieves expected regret O~(d√T) for linear contextual dueling bandits, matching the Ω(d√T) lower bound up to log factors.
- In synthetic experiments with d=5,10,15 and T=2500, FGTS.CDB outperforms MaxInP, MaxPairUCB, CoLSTIM and VACDB by a large margin with lowest variance.
- Ablation shows FGTS.CDB remains competitive even with the feel-good coefficient alpha=0 (no feel-good exploration).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FGTS.CDB instead of MaxInP, MaxPairUCB, CoLSTIM, and VACDB | Contextual dueling bandits · Synthetic data, dimensions d = 5, 10, 15 | cumulative regret | Helped |
| Vary the Feel-Good exploration scale α (ablation) | FGTS.CDB · Synthetic data, d = 5, 10, 15 | cumulative regret | No clear effect |
| Remove Feel-Good exploration (α = 0) (ablation) | FGTS.CDB · Synthetic contextual dueling bandits | cumulative regret | No clear effect |
Surprising findings
- Thompson sampling without the feel-good term (alpha=0) still performs well in the experiments, which the authors leave unexplained theoretically.
Limitations
- Experiments are limited to synthetic data with a finite random arm set of 32 arms.
- Regret bound for general nonlinear rewards scales as K√(dT) with action-set size K, not minimax in K.
- Posterior sampling is approximated by SGLD in practice, so the theory does not directly cover the implementation.
Experimental setup
Datasets: synthetic
Benchmarks: synthetic linear contextual dueling bandit simulations (d=5,10,15)
Metrics: cumulative regret standard deviation across runs
Baselines: MaxInP MaxPairUCB CoLSTIM VACDB
Builds on: Feel-Good Thompson sampling MaxInP CoLSTIM Langevin Monte Carlo
Closest papers by meaning
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.93)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.93)
- Variance-aware Regret Bounds for Stochastic Contextual Dueling Bandits (ICLR 2024 · similarity 0.93)
- Neural Dueling Bandits: Preference-Based Optimization with Human Feedback (ICLR 2025 · similarity 0.92)
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback (ICML 2025 · similarity 0.90)
- Borda Regret Minimization for Generalized Linear Dueling Bandits (ICML 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.