Analysis of Thompson Sampling for Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms

Abstract

We analyze the regret of combinatorial Thompson sampling (CTS) for the combinatorial multi-armed bandit with probabilistically triggered arms under the semi-bandit feedback setting. We assume that the learner has access to an exact optimization oracle but does not know the expected base arm outcomes beforehand. When the expected reward function is Lipschitz continuous in the expected base arm outcomes, we derive $O({\sum }_{i=1}^m\log T/(p_i{\Delta }_i))$ regret bound for CTS, where $m$ denotes the number of base arms, $p_i$ denotes the minimum non-zero triggering probability of base arm $i$ and ${\Delta }_i$ denotes the minimum suboptimality gap of base arm $i$. We also compare CTS with combinatorial upper confidence bound (CUCB) via numerical experiments on a cascading bandit problem.

arXiv commentTo appear in the Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS) 2019

References in corpus (8)

• Analysis of Thompson Sampling for the multi-armed bandit problem
• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Cascading Bandits: Learning to Rank in the Cascade Model
• Matroid Bandits: Fast Combinatorial Optimization with Learning
• Efficient Learning in Large-Scale Combinatorial Semi-Bandits
• Thompson Sampling for Combinatorial Semi-Bandits
• Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications

Cited by in corpus (1)

• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments