Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Probably Anytime-Safe Stochastic 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 PASCombUCB with anytime variance-safety checks | Combinatorial semi-bandits with variance constraints · PASSCSB problem-dependent | expected cumulative regret: O(∑i∈E\S⋆ K ln T/Δi,S∩B,min + ∑i∈E ci K ln T/Δi,Sc∩B,min + 2μ⋆H(Δ(Λ)) + 2μ⋆(L+1)) | Helped |
| Use PASCombUCB with anytime variance-safety checks | Combinatorial semi-bandits with variance constraints and T>L · PASSCSB problem-independent | expected cumulative regret: O(√(KLT ln T) + LK²/(Δv)² ln(1/δT)) | Helped |
| Require safety probability to approach one exponentially quickly in T | Any PASSCSB algorithm · PASSCSB with ln(1/δT)=Ω(T^b) | expected cumulative regret: Ω(T^b) | Hurt |
| Use PASCombUCB with a variance threshold that makes all solutions safe | Set 1 · Experiment 1, unconstrained case | regret | No clear effect |
| Apply a restrictive variance threshold requiring safety checks | PASCombUCB on Set 1 · Experiment 1, σ̄²=0.6 | regret: T>4×10^5 | Mixed |
| Ignore the anytime safety constraint and use CombUCB1 | Combinatorial semi-bandits on Set 1 · Experiment 2, σ̄²=0.4 | safety violations: Ω(T) | Hurt |
| Use PASCombUCB to enforce anytime safety | Combinatorial semi-bandits on Set 1 · Experiment 2, σ̄²=0.4 | safety violations | Helped |
| Vary the variance threshold | PASCombUCB on Set 2 · Experiment 3, T=2×10^6 | additional regret versus 1/(ΔvS)²: barσ²=0.14×1.2^k for k=0,1,…,9 | Mixed |
Closest papers by meaning
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.90)
- Anytime optimal algorithms in stochastic multi-armed bandits (ICML 2016 · similarity 0.90)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.88)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.88)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.88)
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.88)
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.