Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
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 |
|---|---|---|---|
| Use CTS-Beta with a tighter regret analysis for independent bounded outcomes | CTS-Beta · Independent bounded outcomes | regret upper-bound factor before n log(T)/Δ: m -> \log^2(m) | Helped |
| Use a factorized Gaussian prior for sub-Gaussian outcomes | CTS-Gaussian · C-sub-Gaussian outcomes, diagonal C | regret upper-bound factor before n log(T)/Δ: m -> {{\log^2(m) }} | Helped |
| Clip sampled scores below at the empirical mean and above at the UCB | CTS-Gaussian · Arbitrary dependencies | regret upper-bound factor before n log(T)/Δ: {{\log^2(m) m}} -> m | Helped |
| Use CTS policies rather than CUCB and CUCB-KL | Shortest path on Chesapeake road network · Shortest path, independent and correlated outcomes | cumulative regret | Helped |
| Use Clip CTS-Gaussian rather than ESC-B when covariance parameter c is small | Matching on K_{4,4} · Gaussian outcomes, matching | cumulative regret | Helped |
| Use ESC-B rather than Clip CTS-Gaussian when covariance parameter c is large | Matching on K_{4,4} · Gaussian outcomes, matching | cumulative regret | Helped |
| Use a correlated Gaussian prior instead of an independent prior (ablation) | CTS-Gaussian · Matching problem with correlated outcomes | cumulative regret | Helped |
| Use a common prior instead of a correlated prior (ablation) | CTS-Gaussian · Worst-case separate action space with independent outcomes | cumulative regret | Hurt |
| Use CUCB rather than Clip CTS-Gaussian | Matching problem · Computation time per round | computation time: 0.50; 0.80; 1.75; 1.79; 3.30; 5.42 -> 0.39; 0.64; 1.23; 1.65; 2.45; 3.88 | Helped |
| Use Clip CTS-Gaussian rather than ESC-B | Matching problem · Computation time per round | computation time: 0.50; 0.80; 1.75; 1.79; 3.30; 5.42 -> 0.45; 1.93; 10.3; 75.6; 541; 4694 | Helped |
Closest papers by meaning
- Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · similarity 0.93)
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.92)
- The Choice of Noninformative Priors for Thompson Sampling in Multiparameter Bandit Models (AAAI 2024 · similarity 0.91)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.90)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.90)
- Combinatorial Stochastic-Greedy Bandit (AAAI 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.