Latent Contextual Bandits and their Application to Personalized Recommendations for New Users

1 Introduction

In general we desire recommender systems that can quickly start providing good recommendations for new users, which is particularly challenging as no prior information for new users is available. This is often known as the cold-start problem. Despite the lack of prior information for new users, such systems typically have interacted with millions of previous users. Therefore, this problem can be cast as an instance of lifelong learning across sequential decision making tasks: how should information from prior users be leveraged to help improve the recommendations for a new user? Standard techniques like collaborative filtering [Koren et al., 2009] provide good answers to this challenge, but such approaches are typically limited to myopically providing a single recommendation, rather than reasoning about the multi-step interactions the system may have with the user. This is important, because across a sequence of interactions it may be useful for the system to actively gather information (potentially sacrifice immediate performance outcomes) in order to maximize its benefit over the longer run with the individual in question.

One approach to this is to model users by a contextual bandit model [Bubeck, 2012; Zhou, 2015] with a single shared set of model parameters, and all prior users' data can be leveraged to fit those model parameters for use in interacting with a new user. Example algorithms are LinUCB [Li et al., 2010], Thompson sampling with linear payoffs [Agrawal and Goyal,

2013], and CofineUCB [Yue et al., 2012]. However, these approaches work well only when there are many available features that describe users and capture user variability. If those features are not available, then we may need to fall back on a population average that may make poor recommendations for the current new individual.

At the other extreme is to use learning algorithms such as LinUCB and Thompson sampling with linear payoffs to learn from scratch for each new user separately. Such systems can provide full personalization to an individual (using model parameters learned only for that user), but may take an enormous amount of interactions to achieve this, yielding very little value for a long period (and potentially causing the user to get frustrated or cease using the system).

We instead propose an approach that provides partial personalization. We assume that users can be described as each belonging to one of a finite set of latent classes. Each class may be associated with a different set of model parameters, but within a class all individuals share the same parameters. Compared with the two extreme approaches mentioned above, partial personalization does not fully rely on user features to capture user variability, instead it leverages users' latent class structure to more quickly start providing good recommendations for new users.

Latent class structure has been explored in the noncontextual Multi-armed bandits setting [Lazaric et al., 2013; Maillard and Mannor, 2014]. In the contextual setting, the most closely related work is CLUB [Gentile et al., 2014]. CLUB learns an underlying graph structure of users based on user similarities and serves a group of users by taking advantage of the learned graph structure. However, as we will show later, our algorithm is theoretically and empirically better than CLUB.

In this paper, we focus on the latent contextual bandit setting. We consider both the benefit of using a set of learned latent classes, and how we can obtain such latent classes from a prior set of data or online. We also provide a formal analysis of the regret in this setting, by building on recent progress on latent variable learning of regression model mixtures using tensor methods [Chaganty and Liang, 2013], to bound the performance obtained by learning and leveraging a set of latent models learned from data. We then demonstrate the benefit of our approach in simulation and an unbiased offline evaluation using a large real world dataset, as well as a preliminary user study. Our results suggest a substantial benefit of our latent contextual bandit approach.

2 Our Approach

2.1 ProblemFormulation

We assume there is a sequence of contextual bandit tasks, and each contextual bandit task involves multi-step interactions with a particular user. 1 Let there be ˜U users, where ˜U may be infinite. Each user u belongs to one of a finite set of N latent classes. Denote by cu the (unknown) latent class of user u. Users within the same latent class share similar interests and behaviors. Each task (series of interactions with a single user) is assumed to last for Tu steps.

During a task, in each time step tu 2 ¶1↪ ▷ ▷ ▷ ↪ Tu♦, the algorithm observes both the current user u and a set Atu of arms (items) together with their d-dimensional feature vectors xtu↪a 2 Rd for all a 2 Atu . ♣♣xtu↪a♣♣2  1. The feature vector xtu↪a captures the information of both user u and arm a at time tu. For example, xtu↪a could be the linear concatenation of user and arm feature vectors. We assume the size of Atu is fixed: ♣Atu ♣ = K. These K feature vectors are together referred to as the context Ctu at tu: Ctu = ¶xtu↪a♣a 2 Atu ♦.

