Influencer selection under budget constraints: a learning approach

Influencer marketing is becoming the fastest-growing and most cost-effective form of marketing and advertising. In this paper, we consider an influencer selection problem in online learning and adaptive settings: a brand conducts influencer marketing campaigns to promote a product over multiple rounds with a limited promotional budget. We propose a cumulative oversampling (CO) technique for Thompson Sampling (TS) that can be used to construct optimistic parameter estimates using significantly fewer samples from the posterior distributions compared to existing oversampling frameworks. By combining CO with the oracle we designed for the offline problem, our online learning algorithm simultaneously addresses budget allocation, parameter learning, and reward maximisation. We prove that our online learning algorithm achieves a scaled regret comparable to that of the UCB-based algorithms for the Influence Maximisation problem. It is the first regret bound for TS-based algorithms for IM semi-bandits that does not depend linearly on the reciprocal of the minimum observation probability of an edge. Our results provide actionable insights for firms on how to allocate marketing budgets and select influencers in dynamic and uncertain environments.