Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization

• URL: http://arxiv.org/abs/2206.14846v1
• Date: Wed, 29 Jun 2022 18:17:28 GMT
• Title: Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization
• Authors: Kaixuan Huang, Yu Wu, Xuezhou Zhang, Shenyinying Tu, Qingyun Wu, Mengdi Wang, Huazheng Wang
• Abstract summary: We consider an adaptive version of content-dependent online influence problem where seed nodes are sequentially activated based on realtime feedback. Our algorithm maintains a network model estimate and selects seed adaptively, exploring the social network while improving the optimal policy optimistically.
• Score: 53.11458949694947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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(\sqrt{T})$ regret bound for our algorithm. Empirical evaluations on synthetic network demonstrate the efficiency of our algorithm.

Related papers

• Adaptive Anomaly Detection in Network Flows with Low-Rank Tensor Decompositions and Deep Unrolling [9.20186865054847]
  Anomaly detection (AD) is increasingly recognized as a key component for ensuring the resilience of future communication systems. This work considers AD in network flows using incomplete measurements. We propose a novel block-successive convex approximation algorithm based on a regularized model-fitting objective. Inspired by Bayesian approaches, we extend the model architecture to perform online adaptation to per-flow and per-time-step statistics.
  arXiv  Detail & Related papers  (2024-09-17T19:59:57Z)
• Reinforcement Learning for Node Selection in Branch-and-Bound [52.2648997215667]
  Current state-of-the-art selectors utilize either hand-crafted ensembles that automatically switch between naive sub-node selectors, or learned node selectors that rely on individual node data. We propose a novel simulation technique that uses reinforcement learning (RL) while considering the entire tree state, rather than just isolated nodes.
  arXiv  Detail & Related papers  (2023-09-29T19:55:56Z)
• Optimization Guarantees of Unfolded ISTA and ADMM Networks With Smooth Soft-Thresholding [57.71603937699949]
  We study optimization guarantees, i.e., achieving near-zero training loss with the increase in the number of learning epochs. We show that the threshold on the number of training samples increases with the increase in the network width.
  arXiv  Detail & Related papers  (2023-09-12T13:03:47Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks. We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
  arXiv  Detail & Related papers  (2023-07-07T15:03:42Z)
• Network Inference and Influence Maximization from Samples [20.916163957596577]
  We study the task of selecting a small number of seed nodes in a social network to maximize the spread of the influence from these seeds. We provide a novel solution to the cascade to the network inference problem, that is, learning diffusion parameters and the network structure from the data. Our IMS algorithms enhance the learning-and-then-optimization approach by allowing a constant approximation ratio even when the diffusion parameters are hard to learn.
  arXiv  Detail & Related papers  (2021-06-07T08:06:36Z)
• Influence Maximization Under Generic Threshold-based Non-submodular Model [1.5780411262109524]
  Concept of social influence is coined, where the goal is to select a number of most influential nodes (seed nodes) from a social network so that they can jointly trigger the maximal influence diffusion. In this paper, we propose seed selection strategies using network graphical in a generalized threshold-based model, called influence barricade model, which is non-submodular. To the best of our knowledge, this is the first graph-based approach that directly tackles non-submodular influence.
  arXiv  Detail & Related papers  (2020-12-18T16:14:49Z)
• Iterative Amortized Policy Optimization [147.63129234446197]
  Policy networks are a central feature of deep reinforcement learning (RL) algorithms for continuous control. From the variational inference perspective, policy networks are a form of textitamortized optimization, optimizing network parameters rather than the policy distributions directly. We demonstrate that iterative amortized policy optimization, yields performance improvements over direct amortization on benchmark continuous control tasks.
  arXiv  Detail & Related papers  (2020-10-20T23:25:42Z)
• Iterative Surrogate Model Optimization (ISMO): An active learning algorithm for PDE constrained optimization with deep neural networks [14.380314061763508]
  We present a novel active learning algorithm, termed as iterative surrogate model optimization (ISMO) This algorithm is based on deep neural networks and its key feature is the iterative selection of training data through a feedback loop between deep neural networks and any underlying standard optimization algorithm.
  arXiv  Detail & Related papers  (2020-08-13T07:31:07Z)
• Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks [119.81868223344173]
  This paper investigates the optimal resource allocation in free space optical (FSO) fronthaul networks. We consider the graph neural network (GNN) for the policy parameterization to exploit the FSO network structure. The primal-dual learning algorithm is developed to train the GNN in a model-free manner, where the knowledge of system models is not required.
  arXiv  Detail & Related papers  (2020-06-26T14:20:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.