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

Abstract

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^{\ast }$, where $p^{\ast }$ 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^{\ast }$ 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^{\ast }$ is unavoidable for general CMAB-T problems, suggesting that the TPM condition is crucial in removing this factor.

This is the full version of the paper accepted at NIPS'2017

Cited by in corpus (24)

• Thompson Sampling for Combinatorial Semi-Bandits
• Online Influence Maximization under Linear Threshold Model
• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• Contextual Blocking Bandits
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
• Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
• Online A-Optimal Design and Active Linear Regression
• Online Competitive Influence Maximization
• (Locally) Differentially Private Combinatorial Semi-Bandits
• Combinatorial Blocking Bandits with Stochastic Delays
• Thompson Sampling for a Fatigue-aware Online Recommendation System
• Bandit Learning with Delayed Impact of Actions
• Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online Learning
• A Unified Online-Offline Framework for Co-Branding Campaign Recommendations
• Stochastic Online Learning with Probabilistic Graph Feedback
• Recurrent Submodular Welfare and Matroid Blocking Bandits
• Thompson Sampling Algorithms for Cascading Bandits
• On the Equivalence Between High-Order Network-Influence Frameworks: General-Threshold, Hypergraph-Triggering, and Logic-Triggering Models
• Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
• Learning to maximize global influence from local observations
• Combinatorial Multi-armed Bandits for Resource Allocation