Automated Mechanism to Choose Between Reinforcement
Learning and Contextual Bandit in Website Personalization
Abhimanyu Mitra

Afroza Ali

Xiaotong Suo

AMitra@walmartlabs.com
Walmart Labs
Sunnyvale, California

AAli@walmartlabs.com
Walmart Labs
Sunnyvale, California

Xiaotong.Suo@walmartlabs.com
Walmart Labs
Sunnyvale, California

Kailing Wang

Kannan Achan

Kailing.Wang@walmartlabs.com
Walmart Labs
Sunnyvale, California

KAchan@walmartlabs.com
Walmart Labs
Sunnyvale, California

ABSTRACTPersonalizing customer experience typically requires a range ofexperiments with an ever-changing content pool and evolving customer preferences. Since pure experimentation is costly, we need
an appropriate explore-exploit strategy to complement the personalization models and allow the models to perform the necessary
experimentation. If our goal in choosing the content for each customer is to get the best long-term value from them, our exploreexploit strategy should also aim to exploit for the same. With this
exploitation goal, the natural choice of an explore-exploit strategy
seems to be a reinforcement learning framework, which optimizes
for long-term rewards for every state (appropriate customer segment) of the relevant Markov chain. However, one of the crucial
challenges of a reinforcement learning framework is the limited
number of available trials from which it has to estimate the longterm reward for every state-content pair, since the content pool isconstantly changing. Since a good simulation model for customer
preferences is not available, it is costly to experiment with realcustomers by increasing the number of trials for the framework
to learn, potentially providing sub-optimal customer experiences.
On the other hand, if short-term rewards are indicative of longterm rewards, once learning is complete, a reinforcement learning
framework and a contextual multi-armed bandit [2, 7] framework(which uses the states of the Markov chain as context) might makevery similar choices of contents for each of the states. Moreover,since a contextual bandit framework tries to learn only short-term
reward as opposed to a long-term reward, the learning happens
faster. Thus, in some of the modules of the website, it might be morecost-effective to run a contextual bandit algorithm as an exploreexploit strategy, even when we want to optimize long-term reward
from our customers. We propose a framework which analyzes historical data on customer-content interaction to predict for each
module and content pool, which strategy would work best there:
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
IRS 2020, August 24, 2020, Virtual,© 2020 Association for Computing Machinery.
ACM ISBN 978-x-xxxx-xxxx-x/YY/MM. . . $15.00
https://doi.org/10.1145/nnnnnnn.nnnnnnn

reinforcement learning or contextual bandit. We show with empirical data that our framework predicts the correct explore-exploit
strategy with a high precision rate. Furthermore, our framework
quickly adapts its prediction even when the optimal explore-exploit
strategy changes with time within the same module.

CCS CONCEPTS• Mathematics of computing → Probabilistic inference problems; • Information systems → Personalization; • Appliedcomputing → electronic commerce.

KEYWORDS
Reinforcement Learning, Contextual Multi-Armed-Bandit, Website Personalization, Explore-Exploit.
ACM Reference Format:
Abhimanyu Mitra, Afroza Ali, Xiaotong Suo, Kailing Wang, and Kannan
Achan. 2020. Automated Mechanism to Choose Between Reinforcement
Learning and Contextual Bandit in Website Personalization. In Proceedings of 1st International Workshop on Industrial Recommendation Systems at
SIGKDD’20 (IRS 2020). ACM, New York, NY, USA, 9 pages. https://doi.org/
10.1145/nnnnnnn.nnnnnnn

1

INTRODUCTION

Website personalization requires redesigning the webpage according to the customers and their implicit or explicit preferences, whichtranslates to picking the right content from a pool of contents. These
contents could be the web modules which paint the page for thecustomer, or the contents/items/pictures that fill a web module. In
other words, we can think of personalization as choosing the rightcontent(s) for the free web slot(s) from a pool of contents, and if multiple slots are available for the same pool, for example, multiple slots
within the same module which could be filled with contents fromthe same pool, deciding the order of the chosen contents according
to customers and their implicit or explicit preferences. Typically,
personalization algorithms maximize a reward, for example, clicks
or revenue, which means the choice of contents or ordering of
the contents is driven by maximizing rewards for customers. As
opposed to chasing the maximum reward from customers in a single web session, there is an increasing interest in attaining higher
long-term customer value through personalizing the contents ofa webpage. In other words, there is an increasing interest in personalization algorithms that optimize long-term rewards from theIRS 2020, August 24, 2020, Virtual,customers, which can be computed by suitably aggregating current
session rewards with that of several future web sessions of the same
customer.
For a website, with time, the content pools for each of the web
slots keep changing and so do customer preferences. Therefore,predicting the right content for each customer requires the personalization algorithms to experiment with new contents to estimate
the reward associated with each of the customer-content pairs.
With a live website and the ever-changing content pools, it is impossible to run pure exploration as it is too costly. So we need an
explore-exploit strategy to complement our personalization algorithms in order to perform the necessary explorations. In such acase, the exploit part of an explore-exploit strategy should be designed to optimize a reward, which is similar to the reward that thecorresponding personalization algorithm optimizes. Thus, if a personalization algorithm is trained to optimize for long-term reward,
the corresponding explore-exploit strategy should do the same. A
natural explore-exploit strategy to exploit long-term rewards seems
to be a reinforcement learning framework [4] which traces influences of content shown to a customer by noting transformation of
the customer in future sessions and optimizes the choice of content
based on long-term rewards, where the long-term reward for eachcustomer-content interaction is computed by aggregating current
session rewards with discounted future session rewards from thesame customer.
To simplify the reinforcement learning framework, we assume
mutually exclusive customer segments are available to us, which
we could use as the states of the associated Markov chain. To makethe state space complete, we add two states, one is where a visiting
customer does not belong to any of the segments and anotherwhere the customer does not return to the website following a visit.
Though many research has shown how to build an appropriate state
space suitable for reinforcement learning framework, including
deep reinforcement learning networks, see for example [8], time
constraints force us to restrict ourselves to such a simplified version.
However, we believe the following discussion will be as relevant
even when the state space is more diligently and appropriately
constructed.
In the literature on Reinforcement Learning, the primary application is training computers to play games [3, 9–11], where they
are trained to anticipate several steps ahead in order to finally win
the game. In our application, we want to choose contents to get thehighest long-term rewards from our customers and this application
brings a few additional complications. In a game, the next step isobserved at a certain interval unless the game ends, whereas in ourapplication the next step only comes when the customer returns to
the webpage and therefore happens after a random time interval(if the customer never returns, which is also a possible state andonly after waiting for a long-enough interval, we would be able
to conclude if a customer’s state has changed to this one). So, inbuilding our reinforcement learning framework, this additionalrandomness needs to be accounted for. Moreover, when computers
are trained to play games, the learning phase involves computers
playing with each other and therefore, more trials for computers tolearn just means additional simulations. On the other hand, we do
not have a good simulation model to simulate customer-content interaction and our reinforcement learning framework can only learn

