Online learning has long been adopted as one of the archetypal formulations in various applications including online advertising (Li et al. 2010b), personalized recommendation (Li et al. 2010a), and information retrieval (Yue and Joachims 2009). A classic framework for online learning is the multi-armed bandit (MAB) model with a set of K arms (representing all possible actions) and a single player. At each time, the player chooses one of the K arms to play and obtains a random reward generated from an unknown distribution specific to the chosen arm (Lai and Robbins 1985; Auer, Cesa-Bianchi, and Fischer 2002). In order to maximize the total expected reward over a time horizon of length T, the learner needs to design an arm selection policy that balances an intrinsic tradeoff between exploring the unknown reward model and exploiting the current knowledge to maximize the instantaneous gain. The performance of an arm selection policy is measured by regret, which is the expected cumulative reward loss against an omniscient player who knows the reward model and always plays the best arm.

In recent years, contextual bandits (Langford and Zhang 2007; Li et al. 2010a), a variation of the classical MAB model, has received large attention due to its success in various online services where context information associated with either users or items is available. It has been assumed that the unknown reward model of an arm is determined by the given context. Through leveraging the context information, a number of new learning algorithms have been developed to achieve better performance compared with context-free ones in the classical setting (Li et al. 2010a; Wang, Wu, and Wang 2016).

While most existing studies on contextual bandits assume a stationary environment where the unknown reward model is fixed over time given the context information, real-world applications are usually dynamic due to the time-varying interests of users. For example, it has been observed that the click behaviors of users over different news articles evolve over time in both Google News (Liu, Dolan, and Pedersen 2010) and Yahoo News (Zeng et al. 2016). Without the capability of detecting potential changes in the underlying reward model, existing algorithms may lead to sub-optimal decisions using out-of-date observations.

Main Results

In this paper, we study a more realistic setting with non-stationary user interests under the contextual bandit framework. Specifically, we assume that the preferences of users towards items are piecewise-stationary, i.e., the reward model may undergo abrupt changes but between two consecutive change points, the model remains fixed. Furthermore, we consider asynchronous and distinct reward changes across different items, which is a common phenomenon in real applications. For example, in news recommendation, changes on the preferences of readers towards different news categories are triggered by the occurrence of related hot events, which are unlikely to happen at the same time. In e-commerce platforms, customers’ life-long interests over different products also exhibit distinct changes: a customer is more likely to purchase toys in his childhood while in adulthood, he may become more interested in sport-related products. However, the preference changes over the two categories can happen asynchronously as there may exist a time period (e.g., adolescence) when the customer likes both toys and sports. Moreover, it is possible that the customer’s preferences towards other products (e.g., snakes) remain unchanged over time. To characterize such phenomena, we consider two reward models with disjoint and hybrid payoffs as described below.

In the disjoint payoff model, we assume that the expected reward of playing an arm1 is the inner product of the given context vector and an arm-specific unknown co-efficient vector, which represents the preference of the user towards the arm. The preference vector is assumed to be piecewise-stationary and the change points are different across arms. We propose an upper confidence bound (UCB) based algorithm that selects arms by estimating the unknown preference vectors from past observations. To address the challenge of time-varying interests, the algorithm adopts a change-detection procedure to identify potential changes on the preference vectors. Once a change is detected, an effi-cient restart is applied to re-estimate the preference vector using up-to-date observations. We provide theoretical regret analysis of the proposed algorithm and show that a sublinear scaling of regret in T is achieved. We further extend the algorithm to a more general setting with hybrid payoffs. In addition to the arm-specific preference vector, the expected reward in the hybrid model also depends on a joint coeffi-cient vector shared by all arms, which corresponds to the time-invariant component of the user interests. We conduct experiments on real-world datasets to evaluate the performance of the proposed algorithms in both settings.

Related Work

Under the MAB framework, a large number of learning algorithms have been developed to balance the tradeoff between exploration and exploitation. Example algorithms include Thompson sampling (Thompson 1933; Agrawal and Goyal 2012), UCB (Lai and Robbins 1985; Auer, Cesa- Bianchi, and Fischer 2002), and epsilon-greedy (Sutton and Barto 1998) in the classical context-free bandit setting, epoch-greedy (Langford and Zhang 2007) and LinUCB (Li et al. 2010a) in the contextual bandit setting. However, those algorithms assume a stationary environment that hardly holds in real applications.

In addressing the issue of non-stationary environment, various reward models have been studied in the literature. One of the most commonly accepted models is the piecewise-stationary reward model, which allows abrupt reward changes at certain unknown time points but remains fixed between two consecutive change points. Under the piecewise-stationary assumption, the problem has been well studied in the classical context-free setting. A number of learning algorithms have been developed that adapts to the abrupt reward changes by either triggering a reset of the learning algorithm after the detected changes (Hartland et al. 2007; Yu and Mannor 2009; Cao et al. 2019) or applying a discount factor on past observations (Garivier and Moulines 2011). Theoretical regret analysis showed that a sublinear

