2018/11/29 by Mridul Agarwal, Agarwal, Mridul, Vaneet Aggarwal +5 · 1 citation
Computer Science · Mathematics · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.AI #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1811.11925
38 pages, 4 figures, 32nd International Conference on Algorithmic Learning Theory
arxiv created 2021/10/11 · arxiv updated 2021/10/12
Many real-world problems like Social Influence Maximization face the dilemma of choosing the best K out of N options at a given time instant. This setup can be modeled as a combinatorial bandit which chooses K out of N arms at each time, with an aim to achieve an efficient trade-off between exploration and exploitation. This is the first work for combinatorial bandits where the feedback received can be a non-linear function of the chosen K arms. The direct use of multi-armed bandit requires choosing among N-choose-K options making the state space large. In this paper, we present a novel algorithm which is computationally efficient and the storage is linear in N. The proposed algorithm is a divide-and-conquer based strategy, that we call CMAB-SM. Further, the proposed algorithm achieves a regret bound of O(K(1)/(2)N(1)/(3)T(2)/(3)) for a time horizon T, which is sub-linear in all parameters T, N, and K. %When applied to the problem of Social Influence Maximization, the performance of the proposed algorithm surpasses the UCB algorithm and some more sophisticated domain-specific methods.