Online Learning of Independent Cascade Models with Node-Level Feedback

We propose the analysis of the online learning problem for independent cascade (IC) models under node-level feedback. These models have widespread applications in modern social networks. Existing works for IC models have only shed light on edge-level feedback models, where the agent knows the explicit outcome of every observed edge. Little is known about node-level feedback models where only combined outcomes for sets of edges are observed; in other words, the realization of each edge is censored. This censored information, together with the nonlinear form of the aggregated influence probability, makes both parameter estimation and algorithm design challenging. We establish a confidence-region result under this setting. We develop an online algorithm achieving a cumulative regret of $\tilde{\mathcal{O}}(\sqrt{T})$, matching the theoretical regret bound for IC models with edge-level feedback. We also establish a framework to implement the offline oracle and provide its theoretical performance guarantee. Numerical experiments demonstrate the practical efficiency of our algorithm.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2021.0117.