scaling of regret in T is achieved.

Within the contextual bandit setting, however, only a few recent studies have taken the issue of non-stationary environment into consideration. In (Hariri, Mobasher, and Burke 2015), a contextual Thompson sampling algorithm with a change detection module was proposed but theoretical regret analysis is lacking. In (Wu, Iyer, and Wang 2018), a hierarchical bandit algorithm was developed that detects and adapts to changes by maintaining a suite of contextual bandit models and a regret sublinear in T was proved. However, the existing results assumed a uniform payoff model where all arms share a common coefficient vector representing the user interests, which fails to characterize the fact that users’ preferences towards different items vary differently. Recently, a so-called context-dependent property was considered in (Wu et al. 2019) where arms are partitioned into change-invariant and change-sensitive ones based on their context vectors to characterize the distinct reward changes. However, the changes are not completely asynchronous across arms. A more detailed comparison between various models is discussed in the next section.

Consider a contextual bandit problem with K arms and a time horizon of length T. At each time t, a recommender system observes the current player with a d-dimensional feature vector . A subset of arms is available for selection and each arm is associated with an m-dimensional feature vector . The system recommends an arm to the user and observes a random reward (i.e., clicks, ratings, etc.), which is drawn from an unknown distribution where is a time-varying unknown weight matrix representing the preferences of users towards items in the feature space. The conditional expectation of the reward given the feature vectors and the weight matrix is defined as

Without loss of generality, we assume that the probability distribution of the random reward is sub-Gaussian with parameter .2 The objective is an arm selection policy that maximizes the expected cumulative reward over the entire time horizon, i.e., where is the arm selected by policy at time t. Equivalently, we may find a policy that minimizes the expected cumulative regret de-fined as the expected reward loss of policy against the best policy in the known model case, i.e.,

where is the arm with the largest expected reward at t. In the stationary scenario where W(t) is fixed over time (i.e., ), the above formulation is equivalent to the

standard contextual bandit model with linear payoffs as studied in the literature (Auer 2002; Chu et al. 2011; Agrawal and Goyal 2013). Specifically, let vecbe the context vector3 associated with arm a at time t and vec(W) be an unknown preference vector. It is clear that . The unknown prefer- ence vector can be efficiently estimated in an online fashion at each time t via ridge regression (see the LinUCB algorithm in (Li et al. 2010a)), and is applied to the reward estimation and the arm selection at time t + 1.

In the non-stationary scenario, however, estimating W(t) is in general challenging if elements of W(t) vary arbitrarily: without constraints on the variation of the parameters, estimating W(t) is impossible. Moreover, to characterize the fact that the preferences of users towards different items vary asynchronously and distinctly, elements of W(t) should exhibit different varying patterns. However, the effects of different elements of W(t) on the obtained rewards are difficult to be distinguished, which leads to the challenge of detecting unknown changes on each element from reward observations. To address the two challenges, we turn to consider approximated reward models to simplify the problem, and adopt certain assumptions on the varying patterns of the reward parameters. Specifically, we study two reward models, i.e., the disjoint payoff model and the hybrid payoff model.

Disjoint Payoff Model

In the disjoint payoff model, we let the combination of W(t) and , i.e., be the unknown preference vector associated with arm a at time t. The expected reward of recommending item a to user u at time t is then equivalent to the inner product of and , i.e.,

We adopt a piecewise-stationary assumption on . To be specific, the time horizon is partitioned into stationary segments with change points where and . Within each segment, is assumed to be fixed, i.e., , , . The sequence of changes points may be different across arms, which characterizes the fact that users’ preferences towards different items may change asynchronously.

Hybrid Payoff Model In a more general model with hybrid payoffs, we further assume that W(t) consists of both a time-varying component and a time-invariant component , i.e., W(t) = . In particular, represents the dynamically changing preferences of users towards items and represents the stationary internal interests of users that are unaffected by the external environment.

For the time-varying component , we adopt the same approximation method as the one used in the disjoint setting and define be the arm-specific preference vector of arm a. For the time-invariant component, we define vecbe the joint coefficient vector shared by all arms. It is not difficult to see that the expected reward of recommending arm a to user u at time t satisfies that

where vecis a k-dimensional () cross-feature vector of the user-item pair. We adopt the same piecewise-stationary assumption on the arm-specific vectors as that assumed in the disjoint setting, which allows asynchronous changes across different arms.

Comparisons with Existing Models

