Research map / Bandits and online learning / Contextual bandits and Thompson sampling
$\mathtt{VITS}$ : Variational Inference 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 VITS, Thompson sampling for contextual bandits where the posterior is approximated by Gaussian variational inference via Wasserstein Riemannian gradient descent, with Hessian-based and Hessian-free variants, and proves a Õ(d^{3/2}√T) regret bound for linear bandits.
Problem
Thompson sampling in contextual bandits requires samples from intractable posteriors at each round; existing approximations (Laplace, MCMC/LMC, ensembles, mean-field VI) are either poor, expensive, or lack guarantees.
Approach
Approximate each TS posterior with a non-degenerate Gaussian variational family, updated by a few Riemannian (Wasserstein-2) gradient descent steps per round warm-started from the previous round, with a square-root covariance recursion that avoids Cholesky decompositions; Hessian-free and Taylor-approximated variants reduce cost further.
Key results
- For linear bandits, VITS-I has cumulative regret bound Õ(d^{3/2}√T) with probability 1-δ, matching LinTS order.
- In ill-conditioned linear bandits (ζ=0.1), LMC-TS underperforms VITS-II even with 50 Langevin steps, while VITS-II performs similarly to LinTS.
- On MovieLens with logistic rewards, VITS slightly outperforms LMC-TS while being computationally cheaper.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use VITS-II instead of LMC-TS with 10 Langevin steps | Linear bandit · Linear bandit, ζ=1 | cumulative regret | Helped |
| Use VITS-II instead of LMC-TS with 10 or 50 Langevin steps | Linear bandit · Linear bandit, ζ=0.1 | cumulative regret | Helped |
| Use VITS-II instead of LinTS | Linear bandit · Linear bandit, ζ=0.1 and ζ=1 | cumulative regret | No clear effect |
| Use VITS-II instead of LMC-TS or LinTS | Quadratic bandit · Quadratic bandit, ζ=0.1 and ζ=1 | cumulative regret | Helped |
| Use VITS-II instead of LMC-TS (ablation) | VITS-II · Quadratic bandit, ζ=0.1 and ζ=1 | cumulative regret | Helped |
| Use the Hessian-free VITS-IIHF variant instead of VITS-II (ablation) | VITS-II · Linear bandit, ζ=0.1 and ζ=1 | cumulative regret | Hurt |
| Use the Hessian-free VITS-IIHF variant instead of VITS-II (ablation) | VITS-II · Quadratic bandit, ζ=0.1 and ζ=1 | cumulative regret | Hurt |
| Use VITS-II or VITS-IIHF instead of LinTS | MovieLens · MovieLens | cumulative regret | Helped |
| Use VITS-II instead of LMC-TS | MovieLens · MovieLens | cumulative regret | Helped |
| Use VITS-IIHF instead of VITS-II (ablation) | VITS-II · MovieLens | cumulative regret | No clear effect |
Surprising findings
- VTS (mean-field mixture VI) showed linear, notably high cumulative regret in the ill-conditioned setting and was excluded from the figures.
- VITS-I experimentally performed identically to VITS-II, so it was omitted from experiments.
Limitations
- Regret bound only proven for linear bandits, while the method targets nonlinear tasks.
- Hessian-free variant has no regret bound in the comparison table and relies on Monte Carlo approximation that can be unstable for large eta.
- Experiments are on synthetic settings and a single MovieLens setup with small sizes (d=20, 50 arms; 100 movies).
Experimental setup
Datasets: MovieLens
Benchmarks: MovieLens
Metrics: cumulative regret
Baselines: LinTS LMC-TS VTS Laplace approximation TS LinUCB Feel-Good TS
Builds on: Thompson sampling Linear Thompson sampling Langevin Monte Carlo TS Variational Thompson sampling
Closest papers by meaning
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.90)
- Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.89)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.88)
- Online Posterior Sampling with a Diffusion Prior (NeurIPS 2024 · similarity 0.88)
- Thompson Sampling for Multi-Objective Linear Contextual Bandit (NeurIPS 2025 · similarity 0.88)
- Contextual Thompson Sampling via Generation of Missing Data (NeurIPS 2025 · similarity 0.88)
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.