Mitra, Ali, Suo, Wang and Achanby trying contents with customers on a live website and therefore,
while the framework is learning, we are potentially providing thecustomers with a sub-optimal website experience, leading to a lot
more expensive trials.
Any explore-exploit strategy starts from pure exploration and as
it learns the rewards associated with each action for each context, it
starts to exploit. Thus, such a strategy can only bring benefits overa pure exploration strategy, once it has learnt enough. To get mostfrom the reinforcement learning framework, it first needs to learn
for each context, which content produces the highest long-term
reward. Since the learning happens with each trial, which is whena customer visits the webpage, we cannot expedite the process oflearning through simulation or other methods. Moreover, since
the content pool is only active on the webpage for a short time,
if the framework takes too long to learn, the same content poolmight no longer be active when the framework is ready to exploit.
Therefore, the need arises to figure out alternatives, which mightlearn faster and make similar content choices as the reinforcement
learning model would, once it had learnt the best action for eachstate. One such alternative is to rely on short-term rewards if therelative comparison of short-term rewards for different contents
in the content pool is very similar to that of long-term rewards.
For example, say, for each state, the content bringing the best longterm reward also brings in the best short-term reward. Then bothmethods would choose the same content once they are ready to
exploit. Relying on short-term rewards brings us to a contextual
multi-armed bandit model, where we use the states of the Markov
chain as contexts, which acts as the cheaper alternative compared
to enabling a reinforcement learning model, since it learns fasterbut is equally effective in this case. In fact, this could be a better
option since it wastes lesser time (and thus lesser bad customer
experiences throughout the exploration period) in learning which
actions work best in which context.
The choice of the two alternatives described above: the reinforcement learning model or the contextual multi-armed bandit model
as an explore-exploit strategy, depends on the content pool andthe set of states. Even if we are making the choice between thetwo models for the same web module, as the content pool changes
over time, the optimal choice could also change. Customers’ statesmight also change over time because of dynamic nature of theirpreferences. Therefore, even for the same web module, the optimal
choice could be changing over time. Of course, the choice could be
be different for two different modules on the same webpage. Therefore, we need an automated mechanism which crunches historical
data on customer-content interaction to predict at a regular interval(maybe every day) for each of the web modules, given their current
content pools, which explore-exploit strategy is more appropriate
for the module. Similarly, if we are using an explore-exploit strategy to choose and rank web modules on a webpage, the automatedmechanism should predict for each of the webpages, given its current set of possible web modules, which model is more appropriate:
reinforcement learning or contextual multi-armed bandit.
In this paper, we describe how we build such an automatedmechanism. In Section 2, we show how the automated mechanism
works. In Section 3, we present empirical results. In Section 4, weconclude with future research.

Automated Mechanism to Choose Between Reinforcement Learning and Contextual Bandit in Website Personalization