We first compare the two payoff models with the stationary ones in the classical contextual bandit setting. It is clear that both models are direct extensions of the stationary payoff models studied in (Li et al. 2010a) where the preference vectors are assumed to be fixed over time. As discussed in the introduction section, it is more realistic to consider non-stationary preferences in real applications as users’ interests are in general time-varying.

In considering the non-stationary environment within the contextual bandit setting, the majority of existing studies (Wu, Iyer, and Wang 2018; Wu et al. 2019) assumed a uniform (joint) payoff model where all arms share a common coefficient vector representing the interests of user u. The expected reward is thus defined as

Notice that the uniform payoff model is another approximation of the bilinear model defined in (1): is the combination of and W(t), i.e., . In the literature, is assumed to be piecewise-stationary to model the time-varying interests of users. The fact that users’ preferences change differently towards different items is, however, not characterized.

The issue was partially addressed in (Wu et al. 2019) where the so-called context-dependent property was considered. It has been assumed that the expected rewards of certain arms are insensitive to the changes of (i.e., for some stationary periods i and , where is a small constant), while the other arms are change-sensitive. The partition of arms based on their context vectors models the distinct reward changes on different arms. However, the change points across arms are not completely asynchronous: it has been assumed in (Wu et al. 2019) that between any two stationary periods, there should be a sufficient number of change-sensitive arms undergo perceivable changes to distinguish the two periods. As a result, the user preferences towards a large fraction of arms change simultaneously at the change points of .

Moreover, we further study a general hybrid payoff model consisting of both arm-specific and joint preference vectors that correspond to the time-varying and the time-invariant interests of users respectively. To the best of our knowledge, the hybrid payoff model with dynamically changing user interests has not been studied in the literature.

We first consider the disjoint payoff model in this section. The key to achieving the objective of minimizing regret under the assumption of piecewise-stationary payoffs is to i) estimate the preference vectors accurately, and ii) detect the abrupt changes timely and correctly. We propose a Piecewise-Stationary LinUCB (PSLinUCB) algorithm to address the two issues.

To estimate the preference vectors, we adopt a learning structure similar to that of the LinUCB algorithm (proposed in (Li et al. 2010a) in the stationary contextual bandit setting). In particular, the unknown preference vectors are estimated through ridge regression and can be updated incrementally at each time t. To detect the preference changes timely and correctly, the key technique adopted in the algorithm is to maintain a sliding window for each arm consisting of the most recent reward observations from the arm. If the preference vector learned from observations before the sliding window cannot accurately predict the rewards observed within the window, it is likely that the preference vector has changed. A new model should then be rebuilt based on the observations after the change point.

To be more specific, the estimation and the change detection of the preference vector of every arm a can be executed independently in the disjoint payoff model. For every arm a, the algorithm maintains a sliding window and three different models , and . The sliding window of length consists of the latest observations from arm a (including the observed context vectors and the obtained rewards). consists of necessary statistics for estimating the preference vector . It is learned from observations after the last detected change point and before the sliding window . Similarly, with the same set of statistics is learned from observations within the sliding window, and is learned from all observations from the last detected change point to the current time step. In the following subsections, we describe the details of the three models and their usage in the two key components of the PSLinUCB-Disjoint algorithm: (i) parameter estimation and arm selection, and (ii) change detection and model update.

Parameter Estimation and Arm Selection

In each of the three models , and , the preference vector can be estimated by applying ridge regression to the associated set of observations. Without loss of generality, we take for an example to illustrate the estimation process. Denote as the set of observations where is the set of time steps when arm a is played from its last detected change time (initialized to be 0) to the current time step. can be estimated as where A

. The statistics Aand bcan be updated incrementally as described in(Li et al. 2010a).

Based on the estimated preference vector of every arm , we select arms according to the UCB principle Algorithm 1 Piecewise-Stationary LinUCB under the Disjoint Payoff Model (PSLinUCB-Disjoint)

to balance the tradeoff between exploration and exploitation. Similar to the LinUCB algorithm, we define a UCB index for

every arm a at time t as . The arm with the greatest index is selected and the reward observations from the selected arm is used to update the corresponding models.

Change Detection and Model Update To detect potential changes on an arm a, we use to predict the rewards of playing arm a at the time steps within the sliding window. We compare the predicted rewards with the observed ones to test if the model learned from earlier data still fits the current observations. To be specific, let be the set of observations within the sliding window. We check if , where is an input threshold.

If a change is detected on arm a, i.e., the average distance between the predicted rewards and the observed ones in the sliding window exceeds the threshold, we have to restart the learning process of arm a using only observations after the detected change point. Instead of re-constructing a new model without using history data, we exploit the observations within the sliding window again as a warm-start to accelerate learning. In particular, we initialize , which are used for arm selection and change detection respectively, with , which is the model learned from the latest observations after the change point (i.e., within the sliding window). The sliding window is then emptied to collect new observations until its length reaches again.

