Combinatorial multi-armed bandit problem with probabilistically triggered arms: A case with bounded regret

• Main Authors: SARITAC, Omer, TEKIN, Cem
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: Combinatorial multi-armed bandit; probabilistically triggered arms; bounded regret; online learning; Operations and Supply Chain Management
• Online Access: https://ink.library.smu.edu.sg/lkcsb_research/7605; https://ink.library.smu.edu.sg/context/lkcsb_research/article/8604/viewcontent/CombinatorialMulti_ArmedBandit_2017_av.pdf
• Institution: Singapore Management University

In this paper, we study the combinatorial multi-armed bandit problem (CMAB) with probabilistically triggered arms (PTAs). Under the assumption that the arm triggering probabilities (ATPs) are positive for all arms, we prove that a simple greedy policy, named greedy CMAB (G-CMAB), achieves bounded regret. This improves the result in previous work, which shows that the regret is O (log T) under no such assumption on the ATPs. Then, we numerically show that G-CMAB achieves bounded regret in a real-world movie recommendation problem, where the action corresponds to recommending a set of movies, arms correspond to the edges between movies and users, and the goal is to maximize the total number of users that are attracted by at least one movie. In addition to this problem, our results directly apply to the online influence maximization (OIM) problem studied in numerous prior works.