LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908744812593152 |
|---|---|
| author | Xu, Jinyu Umrawal, Abhishek K. |
| author_facet | Xu, Jinyu Umrawal, Abhishek K. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_00933 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection Xu, Jinyu Umrawal, Abhishek K. Machine Learning Artificial Intelligence Social and Information Networks 05C90, 60J60, 68R05, 68R10, 68T05, 90C27, 90C35 E.1; F.2.2; G.1.6; G.2.1; G.2.2; G.3; I.2.0; I.2.6; J.4 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. |
| title | LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection |
| topic | Machine Learning Artificial Intelligence Social and Information Networks 05C90, 60J60, 68R05, 68R10, 68T05, 90C27, 90C35 E.1; F.2.2; G.1.6; G.2.1; G.2.2; G.3; I.2.0; I.2.6; J.4 |
| url | https://arxiv.org/abs/2601.00933 |