LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection
This work addresses influence maximization for social network analysis, but it is incremental as it builds on existing submodularity properties to improve regret.
The paper tackles the problem of online influence maximization under full-bandit feedback by proposing LOFA, which achieves lower empirical regret and superior performance in experiments on a real-world social network compared to existing bandit algorithms.
We study the problem of influence maximization (IM) in an online setting, where the goal is to select a subset of nodes$\unicode{x2014}$called the seed set$\unicode{x2014}$at each time step over a fixed time horizon, subject to a cardinality budget constraint, to maximize the expected cumulative influence. We operate under a full-bandit feedback model, where only the influence of the chosen seed set at each time step is observed, with no additional structural information about the network or diffusion process. It is well-established that the influence function is submodular, and existing algorithms exploit this property to achieve low regret. In this work, we leverage this property further and propose the Lazy Online Forward Algorithm (LOFA), which achieves a lower empirical regret. We conduct experiments on a real-world social network to demonstrate that LOFA achieves superior performance compared to existing bandit algorithms in terms of cumulative regret and instantaneous reward.