Improved Algorithm on Online Clustering of Bandits

1 Introduction

The problem of stochastic multi-armed bandit (MAB) [Bubeck et al., 2012; Lattimore and Szepesv´ari, 2018] has been widely studied in the field of statistics and machine learning, where the learner selects an action each round with the goal of maximizing the cumulative rewards over all rounds (or equivalently minimize the cumulative regret). One successful application of MAB algorithms is recommendation systems [Aggarwal, 2016], such as recommendations of movies, restaurants and news articles. For the setting where new users and items constantly appear where simultaneous exploration and exploitation are naturally needed, bandit algorithms can cope with the "cold start" problem and improve itself as time goes on.

To adjust bandit algorithms for large-scale applications, structural assumptions are usually added on actions and reward functions, among which linear structure is one of the most common due to its simplicity and effectiveness. Each item in the stochastic linear bandits [Abe and Long, 1999; Rusmevichientong and Tsitsiklis, 2010; Dani et al., 2008; Abbasi-Yadkori et al., 2011] is represented by a feature vector whose expected reward is an unknown linear function on the feature vector. In many systems certain side information about users and items are employed as the feature vectors to guarantee recommendation quality [Li et al., 2010; Chu et al., 2011].

Usually user features are not accurate enough or even do not exist to characterize user preferences. When user features exist, these static features are usually combined together with item features to be actions in linear bandit models. This processing might have implacable modeling bias and also neglect the often useful tool of collaborative filtering. One way to utilize the collaborative effect of users is to discover their clustering structure. Clustering methods have been proved to be important in supervised/unsupervised recommendations [Linden et al., 2003; Woo et al., 2014]. The works [Gentile et al., 2014; Li et al., 2016] start to bring these useful techniques to bandit algorithms. These online clustering of bandit algorithms adaptively learn the clustering structure over users based on the collaborative recommendation results to gather information of users' similarity and still keep certain diversity across users.

There are two main challenges in the existing works on online clustering of bandits [Gentile et al., 2014; Li et al., 2016; Korda et al., 2016; Gentile et al., 2017; Li, 2016]. (a) The existing works assume users come to be served in a uniform manner. However, as stated by long tail effect and 80/20 rule, the imbalance between users always exist especially with a large number of low-frequency users. The low-frequency users deteriorate the performance of existing algorithms. (b) The existing works use graphs to represent users, use edges to denote the similarity between users and use connected components to represent clusters. As a result, the learner may split two dissimilar users into two clusters only when it cuts every path between these two users. Even when the edge (representing the similarity) between two users are cut, the two users might still need to stay in the same cluster for a long time. Therefore these algorithms are not efficient in identifying the underlying clusters.

To overcome the first problem, we include frequency properties into the criterion of an underlying clustering structure. To overcome the second problem, we split a user out of her current cluster once we find the current cluster contains other users dissimilar to this one. Since the split operation might be a bit radical and premature, we add a new merge operation to reconcile the radical effect of the split operation. Based on these two building operations, complex graph structure can be discarded and replaced by simple set structures where each cluster is represented by a set of users.

This paper makes four major contributions:

1. We generalize the setting of online clustering of bandits to allow non-uniform frequency distributions over users.
2. We design both split and merge operations on clusters together with set representations of clusters to accelerate the process of identifying underlying clusters.

1. We analyze the regret of our new algorithm to get a regret bound free of the term 1/pmin, where pmin is the minimal frequency probability among all users and the existing algorithms could not avoid it.
2. We compare our algorithm to the existing algorithms on both synthetic and real datasets. A series of experiments consistently show the advantage of our algorithm over the existing ones.

1.1 Related work

The most related works are a series of studies on online clustering of bandits. Gentile et al. [2014] first establish the setting of online clustering of bandits and first show the effectiveness of using graph structure to represent clustering over users. A follow-up [Li et al., 2016] considers the collaborative filtering effects on both users and items but only under the setting of static item pool. They maintain a clustering over items and for each item cluster there is a clustering over all users. Their analysis is only built on a special case that the items form an orthonormal basis in the feature space. Based on [Gentile et al., 2014], Korda et al. [2016] design a distributed version of confidence ball algorithms in peer to peer networks with limited communications where the peers in the same cluster solve the same bandit problem. Gentile et al. [2017] present a context-aware clustering bandit algorithm where the clustering structure depends on items, though with a high computational cost. All these works assume the user frequency distribution is uniform and use connected components of graphs to represent clusters.

