Uplifting Bandits
This work addresses a specific modeling challenge in bandit problems for domains like marketing, but it is incremental as it builds on existing UCB methods with new structural assumptions.
The paper tackles the problem of multi-armed bandits where rewards are sums of random variables, with actions altering only some distributions, motivated by applications like marketing and recommender systems. It proposes UCB-style algorithms that estimate uplifts over a baseline, proves sublinear regret bounds, and shows benefits in experiments on synthetic and real-world datasets.
We introduce a multi-armed bandit model where the reward is a sum of multiple random variables, and each action only alters the distributions of some of them. After each action, the agent observes the realizations of all the variables. This model is motivated by marketing campaigns and recommender systems, where the variables represent outcomes on individual customers, such as clicks. We propose UCB-style algorithms that estimate the uplifts of the actions over a baseline. We study multiple variants of the problem, including when the baseline and affected variables are unknown, and prove sublinear regret bounds for all of these. We also provide lower bounds that justify the necessity of our modeling assumptions. Experiments on synthetic and real-world datasets show the benefit of methods that estimate the uplifts over policies that do not use this structure.