Online Learning of Independent Cascade Models with Node-Level Feedback

• 成果类型: Article; Early Access
• 署名作者: Yang, Shuoguang; Truong, Van-Anh
• 署名单位: Hong Kong University of Science & Technology; Columbia University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.0117
• 发表日期: 2025
• 关键词: bandits

摘要

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 root ffiffiffi cumulative regret of O( 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.