# Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications

arXiv: https://arxiv.org/abs/1703.01610 · HTML: https://mlsanity.com/paper/1703.01610/

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2017.

## Built on by (most cited first, 30 of 45)

- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalization](https://mlsanity.com/paper/2110.14622/) (2021)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits](https://mlsanity.com/paper/2305.12402/) (2023)
- [Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation](https://mlsanity.com/paper/2508.07675/) (2025)
- [Combinatorial Multi-armed Bandits for Resource Allocation](https://mlsanity.com/paper/2105.04373/) (2021)
- [Minimax Regret for Cascading Bandits](https://mlsanity.com/paper/2203.12577/) (2022)
- [The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle](https://mlsanity.com/paper/2111.04295/) (2021)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online Learning](https://mlsanity.com/paper/2106.05065/) (2021)
- [When Combinatorial Thompson Sampling meets Approximation Regret](https://mlsanity.com/paper/2302.11182/) (2023)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference](https://mlsanity.com/paper/2503.07555/) (2025)
- [Combinatorial Blocking Bandits with Stochastic Delays](https://mlsanity.com/paper/2105.10625/) (2021)
- [Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback](https://mlsanity.com/paper/2305.16074/) (2023)
- [Combinatorial Logistic Bandits](https://mlsanity.com/paper/2410.17075/) (2024)
- [Recurrent Submodular Welfare and Matroid Blocking Bandits](https://mlsanity.com/paper/2102.00321/) (2021)
- [Effective Dimension in Bandit Problems under Censorship](https://mlsanity.com/paper/2302.06916/) (2023)
- [Online Influence Maximization under Decreasing Cascade Model](https://mlsanity.com/paper/2305.15428/) (2023)
- [Adversarial Attacks on Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2310.05308/) (2023)
- [Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Making](https://mlsanity.com/paper/2510.21788/) (2025)
- [Hybrid Combinatorial Multi-armed Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2512.21925/) (2025)
- [Online Learning of Independent Cascade Models with Node-level Feedback](https://mlsanity.com/paper/2109.02519/) (2021)
- [Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback](https://mlsanity.com/paper/2109.06077/) (2021)
- [Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization](https://mlsanity.com/paper/2206.14846/) (2022)
- [Targeted Advertising on Social Networks Using Online Variational Tensor Regression](https://mlsanity.com/paper/2208.10627/) (2022)
- [Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewards](https://mlsanity.com/paper/2307.14138/) (2023)
- [Learning to Schedule in Non-Stationary Wireless Networks With Unknown Statistics](https://mlsanity.com/paper/2308.02734/) (2023)

## Abstract (arXiv)

We study combinatorial multi-armed bandit with probabilistically triggered arms (CMAB-T) and semi-bandit feedback. We resolve a serious issue in the prior CMAB-T studies where the regret bounds contain a possibly exponentially large factor of 1/p^*, where p^* is the minimum positive probability that an arm is triggered by any action. We address this issue by introducing a triggering probability modulated (TPM) bounded smoothness condition into the general CMAB-T framework, and show that many applications such as influence maximization bandit and combinatorial cascading bandit satisfy this TPM condition. As a result, we completely remove the factor of 1/p^* from the regret bounds, achieving significantly better regret bounds for influence maximization and cascading bandits than before. Finally, we provide lower bound results showing that the factor 1/p^* is unavoidable for general CMAB-T problems, suggesting that the TPM condition is crucial in removing this factor.