A Sleeping, Recovering Bandit Algorithm for Optimizing Recurring Notifications

Kevin P. Yancey
kyancey@duolingo.com
Duolingo
Pittsburgh, Pennsylvania

ABSTRACT

Many online and mobile applications rely on daily emails and push notifications to increase and enhance user engagement. The multi-armed bandit approach provides a useful framework for optimizing the content of these notifications, but a number of complications (such as novelty effects and orientation) slightly make conventional bandit algorithms unsuitable in practice. In this paper, we introduce the Recovering Difference Softmax Algorithm to address the particular challenges of this problem domain, and use it to successfully optimize millions of daily reminders for the online language-learning app Duolingo. This led to a 0.5% increase in total daily active users (DAUs) and a 2% increase in new user retention over a strong baseline. We provide technical details of its design and deployment and demonstrate its efficacy through both offline and online evaluation experiments.

CCS CONCEPTS

Computing methodologies → Sequential decision making;
Mathematics of computing → Probability and statistics

KEYWORDS

Multi-Armed Bandits, Notification Content Optimization, Bayesian Approaches, Machine Learning

ACM Reference Format:

Kevin P. Yancey and Burr Settles. 2020. A Sleeping, Recovering Bandit Algorithm for Optimizing Recurring Notifications. In Proceedings of the 20th ACCD GLOBAL Conference on Database and Data Analysis (BDO 2020), August 23–27, 2020. Virtual Event, CA, USA, ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3394486.3403351

1 INTRODUCTION

To keep users engaged and promote recurring usage, many mobile and online apps send regular email and push notifications to their users. For Duolingo — the world's most-downloaded language-learning app with more than 300 million users — this involves sending daily practice reminder notifications, such as those shown in Figure 1.

The content of these notifications is generated from pools of hand-written templates (which may contain slots for user-specific information) from which a single template is chosen to generate the content of each notification.

The multi-armed bandit problem provides a well-studied theoretical framework for optimizing the selection of templates in this context. However, two complications arise that makes conventional bandit algorithms unsuitable for our scenario:

Fresh templates (which have not been recently seen) tend to have higher impact on user behavior. Thus, it is essential that the bandit algorithm not only choose templates that perform well in general, but also vary the selection of templates for each user over time in order to exploit this novelty effect. Otherwise, the bandit will converge to a template that does not adequately meet eligibility criteria.
The standard formulation of the multi-armed bandit problem assumes that all options are available at all times, and violation of this assumption complicates the evaluation of each option's notification.

1.1 Relay Bandit Problem

The multi-armed bandit problem is an optimization problem in which an agent repeatedly chooses from among a fixed set of arms over some number of rounds. Each round's reward is obtained based on the chosen arm. In our setting, the arms represent different notification templates and the rewards stem from user satisfaction. This results in a trade-off between exploration (choosing an arm to learn about its expected reward) and exploitation (choosing the best arm based on current information).

2 RECOVERING DIFFERENCE SOFTMAX ALGORITHM

We now describe the Recovering Difference Softmax Algorithm in detail. The algorithm works by learning and periodically updating a policy, π, that attempts to maximize future rewards based on historical observations. For each arm, a set of prior rounds when that arm was eligible is gathered, denoted Hₘ, where the reward and behavior policy are known. These historical rounds are used to evaluate the performance of each arm and build the policy π.

2.1 Sleeping Arms

Not all arms are available every round. This property complicates the problem because eligibility criteria can act as confounding variables regarding the reward. For example, if arm A is available only to highly active users, then its historical rounds may show much higher rewards. Hence, choosing the template with the highest average historical reward may yield poor results.

2.2 Small Sample-Size Arms

The estimated arm scores will have high variance for arms with small sample sizes, which can cause issues when these estimates are used to choose templates for future rounds. To regulate these scores, we use empirical Bayes estimation to shrink abilities towards a Bayesian prior. This improves the accuracy of the reward estimates over time.

2.3 Recovering Arms

We address the novelty effect by applying a recency penalty to an arm's score after it has been selected for a user. This penalty decreases as the user's memory of the previous notification fades, modeled with an exponential decay function.

2.4 Arm Selection

We use the softmax algorithm to define a policy to choose arms each round based on the computed arm scores. Specifically, we select an arm with a probability that is proportional to the exponential of its modified score.

3 EVALUATION

3.1 Offline Log Data Experiments

The offline experiments were conducted using historical data from the legacy system. We used different datasets to evaluate the performance of the bandit algorithm.

3.1.1 Offline Experiment 1: Incorporating UI Language

We evaluated the performance of templates across different user interface languages to observe variations in effectiveness. The results indicated substantial differences in performance across languages.

3.1.2 Offline Experiment 2: Estimating the Recency Penalty

We estimated the recency penalty and its effects on user engagement. Policies employing a recency penalty were found to outperform historical selection methods by a notable margin.

4 CONCLUSION

In this paper, we have introduced the Recovering Difference Softmax Algorithm, a novel and practical multi-armed bandit variant for optimizing recurring notifications. Our results show how relative difference scoring and recency penalties can effectively increase user engagement, demonstrating scalability to millions of users.