# Budgeted Online Influence Maximization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 47 references that are in the map.
- First posted on arXiv 21 Apr 2026.

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

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency](https://mlsanity.com/paper/1404.0900/) (2014)
- [Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/2006.06613/) (2020)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [Influence Maximization with Bandits](https://mlsanity.com/paper/1503.00024/) (2015)
- [Sketch-based Influence Maximization and Computation: Scaling up with Guarantees](https://mlsanity.com/paper/1408.6282/) (2014)
- [Online Influence Maximization with Local Observations](https://mlsanity.com/paper/1805.11022/) (2018)
- [Finding the bandit in a graph: Sequential search-and-stop](https://mlsanity.com/paper/1806.02282/) (2018)
- [Online Learning with Cumulative Oversampling: Application to Budgeted Influence Maximization](https://mlsanity.com/paper/2004.11963/) (2020)
- [Covariance-adapting algorithm for semi-bandits with application to sparse rewards](https://mlsanity.com/paper/2604.13738/) (2026)

## Abstract (arXiv)

We introduce a new budgeted framework for online influence maximization, considering the total cost of an advertising campaign instead of the common cardinality constraint on a chosen influencer set. Our approach better models the real-world setting where the cost of influencers varies and advertisers want to find the best value for their overall social advertising budget. We propose an algorithm assuming an independent cascade diffusion model and edge level semi-bandit feedback, and provide both theoretical and experimental results. Our analysis is also valid for the cardinality constraint setting and improves the state of the art regret bound in this case.