If no change is detected on arm a, i.e., the earlier and the current reward observations follow the same model, we should keep both sets of data to enhance the estimation accuracy. Therefore, keeps unchanged and the sliding window is right-shifted by one time step. Note that and should be updated accordingly after the rightshifting of . The detailed implementation is summarized in Algorithm 1. Note that the computation complexity in each time step is (a finite number of matrix operations for each arm) and the memory size required for learning is (three sets of statistics and a sliding window for each arm).

Regret Analysis In this subsection, we prove an upper bound on the regret of the proposed PSLinUCB-Disjoint algorithm. We first make several modifications on the algorithm without changing the underlying key strategies to get rid of certain technical diffi-culties in the theoretical analysis.

The modification includes three steps. First, to avoid heavy dependency between the estimation and the change detection of the underlying parameters and across different time steps, the observations in the sliding-window are not reused for initialization after a detected change. Besides, the change detection procedure only uses observations within the sliding window rather than all observations after the last detected change (note that uses observations before the sliding window). Second, once a change is detected on an arm, the learning procedures of all arms get restarted. Finally, a round-robin exploration step is added to guarantee sufficient exploration of every arm so that the changes in the reward models can be detected timely. Due to the page limit, the details of the modified algorithm are summarized in the appendix. Based on certain mild assumptions, we prove an upper bound on regret in the following theorem.

Theorem 1. With appropriate choices of the input parameters, the cumulative regret of the modified PSLinUCB algorithm under the disjoint payoff model satisfies:

where are constants independent of T and M is the number of total piecewise-stationary segments, i.e.,

Proof. See the appendix.

Remark 1. Assume that . The cumulative regret achieved by the modified PSLinUCB-Disjoint algorithm has a sublinear scaling in T, i.e., where the notation hides the logarithmic factor. In other words, the average regret per time step diminishes to zero as .

In the hybrid payoff model, the preference of a user towards an arm a is determined by both an arm-specific preference vector and a joint coefficient vector , which should be estimated simultaneously. Therefore, in addition to a sliding window and three models , and for each arm a, the PSLinUCB-Hybrid algorithm maintains two global models and to estimate . Specifically, is the model learned from the observations from all arms before their sliding windows and is used for change detection. is the model learned from the observations from all arms up to the current time step and is used for arm selection. The statistics in the two global models are obtained by applying ridge regression to the associated data. Due to the page limit, we omit the detailed theoretical derivations of ridge regression and only describe the process of updating the arm-specific and the global parameters.

Parameter Estimation and Arm Selection

By applying ridge regression to the observed data, it can be shown that the joint coefficient vector is estimated as where Aand bare coupled with arm-specific parameters Aand b. Therefore, the global and the arm-specific parameters should be updated simultaneously. Specifically, Aand bare initialized to Irespectively and the parameters are updated as follows:

The update procedures of Aand bare similar to the ones of A, and bas described above.

In the arm selection step, we follow (Li et al. 2010a) to define the UCB index of arm a at time t as where B. The exploration term is computed as follows:

where P .

Change Detection and Model Update

We conduct a change detection process similar to the one adopted in PSLinUCB-Disjoint to test if the preference vector of arm changes or not. The occurrence of a change on is equivalent to being replaced by a new arm with a different set of arm-specific parameters spec-ified by A, and b. As a result, the global pa- rameters Aand bare coupled with two sets of arm-specific parameters associated with both the old and the new arm. In particular, the original arm-specific parameters (i.e., A, and b) used in estimating Aand bshould be replaced by the aggregation of the parameters corresponding to the old arm (i.e., A, and b) and the new arm (i.e., A, and b):

Moreover, is re-initialized to the updated after the detected change and the arm-specific parameters are updated in the same way with that in the disjoint payoff case.

similar to that in PSLinUCB-Disjoint. The detailed implementation is summarized in Algorithm 2.

We use both synthetic and real-world data to evaluate the performance of the proposed learning algorithms under the disjoint and the hybrid payoff models. Due to the page limit, we only present the simulation results on two real-world datasets in this section. The results on synthetic data can be found in the appendix. The first real-world dataset is a collection of user-visit log information from Yahoo! front page, which is widely used for algorithm evaluation in the contextual bandit setting (Li et al. 2010a; Li et al. 2011). The Yahoo! dataset contains 45,811,883 user-visits to Yahoo Today Module in a ten-day period in May 2009. The log information of each user-visit includes a feature vector of the current user, a pool of candidate articles (arms) for recommendation associated with feature vectors, the recommended article, and the feedback from the user (click or not). It has been observed in (Wu et al. 2019) that the preferences of users towards different items are dynamically changing in this dataset. The second dataset is extracted from the Last.fm online music system, which is made available on the HetRec 2011 workshop. This dataset contains 1892 users, 17,632 artists (arms), and 92,834 user-artist listening records. Each user may assign multiple tags to the listened artists, which can be preprocessed as the context information to fit into the contextual bandit setting. Following (Hartland et al. 2006), a non-stationary environment can be simulated. We compare the proposed learning algorithms with the following baselines:

