Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown
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.
Empirical study of Feel-Good Thompson Sampling (FG-TS) and smoothed FG-TS with approximate MCMC posterior samplers (LMC, MALA, HMC, underdamped LMC, SVRG, preconditioning) across linear, logistic, and neural contextual bandits.
Problem
How approximate (MCMC-based) posterior sampling affects the performance of Feel-Good Thompson Sampling and its smoothed variant in contextual bandits, where theory assumes exact posteriors.
Approach
Benchmarks FG-TS and SFG-TS paired with a range of MCMC samplers (LMC, MALA, HMC, ULMC, SVRG, preconditioned variants) against classical bandit baselines on synthetic and real-world tasks, plus ablations over the feel-good weight, inverse temperature, and damping.
Key results
- In the synthetic linear bandit (d=20), MALATS attains the lowest cumulative regret (61.3 ± 26.6) among the TS variants, slightly below LMCTS (62.6 ± 9.5) and LinUCB (73.0 ± 13.8).
- In the logistic bandit, LinUCB (176.9 ± 41.9) and LinTS (179.9 ± 53.2) lead, with FGLMCTS (184.8 ± 38.0) close behind, while MALATS reaches 194.0 ± 76.9.
- On real-world neural bandits, LMCTS is competitive with or better than its feel-good variants on most datasets, and Neural-epsilon-Greedy or NeuralUCB attain the lowest regret on Mushroom and Adult.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add a feel-good bonus with λ=0.5 to MALA TS | MALA TS in linear Gaussian bandits · Linear-20d and Linear-40d | cumulative regret: 61.3 $\pm$ 26.6 -> 220.0 $\pm$ 159.9; 100.6 $\pm$ 10.0 -> 139.7 $\pm$ 16.1 | Hurt |
| Use a feel-good bonus λ=0.1 (ablation) | FG LMC TS · Linear-20d (β=10³) | cumulative regret: 62.6 $\pm$ 9.5 -> 50.8 $\pm$ 15.8 | Helped |
| Increase the feel-good bonus from λ=0.1 to λ=0.5 (ablation) | FG LMC TS · Linear-20d (β=10³) | cumulative regret: 50.8 $\pm$ 15.8 -> 235.8 $\pm$ 185.8 | Hurt |
| Set the smoothed feel-good bonus λ to 0.01 (ablation) | Smoothed FG MALA TS · Linear-20d (β=10³) | cumulative regret: 61.3 $\pm$ 26.6 -> 56.2 $\pm$ 22.8 | Helped |
| Increase feel-good bonus strength (ablation) | FG and smoothed FG samplers · Linear-20d (β=10³) | cumulative regret: λ=0.5: 235.8 $\pm$ 185.8; λ=1.0: 612.7 $\pm$ 340.4 | Hurt |
| Add preconditioning to HMC TS (ablation) | HMC TS · Linear bandit | cumulative regret: 240 $\pm$ 35.4 -> 90 $\pm$ 16.2 | Helped |
| Add preconditioning to LMC TS (ablation) | LMC TS · Linear-20d (β=10³) | cumulative regret: 62.6 $\pm$ 9.5 -> 134.4 $\pm$ 19.9 | Hurt |
| Use variance-reduced gradients (ablation) | LMC TS · Linear-40d (β=10³) | cumulative regret: 129.1 $\pm$ 16.1 -> 19236.8 $\pm$ 15560.8 | Hurt |
| Use underdamped rather than overdamped Langevin dynamics (ablation) | LMC TS · Linear contextual bandits | cumulative regret | Hurt |
| Add the feel-good bonus to neural LMC TS | LMC TS · Adult | cumulative regret: 2456.6 $\pm$ 36.5 -> 3505.0 $\pm$ 2257.5 | Hurt |
| Add the smoothed feel-good bonus to neural LMC TS | LMC TS · Magic Telescope | cumulative regret: 2220.0 $\pm$ 40.7 -> 2193.2 $\pm$ 34.0 | Helped |
| Add the smoothed feel-good bonus to neural LMC TS | LMC TS · Shuttle | cumulative regret: 210.2 $\pm$ 49.0 -> 1503.0 $\pm$ 2721.0 | Hurt |
Surprising findings
- Feel-good optimism tends to hurt in neural contextual bandits, where vanilla LMCTS remains more competitive.
- Underdamped Langevin samplers perform worse than overdamped ones, with the gap shrinking as damping increases.
Limitations
- Grid search for hyperparameters was modest and the study is not exhaustive.
- Sensitivity to learning-rate schedules and mini-batch noise makes results variable across seeds.
- Neural experiments use only LMC-based samplers because more sophisticated MCMC is too expensive.
Experimental setup
Datasets: Adult Shuttle MagicTelescope Mushroom Jester Covertype RestaurantRatings Financial MNIST_784 CIFAR-10 Wheel bandit synthetic linear bandit
Benchmarks: Adult Covertype Magic Telescope Mushroom Shuttle MNIST_784 linear bandit synthetic logistic bandit synthetic
Metrics: cumulative regret simple regret
Baselines: LinUCB LinTS epsilon-Greedy Neural-epsilon-Greedy NeuralUCB LMCTS
Builds on: Feel-Good Thompson Sampling Thompson Sampling Langevin Monte Carlo NeuralUCB LinUCB
Closest papers by meaning
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.94)
- Feel-Good Thompson Sampling for Contextual Dueling Bandits (ICML 2024 · similarity 0.93)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.92)
- Contextual Thompson Sampling via Generation of Missing Data (NeurIPS 2025 · similarity 0.90)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.90)
- $\mathtt{VITS}$ : Variational Inference Thompson Sampling for contextual 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.