Besides these works with new algorithms and theoretical guarantees, there are many progress of applying these online algorithms in real applications. Nguyen and Lauw [2014] design a variant of clustering of bandit algorithms by performing k-means clustering method [MacQueen, 1967] on the estimates of user weight vectors with a known number of clusters. Christakopoulou and Banerjee [2018] present a variant of clustering of bandit algorithms based on Thompson sampling and allow recommending a list of items to users. Kwon [2018] allows the underlying clustering has overlapping. All these works focus on experimental performance and do not include theoretical guarantees, especially on regret bounds. Li and Zhang [2018] study an application of using clustering of bandit algorithms to improve the performance of recommending a list of items under a specific click model, and they provide a regret guarantee.

There is a group of works on stochastic low-rank bandits [Katariya et al., 2017b; Katariya et al., 2017a; Kveton et al., 2017]. They assume the reward matrix of users and items are of low-rank and the learner selects a user-item pair each time. The goal of the learner is to find the user-item pair that has the maximum reward. This is different from the setting of online clustering of bandits where there is no control over user appearances and the goal of the learner is to maximize satisfaction of each appearing user.

The works on linear bandits are cornerstones of clustering of bandits, where the latter has different weight vectors and adaptively clusters users. It is first studied by [Abe and Long, 1999] and refined by [Dani et al., 2008; Abbasi-Yadkori et al., 2011] and many others. Turgay et al. [2018] present a similar work to make use of collaborative results but they assume the similarity information is known.

2 Model and ProblemDefinitions

In this section, we formulate the setting of "online clustering of bandits". There are nu users, denoted by the set [nu] = {1, . . . , nu}, with a fixed but unknown distribution p = (p1, . . . , pnu ) ∈ ∆nu over users. Here ∆n = {x ∈ [0, 1]n : ∑ni=1 xi = 1} denotes the simplex in Rn . There is also a fixed but unknown distribution ρ over {x ∈ Rd : ‖x‖ ≤ 1}, which is the set of feature vectors for all items, and we simply call such a feature vector an item. At each time t, a user it ∈ [nu] is randomly drawn from the distribution p, and L items are drawn independently from distribution ρ to form a feasible item set Dt. The learning agent receives the user index it and the feasible item set Dt, selects an item xt ∈ Dt and recommends it to the user. After the user checks the item xt, the learning agent receives a reward yt. The setting follows the previous work [Gentile et al., 2014] but allows non-uniform distribution over users.

Let Ht = {i1, x1, y1, . . . , it-1, xt-1, yt-1, it} be all the information after receiving the user index in time t. Then the action xt is Ht-adaptive. Henceforth, we will write Et [·] for E [· | Ht] for the sake of notational convenience, use the boldface symbols to denote random variables, and denote [n] to be the set {1, . . . , n}.

For any time t, given a fixed user i at time t and a fixed item x ∈ Dt selected for user i, we define the random reward of item x for user i to be yt(i, x) = θ⊤ i x+εi,t,x, where (a) θi is a fixed but unknown weight vector in Rd×1 with ‖θi‖ ≤ 1, independently of other items and other user behaviors; and (b) εi,t,x is an Ht-conditional random noise with zero mean and R-sub-Gaussian tail, i.e. E [exp(νεi,t,x)] ≤ exp(R2 ν 2 /2) for every ν ∈ R. Then the mean reward is E [yt(i, x)] = θ⊤ i x. At time t, the learning agent recommends xt to user it and receives reward yt(it, xt), which satisfies

Suppose there are m (unknown) different weight vectors in the set {θi : i ∈ [nu]}. An underlying clustering exists over the users according to the weight vectors, where the users with the same weight vector form a cluster. The goal is to learn the underlying clustering to help the recommendation process. We make the following assumptions on the weight vectors {θi : i ∈ [nu]}, the distribution p over users, and the distribution ρ on items.

