Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Contextual Thompson Sampling via Generation of Missing Data
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 generative Thompson sampling for contextual bandits: a sequence model offline-learned imputes missing future contexts and counterfactual outcomes, a policy is refit on the imputed complete task each decision, and the method is shown to be a generative TS with a regret bound depending only on the model's offline prediction loss.
Problem
Thompson sampling for contextual bandits with neural models is hard because posterior inference over latent parameters is difficult; the paper seeks a principled uncertainty quantification approach for meta-contextual bandits that leverages generative models and arbitrary policy fitting procedures.
Approach
Treat uncertainty as missing (future and counterfactual) outcomes rather than latent parameters: at each decision time, impute the missing outcomes with an offline-trained autoregressive generative model, fit an oracle policy on the imputed complete dataset, and act with it. This is a generative formulation of Thompson sampling, and the regret bound depends on the model only through its offline pr
Key results
- TS-Gen outperforms Greedy, Epsilon-greedy, TS-Neural-Linear (same generative model), linear TS, and LinUCB in both synthetic and semi-synthetic settings, averaged over 500 bandit tasks.
- Regret bound: Delta <= sqrt(|A|/(2T) * H(pi*(X_1:T)|Z)) + sqrt(2(l(p_theta)-l(p*))), so the model affects the bound only through its offline prediction loss gap.
- Lower offline prediction loss of the sequence model corresponds to lower TS-Gen regret, as suggested by the theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TS-Gen instead of Greedy with the same generative model | Generative Thompson Sampling · Synthetic and semi-synthetic contextual bandits | cumulative regret | Helped |
| Use TS-Gen instead of epsilon-greedy with the same generative model | Generative Thompson Sampling · Synthetic and semi-synthetic contextual bandits | cumulative regret | Helped |
| Use TS-Gen instead of TS-Neural-Linear with the same generative model | Generative Thompson Sampling · Synthetic and semi-synthetic contextual bandits | cumulative regret | Helped |
| Use TS-Gen instead of standard linear TS or LinUCB | Generative Thompson Sampling · Synthetic and semi-synthetic contextual bandits | cumulative regret | Helped |
| Use autoregressive generation rather than alternative non-autoregressive sampling | Generative Thompson Sampling · Contextual bandit experiments | decision-making performance | Helped |
| Improve the offline prediction loss of the generative model | TS-Gen · Contextual bandit experiments | cumulative regret | Helped |
Surprising findings
- TS-Gen outperforms linear TS and LinUCB, which the authors attribute to pretraining and the use of prior task information Z.
Limitations
- Experiments cover only two settings, so they are a proof of concept.
- Complete task datasets are approximated from partial logs via bootstrap heuristics without theoretical guarantees.
- Generative sampling and per-decision policy refitting are computationally costly (4.2 s generation and 2.2 s policy fitting per decision on CPU in semi-synthetic runs).
Experimental setup
Datasets: MIcrosoft News Dataset synthetic Bayesian logistic regression bandit tasks
Benchmarks: synthetic Bayesian logistic regression bandit semi-synthetic news recommendation (Microsoft News Dataset)
Metrics: cumulative regret vs best-fitting policy per-period regret
Baselines: Greedy Epsilon-greedy TS-Neural-Linear Linear TS LinUCB
Builds on: Thompson sampling information-theoretic regret analysis Natarajan dimension
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.89)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.88)
- Feel-Good Thompson Sampling for Contextual Dueling Bandits (ICML 2024 · similarity 0.88)
- $\mathtt{VITS}$ : Variational Inference Thompson Sampling for contextual bandits (ICML 2024 · 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.