The algorithm then recommends an arm atu to the current user u, and receives reward rtu 2 [0↪ 1] from the user. We assume that the reward is a noisy linear function of the current user's latent class. More precisely, each latent class h 2 ¶1↪ ▷▷▷↪N♦ is associated with an (unknown) weight vector βh 2 Rd . The reward of an arm a 2 Atu is given by

where ✏cu follows a Gaussian distribution with zero mean and bounded variance. Let a⇤tu = argmaxa2Atu β> cu xtu↪a be the arm with highest expected reward at time tu, and atu be the arm selected at tu. Then the algorithm's goal is to minimize the regret, which is defined as

2.2 Latent Contextual Bandits

Our algorithm, Latent Contextual Bandits (LCB), is described in Algorithm 1. LCB learns the set of latent models from prior users and leverages the learned models to make recommendations for new users. The algorithm consists of two phases. In phase 1, LCB simply runs LinUCB algorithm on the first J users and collects the pulled arms and rewards. (line 2 - 11, Algorithm 1). The reason to do phase 1 is that initially when LCB starts from scratch, there are no prior users or training data for LCB to learn the latent models. Therefore, phase 1 is the bootstrap phase of the algorithm. A short phase 1 will cause a high model estimation error at the early stage of phase 2, while a long phase 1 will cause large regret in phase 1. In Section 3 we will discuss how to pick the length of phase 1 to get low overall regret bound. In real world systems, usually we already have a huge set of interactions made by prior users, then phase 1 is not needed.

1 While in the paper we assume users come sequentially and interact with our algorithm, our approach can also handle interleaved users. As we will describe later, in phase 1 of our algorithm, it doesn't matter if users interleave as LinUCB is used. In phase 2, we can fix the current set of clusters and parameters for a new user when he/she first arrive, and use that for the entire time we interact with that user.

In phase 2, LCB train/re-train latent models using data collected in both phases 1 and 2 so far (line 13, Algorithm 1). We will show how to learn the latent models in Section 2.3. In practice, we may want to re-train the latent models after a batch set of users instead of each user.

Meanwhile, in phase 2 LCB should leverage the learned latent models to improve performance for new tasks (users). Though there are many ways to do this, we propose an approach that first constructs a policy for each learned latent model, and then uses a contextual bandit algorithm that can adaptively select across the policies for a new task. A policy is a function that takes a context as input and returns an arm or a distribution over arms. For example, one policy could be a function that always return the arm with the highest expected reward estimated by a learned latent model. There already exist numerous contextual bandit algorithms that take as input a finite set of policies and compete with the best policy inside the policy set [Beygelzimer et al., 2011; Agarwal et al., 2014], so LCB can build upon these existing works. However, LCB in phase 2 offers multiple advantages relative to these prior works: the policy set N is often smaller than the set of policies considered by generic contextual bandit approaches; LCB automatically constructs the set of policies (instead of requiring an oracle or expert to provide a good set); and assuming the problem setting holds, the set of N policies is sufficient to enable optimal performance for any new task, in contrast to standard contextual bandit approaches which can only achieve performance as good as the input policies (which may not achieve optimal performance).

More precisely, LCB constructs one policy for each learned latent model (line 14, Algorithm 1), and then runs a preselected contextual bandit algorithm B that takes in the set of N learned policies for the N latent contextual bandit tasks (line 15 - 22, Algorithm 1). We will discuss specific choices of B and ways to construct policies in Section 2.4, and we will shortly provide a theoretical analysis of our approach in Section 3.

2.3 Learn Latent Models fromPast Users

We model latent user classes using a mixture of linear regressions [Viele and Tong, 2002]. A mixture of linear regressions consists of N mixture components, each is a linear regression model. Let ⇥ = ¶⇡h↪ βh↪ σ2h ♣h 2 ¶1↪ ▷▷▷↪N♦♦ be the model parameters, where ⇡h is the mixture proportion, βh is the coefficient vector, and σ2h is the variance of the response. Then the likelihood of mixture of linear regressions is defined as

