In the CLEF NewsREEL 2017 challenge, we build a delegation model based on the contextual bandit algorithm. Our goal is to investigate whether a bandit approach combined with context extracted from the user side, from the item side and from user-item interaction can help choose the appropriate recommender from a recommender algorithm pool for the incoming recommendation requests. We took part in both tasks: NewsREEL Live and NewsREEL Replay. In the experiment, we test several bandit approaches with two types of context features. The result from NewsREEL Replay suggests that delegation model based on the contextual bandit algorithm can improve the click through rate (CTR). In NewsREEL Live, a similar delegation model is implemented. However, the delegation model from NewsREEL Live is trained by the data stream from NewsREEL Replay. This is due to the fact that the low volume of data received from the online scenario is not enough to support the training of the delegation model. For our future work, we will add more recommender algorithms to the recommender algorithm pool and explores other context features.
The CLEF NewsREEL Challenge [
Our work was initially inspired by Lommatzsch and Albayrak, who, in their
work [
However, our consideration is not directly related to news items, but the recommender algorithms. Given the e ective recommender algorithms from previous years, we believe the contextual bandit algorithm is able to combine them in a wise way and ultimately improve the recommendation performance. Our research interest comes with the assumption that given the context of a user, item and user-item interaction, contextual bandit algorithms can help choose appropriate recommender algorithm for each recommendation request and thereby improve the CTR.
This paper is structured as follows: in Section 2, we discuss the work related to the contextual multi-armed bandit algorithm. In Section 3, we introduce the method that we implemented in this work. Section 4 describes our evaluation methods, including NewsREEL Replay and NewsREEL Live. In Section 5, we analyze the evaluation results. In the last section, we summarize the results and discuss future work. 2 2.1
epsilon-Greedy Epsilon-Greedy is the simplest algorithm to solve the
multiarmed bandit problem. The only parameter in the model is . In the standard
settings, is xed. With probability 1 , the policy plays the currently best
arm, and with probability , it plays a random arm. The algorithms also have
several variations, e.g., -decreasing in which decreases over time [
Thompson Sampling Another widely used multi-armed bandit algorithm is
Thompson Sampling. Thompson sampling models the probability distribution of
each arm's reward. The reward of arm follows a probability distribution with
mean [
Contextual bandit algorithms combine MABs with context features. In our settings, users and news articles are always represented by feature vectors, such as domains. The contextual bandit algorithm chooses arms in such a way that the most appropriate arm for each context is played to maximize the reward. A trivial implementation is to build a MAB model for each context. Another idea is assuming there is a relationship between the expected reward and the context. We implement both ideas.
Linear UCB Linear UCB is a contextual bandit algorithm rst proposed in [
Our framework is designed to validate the hypothesis that contextual bandit algorithms can choose the appropriate recommender algorithm from the recommender algorithm pool for the incoming recommendation requests given context from users and items. In NewsREEL Replay, we consider two types of training: the training of the delegation model and the training of the recommender algorithms. The delegation model is trained and updated in batches (a more detailed discussion is presented in Section 3.2). In contrast, the recommender algorithms are trained and are able to update continuously regardless of the batches. The delegation model implemented in the Live task is also trained in the same way, but the data stream for training is from the o ine dataset due to the low volume received from the online scenario. The recommender algorithms in the Live scenario also update continuously. 3.1
We build up our delegation recommender based on the recommender developed
by recommenders.net. The recommender algorithm pool consists of ve simple
recommender algorithms:
{ Recent : Recommend the most recently created or updated articles. For the
realization, a ring bu er is implemented to store the most recently created
or updated articles. The size of the ring bu er is set to 100. When there is
a new item, it will be inserted into the ring bu er. If the ring bu er reaches
its size, it will drop the least recent news articles.
{ Path: Given the news articles that the user is currently reading, recommend
the most popular3 news articles requested next by users, referring to the
Most Popular Sequence in the work [
Our proposed delegation framework is trained and updates only in the Replay
task. The low volume of data from the Live task is not enough for training such
a framework. However, in NewsREEL Live, we implement the delegation model
trained from the NewsREEL Replay. More details about NewsREEL Live can be
found in Section 4.1. It is not trivial to implement MAB algorithm in the
realworld settings. We rst de ne the reward. In our settings, the reward is de ned
as clicks received from recommendations. If a user clicks on a recommendation,
the reward is 1, otherwise, the reward is 0. Therefore, the reward is a binary
value. Given the context, the recommender algorithm, and its corresponding
reward, the delegation model is able to update. However, unlike what is
implemented in [
Batch update and assignment The whole recommendation process is divided into batches. The contextual bandit algorithm is updated at the end of each batch with the rewards collected in each batch, as illustrated in Figure 1. After each update, the delegation model will preassign appropriate recommender for each context to serve incoming requests in the next batch.
Initialization In the rst batch, there is no historical data from which the contextual bandit algorithm can learn the model. Therefore, at the initial phase of recommendation, recommender algorithms are randomly selected to serve the incoming recommendation requests. At the end of the rst batch, the contextual bandit algorithm is able to update for the rst time with the rewards collected in the rst batch.
Rewards Rewards are de ned as `clicks' received from the recommendations. However, in both tasks, we cannot directly track whether our previous recommendations are successful or not. Making use of the evaluator from NewsREEL Replay, the reward is de ned, for a given recommendation, based on whether the user interacts with the item in the next 10 minutes. 3.3
We exploit context with two di erent methods. In the rst method, the context
is used to lter the model. For example, if the recommendation request belongs
to a domain A, the method chooses the model that is trained from items in A.
We refer to this method as context pre- ltering. Our second approach exploits
context for training the model. We refer to this method as context modeling. We
use the Linear UCB algorithm [
For the contextual bandit algorithm, it is important to nd useful context
features. Unlike other work [
Figure 2 shows the recommender algorithms' performance with respect to di erent context features using the CTR metric. In domain `418', a general news portal, the recommender Click performs the best. This recommender also shows a good performance in domain `1677', which is also a general news portal. However, the popularity based algorithm does not perform well in domain `35774', a sports news portal. The recommender algorithm Recent shows the best performance in this domain. This can be explained by the fact that people always prefer the newest sports news. Also, the bad performance of PRCate might be due to the reason the sports domain is already very speci c, and further speci c category would not help. The ndings are consistent with the ndings in previous work. Figure 3 shows the algorithms performance with respect to the number of user-domain impressions in domain `418'. Normally, with the increase of the number of user-domain impressions, CTR should also be increased as users with more interactions with the publishers would be more willing to click on the recommendations. However, there are some exceptions. With the increase of User-Domain Impressions, CTR observed from the Click algorithm experience a sharp decrease. The decrease can be explained by the fact people with enough interactions with the publisher have already seen the popular articles and prefer the newest news. In context modeling, the categorical context features are encoded by one-hot coding. The context Domain is already a categorical feature by itself. For the context User-Domain Impressions, we implement some transformation. Speci cally, we classi es the number of User-Domain Impressions into three groups: 0 number of User-Domain Impressions < 5, 5 number of User-Domain Impressions < 10 and 10 number of User-Domain Impressions < 15. In both online and o ine scenario, there are four types of messages: recommendation request, item update, event noti cation and error noti cation. Speci cally, in the Live task, the recommender needs to give recommendations within 100ms, otherwise the recommendations will be regarded as invalid. As the data volume redirected to our recommender is too low in the Live task, the delegation model implemented online is the one with the best performance in NewsREEL Replay. Thus, in the following sections, we will rst discuss our experiment in NewsREEL Replay, and then NewsREEL Live. Our recommendation framework that is used in NewsREEL Replay is described in Section 3. For this task, we are provided with a month-long dataset collected Fig. 3. Recommender Algorithms Performance w.r.t. User-Domain Impressions in Domain \418" during February 2016. Normally, a replay of a daily dump takes about 3-4 hours. Due to the time constraints, data collected from 2016-02-01 to 2016-02-03 is replayed for evaluation. The dataset is not evenly distributed: about 75% tra c is from the domain `35774', a sports domain, followed by two general news domains `1677' and `418'. In the evaluation phase, we only consider the results from the above three domains since a majority of tra c comes from these three domains. The evaluation phase is as follows: Firstly, the daily dump from 201602-01 is replayed to prevent the cold-start problem. Then the evaluation phase is implemented in the following way: The rest of the dataset (data from 201602-02 to 2016-02-03) is split into N smaller mutually exclusive datasets with the same size. The dataset is replayed in batches. See Figure 1 for clari cation. There are two di erent batch sizes, one containing 100000 line messages, and the other containing 300000 line messages. Next, as explained in Section 3.1, for each batch, rewards are computed at the end of the batch. After that, the contextual bandit algorithm is able to update the model. Finally, the chosen recommender algorithm is assigned for the incoming requests in the next batch. In Table 1, results with the best performance in each domain are highlighted. In Table 2 and 3, results with similar or better performance than the results in Table 1 are also highlighted. For all algorithms, we measure their performance based on average CTR and CTR in the three domains. We also further compare the CTR with the random baseline. The percentage in the tables shows the CTR change comparing to the baseline. 1 Algorithm labels: epsilon 0.5 b3: epsilon greedy with = 0:5 with context Domain and batch size 300000, ucb1 b3: UCB1 with context Domain and batch size 300000, ts b3: Thompson Sampling with context Domain and batch size 300000
With the context given in Section 3.2, we propose two di erent delegation models in the Replay task. In the rst method, referred as context pre- ltering, we only consider the context Domain and implement a separate bandit model in each of the three news domains. In the second approach, referred as contextmodeling, we encode context (Domain and User-domain Impressions ) as feature vectors. Then we build a contextual bandit model based on the linucb (Linear UCB) model. The results of the simple baseline recommender algorithms are presented in Table 1, the results of the context pre- ltering model in Table 2, and the results of the context-modeling approach is listed in Table 3. The random algorithm, which randomly selects a recommender algorithm to serve the incoming requests, is set as the baseline, referred to as random in Table 1. The names of the contextual bandit algorithms in Table 2 contain algorithm hyperparamter value batch size. There are three di erent bandit algorithms in context pre- ltering: epsilon-greedy (epsilon), ucb1 and Thompson Sampling (ts). For epsilon-greedy, we tried three di erent value: 0:5, 0:3 and 0:1. In the experiment, we also tried two batch sizes: b3 means each batch containing 300000 messages and b1 indicating 100000 messages. Contextual bandit algorithms in Table 3 are formatted as algorithm hyperparamter value context used batch size. The only algorithm used in context-modeling is linear UCB. In the model, linear UCB is implemented with three di erent value in Eq.(1): 1, 0:5 and 0:2, and two context: Domain and User-Domain Impressions. In Table 2 and Table 3, d stands for the context Domain. In Table 3, di indicates the use of both contexts. 4.2
The online evaluation of NewsREEL Live is from 24 April to 7 May 2017. The Open Recommendation Platform (ORP) is responsible for redirecting the tra c from the publishers and monitoring di erent recommender algorithms' performance. With ORP, participants are able to deploy their recommender services and receive recommendation requests. The low volume of data refers to the small number of recommendation requests, user clicks and user impressions, redirected to our recommender from plista. Comparing with the data stream in the Replay dataset, the data stream redirected in the Live task consists only a small portion of the whole plista data stream and is not enough to support training or updating of our contextual bandit algorithm. In the Live task, we deployed the best delegation recommender model trained from the NewsREEL Replay, referring to linucb 0.2 di b3 in Table 3, to serve the incoming recommendation requests. In addition, a portion of data from the Live task comes from a domain that is not included in the Replay dataset. This also gives rise to a challenge for us. Our solution is that for all the recommendation requests from that domain, we redirect them to the PRCate recommender. Table 4 shows our online evaluation results. There are two types of impressions created by ORP. The rst type considers the impressions from the recommendation list, which are referred to as `widget impressions', and the second type considers the impressions from individual items, which are referred to as `item impressions'. ORP also creates a `click' for each click on the recommended articles from users. The nal metric for the recommender performance is measured by the CTR, which equals to the number of clicks divided by the number of impressions. 5 5.1
The NewsREEL Replay evaluation results are summarized in Table 1, Table 2 and Table 3. Table 1 shows the recommendation performance of the ve basic recommenders from which the delegation model is able to choose an appropriate recommender. A random algorithm, which randomly selects a recommender for the incoming recommendation requests, is served as the baseline. Table 2 shows the evaluation results from the contextual bandit delegation model in which a MAB model is set up for each context. Table 3 shows the evaluation results from the contextual bandit delegation model in which the linear UCB model is implemented. The only context in Table 2 is Domain, while in Table 3, two contexts Domain and User-Domain Impressions are considered. From both Table 2 and Table 3, we can see the evaluation results from the delegation model outperform the random baseline. This indicates the delegation model is able to learn from the past and chooses appropriate recommender for the incoming recommendation requests in order to maximize the CTR.
To further explain the results, we rst describe two facts with respect to
the domain `35774': Firstly, as explained in the previous section, about 70% of
the tra c is from this domain. Therefore, a CTR increase in domain `35774'
leads to an increase of average CTR. Secondly, as shown in Table 1, the
recommender Recent performs much better than any other recommender in this
domain. For the performance of di erent MAB algorithms, UCB1 works better
than epsilon-greedy in domain `35774', but worse in domain `418' and domain
`1677'. This result is a little bit unexpected since UCB1 explores under the
guidance of a con dence bound [
For NewsREEL Live we test our recommender for 14 days. There are two challenges in the Live task: Firstly, as discussed before, the low volume of data from the ORP to our account makes it hard for us to train the contextual bandit algorithm online. A delegation model trained from the Replay task is deployed to serve the incoming recommendation requests. Secondly, publishers in the Live task are di erent from the publishers in the Replay task. In NewsREEL Live, a portion of requests comes from domain `17614', which is not included in the Replay dataset. As the result, the corresponding requests from that domain are delegated to the PRCate recommender. The two challenges might lower our recommendation performance in the Live task. In total 19 teams which participate in NewsREEL Live, our delegation model ranked 10th. 5.3
In conclusion, our results have veri ed our assumption the contextual bandit algorithm is able to select the appropriate recommender algorithm given the context. However, the balance between exploration and exploitation is important. If one particular recommender algorithm is performing signi cantly better, then exploitation does not necessarily help. For future work, rstly, we will add more recommender algorithms to our recommender algorithm pool, such as collaborative ltering since the performance of the contextual bandit algorithm is to some extent limited by the single recommender algorithm. Secondly, we will explore more contexts in order to further improve the recommendation CTR. Last but not least, we would like to evaluate the contextual bandit algorithm on a dataset with a more equally distributed tra c among di erent domains.