Title: Combinatorial Multi-armed Bandit with Probabilistically Triggered Arms: A Case with Bounded Regret,
Abstract: 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
class of upper confidence bound (UCB) policies, named Combinatorial UCB with
exploration rate $\kappa$ (CUCB-$\kappa$), and Combinatorial Thompson Sampling
(CTS), which estimates the expected states of the arms via Thompson sampling,
achieve bounded regret. In addition, we prove that CUCB-$0$ and CTS incur
$O(\sqrt{T})$ gap-independent regret. These results improve the results in
previous works, which show $O(\log T)$ gap-dependent and $O(\sqrt{T\log T})$
gap-independent regrets, respectively, under no assumptions on the ATPs. Then,
we numerically evaluate the performance of CUCB-$\kappa$ and CTS in a
real-world movie recommendation problem, where the actions correspond to
recommending a set of movies, the arms correspond to the edges between the
movies and the users, and the goal is to maximize the total number of users
that are attracted by at least one movie. Our numerical results complement our
theoretical findings on bounded regret. Apart from this problem, our results
also directly apply to the online influence maximization (OIM) problem studied
in numerous prior works.