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 re...