Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Variance-Aware Feel-Good Thompson Sampling for Contextual 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-VA, a variance-aware feel-good Thompson sampling algorithm for general-function contextual bandits with variance-weighted log-likelihood and a generalized decoupling coefficient, achieving near-optimal variance-dependent regret.
Problem
Variance-dependent regret bounds for contextual bandits have mostly been studied for UCB methods; Thompson sampling variants lack optimal-in-dimension variance-aware guarantees, and the only TS variant (LinVDTS) is linear and suboptimal in d.
Approach
Uses a Type-B feel-good posterior with variance-dependent weights eta_s = 1/sigma_bar_s^2 on squared losses and a feel-good term lambda_t = c*sqrt(Lambda_t)/sigma_bar_t^2 on the current step, plus a generalized decoupling coefficient that handles the non-constant weights, yielding regret O(sqrt((1+Lambda) dc log|F|) + dc) without knowing T or Lambda in advance.
Key results
- Theory: expected regret O(sqrt((1+Lambda) dc log|F|) + dc); for linear bandits this gives nearly optimal d*sqrt(Lambda)+d, and O(dc) in the deterministic case.
- Synthetic experiments (d=5, 100 runs): FGTS-VA with c=0.003 outperforms Weighted OFUL+, SAVE and FGTS by a large margin under both sparse and dense noise.
- Ablation: feel-good exploration (c bounded away from 0) helps under sparse noise, while the optimal c is near 0 under dense noise.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FGTS-VA instead of the baselines | Linear bandits with sparse or dense noise · Synthetic linear bandits, sparse and dense noise | regret | Helped |
| choose c bounded away from 0 rather than near 0 (ablation) | FGTS-VA · Synthetic linear bandits, sparse noise | regret | Helped |
| choose c close to 0 rather than bounded away from 0 (ablation) | FGTS-VA · Synthetic linear bandits, dense noise | regret | Helped |
Surprising findings
- For dense heteroscedastic noise the optimal feel-good coefficient c is close to zero, indicating exploration bonus is not needed there.
Limitations
- Requires variance sigma_t^2 to be revealed to the agent at the start of step t (weak adversary with variance revealing).
- Experiments are limited to a small synthetic linear bandit with d=5.
- Hyperparameter c is the only tunable parameter and its theoretical choice depends on unknown decoupling coefficient and log|F|.
Experimental setup
Benchmarks: synthetic linear bandit (d=5, hypercube action set)
Metrics: cumulative regret
Baselines: Weighted OFUL+ SAVE FGTS LinVDTS
Builds on: Feel-Good Thompson sampling LinVDTS Weighted OFUL+ SAVE Eluder dimension
Closest papers by meaning
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.94)
- Feel-Good Thompson Sampling for Contextual Dueling Bandits (ICML 2024 · similarity 0.93)
- Catoni Contextual Bandits are Robust to Heavy-tailed Rewards (ICML 2025 · similarity 0.91)
- Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling (ICLR 2024 · similarity 0.91)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.90)
- How Does Variance Shape the Regret in Contextual Bandits? (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.