Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
We study combinatorial multi-armed bandit with probabilistically triggered arms and semi-bandit feedback (CMAB-T). 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.
Overview: The paper studies combinatorial multi-armed bandit with probabilistically triggered arms and semi-bandit feedback (CMAB-T). The paper improves the existing regret bounds by introducing a new version of the bounded smoothness condition on the reward functions, called triggering probability modulated bounded smoothness condition. The intuition behind this is that hard-to-trigger arms do not contribute much to the expected regret. With this new condition, the authors are able to remove a potentially exponentially large factor in the existing regret bounds. The paper then shows that applications such as influence maximization bandit and combinatorial cascading bandit both satisfy this condition. Finally, the paper gives a lower bound and shows that for general CMAB-T problems, the exponential factor is unavoidable. 
Quality: The paper provides rigorous proofs for all its claims. 
Clarity: The paper is well-organized and clearly-written. Everything is well-defined and well-explained. The paper also has a nice flow to it. My only complaint is that a concluding section is missing. The authors may also want to proofread for typos and grammatical errors. 
Originality: The paper strengthens an existing condition and gives a tighter regret bound for CMAB-T problems. The paper also applies this new condition to influence maximization bandit and combinatorial cascading bandit. The authors introduce several new techniques in their proofs. 
Significance: The paper greatly improves the regret bound for CMAB-T problems with a new condition that has many applications.