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: \emph{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 \emph{online influence maximization} under the independent cascade model, where influence probabilities are unknown and feedback is limited to \emph{node-level} activation outcomes. Prior work relies on a \emph{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 \emph{standard} offline oracle. We resolve this question by designing an online learning algorithm that achieves $\widetilde{O}(\sqrt{T})$ regret using only a \emph{standard} offline oracle. Finally, we validate our theoretical results via experiments on real and synthetic data.