1. Random: a policy that selects arms uniformly at random. Algorithm 2 Piecewise-Stationary LinUCB under Hybrid Payoff Model (PSLinUCB-Hybrid)

Figure 1: Average CTR v.s. time in the Yahoo! dataset.

predicted reward at a single time step with the observed one to detect potential changes. In cases with larger noise (e.g., binary rewards), we modify the algorithm by using observations at multiple time steps for change detection.

Yahoo! Dataset We randomly sample a subset of data from the original dataset for testing (i.e., each user-visit is selected independently with probability 0.1). We adopt an unbiased offline evaluation method proposed in (Li et al. 2010a; Li et al. 2011) to evaluate the online performance of the proposed learning algorithms and the baseline ones.

In Figure 1, we report the average Click-Through-Rate (CTR) of different algorithms versus time. We first observe that algorithms exploiting the context information (i.e., PSLinUCB, LinUCB, and DenBand) outperform context-free ones (i.e., UCB and MUCB). This observation is rather intuitive since context vectors provide significant side information on the preferences of users towards items. In addition, under each reward model (i.e., classical context-free bandits and contextual bandits with uniform, disjoint, and hybrid payoffs), the algorithm that adapts to reward changes outperforms the one that does not (i.e., MUCB v.s. UCB, DenBand v.s. LinUCB-uniform, PSLinUCB-Disjoint v.s. LinUCB-Disjoint, and PSLinUCB-Hybrid v.s. LinUCBHybrid). In particular, PSLinUCB-Disjoint achieves a performance gain of 2.7% (2.9% at the peak) against LinUCBDisjoint and PSLinUCB-Hybrid achieves an improvement of 1.3% (2% at the peak) against LinUCB-Hybrid (see the appendix for details). The comparison results verify the assumption that users’ interests are dynamically changing and should be taken into consideration in learning.

Moreover, within the contextual bandit setting, algorithms developed under the hybrid payoff model (i.e., PSLinUCBHybrid and LinUCB-Hybrid) or the disjoint payoff model (i.e., PSLinUCB-Disjoint and LinUCB-Disjoint) achieve better performance compared with the ones developed under the uniform payoff model (i.e., DenBand and LinUCBUniform). This is because the uniform payoff model fails to exploit the personalized interests of different users. An alternative approach is to learn the preferences of every user individually. However, the amount of data associated with a

Figure 2: Average CTR v.s. time in the LastFM dataset.

single user is rather limited. Furthermore, the performance gain of PSLinUCB over DenBand (31.2% under the hybrid model and 29.5% under the disjoint model) verifies the fact that users’ preferences towards different items vary differently. We also conduct experiments to anaylze the sensitivity of the proposed algorithms to the hyper-parameters. Due to the page limit, we leave the results in the appendix.

LastFM Dataset

Given that the original LastFM dataset dose not provide context vectors of neither users nor items, we first preprocess the dataset to fit into the contextual bandit setting. Specifically, following the settings in (Cesa-Bianchi, Gentile, and Zap- pella 2013; Wu et al. 2019), we treat the ‘listened artists’ of each user as positive feedback. For each artist, we use its associated tags to create a TF-IDF feature vector and then apply PCA to reduce the dimension to 10. For each user, we adopt a method similar to the one used in (Li et al. 2010a) to generate a feature vector: we use matrix factorization to obtain a raw feature vector and then apply the K-means method to group users into 10 clusters. The fi-nal user feature is a 10-dimensional vector corresponding to the soft-membership of the user in the 10 clusters (computed with a Gaussian kernel and then normalized). In the experiment, we only consider artists that have been listened by at least 100 users and we follow (Wu, Iyer, and Wang 2018) to generate the log data. The results are presented in Figure 2 and similar conclusions with those in the experiment on the Yahoo! dataset can be drawn. In particular, PSLinUCB-Disjoint achieves a performance gain of 2% against LinUCB-Disjoint and PSLinUCB-Hybrid achieves a performance gain of 2.4% against LinUCB-Hybrid, which again verify the advantages of the proposed algorithms.

We studied a contextual bandit problem for personalized recommendation in a non-stationary environment. To characterize the fact that users’ interests towards different items vary asynchronously and distinctly, two models with disjoint and hybrid piecewise-stationary payoffs were considered. Effi-cient learning algorithms were developed under both models and theoretical analysis validating a vanishing per-time regret was provided under the disjoint payoff model. Numerical results on real-world datasets verified the advantages of the proposed learning algorithms against baseline ones.

