Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization
Authors: Kaixuan Huang
Yu Wu
Xuezhou Zhang
Shenyinying Tu
Qingyun Wu
Mengdi Wang
Huazheng Wang
Venue: Submitted to ICLR 2023 (2023)
Keywords: influence maximization
reinforcement learning

Abstract: Online influence maximization aims to maximize the influence spread of a content in a social network with an unknown network model by selecting a few seed nodes. Recent studies followed a non-adaptive setting, where the seed nodes are selected before the start of the diffusion process and network parameters are updated when the diffusion stops. We consider an adaptive version of content-dependent online influence maximization problem where the seed nodes are sequentially activated based on real-time feedback. In this paper, we formulate the problem as an infinite-horizon discounted MDP under a linear diffusion process and present a model-based reinforcement learning solution. Our algorithm maintains a network model estimate and selects seed users adaptively, exploring the social network while improving the optimal policy optimistically. We establish $\widetilde O(\sqrt{T})$ regret bound for our algorithm. Empirical evaluations on synthetic and real-world networks demonstrate the efficiency of our algorithm. 

Under review as a conference paper at ICLR 2023
PROVABLY EFFICIENT REINFORCEMENT LEARNING FOR ONLINE ADAPTIVE INFLUENCE MAXIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Online influence maximization aims to maximize the influence spread of a content in a social network with unknown network model by selecting a few seed nodes. Recent studies followed a non-adaptive setting, where the seed nodes are selected before the start of the diffusion process and network parameters are updated when the diffusion stops. We consider an adaptive version of content-dependen online influence maximization problem where the seed nodes are sequentially activated based on real-time feedback. In this paper, we formulate the problem as an infinite-horizon discounted MDP under a linear diffusion process and present a model-based reinforcement learning solution. Our algorithm maintains a network model estimate and selects seed users adaptively, exploring the social network while improving the optimal policy optimistically. We establish ((VT) regret bound for our algorithm. Empirical evaluations on synthetic and real-world networks demonstrate the efficiency of our algorithm.
INTRODUCTION
Influence Maximization (IM) (Kempe al., 2003; Kitsak et al., 2010; Centola & Macy, 2007), motivated by real-world social-network applications such as viral marketing, has been extensively studied in the past decades. In viral marketing, marketer selects a of users (seed nodes) with significant influence for content promotion. These selected users are expected to influence their social network neighbors, and such influence will be propagated across the network. With limited seed nodes, the goal of IM is to maximize the information spread over the network. A typical IM formulation models the social network as a directed graph and the associated edge weights are the propagation probabilities across users. Influence propagation is commonly modeled by certain stochastic diffusion process, such as independent cascade (IC) model and linear threshold (LT) model (Kempe et al., 2003). A popular variant is topic-aware IM (Chen et al., 2015; 2016) where the activation probabilities are content-dependent and personalized, i.e., edge weights are different when propagating different contents.
Classical influence maximization solutions are studied in an offline setting, assuming activation probabilities are given (Kempe al., 2003; Chen et al., 2009; 2010). However, this information may not be fully observable in many real-world applications. Online influence maximization (Chen et al., 2013; Wen et al., 2017; Vaswani al., 2017) has recently attracted significant attention tackle this problem, where an agent learns the activation probabilities by repeatedly interacting with the network. Most existing works on online influence maximization are formulated bandits problem making a non non-adaprive batch decision: at each round, the seed nodes are computed prior to the diffusion process by balancing exploring the unknown network and maximizing the influence spread; the agent observes either edge-level (Chen et al., 2013; Wen et al., 2017; Wu et al., 2019) or node-level (Vaswani et al., 2017; Li et al., 2020) activations when the diffusion finishes and updates its model. Combinatorial multi-armed bandits (Chen et al., 2013; Wang & Chen, 2017) and combinatorial linear bandits (Wen et al., 2017; Wu et al., 2019) algorithms have been proposed as solutions, where most works follow independent cascade model with edge-level feedback.
multi-armed
In contrast to the non-adaptive setting, adaptive influence maximization allows the agent to select seed nodes in sequential manner after observing partial diffusion results (Golovin & Krause, 2011; 1; Tong et al., 2016; Peng & Chen, 2019). The agent can achieve a higher influence spread since the decision adapts to the real-time feedback of diffusion. In viral marketing, the agent could observe

---

Under review as a conference paper at ICLR 2023
partial diffusion feedback from the customer and adjust the campaign for the rest of budgets based on current diffusion state. Unfortunately, online influence maximization in an adaptive setting is under-explored. Previous bandit-based solutions cannot be applied because the decisions of bandit algorithms are independent of the network state.
In this paper, we study the content-dependen online adaptive influence maximization problem: at each round, the agent selects a user-content pair to activate based on current network state, observes the immediate diffusion feedback, and updates its policy in real-time. The network's s actívation probabilities are content-dependent and are unknown to the agent. The agent's goal is to maximize the total influence spread. We formulate this problem as an infinite-horizon discounted Markov decision process (MDP). where the state is users' current activation status under different contents (user-content pairs), an action is to pick user-content pair as the new seed, and the total reward is the discounted sum of active user counts. Specifically, we study the problem under the independent cascade model with node-level feedback. Similar to combinatorial linear bandits (Wen al., 2017; Vaswani et al., 2017). we formulate a tensor network diffusion process where activation probabilities are assumed to be linear with respect to both user and content features. To tackle the problem of node-level feedback, we propose Bernoulli independent cascade model, linear approximation to the classic IC model which requires edge-level feedback to learn.
We propose model-based reinforcement learning (RL) algorithm to learn the optimal adaptive policy, Our approach builds on prior work of bandit-based influence maximization algorithms (Chen et al., 2013; Wen et al., 2017; Wu al., 2019) and has the following distinct features: (1) Our adaptive IM policy makes decisions and updates policy on the fly, without waiting till the end of diffusion process; (2) Our algorithm takes into consideration real-time feedback from the network, thus approaching a dynamic-optimal policy and outprforming bandit-based static-optimal solutions; (3) Our algorithm learns from node-level feedback, which greatly relaxes the common edge-level feedback assumption in previous works with IC model; (4) Our policy can handle content content-dependent networks and select the best content for the right user for the campaign; (5) To improve computation efficiency, we adopt the slow switching strategy (Abbasi-Yadkori Yadkori et al., 2011) 1) that only update model parameter for (dd log times, where is the feature space dimension. Our contributions are summarized as follows:
We propose linear tensor diffusion model for content propagation in social networks and formulate the problem as dulinite-horizon discounted MDP.
We propose a censor-regressonn baaeed RL influence maximization algorithm with optimistic plan- ning that learns an adaptive policy from node-level feedback, which selects the content and next seed user based current state of the network.
We proved a Odd/T/A + VdN regret of our algorithm, where T' is the total rounds, N is the number of users, K is the number of contents, A is the coefficient for diffusion decay, d is the dimension related to user and content feature. To our best knowledge, this the first sublinear regret bound for online adaptive influence maximization.
We empirically validated on synthetic and real-world social networks that our algorithm explores the unknown network more thoroughly than conventional bandit methods, achieving larger influence spread.
Related Works. The classical works on (offline) influence maximization (Kempe et al., 2003; Chen al., 2009; 2010) assume the network model, i.e., the activation probabilities, is known to the agent and the goal is to maximize the influence spread, i.e., total number of activated users. IM has been studied in a non-adaptive setting where the agent chooses the seed nodes before the diffusion starts (Kempe et al., 2003; Chen et al., 2009; 2010; Bourigault et al., 2016; Netrapalli & Sanghavi, 2012: Saito et al., 2008), or an adaptive setting where the agent sequentially selects the seed nodes adaptive to current diffusion results (Golovin & Krause, 2011: Tong et al., 2016; Han et al., 2018; Peng & Chen, 2019; Tong& & Wang, 2020). Online influence maximization (Chen al., 2013; 2015; Lei et al., 2015; Lugosi et al., 2019; Perrault et al., 2020; Zuo et al., 2022) is proposed to learn network model while selecting seed nodes in the non-adaptive setting. Existing works on online IM studies mostly follow IC model and edge-level feedback (Chen et al., 2013; Wang & Chen, 2017: Wen et al., 2017; Vaswani et al., 2017; 7 Lugosi et al., 2019). Chen et al. (2013) and Wang & Chen (2017) formulated the online IM problem as combinatorial bandits problem and proposed combinatorial upper confidence
'6)-) ignores all logarithmic terms.
2

---

Under review as a conference paper at ICLR 2023
bound (CUCB) algorithm to estimate the activation probabilities of edges in a tabular manner. Wen et al. (2017) assumed a linear parameterization on each edge with known edge features and proposed linear bandits- based solution. Our paper is the first to consider online influence maximization in the adaptive setting and formulate it as an RL problem. We also can handle the more challenging node-level feedback. Some recent works also explored settings beyond IC model and edge-level feedback. Li et al. (2020) studied online IM with linear threshold model, and proposed a linear bandits-based solution to model the linearity in LT model for node-level feedback. We also leveraged the linearity in diffusion model to handle node-level feedback similar to Li et al. (2020) but for IC model. Vaswani et al. (2017) considered diffusion mooell-nddeenneen setting using heuristic objective function, but without theoretical guarantee of the heuristic. Olkhovskaya et al. (2018) studied JCB-based algorithm for node-level feedback, but their algorithm designed only for certain random graph models such as stochastic block models and Chung-Lu models.
Our analysis is related to regret analysis of model-based reinforcement learning, which have been studied in various settings such tabular MDP (Auer et al., 2008), linear/kernel MDP (Yang & Wang, 2020; Yang et al., 2020), factored MDP (Rosenberg & Mansour, 2021), general model class (Ayoub al., 2020), etc. We provide a first problem- sepeeffi--peieeeeeeee analysis for influence maximization. Our analysis differs from existing regret analysis a couple of ways. First, although we focus on a linear model for network diffusion, the state-to-state transition of the IM is highly nonlinear, thus the value and Q functions for IM do not admit a linear model and invalidate linear/kernel MDP approaches. Second, due to the nature of network diffusion process, the state and its value can grow unboundedly for large networks, causing unbounded variance at the same time. Our analysis is specially tailored to such growth process over large networks and derive regret bound by focusing a high probability event where states stay bounded. To our best knowledge, this is first IM-specffic regret analysis for controlling unbounded growth process over large networks.
2 PROBLEM FORMULATION
We present a tensor network diffusion process to model user feature-dependent content feature- dependent network propagation. Our goal is to both select seed users and customize contents for influence maximization. Further, we formulate IM into an RL problem to enable much more delicate control of the network diffusion process based on real-time feedback.
2.1 TENSOR NETWORK DIFFUSION PROCESS
Consider a social network of N users, where the network structure may be hidden. Let there be K choices of contents. Let S1,A {0, 1} denote the status of user-content pair, i.e., 81,k 1 if user is actively tweeting content k. The full state of the network is denoted by E {0, N a binary matrix. We focus on the asymptotic regime of large networks, i.e., N can be arbitrarily We assume that each content be propagated from
large even N users following an independent network diffusion process.
multiple
Assumption (Bernoulli Independent Cascade Model). Let s' be the next state. For each E [K]. assume there is an underlying connectivity matrix A E RRxx such that
P(
1|s)
Σ A A JEIN]
And we assume s 's are independent conditioned
Here A measures the level of influence user j has over user i for the k-th content. Therefore, the aggregate "influence" received by user i is E, Sj.. We model the status of user as Bernoulli variable, which is parameterized by the aggregate "influence" received by user i.
Our model closely related to the independent cascade model (Kempe et al., 2003). In IC model, the activation probability takes of the form P( 1|s) 1 - 11 A s.,)). ). A limitation is that efficient estimation of IC model requires leve- observations (Chen al., 2013; Wang & Chen, 2017). Assumption 1 can be viewed as an lincarized approximation to IC model, i.c. Σ3 Ai when all the A values are tiny (see Assumption 3). In
1 [1 A s5,k)
3

