Efficient Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback

Influence maximization is an important research area in social network analysis, where the goal is to select a small set of seed nodes so as to maximize the expected spread of influence under a stochastic diffusion process. Classical approximation algorithms for this problem rely on full knowledge of the underlying influence probabilities and operate in an offline manner. In many real-world settings, however, these probabilities are unknown and must be learned from data, raising the question: can one still obtain strong performance guarantees while simultaneously learning the diffusion model parameters through repeated interactions? In this paper, we study the problem of online influence maximization under the independent cascade model, where influence probabilities are unknown and feedback is limited to node-level activation outcomes. Prior work relies on a pair oracle which needs to perform a joint optimization over seed sets and feasible parameters. This oracle is difficult to implement in practice and it was open whether one can achieve sublinear regret using only a standard offline oracle. We resolve this question by designing an online learning algorithm that achieves $\widetilde{O}(\sqrt{T})$ regret using only a standard offline oracle. Finally, we validate our theoretical results via experiments on real and synthetic data.