Several issues in this work ask for future studies. First, theoretical regret analysis under the hybrid payoff model is still lacking. Moreover, one limitation of the proposed algorithm is that estimating a preference vector for every arm is costly in computation and memory, especially when the number of arms is extremely large. A potential solution is to cluster similar arms into groups and collectively learn the preferences of users towards arms within the same group.

[Abbasi-Yadkori, P´al, and Szepesv´ari 2011] Abbasi- Yadkori, Y.; P´al, D.; and Szepesv´ari, C. 2011. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2312–2320.

[Agrawal and Goyal 2012] Agrawal, S., and Goyal, N. 2012. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on Learning Theory, 39–1.

[Agrawal and Goyal 2013] Agrawal, S., and Goyal, N. 2013. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, 127–135.

[Auer, Cesa-Bianchi, and Fischer 2002] Auer, P.; CesaBianchi, N.; and Fischer, P. 2002. Finite-time analysis of the multiarmed bandit problem. Machine learning 47(2-3):235–256.

[Auer 2002] Auer, P. 2002. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research 3(Nov):397–422.

[Cao et al. 2019] Cao, Y.; Wen, Z.; Kveton, B.; and Xie, Y. 2019. Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In The 22nd International Conference on Artificial Intelligence and Statistics, 418–427.

[Cesa-Bianchi, Gentile, and Zappella 2013] Cesa-Bianchi, N.; Gentile, C.; and Zappella, G. 2013. A gang of bandits. In Advances in Neural Information Processing Systems, 737–745.

[Chu et al. 2011] Chu, W.; Li, L.; Reyzin, L.; and Schapire, R. 2011. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 208–214.

[Garivier and Moulines 2011] Garivier, A., and Moulines, E. 2011. On upper-confidence bound policies for switching bandit problems. In International Conference on Algorithmic Learning Theory, 174–188. Springer.

[Guo, Wang, and Liu 2019] Guo, X.; Wang, X.; and Liu, X. 2019. Adalinucb: Opportunistic learning for contextual bandits. arXiv preprint arXiv:1902.07802.

[Hariri, Mobasher, and Burke 2015] Hariri, N.; Mobasher, B.; and Burke, R. 2015. Adapting to user preference changes in interactive recommendation. In Twenty-Fourth International Joint Conference on Artificial Intelligence.

[Hartland et al. 2006] Hartland, C.; Gelly, S.; Baskiotis, N.; Teytaud, O.; and Sebag, M. 2006. Multi-armed bandit, dynamic environments and meta-bandits.

[Hartland et al. 2007] Hartland, C.; Baskiotis, N.; Gelly, S.; Sebag, M.; and Teytaud, O. 2007. Change point detection and meta-bandits for online learning in dynamic environments.

[Lai and Robbins 1985] Lai, T. L., and Robbins, H. 1985. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 6(1):4–22.

[Langford and Zhang 2007] Langford, J., and Zhang, T. 2007. The epoch-greedy algorithm for contextual multi-armed bandits. In Proceedings of the 20th International Conference on Neural Information Processing Systems, 817–824. Citeseer.

[Li et al. 2010a] Li, L.; Chu, W.; Langford, J.; and Schapire, R. E. 2010a. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, 661–670. ACM.

[Li et al. 2010b] Li, W.; Wang, X.; Zhang, R.; Cui, Y.; Mao, J.; and Jin, R. 2010b. Exploitation and exploration in a performance based contextual advertising system. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 27–36. ACM.

[Li et al. 2011] Li, L.; Chu, W.; Langford, J.; and Wang, X. 2011. Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms. In Proceedings of the fourth ACM international conference on Web search and data mining, 297–306. ACM.

[Liu, Dolan, and Pedersen 2010] Liu, J.; Dolan, P.; and Ped- ersen, E. R. 2010. Personalized news recommendation based on click behavior. In Proceedings of the 15th international conference on Intelligent user interfaces, 31–40. ACM.

[Sutton and Barto 1998] Sutton, R. S., and Barto, A. G. 1998. Reinforcement learning: An introduction. MIT Press.

[Thompson 1933] Thompson, W. R. 1933. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3/4):285–294.

[Wang, Wu, and Wang 2016] Wang, H.; Wu, Q.; and Wang, H. 2016. Learning hidden features for contextual bandits. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 1633–1642. ACM.

[Wu et al. 2019] Wu, Q.; Wang, H.; Li, Y.; and Wang, H. 2019. Dynamic ensemble of contextual bandits to satisfy users’ changing interests. In The World Wide Web Conference, 2080–2090. ACM.

[Wu, Iyer, and Wang 2018] Wu, Q.; Iyer, N.; and Wang, H. 2018. Learning contextual bandits in a non-stationary environment. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, 495– 504. ACM.

