Revealing graph bandits for maximizing local influence
arXiv:2605.00489
Abstract
We study a graph bandit setting where the objective of the learner is to detect the most influential node of a graph by requesting as little information from the graph as possible. One of the relevant applications for this setting is marketing in social networks, where the marketer aims at finding and taking advantage of the most influential customers. The existing approaches for bandit problems on graphs require either partial or complete knowledge of the graph. In this paper, we do not assume any knowledge of the graph, but we consider a setting where it can be gradually discovered in a sequential and active way. At each round, the learner chooses a node of the graph and the only information it receives is a stochastic set of the nodes that the chosen node is currently influencing. To address this setting, we propose BARE, a bandit strategy for which we prove a regret guarantee that scales with the detectable dimension, a problem dependent quantity that is often much smaller than the number of nodes.
Published at AISTATS 2016 (19th International Conference on Artificial Intelligence and Statistics)
References in corpus (11)
- Community structure in social and biological networks
- Online Influence Maximization (Extended Version)
- Efficient learning by implicit exploration in bandit problems with side observations
- Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
- Online Clustering of Bandits
- Leveraging Side Observations in Stochastic Bandits
- Spectral bandits for smooth graph functions
- From Bandits to Experts: A Tale of Domination and Independence
- Influence Maximization with Bandits
- Online learning with noisy side observations
- Information Gathering in Networks via Active Exploration