Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect

Priyank Agrawal, Theja Tulabandhula

Abstract: 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.

Introduction

In digital marketing and recommendation engines, human behavior is rarely static. A user might ignore an advertisement the first time they see it, but after five exposures, they may finally click—a phenomenon known as the wear-in effect. Conversely, showing the same ad fifty times might lead to fatigue or "banner blindness," causing the user to stop responding entirely—the wear-out effect.

This paper, presented at UAI 2020, formalizes these behaviors as a Multi-armed Bandit (MAB) problem under the "Priming Effect." By providing a theoretical framework and novel algorithms, the authors demonstrate how to navigate these temporal traps to optimize long-term engagement.

The Priming Problem

Standard MAB algorithms assume that the reward from an action is independent of past decisions. However, in systems governed by priming, rewards are endogenous—they depend on the agent's own history.

  1. Wear-in: Requires a minimum frequency of recent repetitions to trigger a positive response.
  2. Wear-out: Excessive repetition causes the reward to drop to zero due to user fatigue.

Traditional algorithms like UCB1 or Thompson Sampling often fail here. Their exploration strategies may switch arms too frequently to achieve wear-in, or stay with a single arm too long, triggering wear-out.

The decision logic for choosing an action under priming constraints, where rewards depend on recent history.

Proposed Methods

The authors introduce a phased algorithmic template to manage these dependencies, moving away from simple round-by-round decisions.

WI-UCB (Wear-In UCB)

Designed for environments where only wear-in is a concern, this algorithm plays arms in distinct, non-overlapping phases. By playing an active arm consecutively for an "incremental phase length," it ensures the wear-in threshold is surpassed before the arm's performance is evaluated.

WI/WO-UCB (Wear-In/Wear-Out UCB)

To handle both effects, the authors propose the Compound Arm strategy. Instead of a single arm, the algorithm plays a pair of arms, alternating between them. This "local exploration" prevents the user from reaching the wear-out threshold for either arm while maintaining enough total frequency to stay within the wear-in window.

Key Results and Analysis

The theoretical analysis, utilizing martingale concentration inequalities, proves that these strategies achieve sublinear regret. Crucially, the priming effect introduces an additive penalty to the regret bound based on wear-in/wear-out parameters. If these parameters are zero, the performance gracefully matches standard UCB1 guarantees.

Comparison of regret bounds for the proposed algorithms against standard baselines.

In synthetic benchmarks with up to 30 arms, standard baselines like UCB1 and MOSS incurred linear regret because they failed to account for the temporal dependencies of priming. In contrast, WI-UCB and WI/WO-UCB maintained $O(\sqrt{T \log T})$ regret, converging toward the optimal strategy over time.

Conclusion

This work extends the utility of multi-armed bandits to more realistic behavioral models. The "Compound Arm" insight suggests that rotating between a small set of high-quality messages is often superior to repetitive hammering or excessive variety. Future work may involve extending this framework to contextual bandits or modeling priming as a continuous, smooth curve rather than a binary threshold.

Summary updated

Abstract

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.
BibTeX
@inproceedings{agrawal2020learning,
  author = {Priyank Agrawal and Theja Tulabandhula},
  title = {{Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=S_uZsUv4zXc},
}

Loading related content...

Figure