Research map / Bandits and online learning / Multi-armed bandits
Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
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 |
|---|---|---|---|
| Add 1-norm triggering-probability-modulated (TPM) bounded smoothness condition to CMAB-T | CUCB on CMAB-T · influence maximization and cascading bandits | regret bound dependence on 1/p* | Helped |
| Use 1-norm instead of infinity-norm bounded smoothness | influence maximization bandit · distribution-dependent and -independent regret bounds | dominant regret term factor | Helped |
| Remove probabilistic triggering (p*=1) and use the tighter analysis | linear bandit special case · distribution-dependent bound | leading constant: 624 -> 48 | Helped |
| Reverse amortization analysis versus Kveton et al. linear bandit analysis | linear bandit (CUCB) · distribution-dependent and -independent bounds | leading constants (534 and 47 in prior work vs 624/50 here with triggering) | Mixed |
| Apply the TPM-based analysis to cascading bandits (B=1) instead of prior 1/f* analysis | combinatorial cascading bandits · disjunctive cascading bandits | regret dependence on 1/f* | Helped |
| Lower bound: general CMAB-T without TPM condition (FTP(p) instance) | general CMAB-T · distribution-independent | regret lower bound | No clear effect |
Closest papers by meaning
- Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond (ICML 2024 · similarity 0.91)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.89)
- Offline Learning for Combinatorial Multi-armed Bandits (ICML 2025 · similarity 0.88)
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.88)
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.87)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · 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.