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 [Formula: see text], 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 .