---

Under review as a conference paper at ICLR 2023
Appendix F, extend the assumption the generalized linear setting and establish the regret bound for our algorithm.
Consider parameterized network diffusion model based user features and content features, Let the i-th user associated with a user feature vector 2 E Rd for all E [M. Let the k-th content be associated with content feature 02 R for all l [K]. We assume that the influence is linear with respect to both user and content feature.
Assumption
Deeeedet Linear Tensor Model). There exists a d1 x di x d2 tensor T* [dd da such that
A = (T, 0 8 0g),
where & denotes outer product and (,) denotes inner product.
Note that this is different from the linear MDP model commonly studied the theoretical RL literature (Jin et al., 2020). We focus on large networks where N can be arbitrarily large. We also assume each individual user has bounded influence over its neighbors and the diffusion process has a natural decay property.
Assumption 3 (Uniform transition probability upper bound). There exists constant C > 0 such that || S C.
Assumption 4 (Diffusion decay). There exists A > 0 such that ΣVENN A S 1- - A for all j.
Assumption 4 says that influence from any seed user has discounting nature; without this assumption, some seed user may have infinitellnn influence and make the diffusion process unbounded. This assumption also implies that, the "influence" of any seed user-content pair would last O(1/A) time steps on average.
2.2 REINFORCEMEN LEARNING MODEL
We formulate the influence maximization problem as an anfinit-hhoiizn discounted MDP. Define the state space as S = {0, 1) ||N* where 1 refers to activated user-content pair. At each timestep. N
the agent observes the current network state and picks an action a E A == [N] [K] to activate one user-content pair. Let be the post-action state, i.e., 8, = 1.- Then the state of network transitions following the network diffusion process, i.c., Assumptions 1,2. Since users are activated independently from one another, the state-transition law of the MDP admits product structure:
P(s'(s,a)
II P(s..lssa). sE[N],KE[K]
At each state-action pair, the agent receives a reward r(s,a) = Ei S1, measuring the amount of influence over the network. For examples, we 0i = 1, then we have r(s, a) = || which counts the number of active users. Without lost of generality, we assume V1 S 1. Let π S - A be a decision policy. We measure the value of policy π at state as a cumulative sum of discounted rewards
(*(()= E
rss, a:)
Recall Assumption 4 that the influence of any action lasts 1/A time steps. Thus, natural choice of the discount factor to be & = o(A). Finally, the policy optimization problem is to find π argmax, (*(s).
Relation between Discounted MDP and Bandit IM model. The discounted MDP formulation differs from the bandit IM optimization in two ways. (1) Our policy dynamic and makes state- dependent decisions, while the bandit approach would make batch of decisions only at the beginning of the diffusion process; (2) In both cases, the optimization objectives are sums of total influences from all seed users. The difference lies in how measure the per-seed influence. In IM bandit, the per-seed influence is a cumulative sum calculated after the diffusion process is over. In our formulation, the per-seed influence is cumulative r-discounted sum of rewards from this seed's descendants. If we choose = 1 - of ()), these values differ by only o(1) and we can make the difference arbitrarily small.
4

---

Under review as a conference paper at ICLR 2023
3 MODEL-BASED RL FOR INFLUENCE MAXIMIZATION (MORIMA)
To reduce the statistical complexity, we adopt model-based RL approach for exploring the unknown network and learning the optimal policy. Our approach alternates between model estimation and policy update. Our algorithm calculates a bonus function based on the collected data and and add to the reward, which dynamically trades-off between exploitation and exploration. We also adopt slow switching technique to reduce computational burden.
Tensor ridge regression for model estimate. Under the linear tensor model (Assumption 2), we can use tensor ridge regression perform model- RL. This reduces the statistical complexity since the dimension of the unknown parameter is smaller. Furthermore, this approach only requires node-level feedback, While previous bandits approaches for IC model require edge-level feedback (Chen et al., 2013; Wen et al., 2017; Wu et al., 2019).
Specifically, let & be the altered state after applying action a. Observe that, conditioned on (s, a). the random variable s', satisfies a linear relation:
E S
8, a) = Ej A. (8a) (T. (E, (Su)3k) 0%)
Denote for short 01,x(5,a) a) = x, @ (E zj (Ba)jik) 8 00g E Rdidida, and o = (s, a.). At
time t, after observing the history ($1, 01....,......................... St-1, a1-1: st), we estimate the tensor model by
1-
Te argmin ΣΣΣ9N (T, (T,,) (s++1)xx) A11TI12
(2)
where || is calculated by vectorizing T. This allows an analytical solution:
(3)
where
1-1 K N
1-1 K N
XI+ ΣΣΣ T (T)
BI-1 -1=>E>> r=1
The
(87+1)i,
(4)
Notice that the sizes of the covariance matrix Σ,-1 and the right-hand-See term B are d and d, respectively, where d = d'd22 < N.
Optimistic Plamning with truncated-reward model. To avoid the worst-case O(NK) reward, we identify high probability upper bound A for the rewards and truncate the reward as F(s a) = min(r(s, a), A). Then based on the ridge regression estimation Te. we add bonus term by (r a) to the truncated reward F and solve for an optimistic Q-function 27, (s, a) using the model estimate.
Specifically, we can choose A
- log(4NKT*). For Tr. we define the reward bonus
K (1 B (1100.16s
A
ae( = 1 1- 1
(5)
where we use the notation A = min (1, and
8, ( 24 Ca/(NK) d log(1 NKL*t/(d))) + +4) log(8N2 VAIT*>
(6)
with L being upper bound of || and d = dfd2..
This choice of Br ensures with high probability. Q7 F4b (s, a) is an upper bound of 2* (s, a). which the optimal Q-function for ground-truth transition with truncated-reward, We calculate the optimal truncated Q-function Q 7+b. (s,a) using value iteration with truncation (Algorithm 2).
5

---

Under review as a conference paper at ICLR 2023
Slow switching. To reduce computation overhead, we adopt slow switching technique from bandit and RL literatures (Abbasi- Yadkori et al., 2011; Zhou et al., 2021b). The idea is that we only update model and policy when enough new data has been collected, via checking the covariance matrix. Specifically, say the most recent switching happens at time i, we choose to switch at time only if
det (ctr-E)1) dct
After switching, we calculate the optimistic Q-function Qr Q7 (s. Then we pick actions greedily using Qi i.e., argmax, (s, a), until the next switching.
Algorithm Model-based RL for Influence Maximization (MORIMA) Initialize Σ₁ = AI, B1 0. = dct(En).
2: Calculate Ti and bı (s, a) and compute Q1 = Q7 7,741 (8,
3: Take the greedy action with respect to Qı: a1 = argmax, (8),
4: / 2 do
5: Calculate -, and B according Eqn. (4).
6: if' det(E >> 2Z then
7:
Calculate To and (s(s, a) according Equ. (3) and Eqn. (5). Compute the optimistic Q-function Q: = Q7..40. (s,a) (Algorithm 2).
8:
9:
Set = dct(E
10:
else
11: Set Q. = Qt-1.
12:
end if
13: Take the greedy action with respect to Q:: 0z = argmax, Qe(se: a).
end for
Algorithm 2 Truncated Value Iteration
1: Input: parameter T, reward a(s, bonus term b(s, a).
2: Initialize Q(s, a) A
1---
3: while Not Converged do
3: Q(s, a) + min - + b(s,a) + +BBy (1s.a) max Q(s',a'))
4: end while
5: Return: Optimistic Q function Q(s.a).
Full algorithm. We put together the pieces and present the full Algorithm 1. The algorithm makes only (og(T()) model updates and policy updates until time T. Each model update can be done efficiently using least square regression. Policy updates require solving a planning problem which can be combinatorially hard. In practice, one can solve the planning problem using approximate dynamic programming (Powell, 2007) Monte-Carlo Tree Search (MCTS) methods (Browne et al., 2012), and we will use a two-step lookahead scheme in our experiments. For theoretical analysis, we assume access planning oracle that is able to find the optimal policy with respect to known model F. Relaxing such assumption to an approximated planning oracle can be also be done with minor algorithmic and analysis modifications.
REGRET ANALYSIS
In this section, we provide regret analysis for Algorithm 1. We define the regret for the infinite-horizon discounted MDP as in (Zhou et al., 2021b).
Definition 1. For any possibly non-stationary policy n, the infinite-horizon discounted regret is defined as
T
Regret(T) = Σ D.. where A, = V*(a)) V*+

---

Under review as a conference paper at ICLR 2023
where V is the optimal value function, and Vi is defined
(+) = E
(r ((45)181 , ,
==0
Now present our main theorem.
Theorem 2. Let Assumptions 1-4 hold. With probability at least 1 6, Algorithm 1 satisfies the following regret upper bound:
Regret (T) 0 12(111) (dVC/A+vaNT) vT) + (olylog(T)-tenme)
where d = dim(T))= = dld2.
We see that the dominant term the regret is ( --(1-)} (dvC/A + VaNK) .T) Notice that the worst-case reward would scale with NK, while we managed to reduce the scaling of the regret to 1/A2.
4.1
PROOF SKETCH OF THEOREM 2
Next, we provide a proof sketch and defer the complete proof Appendix C.
Proof. High probability upper bounds for the size of active user-content pairs. We utilize the diffusion decay assumption (Assumption 4) provide high probability upper bound on the number of active user-content pairs. We show that for any policy т, with probability at least 1 - we have for all
| 11 S O 1
4
log
A
P
We see that although we have in total N user-content pairs, the number active ones is constrained by constant intrinsic to the network diffusion dynamics.
Sharper bounds for the confidence region. We derive a batched version of Bernstein-ty typp self-normalized bounds from (Zhou al., 2021b) and show that with high probability for all t, IIT. T |x_,, I 3,, where 8n be chosen as Ölovd + 1) and o² is the upper bound of var((>++1)i,t Ae, ar). Combing Eqn. (7) and Assumption 3, we have
C var((942)).l$1110) ar) < ((((5+4))als)) ail A S NK N (11sell2 + +1) S Ō N
Then 3, = Öly normalzoma bounds.
/ 1), which improves upon 3 Ö(Vd) given by the sub-Gaussian type NK
dc
Surrogate regret of the truncated-rewart model. Since we essentially
algorithm against
the truncated-reward model, we define the surrogate regret as Regret(T) = - (TT(s)) (s:)). where 5 and V computed using the truncated reward F(s, a) minfr(s, a). A}. By Eqn. (7), with probability at least 1 1/(2N under any policy, we have r(sr, 0z) < || < A =
(x+)
( for all /. < T. This means with high probability we have r(st, 0z) F(st; a+) and hence the true regret and the surrogate regret is similar. Specifically, we will show Regret(T)) < Regret(T) 1/(1 77)
Bonus term. Let [P(s"|s, a) be the true transition probability and ((s'[s, a) be the empirical estimate.
As typical result in MDP theory, we require b(s, a) 2 7olV/ [|I((1ss, a) - P-lss, a)Il I to ensure optimism. We exploit the fact that P(s [s, a) and P(-|s, a) is factorized, i.c., (P-l
S/ @
(.,((+s,,) and F(-ss, a) = S & P. P. (-s, a). which stem from the independence assumption (Assumption 1). This gives us |P(-|s, a) P(Jss a)]l < Ei EK (+).. (P,, a)ll- Notice that (-]s, a) is a Bernoulli distribution, then by Assumption
have | a)
P., (-1s, a)]l < 2(1 A (T T, (s. Therefore, the bonus term can be chosen as Eqn. (5) and ensure optimism each time.
7

---

Under review as a conference paper at ICLR 2023
Regret decomposition. We have the following regret decomposition for the surrogate regret.
(Tg S 0 ( bi (sc.
2
+ 1 3
A (1-rM)) m)]
T log
where M = (T) is the total number of switches and we will show that M = (dd.. Then the dominant term of the regret
7)2 bt, (st, ar) = =0 (1-))))2) Br ΣΣΣ L a.),,,
1
<ō (1 >))ー)) BT OVANKK MNK).
1
where la denotes the last switch up to time I, and the last inequality follows from a variant of Elliptical Potential Lemma. Plug in the choice of 3r and we derive the result.
4.2 EXTENSION TO GENERALIZED LINEAR INDEPENDENT CASCADE MODELS
In this subsection, briefly show how to extend our algorithm and regret bound to generalized linear IC models. The details can found Appendix F.
Assumption (Generalized Linear Independent Cascade (GLIC) Model), Let s' be the next state. For each k E [K], we assume there is an underlying connectivity matrix A E IR=xn such that
P( = 1|s) 1 1 Ai)
(8)
where μ
R satisfies p(0) 0 and 1/15 pl S for some 1. And we assume s are independent conditioned on 8.
Given Assumption there are two major differences extending MORIMA to GLIC models: (1) new objective of tensor model estimation under GLM, which does not have analytical solutions; and (2) new optimistic planning. which analyzed following new tensor estimate. We have the following regret bound for MORIMA under GLIC.
Theorem 3.
Let Assumption 5, Assumptions 2-4 hold. With probability at least 1 5, Algorithm / satisfies the following regret upper bound:
Regret (T) < 2 12(1- (dVC/A+ .VT polylog(TT)
where d = dim(T.) = dfd2.
EXPERIMENTS
We experiment with MORIMA (Algorithm for influence maximization both synthetic networks and large-scale Twitter social network.
Synthetic networks. We run benchmark experiments on two synthetic networks. The first cascade network (see Appendix E Figure 2a), consisting of N 300 users and K = 4 content types, is constructed bear hierarchical structure with users with high, medium, and low influences, with 9-dimensional user feature and 3-dimensional content features (see Appendix E for details). The second network is constructed to have a star-like structure, consisting of N = 70 users of various influence levels and K contents (see AppendixE Figure2b for details). Experiment result of the first network is reported in Figure I(a), and result the second star network is reported in Appendix E Figure 3.
Twitter social network. We further conduct experiments using the Twitter Social Network dataset (Leskovec & Krevl, 2014), which represents real-world social networks. The dataset contains ~80k nodes and ~ million directed edges, where a directed edge (u, v) means the node u follows the node Twitter. We randomly sample multiple sub- sub-graphs from the Twitter network and construct K
8

---

Under review as a conference paper at ICLR 2023
1265
HORRIN
0553
PORRING withoree
7043
SOR/MA bnown
cumtlltive rewardd
0443
Clmulative
.003
2005
200
2003
300
timestep
timestep
(a) Synthetic cascade network (300 nodes) Figure 1: Real-time discounted sum of rewards of IM on synthetic and Twitter networks. Averaged results with 85% CI bands are included.
(b) Twitter network (1966 nodes)
networks corresponding to different topics/content types. For the sampled networks, we first pick out n1 nodes with most out-degrees and then include all their ε-hop neighbors, with n1 8, l 5. We construct a connectivity tensor over these networks by randomly drawing edge weights from [0, 0.1] and normalizing tensor row sums to 0.9. Next we apply non-negative Tucker decomposition (Kossaifi et al., 2019) to extract the Tensor core model T user features (of dimension dN = 10) and content features (of dimension d2 2). Thus, we have generated a large-scale topic-aware Twitter diffusion network with K 3 content types, N 1966 nodes, and 38023 edges for dynamic influence maximization.
Implementation and Baselines. Exactly solving for the optimal policy, even if the network is fully known, requires solving a combinatorially hard planning problem and is intractable. In our experiment, adopt the two-step lookahead approximate dynamic programming scheme (Powell, 2007) as the planning oracle for Algorithm of MORIMA. In the implementation of Algorithm 1, we s 0.9, À 1 for synthetic networks and X 0.01 for the Twitter network.
For comparison with MORIMA, we also test the following baselines: (i) the naive random policy that uniformly selects user-content pair to activate; (2) the IMLinUCB (Wen al., 2017) which is combinatorial linear bandits baseline that was originally designed for non-adaptive online IM. To make a fair comparison with the two-step lookahead oracle, we run IMLinUCB every timesteps and play the 2 selected actions spontancously, (3) MORIMA without slow switching, where we force the Q-function to be updated at each time step: (4) MORIMA with known A purely planning with a fully know model it would be performance upper bound of the reinforcement learning algorithm.
Results and analysis. We report the averaged discounted cumulative rewards and its empirical confidence region of our experiments in Figure 1, where each test is repeated on synthetic networks for 20 times and Twitter network for times. In Figure (a), we observe that the discounted sum of reward of MORIMA reaches the same level of the performance upper bound with true A in less than 100 rounds on synthetic network, showing that our algorithm can quickly explore the unknown network and learn to make optimal decisions. In Figure (b), observe that MORIMA can still match the performance of the planning oracle large real social network with thousands of users. Across all experiments, our reinforcement learning- based MORIMA significantly outperforms IMLinUCB because it can adaptively make decisions based on current state while IMLinUCB does not take state into consideration. Further, slow switching did not hurt the performance of MORIMA while greatly reducing the computation complexity from (T)) parameter updates to Odd log T).
6 CONCLUSION
In this paper, we study the problem of content-aware online adaptive influence maximization and formulate the problem as an hnfinite-hoiioon discount MDP. We propose MORIMA, a model-based reinforcement learning algorithm that learns optimal policy using only node-level feedback under the IC model. We provide OdvTT/A + VdNKT) regret bound for our algorithm, which is the first sublinear regret bound of online adaptive influence maximization problem. We empirically validated the effectiveness of our algorithm on synthetic and real-world social networks.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp- 463-474. PMLR, 2020.
Simon Bourigault, Sylvain Lamprier, and Patrick Gallinari. Representation learning for information diffusion through social networks: embedded cascade model. In Proceedings of the 9th ACM WSDM, pp. 573-582, ACM, 2016.
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener. Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012.
Damon Centola and Michael Macy, Complex contagions and the weakness long ties, American journal of Sociology, 11 1133):702-734, 2007.
Shuo Chen, Ju Fan, Guoliang Li, Jianhua Feng, Kian-lee Tan, and Jinhui Tang. Online topic-aware influence maximization. Proceedings of the VLDB Endowment, 8(6):666-677, 2015.
Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD, pp. 199-208. ACM, 2009.
Wei Chen, Chi Wang, and Yajun Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD, pp. 1029-1038. ACM, 2010.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi multi-armed bandit: General framework and applications. ICML., pp. 151-159, 2013.
Wei Chen, Tian Lin, and Cheng Yang. Real-time topic-aware influence maximization using prepro-
cessing. Computational social networks, 3(1):1-19, 2016.
Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486, 2011.
Kai Han, Keke Huang, Xiaokui Xiao, Jing Tang, Aixin Sun, and Xueyan Tang. Efficient algorithms for adaptive influence maximization. Proceedings of the VLDB Endowment, 10200 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through social network. Proceedings of the ninth ACM SIGKDD, pp. 137-146. ACM, 2003.
Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eugene Stanley, and Hernán Makse. Identification of influential spreaders in complex networks. Nature physics, 6(1 1)88 2010.
Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, and Maja Pantic. Tensorly: Tensor learning in python. Journal of Machine Learning Research (JMIR). 20(26), 2019.
Siyu Lei, Silviu Maniu, Luyi Mo, Reynold Cheng, and Pierre Senellart. Online influence maximiza- tion. In Proceedings of the 21th ACM SIGKDD, pp. 645-654. ACM, 2015.
10

