Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
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 BG-CTS, a boosted-variance Gaussian Thompson Sampling for linear combinatorial semi-bandits with polynomial finite-time regret, and shows a mismatched-sampling paradox where a Gaussian-likelihood TS beats a Bernoulli-matched Beta TS exponentially.
Problem
Thompson Sampling for linear combinatorial semi-bandits with subgaussian rewards has known regret bounds that scale exponentially with the action size m in finite time, making TS look worse than UCB-type methods in the moderate-horizon, large-m regime.
Approach
Use a Gaussian posterior with an improper uniform prior and a time-varying variance boost g(t) ~ (1+lambda) (log-scale), so that the Thompson samples explore enough to yield polynomial finite-time regret; this mismatched Gaussian likelihood can beat the correctly specified Beta/Bernoulli TS exponentially.
Key results
- BG-CTS achieves regret upper bound of form O(sigma^2 d ln m ln T / Delta_min + sigma^2 d^2 m ln m ln ln T / Delta_min + P(...)) with P polynomial in m, d, 1/Delta_min, Delta_max, sigma.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add a time-varying exploration boost to Gaussian CTS (BG-CTS) | G-CTS on linear combinatorial semi-bandits · Two-action Bernoulli example | regret | Helped |
| use Gaussian likelihood and an improper uniform prior instead of the natural Bernoulli likelihood and Beta prior | Thompson Sampling on Bernoulli combinatorial bandits · Two disjoint actions of size m=d/2 | regret | Helped |
| use Beta-based Thompson sampling rather than BG-CTS | Thompson Sampling · Two-action Bernoulli example, m=50 | regret | Hurt |
| increase decision size m | Beta-based Thompson sampling · Two-action Bernoulli example, m in {5,25,45,65} | final regret | Hurt |
| increase decision size m | BG-CTS and ESCB · Two-action Bernoulli example, m in {5,25,45,65} | final regret | No clear effect |
| use Jeffreys prior rather than the uniform prior | Beta-CTS · Two-action Bernoulli example | exploration | Helped |
Surprising findings
- Mismatched TS (Gaussian likelihood with improper uniform prior) can perform exponentially better than correctly specified Beta-Bernoulli TS, the mismatched sampling paradox.
- Using Jeffreys prior for Beta-CTS does not fix the exponential regret.
Limitations
- Polynomial degrees in the bound are very large (e.g., 30 in m, 20 in 1/Delta_min), so the bound is loose.
- Analysis restricted to linear combinatorial semi-bandits with subgaussian rewards and the stated two-action experiment.
- Experiments limited to a single two-action Bernoulli instance.
Experimental setup
Benchmarks: two-action Bernoulli combinatorial bandit (m=d/2)
Metrics: cumulative regret final regret vs m
Baselines: Beta-CTS (uniform prior) Beta-CTS (Jeffreys prior) ESCB G-CTS
Builds on: Thompson Sampling CUCB ESCB Wang and Chen 2018 combinatorial TS analysis
Closest papers by meaning
- On the Suboptimality of Thompson Sampling in High Dimensions (NeurIPS 2021 · similarity 0.94)
- Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits (NeurIPS 2020 · similarity 0.93)
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.90)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.90)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.89)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.89)
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.