where N(r♣θ↪ σ2 ) is the probability density function of a Gaussian distribution with mean θ and variance σ2 . One

Algorithm 1: Latent Contextual Bandits (LCB)

Input: J 2 R+: number of users in phase 1 N 2 R+: number of latent classes P: policies construction strategy B: contextual bandit algorithm 1: Samples D = ? // Phase 1 2: Create a LinUCB instance 3: for user u 2 ¶1↪ 2↪ ▷▷▷↪ J♦ do 4: for tu 2 ¶1↪ 2↪ ▷▷▷↪ Tu♦ do 5: Observe context Ctu = ¶xtu↪a 2 Rd ♣a 2 Atu ♦ 6: Pull atu = LinUCB(Ctu ) 7: Observe reward rtu 8: Update LinUCB based on reward 9: Add (xtu↪atu ↪ rtu ) to D 10: end 11: end // Phase 2 12: for user u 2 ¶J +1↪ J +2↪ ▷▷▷♦ do 13: Learn N latent models ¶ˆ β1↪ ▷▷▷↪ ˆ βN♦ using data D 14: Construct N policies ¶P(ˆ β1↪ · )↪ ▷▷▷↪P(ˆ βN↪ · )♦ 15: Create a B instance for u 16: for tu 2 ¶1↪ 2↪ ▷▷▷Tu♦ do 17: Observe context Ctu = ¶xtu↪a 2 Rd ♣a 2 Atu ♦ 18: Pull atu = Bu(Ctu ↪ ¶P( ˆ β1↪ · )↪ ▷▷▷↪P(ˆ βN↪ · )♦) 19: Observe reward rtu 20: Update Bu based on reward 21: Add (xtu↪atu ↪ rtu ) to D 22: end 23: end

classic algorithm to learn a mixture model is the ExpectationMaximization (EM) algorithm. However, EM does not guarantee convergence to the globally optimal parameters, and it does not provide finite sample guarantees on the quality of the resulting parameter estimates. On the other hand, tensor decomposition based methods, as we will describe shortly, give us finite sample guarantees which can be further used to derived our regret bound.

Learn Latent Models using Spectral Experts

Anandkumar et al. [2014] showed that tensor decomposition can efficiently recover parameters for a wide class of latent variable models. They exploited a special tensor structure derived from second and third-order moments of the observations, and apply the robust tensor power method to recover model parameters. Spectral Experts [Chaganty and Liang, 2013], built on top of Anandkumar et al.'s work, provide provably consistent estimator for mixture of linear regressions. Our algorithm uses Spectral Experts to estimate parameters of mixture of linear regressions. Later in Section 3 we also use the parameter error bound provided by Spectral Experts to bound the regret of our algorithm.

Though Spectral Experts algorithm has appealing theoretical properties, it is not particularly sample efficient and it is computationally expensive. Therefore, in the following section, we also derive and implement a computationally efficient Gibbs sampling based procedure to estimate parameters of mixtures of linear regressions.

Learn Latent Models using Gibbs Sampling

Gibbs sampling is an efficient inference technique to learn latent models for large scale dataset. We derive a sampling procedure for Dirichlet Process [Neal, 2000] mixtures of linear regressions. By using a Dirichlet Process prior, we do not need to specify the number of latent models. Specifically, we assume the prior of βh and σ2h follow the Normal-inverseGamma distribution and the prior of ⇡ follows GEM distribution [Murphy, 2012a], which is used by the stick-breaking construction of the Dirichlet process. The generative process is as follows:

1. ↵ ⇠ Gamma(u0↪ v0)
2. ⇡ ⇠ GEM(↵)
3. For each latent model h 2 ¶1↪ ▷▷▷↪N♦
4. For each user u 2 ¶1↪ ▷▷▷↪ U♦

• (a) cu ⇠ Categorical(⇡)

(b) For each interaction tu 2 ¶1↪ ▷▷▷↪ Tu♦

We use collapsed Gibbs sampling to sample cu and ↵. Denote all the rewards of a user u by ru = ¶rtu : tu 2 ¶1↪ ▷▷▷↪ Tu♦♦. To sample cu,

