# LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection

arXiv: https://arxiv.org/abs/2601.00933 · HTML: https://mlsanity.com/paper/2601.00933/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 2 Jan 2026.

## Builds on (most cited first, 12 of 12)

- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits](https://mlsanity.com/paper/1507.04523/) (2015)
- [Stochastic Top-K Subset Bandits with Linear Space and Non-Linear Feedback](https://mlsanity.com/paper/1811.11925/) (2018)
- [A Community-Aware Framework for Social Influence Maximization](https://mlsanity.com/paper/2207.08937/) (2022)
- [Adaptive Sensor Placement for Continuous Spaces](https://mlsanity.com/paper/1905.06821/) (2019)
- [Fractional Budget Allocation for Influence Maximization under General Marketing Strategies](https://mlsanity.com/paper/2407.05669/) (2024)
- [Online Influence Maximization in Non-Stationary Social Networks](https://mlsanity.com/paper/1604.07638/) (2016)
- [How to Influence People with Partial Incentives](https://mlsanity.com/paper/1401.7970/) (2014)
- [A Pressure-Based Diffusion Model for Influence Maximization on Social Networks](https://mlsanity.com/paper/2509.12822/) (2025)
- [A Community-Aware Framework for Influence Maximization with Explicit Accounting for Inter-Community Influence](https://mlsanity.com/paper/2512.23973/) (2025)

## Abstract (arXiv)

We study the problem of influence maximization (IM) in an online setting, where the goal is to select a subset of nodesunicodex2014called the seed setunicodex2014at 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.