[Yu and Mannor 2009] Yu, J. Y., and Mannor, S. 2009. Piecewise-stationary bandit problems with side observations. In Proceedings of the 26th Annual International Conference on Machine Learning, 1177–1184. ACM.

[Yue and Joachims 2009] Yue, Y., and Joachims, T. 2009. In- teractively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, 1201–1208. ACM.

[Zeng et al. 2016] Zeng, C.; Wang, Q.; Mokhtari, S.; and Li, T. 2016. Online context-aware recommendation with time varying multi-armed bandit. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2025–2034. ACM.

Modified PSLinUCB-Disjoint Algorithm

To simplify the algorithm design and regret analysis, we assume that the candidate arm set at each time is fixed, i.e., . The details of the modified PSLinUCB-Disjoint algorithm are summarized below in Algorithm 3.

Proof of Theorem 1

Before we present the proof on the regret upper bound, we first introduce some notations used in the analysis. Let be the change-points where . Define where are input parameters of the modified PSLinUCB policy. Let be the amplitude of the preference change from user x to arm a at the i-th change point, i.e.,

Without loss of generality, we assume that the sub-Gaussian parameter in the distribution of the random reward is 1. We further assume that . The proof of Theorem 1 is based on three key lemmas as presented below. To avoid breaking the logic flow, we leave the detailed proofs of the three lemmas to the next three appendices.

We first consider a stationary scenario where the reward model, i.e., is fixed for all . Lemma 1. Consider a stationary scenario with M = 1, consider and , the expected cumulative regret of the modified PSLinUCB algorithm is upper bounded as follows:

where is the first detection time.

Second, we upper bound the probability of raising false alarms, i.e., changes are detected in the stationary environment.

Lemma 2. Consider a stationary scenario with M = 1, consider , the probability of false alarm is upper bounded as follows:

if the threshold b satisfies (33) for all . Let and assume

We further upper bound the probability of a late detection.

Lemma 3. Consider a piecewise-stationary scenario with . Assume that for some and for any x. Suppose and . Then we have

Theorem 1 can be proved based on the above three lemmas and properties of the restart process of the algorithm. Specifically, define events and . Then we

have

Note that the first inequality follows from Lemma 2 on bounding the probability of false alarm in the first fist stationary segment provided that b satisfies (33) and . The second inequality follows from Lemma 1 on . The next step is to bound , which satisfies

where the second inequality holds due to the following facts

• according to Lemma 2, provided that b satisfies (33) and

• according to Lemma 3;

• since and cannot happen simultaneously.

The third inequality holds due to the fact that the learning process is restarted once a change is detected and is the expectation taken over the random process induced by the learning algorithm after the first detected change time.

Finally, if we recursively upper bound by the same arguments as above and repeat the process for times, we have

Let δ/T, γ

, and apply Cauchy-Schwatz inequality to the second term, we can obtain

Proof of Lemma 1

Let be the indicator function and be the one-step regret at time t when the algorithm plays arm . The expected cumulative regret can be partitioned as follows:

is random selected)]

is selected by UCB index)].

According to the algorithm, it is not difficult to see that the second term on the RHS of the above inequality satisfies

is random selectedK

For the last term, we have:

no change detected up to time is selected by UCB index)]

no change detected up to time is selected by UCB index)

Note that if no change has been detected up to time , the estimation of has not been restarted and thus, is calculated based on all past observations. Thus, according to the algorithm, the RHS of (22) is upper bounded by

no change detected up to time is selected by UCB index)

is selected by UCB index)

where and . The first inequality simply follows from Lemma 2 in (Guo, Wang, and Liu 2019). By selecting and t, the second inequality follows from the fact that the UCB index of is greater than at time t. The last inequality also holds according to Lemma 2 in (Guo, Wang, and Liu 2019) and the selection of . It has been shown in (Abbasi-Yadkori, P´al, and Szepesv´ari 2011) (specifically, Theorem 2) that for an arm a and any constant , with probability at least ,

Therefore, if we choose and , then with probability at least , we have and t, and consequently, (23) holds with probability . Moreover, with probability when the upper bounds in (23) does not hold, the cumulative regret is trivially upper bounded by T.

Furthermore, let be the set of time steps when arm a is selected up to time T, the RHS of (23) satisfies:

where the first and third inequalities hold by Cauchy-Schwarz inequality and the second inequality hold by Lemma 11 in (Abbasi-Yadkori, P´al, and Szepesv´ari 2011) and Lemma 3 in (Guo, Wang, and Liu 2019). In summary, the expected cumulative regret under the stationary environment is upper bounded by

Proof of Lemma 2 Define be the first detection time of arm a. Then and

Let be the last observations of arm a before time t and define

where is the estimate of based on the observations in . According to the modified PSLinUCB algorithm, we have