where c-u = ¶cu0 : u0 6= u♦ and rh-u = ¶ru0 : cu0 = h↪ u0 6= u♦. The first term in Equation (1) is given by the Chinese Restaurant Process (CRP) [Neal, 2000], the second term in Equation (1) is the posterior predictive distribution of ru given rh-u , and it follows Multivariate t-distribution [Murphy, 2012b]. To sample ↵, we adopt the auxiliary variable method [Escobar and West, 1995].

2.4 Leverage LearnedModels for NewUsers

Let ¶ˆ β1↪ ▷▷▷↪ ˆ βN♦ be the N learned latent models. We define N policies based on these models. There are two types of policies we can define, one is deterministic, and the other one is probabilistic. The deterministic one maps a context Ctu to an arm a 2 Atu :

The probabilistic one maps a context Ctu to a categorical distribution over arms:

where

The constructed polices can be used by many contextual bandit algorithms to serve new users. If the policies are deterministic, possible contextual bandit algorithms include Epoch-Greedy [Langford and Zhang, 2008], ILOVETOCONBANDITS [Agarwal et al., 2014], and Generalized Thompson Sampling [Li, 2013]. If the policies are probabilistic, possible contextual bandit algorithms include EXP4 [Auer et al., 2002] and EXP4.P [Beygelzimer et al., 2011]. The algorithm choice depends on the desired outcome, and we will shortly consider specific choices for both our theoretical analysis and empirical results.

3 Theoretical Analysis

In this section, we analyze LCB's expected regret. We assume the latent models are learned using the Spectral Experts algorithm. Let J be the number of users in phase 1, U be the number of users in phase 2, and ˜U = J +U be the total number of users. Let S = PJu=1 Tu, T = P˜Uu=J+1 Tu, and ˜ T = S + T be the total number of interactions. We denote the first n positive integers by [n]. For convenience, we define the true policy of a user u 2 [ ˜U] as the deterministic policy constructed by βcu (the true latent model the user belongs to).

For theoretical analysis, we make two minor changes to the Algorithm 1. First, instead of running a single LinUCB instance for all users in phase 1, we run a separate LinUCB instance for each user. The reason is that under our realizability assumption (each user belongs to one of the latent models) single LinUCB instance which runs for all users has linear regret O(S). Second, we collect ⌧u i.i.d. samples from each user u 2 [ ˜U], that is, we select arms uniformly at random for the first ⌧u interactions for each user u 2 [ ˜U]. When training latent models using Spectral Experts, we only use these i.i.d. samples. We do this because Spectral Experts requires i.i.d. training examples to get theoretical guarantee on the parameter error bound.

Assume Tu  L for all u 2 [ ˜U] for some constant L. Denote the minimum Euclidean distance of any two latent models by 4, that is, ♣♣βh - βh0 ♣♣ ≥ 4 for any h 6= h0 . The following two theorems show a problem-independent expected regret bound which is independent of 4 and a problemdependent expected regret bound which depends on 4.

Theorem 1. Set ⌧u = pTu for all u 2 [ ˜U] and J = pL. Assume P constructs deterministic policies. If B is a contextual bandits algorithm with optimal regret bound (e.g. EXP4.P), then the problem-independent expected regret bound of LCB with respect to the true policy is

as UT ≫max n1↪ d2 K o JS, that is, as T and U grows large. Similarly, if B is EXP3 [Auer et al., 2002] which treats each learned policy as an arm, then the problem-independent expected regret bound of LCB with respect to the true policy is as UT ≫max n1↪ d2 N o JS, that is, as T and U grows large.

Theorem 2. Set ⌧u = 3 for all u 2 [ ˜U] and J = L2 . Assume P constructs deterministic policies and B is Epoch-Greedy, then the problem-dependent expected regret bound of LCB with respect to the true policy is

Proof (Theorem 1). The expected regret of LinUCB [Zhou,

2015] isE [RegLinUCB(Tu)] = O(dpTu ln(1 + Tu)) so in phase 1 the expected regret of LCB is