2 METHOD
2.1 Motivation
To motivate the use of enabling a Reinforcement Learning (RL)
framework to complement a Contextual Multi-Armed-Bandit(CMAB),
we first describe how these two frameworks are used in website
personalization. For every customer visit, personlization models
generate a list of eligible content candidates per module and CMAB
or RL framework ranks the final contents before it is renderedon the web module. This system renders content for every module on the homepage and item pages. A CMAB framework makes
the exploration-exploitation balance separately for each context.
Customers have been grouped based on their interactions withthe website and other relevant activities, and we use them as contexts for the CMAB framework. For example, a customer who haveshown strong affinity towards technology products, are grouped
under ‘Tech’ customer segment, and an another customer, identified
to be part of busy families, is classified as ‘Busy Families’ etc. The
short-term reward function, which the CMAB framework tries toestimate and optimize, could be engagement metrics such as clicks
on the web module, or conversion metrics if the customer purchases products featured in the web module. However, the fact that
CMAB framework never takes a long-term view or connects customer activities over multiple web sessions can lead to inaccurate
results. For example, suppose it is established through statisticallysignificant metrics that ‘Busy families’ customers are less likely
to engage in a ‘Tech’ content and therefore, in this case, a CMAB
framework never shows ‘Tech’ content to customers identified as‘Busy families’. This choice might be myopic if there is a probability
that a ‘Busy families’ customer if presented with ‘Tech’ content,
might get interested in ‘Tech’ products and thus transform to a
‘Tech’ customer in future. An RL framework mitigates this problem
by connecting multiple web sessions of the same customer and also
incorporating the influence of contents in transitioning a customer
to belong to a different group/context in some future web session
into the model. Thus, an RL model forego some short-term rewards(say, in-session engagement) in the hope of getting higher rewards
in future.

2.2

Detailed description of our method

We now formally introduce our notation. We denote the customer
groups as the states of a Markov chain {𝑆 1, 𝑆 2, · · · , 𝑆𝑛 }, and assume
that a customer can only belong to one state at a given time. For eachstate, action space consists of eligible contents; i.e., for each state
𝑆 𝑗 , 𝑗 = 1, 2, · · · , 𝑛, there are possible actions {𝐶 𝑗,1, 𝐶 𝑗,2, · · · , 𝐶 𝑗,𝐾𝑆 𝑗 },where 𝐾𝑆 𝑗 is the total number of eligible candidate contents forthe state 𝑆 𝑗 . Short-term reward function can be clicks on the web
module, or conversion metrics. In details, if the short-term reward
function is defined as clicks on the web module, and if the current state of a customer is 𝑆𝑖 , 𝑖 ∈ {1, 2, · · · , 𝑛}, when (s)he visits
webpage and sees impression, the short-term reward 𝑟𝑖 is 1 if (s)heclicks on the module impression and 0 otherwise. To calculate thelong-term reward associated with the impression, we need to track
the customer over future sessions and the rewards on the module
impressions from those sessions. Suppose the customer comes backafter 𝑘 1 < 𝑘 2 < · · · days from when (s)he first saw the impression

IRS 2020, August 24, 2020, Virtual,and in those future web sessions, (s)he sees the module impressions 𝑖𝑘1 , 𝑖𝑘2 , · · · in the chronological order and the corresponding
rewards to the module impressions 𝑖𝑘1 , 𝑖𝑘2 , · · · are 𝑟𝑖𝑘1 , 𝑟𝑖𝑘2 , · · · respectively, then the long-term reward of the impression can becomputed as𝑞𝑖 = 𝑟 𝑖 + 𝛾 𝑘 1 𝑟 𝑖 𝑘 1 + 𝛾 𝑘 2 𝑟 𝑖 𝑘 2 + · · · ,(1)where 0 < 𝛾 < 1 is a fixed discount factor used to discount future
rewards. To approximate the infinite series, we ignore terms when
the discount factor becomes small enough, say less than 𝜖, where 𝜖
is a positive number. Let 𝑇 be the smallest integer so that 𝛾 𝑇 < 𝜖.
Then for all 𝑘𝑛 > 𝑇 , 𝛾 𝑘𝑛 < 𝜖. Let 𝑚 be the largest integer so that𝑘𝑚 ≤ 𝑇 . Then, 𝑞𝑖 in (1) could be approximated as𝑞𝑖 = 𝑟𝑖 + 𝛾 𝑘1 𝑟𝑖𝑘1 + 𝛾 𝑘2 𝑟𝑖𝑘2 + · · · + 𝛾 𝑘𝑚 𝑟𝑖𝑘𝑚 .

(2)

The short-term reward 𝑟𝑖 and long-term reward 𝑞𝑖 for each impression could be averaged over the state, action pairs to obtainaverage short-term reward 𝑅(𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and average long-term reward 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) for each state, action pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ). Using these
average estimates, we could approximate 𝑞𝑖 in (1) using one-step
updates𝑞𝑖 = 𝑟𝑖 + 𝛾 𝑘1 𝑄 (𝑆𝑖𝑘1 , 𝐶𝑖𝑘1 ,𝑖𝑘1 ),(3)

