{'fraction_non_alphanumeric': 0.050266205151729984, 'fraction_numerical': 0.014540500715904193, 'mean_word_length': 3.7984258271077906, 'pattern_counts': {'":': 1, '<': 7, '<?xml version=': 0, '>': 24, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 30, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Online Competitive Influence Maximization

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.


Introduction
Influence maximization, motivated by viral marketing applications, has been extensively studied since Kempe et al. (2003) formally defined it as a stochastic optimization problem: given a social network G and a budget k, how should a set of k seed nodes in G be chosen such that the expected number of final activated nodes under a given diffusion model is maximized? They proposed the well-known Independent Cascade (IC) and Linear Threshold (LT) diffusion models, and gave a greedy algorithm that outputs a (1 − 1/e − )-approximate solution for any > 0. However, they only considered a single item (e.g., product, idea) propagating in the network. In reality, different items could propagate concurrently in the same network, interfering with each other and leading to competition during propagation. Several competitive diffusion models (Carnes et al., 2007;Bharathi et al., 2007;Budak et al., 2011;He et al., 2012;Ivanov et al., 2017) have been proposed for this setting. We use a Competitive Independent Cascade (CIC) model (Chen et al., 2013), which extends the classical IC model to multi-item influence diffusion. We consider the competitive influence maximization problem between two items from the "follower's perspective": given the seed nodes of the competitor's item, the follower's item chooses a set of nodes so as to maximize the expected number of nodes activated by the follower's item, referred to as the influence spread of the item.
We refer to the above problem as "offline" competitive influence maximization, since the influence probabilities on edges, i.e., the probabilities of an item's propagation along edges, are known in advance. It can be solved by a greedy algorithm due to submodularity (Chen et al., 2013). However, in many real-world applications, the influence probabilities on edges are unknown. We study the competitive influence maximization in this setting, and call it the Online Competitive Influence Maximization (OCIM) problem. In OCIM, the influence probabilities on edges need to be learned through repeated influence maximization trials: in each round, given the seed nodes of the competitor, we (i) choose k seed nodes; (ii) observe the resulting diffusion that follows the CIC model to update our knowledge of the edge probabilities; and (iii) obtain a reward, which is the total number of nodes activated by our item. Our goal is to choose the seed nodes in each round based on previous observations so as to maximize the cumulative reward.
Most previous studies on the online non-competitive influence maximization problem use a combinatorial multi-armed bandit (CMAB) framework (Chen et al., 2016;Wen et al., 2017), an extension of the classical multi-armed bandit problem that captures the tradeoff between exploration and exploitation in sequential decision making. In CMAB, a player chooses a combinatorial action to play in each round, observes a set of arms triggered by this action and receives a reward. The player aims to maximize her cumulative reward over multiple rounds, navigating a tradeoff between exploring unknown actions/arms and exploiting the best known action. CMAB algorithms must also deal with an exponential number of possible combinatorial actions, which makes exploring all actions infeasible.
Our Contributions. To the best of our knowledge, we are the first to study the online competitive influence maximization problem. We introduce a general contextual combinatorial multi-armed bandit framework with probabilistically triggered arms (C 2 MAB-T) for OCIM. Within this framework, OCIM presents a new challenge: the key monotonicity property (influence spread increases when influence probabilities on edges increase) no longer holds due to the competitive nature of propagation, and thus upper confidence bound (UCB) based algorithms (Chen et al., 2016;Wen et al., 2017) cannot be directly applied to OCIM. Such non-monotonicity also complicates the analysis of the important Triggering Probability Modulated (TPM) condition for CMAB (Wang and Chen, 2017), and we provide a non-trivial new proof to show it still holds for OCIM. We are the first to identify the OCIM problem as a natural CMAB problem without monotonicity and tackle it from three directions, providing three solutions with different tradeoffs, as shown in Table 1: OCIM-TS uses standard offline oracles to achieve good Bayesian regret, but requires prior knowledge of edge probabilities; OCIM-OFU has a stronger frequentist regret bound without prior knowledge, but requires harder offline computation; and OCIM-ETC uses standard offline oracles and fewer observations, but leads to a worse frequentist regret bound. None is a perfect solution for OCIM, but we believe their tradeoffs shed light on the challenges involved in solving OCIM and even general CMAB problems without monotonicity. Our regret analysis of OCIM-TS delicately combines the key property of Thompson Sampling (TS) with the TPM condition to tackle nonmonotonicity and allows any benchmark (exact, approximate, or even heuristic) oracle; our analysis of OCIM-OFU and OCIM-ETC extends the analysis for CMAB to a new contextual setting (C 2 MAB-T) where the contexts are defined as the feasible sets of super arms and are not bonded with base arms. We also discuss the extension of our framework to settings with more complex competitor actions. Experiments on two real-world datasets demonstrate the effectiveness of our proposed algorithms. Due to the space constraint, we discuss important insights of our proofs and move the complete proofs as well as the results for the general C 2 MAB-T problem to the Appendix.
Related Work. Kempe et al. (2003) formally defined the influence maximization problem in their seminal work. Since then, the problem has been extensively studied (Li et al., 2018). Borgs et al. (2014) presented a breakthrough approximation algorithm that runs in near-linear time, which was improved by a series of algorithms (Tang et al., 2015;Nguyen et al., 2016;Tang et al., 2018). A number of studies (Carnes et al., 2007;Bharathi et al., 2007;Budak et al., 2011;He et al., 2012;Lin and Lui, 2015;Ivanov et al., 2017) addressed competitive influence maximization problems where multiple competing sources propagate in the same network. Carnes et al. (2007) proposed the distance-based and wave propagation models, and considered the influence maximization problem from the follower's perspective. Bharathi et al. (2007) considered the CIC model and gave an algorithm for computing the best response to an opponent's strategy.
When the influence probabilities of edges are un-known, the non-competitive online influence maximization problem has been extensively studied (Chen et al., 2016;Wang and Chen, 2017;Wen et al., 2017;Wu et al., 2019;Vaswani et al., 2017;Perrault et al., 2020). Chen et al. (2016) studied the problem under the IC model and proposed a general CMAB framework. We introduce a new contextual extension of CMAB, called C 2 MAB-T, different from the contextual CMAB studied by Chen et al. (2018) and Qin et al. (2014): they consider the context features of all base arms and assume the action space of super arms is a subset of all base arms, while we consider the feasible set of super arms as the context, which is more flexible than a subset of all base arms. Wang and Chen (2017) introduced a triggering probability modulated (TPM) bounded smoothness condition to remove an undesired factor in the regret bound of Chen et al. (2016). Perrault et al. (2020) introduced a budgeted online influence maximization framework, where marketers optimize their seed sets under a budget rather than a cardinality constraint. Our OCIM-TS algorithm is similar to the Combinatorial Thompson Sampling (CTS) algorithm of Wang and Chen (2018). However, CTS requires an exact oracle and has frequentist regret bound, while OCIM-TS allows any benchmark oracle and has Bayesian regret bound. Hüyük and Tekin (2020) studied the Bayesian regret of CTS for CMAB, but they also require an exact oracle and a monotonicity assumption that does not hold for OCIM. Our Bayesian regret analysis is also different from that of Russo and Van Roy (2016): they only study a simple special CMAB problem, while we provide the regret bound for general C 2 MAB-T instances, including the OCIM problem.

OCIM Formulation
In this section we present the formulation of OCIM. We first introduce the traditional competitive influence maximization problem, and then discuss its online extension where edge probabilities are unknown.

Competitive Independent Cascade Model
We consider a Competitive Independent Cascade (CIC) model, which is an extension of the classical IC model to multi-item influence diffusion. A network is modeled as a directed graph G = (V, E) with n = |V | nodes and m = |E| edges. Every edge (u, v) ∈ E is associated with a probability p(u, v). There are two items, A and B, trying to propagate in G from their own seed sets S A and S B . The influence propagation runs as follows: nodes in S A (resp. S B ) are activated by A (resp. B) at step 0; at each step s ≥ 1, a node u activated by A (resp. B) in step s − 1 tries to acti-vate each of its inactive out-neighbors v to be A (resp. B) with an independent probability p(u, v) that is the same for A and B (i.e., we consider a homogeneous CIC model). The homogeneity assumption is reasonable since typically A and B are two items of the same category (thus competing), so they are likely to have similar propagation characteristics.
If two in-neighbors of v activated by A and B respectively both successfully activate v at step s, then a tie-breaking rule is applied at v to determine the final adoption. In this paper, we consider two types of tie-breaking rules: dominance (Budak et al., 2011) andproportional (Chen et al., 2011) tie-breaking rules. Dominance tie-breaking with A > B (resp. B > A) means v will always adopt A (resp. B) in a competition. Proportional tie-breaking means that if there are n A in-neighbors activated by A and n B in-neighbors activated by B trying to activate v at the same step, the probability that v adopts A (resp. B) is n A n A +n B (resp. n B n A +n B ). The same tie-breaking rule also applies to the case when a node u is selected both as an A-seed and a B-seed. The process stops when no nodes activated at a step s have inactive out-neighbors.
We consider the follower's perspective in the optimization task: let A be the follower and B be the competitor. Then given S B , our goal is to choose at most k seed nodes in G as S A to maximize the influence spread of A, denoted as σ A (S A , S B ), which is the expected number of nodes activated by A after the propagation ends. According to Budak et al. (2011)'s result, the above optimization task under the homogeneous CIC model with the dominance tie-breaking rule has the monotone and submodular properties, and thus can be approximately solved by a greedy algorithm.

OCIM Model
In the online competitive influence maximization (OCIM) problem, the edge probabilities p(u, v)'s are unknown and need to be learned: in each round t, given S (t) B , we can choose up to k seed nodes as S

(t)
A , observe the whole propagation of A and B that follows the CIC model, and obtain the reward, which is the number of nodes finally activated by A in this round. The propagation feedback observed is then used to update the estimates on edge probabilities p(u, v)'s, so that we can achieve better influence maximization results in subsequent rounds. Our goal is to accumulate as much reward as possible through this repeated process over multiple rounds.
We introduce a new contextual combinatorial multiarmed bandit framework with probabilistically triggered arms (C 2 MAB-T) for the OCIM problem, which is a contextual extension of CMAB-T from Wang and Chen (2017). In OCIM, the set of edges E is the set of (base) arms [m] = {1, ..., m}, and their outcomes follow m independent Bernoulli distributions with expectation µ e = p(u, v) for all e = (u, v) ∈ E. We denote the independent samples of arms in round t as = 1 means the i-th edge is on (or live) and X (t) i = 0 means the i-th edge is off (or blocked) in round t, and thus X (t) corresponds to the live-edge graph (Kempe et al., 2003) in round t. We consider the seed set of the competitor, S (t) B , as the context in round t since it is determined by the competitor and can affect our choice of S A | ≤ k as the action space in round t and S (t) ∈ S (t) as the real action. We define the triggered arm set τ t as the set of edges reached by the propagation from either S for all i ∈ τ t are observed as the feedback. We denote the obtained reward in round t as R(S (t) , X (t) ), which is the number of nodes finally activated by A. The expected reward ] is a function of the action S (t) and the vector µ = (µ 1 , . . . , µ m ). Note that our framework can also handle dynamic tie-breaking rules over different rounds, by treating the tie-breaking rule as a part of the context. For ease of explanation, we assume a fixed tie-breaking rule in this paper.
The performance of a learning algorithm A is measured by its expected regret, which is the difference in expected cumulative reward between always playing the best action and playing actions selected by algorithm A. Let opt (t) (µ) = sup S (t) A r S (t) (µ) denote the expected reward of the optimal action in round t. Since the offline influence maximization under the CIC model is NP-hard (Budak et al., 2011), we assume that there exists an offline (α, β)-approximation oracle O, which takes S (t) B and µ as inputs and outputs an action where α is the approximation ratio and β is the success probability. Instead of comparing with the exact optimal reward, we use the following (α, β)-approximation frequentist regret for T rounds: Another way to measure the performance of the algorithm A is using Bayesian regret (Russo and Van Roy, 2014). Denote the prior distribution of µ as Q (we will discuss how to derive Q for OCIM in Section 4). When the prior Q is given, the corresponding Bayesian regret is defined as: We will design algorithms to solve the OCIM problem and bound their achieved Bayesian and frequentist regrets in Section 4 and Section 5, respectively. We also discuss the general C 2 MAB-T problem and its solutions in the Appendix.

Properties of OCIM
In this section, we first show that the key monotonicity property for CMAB does not hold in OCIM. We then prove that the important Triggering Probability Modulated (TPM) condition still holds, which is essential for the analysis of all proposed algorithms.

Non-monotonicity
The monotonicity condition given by Wang and Chen (2017) could be stated as follows in the context of OCIM: for any action S = (S A , S B ), for any two expectation vectors µ = (µ 1 , . . . , µ m ) and µ = (µ 1 , . . . , µ m ), we have Figure 1 shows a simple example of OCIM that does not satisfy the monotonicity condition. The left and right nodes are the seed nodes of A and B; the numbers below edges are influence probabilities. It is easy to calculate that r S (µ) = µ 1 (1 − µ 2 ) + 2, for both dominance and proportional tie-breaking rules. Thus, if we increase µ 2 , r S (µ) will decrease, which is contrary to monotonicity. In general, for every edge (u, v), depending on the positions of the A-and B-seeds, increasing the influence probability of (u, v) may benefit the propagation of A or may benefit the propagation of B and thus impair the propagation of A. Thus, the influence spread of A has intricate connections with the influence probabilities on the edges. The lack of monotonicity poses a significant challenge to the OCIM problem. We cannot directly use UCBtype algorithms (Chen et al., 2016), as they will not provide optimistic solutions to bound the regret.

Triggering Probability Modulated (TPM) Bounded Smoothness
The lack of monotonicity further complicates the analysis of the Triggering Probability Modulated (TPM) condition (Wang and Chen, 2017), which is crucial in establishing regret bounds for CMAB algorithms. We use p S i (µ) to denote the probability that the action S triggers arm i when the expectation vector is µ. The TPM condition in OCIM is given below.

Condition 1.
(1-Norm TPM bounded smoothness). We say that an OCIM problem instance satisfies 1norm TPM bounded smoothness, if there exists C ∈ R + (referred to as the bounded smoothness coefficient) such that, for any two expectation vectors µ and µ , and any action S = (S A , S B ), we have |r Fortunately, with a more intricate analysis, we are able to show the following TPM condition.
Theorem 3.1. Under both dominance and proportional tie-breaking rules, OCIM instances satisfy the 1-norm TPM bounded smoothness condition with coefficient C =C, whereC is the maximum number of nodes that any one node can reach in graph G.
The proof of the above theorem is one of the key technical contributions of the paper. In the noncompetitive setting, an edge coupling method could give a relatively simple proof for the TPM condition. 1 The idea of edge coupling is that for every edge e ∈ E, we sample a real number X e ∈ [0, 1] uniformly at random, and determine e to be live under µ if X e ≤ µ e and blocked if X e > µ e , and similarly for µ . This couples the live-edge graphs L and L under µ and µ respectively. In the non-competitive setting, due to the monotonicity property, we only need to consider the TPM condition when µ ≥ µ (coordinate-wise), and this implies that L is a subgraph of L, which significantly simplifies the analysis. However, in the competitive setting, monotonicity does not hold, and we have to show the TPM condition for every pair of µ and µ . Thus, L and L no longer have the subgraph relationship. In this case, we have to show that for every coupling L and L , for every v ∈ V that is activated by A in L but not activated by A in L , it is because either (a) some edge e = (u, w) is live in L but blocked in L while u is A-activated (or equivalently e is A-triggered); or (b) some edge e is live in L but blocked in L while e is B-triggered.  For each arm i ∈ [m], draw a sample µ

6:
Play action S (t) , which triggers a set τ ⊆ [m] of base arms with feedback X for all i ∈ τ do 8: end for 10: end for needs nontrivial inductive proofs for dominance and proportional tie-breaking rules, and then its correctness ensures the TPM condition.

Bayesian Regret Approach
In our OCIM model, since the samples of base arms follow Bernoulli distributions with mean vector µ, we can assume the prior distributions of µ, Q, are Beta distributions, where µ i ∼ Beta(a i , b i ) for all arm i. Given the prior distributions of all arms, we propose an Online Competitive Influence Maximization-Thompson Sampling (OCIM-TS) algorithm, which is described in Algorithm 1. We initialize the prior distribution of each arm i to Beta(a i , b i ). Then we take the context S (t) B and the sampled µ (t) from prior distributions as inputs to the oracle O, and get an output action S (t) . After taking this action, we get feedback X (t) i 's from all triggered arms i ∈ τ , then use them to update the prior distributions of all triggered base arms in τ . Let S = {i ∈ [m] | p S i (µ) > 0} be the set of arms that can be triggered by S. We define K = max S∈S (t) | S| as the largest number of arms that could be triggered by a feasible action. We provide the Bayesian regret bound of OCIM-TS.
Theorem 4.1. The OCIM-TS algorithm has the following Bayesian regret bound withC as defined in Theorem 3.1: This regret bound essentially matches the distributionindependent frequentist regret bound of OCIM-OFU in the next section. The proof of the above theorem is inspired by the posterior sampling regret decomposition of Russo and Van Roy (2014). However, we combine the key property of posterior sampling with the TPM condition in Theorem 3.1 to tackle nonmonotonicity. OCIM-TS can also be applied to gen-eral C 2 MAB-T problems and allows any benchmark offline oracles (e.g., approximate or heuristic oracles). We provide the Bayesian regret bound of OCIM-TS on general C 2 MAB-T problems in the Appendix.

Frequentist Regret Approach
Although OCIM-TS can solve the OCIM problem with a standard offline oracle (e.g., TCIM in Lin and Lui (2015)), it requires the prior distribution of the network parameter µ, which might not be available in practice. In this section, we first propose the OCIM-OFU algorithm. It achieves good frequentist regret without the prior knowledge, but requires a new oracle to solve a harder offline problem. We then design the OCIM-ETC algorithm, which requires less feedback and easier offline computation, but yields a worse frequentist regret bound.

OCIM-OFU Algorithm
As discussed in Section 3.1, due to the lack of monotonicity, we cannot directly use UCB-type algorithms. However, it is still possible to design bandit algorithms following the principle of Optimism in the Face of Uncertainty (OFU). We first introduce a new offline problem that jointly optimizes for both the seed set S * and the optimal influence probability vector µ * , where each dimension of µ * , µ * i , is searched within a confidence interval c i , for all i ∈ E.
We then define a new offline (α, β)-approximation oracle O to solve this problem. Oracle O takes S B and c i 's as inputs and outputs µ O and action is the optimal solution for Eq.(4).
With the offline oracle O, we propose an algorithm following the principle of Optimism in the Face of Uncertainty (OFU), named OCIM-OFU. The algorithm maintains the empirical meanμ i and confidence radius ρ i for each edge probability. It uses the lower and upper confidence bounds to determine the range of and (x) 1− to denote max{x, 0} and min{x, 1} for any real number x. It feeds S to play at round t. The confidence radius ρ i is large if arm i is not triggered often, which leads to a wider search space c i to find the optimistic estimate of µ i . We provide its frequentist regret bound. 10: Theorem 5.1. The OCIM-OFU algorithm has the following distribution-independent bound (see the Appendix for the distribution-dependent bound) withC defined in Theorem 3.1 , The above regret bound has the typical form of √ T ln T , indicating that it is tight on the important time horizon T . In fact, it has the same order as in Wang and Chen (2017)'s for the CMAB problem under monotonicity, despite the fact that the OCIM problem does not enjoy monotonicity, and matches the lower bound of CMAB with general reward functions in (Merlis and Mannor, 2020). This result is due to our non-trivial TPM condition analysis (Theorem 3.1) that shows the same condition as in Wang and Chen (2017)'s setting with monotonicity.
Computational Efficiency. We now discuss the computational complexity of implementing the OCIM-OFU algorithm. We show the complexity of the new offline optimization problem in Eq. (4).
As mentioned before, the original offline problem, i.e., maximizing r S (µ) over S when fixing µ, can be solved by several algorithms (Lin and Lui, 2015) based on submodularity of r S (µ) over S. A straightforward attempt on the new offline problem in Eq.(4) is to show the submodularity of g(S) = max µ r S (µ) over S, and then to use a greedy algorithm on g to select S. Unfortunately, we find that g(S) is not submodular (see the Appendix for a counterexample). Implementing the oracle O is then a challenge. However, it is possible to design efficient approximate oracles for bipartite graphs, which model the competitive probabilistic maximum coverage problem with applications in online advertising (Chen et al., 2016). The main idea is that we can pre-determine that either the lower or the upper bound of c i is optimal and should be chosen as µ * i depending on the tie-breaking rule, then use existing efficient influence maximization algorithms to get approximate solutions. The competitive propagation in the general graph is much more complicated, but we have a key observation that the optimal solution for the optimization problem in Eq.(4) must occur at the boundaries of the intervals c i . Based on that, we discuss solutions for some specific graphs such as trees. See the Appendix for more details.

OCIM-ETC Algorithm
In this section, we propose an OCIM Explore-Then-Commit (OCIM-ETC) algorithm. It has two advantages: first, it does not need the new offline oracle discussed in Sec. 5.1; and second, it requires fewer observations than our other algorithms: instead of the observations of all triggered edges, i.e., τ , it only needs the observations of all direct out-edges of seed nodes.
Like other ETC algorithms (Garivier et al., 2016), OCIM-ETC divides the T rounds into two phases: an exploration phase and an exploitation phase. In the exploration phase, it chooses each node as the seed node of A for N times. The exploration phase thus takes nN/k rounds. In the exploitation phase, it takes S (t) B and the empirical meansμ i as inputs to the oracle O mentioned in Sec. 2, then plays the output action S O,(t) . We give its frequentist regret bound. Theorem 5.3. The OCIM-ETC algorithm has the following distribution-independent regret bound (see the Appendix for the distribution-dependent bound) withC defined in Theorem 3.1, when N = (Cmk) Although this regret bound is worse than that of the OCIM-OFU algorithm in Theorem 5.1, OCIM-ETC requires easier offline computation and less feedback since it only needs to observe the results of direct outedges of seed nodes, which shows the tradeoff between regret bound and feedback/computation in OCIM.

Extension to Probabilistic Seed Distribution for the Competitor
Lin and Lui (2015) extend the offline CIM problem to a probabilistic setting where the competitor's seed distribution is known (i.e., the probability of each node being selected as a seed by the competitor). In this section, we extend our algorithms to handle two new settings where the competitor has a probabilistic seed distribution. Note that we need to slightly modify the TPM condition for these settings. We denote the expected reward of follower A as r( We use p i (S A , D B , µ) to denote the probability that either S A or S B will trigger arm i when the seed set of A is S A , the seed set of B, S B , is sampled from D B , and the expectation vector is µ. The modified TPM condition is given below.

Condition 2. (Modified TPM bounded smoothness).
We say that an OCIM problem instance satisfies modified TPM bounded smoothness, if there exists C ∈ R + such that, for any two expectation vectors µ and µ , and any seed set S A and seed distribu- With the similar analysis of Theorem 3.1, we can show the following TPM condition when the competitor has probabilistic seed distribution.
Theorem 6.1. Under both dominance and proportional tie-breaking rules, OCIM instances satisfy the modified TPM bounded smoothness condition with coefficient C = 2C, whereC is the maximum number of nodes that any one node can reach in graph G.
Known dynamic seed distribution. In round t, the competitor's seed set S A . Since our proposed framework has a nice separation between online learning and offline computation, in this setting, only the offline computation part will be affected. Specifically, we can replace the oracle and the confidence intervals {c i } as inputs and outputs S (t) A . We can use the TCIM algorithm of (Lin and Lui, 2015) to design O new and O new . Our proposed algorithms will have the same regret bounds as in Theorems 4.1 and 5.1.
Unknown fixed seed distribution. In this setting, the seed distribution of the competitor, D B , is unknown to the follower but fixed for all rounds. To solve this problem, we introduce a virtual B seed node u B , which connects to each existing node u with an unknown edge probability p(u B , u) equal to the probability of u being selected as a B seed. This reduces the case of probabilistic seed selection to the standard CIC model with a known seed node u B . The unknown edge probabilities p(u B , u)'s can be learned together with the edge probabilities in the original graph. Therefore, we do not need to know the competitor's seed selection in advance and can learn it over time through the online learning process. Our algorithms will have the same regret guarantees as in Theorems 4.1 and 5.1.

Experiments
Datasets and settings. To validate our theoretical findings, we conduct experiments on two real-world datasets widely used in the influence maximization literature, with detailed statistics summarized in Table 2. First, we use the Yahoo! Search Marketing Advertiser Bidding Data 2 (denoted as Yahoo-Ad), which contains a bipartite graph between 1, 000 keywords and 10, 475 advertisers. Every entry in the original Yahoo-Ad dataset is a 4-tuple, which represents a "keywordid" bid by "advertiser-id" at "time-stamp" with "price". We extract advertiser-ids and keyword-ids as nodes, and add an edge if the advertiser bids the keyword at least once. Each edge shows the "who is interested in what" relationship. This dataset will contain 11, 475 nodes and 52, 567 edges. The motivation of this experiment is to select a set of keywords that is maximally associated to advertisers, which is useful for the publisher to promote keywords to advertisers. We then consider the DM network (Tang et al., 2009) with 679 nodes representing researchers and 3, 374 edges representing collaborations between them. We simulate a researcher asking others (i.e., S A ) to spread her ideas while her competitor (i.e., S B ) promotes a competing proposal. We set the parameters of our experiments as the following. For the edge weights, Yahoo-Ad uses the weighted cascade method (Kempe et al., 2003), i.e. p(s, t) = 1/deg − (s), where deg − (s) is the in-degree of node s, and weights for DM are obtained by the learned edge parameters from (Tang et al., 2009). For Bayesian regrets, we set a prior distribution of µ e ∼ Beta(5w e , 5(1−w e )), where w e is the true edge weight as specified above.
We model non-strategic and strategic competitors by selecting the seed set S B uniformly at random (denoted as RD) or by running the non-competitive influence maximization algorithm (denoted as IM). In our experiments, we set |S A | = |S B | = 5 for Yahoo-Ad and |S A | = |S B | = 10 for the DM dataset, and B > A. Since the optimal solution given the true edge probabilities cannot be derived in polynomial time, for Yahoo-Ad, we use the greedy solution as the optimal baseline, which is a (1 − 1/e, 1)-approximate solution.
2 https://webscope.sandbox.yahoo.com  For the DM dataset, we use the IMM solution as the optimal baseline, which is a (1 − 1/e − , 1 − n −l )approximate solution. For frequentist regrets, we repeat each experiment 50 times and show the average regret with 95% confidence interval. For Bayesian regrets, we draw 5 problem instances according to the prior distributions, conduct 10 experiments in each instance and report the average Bayesian regret over the 50 experiments. Due to the space constraint, results of other settings are provided in the Appendix.
Algorithms for comparison. For OCIM-TS, since the true prior distribution is unknown for the frequentist setting, we use the uninformative prior Beta(1, 1) for each µ e . For OCIM-OFU, we shrink its confidence interval by α ρ , i.e., ρ i ← α ρ 3 ln t/2T i , to speed up the learning. The role of α ρ represents a tradeoff between theoretical guarantees and real-world performance. α ρ ≥ 1 provides theoretical regret bounds for the worst-case (i.e., our algorithms have sublinear regret for any problem instance) and most of the bandit literature gives regret analysis under this condition. However, in practice, we often do not face the worst problem instance. Taking a more aggressive α ρ helps speed up the learning empirically (Liu et al., 2021), though the algorithms may incur linear regrets for bad problem instances (which are likely rare in practice), preventing us from achieving worst-case theoretical regret bounds. We compare OCIM-OFU/OCIM-TS to the -Greedy algorithm with parameter = 0 (denoted as the EMP algorithm) and = 0.01, which inputs the empirical mean into the offline oracle with 1 − probability and otherwise selects S A uniformly at random. The results of OCIM-ETC are moved to the Appendix as it requires more rounds to learn than others.
Running time. We show the average running times for different algorithms in Table 3. For the Yahoo-Ad dataset, OCIM-ETC is the fastest one as it only needs to call the oracle for one time before the exploitation phase. The running time of OCIM-TS is slower than that of OCIM-OFU because it requires an extra sampling procedure to generate Thompson samples. For the DM dataset, all algorithms consume less time since the graph is smaller, but the relative order for different algorithms are preserved.
Experimental result for frequentist regrets Figures 2a and 2b show the results for Yahoo-Ad. First, the regret of OCIM-OFU grows sub-linearly with respect to round T for all α ρ , consistent with Theorem 5.1's regret bound. Second, we can observe that OCIM-OFU is superior to EMP and -Greedy when α ρ = 0.05. When α ρ = 0.2, OCIM-OFU may have larger regret due to too much exploration. The OCIM-TS algorithm has larger slope in regrets compared to other algorithms. We speculate that such large slope comes from the uninformative prior, which requires more rounds to compensate for the mismatch of the uninformative and the true priors.
The results on the DM dataset are shown in Figs. 2c and 2d. Generally, they are consistent with those on the Yahoo-Ad dataset: OCIM-OFU also grows sublinearly w.r.t round T . When α ρ = 0.05, OCIM-OFU has smaller regret than all baselines. Moreover, the difference between OCIM-OFU and the baselines for the non-strategic competitor (RD) is more significant than that of the strategic competitor's (IM), because the non-strategic competitor is less "dominant" and OCIM-OFU can carefully trade off exploration and exploitation to maximize A's influence. OCIM-TS learns faster and achieves better performance in this dataset compared to that in the Yahoo-Ad dataset.
Experimental result for Bayesian regrets We show Bayesian regrets of all algorithms in Figure 3. All algorithms except for OCIM-TS have similar curves. OCIM-TS, however, achieves at least two orders of magnitudes lower regret (BayesReg(T ) ≈ 100) compared with other algorithms. The reason is that OCIM-TS leverages its prior knowledge to quickly converge to the optimal solution, but other algorithms cannot use this knowledge effectively.

Conclusion and Future Work
In this paper, we formulate the OCIM problem and introduce a general C 2 MAB-T framework for it. We prove that one important condition required by prior CMAB algorithms, the TPM condition, still holds, while the other one, monotonicity, is not satisfied. We propose three algorithms that balance between prior knowledge, offline computation, feedback and regret bound: OCIM-TS relies on prior knowledge and achieves logarithmic Bayesian regret; OCIM-OFU needs to solve a harder offline problem and achieves logarithmic frequentist regret; and OCIM-ETC requires less feedback at the expense of a worse frequentist regret bound. We extend our framework to settings with more complex competitor actions.
This paper initiates the first study on OCIM, and it opens up a number of future directions. One is to design efficient offline approximation algorithms in the competitive setting when edge probabilities take a range of values. Another interesting direction is to study other partial feedback models, e.g. we only observe feedback from edges triggered by A but not B. A further direction is to look into distributed online learning, when competitors A and B both learn from the propagation and deploy their seeds accordingly. He, X., Song, G., Chen, W., and Jiang, Q. Liu, X., Zuo, J., Chen, X., Chen, W., and Lui, J. C.  A Proof of Theorem 3.1 Proof. Let r v S (µ) be the probability that node v is activated by A. From the proof of Lemma 2 in (Wang and Chen, 2017), we know that if for every node v and every µ and µ vectors we have then Theorem 3.1 is true. Notice that r where L and L are two live-edge graphs sampled under µ and µ , respectively. As mentioned in Sec. 3.2, we use an edge coupling method to compute the difference between r v S (µ) and r v S (µ ). Specifically, for each edge e, suppose we independently draw a uniform random variable X e over [0, 1], let where L(e) represents the live/blocked state of edge e in live-edge graph L. Notice that L and L does not have the subgraph relationship. Let X := (X 1 , . . . , X e ), the difference can be written as: where f (S, L, v) := 1{v is activated by A under L}. Since f (S, L, v) − f (S, L , v) could be 0, 1 or -1, we will discuss these cases separately.
This will not contribute to the expectation.
2) f (S, L, v) − f (S, L , v) = 1. This will occur only if there exists a path such that: under L, v can be activated by A via this path, while under L , v cannot be activated by A via this path. We denote this event as E 1 . We will show that E 1 occurs only if at least one of E A 1 and E B 1 occurs.
1 : There exists a path u → v 1 → · · · → v d = v such that: 1. u is activated by B under both L and L 2. edge (u , v 1 ) is live under L but not L Lemma A.1. E 1 occurs only if at least one of E A 1 and E B 1 occurs.
Proof. Let us first discuss the relationship between E 1 , E A 1 and E B 1 . For E 1 , if v can be activated by A under L but not L , it is because either: (a) some edge e = (u, w) is live in L but blocked in L while u is A-activated (or equivalently e is A-triggered); or (b) some edge e is live in L but blocked in L while e is B-triggered. The former could be relaxed to E A 1 , and the latter could be relaxed to E B 1 . Notice that E A 1 and E B 1 are not mutually exclusive and we are interested in the upper bound of P{E 1 }. Assuming E 1 is true, consider the shortest path P 0 := {u 0 → u 1 → · · · → u l0 = v} from one seed node of A, u 0 , to node v, such that under L node v is activated by A but under L it is not. When E 1 is true, there must exist a node that is not activated by A in P 0 under L . We denote the first node from u 0 to v (i.e., closest to u 0 ) in P 0 that is not activated by A under L as u i .
Next, let us consider the live/blocked state of edge (u i−1 , u i ). We already know edge (u i−1 , u i ) is live under L. If edge (u i−1 , u i ) is blocked under L , since u i−1 is activated by A under both L and L , it directly becomes E A 1 . Otherwise, if edge (u i−1 , u i ) is live under L , the reason that node u i is not activated by A could only be that it is activated by B. In this case, there must exist a path P 1 := {u 0 → u 1 → · · · → u l1 = u i } from one seed node of B, u 0 , to node u i , such that u i is activated by B under L but not L. This can only occur when there exists a node that is not activated by B in P 1 under L. We denote the first node from u 0 to u l1 (i.e., closest to u 0 ) in P 1 that is not activated by B under L as u j . Notice that when the tie-breaking rule is A > B, we have l 1 < i ≤ l 0 as B should arrive at u i earlier than A; when the tie-breaking rule is B > A, we have l 1 ≤ i ≤ l 0 as B should arrive at u i no later than A. We will discuss the case of the proportional tie-breaking rule separately after the discussion of the dominance tie-breaking rules.
Then, let us consider the live/blocked state of edge (u j−1 , u j ). We already know edge (u j−1 , u j ) is live under L . If edge (u j−1 , u j ) is blocked under L, since u j−1 is activated by B under both L and L , it directly becomes E B 1 . Otherwise, if edge (u j−1 , u j ) is live under L, the reason that node u j is not activated by B could only be that it is activated by A. It also means neither E A 1 nor E B 1 occurs so far. In this case, there must exist a path P 2 := {u 0 → u 1 → · · · → u l2 = u j } from one seed node of A, u 0 , to node u j , such that u j is activated by A under L but not L . This can only occur when there exists a node that is not activated by A in P 2 under L . We denote the first node from u 0 to u l2 (i.e., closest to u 0 ) in P 2 that is not activated by A under L as u k . Notice that when A > B, we have l 2 ≤ j ≤ l 1 < l 0 as A should arrive at u j no later than B; when B > A, we have l 2 < j ≤ l 1 ≤ l 0 as A should arrive at u j earlier than B. Now let us consider the live/blocked state of edge (u k−1 , u k ). We already know edge (u k−1 , u k ) is live under L.
If edge (u k−1 , u k ) is blocked under L , since u k−1 is activated by A under both L and L , it directly becomes E A 1 . Otherwise, if edge (u k−1 , u k ) is live under L , the reason that node u k is not activated by A could only be that it is activated by B. In this case, there must exist a path P 3 := {u 0 → u 1 → · · · → u l3 = u k } from one seed node of B, u 0 , to node u k , such that u k is activated by B under L but not L. This can only occur when there exists a node that is not activated by B in P 3 under L. We denote the first node from u 0 to u l3 (i.e., closest to u 0 ) in P 3 that is not activated by B under L as u s . Notice that when A > B, we have l 3 < k ≤ l 2 ≤ l 1 as B should arrive at u k earlier than A; when B > A, we have l 3 ≤ k ≤ l 2 < l 1 as B should arrive at u k no later than A.
Again, let us consider the live/blocked state of edge (u s−1 , u s ). We already know edge (u s−1 , u s ) is live under L . If edge (u s−1 , u s ) is blocked under L, since u s−1 is activated by B under both L and L , it directly becomes E B 1 . Otherwise, if edge (u s−1 , u s ) is live under L, similar to the discussion above, we need to consider a new path P 4 with length l 4 and l 4 < l 2 .
For the case of the proportional tie-breaking rule, in addition to the edge coupling, we also need to couple the permutation order (Chen et al., 2011) for each node in L and L . More specific, for each node j, we randomly permute all of its in-neighbors, then when we need to break a tie on j, we find its activated neighbor i that is ordered first in the permutation order, and assign the state of i as j's state. Assuming the same permutation order in L and L , let us consider path P 0 and P 1 again. If l 0 = l 1 , then u i must be v. If E A 1 does not occur in P 0 , then the only neighbor of v in P 1 must be ordered before the only neighbor of v in P 0 in the permutation order on v. However, if E B 1 does not occur in P 1 , with such permutation order, it is impossible that v is activated by A under L but not L . As a result, if neither E A 1 nor E B 1 occurs in path P 0 and P 1 , we have l 2 ≤ l 1 < l 0 in the case of the proportional tie-breaking rule.
To sum up, if neither E A 1 nor E B 1 occurs in path P 0 and P 1 , we need to check whether they could occur in a new path P 2 shorter than P 0 , and P 3 shorter than P 1 . As a result, we only need to check whether E A 1 or E B 1 occurs in the path with only one edge. In that case, E A 1 or E B 1 occurs for sure. Thus, by induction, we conclude that at least one of E A 1 and E B 1 occurs when considering any path with more than one edge, so E 1 will occur only if at least one of E A 1 and E B 1 occurs. Now, let us consider the two events in E A 1 for a specific edge e = (u, v 1 ). We find that the first event {u is activated by A under both L and L }, is independent of the second event {edge e is live under L but not L }, since the live/blocked state of edge e does not affect the activation of its tail node u. Also, for edge e = (u, v 1 ), the probability of these two events can be written as P{u is activated by A under L and L } = P{e is triggered by A under L and L }, P{e is live under L but not L } = µ e − µ e if µ e > µ e 0 otherwise.
As a result, we have: P{e is triggered by A under L and L }(µ e − µ e ) Since E A 1 and E B 1 are symmetric, we also have: P{e is triggered by B under L and L }(µ e − µ e ) Combining with Lemma. A.1, we have 3 Similar to the previous case, this will occur only if there exists a path such that: under L , v can be activated by A via this path, while under L, v cannot be activated by A via this path. We denote this event as E −1 . We show that E −1 occurs only if at least one of E A −1 and E B −1 occurs. E A −1 : There exists a path u → v 1 → · · · → v d = v such that: 1. u is activated by A under both L and L 2. edge (u, v 1 ) is live under L but not L E B −1 : There exists a path u → v 1 → · · · → v d = v such that: 1. u is activated by B under both L and L 2. edge (u , v 1 ) is live under L but not L Since they are symmetric with E A 1 and E B 1 , following the same analysis, we can get P{e is triggered by A under L and L }(µ e − µ e ) P{e is triggered by B under L and L }(µ e − µ e ) (16) Combining all cases together, we have: The last inequality above is due to: P{e is triggered by A or B under L and L }|µ e − µ e | Notice that Eq.(18) could be relaxed to: B Proof of Theorem 4.1 Proof. We define G (t) as the feedback of OCIM in round t, which includes the outcomes of X (t) i for all i ∈ τ t . We denote by F t−1 the history (S (1) , G (1) , · · · , S (t−1) , G (t−1) ) of observations available to the player when choosing an action S (t) . For the Bayesian analysis, we assume the mean vector µ follows a prior distribution Q. In round t, given F t−1 , we define the posterior distribution of µ as Q (t) (i.e., µ (t) ∼ Q (t) where µ (t) is given in Alg. 1). As mentioned in Section 4, OCIM-TS allows any benchmark offline oracles, including approximation oracles. We consider a general benchmark oracle O(S B , µ). As oracle O might be a randomized policy (e.g., an (α, β)-approximation oracle with success probability β), we use a random variable ω ∼ Ω to represent all its randomness. In order to discuss the performance of OCIM-TS with oracle O, we rewrite the Bayesian regret in Eq.(2) as Notice that O(S The key step to derive the Bayesian regret bound of OCIM-TS is to show that the conditional distributions of µ and µ t given F t−1 are the same: which is true since we use Thompson sampling to update the posterior distribution of µ. With this finding, we consider the Bayesian regret in Eq. (2): where Eq. (24) We can bound these three terms separately. For term (a), when µ t ∈ C t , µ ∈ C t , we could bound |µ i,t − µ i | ≤ |µ i,t −μ i,t | + |µ i −μ i,t | ≤ 2ρ i,t , ∀i. When ∆ St ≥ M and N t t (Definition 7 in (Wang and Chen, 2017)) holds, by the proof of Lemma 5 in (Wang and Chen, 2017), we have ∆ St ≤ i∈St κ ji,T (M i , N i,ji,t−1 ) whereS t is the set of arms triggered by S t and κ ji,T (M i , N i,ji,t−1 ) is defined in (Wang and Chen, 2017). We have , since C t is determined given F t−1 , and given F t−1 , µ and µ t follow the same distribution. Since max St ∆ St ≤ n, we have For term (c), we can bound it by For term (d), similar to Eq.(20) in (Wang and Chen, 2017), we have Combine them together, we have . Take M = 576C 2 mK ln T /T , we finally get finally get the Bayesian regret bound of TS-OCIM: mKT ln T + 2Cm + log 2 T 18 ln T 0 + 4 · π 2 6 · n · m.
C Proof of Theorem 5.1 Proof. We first introduce the following definitions to assist our analysis. Recall that S (t) is the action space in round t. We define the reward gap ∆ (t) be the set of arms that can be triggered by S. We define K = max S∈S (t) | S| as the largest number of arms could be triggered by a feasible action. We use x 0 to denote max{ x , 0}. If ∆ (T ) min > 0, we provide the distribution-dependent bound of the OCIM-OFU algorithm.
To prove the distribution-dependent and the distribution-independent regret bounds, we generally follow the proof of Theorem 1 in Wang and Chen (2017). However, since we extend the original CMAB problem to a new contextual setting where the action space S (t) is the context, and monotonicity does not hold in the OCIM setting, we need to modify their analysis to tackle these changes. We introduce a positive real number M i for each arm i and define M S (t) = max i∈S (t) M i . Define Let N s t be the event that at the beginning of round t, for every arm i.e., oracle O fails to output an α-approximate solution. Let N t t be the event that the triggering is nice at the beginning of round t (Definition 7 in (Wang and Chen, 2017)). The following lemma explains how κ contributes to the regret.
where j i is the index of the TP group with S (t) ∈ S i,ji (see Definition 5 in (Wang and Chen, 2017)).
Proof. By N s t and 0 ≤ µ i ≤ 1 for all i ∈ [m], we have It means that we have the correct estimated range of µ i for all i ∈ [m] at round t. Combining with ¬H t for the offline oracle O, we have By the TPM condition in Theorem. 3.1, we have We want to bound ∆ (t) In fact, if N s t holds and µ So far, all requirements on bounding ∆ St in Lemma 5 from (Wang and Chen, 2017) are also satisfied by ∆ S (t) of OCIM-OFU algorithm in the OCIM setting without monotonicity. We can then follow the same steps to bound p S (t) i (µ)|µ (t) i − µ i | in the two cases they considered (combining their Eq.(11)-(13)) and get With Lemma C.1, we can follow the proof of Lemma 6 in (Wang and Chen, 2017) to bound the regret when {∆ (t) Thus, no regret is accumulated when ∆ To derive the distribution-independent bound, we take M i = M = (576C 2 mK ln T )/T , follow Eq.(23) in (Wang and Chen, 2017) and get Reg α,β (T ; µ) ≤ 12C √ mKT ln T + 2Cm + log 2 T 18 ln T 0 + 2 · π 2 6 · n · m.

D.1 Proof of Theorem 5.2
Proof. In order to prove Theorem 5.2, we first introduce a new optimization problem denoted as P 1 : given S, the new problem aims to find the optimal µ i for one edge i to maximize r S (µ), while fixing the values of all others. The following lemma shows it is #P-hard.
Lemma D.1. Given S and fixing µ e for all e = i, finding the optimal µ i ∈ c i for one edge i that maximizes r S (µ) is #P-hard.
Proof. We prove the hardness of this optimization problem via a reduction from the influence computation problem. We first consider a general graph G 0 with n nodes and m edges, where all influence probabilities on edges are set to 1/2. Given S A , computing the influence spread of A in such a graph is #P-hard. Notice that there is no seed set of B in G 0 . Now let us take one node v in G 0 and denote its activation probability by A as is also #P-hard and we want to show that it can be reduced to our optimization problem in polynomial time. We first construct a new graph G 1 based on G 0 . For G 1 , we keep G 0 and S A unchanged, then add several nodes and edges as shown in Fig. 5. We add node 1 to the seed set of B and node 5 to the seed set of A, so the joint action S = {S A ∪ {5}, S B = {1}}. In this new graph G 1 , we consider the optimization problem of finding the optimal µ 1 (influence probability on edge (3, 4)) within its range c 1 that maximizes r S (µ). Notice that the influence probability γ on edge (1, 3) is a constant and µ 1 would only affect the activation probability of node 4. We denote the activation probability by A of node 4 as h A (G 1 , S, 4). In order to maximize r S (µ), we only need to maximize h A (G 1 , S, 4). It can be written as: It is easy to see h A (G 1 , S, 4) has a linear relationship with µ 1 , so the optimal µ 1 could only be either the lower or upper bound of its range c 1 . Assuming we can solve the optimization problem of finding the optimal µ 1 , then we can determine the sign of µ 1 's coefficient in Eq.(36): if the optimal µ 1 is the upper bound value in c 1 , It means we can answer the question that whether h A (G 1 , S, v) is larger (or smaller) than γ 1−γ . Notice that h A (G 0 , S A , v) = h A (G 1 , S, v), so we can manually change the value of γ to check whether h A (G 0 , S A , v) is larger (or smaller) than x = γ 1−γ for any x ∈ [0, 1], Recall that all edge probabilities in G 0 are set to 1/2, so the highest precision of h A (G 0 , S A , v) should be 2 −m . Hence, we can use a binary search algorithm to find the exact value of h A (G 0 , S A , v) in at most m times. It means computing the activation probability of v in G 0 can be reduced to the optimization problem of finding the optimal µ 1 in G 1 , which completes the proof.
We then show that P 1 is a special case of Eq.(4). The main idea is to relax the constraints |S A | ≤ k, S = {S A , S B } in Eq.(4) and show that it can find the optimal µ for any given S. Consider a graph G with n nodes and a given seed set S = {S A , S B }. We construct a new graph G by manually add additional n + 1 nodes pointing from each seed node in S A . If we can solve the optimization problem Eq.(4) in the new graph G , since S A must be the optimal seed set of A and the added nodes will not affect the prorogation in G, we will also find the optimal µ i 's in the original graph G for the given S. Then, it is easy to see P 1 is a special case of Eq.(4) since P 1 only find the optimal µ i for one edge i. With Lemma D.1, we know Eq.(4) is also #P-hard.

D.2 Non-submodularity of g(S)
In Section 5.1, we introduce g(S) = max µ r S (µ), which is an upper bound function of r S (µ) for each S. If g(S) is submodular over S, we can use a greedy algorithm on g(S) to find an approximate solution. However, the following example in Fig. 6 shows that g(S) is not submodular.
which is contrary to submodularity.

D.3 Bipartite Graph
We consider a weighted bipartite graph G = (L, R, E) where each edge (u, v) is associated with a probability p(u, v). Given the competitor's seed set S B ⊆ L, we need to choose k nodes from L as S A that maximizes the expected number of nodes activated by A in R, where a node v ∈ R can be activated by a node u ∈ L with an independent probability of p(u, v). As mentioned before, if A and B are attempting to activate a node in L at the same time, the result will depend on the tie-breaking rule. If all edge probabilities are fixed, i.e., µ is fixed, r S (µ) is still submodular over S A , so we can use a greedy algorithm as a (1 − 1/e, 1)-approximation oracle O greedy . Based on it, let us discuss the new offline optimization problem in Eq.(4) under our two tie-breaking rules: (1) A > B: since B will never influence nodes in R earlier than A in bipartite graphs, and A will always win the competition, from A's perspective, we can ignore S B to choose S A . In this case, all edge probabilities should take the maximum values: for all i ∈ E, µ i equals to the upper bound of c i , and we then use the oracle O greedy to find S A .
(2) B > A: since A will never influence nodes in R earlier than B in bipartite graphs, and B will always win the competition, all out-edges of S B , denoted as E S B , should take the minimum probabilities to maximize the influence spread of A. All the other edges in E\E S B should take the maximum probabilities. Formally, for all i ∈ E S B , µ i equals to the lower bound of c i ; for all i ∈ E\E S B , µ i equals to the upper bound of c i . We then use the oracle O greedy to find S A . To sum up, in bipartite graphs, r S (µ) is optimized by pre-determining µ based on the tie-breaking rule, and then using the greedy algorithm to get a (1 − 1/e, 1)-approximation solution. Since the time complexity of influence computation in the bipartite graph is O(m), the time complexity of the offline algorithm is equal to that of the greedy algorithm, O(kmn).

D.4 General Graph
GraphWe The competitive propagation in the general graph is much more complicated, so it is hard to predetermine all edge probabilities as in the bipartite graph case. However, we have a key observation: where L is one possible live-edge graph (each edge e ∈ E is in L with probability µ e and not in L with probability 1 − µ e , and this is independent from other edges), Γ A (L, S) is the set of nodes activated by A from seed sets S = {S A , S B } under live-edge graph L and E(L) is the set of edges that appear in live-edge graph L. Eq.(38) shows that r S (µ) is linear with each µ i , so the optimal µ i must take either the minimum or the maximum value in its range c i .
Lemma D.2 implies that for any edge e not reachable from B seeds, it is safe to always take its upper bound value since it can only helps the propagation of A. This further suggests that if we only have a small number (e.g. log m) of edges reachable from B, then we can afford enumerating all the boundary value combinations of these edges. For each such boundary setting µ, we can use the IMM algorithm (Tang et al., 2014) to design a (1 − 1/e − , 1 − n −l )-approximation oracle O IMM with time complexity T IMM = O((k + l)(m + n) log n/ 2 ). We discuss such graphs that satisfy the above condition in directed trees. Specifically, we consider the inarborescence, where all edges point towards the root. For general graphs, designing efficient approximation algorithms for the offline problem in Eq. (4) remains a challenging open problem, due to the joint optimization over S and µ and the complicated function form of r S (µ). Nevertheless, heuristic algorithms are still possible. In the experiment section, we employee the following heuristic with the B > A tie-breaking rule: for all outgoing edges from B seeds, we set their influence probabilities to their lower bound values, while for the rest, we set them to their upper bound values. This setting guarantees that the first-level edges from the seeds are always set correctly, no matter how we select A seeds. They do not guarantee the correctness of second or higher level edge settings in the cascade, but the impact of those edges to influence spread decays significantly, so the above choice is reasonable as a heuristic.

E Proof of Theorem 5.3
Algorithm 3  Take k nodes that have not been chosen for N times as S A .

7:
Observe the feedback X (t) i for each direct out-edge of S A , i ∈ τ direct .

15: end for
The OCIM-ETC algorithm is described in Alg. 3. We utilize the following well-known tail bound in our proof.
With the same definitions in Appendix C, we can decompose the regret as: Next, let us rewrite the TPM condition in Theorem 3.1. For any S, µ and µ , we have where C is the maximum number of nodes that any one node can reach in graph G. Let S * ,t µ denote the optimal action for µ in round t. Under ¬F, we have where the third inequality is due to Eq.(40). Combining Eq.(40) and Eq.(41) together, we have Let us define δ 0 := is at least an α-approximate solution, such that ∆ The first inequality is obtained by applying the Hoeffding's Inequality (Lemma E.1) and union bound to the event max i∈[m] |µ i −μ i | ≥ δ 0 . Now we need to choose an optimal N that minimizes Eq.
Next, let us prove the distribution-independent bound. Let N denote the event that |μ i − µ i | ≤ 2 ln T N for all i ∈ [m]. By the Hoeffding's Inequality and union bound, we have When N holds, with Eq.(42), we have and the regret in Eq.(39) can be written as We can choose N so as to (approximately) minimize the regret. For N = (Cmk) 2 3 n − 4 3 T 2 3 (ln T ) 1 3 , we obtain: To complete the proof, we need to consider both N and ¬N . As shown in Eq.(45), the probability that ¬N occurs is very small, and we have: F Proof of Theorem 6.1 Proof. As mentioned in Section 6, we need to introduce a virtual B seed node u B , which connects to each existing node u with an unknown edge probability p(u B , u) equal to the probability of u being selected as a B seed. By adding these virtual nodes and edges, we get a new graph G with 2n nodes and m + n edges. Since S B is fixed under G , we can follow the same steps in the proof of Theorem 3.1 to show the TPM condition holds under G . Note that the maximum number of nodes that any one node can reach in G is twice as that in the original graph G, so the new bounded smoothness coefficient C = 2C.

G.1 Experiments for A > B Tie-breaking Rule
When we consider A > B in bipartite graphs, we can trivially ignore S B to choose S A since the influence spread ends in one diffusion round, and OCIM becomes the online influence maximization problem without competition. We show such results in Figure 7. Note that the distribution of B no longer affects the performance of A when A > B and we only use one figure for the IM and RD distribution. For general graphs, we use the same DM dataset and parameter settings described in Sec. 7, and the only difference is that A now dominates B. We show the results in Figure 8. Overall, the results and the analysis for A > B are consistent with B > A.

G.2 Experiments for OCIM-ETC
We show the frequentist/Bayesian regret results for the OCIM-ETC algorithm in Figure 9, Figure 10 and Figure 11. In Figure 9, we set exploration phase to be 250 rounds and the experiments show that we suffer linear regrets in both the exploration and the exploitation phase, meaning that the unknown parameters are under-explored. Thus we reset exploration to be 1500 and Figure 11 shows that OCIM-ETC now has constant regret in the exploitation phase. For DM dataset, since the node number and the edge number are less than Yahoo-Ad, we can see constant regrets after 1000 rounds of exploration in Figure 10. Compared with OCIM-OFU/OCIM-TS, OCIM-ETC requires more rounds to learn the unknown influence probabilities and has larger regrets than OCIM-OFU/OCIM-TS, but with sufficient exploration (which is much less than the theoretical requirements N = (Cm)

G.3 Experiments for Probabilistic Seed Distribution
For the settings where the competitor has unknown fixed seed distribution, we first run the non-competitive influence maximization algorithm for S B . and get the best 5 seeds on Yahoo-Ad and the best 10 seeds on DM, respectively, We then consider the seed distribution of S B as choosing each node from the best seeds with probability 0.5, i.e., the probability that choosing all best 5 seeds on Yahoo-Ad is 0.5 5 and the probability that choosing all best 10 seeds on DM is 0.5 10 . This seed distribution of S B is unknown to our algorithms. In our experiments, we set |S A | = 5 for Yahoo-Ad and |S A | = 10 for DM, and assume B > A. Figure 12 shows that OCIM-OFU is still superior to EMP and -Greedy for this setting with more complex competitor actions. We omit the results of OCIM-TS here as it requires the prior knowledge of the competitor's seed distribution. However, as long as the given prior does not differ much from the true prior, OCIM-TS will also achieve good regret results.  H Contextual combinatorial multi-armed bandit framework C 2 MAB-T

H.1 General Framework
We propose a general framework of contextual combinatorial multi-armed bandit with probabilistically triggered arms (C 2 MAB-T), which is a contextual extension of CMAB-T in (Wang and Chen, 2017).
C 2 MAB-T is a learning game between a learning player and an environment. The environment consists of m random variables X 1 , · · · , X m called base arms following a joint distribution D over [0, 1] m . Distribution D is chosen by the environment from a class of distributions D before the game starts. The player knows D but not the actual distribution D in advance. Different from that in CMAB-T, the environment in C 2 MAB-T also provides contexts for the learning agent, which will be discussed in detail later.
The learning process runs in discrete rounds. In round t, the environment first provides a context, S (t) ⊆ S, to the player, where S is the full action space and S (t) is a subset of it, representing the current action space in round t. The player then chooses an action S (t) ∈ S (t) based on the feedback history from previous rounds. The environment also draws an independent sample X (t) = (X (t) 1 , · · · , X (t) m ) from the joint distribution D. When action S (t) is played on the environment outcome X (t) , a random subset of arms τ t ∈ [m] are triggered, and the outcomes of X (t) i for all i ∈ τ t are observed as the feedback to the player. τ t may have additional randomness beyond the randomness of X (t) . Let D trig (S, X) denote a distribution of the triggered subset of [m] for a given action S and an environment outcome X. We assume τ t is drawn independently from D trig (S (t) , X (t) ). The player obtains a reward R(S (t) , X (t) , τ t ) fully determined by S (t) , X (t) and τ t . A learning algorithm aims at selecting actions S (t) 's over time based on the past feedback to accumulate as much reward as possible.
For each arm i, let µ i = E X∼D [X i ]. Let µ = (µ 1 , · · · , µ m ) denote the expectation vector of arms. We assume that the expected reward E[R(S, X, τ )], where the expectation is taken over X ∼ D and τ ∼ D trig (S, X), is a function of action S and the expectation vector µ of the arms. Thus, we denote r S (µ) := E[R(S, X, τ )]. We assume the outcomes of arms do not depend on whether they are triggered, i.e., The performance of a learning algorithm A is measured by its expected regret, which is the difference in expected cumulative reward between always playing the best action and playing actions selected by algorithm A. Let opt (t) (µ) = sup S (t) ∈S (t) (µ) denote the expected reward of the optimal action in round t. We assume that there exists an offline oracle O, which takes context S (t) and µ as inputs and outputs an action S O,(t) such that Pr{r S O,(t) (µ) ≥ α·opt (t) (µ))} ≥ β, where α is the approximation ratio and β is the success probability. Instead of comparing with the exact optimal reward, we take the αβ fraction of it and use the following (α, β)-approximation frequentist regret for T rounds: where S A,(t) is the action chosen by algorithm A in round t.
Another way to measure the performance of the algorithm A is using Bayesian regret. Denote the prior distribution of µ as Q. When the prior Q is given, the corresponding Bayesian regret is defined as: Note that the contextual combinatorial bandit problem is also studied in (Chen et al., 2018;Qin et al., 2014). They consider the context features of all bases arms, which can affect their expected outcomes in each round, and assume the action space of super arms is a subset of [m]. However, we do not bond the context with base arms and consider the feasible set of super arms, S (t) , as the context, which is more flexible than a subset of [m]. Besides, we are the first to consider probabilistically triggered arms in the contextual combinatorial bandit problem.

H.2 Monotonicity and Triggering Probability Modulated Condition
In order to guarantee the theoretical regret bounds, we consider two conditions given in (Wang and Chen, 2017). The first one is monotonicity, which is stated below. Condition 3. (Monotonicity). We say that a C 2 MAB-T problem instance satisfies monotonicity, if for any action S, for any two expectation vectors µ = (µ 1 , . . . , µ m ) and µ = (µ 1 , . . . , µ m ), we have r S (µ) ≤ r S (µ ) if µ i ≤ µ i for all i ∈ [m].
Algorithm 4 Contextual CUCB with offline oracle O, C 2 -UCB Obtain context S (t) .

9:
Play action S (t) , which triggers a set τ ⊆ [m] of base arms with feedback X (t) i 's, i ∈ τ .

10:
For every i ∈ τ update T i andμ i : The second condition is Triggering Probability Modulated (TPM) Bounded Smoothness. We use p S i (µ) to denote the probability that the action S triggers arm i when the expectation vector is µ. The TPM condition in C 2 MAB-T is given below.

Condition 4.
(1-Norm TPM bounded smoothness). We say that a C 2 MAB-T problem instance satisfies 1-norm TPM bounded smoothness, if there exists C ∈ R + (referred as the bounded smoothness coefficient) such that, for any two expectation vectors µ and µ , and any action S, we have |r S (µ) − r S (µ )| ≤ C i∈[m] p S i (µ)|µ i − µ i |.

H.3 Regret Bounds with Monotonicity
For the general C 2 MAB-T problem that satisfies both monotonicity (Condition 3) and TPM bounded smoothness (Condition 4), we introduce a contextual version of the CUCB algorithm (Wang and Chen, 2017), which is described in Algorithm 4. Recall that S (t) is the action space in round t. We define the reward gap ∆ | p S i (µ) > 0} be the set of arms that can be triggered by S. We define K = max S∈S (t) | S| as the largest number of arms could be triggered by a feasible action. We use x 0 to denote max{ x , 0}. Contextual CUCB (C 2 -UCB) has the following regret bounds.
Proof. We first show that Lemma 5 in (Wang and Chen, 2017) still holds for Contextual CUCB algorithm in the C 2 MAB-T problem. Let N s t be the event that at the beginning of round t, for every arm i ∈ [m], |μ i,t −µ i | ≤ ρ i,t . Let H t be the event that at round t oracle O fails to output an α-approximate solution. In Lemma 5 from (Wang and Chen, 2017), it assumes that N s t and ¬H t hold, then we have r S (t) (μ t ) ≥ α · opt (t) (μ t ) ≥ α · opt (t) (µ) = r S (t) (µ) + ∆ (t) By the TPM condition, we have Draw a sample µ (t) from Q t .

7:
Play action S (t) , which triggers a set τ ⊆ [m] of base arms with feedback X (t) i 's, i ∈ τ .

9:
Play action S (t) , which triggers a set τ ⊆ [m] of base arms with feedback X (t) i 's, i ∈ τ .

10:
For every i ∈ τ update T i andμ i : T i = T i + 1,μ i =μ i + (X (t) i −μ i )/T i . 11: end for which is in the same form of Eq.(10) in (Wang and Chen, 2017). Hence, we can follow the remaining proof of its Lemma 5. With Lemma 5, we can follow the proof of Lemma 6 in (Wang and Chen, 2017) to bound the regret when ∆

H.4 Regret Bounds without Monotonicity
As discussed in Section 3, OCIM is an example of C 2 MAB-T that satisfies the TPM condition but not monotonicity. For the general C 2 MAB-T problem without monotonicity, we proposed two algorithms, C 2 -TS, C 2 -OFU, that can still achieve logarithmic Bayesian and frequentist regrets respectively. We also present C 2 -ETC that has a tradeoff between feedback requirement and regret bound.
C 2 -TS is described in Algorithm 5. Different from OCIM-TS, we input a general prior Q (which depends on D and might not be Beta distributions anymore) and update the posterior distribution Q t accordingly. With the same definitions in H.3 and δ (T ) max = max µ ∆ (T ) max , it has the following Bayesian regret bound. Theorem H.2. For the C 2 -TS (Algorithm 5) on an C 2 MAB-T problem satisfying 1-norm TPM bounded smoothness (Condition 4) with bounded smoothness constant C, we have the Bayesian regret bound BayesReg α,β (T ) ≤ 12C √ mKT ln T + 2Cm + log 2 T 18 ln T 0 + 4 · m · π 2 6 · δ (T ) max , . C 2 -OFU is described in Algorithm 6. Similar to OCIM-OFU, it requires an offline oracleÕ that takes the context S (t) and c i 's (ranges of µ i 's) as inputs and outputs an approximate solution S (t) . With such an oracle, C 2 -OFU has the following frequentist regret bounds.