Gap betweenweight vectors. For any two different weight vectors θi1 ̸= θi2 , there is a (fixed but unknown) gap γ between them: ‖θi1 - θi2 ‖ ≥ γ > 0.

Itemregularity. For itemdistribution ρ, Ex∼ρ[xx⊤] is full rank with minimal eigenvalue λx > 0. Also at all time t, for any fixed unit vector θ ∈ Rd , (θ⊤x)2 has sub-Gaussian tail with variance parameter σ2 ≤ λ2x /(8 log(4L)). We assume a lower bound for λx is known.

Gap between user frequencies. Users with same weight vectors will have same frequencies: θi1 = θi2 implies that

Algorithm 1 SCLUB

• 1: Input: exploration parameter αθ, αp > 0, and β > 0;
• 2: Initialize information for each user i ∈ [nu] by Si = Id×d, bi = 0d×1, Ti = 0;
• 3: Initialize the set of cluster indexes by J = {1} and initialize the single cluster by S1 = Id×d, b1 = 0d×1, T 1 = 0, C 1 = [nu], j(i) = 1, ∀i;
• 4: for s = 1, 2, . . . do
• 5: Mark every user unchecked for each cluster;
• 6: For each cluster j, compute ˜ T j = T j , and ˜θj = (Sj )-1bj ;
• 7: for t = 1, . . . , 2s do
• 8: Compute the total time step τ = 2s -2+ t;
• 9: Receive a user iτ and an item set Dτ ⊂ Rd ;
• 10: Get the cluster index j = j(iτ) and its associated information (Sj , bj , T j );
• 11: Recommend itemxτ = argmaxx∈Dτ U(x) where

to user iτ and receive feedback yτ

• 12: Run Update
• 13: Run Split
• 14: Mark user iτ has been checked;
• 15: RunMerge
• 16: end for t
• 17: end for s

pi1 = pi2 . Also for any two different user frequency probabilities pi1 ̸= pi2 , there is a (fixed but unknown) gap γp between them: |pi1 - pi2 | ≥ γp > 0.

All the assumptions except the last one follow the previous work [Gentile et al., 2014]. The first part of last assumption could be relaxed. Discussions are provided in a later section.

The optimal item for user it in round t is x∗it,Dt = argmaxx∈Dt θ⊤ it x. Then the expected regret for user it in time t is Rt = θ⊤ it x∗it,Dt - θ⊤ it xt. The goal of the learning agent is to minimize the expected cumulative regret

where the expectation is taken over the randomness of users i1, . . . , iT , the randomness of the item sets D1, . . . ,DT and the possible randomness in selected items x1, . . . , xT .

3 Algorithm

In this section, we introduce our algorithm of "set-based clustering of bandits (SCLUB)" to deal with the online clustering of bandit problem. Recall that the related previous work [Gentile et al., 2014; Li et al., 2016] adopted connected components in graphs to represent clusters and the learning process only split clusters. In contrast, our algorithm uses sets to represent clusters and allow both split and merge operations on sets in the learning process. The pseudocode is provided in Algorithm 1.

Algorithm 2 Update

Update the information for user iτ and cluster j

Algorithm 3 Split

user i′ ∈ Cj with ∣∣ˆpiτ - ˆpi′ ∣∣ > 2αpF(τ) then / / Split user iτ from cluster j and form a new cluster j ′ (= max J + 1) of user iτ

end if

In the algorithm, we store a profile of (Si, bi, Ti) for each user i, where Ti is the number of times that the user i has appeared, Si is the Gramian matrix and bi is the moment vector of regressand by regressors. For example, if (x1, y1), . . . , (xn, yn) are pairs of items and corresponding rewards collected for user i before time t, then

The user profiles are initialized in the beginning of the algorithm (line 2), and the clustering is initialized to be a single set with index 1 containing all users (line 3). We store a profile of (Sj , bj , T j , Cj ) for each cluster j, where Cj is the set of all user indexes in this cluster and

