2023/03/30 by Liu, Xutong, Zuo, Jinhang, Wang, Siwei +4 · 3 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · doi:10.48550/arxiv.2303.17110
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 O(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 O(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.