Moreover, we define . Then it is not difficult to see that at each , the observations used for change detection are disjoint and thus, is a random variable with the geometric distribution:

where and thus

To upper bound p, we have

For the first term in the RHS of (32), if we choose b to satisfy the following condition for any t:

where , then the first term in the RHS of (32) is upper bounded by according to Lemma 2 in (Guo, Wang, and Liu 2019) and Theorem 1 in (Abbasi-Yadkori, P´al, and Szepesv´ari 2011). The second term can be bounded by according to the Hoeffding’s inequality. Let and , it is not difficult to see that

(34) Since for a > 1 and , it can be shown that

Proof of Lemma 3

Notice that the round-robin exploration in the algorithm guarantees that within L/2 time steps, each arm is sampled at least times. We upper bound the probability of as follows: consider a be the arm at which the change point occurs. Let t be the time step when a is sampled times in the new stationary segment (notice that ). The change at a is not detected only if one of the following events happens:

x, t ω/θold

t i

t i

where and correspond to the ground-truth preference vectors of arm a after and before the change point. Therefore,

(39) The first two terms has been shown to be upper bounded by in the proof of Lemma 2 and the last term equals 0 under the condition that for any x. Therefore, the conclusion in Lemma 3 holds.

Additional Numerical Results Regret Analysis on Synthetic Datasets We use synthetic datasets to evaluate the regret performance of the proposed learning algorithms. In the first experiment, we generate a dataset under the disjoint payoff model. Specifically, we assume a time horizon of length T = 20000. We randomly generate K = 10 arms. Each arm a is associated with a m-dimensional (m = 5) feature vector with . We consider a single user setting where a user u is associated with a d-dimensional (d = 5) feature vector with . The d-dimensional preference vectors are randomly generated satisfying the piecewise-stationary assumption (the preference vector changes every 2000 time steps) and . The reward of playing an arm a at time t is generated according to the disjoint payoff model, i.e., , where is a Gaussian noise with (mean) and (standard deviation).

We compare the cumulative regret of PSLinUCB-Disjoint and LinUCB-Disjoint. To guarantee a fair comparison, the parameters balancing the tradeoff between exploration and exploitation in the UCB indices of the two algorithms are equal (). In PSLinUCB-Disjoint, we set and . The experiment is run 100 times and the simulation results are included in Fig. 3. It can be seen that the PSLinUCB-Disjoint algorithm adapts to the changing environment and achieves a lower cumulative regret (30% performance gain).

In the second experiment, we consider the hybrid payoff model. In addition to the parameters generated in the first experiment, we further construct an -dimensional joint preference vector . The random reward of playing an arm a at time t is generated according to the hybrid payoff model, i.e., , where vecand is a Gaussian noise with and . We compare the regret performance of PSLinUCB-Hybrid and LinUCB-Hybrid with . In PSLinUCB-Hybrid, we set and . The experiment is also run 100 times and the simulation results are included in Fig. 4. Similar performance gain can be observed.

Figure 3: Regret v.s. time under the disjoint payoff model.

Figure 4: Regret v.s. time under the hybrid payoff model.

Recommendation Performance on Real Datasets The detailed recommendation performance (i.e., CTR) of the proposed algorithms along with baseline ones on the Yahoo! dataset are summarized in Table 1. In PSLinUCB-Disjoint, we set , , and . In PSLinUCB-Hybrid, we set , and . In addition to the comparison results discussed in the main file, PSLinUCB-Disjoint and PSLinUCB-Hybrid achieves a performance gain of 59.2% and 61.2% compared with the Random policy, which does not learn from the observation history.

In the second experiment on LastFM, the pre-processing step on the dataset, although follows the same strucutre, is different in details from the one adopted in (Wu et al. 2019). Therefore, the DenBand algorithm does not achieve the expected performance as claimed in (Wu, Iyer, and Wang 2018). In Table 2, we only report the simulation results of the proposed algorithms and their corresponding opponents in the stationary setting. Note that in PSLinUCB-Disjoint, . In PSLinUCB-Hybrid, .

Sensitivity Analysis At last, we test the proposed algorithms’ sensitivity to hyper-parameters: and on both the Yahoo! dataset and the LastFM dataset. Since the effect of users’ changing interests on the recommendation performance emerges after a sufficient time of learning, we use the first 1/2 of the Yahoo dataset and the entire LastFM dataset for testing. From

Table 1: Comparison of CTR on Yahoo dataset.

Table 2: Comparison of CTR on LastFM dataset.

the results shown in Figure 5a and Figure 5b, we observe that both PSLinUCB-Disjoint and PSLinUCB-Hybrid are relatively robust towards the change of the hyper-parameter within certain ranges.

Figure 5: Sensitivity analysis.