Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Thompson Sampling with Less Exploration is Fast and Optimal
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce exploration: sample from posterior only with prob. 1/K, greedy on empirical mean otherwise (ε-TS) vs. full TS | Thompson Sampling · Table 2, Bernoulli K=10 and K=50, Gaussian K=10 and K=50 (running time) | average running time (s): 0.25 → 0.11 (K=10); 0.98 → 0.27 (K=50) | Helped |
| Replace ExpTS+ KL-inverse sampling with ε-TS posterior sampling at ε=1/K | ExpTS+ · Table 2, Bernoulli (running time) | average running time (s): 43 → 0.11 (K=10); 38 → 0.27 (K=50) | Helped |
| Reduced exploration (ε=1/K) in ε-TS | Gaussian rewards · Table 2, Gaussian K=10 (running time) | average running time (s): ε-TS 0.11 vs ExpTS+ 0.15 | No clear effect |
| Set ε=1/K in ε-TS | ε-TS · Figure 1 regret, K=10 and K=50 (Bernoulli, Gaussian, Poisson, Gamma) | cumulative regret | Helped |
| Set ε=1/K in ε-TS vs ExpTS+ (regret) | ε-TS · Figure 1, Bernoulli and Gamma (K=10); Gaussian and Gamma (K=50) | cumulative regret | No clear effect |
| Set ε=1/K in ε-TS vs ExpTS+ (regret, Poisson and Bernoulli K=50) | ε-TS · Figure 1, Gaussian and Poisson (K=10); Bernoulli and Poisson (K=50) | cumulative regret | Helped |
| Use ε=1/K sampling instead of full TS (ε=1) with posterior sampling | Thompson Sampling · Theory: worst-case regret bound for Gaussian, Bernoulli, Poisson, Gamma | worst-case regret bound order: O(√(KT log K)) with ε=1 (within √log K of minimax) vs. minimax optimal with ε=1/K | Helped |
Closest papers by meaning
- On the Suboptimality of Thompson Sampling in High Dimensions (NeurIPS 2021 · similarity 0.93)
- On Approximate Thompson Sampling with Langevin Algorithms (ICML 2020 · similarity 0.92)
- Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown (NeurIPS 2025 · similarity 0.92)
- Optimality of Thompson Sampling with Noninformative Priors for Pareto Bandits (ICML 2023 · similarity 0.92)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.92)
- Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · similarity 0.91)
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.