mlsanityData to 14 Oct 2026

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

arXiv 1703.01610 ↗First posted 5 Mar 2017cs.LG stat.MLcited by 45

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 4; 2023: 11; 2024: 5; 2025: 12; 2026: 3.

45 papers.

Sort:

By area:

  1. 2024Cost-Effective Online Multi-LLM Selection with Versatile Reward Modelscited by 39
  2. 2021Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalizationcited by 18
  3. 2023Contextual Combinatorial Bandits with Probabilistically Triggered Armscited by 18
  4. 2022Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Armscited by 15
  5. 2023Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Banditscited by 13
  6. 2025Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptationcited by 13
  7. 2021Combinatorial Multi-armed Bandits for Resource Allocationcited by 10
  8. 2022Minimax Regret for Cascading Banditscited by 10
  9. 2021The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oraclecited by 7
  10. 2024Query-Efficient Correlation Clustering with Noisy Oraclecited by 7
  11. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  12. 2021Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online Learningcited by 6
33 more
  1. 2023When Combinatorial Thompson Sampling meets Approximation Regretcited by 6
  2. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  3. 2025Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interferencecited by 5
  4. 2021Combinatorial Blocking Bandits with Stochastic Delayscited by 3
  5. 2023Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedbackcited by 3
  6. 2024Combinatorial Logistic Banditscited by 3
  7. 2021Recurrent Submodular Welfare and Matroid Blocking Banditscited by 2
  8. 2023Effective Dimension in Bandit Problems under Censorshipcited by 2
  9. 2023Online Influence Maximization under Decreasing Cascade Modelcited by 2
  10. 2023Adversarial Attacks on Combinatorial Multi-Armed Banditscited by 2
  11. 2025Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Makingcited by 2
  12. 2025Hybrid Combinatorial Multi-armed Bandits with Probabilistically Triggered Armscited by 2
  13. 2021Online Learning of Independent Cascade Models with Node-level Feedbackcited by 1
  14. 2021Online Influence Maximization under the Independent Cascade Model with Node-Level Feedbackcited by 1
  15. 2022Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximizationcited by 1
  16. 2022Targeted Advertising on Social Networks Using Online Variational Tensor Regressioncited by 1
  17. 2023Piecewise-Stationary Combinatorial Semi-Bandit with Causally Related Rewardscited by 1
  18. 2023Learning to Schedule in Non-Stationary Wireless Networks With Unknown Statisticscited by 1
  19. 2024Merit-based Fair Combinatorial Semi-Bandit with Unrestricted Feedback Delayscited by 1
  20. 2025A Unified Online-Offline Framework for Co-Branding Campaign Recommendationscited by 1
  21. 2025LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inferencecited by 1
  22. 2026Covariance-adapting algorithm for semi-bandits with application to sparse rewardscited by 1
  23. 2021On Learning to Rank Long Sequences with Contextual Banditscited by 0
  24. 2021Learning to maximize global influence from local observationscited by 0
  25. 2023Constant or logarithmic regret in asynchronous multiplayer banditscited by 0
  26. 2023Online Influence Maximization: Concept and Algorithmcited by 0
  27. 2025Bandits with Anytime Knapsackscited by 0
  28. 2025On the Sublinear Regret of Continuous K-Max Banditscited by 0
  29. 2025Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Banditscited by 0
  30. 2025Multi-Play Combinatorial Semi-Bandit Problemcited by 0
  31. 2025Online Learning to Rank under Corruption: A Robust Cascading Bandits Approachcited by 0
  32. 2026Budgeted Online Influence Maximizationcited by 0
  33. 2026Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Banditscited by 0