are the aggregate information in the cluster j. As a convention, we use subscript Si, bi, Ti to denote the information related to a user i and use superscript Sj , bj , T j to denote the information related to a cluster j.

The learning agent proceeds in phases (line 4), where the s-th phase contains 2s rounds (line 7). Each phase has an accuracy level such that the learner could put accurate clusters aside and focus on exploring inaccurate clusters. In the beginning of each phase, mark every user to be unchecked (line 5), which is used to identify good clusters in the current accuracy level. If all users in a cluster are checked, then

Algorithm 4 Merge

for any two checked clusters j1 < j2 satisfying

and

do

/ / Merge them: add information of cluster j2 to cluster j1 and remove cluster j2

end for

this cluster is checked to be an accurate cluster in the current phase. Compute the estimated weight vectors for each cluster (line 6), which serve as the pivots to be compared for splitting its containing users. Note that the pivot weight vectors are denoted as ˜θj instead of ˆθj .

At each time t in the s-th phase, a user iτ comes to be served with candidate item set Dτ (line 9), where τ denotes the index of the total time step (line 8). First obtain the information (Sj , bj , T j ) for the cluster j of user iτ (line 10) and then recommend based on these information (line 11). Here ‖x‖A = √x⊤Ax for any positive definite matrix A. After receiving feedback yτ , the learner will update information (Algorithm 2) and check if a split is possible (Algorithm 3).

By the assumptions in Section 2, users in one cluster have same weight vector and same frequency. Thus if a cluster is a good cluster, which only contains users of same underlying cluster, the estimated parameters for containing users will be close to estimated parameters of the cluster. We call a user i is consistent with the current cluster j if ˆ θi is close to ˆ θj and ˆ pi is close to ˆ pi′ for any other user i′ of cluster j. If a user is inconsistent with the current cluster, the learner will split her out (Algorithm 3).

We call two checked clusters consistent if their estimated weight vectors and estimated frequencies are close enough. The algorithm will merge two checked clusters if they are consistent (Algorithm 4). Here ˆ pj = T j /(∣∣C j ∣∣ τ) is the average frequency of cluster j. The condition of clusters to be checked is to avoid merging two clusters that are not accurate enough in the current level. The operations of split and merge, together with the conditions, can guarantee that the clusters are good at the end of each phase in the corresponding accuracy level with high probability (the analysis is part of the regret bound proof).

4 Results

Recall that d is the feature dimension, m is the (unknown) number of clusters and nu is the number of users. Let nj

be the (unknown) number of users in cluster j and pj be the (unknown) frequency for cluster j, which is the sum of (unknown) user frequencies in cluster j. The following main theorem bounds the cumulative regret of our algorithm SCLUB.

Theorem 1 Suppose the clustering structure over the users, user frequencies, and items satisfy the assumptions stated in Section 2 with gap parameters γ, γp > 0 and item regularity parameter 0 < λx ≤ 1. Let αθ = 4R√d/λx, αp = 2 and β = R√d ln(1 + T/d) + 2 ln(4mnu). Then the cumulative regret of the algorithm SCLUB after T rounds satisfies

Proof. [sketch] The proof is mainly based on two parts. The first part bounds the exploration rounds to guarantee the clusters partitioned correctly. The second part is to estimate regret bounds for linear bandits after the clusters are partitioned correctly.

By Chernoff-Hoeffding inequality, we prove when τ ≥ O ( 1 γ 2 p ln(T) + 1 pi ln(T)) the distance of pi and ˆ pi is less than γp/2. Then the users with different frequencies will be assigned to different clusters. Thus, the cluster containing user i only contains users with the same frequency probabilities, for all user i.

Then by the assumption of item regularity, when τ ≥ O ( 1 γ 2 p ln(T) + 1 pi ln(T) + 1 piγ 2 λ3x ln(T)) the estimated weight vectors will be accurate enough for all the users with the frequency probability same as pi. The 2-norm radius for the confidence ellipsoid of the weight vector will be less than γ/2. Thus the split and merge operations will function correctly for users. Next, we prove that if two clusters containing the users of same frequency probabilities have accurate estimates for weight vectors and frequencies, the combined cluster inherits the accuracies with high probability. Thus, the combination steps can continue until it contains all users of an underlying cluster.

