Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect
This work addresses the challenge of incorporating user engagement persistence into sequential decision-making for platforms, though it is incremental as it extends existing bandit models with temporal constraints.
The paper tackles the problem of modeling priming effects, such as wear-in and wear-out periods, in stochastic multi-armed bandits for applications like advertising and recommendation systems, and provides novel algorithms that achieve sublinear regret with additive effects on the regret upper bound, matching standard algorithms like UCB1 and Thompson sampling when no priming is present.
We study the effect of persistence of engagement on learning in a stochastic multi-armed bandit setting. In advertising and recommendation systems, repetition effect includes a wear-in period, where the user's propensity to reward the platform via a click or purchase depends on how frequently they see the recommendation in the recent past. It also includes a counteracting wear-out period, where the user's propensity to respond positively is dampened if the recommendation was shown too many times recently. Priming effect can be naturally modelled as a temporal constraint on the strategy space, since the reward for the current action depends on historical actions taken by the platform. We provide novel algorithms that achieves sublinear regret in time and the relevant wear-in/wear-out parameters. The effect of priming on the regret upper bound is also additive, and we get back a guarantee that matches popular algorithms such as the UCB1 and Thompson sampling when there is no priming effect. Our work complements recent work on modeling time varying rewards, delays and corruptions in bandits, and extends the usage of rich behavior models in sequential decision making settings.