where Equation (2) follows from the Cauchy-Schwarz inequality.

We next need to bound the regret in phase 2. For each user u 2 ¶J + 1↪ ▷▷▷↪ J + U♦ in phase 2, define

as the best model of that user within all estimated models. Also recall that βcu is the true model of the user u and ˆ βcu is the estimate of βcu returned by Spectral Experts. Let a⇤tu ↪ ˜a⇤tu and ˆa⇤tu be the arm proposed by βcu ↪ ˆ βcu and ˆ β⇤u . ˆ β⇤u achieves the highest expected cumulative reward based on its definition, so it achieves higher expected cumulative reward than ˆ βcu , so

Meanwhile, we can bound the gap between the expected cumulative reward achieved by βcu and by ˆ βcu as follows:

The last step uses the fact that ♣♣xtu↪a♣♣2  1. Using Equation (4) and (5) together we can bound the gap between the expected cumulative reward achieved by βcu and by ˆ β⇤u :

Chaganty and Liang [2013] showed that ♣♣βcu - ˆ βcu ♣♣ = O ⇣ 1 pn ⌘ where n is the number of training examples. Now if B is a bandits algorithm with optimal expected regret bound O(pTuK lnN), then in phase 2 the expected regret of Latent Contextual Bandits is

Equation (6) follows from J ≥ pTu for all u. Equation (7) follows from bounding the last term in (6) by 3pTu, and then applying Cauchy-Schwarz inequality. 2 Similarly, if B is EXP3 which achieves a regret of O(pTN lnN), then the expected regret of LCB in phase 2 is O(3pUT +pUTN ln N). Finally, by adding the regret bound of phase 1 and phase 2, we prove the theorem.

Proof (Theorem 2). The proof of Theorem 1 shows that the regret in phase 1 is

If B is Epoch-Greedy, then based on Epoch-Greedy's problem-dependent bound we have

2 The last term actually decreases at the rate of O(1◁pu) with respect to u, so our regret bound gets tighter as u increases in phase 2, but only by a constant factor.

Set J = L2 , then the last term is less than or equal to 1. Set ⌧ = 3, then the regret of LCB, by adding the regret in phase 1 and phase 2, is

which proves the theorem.

To put these results in context, we now compare our regret results to several other approaches. We compare the following algorithms: 1) Population EXP4.P: runs a single EXP4.P model for all users, 2) Individual EXP4.P: runs a separate EXP4.P model for each user, 3) Population LinUCB: runs a single LinUCB model for all users, 4), Individual LinUCB: runs a separate LinUCB model for each user, 5) EXP4.P enum-policies: enumerates all policies by mapping all possible contexts to all possible arms and then runs EXP4.P on each user (assuming contexts are enumerable), 6) CLUB, 7) LCB. Table 1 shows the expected regret of each algorithm; it also shows the policy each algorithm is competing with when deriving the regret bound. Keep in mind that all comparisons are under our realizability assumption that each user belongs to one of the latent models.

Within the 7 algorithms in Table 1, 3 of them does not compete with the true policy of each user: Population LinUCB doesn't distinguish between users from different classes, so it is competing with the best average policy of all users; Population/Individual EXP4.P requires a set of pre-defined policies as input, and compete with the best one inside the policy set instead of the true policy of each user.

The remaining 4 algorithms all compete with the true policy of each user; however, LCB achieves the best expected regret bound. The problem-independent regret bound of Individual LinUCB is linear with respect to the contexts' feature dimension which is often very large. Define C as the total number of contexts. EXP4.P enum-policies has a C term in its problem-independent regret bound which is often large or even infinite. LCB's problem-independent regret bound, on the other hand, only has square root dependence on U↪ T and min¶K↪ N♦.

Table 1 also shows the problem-dependent regret bound of CLUB analyzed by Gentile et al. [2014]. Both LCB and CLUB's problem-dependent regret bounds depends on 1◁42 . However, CLUB has a square root dependence on ˜ T, while LCB only has a square root dependence on S (number of interactions in phase 1) which is a constant. Moreover, the analysis of CLUB (see Appendix of Gentile et al. [2014]) shows that CLUB's expected regret on a new user u is linear with respect to Tu when Tu < B for some constant B that is in the order of O( d 42 ). B may be enormous if 42 is small. Meanwhile, LCB's problem-independent regret bound guarantees that LCB's expected regret on a new user u is always sublinear (square root) with respect to Tu even when Tu is small.

