  Online influence maximization has attracted much attention as a way to
maximize influence spread through a social network while learning the values of
unknown network parameters. Most previous works focus on single-item diffusion.
In this paper, we introduce a new Online Competitive Influence Maximization
(OCIM) problem, where two competing items (e.g., products, news stories)
propagate in the same network and influence probabilities on edges are unknown.
We adopt a combinatorial multi-armed bandit (CMAB) framework for OCIM, but
unlike the non-competitive setting, the important monotonicity property
(influence spread increases when influence probabilities on edges increase) no
longer holds due to the competitive nature of propagation, which brings a
significant new challenge to the problem. We provide a nontrivial proof showing
that the Triggering Probability Modulated (TPM) condition for CMAB still holds
in OCIM, which is instrumental for our proposed algorithms OCIM-TS and OCIM-OFU
to achieve sublinear Bayesian and frequentist regret, respectively. We also
design an OCIM-ETC algorithm that requires less feedback and easier offline
computation, at the expense of a worse frequentist regret bound. Experimental
evaluations demonstrate the effectiveness of our algorithms.
