Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
We study the online influence maximization problem in social networks under the independent cascade model. Specifically, we aim to learn the set of "best influencers" in a social network online while repeatedly interacting with it. We address the challenges of (i) combinatorial action space, since the number of feasible influencer sets grows exponentially with the maximum number of influencers, and (ii) limited feedback, since only the influenced portion of the network is observed. Under a stochastic semi-bandit feedback, we propose and analyze IMLinUCB, a computationally efficient UCB-based algorithm. Our bounds on the cumulative regret are polynomial in all quantities of interest, achieve near-optimal dependence on the number of interactions and reflect the topology of the network and the activation probabilities of its edges, thereby giving insights on the problem complexity. To the best of our knowledge, these are the first such results. Our experiments show that in several representative graph topologies, the regret of IMLinUCB scales as suggested by our upper bounds. IMLinUCB permits linear generalization and thus is both statistically and computationally suitable for large-scale problems. Our experiments also show that IMLinUCB with linear generalization can lead to low regret in real-world online influence maximization.
The paper studies the following bandit model: actions are nodes in a known directed graph and at each time step t the following happens: (1) hidden from the player, each edge (i,j) is independently declared "open" or "closed" with fixed but unknown probability w(i,j); (2) the player chooses a subset S_t of nodes of cardinality at most K; (3) all directed paths originated from nodes in S_t that go through open edges are revealed to the player; (4) the player's reward is the number of nodes in these paths. The regret of the player is measured with respect to the expected reward obtained by consistently playing the K-sized subset S of nodes that maximizes the expected reward. Since this set is NP-hard to compute, but easy to approximate, it is assumed that the player has access to an oracle that, given G and estimates of w(i,j) for each edge (i,j), returns the K-sized subset S_t that maximizes the expected reward according to the estimates. The probabilities w(i,j) are assumed to follow a linear model, w(i,j) = x(i,j)*theta, where x(i,j) is the known d-dimensional feature vector associated with edge (i,j) and theta is an unknown parameter vector. A special case is the "tabular model" where all the feature vectors are orthogonal. The paper proposes a natural variant of LinUCB to learn the vector theta using the oracle to compute the maximizing subset. The regret scales with dC_*\sqrt{|E|T} where d is the dimension of theta, E is the edge set, and C_* is a parameter that depends on the interaction between G and w. The experimental section is properly done.
The paper builds on a series of works that study influence maximization in the bandit model. The main new ideas are the linear model for probabilities, which provides a key to scalability, and the introduction of C_* as a natural scaling parameter for the regret. The results are not extremely strong, but they are nevertheless interesting and technically solid.
The parameter sigma plays no role and could perhaps be omitted from the analysis.