4 Experiments

In this section, we evaluate our algorithm both on simulation and on a large real world dataset from Yahoo!. We compare

42 (lnN + ln(T +1))) true policy of each user

Table 1: Expected regret bounds of LCB and baseline algorithms. We use N to denote both the number of policies in the three EXP4.P variants and the number of latent models in LCB and CLUB. We use C to denote the total number of contexts.

the following algorithms: 1) LCB: our approach. We choose Generalized Thompson Sampling as B in Algorithm 1. For simulation we use Spectral Experts to learn latent models, but due to time/memory constrains, for large real world dataset we use Gibbs sampling to learn latent models; 2) LCB GT: this is similar to LCB, except that instead of learning the latent models, we provide true latent models to the algorithm. 3) CLUB; 4) Population LinUCB: runs single LinUCB instance on all users; 5) Individual LinUCB: runs a separate LinUCB instance on each user; 6) Random : selects each arm uniformly at random.

4.1 Simulation

We artificially created 5 latent models as shown in Figure 1. Each model had 10 parameters, and 4 of them were assigned higher weights. Users were sampled uniformly at random from these latent models. For each user interaction we generated 20 arms, that is, ♣Atu ♣ = 20. Each arm a was associated with a feature vector xtu↪a sampled uniformly from [-1↪ 1]10 , and was normalized so that ♣♣xtu↪a♣♣2 = 1. We sampled the reward of each arm a from N(β> cu xtu↪a↪ σ2 ) with σ = 0▷1. For LCB, we set J = 50, and in phase 2 we re-trained the latent models after every 50 users.

In the first experiment, we fixed Tu = 20 for all users, and reported the averaged per-user regret vs. number of users. Results are shown in Figure 2a. We can see that the regret of LCB was about 35% lower than CLUB and 50% lower than Population LinUCB. In the second experiment, we fixed the number of users

to 1000, and varied Tu from 10 to 100. Tu were set to the same for all users. Figure 2b shows the averaged per-user regret vs. Tu. We can see that LCB outperformed CLUB and LinUCB, and as Tu increased, the gap between their regret also increased. Also, when Tu was more than 40, Individual LinUCB started to learn a good model for each user, and outperformed Population LinUCB, however, it still had much higher regret than LCB.

3 Under our realizability assumption, Population LinUCB has O( ˜ T) linear regret, so here we show the regret under its own realizability assumption

• (a) Averaged per-user regret vs. number of users.
• (b) Averaged per-user regret vs. number of interactions per users.

Figure 2: Experiment results on simulation

4.2 Experiments on Real World Dataset

We evaluated our algorithm on a news feed dataset provided by Yahoo!. The dataset contained 500↪000 users and all their visits in a one month period. In each visit, a user was shown 25 news articles from the top down. User clicks (binary feedback) were logged. There were 21 news categories, and each news article belonged to 1 ⇠ 3 categories. Therefore, articles were represented as a 21-dimensional binary feature vector. User features were not available because of privacy issues.

To the best of our knowledge, in our case there is no perfect solution for unbiased offline evaluation. For stationary algorithm one can use propensity scoring [Strehl et al., 2010], however our algorithm is nonstationary, and propensity score is not available in this dataset. One state-of-the-art solution is rejection sampling based replay method [Li et al., 2011]. However, rejection sampling is quite sample inefficient on our dataset because the policy which generated our dataset was biased towards exploitation. Therefore, we adopted the queue method [Mandel et al., 2015], a sample efficient offline evaluation method for non-contextual bandits, and extended it to our contextual case.

To use the queue method, we defined arms as news categories instead of news articles. As there were 21 categories, we defined 21 queues for each user. The queues of each user were initialized with click labels (0 or 1) of articles shown to that user. For example, if an article belonged to two categories, then its click label was added to the two corresponding queues. Finally, we ran PCA to project the 21-dimensional article feature space to a 6-dimensional lower space so that each category (arm) can be represented as a dense vector.