---

Under review as a conference paper at ICLR 2023
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: //snap. stanford. / June 2014.
Shuai Li, Fang Kong, Kejie Tang, Qizhi Li, and Wei Chen. Online influence maximization under
linear threshold model. Advances in Neural Information Processing Systems, 33:1192-1204, 2020.
Gábor Lugosi, Gergely Neu, and Julia Olkhovskaya. Online influence maximization with local observations. In Algorithmic Learning Theory, pp. 557-580. PMLR, 2019.
Praneeth Netrapalli and Sujay Sanghavi. Learning the graph of epidemic cascades. SIGMETRICS Perform. Eval. Rev. 40(1) (12)::1122222 June 2012. ISSN 0163-5999, doi: (1145/231885.225477777
Julia Olkhovskaya, Gergely Neu, and Gábor Lugosi. Online influence maximization with local observations, 2018.
Binghui Peng and Wei Chen. Adaptive influence maximization with myopic feedback. Advances in Neural Information Processing Systems, 32, 2019.
Pierre Perrault, Jennifer Healey, Zheng Wen, and Michal Valko. Budgeted online influence maxi- mization. In International Conference on Machine Learning, pp. 7620-7631. PMLR, 2020.
Warren B Powell. Approximate Dynamic Programming: Solving the curses of dimensionalityy volume 703. John Wiley & Sons, 2007.
Aviv Rosenberg and Yishay Mansour. Oracle-efficient regret minimization in factored mdps with unknown structure. Advances in Neural Information Processing Systems, 34:1 14:11198-1119, 2021.
Kazumi Saito, Ryohei Nakano, and Masahiro Kimura. Prediction of information diffusion probabili- ties for independent cascade model. In Proceedings of the 12th KES, pp. 67-75, Berlin, Heidelherg, 2008. Springer- Verlag. ISBN 118-3-540-85566-- doi: 10.1007/978-3-5500
Guangmo Tong and Ruiqi Wang. On adaptive influence maximization under general feedback models. IEEE Transactions on Emerging Topics in Computing, 2020.
Guangmo Tong, Weili Wu, Shaojie Tang, and Ding- -hu Du. Adaptive influence maximization in dynamic social networks. JEFE/ACM Transactions on Networking, 25(1):112-125 2016.
Sharan Vaswani, Branislav Kveton, Zheng Wen, Mohammad Ghavamzadeh, Laks VS Lakshmanan, and Mark Schmidt. Model-independent online learning for influence maximization. In ICML, pp. 3530-3539, 2017.
Qinshi Wang and Wei Chen. Improving regret bounds for combinatorial seni-bandits with proba- bilistically triggered arms and its applications. In NIPS, pp. 1161-1171, 2017.
Zheng Wen, Branislav Kveton, Michal Valko, and Sharan Vaswani. Online influence maximization under independent cascade model with semi-handit feedback. In NIPS, pp. 3022-3032, 2017.
Qingyun Wu. Zhige Li, Huazheng Wang, Wei Chen, and Hongning Wang. Factorization bandits for online influence maximization. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 636-646, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 10746-10756. PMLR, 2020.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin (eds.). Advances in Neural Information Processing Systems, volume 33, pp. 13903-13916. Curran Asso- ngs neurips. cc. Seceeeee44eeeppppee pdf.
ciates, Inc., 2020. URL 9fa04f877 (11187999119822222222e29
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. Conference on Learning Theory, pp. 1532-4576.. PMLR, 2021a.
11

---

Under review as a conference paper at ICLR 2023
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pp. 12793-12800 PMLR. 2021b.
Jinhang Zuo, Xutong Liu, Carlee Joe-Wong, John CS Lui, and Wei Chen. Online competitive influence maximization. In International Conference on Artificial Intelligence and Statistics, pp. 11472- 11502. PMLR, 2022.
12

---

Under review as a conference paper at ICLR 2023
A LIMITATIONS AND BROADER IMPACT
As a common limitation for all previous work on influence maximization, it is computationally infeasible find the exact optimal policy, especially when applied real-world networks with millions of nodes. Therefore, the scalability of our proposed algorithm comes at the cost of using approximations. Given certain computational budget constraint, the optimality of the policy needs to be traded-off towards affordable computational and storage complexity. In our experiments, we use Monte- Carlo methods, parallel computation and randomized methods for approximating the optimal policies. While the real-world social network graph in our experiment in the same scale as the graphs used in previous online IM studies, scaling up to larger network is an important future work of ours.
search (dynamic programming)
In the paper, we propose a model-based RL algorithm to learn the optimal policy for online adaptive influence maximization problems, which can be applied to advertisements for promoting beneficial ideas, new knowledge, and innovative products across social networks. However, such algorithms might be exploited to propagate fake news rumors through the social networks. Addressing the ethical concerns also needs to be considered in future work.
B A SHARPER BOUND FOR THE CONFIDENCE REGION
B.1 MAIN LEMMA
Lemma B.1 (Confidence Region). Let Assumptions 1-4 hold. With probability least have for all t 2 1,
l - 1T-111 SB..
where
B: = 24 VC/(NK) d log(1 NKL + +4) 1og(8N2K2P/00 + VAI/T"
and L = sup 1l,2, d = dfd2.
Before the proof of Lemma B.I, we introduce two lemmas below:
Lemma B.2 (High probability bounds for the number of active user-content pairs). Let Assumptions 1- 4 hold. For any possibly non-stationary policy v, with probability at least 1 - 8, we have for all t 1,
2t 2 log A A
|sc/11 -
1).
5
Lemma B.3 (Bernstein-type self-normalized bound, batched version (Zhou et al., 2021a)). Let (F.)g= be a filtration, {2), 12 be a stochastic process such that æ Rd is Fi- measurable and vi R is Fen--meauurabl. Assume that conditioned on Fr, (ub, vit) independent, and
WA < R. = a4)
varl
| S L,
then with probability least 1 - 8, the following holds simultaneously for all t > 1:
- S 3ΣΣ - (T" (T.)))) S.B VAlIT 1|2.
where T. = 2i B,-1, - - Σ (x+) B:-1= Em Et=l vivi and
= + mLL3//(X)) log(Am²² + 4R logl (log((4m22')) (22 + vXITT"12.
proof of Lemma B.I. I. We use Lemma B.3 for batched stochastic process (0l (8.41),,a). Notice that we can choose o² to be the upper bound of var[(sr+) ) (8,, arJ. and
C NK
C
var var[(s 1) (se, ar] S B[(s Se, ar] = Σ A (Sta S
Σ (taa))i S NK (1]s:]1++)).
13

---

Under review as a conference paper at ICLR 2023
where we used the assumption that A S 1 8/2, for all t,
C NK
By Lemma B.2, we have with probability at least
2 2
4t2
||+||| - -
log
1).
A
A
8
Therefore, when the above inequalities hold, we have
C'
2
4t
C
4t
var[(st+1)<als; asl - NK A
log
+ +))+1)
3 log
NK
8
By Lemma B.3 with m NK, R 1, and 0²
C
(3/
log 412
5. have
NK
24 8. V CC/(K)) d log (1 -TTHH///CD0000007722200200000000
which is smaller than the result stated in the lemma.
B.2 DEFERRED PROOFS SUBSECTION B.1
proof of Lemma B.2. First, we bound the expectation of ||sell2. By the transition, we have
((s arl = Σ A t (stae)
Therefore,
Bll [s) Σ A. (sbar)))
i.jik
Recall that we have assumed that for any content &s and any user j.
Σ 51-A.
Then we have
B[]ls++|ll|es arl S (1- (1-4) A) Σ
(sta )i. =(1 - -]]](assta))) 1l S (1- A)[l=el + +1,
(9)
J.k
where the last inequality holds since the action alters most entry of the state.
Next, notice that conditioned on (st, az). || is the summation of NK independent Bernoulli random variables. By Bernstein inequality, have with probability at least 1- 8c.
I + log 8c"
1
|| |s411ll |[]|s41lll|s,, ail s 2(
var[(s(41)s. ad] log 8, 2.k
Since the variance of a Bernoulli random variable is bounded by its expectation, we have
+ log 8, || [[[|st ai] s 2(v B|||stalll 1as oz) log 8,
Therefore, by Equation (9), we have
||8-1111 |1| < (1 ([[+=]]] 1) + 2 (][ + 1 log 1
1
+0loog
2 log
5c
5z
1
< (1 - ([]ss: +
{||>a|1 + +) (1 - A)
22oog
2
be
8,
2 log &
= (1 -
+ +1) + A
where we used at + b/t 2 2v ab for the last inequality.
Finally, set d, 37. that Σ. 6 and take union bound over all 1. By solving the recursion, we have with probability at least 1-5, 5,
2 2
2t
|| |1
log
+ 1)
A
A
for all i. > 1.
14

---

Under review as a conference paper at ICLR 2023
proof of Lemma B.3. We consider "serialized" stochastic process. Let Gr,s oFii Ve ye.................. ...., vi )
When $ Σ m, we have G1, S 91,411 while when i = m + 1, we have gr
(FFt (Ft.y/..... ........... - 91+1,1 Fit1- Then we know that
91,1 C -122 C C 91,m - 22, 22,2 -... S F2.m C... E... 9t,1 S 91, C
S 9t.
filtration. Clearly have st is Gr, mee-muaura and y is meeassuaarr.. By the conditional independence assumption, we also have
I =a Vi : =a v.lFi-
Therefore, by Theorem 4.1 of Zhou al. (2021a), we have with probability least 6, for all t 2 1 and ..,, m.
| T T1s,, $ Be,b.
and
MΣ=#!- (T - +
ot (vi (T" x()1) 177
SB.
VAITT
r=lj=1
where
i-1 m
1-1 m
Tr, = -1 Bi,is Ltj XI +
Σ
o x
Σ [T!) B =
-ΣΣ j=
+ Σ s..e
r=
j=1
j=1
and
Br, So y + (412((()))))))) lo(((//0) + 4R Aolog(41)) + V/ITT
4= 4=m(L 1) +
Then the result of Lemma B.3 follows by setting = m.
C PROOF OF THEOREM 2
Additional Notation.
Let t and for 2 the next switching time fs+1 is recursively defined
to+1 min(t] det(E..1) > det(E:,-1))
Denote the set of switching times by W = (2... Jas) where M is the total number of switches.
We have 1 t1 t2 <...... tM < T fM+1. We slightly abuse the notation and use to denote the last switch up to time i..., t, S t < fs+1. Then by slow switching we mean Q2 = 2 F+b.,"
Recall the definition of the regrets
T
Regret (T) = ((v VT((s)), Regret
(s))),
where V, Regret are defined with the original untruncated model and V, Regret are defined with the truncated-reward model.
Key Lemmas. Before the proof of Theorem 2, we introduce several key lemmas.
Lemma C.1 (optimism). Let Assumptions 1-4 hold. Set the bonus term to be
2A K
be(s,a) = 1 ΣΣ (1A
Then with probability at least we have the optimistic condition (2 a) S Qe(s, o) holds for all t 2 L.
Furthermore, we have for any V (s) such that 0 V(s) < A/(1 7)),
7BBere((r Ea V(8') S (s)
15

---

Under review as a conference paper at ICLR 2023
Lemma C.2 (surrogate regret). Let Assumptions 1-4 hold. Assume that T log(1/1) log(2.VTT) For any policy 9, we have the following connection of the regrets of the two MDPs.
1
Regret (T) I Regret +
1-7
Lemma C.3 (regret decomposition (Zhou et al., 2021b)). Let Assumptions 1-4 hold. Assume at each time step I, the results of Lemma C.I holds. Then with probability at least 1 - 6, we have the following regret decomposition
2yA V
T 1log g + (21/(11-))) -7) + ET)
Regret(T) 5
be, (St, az) +
where ET is the switching error
T FT Σ
Vi(s41) Ve+1(S++1)
Lemma C.4 (bounding the number of switches). Let Assumptions 1-4 hold. The total number of the switches M incurred by Algorithm / is bounded as
1
d + O4NNTE +
M
dlog
log2
d
where L. sup 1l2
Next we state the proof of Theorem 2.
proof of Theorem Combing Lemma C. Lemma C.2, and Lemma C.3, we have with probability at least 1 - 25, when Tlog(1 /7) 2 1og(2NKT),
1
T
2
I x Toog + + (22/2111111) - ())]] + --
Regret (T) v
by (sc. or) + 1->
1=1
Next we provide an upper bound for Σr 1
b,, (st, at). By Lemma C. we know that
2yA
be, (3 ar) <
3T
(L (5. ) Σ
1 -
For any (i, k), define Σe,,, = Ex- 2 j=1 Σt1 (5 + + (0,() By the definition
that 1- = min(4] (E, > 2 det (2t, we have det ( S (eet(E,, Therefore,
when l, < 1x+1 1, have
del(E(,.)) < del(E,) < det det(E,,)1-2) < (
By Lemma D.4, this implies
(st,
S 22 at)1
16

---

Under review as a conference paper at ICLR 2023
Then we have
N K
aA 1 ( ,)
N K
Σ ΣΣ
(1 A ( an)
Σ ΣΣ
(1 A | (8t, an)1lxg;1
t+IEW == k=1
i= k=1
N K NKT E ΣΣ
S MNK+ +
A (1 a+) ) P2-n
E+ k=1
N K ΣΣ
& MNK +
2NKT Σ
(1 (8t an)
2+1GW 1= k=1
T N K 2NKT ΣΣΣ EESE
S MNK +
(IA (1)
dA + NKTL2
S MNK +
2N 2d
dd
where the last inequality follows from Lemma D.3. This implies
2 Σ by, (St. a.) - 1 7 3T (MNK+
dA + NKTI2
|ANK log
dA
Next we bound the switching error Er. Since there are total M switches, we know that there are at most M non-zero terms in the summation of Er. Then we have
ET Σ (V((5)))) - V1+1(8411) 1-7 M.
Plugging the result of Lemma C.4, we have E, = 0
Therefore, we have the final regret upper bound when T (og(1/n) 2 log(2NXT):
Regret(T) S Ō 1 >)² (dVC/A+ vT) (olylog(T)-termss,
where d = dimi(T) = d2d2. When Tlog(1/7) < log(2N the above inequality trivially holds.
C.I DEFERRED PROOFS
proof of Lemma C.I. For simplicity, define P7. which is the estimated transition distribu- tion obtained using T.. Notice that Ps,(-ls, a) is a Bernoulli distribution with success probability (T & a)), while (-,,(-ls, a) is Bernoulli distribution with success probability (Te, as) Therefore, we have
I a) - (-1s, a)ll s 2(1 A ATT -T,, (s,,
By Lemma B.I, with probability at least 6, we have || Talb., S Br for all 2 1. Then by Cauchy Inequality, the above term can be further bounded as
[PPu((lss,) - (-,,(-18, a)ll: s 2(1 A B I1r. (8,
By Lemma D.2, we have
[P a) [P--ss, a)ll1 &
Σ [IPP,o(-ls,) - Pr. 2 (1 8 -10 i.k
>
i.k
Then by Lemma D. know the desired result holds.
17

---

Under review as a conference paper at ICLR 2023
proof of Lemma C.2. Define x² the optimal policy under the original model. Then have
- (s:) V
V (s:) V= (st) + V (s+))) - (st)
< V= (st)
x
DC Σ
E
(s) =
ET
(Ts; 81 81)
where the inequality holds because V (st) is the optimal V-function with respect to the truncated- reward model.
Notice that by Lemma B.2 with óu = 1/(2NXT), we know that for policy x², with probability at least 1 80. we have ||s: I A ( for all 1 S i T. Therefore, with probability at least 1 - -o. r(8;; as) = F(8e, ai) for all < i i T. Then
(*())) V' (8)) = E=T
- (r(si, az) (ss. =8t
1 (r(s) as)) =
E
(r(ss,), Fisi, 8t.
i=T41
NK + NK 7T
< (1 - 60) 0+ 60
1 1-7
1=1
$ NONK
N
T(1 - 77
where the last inequality holds when I llog(1/>)) 2 1og(2NNKT) On the other hand, we have
(st( ViT (st) =E
t (1(11,))4t)))) F(sets, (1t))) s1. .88 2
Therefore,
-V7 (/ S Regret(T) 1-7 Regret(T) S Regret(T) + -()
proof of Lemma C.3. Define Vi(s) max, a). By the assumption that (=(,, S Qi(s,a),
we have (s) S Vs(s). Then
A = (s.) V." & Vi(s.) Vi (st) = Qi(ss, a.) V (st).
where the last equality holds since o, argmax, Qr(se, a), i.e., we take the action d, greedily according to Qr-
The optimal truncated Q-function 27 F4b,, (x) (Algorithm 2) satisfies the following truncated Bellman equation:
F4d,, (s) (in(AA(1-7),,(s.00 + be, (s, + &.Ber (18.a) max Q2 Tr, Fth. (s',a')). (10)
18

---

Under review as a conference paper at ICLR 2023
Then have
(r) A. min (()), + bi, (8t, az) + +yBorry (1s), ()))))) V/(5), 11)
(F(st. 0i) + yBoun snd Viti (1')
F(st, be, (se, at) +, BBy (lecnr)) (leen))) (7(st, ae) + (2
-b, as) + + [gnnr (1 Vi((s) Eg V (6')
=be, (s), az) + + [BxiNT (1)1,))) (()s))))((s))) ExenF(I Vi(('))
+ + (ES Ve(s') - Ey' EE Vi7 (s)).
For the second term, since [V((5)) & A/(1 - 7), by Lemma C.I, we have
? (WoreRR (ara,) Ve(s') - EE ) s be, (sc. at).
For the last term, we have
(BonR(lor - BowF(lbea Vita('')
= + (V
where
& = (n (V)6)))V((<)'))> (Vi(8++1) - V/ V(
Therefore, we have
Vi((e) - (s.)
T
T
T
be, (1) +7 >
Ee + Σ
(V((842)-Vz) (
1=1
t=1
For the last term above, we have
Vo(se41) - Vi7 (
r
(ee1((4+1)) - Vi ((1()+4)))(()(04+11)))) + Σ
(Vi(8141) - (144()4+1)
Er
(Vo+1(0411)- - Vz (771(1411) + (1+4(11+1)- - Vi -V7 (sT+1)
- Vi(s1) + (r + Er
T
(V((s)) - (s.)) + 2A/(111)) (1-)) + Ex.
1=1
Notice that } is martingale difference sequence. Therefore, by Azuma-Hoefiding inequality, we have with probability at least 1 - 6,
T &
2A
<
T Tlog
19

---

Under review as a conference paper at ICLR 2023
To summarize, we have
T
Regret(x) -
Ve((s) - ViT(())
t=1
2
bi, (86,
Tlog
1
7
Σ Vi((s) v. + +24/(1 -7) Fr))
1-7
8
1=1
which implies
Regret(T) 5
1
27A be, (St, (st, az) +
(Tlog + (21/(11 -7) Brr]
1
1-7 7
1-
proof of Lemma C.4. On the one hand, we have
(et( det(Eo)
M det (ct(E).
> 2M
det (et(
On the other hand, we also have
(cr) det (D)
Tr Eny')
= det(ED Er) 1
Tr(I A E
Eipe (o
d
d -
d
Therefore, M log |+NKKII//A
+
D AUXILIARY LEMMAS
Lemma D.I. Let (s'lls, a) and ( (s'ls, a) be two transition probabilities. Assume that 0 S r(s, S A. Let Q" be optimal Q-function for MDP Mr. Let Q" be the optimal truncated Q-function for Me.+o which satisfies the following equation
(+),aa) min((A/11-)0 ()))))))))))) b(s, a) P(-baa) max (d)))
Then if
7d
b(s,a) 2
1-7 P[||s, a) - a(1ls,))ll,,
we have
(s z Q" a) for all (s,a).
Furthermore, we have for any (s) such that < (s)) < A/(1-7)
Y (E (ss) B V(s')) b(s,a).
Lemma D.2 (Factorization). 1f 1/1((-ss,a) = P. P(-1s.0) &h then
(P(-Is,a) - < -)
Lemma D.3 (Lemma 11 in (Abbasi-Yadkori et al., 201 1)). For any faetfm S Rd. let E,
AI + Σrn TNTT, then we have
E 1 ) 2d dA + TI2
where I. sup ||se||2
20

---

Under review as a conference paper at ICLR 2023
Lemma D.4 (Lemma 12 in (Abbasi- Yadkori et al., 2011)). Let A, B Raxd be positive definite matrices and =z= B. Then for any x E R we have
det(A) dBt
| < |
E ADDITIONAL EXPERIMENTS
E.1 SYNTHETIC CASCADE NETWORK
We conduct experiments on cascade synthetic networks as shown in Figure 2a. There are K = identical networks are associated with different contents; each cascade network has 300 nodes with high/medium/low influential power, 5/20/273 nodes respectively. More specifically. the five high nodes can activate theirselves and each others at the next time step with probability 0.1; the high nodes can activate the medium nodes with probability 0.2; the medium nodes can only activate the low nodes with probability 0.12. Therefore, these networks would appreciate the high nodes as better actions with more delayed reward. In addition, the d2 3-dim content features for K 4 contents are {(1, 0, 0), (0, 1), (0, O, 1), (0.3, 0.3, 0.3.0.4)) the d1 = 9-dim user features are one-hot for each type of nodes associated with each dimension of content features. Finally, the underlying linear dynamic T can be easily computed for desired probabilities of edges. The experiment result of the cascade synthetic networks reported in Figure
21

---

Under review as a conference paper at ICLR 2023
node content
node content
node content
node content
(a) Cascade network (300 nodes for cach content)
seed node
active node
decayed node after diffuse
inactive
=
(b) Star shape network (70 nodes)
Figure 2: Synthetic network visualization. (a) Cascade network. Four identical networks are associated with different content; their nodes colored differently. The node activation could not happen across content. The cascade network has nodes with high/medium/low influential power, 5/20/275 nodes respectively. (b) Star-shape network. This network has three influential nodes; the center one can activate the other two influential nodes. Only edges with positive probability are visualized.
22

---

is the Under review as a conference paper at ICLR 2023
100
IMLinUCB random policy
cumulative reward
60
40
0
300
400
timestep
Real-time discounted sum of rewards on synthetic star-shape graph (Fig.2b). The synthetic network has static underlying dynamics T generating diffusion probabilities from each node to all other nodes. Each line averaged from 20 trajectories; 85% CI bands are included.
Figure 3:
E.2 SYNTHETIC STAR-SHAPE NETWORK
We conduct additional experiments another synthetic network shown in Figure 2b, where better action has more delayed reward and making decision at each time step is appreciated. This synthetic network has three influential nodes out of total N 70 nodes, while the center best choice and has the ability to activate the other two influential nodes. Also the central influential node has delayed but higher expected reward than expected reward by activating either of other two neighboring influential nodes. For simplicity, we set only one content available here, = 1 and features are one-hot vectors, indicating their neighborhood subgraph. The
d2 1. The di discount factor of reward is = 0.9.
In Figure 3, compare the performance of our MORIMA MORIMA with known A k as upper bound and IMLinUCB as bascline. The details of these algorithms are the same as in section 5. MORIMA exhibits its great power to explore the unknown graph efficiently; its learning curve at the first 40 time steps overlaps with MORIMA while knowing the true dynamics A In addition, the sum of cumulative rewards of MORIMA and the upper bound stay the same high level. Furthermore, we observe that the learning procedure of IMLinUCB takes much longer and converges to much lower level. The classic IM setting, activating & seeds at once for every k step, shows its limit while adaptive decision making leads to better result.
We ran all experiments on our internal cluster with CPUs, 128G memory per task.
23

---

Under review as a conference paper at ICLR 2023
F EXTENSION TO GENERALIZED LINEAR MODEL
In this section, we show how to extend our algorithm and regret bound to generalized linear models. We first re-state below the modified assumption on the transition model.
Assumption (Generalized Bernoulli Independent Cascade Model), Let be the next state. For each & E [K) we assume there underlying connectivity matrix A E Raxn such that
P( = 11s)) 10
11 A A5,k)
(11)
where μ R. - I. satisfies p(0) = 0 and 1/M6 S p¹ S for some 2 1. And we assume 84, 's are independent conditioned on s.
MORIMA FOR GENERALIZED LINEAR MODEL
Next, state the changes to algorithm. Under this assumption, cannot simply ridge regression to get an empirical estimation of T". Instead, we estimate the tensor model by
T. argmin (.
XT
ΣΣΣ [u((T, (() 1=1k=lis
(s.+1) 2221
(12)
where of.x and E, are defined as Section 3.
We still perform optimistic planning with respect the truncated-reward model, where the reward bonus term (s, a) is replaced with
4nyA ΣΣ (1AB: (1)::),
()(s,a)
(13)
which is the original bonus term multiplied by 2x. We adopt the same slow switching method as before.
F.2 REGRET ANALYSIS
We have the following regret bound, which is the original bound multiplied by K. Theorem 4 (Re-state Theorem 3). Let Assumption 5. Assumptions 2-4 hold. With probability least 1 8, Algorithu satisfies the following regret upper bound:
Regret (T) < ④
A2 7)3 (JVC/A+VaNK) vT) +
K
where d = dim(T*) = d2d2.
F.3 PROOF SKETCH OF THEOREM
The proof of Theorem 3 only differs from the proof of Theorem 2 slightly. Next we examine through the proof of Theorem and state the corresponding lemmas in the generalized linear model setting.
First, we have exactly the same result for the high probability bounds for the number of active user-content pairs.
Lemma F.1 (High probability bounds for the number of active user-content pairs). Let Assumption 5, Assumptions 2-4 hold. For any possibly non-stations oon-stationary policy n, with probability at least 1 we
have for all t 2 1,
2
21a
||x 1l <
log
1).
A
5
The next two lemmas justify the choice of the bonus term. Lemma F2 (Confidence Region). Let Assumption 5, Assumptions 2-4 hold. With probability at least
1 8, we have for all
Le(TT) S Br,
where Br is defined in Eqn. (6).
24

---

Under review as a conference paper at ICLR 2023
Lemma E.3 (Optimism). Let Assumption 3, Assumptions 2-4 hold. Set the bonus term be be(s,a) 4mAy
K
CLABB [0
Then with probability at least we have the optimistic condition Q" - Qr(s, a) holds for all & 2 1.
Furthermore, we have for any (8) such that 0 < V(s) S A/(1 - -7), P( V(')) Eyrny (.)) V(5)| S (s)
proof of Theorem We can verify that Lemma C.2, Lemma C.3, and Lemma C.4 also hold for the generalized linear model. Therefore, the exact proof of Theorem applies with Lemma C.1 replaced with Lemma F.3. The result only differs by a factor k.
F.4 DEFERRED PROOFS OF LEMMAS
proof of Lemma F.I. Notice that we have assumed pd0) and pl < Therefore for uu=)= = [()= - (00) - = - 0 2. Then
1(( ael p Σ
LA (sta)) S Σ (
Then the result holds by applying the same proof of Lemma B.2.
proof of Lemma F22. We have
TT(T)= = AT
(M(T ((T))))))) (8++1)sa) 0 x
< |XT ||
(M((T,,TT)) - (8r+1)e. s
t-1 K N
I |XT 11A
Σ
ΣΣ>
[P(TT" (T,))) (s7+1)e,) of
x
< VAITT (8. v\ITT*
= Br
where the last but one inequality holds by applying Lemma B.3 with the same variance upper bound as in the proof of Lemma B.
proof of Lemmna E3. Let P Pt.. By the assumption that μd S still have
[Prx(-(s, - -P a))l s 2(1 KT Tr, (s.
< 2 -
a)ll,, 1,)
By Lemma F.2, with probability at least 1 - 6, we have (T(T)) S and then Li( Br for all t 2 1. Therefore, we have
23, 2 (T)) + Le(T))
> AT + (-1 K N ΣΣΣ
- 1 XT 1- K N
((((T")TT))) - BertideJ@oTA
K N = =I[[x AI ΣΣΣ
[P'((T ([TF
.
2 1/K- || (Ta T
1/x 11+ T 12x1>,111
25

---

Under review as a conference paper at ICLR 2023
where use Lagrange Mean Value Theorem in the first equality and μ²(+) 2 1/k. Then the desired result holds by applying Lemma D.2 and Lemma D.1 in the same way as the proof of Lemma C.I. O
26


Reviews:
[{"review_id": "se5LL5fItC7", "reviewer": "Reviewer_o5dv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studied adaptive content-dependent online influence maximization where the seed nodes are sequentially activated based on real-time feedback. The authors formulated the problem as an infinite-horizon discount MDP and proposed a model-based RL algorithm that only requires node-level feedback. They proved the first sublinear regret bound for the adaptive content-dependent online influence maximization problem and validated the effectiveness of the algorithm on both synthetic and real-world data.", "summary_of_the_review": "This paper studied a new adaptive online influence maximization problem and provided an RL algorithm with theoretical regret bound. My main concerns are Assumption 3 for the Bernoulli Independent Cascade Model and the availability of user and content features in real problems. Also, the social networks considered in the experiments are relatively small (~2000 nodes).", "strength_and_weaknesses": "Strength\n1. This paper is the first to study the adaptive online influence maximization (OIM) problem, which is an interesting direction motivated by the recent advances in offline adaptive influence maximization.\n2. The infinite-horizon discount MDP formulation of the adaptive OIM problem is reasonable.\n3. The authors designed a model-based RL algorithm that only requires node-level feedback, while most previous works rely on edge-level feedback. They also proved the theoretical regret bound of the algorithm, which is the first sublinear regret bound for online adaptive influence maximization.\n\nWeaknesses\n1. The Bernoulli Independent Cascade Model relies on Assumption 3. However, IMHO, this assumption is relatively strong: it suggests that with larger $N$ and $K$, the A values should be smaller. This may not be reasonable in practice since the “influence” between two users should not be affected by the total number of users or contents.\n2. In the infinite-horizon discounted MDP formulation, the action at each timestep is to activate just one user-content pair; it would be more interesting to consider the action of multiple user-content pairs per timestep.\n3. I’m a bit concerned about how to obtain the user feature $x$ and content feature $\\theta$ for real-world OIM problems.\n4. In the problem formulation, the authors argue they focus on the asymptotic regime of large networks where $T<<N$, while in the explements, $T$ and $N$ are close (e.g., N=300, T=1000 in Fig. 1).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Nm1brgU1KTu", "reviewer": "Reviewer_vMK7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The adaptive version of the online adaptive topic-aware influence maximization problem is considered in this work, where its primary objective is the spreading of specific content in social networks. The problem is formulated as an infinite-horizon discounted MDP, and a model-based reinforcement algorithmic scheme, called MORIMA, has been proposed that learns a policy adaptively. The authors provide a regret analysis for the proposed algorithm. Experiments have been conducted on small synthetic and real-world networks, while the proposed algorithm has been compared with the IMLinUCB algorithm.\n", "summary_of_the_review": "The authors should address the limitations of the MORIMA algorithm in a clear way. As aforementioned, the main question of this work is its applicability in real-world networks with a large number of users. The potential negative social impact of this work should be discussed further. How can this work have a positive impact on our society and what is its main objective?\n\n", "strength_and_weaknesses": "**Strengths**\n- The examination of the online influence maximization problem under the adaptive setting is quite interesting, as resembles what happens in the real-world. \n- The adoption of a model-based reinforcement learning algorithm for selecting seed users adaptively.\n- A regret bound is provided for the proposed algorithm.\n\n**Weaknesses**\n- In general, the paper is well written, nevertheless, some of its parts need to be clarified.\n- The exploration efficiency of the proposed reinforcement learning algorithm is not clear.\n- The applicability of the MORIMA algorithm in real-world networks with millions of users seems to be not possible.\n- Experiments have been conducted only on small synthetic and real-world networks that are  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7nBgsLK41A", "reviewer": "Reviewer_Asps", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a network diffusion process to model (user, content) feature dependent network propagation and formulate the problem as an infinite-horizon discounted MDP, with the goal to select seed users and customize contents to maximize network influence. Then it proves a sub-linear regret bound for the proposed algorithms, and validate their results empirically on both synthetic and twitter social network datasets. ", "summary_of_the_review": "The paper proposes a network diffusion process to model (user, content) feature dependent network propagation and formulate the problem as an infinite-horizon discounted MDP, with the goal to select seed users and customize contents to maximize network influence. Then it proves a sub-linear regret bound for the proposed algorithms, and validate their results empirically on both synthetic and twitter social network datasets. \n\nIn the experimentation section, the paper only compares to random policy and IMLinUCB, lack of strong comprehensive baseline comparison and empirical evaluation. In addition to that, there are some unclarity in the experimentation results, shared in below: \n1. Comparing to IMLinUCB, MORIMA variants seems to have low variance, so curious to understand why that's the case? \n2. Among MORIMA variants, MORIMA without slow switching (in green) seems to be more stable over timesteps comparing to MORIMA (blue). Should we factor in stability over timesteps in choosing these variants? If so, how? \n3. In Figure (b), \"MORIMA with known A\" seems to underperform the other two MORIMA variants when timesteps reaches 200+. Is that expected or why is that? ", "strength_and_weaknesses": "Strengths: \n1. The paper proposes a network diffusion process to model (user, content) feature dependent network propagation and formulate the problem as an infinite-horizon discounted MDP, with the goal to select seed users and customize contents to maximize network influence. \n2. it proves a sub-linear regret bound for the proposed algorithms, and validate their results empirically on both synthetic and twitter social network datasets. \n\n\nWeakness: \nThe paper only compares to random policy and IMLinUCB, lack of strong comprehensive baseline comparison and empirical evaluation. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject