# Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 31 Aug 2022.

## Builds on (most cited first, 15 of 15)

- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Tight Lower Bounds for Combinatorial Multi-Armed Bandits](https://mlsanity.com/paper/2002.05392/) (2020)
- [Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem](https://mlsanity.com/paper/1905.03125/) (2019)
- [Statistically Efficient, Polynomial Time Algorithms for Combinatorial Semi Bandits](https://mlsanity.com/paper/2002.07258/) (2020)
- [Minimax Regret for Cascading Bandits](https://mlsanity.com/paper/2203.12577/) (2022)
- [Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online Learning](https://mlsanity.com/paper/2106.05065/) (2021)
- [Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/1410.0949/) (2014)

## Built on by (most cited first, 15 of 15)

- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation](https://mlsanity.com/paper/2508.07675/) (2025)
- [Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits](https://mlsanity.com/paper/2408.11202/) (2024)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users](https://mlsanity.com/paper/2402.16312/) (2024)
- [Offline Learning for Combinatorial Multi-armed Bandits](https://mlsanity.com/paper/2501.19300/) (2025)
- [Online Corrupted User Detection and Regret Minimization](https://mlsanity.com/paper/2310.04768/) (2023)
- [Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2402.15171/) (2024)
- [Hybrid Combinatorial Multi-armed Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2512.21925/) (2025)
- [A Unified Online-Offline Framework for Co-Branding Campaign Recommendations](https://mlsanity.com/paper/2505.22254/) (2025)
- [LLM Cache Bandit Revisited: Addressing Query Heterogeneity for Cost-Effective LLM Inference](https://mlsanity.com/paper/2509.15515/) (2025)
- [Online Influence Maximization: Concept and Algorithm](https://mlsanity.com/paper/2312.00099/) (2023)
- [Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.06247/) (2025)
- [Online Learning to Rank under Corruption: A Robust Cascading Bandits Approach](https://mlsanity.com/paper/2511.03074/) (2025)

## Abstract (arXiv)

In this paper, we study the combinatorial semi-bandits (CMAB) and focus on reducing the dependency of the batch-size K in the regret bound, where K is the total number of arms that can be pulled or triggered in each round. First, for the setting of CMAB with probabilistically triggered arms (CMAB-T), we discover a novel (directional) triggering probability and variance modulated (TPVM) condition that can replace the previously-used smoothness condition for various applications, such as cascading bandits, online network exploration and online influence maximization. Under this new condition, we propose a BCUCB-T algorithm with variance-aware confidence intervals and conduct regret analysis which reduces the O(K) factor to O(log K) or O(log2 K) in the regret bound, significantly improving the regret bounds for the above applications. Second, for the setting of non-triggering CMAB with independent arms, we propose a SESCB algorithm which leverages on the non-triggering version of the TPVM condition and completely removes the dependency on K in the leading regret. As a valuable by-product, the regret analysis used in this paper can improve several existing results by a factor of O(log K). Finally, experimental evaluations show our superior performance compared with benchmark algorithms in different applications.