(b) Relative CTR of 10,000 new users vs. number of latent models specified in batch training. (c) Relative CTR vs. number of users that have been interacted with the algorithm.

Figure 3: Experiment results on a large real world news recommendation dataset.

We fixed the number of interactions per user (Tu) to 20 for all users to ensure all users were new users. We reported relative CTR, the algorithm's CTR divided by the CTR in the data, due to confidentiality. In the first experiment, we ran batch training: each algorithm was pre-trained with 20↪000 - 200↪000 users, and then tested on the 10↪000 new users. Relative CTR of the test users was reported. For LCB, we used the training users to learn 30 latent models, then we directly ran phase 2 for the test users without re-training latent models. Figure 3a shows the experiment results. We can see that LCB achieved the highest CTR, and outperformed CLUB by about 10%. Moreover, CLUB only outperformed Population LinUCB by about 2%. One reason is that the rewards in our real dataset were binary and noisy, so 20 samples per user (Tu = 20) were not enough for CLUB to learn a good regression model for each user and hence to learn a good latent graph structure. In the second experiment, we varied the number of latent models of LCB from 1 to 30. Similar to the batch training, each algorithm was pre-trained with 150↪000 users and then tested on 10↪000 new users. The result is shown in Figure 3b. We can see that with 10 or more models, LCB started to take the benefit of latent class structure and outperformed CLUB and LinUCB. With 15 and 30 latent models, our approach improved the CTR by about 5% and 10% respectively compared with CLUB and Population LinUCB. The third experiment simulated the real world environment in which users came sequentially and interacted with the algorithm. For LCB, 20↪000 users were used in phase 1. In phase 2, 30 latent models were trained and re-trained after every 10↪000 users. To collect i.i.d data points to better learn the latent models, we picked arms uniformly at random for the first 5 interactions of each user, and only used these data points to train/re-train latent models. For all algorithms, we reported relative CTR after every 10↪000 users. Results

0▷196 ◦ 0▷096

0▷380 ◦ 0▷076

Table 2: CTR mean and standard deviation in user study.

in Figure 3c shows that LCB achieved about 5% higher CTR than CLUB and Population LinUCB.

4.3 Pilot Results on User Study

In this section, we show the pilot results of our user study with 10 users, 5 for each algorithm. We compared two algorithms: Population LinUCB and LCB. Since the experiments in Section 4.2 used the Yahoo! real world dataset, so the learned models can be directly used for the user study. For LCB, we used the learned latent models from Section 4.2 and directly ran phase 2 of LCB. For Population LinUCB, we used the learned Population LinUCB model from Section 4.2 to initialize the LinUCB model used in the user study. Users interacted with the algorithms through an app developed on the Android platform. Tu = 20 for all users. During each user interaction, the app requested 170 latest news articles from the Yahoo! news service in real time. Similar to Section 4.2, each news article was represented by a 21-dimensional vector. The algorithm then selected one of the articles for the user and received user feedback (click). Table 2 shows the CTR mean and standard deviation achieved by these two algorithms. We can see from the pilot results that LCB outperformed Population LinUCB. User study with more users and algorithms is in progress.

5 Conclusion

In this paper, we propose Latent Contextual Bandits, a contextual bandits algorithm that learns the latent structure of users and leverages the learned latent structure to make personalized recommendations for new users. We prove both a problem-independent and a problem-dependent regret bound with respect to the true policies of users. The regret bounds significantly improved over baseline algorithms. We then demonstrate the benefit of our approach using both simulation and an unbiased offline evaluation with a large real world dataset, as well as a preliminary user study.

Acknowledgments

This work was supported by the CMU-Yahoo! InMind project. We also gratefully acknowledge the assistance and/or helpful feedback of Liangjie Hong, Suju Rajan, Michal Valko, Saloni Potdar, Zhengyang Ruan, Linxi Zou, Mingzhi Zeng and the pilot study participants.