where 𝑆𝑖𝑘1 is the state of the customer when (s)he returns first timeafter 𝑘 1 days and views impression 𝑖𝑘1 and 𝐶𝑖𝑘1 ,𝑖𝑘1 is the chosencontent for the module impression 𝑖𝑘1 .
In the CMAB framework, all we need is to update the short-term
reward 𝑅(·, ·) by simply including new impressions in the average.
In the RL framework, we use (3) to estimate long-term reward associated with each impression. It is an online learning framework
where we begin with an initialization 𝑄 (·, ·) ≡ 𝑅(·, ·) and as more
impressions come in (potentially customers come back), we update
the long-term rewards associated with each impression using (3)and then average over state-action pairs to update estimates of𝑄 (·, ·). As we collect more data and 𝑅(·, ·) and 𝑄 (·, ·) are averages
over a lot of impressions, by Central Limit theorem, we could assume they would follow Normal distribution and the variance of theNormal distribution could be estimated via the short-term rewards
𝑟𝑖 -s associated with each impression and long-term rewards 𝑞𝑖 -s
associated with each impression (approximated via (3)).
For each state 𝑆 𝑗 , 𝑗 = 1, 2, · · · 𝑛, the CMAB framework allocates impressions to {𝐶 𝑗,1, 𝐶 𝑗,2, · · · , 𝐶 𝑗,𝐾𝑆 𝑗 } in proportion to estimated 𝑅(𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and the RL framework allocates impressions
to {𝐶 𝑗,1, 𝐶 𝑗,2, · · · , 𝐶 𝑗,𝐾𝑆 𝑗 } in proportion to estimated 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ).
However, adapting this to other mechanisms of resolving exploreexploit dilemma like Thompson sampling [1, 6] follows similar
steps. For example, we can run simulations to figure out impression
allocation using any mechanism resolving explore-exploit dilemma,
as long as the mechanisms are solely reliant on distributions of𝑅(𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ), 𝑗 = 1, 2, · · · , 𝑛, 𝑘 = 1, 2, · · · , 𝐾𝑆 𝑗 .
For each state 𝑆 𝑗 , 𝑗 = 1, · · · 𝑛, note that the only way these twoframeworks resulting in different customer experiences is throughallocating different impressions to contents {𝐶 𝑗,1, 𝐶 𝑗,2, · · · , 𝐶 𝑗,𝐾𝑆 𝑗 }.
Therefore, to compare the impact of a RL framework over CMAB
framework, we need to figure out how these different impression
allocations are bringing in different total long-term rewards. In

IRS 2020, August 24, 2020, Virtual,

Mitra, Ali, Suo, Wang and Achanabsence of an A/B test, all we have is historical data of impressions and their short-term rewards. We divide the historical impression data in training and evaluation period so that chronologically the evaluation period comes after the training period. From
the training data we estimate 𝑅(·, ·) and 𝑄 (·, ·) and assume thatin the evaluation period, for each 𝑆 𝑗 , our CMAB framework allocates impressions to {𝐶 𝑗,1, 𝐶 𝑗,2, · · · , 𝐶 𝑗,𝐾𝑆 𝑗 } in proportion to theestimated 𝑅(𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and our RL framework allocates impressions
to {𝐶 𝑗,1, 𝐶 𝑗,2, · · · , 𝐶 𝑗,𝐾𝑆 𝑗 } in proportion to estimated 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ).
To connect the impression allocations with the total reward,
we need to know the average long-term reward per impression
associated with each state-action pair in the evaluation period.
To estimate that, we use the long-term reward estimate of each
impression in the evaluation period using (2) and then average them
¯ 𝑗 , 𝐶 𝑗,𝑘 ) for each state-action
over the state-action pairs to get 𝑞(𝑆¯ 𝑗 , 𝐶 𝑗,𝑘 ) is also an average, the distribution
pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ). Since 𝑞(𝑆¯ 𝑗 , 𝐶 𝑗,𝑘 ) could be approximated by Normal distribution andof 𝑞(𝑆the variance can be estimated using the 𝑞𝑖 -s associated with each
impression, as given in (2).
Let 𝑊 𝑅 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) denote the number of allocated impressions
to 𝐶 𝑗,𝑘 in state 𝑆 𝑗 using our CMAB framework and 𝑊 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 )denote the same using our RL framework. Note that the condition
ÍÍ𝑅𝑄𝑘 𝑊 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) =𝑘 𝑊 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) must be satisfied for all 𝑆 𝑗 ,since total impressions to state 𝑆 𝑗 in the evaluation period is fixed.
Let us also denote the total rewards associated with a CMAB framework 𝑇 𝑅 and a RL framework 𝑇 𝑄 in the evaluation period could becomputed as
𝑇𝑅 =

ÕÕ
𝑗

𝑇𝑄 =

(4)

¯ 𝑗 , 𝐶 𝑗,𝑘 ).
𝑊 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 )𝑞(𝑆

(5)

𝑘

ÕÕ
𝑗

¯ 𝑗 , 𝐶 𝑗,𝑘 )𝑊 𝑅 (𝑆 𝑗 , 𝐶 𝑗,𝑘 )𝑞(𝑆𝑘Therefore the improvement in total reward from our RL framework over our CMAB framework could be computed as (𝑇 𝑄 −𝑇 𝑅 )/𝑇 𝑅 . We can also estimate the noise of this measured lift fromsimulation. As noted before, the estimates of 𝑅(𝑆 𝑗 , 𝐶 𝑗,𝑘 ), 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 )¯ 𝑗 , 𝐶 𝑗,𝑘 ) all follow Normal distribution with known meanand 𝑞(𝑆and standard deviation. In each run of the simulations, we can¯ 𝑗 , 𝐶 𝑗,𝑘 ) from their respecsimulate 𝑅(𝑆 𝑗 , 𝐶 𝑗,𝑘 ), 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and 𝑞(𝑆tive distributions. Using these simulated numbers, we can obtain
𝑊 𝑅 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and 𝑊 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ), and then calculate 𝑇 𝑅 and 𝑇 𝑄 and
thereafter get a lift. Each simulation run gives us one estimated lift.
Therefore, from multiple simulations, we can obtain the estimatedlift through averaging as well as the noise associated with it.

2.3

Design Overview

