# Contextual Combinatorial Bandits with Probabilistically Triggered Arms

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 38 references that are in the map.
- First posted on arXiv 30 Mar 2023.

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

- [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)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Cascading Bandits for Large-Scale Recommendation Problems](https://mlsanity.com/paper/1603.05359/) (2016)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Combinatorial Cascading Bandits](https://mlsanity.com/paper/1507.04208/) (2015)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem](https://mlsanity.com/paper/1905.03125/) (2019)
- [A General Framework for Estimating Graphlet Statistics via Random Walk](https://mlsanity.com/paper/1603.07504/) (2016)
- [Minimax Regret for Cascading Bandits](https://mlsanity.com/paper/2203.12577/) (2022)
- [Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions](https://mlsanity.com/paper/2101.07957/) (2021)
- [Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online Learning](https://mlsanity.com/paper/2106.05065/) (2021)
- [Online Competitive Influence Maximization](https://mlsanity.com/paper/2006.13411/) (2020)

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

- [Cost-Effective Online Multi-LLM Selection with Versatile Reward Models](https://mlsanity.com/paper/2405.16587/) (2024)
- [Nearly Minimax Optimal Regret for Multinomial Logistic Bandit](https://mlsanity.com/paper/2405.09831/) (2024)
- [Semantic Caching for Low-Cost LLM Serving: From Offline Learning to Online Adaptation](https://mlsanity.com/paper/2508.07675/) (2025)
- [Online Clustering of Bandits with Misspecified User Models](https://mlsanity.com/paper/2310.02717/) (2023)
- [Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond](https://mlsanity.com/paper/2406.01386/) (2024)
- [Adversarial Attacks on Online Learning to Rank with Click Feedback](https://mlsanity.com/paper/2305.17071/) (2023)
- [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)
- [AxiomVision: Accuracy-Guaranteed Adaptive Visual Model Selection for Perspective-Aware Video Analytics](https://mlsanity.com/paper/2407.20124/) (2024)
- [Online Corrupted User Detection and Regret Minimization](https://mlsanity.com/paper/2310.04768/) (2023)
- [Combinatorial Logistic Bandits](https://mlsanity.com/paper/2410.17075/) (2024)
- [Hybrid Combinatorial Multi-armed Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2512.21925/) (2025)
- [Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation](https://mlsanity.com/paper/2607.13686/) (2026)
- [Online Influence Maximization: Concept and Algorithm](https://mlsanity.com/paper/2312.00099/) (2023)
- [Bandits with Anytime Knapsacks](https://mlsanity.com/paper/2501.18560/) (2025)
- [On the Sublinear Regret of Continuous K-Max Bandits](https://mlsanity.com/paper/2502.13467/) (2025)
- [Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.06247/) (2025)
- [Diversified Multinomial Logit Contextual Bandits](https://mlsanity.com/paper/2607.11684/) (2026)

## Abstract (arXiv)

We study contextual combinatorial bandits with probabilistically triggered arms (C2MAB-T) under a variety of smoothness conditions that capture a wide range of applications, such as contextual cascading bandits and contextual influence maximization bandits. Under the triggering probability modulated (TPM) condition, we devise the C2-UCB-T algorithm and propose a novel analysis that achieves an tildeO(d√KT) regret bound, removing a potentially exponentially large factor O(1/pmin), where d is the dimension of contexts, pmin is the minimum positive probability that any arm can be triggered, and batch-size K is the maximum number of arms that can be triggered per round. Under the variance modulated (VM) or triggering probability and variance modulated (TPVM) conditions, we propose a new variance-adaptive algorithm VAC2-UCB and derive a regret bound tildeO(d√T), which is independent of the batch-size K. As a valuable by-product, our analysis technique and variance-adaptive algorithm can be applied to the CMAB-T and C2MAB setting, improving existing results there as well. We also include experiments that demonstrate the improved performance of our algorithms compared with benchmark algorithms on synthetic and real-world datasets.