After the cluster j with frequency probability pj is correctly partitioned, the recommendation is based on the estimates of cluster weight vector. The regret for the second part reduces to linear bandits with pj T rounds. □

The proof is much different from that of CLUB [Gentile et al., 2014] with the additional frequency probability and merge operation. The full proof is put in the supplementary materials.

4.1 Discussions

First, we compare our regret bound with that of CLUB. Since CLUB is designed and proved only for uniform distribution over users, we first generalize the regret bound of CLUB to the setting of arbitrary distribution over users.

Theorem 2 Under the same setting with SCLUB, the cumulative regret of the algorithm, CLUB, after T rounds satisfies

Note that in the degenerate setting where the distribution p over users is uniform, pmin = 1/nu and the regret bound recovers the one in the previous work [Gentile et al., 2014].

In real applications, there might be a lot of infrequent users with frequency close to 0. Since the algorithm CLUB initializes with a complete graph or a random connected graph, there would be a lot of infrequent users connecting with frequent users. Infrequent users receive a recommendation once a long time. Thus it takes a long time to differentiate them from frequent users, or to be split into a different cluster (connected component) from frequent users. Then the recommendations for frequent users would be polluted by these infrequent and dissimilar users for a long time. The length of rounds to separate infrequent dissimilar users is proportional to 1/pmin, the minimal frequency over all users. pmin could be arbitrarily small in real applications, the log term in regret bound for CLUB is not satisfactory. Due to an additional care on frequencies, SCLUB could get rid of the uncontrollable term 1/pmin.

The assumption that users with same weight vectors have same frequencies is based on the intuition that frequent users and infrequent users usually have different preferences. It can be relaxed to that users with same weight vectors have close frequencies. For more general cases, a new structure of nested clusters could help where the infrequent users could use the information of frequent users but not vice versa. We leave this as interesting future work.

Second, our result can be generalized by allowing multiple users each round. In applications the recommender system will update itself every a fixed time slot, and during each time slot, multiple users will be served using the same history information.

Theorem 3 Under the same setting with SCLUB, each user appear with frequency pi ∈ [0, 1], then the cumulative regret of the algorithm after T rounds satisfies

where ¯ p = ∑nu i=1 pi is the sum of all user frequencies.

Note this recovers the regret bound in Theorem 1 when ¯ p = 1. The regret bound for CLUB can also be generalized in a similar way.

Third, if the clustering structure is known, the setting would be equivalent to m independent linear bandits, each with the expected number of rounds pj T. Then the regret bound would be O(d ∑mj=1 √pj T ln(T)) by [AbbasiYadkori et al., 2011] which matches the main term of ours

(1). The upper bound reaches its maximumO(d√mT ln(T)) when p1 = · · · = pm = 1/m. Also the regret lower bound in this case is Ω(∑mj=1 √dpj T) by [Dani et al., 2008] which matches the main term of (1) up to a term of √d ln(T ).

Fourth, we would like to state the additional benefit of SCLUB in privacy protection. To protect user privacy, when a user i comes to be served, the learning agent will have the only access to the information of user i and some aggregate information among users, but does not have the access to other individual users' information. In this sense, lack of other individual users' information will make existing graphbased methods [Gentile et al., 2014; Li et al., 2016] inapplicable. Our algorithm SCLUB only uses information of user i and aggregate information of clusters to split and merge.

Due to space limit, more discussions are put in the supplementary materials.

5 Experiments

SCLUB algorithm is compared with CLUB [Gentile et al., 2014], LinUCB-One which uses a single estimated weight vector for all users and LinUCB-Ind which uses a separate estimated weight vector for each user on both synthetic and real datasets.

5.1 Synthetic experiments

We consider a setting of nu = 103 users with m = 10 clusters where each cluster contains equal number of users. The weight vectors θ1, . . . , θm and item vectors at each round are first randomly drawn in d - 1 (d = 20) dimension with each entry a standard Gaussian variable, then normalized, added one more dimension with constant 1, and divided by √2. The transformation is as follows

