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.
- Wear-in: An arm may yield zero reward until a certain threshold of repetition is met within a sliding window.
- Wear-out: If an arm is played too frequently, the user develops fatigue, and the reward drops to zero.
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.
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