Budgeted Online Influence Maximization

• URL: http://arxiv.org/abs/2604.19672v1
• Date: Tue, 21 Apr 2026 16:51:57 GMT
• Title: Budgeted Online Influence Maximization
• Abstract summary: We introduce a new framework for online influence, considering the total cost of an advertising campaign instead of the common cardinality constraint on a chosen set.<n>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.
• Score: 25.113510553720683
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Nash Equilibrium Constrained Auto-bidding With Bi-level Reinforcement Learning [64.2367385090879]
  We propose a new formulation of the auto-bidding problem from the platform's perspective.<n>It aims to maximize the social welfare of all advertisers under the $epsilon$-NE constraint.<n>The NCB problem presents significant challenges due to its constrained bi-level structure and the typically large number of advertisers involved.
  arXiv  Detail & Related papers  (2025-03-13T12:25:36Z)
• Adaptive Budget Optimization for Multichannel Advertising Using Combinatorial Bandits [9.197038204851458]
  We introduce three key contributions to the field of budget allocation in digital advertising.<n>First, we develop a simulation environment designed to mimic multichannel advertising campaigns over extended time horizons.<n>Second, we propose an enhanced bandit budget allocation strategy that leverages a saturating mean function and a targeted exploration mechanism with change-point detection.
  arXiv  Detail & Related papers  (2025-02-05T06:29:52Z)
• Hierarchical Multi-agent Meta-Reinforcement Learning for Cross-channel Bidding [4.741091524027138]
  Real-time bidding (RTB) plays a pivotal role in online advertising ecosystems.<n>Traditional approaches cannot effectively manage the dynamic budget allocation problem.<n>We propose a hierarchical multi-agent reinforcement learning framework for multi-channel bidding optimization.
  arXiv  Detail & Related papers  (2024-12-26T05:26:30Z)
• Cost-Control in Display Advertising: Theory vs Practice [0.2574913881702984]
  In display advertising, advertisers want to achieve a marketing objective with constraints on budget and cost-per-outcome. This is usually formulated as an optimization problem that maximizes the total utility under constraints. The optimization is carried out in an online fashion in the dual space - for an incoming Ad auction, a bid is placed using an optimal bidding formula. based on the outcome of the previous auctions, the dual variables are updated in an online fashion. While this approach is theoretically sound, in practice, the dual variables are not optimal from the beginning, but rather converge over time.
  arXiv  Detail & Related papers  (2024-09-05T19:22:33Z)
• Rate-Optimal Policy Optimization for Linear Markov Decision Processes [65.5958446762678]
  We obtain rate-optimal $widetilde O (sqrt K)$ regret where $K$ denotes the number of episodes. Our work is the first to establish the optimal (w.r.t.$K$) rate of convergence in the setting with bandit feedback. No algorithm with an optimal rate guarantee is currently known.
  arXiv  Detail & Related papers  (2023-08-28T15:16:09Z)
• Model-based Causal Bayesian Optimization [74.78486244786083]
  We introduce the first algorithm for Causal Bayesian Optimization with Multiplicative Weights (CBO-MW) We derive regret bounds for CBO-MW that naturally depend on graph-related quantities. Our experiments include a realistic demonstration of how CBO-MW can be used to learn users' demand patterns in a shared mobility system.
  arXiv  Detail & Related papers  (2023-07-31T13:02:36Z)
• Structured Dynamic Pricing: Optimal Regret in a Global Shrinkage Model [50.06663781566795]
  We consider a dynamic model with the consumers' preferences as well as price sensitivity varying over time. We measure the performance of a dynamic pricing policy via regret, which is the expected revenue loss compared to a clairvoyant that knows the sequence of model parameters in advance. Our regret analysis results not only demonstrate optimality of the proposed policy but also show that for policy planning it is essential to incorporate available structural information.
  arXiv  Detail & Related papers  (2023-03-28T00:23:23Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Demystifying Advertising Campaign Bid Recommendation: A Constraint target CPA Goal Optimization [19.857681941728597]
  This paper presents a bid optimization scenario to achieve the desired cost-per-acquisition (tCPA) goals for advertisers. We build the optimization engine to make a decision by solving the rigorously formalized constrained optimization problem. The proposed model can naturally recommend the bid that meets the advertisers' expectations by making inference over advertisers' historical auction behaviors.
  arXiv  Detail & Related papers  (2022-12-26T07:43:26Z)
• Contextual Bandits for Advertising Campaigns: A Diffusion-Model Independent Approach (Extended Version) [73.59962178534361]
  We study an influence problem in which little is assumed to be known about the diffusion network or about the model that determines how information may propagate. In this setting, an explore-exploit approach could be used to learn the key underlying diffusion parameters, while running the campaign. We describe and compare two methods of contextual multi-armed bandits, with upper-confidence bounds on the remaining potential of influencers.
  arXiv  Detail & Related papers  (2022-01-13T22:06:10Z)
• Correlation Robust Influence Maximization [5.508091917582913]
  We propose a distributionally robust model for the influence problem. We seek a seed set whose expected influence under the worst correlation is maximized. We show that this worst-case influence can be efficiently computed.
  arXiv  Detail & Related papers  (2020-10-24T04:43:56Z)
• Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising [52.3825928886714]
  We formulate the sequential advertising strategy optimization as a dynamic knapsack problem. We propose a theoretically guaranteed bilevel optimization framework, which significantly reduces the solution space of the original optimization space. To improve the exploration efficiency of reinforcement learning, we also devise an effective action space reduction approach.
  arXiv  Detail & Related papers  (2020-06-29T18:50:35Z)

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.