This transformation on both the item vector x and weight vector θ is to guarantee the mean 〈θ, x〉 lies in [0, 1]. The parameters in all algorithms take theoretical values. The comparisons on theoretical computational complexities of these algorithms is put in supplementary materials. The evolution of the regret as a function of time is shown in the first row of Figure 1 1 . The regrets at the end and total running times are given in supplementary materials. The left figure (a) is under the setting of uniform distribution over all users where each user has a frequency 1/nu; middle figure (b) is under the setting of arbitrary distribution over clusters where the users in the same cluster have the same frequency probability; right figure (c) is under the setting of arbitrary distribution over users.

The performance of SCLUB improves over CLUB by 5.94% (Figure 1(1a)) even in the setting of CLUB where the frequency distribution over users is uniform. The reason is that CLUB uses connected components of graphs to represent clusters and if it wants to identify the underlying cluster of

1 The parameters of CLUB are theoretical values and might be suboptimal. We do not optimize the parameters of any algorithm and just use theoretical values of the parameters in all algorithms including SCLUB.

(1) Synthetic Dataset

a user i, it has to delete every bad edge of its neighbors (and neighbors of neighbors, etc.). In comparison, SCLUB is much faster, will split a user i out if it finds any inconsistency from her current running cluster, and merge her to any consistent running cluster. The improvement is enlarged to be 13.02% (Figure 1(1b)) in the setting of Section 2 where users in the same cluster have the same frequency probability but users in different clusters might have different frequencies. SCLUB is robust in the setting of arbitrary distribution over users where the assumptions in Section 2 might fail and can still improve over CLUB by 14.69% (Figure 1(1c)).

5.2 Real datasets

We use the 20m MovieLens dataset [Harper and Konstan, 2016] which contains 20 million ratings for 2.7×104 movies by 1.38×105 users and Yelp dataset 2 which contains 4.7 million ratings of 1.57×105 restaurants from 1.18 million users. The Yelp dataset is more sparse than MovieLens. For each of the two real datasets, we extract 103 items with most ratings and nu = 103 users who rate most. Then use the rating matrix to derive feature vectors of d - 1 (d = 20) dimension for all users by singular-value decomposition (SVD). The feature vectors are also processed as (3) and the resulting vectors are regarded as the underlying weight vectors of each user.

The performances are shown in Figure 1(2) where (2a)(2b) are for MovieLens dataset and (2c)(2d) are for Yelp dataset. (2a)(2c) are under the setting of uniform distribution over users and (2b)(2d) are under the setting of arbitrary distribution over users. Since there is no underlying clustering over the users, we do not experiment on the setting of arbitrary distribution over clusters like Figure 1(1b). The algorithms of SCLUB and CLUB adaptively find finer and finer clustering as more data flows in. The performance of SCLUB improves over CLUB by 5.94%, 14.84%, 5.94%, 16.24% respectively.

2 http://www.yelp.com/dataset challenge

6 Conclusions and FutureWork

In this paper, we extend the existing setting for online clustering of bandits to include non-uniform distribution over users. The new set-based algorithm together with both split and merge operations clusters users adaptively and is proven with a better theoretical guarantee on cumulative regrets than the existing works. Our algorithm also has an additional benefit of privacy protection. The experiments on both synthetic and real datasets show that our algorithm is consistently better then the existing works.

One interesting future direction is to explore the asymmetric relationships between users, whereas all existing works use symmetric relationships including ours. For example, recommendations of low-frequency users can use information (or feedback) from high-frequency users, but not vice versa. This idea can be extended by using nested clusters where an underlying cluster of frequent users can be a subset of another underlying cluster containing many infrequent users. Another interesting problem is to generalize the idea of our method to collaborative filtering of both users and items such as Li et al. [2016]. Also extending [Li et al., 2016] to the general setting of changing item set would be a challenge one.

Acknowledgements

This work was partially supported by The Chinese University of Hong Kong Direct Grants [ID: 4055073 and 4055104]. Wei Chen is partially supported by the National Natural Science Foundation of China (Grant No. 61433014).