The explore exploit system is tightly weaved into our personalization platform. The end-to-end system is illustrated in the figure 1.
It comprises of 2 main components:
2.3.1 Optimal strategy selection and Model parameters estimation.
We have built a complex evaluation system that comprises of asuit of frameworks to evaluate different reward strategies( global,
contextual or RL) and pick the optimal strategy for each module
independently . These module specific strategy recommendations

are then used by specific parameter estimation models, to estimate
the parameters of the reward functions for different modules.
2.3.2 Content candidates selection & Ranking. This is a real-timesystem that uses customer and content features to dynamicallyselect a pool of eligible content candidates. Using the explore exploit
reward parameters estimation for each of them , it ranks them inthe descending order of their posterior probability weights. This
final ranked list of content candidates for each recommendations
module goes to the front end for rendering on customers’ devices.

3 EXPERIMENTAL RESULTS
3.1 Setup
The offline evaluation framework predicts optimal reward strategy
and is capable to evaluate for rewards based on user engagement,
conversion or revenue – in this implementation, we have used clickas the reward. For each module, the mean rewards are estimated foreach pair of customer context as state, say 𝑆 𝑗 and content candidate
as action, say 𝐶 𝑗,𝑘 denoted by (𝑆 𝑗 , 𝐶 𝑗,𝑘 ).
We maintain a daily update model for customer segmentation.
It uses customers’ activity data and content level features to assign
each customer to a segment or context. The model learns their
evolving behavior, and update their segments/context daily.
The framework independently makes daily predictions of optimal strategy for different recommendation modules. Each prediction involves 2 chronological steps – training period and evaluation
period.
3.1.1 Training Period. In this implementation, the evaluation framework uses historical click and impression data generated across several customers visits on the website. Our back end system records
every click and visit data for each recommendation module and aggregates them for each day separately. During each training period
which comprises of several training days, CMAB and RL models
consume this data to update the model reward estimations for allstate-content pairs (𝑆 𝑗 , 𝐶 𝑗,𝑘 ).
CMAB based model estimates the parameters of the distributionof the mean short-term rewards function 𝑅(·, ·) for every statecontent pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ), each of which is approximated by a Normal
distribution. For estimating long-term rewards, RL based model
updates the parameters of the distribution of 𝑄 (·, ·), which is again
approximated by Normal distribution for every state-content pair
(𝑆 𝑗 , 𝐶 𝑗,𝑘 ).
RL based model computes discounted long-term rewards foreach repeat visit by a returning customer and updates the rewardsof the last impression by the same customer using (3). For eachstate-content pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ), these updated rewards are used to
update the parameters of the distribution of 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ). Initially,
𝑄 (·, ·) will be very similar to short-term reward distributions 𝑅(·, ·),however overtime, as the customers come back to the website, it
updates 𝑄 (·, ·) with average discounted long-term rewards. We
use the posterior sampling method called Thompson sampling toresolve the explore-exploit dilemma for both CMAB and RL basedmodels.
Ideally the discounted long-term rewards can be awarded toinfinitely long window of time in the past. Customers impressions

Automated Mechanism to Choose Between Reinforcement Learning and Contextual Bandit in Website Personalization

IRS 2020, August 24, 2020, Virtual,

Figure 1: End-to-end design scheme of personalized online recommendation system. Its comprises of 3 main components,a)Evaluation framework for predicting the most reward generating model(CMAB/RL) per recommendation module, b)Modelparameters estimation used for parameters estimation for each module based on the recommendation by the evaluation framework, c)Content Candidates Generation that extracts eligible content candidates using personalized models and select andorder the final recommendations using RL/CMAB model parameters.
from months or years ago can be used to update the reward estimations of state-content pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ). However, e-commerce
world customers’ preferences evolve and content space is changing quickly, long-term rewards beyond a certain window of time
becomes insignificant or unimportant. To address this, the evaluation framework uses (2) and defines parameter T, which represents
the window of time up to which the model computes discounted
long-term rewards. The choice of the value of T may vary acrossdifferent products and recommendation modules. It may also be
impacted by how fast the content candidate pool changes, as wellas on the definition of the reward function.
We use an exploration-biased modified Thompson Sampling as
our impression allocation strategy for both RL and CMAB, where
after sampling from posterior distributions of rewards, instead ofsorting and picking the action/content with the highest sample,

we use weighted random sampling using the generated samples
as weights to pick the content. As an approximation of this impression allocation strategy, we can assume CMAB and RL models
following this impression allocation strategy would allocate impressions to content space {𝐶 𝑗,1, 𝐶 𝑗,2, · · · , 𝐶 𝑗,𝐾𝑆 𝑗 } in proportion totheir reward functions 𝑅(𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) respectively. For
each state-content pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ), the evaluation framework computes impression allocation weight, 𝑊 𝑅 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) for CMAB and𝑊 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) for RL model.
3.1.2 Evaluation Period. For a given recommendation module, theaim of the evaluation framework is to select the model that maximizes expected cumulative long-term reward. The long-term reward is optimal when the model estimates higher impression allocation for state-content pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) with larger average long-term

IRS 2020, August 24, 2020, Virtual,

Figure 2: An example of training and evaluation period with
T set to 7 and prediction date is April 28th 2020. The evaluation framework uses Jan 1st to April 13th as the training
period to learn the impression allocations 𝑊 𝑅 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and𝑊 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) for each state-action pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) for CMAB
and RL respectively. Following that, it runs the evaluation
period from April 14th to April 27th to compute the average
long-term rewards for every state-content pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ). It
updates the long-term reward using (2) for every impression
in the lockdown period between April 14th to April 20th.

