# Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 36 references that are in the map.
- First posted on arXiv 29 Jun 2022.

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

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Online Influence Maximization (Extended Version)](https://mlsanity.com/paper/1506.01188/) (2015)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Factorization Bandits for Online Influence Maximization](https://mlsanity.com/paper/1906.03737/) (2019)
- [Adaptive Influence Maximization in Dynamic Social Networks](https://mlsanity.com/paper/1506.06294/) (2015)
- [Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure](https://mlsanity.com/paper/2009.05986/) (2020)
- [Online Influence Maximization with Local Observations](https://mlsanity.com/paper/1805.11022/) (2018)
- [Adaptive Influence Maximization with Myopic Feedback](https://mlsanity.com/paper/1905.11663/) (2019)
- [Adaptive Influence Maximization under General Feedback Models](https://mlsanity.com/paper/1902.00192/) (2019)

## Built on by (most cited first, 1 of 1)

- [Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening](https://mlsanity.com/paper/2607.22009/) (2026)

## Abstract (arXiv)

Online influence maximization aims to maximize the influence spread of a content in a social network with unknown network model by selecting a few seed nodes. Recent studies followed a non-adaptive setting, where the seed nodes are selected before the start of the diffusion process and network parameters are updated when the diffusion stops. We consider an adaptive version of content-dependent online influence maximization problem where the seed nodes are sequentially activated based on real-time feedback. In this paper, we formulate the problem as an infinite-horizon discounted MDP under a linear diffusion process and present a model-based reinforcement learning solution. Our algorithm maintains a network model estimate and selects seed users adaptively, exploring the social network while improving the optimal policy optimistically. We establish widetilde O(√T) regret bound for our algorithm. Empirical evaluations on synthetic network demonstrate the efficiency of our algorithm.