Research map / Bandits and online learning / Contextual bandits and Thompson sampling
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 Thompson sampling (CTS) instead of UCB-style CUCB for combinatorial bandits | General CMAB and matroid bandit · Max spanning tree and shortest path simulations | regret | Helped |
| Use Thompson sampling instead of C-KL-UCB | Matroid bandit and general CMAB · Max spanning tree and shortest path simulations | regret | Helped |
| Use an approximation oracle inside TS (CTS) | Original MAB instance with approximation oracle · Constructed 3-arm MAB instance (Theorem 2) | approximate regret | Hurt |
| Remove independence across arms assumption, using matroid structure | Matroid bandit CTS · Theoretical analysis | regret bound | No clear effect |
| Use CUCB with tuned confidence radius (CUCB-m) versus theoretical radius (ablation) | CUCB · Matroid bandit and shortest path simulations | regret | Mixed |
| Pull each base arm about O(1/eps^2) times before running CTS | General CMAB CTS · Theoretical analysis | constant regret term | Helped |
Closest papers by meaning
- Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits (NeurIPS 2020 · similarity 0.94)
- When Combinatorial Thompson Sampling meets Approximation Regret (NeurIPS 2022 · similarity 0.93)
- Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · similarity 0.91)
- Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit (AAAI 2024 · similarity 0.89)
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.89)
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · 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.