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

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

Full description

Saved in:
Bibliographic Details
Main Authors: SARITAC, Omer, TEKIN, Cem
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2017
Subjects:
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
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.lkcsb_research-8604
record_format dspace
spelling sg-smu-ink.lkcsb_research-86042024-10-17T03:16:46Z Combinatorial multi-armed bandit problem with probabilistically triggered arms: A case with bounded regret SARITAC, Omer TEKIN, Cem 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. 2017-11-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/lkcsb_research/7605 info:doi/10.1109/GlobalSIP.2017.8308614 https://ink.library.smu.edu.sg/context/lkcsb_research/article/8604/viewcontent/CombinatorialMulti_ArmedBandit_2017_av.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection Lee Kong Chian School Of Business eng Institutional Knowledge at Singapore Management University Combinatorial multi-armed bandit probabilistically triggered arms bounded regret online learning Operations and Supply Chain Management
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Combinatorial multi-armed bandit
probabilistically triggered arms
bounded regret
online learning
Operations and Supply Chain Management
spellingShingle Combinatorial multi-armed bandit
probabilistically triggered arms
bounded regret
online learning
Operations and Supply Chain Management
SARITAC, Omer
TEKIN, Cem
Combinatorial multi-armed bandit problem with probabilistically triggered arms: A case with bounded regret
description 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.
format text
author SARITAC, Omer
TEKIN, Cem
author_facet SARITAC, Omer
TEKIN, Cem
author_sort SARITAC, Omer
title Combinatorial multi-armed bandit problem with probabilistically triggered arms: A case with bounded regret
title_short Combinatorial multi-armed bandit problem with probabilistically triggered arms: A case with bounded regret
title_full Combinatorial multi-armed bandit problem with probabilistically triggered arms: A case with bounded regret
title_fullStr Combinatorial multi-armed bandit problem with probabilistically triggered arms: A case with bounded regret
title_full_unstemmed Combinatorial multi-armed bandit problem with probabilistically triggered arms: A case with bounded regret
title_sort combinatorial multi-armed bandit problem with probabilistically triggered arms: a case with bounded regret
publisher Institutional Knowledge at Singapore Management University
publishDate 2017
url 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
_version_ 1814047922992447488