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 a user needs to see an item multiple times before acting, and a wear-out period, where excessive exposure leads to fatigue. We introduce a framework to model these effects and propose algorithms that achieve sublinear regret by strategically managing repetition.

Introduction

In digital advertising and recommendation engines, user responses are rarely independent of history. A user’s reaction to an ad or a movie recommendation depends heavily on recent exposure. Standard Multi-armed Bandit (MAB) models, which assume rewards are independent of past actions, fail to capture this temporal dependency. This paper addresses the "priming effect"—the combination of wear-in (the need for repeated exposure before a user acts) and wear-out (the decline in engagement due to over-exposure).

The Priming Effect Framework

The authors model the priming effect as a temporal constraint where the reward at time $t$ is a function of the history of the last $N$ rounds. This introduces endogeneity: the current reward depends on the learner's own previous choices.

  1. Wear-in: An arm may yield zero reward until a certain threshold of repetition is met within a sliding window.
  2. Wear-out: If an arm is played too frequently, the user develops fatigue, and the reward drops to zero.
Visualization of the wear-in and wear-out thresholds, defining the window of allowed repetitions in history.

Proposed Algorithms

To navigate these opposing behavioral effects, the paper introduces two novel algorithms:

WI-UCB (Wear-In UCB)

Designed for settings where only wear-in exists, WI-UCB employs a phase-based approach. Instead of switching arms every round, it plays an active arm for a block of time (a phase). This ensures the arm is played enough to overcome the wear-in period, allowing the algorithm to observe the true underlying reward.

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

To handle both wear-in and wear-out, the authors introduce compound arms. The algorithm plays a pair of arms with equal probability within a phase. This "compound arm" strategy provides enough "global" repetition to satisfy wear-in requirements for a category while providing enough "local" variety to prevent the user from reaching the wear-out threshold for any single specific item.

Theoretical Results

The primary contribution of this work is the proof that these algorithms achieve sublinear regret, meaning the learner's performance eventually converges to that of an optimal policy with prior knowledge of rewards.

Comparison of regret bounds for standard MAB algorithms and the proposed WI-UCB and WI/WO-UCB frameworks.

The regret bounds show that the "cost" of priming is additive. As time $T$ increases, the penalty for managing wear-in and wear-out becomes negligible compared to the standard cost of learning. Furthermore, the algorithms exhibit "graceful degradation": if there is zero priming effect, their performance bounds match standard algorithms like UCB1.

Discussion and Future Work

While the proposed framework provides a robust theoretical foundation for priming in MABs, several avenues for future research remain:

  • Parameter Estimation: Current algorithms require prior knowledge of the expected wear-in time $\mathbb{E}[D]$ and the history window $N$.
  • Reward Modeling: Moving from binary indicator functions to smoother reward curves would better reflect real-world user behavior.
  • Contextual Extensions: Integrating user features into a Contextual Bandit framework would enhance applicability in production systems.

This summary is based on the paper "Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect" presented at UAI 2020.

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, wher...
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},
}
Figure