Research map / Bandits and online learning / Contextual bandits and Thompson sampling
The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle
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 with a greedy oracle on the constructed PMC instance | CTS · Constructed PMC instance | greedy regret: \Omega\bracket{\log T/\Delta^2} | Hurt |
| Use the greedy oracle with CTS rather than requiring an exact oracle | CTS for CMAB · CMAB with greedy oracle | greedy regret: lower bound: \Omega\bracket{\log T/\Delta^2}; upper bound: O\bracket{\sum_{s \neq s_{g,1} } \max_{k:s \notin S_{g,k}}\fr | Mixed |
Closest papers by meaning
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.91)
- Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox (NeurIPS 2024 · similarity 0.90)
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.88)
- Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit (AAAI 2024 · similarity 0.87)
- Feasible Action Search for Bandit Linear Programs via Thompson Sampling (ICML 2025 · similarity 0.87)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.87)
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.