reward. The evaluation period consists of impression lock down
window and T days rolling window. Using every impression in thelock down window, the framework computes the average long-term
reward for every state-action pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) using (2). An impression lock down window could be few days, in this implementation
we have used 1 week following the training period. All the impressions in the impression lock down window uses T days of rolling
window, where the value of T is the same as used in training the RL
model. Each customer impression in the lock down period receives
discounted long-term reward when the same customer shows up
again during the rolling window period. For each state-action pair
(𝑆 𝑗 , 𝐶 𝑗,𝑘 ), these long-term rewards are then used to estimate pa¯ 𝑗 , 𝐶 𝑗,𝑘 ), which is approximatedrameters of the distribution of 𝑞(𝑆by a Normal distribution.
In this implementation, the total time window for the evaluation
period is one week + T days.
Note that, using the impression allocation weights 𝑊 𝑅 (𝑆 𝑗 , 𝐶 𝑗,𝑘 )and 𝑊 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) from the training period, and average long-term¯ 𝑗 , 𝐶 𝑗,𝑘 ) for each state-content pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ), the evalreward 𝑞(𝑆uation framework computes the expected cumulative long-term
reward estimates by CMAB and RL models using (4) and (5) respectively. To estimate noise associated with them, the evaluation
framework runs thousands of simulations – in each simulation,¯ 𝑗 , 𝐶 𝑗,𝑘 ) from their
it samples from 𝑅(𝑆 𝑗 , 𝐶 𝑗,𝑘 ), 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and 𝑞(𝑆respective Normal distributions to compute 𝑇 𝑅 and 𝑇 𝑄 . Using the
𝑇 𝑅 and 𝑇 𝑄 from each simulation, we could estimate the average
lift (𝑇 𝑄 − 𝑇 𝑅 )/𝑇 𝑅 as well as the noise associated with the lift.
The evaluation framework chooses the model that generates
largest expected cumulative long-term reward. Each point in thetime series in Fig 4 and 5 are the average cumulative long-term
rewards 𝑇 𝑅 and 𝑇 𝑄 .

3.2

Performance

3.2.1 Prediction. The day following the evaluation period is theprediction day. The evaluation framework predicts the optimal
reward strategy using impression allocations estimated in the training period and estimated average long-term reward for each statecontent pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) in the evaluation phase.

Mitra, Ali, Suo, Wang and Achan

Figure 3: To generate the ground label strategy on April 28th,
the evaluation framework used all the click-impression datafrom Jan 1st to April 27th and estimates the impression allocations for each state-action pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) for CMAB and
RL models. It then estimates the average long-term reward
for state-action pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) using the all the impressions in
the impression lock down window, which is the prediction
day and T days sliding window for each impression.

