We consider how dynamic A/B experiments { used to discover and deploy policies for personalizing items { can be interpreted from the perspective of a recommendation problem, where no prior data is available. We present an illustrative data set we collected, to evaluate algorithms for recommending emails (that vary along dimensions like subject lines) that will maximize response rate, from di erent subgroups of online learners. This problem is formalized as a contextual bandit, and we do an o ine regret comparison of how standard bandit algorithms would perform in optimizing response rate. We report a system that provides an API for real{time data exchange and recommendation policy updates from algorithms from external machine learning researchers, and compare our best-performing o ine algorithm { Thompson Sampling { against a randomized policy.
Despite widespread applications of recommender systems,
the majority of algorithms researchers develop are
evaluated using o ine data. There are few opportunities to test,
in real-time, algorithms that choose item recommendations
with the goal of balancing exploitation (maximizing user
satisfaction) with exploration (testing out items in order to
improve the underlying model in the long-run, potentially
with short-term suboptimal performance). Even algorithms
tackling these exploration-exploitation problems often have
to use o ine data [
This poster aims to formulate sequential decision making in A/B experimentation in terms of a problem in personalized recommendation. The characteristics of this situation Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).
Copyright held by the owner/author(s) are atypical in most recommender systems, but arguably of interest in real{world applications. Optimal performance requires rst discovering which features of items make for good recommendations on average, and then further gains in optimization are achieved by personalizing item recommendation.
In addition to this formulation, the other contributions are: 1. Collecting a data set for o ine evaluation of algorithms for recommendation, that illustrates a problem at the intersection of dynamic A/B experimentation and recommendation. This involves recommending emails to MOOC participants that will maximize their response rate. 2. Our contextual bandit formulation of how to solve this email recommendation problem, and results from applying several standard bandit algorithms. 3. A system that allows online evaluation and comparison of algorithms for bandits/recommendation via an API that provides data and requests recommendations in real time 4. An online evaluation of the algorithm that performed best in our o ine evaluation { Thompson Sampling { against a random policy, by dynamically changing the policy for experimentation/recommendation, as each email is sent and each participant's response observed. 2.
The goal was to recommend emails that could be sent to participants, and maximize their response rate in providing feedback on an online course. In our email recommendation deployment, we chose three dimensions of the text of the email to change - subject line, introduction, body of email. Each of these three dimensions can be varied by writing di erent text. In this deployment, we chose to create three versions of each - three subject lines, three introduction messages, and three versions of the body of the email. This resulted in 27 unique email items, although any one dimension (with just three versions) could be analyzed independently (marginalizing over the others). This was because we designed the dimensions to be modular and randomized independently.
We consider just two user characteristics - user's age group (18-22, 23-26, 27-35, or 36 or older), and the number of days the user was active in the course (grouped as 0, 1, or 2 or more). While there are up to 50 other characteristics that are available about users, our preliminary analyses suggested these did not have substantial impact on which items would be recommended.
Following previous approaches for collecting a data set
useful for testing a range of approaches and policies [
E[PtT=1 rt;a].
The problem of how to make person by person dynamic
decisions about what email to recommend is formulated as
a contextual multi{armed bandit problem [
Formally, each step in a sequence is indexed by t from f1; 2; ::; T g, and furnishes a context vector xt, with the choice of an action a 2 A producing an observed reward rt;a.
The computational problem is to choose a sequence of actions fa1; a2; ::; aT g that maximize the expected reward
We consider each email dimension (subject line, introduction, body) as a separate contextual bandit, so we solve three contextual bandit problems.
For each contextual bandit, our approach is twofold,
following [
The reward rt;a 2 f0; 1g depends on each xt as well as the regression weights for action a, wa. We use Bayesian logistic regression, since this gives us distributions over the weight parameters that we can use in Thompson Sampling.
Second, given these models, use an algorithm for selecting
subsequent actions, which trades o maximizing response
rate against collecting data that will informatively update
the models. We compare Thompson Sampling [
To do Thompson Sampling, we use the posterior distributions over each wa. At each time step t: 1. For each a 2 A, sample wa. 2. Select argmax ra;xt
a 3. Observe reward ra;xt and update the posterior distribution on wa (Bayesian logistic regression).
To accomplish our goal of testing out these algorithms
on online data, we built a system that updates the policy
for recommending emails can be updated in real-time, after
each email is sent and data is received. This system was
constructed using the MOOClet framework, which enables
any A/B experimentation infrastructure to adapt policies
[
To compare alternative algorithms, which algorithm is called to provide a recommendation can itself be randomized, interleaving the algorithms as users are selected. This will enable the algorithms analyzed for this o ine data to be compared against each other in this real-time situation, as well as the evaluation of any other algorithm, from both the recommender systems and multi-armed bandits literature.
As a test deployment of our system, we compared the response rate of a new group of 1775 participants when recommended emails using a random policy (4.5%) against a heuristic that approximated Thompson Sampling (7.2%).
PROVIDES: For each of N participants, User Context Variables (Age Group, Number Days Active), Item Assigned (Email Subject Line, Introduction, Body), Response (0 or 1)
PROVIDES: User Context Variables (Age Group, Number Days Active) RETURNS: Item assignment (Email Subject Line, Introduction, Body)