Figure 4: Time series plot of the daily prediction made by theevaluation framework for module A during Sept/Oct time
window. In the graph, for each prediction date we have plotted logarithm of average cumulative long-term rewards 𝑇 𝑅
and 𝑇 𝑄 for CMAB and RL. The blue curve represents expected total long-term rewards by RL model. The orange
curve represents expected total long-term rewards by CMAB
model. Optimal strategy prediction by the evaluation framework is shown by the red curve. The evaluation frameworktakes the expected cumulative long-term reward of the predicted optimal strategy. During this time window, the prediction curve often overlaps with 𝑇 𝑄 shown by blue curve.
For this analysis the value of the parameter T is set as 7.
3.2.2 Prediction Accuracy. To measure the prediction accuracyof the evaluation framework, we need the ground truth labels for
optimal strategy. The optimal strategy, on a given day, is the one thatgenerates maximum expected cumulative long-term reward. We
use (4) and (5) to compute expected cumulative long-term reward
estimation for CMAB and RL models, and then pick the maximum.
For ground truth labels, we first need to estimate how RL and
CMAB models would allocate impressions on the prediction day.
For each state-action pair (𝑆 𝑗 , 𝐶 𝑗,𝑘 ), we use the historical data up
to the prediction date in order to estimate the impression allocations 𝑊 𝑅 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) and 𝑊 𝑄 (𝑆 𝑗 , 𝐶 𝑗,𝑘 ) as the impression allocation
recommended by CMAB and RL strategy respectively. It locks all
the impressions on the prediction date to compute the long-term
reward for each of them using (2) with a sliding window of T days
¯ 𝑗 , 𝐶 𝑗,𝑘 ).
and averages them over the state-action pair to estimate 𝑞(𝑆After that, as mentioned earlier, we use (4) and (5) to estimate 𝑇 𝑅

Automated Mechanism to Choose Between Reinforcement Learning and Contextual Bandit in Website Personalization

IRS 2020, August 24, 2020, Virtual,

Table 1: Overall Prediction Accuracy for Module A
T value[𝑑𝑎𝑦𝑠]
57
10
12
14
Figure 5: Time series plot of the daily prediction made by theevaluation framework for module A during Nov/Dec time
window. In the graph, for each prediction date we have plotted logarithm of average cumulative long-term rewards 𝑇 𝑅
and 𝑇 𝑄 for CMAB and RL. The blue curve represents expected total long-term rewards by RL model. The orange
curve represents expected total long-term rewards by CMAB
model. Optimal strategy prediction by the evaluation framework is shown by the red curve. The evaluation frameworktakes the expected cumulative long-term reward of the predicted optimal strategy. During this time window, the prediction curve often overlaps with 𝑇 𝑅 shown by orange curve.
For this analysis the value of the parameter T is set as 7.

November/December time window. For different values of T weanalysed the prediction accuracy on the two data sets separately.
Table 2 summarizes the prediction accuracy at different T values for the September/October window and November/December
window separately. During this window, the expected cumulative
long-term reward estimations for RL and CMAB are similar, as themodel training was bootstrapped in early September. During thiswindow, the reward estimations by both the models are somewhat
noisy and unstable.
Table 2: Prediction Accuracy for different dataset windows
for Module A
T value[𝑑𝑎𝑦𝑠]
5
7
10
12
14

and 𝑇 𝑄 as total rewards associated with the strategies CMAB andRL respectively and pick the model corresponding to the maximum
expected cumulative long-term reward as the ground truth label.
Fig.4 shows the time series plot of the daily prediction made by
the evaluation framework for module A during September/Octobertime window. In the graph, for each prediction date we have plotted
logarithm of average cumulative long-term rewards 𝑇 𝑅 and 𝑇 𝑄
for CMAB and RL. Optimal strategy prediction by the evaluation
framework is shown by the red curve. In our implementation, we
make the evaluation framework take the expected cumulative longterm reward of the predicted optimal strategy. During this window,
the prediction curve often overlaps with RL 𝑇 𝑄 shown by orange
curve. For this analysis the value of the parameter T is set as 7.
Fig.5 shows the time series plot of predictions made by the evaluation framework on Module A during November/December time
window. The orange CMAB expected cumulative long-term reward
𝑇 𝑅 curve is often overlapped by the red evaluation framework
prediction output.

3.3

Prediction Accuracy at different T values

The significance of T is to define how long in the future the model
will consider in order to estimate the optimal long-term rewards.
In our analysis we observed that different value of T may impact
prediction accuracy. Table 1 shows the prediction accuracy of evaluation framework over the entire data set of 3 months on module
A for different values of T.
During the course of our analysis, there were several changes tothe underlying distribution of customer-content interactions space.
To understand how changes in customer traffic and constantly
changing content pool affect prediction accuracy, we divided theentire data set into 2 parts – September/October time window and

Accuracy
[%]
80.0
67.9
71.7
69.2
60.3

Sept/Oct Window
[%]
74.7
54.1
55.5
50.0
55.8

Nov/Dec Window
[%]
87.0
91.1
94.0
85.0
78.4

For the November/December time window, the prediction accuracy for module A is much more improved across every valueof T. During this time, there was a significant increase in overall
traffic, with 30% traffic contributed by new customers who were
not mapped to any customer segment. As any prediction model
performance depends on the richness of its training dataset, we
believe this additional data is the reason for improved prediction
accuracy in November/December time window.

3.4

RL predictability Analysis

Besides prediction accuracy, we wanted to understand how accurately the evaluation framework predicts RL strategy in a nonstationary customer-content space. The ground truth labels in theNovember/December dataset were almost all CMAB. This was contributed by three main factors that changed the underlying data
distributions – overall increase in customer footprint across thewebsite, with significant increase in the new customers traffic thatbelonged to no known context. Secondly, there was a drastic increase in the content pool across different contexts and lastly the
evolving customers’ behavior. Examining the customers activities
at the context level, we observed the niche customer segments lostlarge portion of impressions, while there was a huge increase incustomers activities towards few popular contexts. The average
RL based reward estimations for these smaller customer segments

IRS 2020, August 24, 2020, Virtual,

Mitra, Ali, Suo, Wang and Achan

Figure 6: Time series plot of the lift calculated using (𝑇 𝑄 −𝑇 𝑅 )/𝑇 𝑅 on module A for September/October time window.
The blue curve shows the lift with respect to baseline CMAB
model.
grew significantly smaller in comparison to the estimations in September/October dataset.
For the September/October dataset, optimal policy labels andevaluation system predictions were skewed towards CMAB. We
evaluated the prediction output as a RL classification problem andobserved average precision as about 30% across all T values. On further examining the reward distributions and optimal policy at theindividual context level, the average RL precision rate was above
70% across different T values . This led to a realization that there
may exist few dominating contexts that may favor the optimal policy to maximize their reward estimations. Our website receives alarge proportion of new customers as well as inactive customers
who haven’t visited in past few months. They together form the‘unknown’ customer segment. This customer segment consistently
favored CMAB. Hence we filtered them out to re-evaluate RL predictability.
Table 3 shows the precision recall evaluation for RL strategy
predictions for the September/October dataset after filtering out the’unknown’ customer segment. The RL strategy prediction accuracy
significantly improved.
Table 3: Precision Recall Analysis for RL prediction on Module A after filtering unknown context customers
T value[𝑑𝑎𝑦𝑠]
5
7
10
12
14

3.5

Precision
[%]
89.33
84.9
87.81
88.43
87.02

Recall
[%]
1.0
1.0
1.0
1.0
1.0

Context level prediction of optimal reward
strategy

At the module level, the evaluation framework uses a greedy approach to predict optimal reward strategy. It is driven by the popular customer contexts/states which have either higher expected
rewards or larger customer footprint, or both. In our analysis weobserved that when these prominent customer segments favored

Figure 7: Time series plot of the lift calculated using (𝑇 𝑅 −𝑇 𝑄 )/𝑇 𝑄 on module A for November/December time window.
The blue curve shows the lift with respect to baseline RL
model.

Figure 8: Plot of prediction accuracy for optimal policy
prediction at the (global) module level compared to at thestate/context level across different values of T

short-term reward strategy(CMAB), the evaluation framework (andthe ground truth) also inclined towards them. In such scenarios,
few customer segments/states influence the reward strategy forother smaller and niche customer segments/states. Overtime, thismay negatively impact content discovery and exploration, leading
to sub-optimal expected long-term reward. What if the optimal
reward strategy for a recommendation module is decided at thecustomer’s context or state instead for all customer contexts collectively. By doing that we make very personalized decision at thecustomer’s current state and serve the most relevant recommendation using the optimal reward strategy. In our initial experimentto predict optimal reward strategy at the customer context/state,
we have observed higher prediction accuracy than at the global
level which we refer as module level. Fig.8 shows the graph withprediction accuracy for different customer contexts and the module
level prediction accuracy.

4

CONCLUSION AND FUTURE WORKIn this paper, we presented a novel evaluation framework to automate the choice between RL and CMAB as the impression allocation
strategy in an e-commerce setting where both customers’ behaviors and content pool are assumed to be non-stationary. While one
might be tempted to assume that long-term reward optimization

Automated Mechanism to Choose Between Reinforcement Learning and Contextual Bandit in Website Personalization

using RL is optimal, our results indicate that there are certain scenarios where CMAB is better suited to reap long-term returns. As
is evident, an appeal of our model is its dynamic nature and the factthat it is fully automatic, completely driven by data. Our system isdeployed in production in one of the top e-commerce portal, and isable to handle web scale traffic (millions of impressions on a daily
basis) with significant impact to financial metrics.
The trade off between exploration and exploitation is generally
complex, and a general solution for non-stationary environments
is largely an open problem. RL algorithms learn reward associations with respect to their action space, and by nature they are well
suited for stationary environments. Any decoupling or reversal
from learnt associations takes longer and requires plenty of data.
In our experience, the use of annealing parameter to discount rewards helped with learning new associations rapidly. Nevertheless,considering the dynamic nature of the environment as an input
to the model is a ripe area for future research. Perhaps there has
been studies that indicate that humans are willing to explore morewhen the amount of time left in a game or task is small(and not theearned reward at that point in time) with the hope that they will
uncover to eventually exploit [5].
In the current implementation, the evaluation framework predicts the optimal strategy using the expected rewards across allunderlying contexts. It is worth mentioning that while using CMAB
and RL, in several cases we observed significant variance of rewards
in the underlying bandits, there were a few contexts that offeredhigher rewards (with low noise estimates). If the optimization strategy is purely driven by the expectation over contexts, it is possible
to end up with sub-par performance at the context level. An area
ripe for further research is to select the strategy that is optimal fora context or more generally to a cohort of contexts. Additionally, itleads to a deeper question, what makes a good representation for acontext, and can we learn rich high-dimensional representation ofa context.

REFERENCES[1] Shipra Agrawal and Navin Goyal. 2011. Analysis of Thompson Sampling forthe multi-armed bandit problem. CoRR abs/1111.1797 (2011). arXiv:1111.1797
http://arxiv.org/abs/1111.1797[2] Shipra Agrawal and Navin Goyal. 2012. Thompson Sampling for Contextual
Bandits with Linear Payoffs. CoRR abs/1209.3352 (2012). arXiv:1209.3352 http://arxiv.org/abs/1209.3352[3] Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. 2018.
Efficient Exploration through Bayesian Deep Q-Networks. 2018 Information
Theory and Applications Workshop (ITA) (2018).
[4] Richard S. Sutton; Andrew G. Barto. 1998. Introduction to Reinforcement Learning.
MIT Press.
[5] Laura Carstensen, Derek Isaacowitz, and Susan Charles. 1999. Taking time
seriously: A theory of socioemotional selectivity. The American psychologist 54(04 1999), 165–81. https://doi.org/10.1037//0003-066X.54.3.165[6] Olivier Chapelle and Lihong Li. 2011. An empirical evaluation of thompson
sampling. In Advances in neural information processing systems. 2249–2257.
[7] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. 2010. A ContextualBandit Approach to Personalized News Article Recommendation. CoRR
abs/1003.0146 (2010). arXiv:1003.0146 http://arxiv.org/abs/1003.0146[8] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis
Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013. Playing Atari with
Deep Reinforcement Learning. Arxiv preprint arXiv:1312.5602 (2013).
[9] Brendan O’Donoghue, Ian Osband, Remi Munos, and Vlad Mnih. 2018. The Uncertainty Bellman Equation and Exploration. Proceedings of the 35th International
Conference on Machine Learning (2018).
[10] Ian Osband, John Aslanides, and Albin Cassirer. 2018. Randomized Prior Functions
for Deep Reinforcement Learning. Proceedings of the 32nd International Conference
on Neural Information Processing Systems (2018), 8626–8638.

IRS 2020, August 24, 2020, Virtual,[11] Ian Osband, Benjamin Van Roy, Daniel J. Russo, and Zheng Wen. 2017. Deep
Exploration via Randomized Value Functions. Arxiv preprint arXiv:1703.07608(2017).