{'fraction_non_alphanumeric': 0.04458476321207962, 'fraction_numerical': 0.015593685655456418, 'mean_word_length': 4.436716417910448, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Local Clustering in Contextual Multi-Armed Bandits

We study identifying user clusters in contextual multi-armed bandits (MAB). Contextual MAB is an effective tool for many real applications, such as content recommendation and online advertisement. In practice, user dependency plays an essential role in the user's actions, and thus the rewards. Clustering similar users can improve the quality of reward estimation, which in turn leads to more effective content recommendation and targeted advertising. Different from traditional clustering settings, we cluster users based on the unknown bandit parameters, which will be estimated incrementally. In particular, we define the problem of cluster detection in contextual MAB, and propose a bandit algorithm, LOCB, embedded with local clustering procedure. And, we provide theoretical analysis about LOCB in terms of the correctness and efficiency of clustering and its regret bound. Finally, we evaluate the proposed algorithm from various aspects, which outperforms state-of-the-art baselines.


INTRODUCTION
The recommender system is ubiquitous in online applications. However, in the cold-start setting and the rapid change of recommendation contents, the conventional approaches that demand sufficient historical records, e.g., collaborative filtering [29,31], usually suffer from the sub-optimal performance [16,22]. This dilemma between the exploration of new information and the exploitation of empirical feedback also exists in clinical trials [6,13], crowdsourcing [44,45]. Multi-Armed Bandit (MAB) has been extensively studied for online decision making and provides principled solutions for the dilemma of exploration and exploitation [1,4,7].
One of MAB's common applications is the personalized recommendation [1,10,12,16,[22][23][24]33], such as the recommendation of movies, music, and articles for a user. In contextual MAB, in each round, a set of context vectors is presented to incorporate the side information of recommended items, and an unknown bandit parameter is held for each user to formulate his/her preference (i.e., how the user interacts with the environment). Then, the learner uses some strategy to choose a context vector and receives the corresponding reward. In this paper, we consider one common setting that the received reward is computed by a linear function of a context vector and the bandit parameter. [1,10,11,16,[22][23][24].
Standard bandit algorithms view each user as an individual and make recommendations only based on the user's own historical rewards, not taking other users' feedback into account [1,10,12,22,33]. In practice, mutual influence among people does exist and plays an essential role in a user's action. Hence, leveraging user dependency is able to improve the quality of recommendation. For example, in a music recommendation platform, some users are facing a fixed set of songs that is formulated as a set of arms. The users who have similar tastes can be clustered into a group; then, when a learner is about to recommend a song (arm) to a user, the songs that have been rated highly by other users in the same group should be taken into account. Such applications can be easily found in movie/article/news recommendations.
A line of works [15,16,23,24] has been proposed to incorporate the user dependency in the contextual MAB framework. Consider the scenario that many users are facing a fixed set of arms. In each round, a user is given, and the learner needs to pull an arm for the user, obtaining a reward. As the user's bandit parameter is unknown, these works cluster users based on the empirical estimate of the bandit parameter, using a top-down hierarchical clustering procedure. When trying to select the optimal arm, instead of only using the user's own historical rewards in standard bandits, this line of works chooses the arm based on all the users' historical rewards from the same cluster as the current user, thus improving the quality of recommendation.
However, this line of works suffers from two major drawbacks. First, they apply a strict assumption to the definition of a cluster [15,16,23,24], i.e., they consider the users within the same cluster to share exactly the same bandit parameter. In real applications, this assumption is often violated: users may have similar tastes or preferences (represented by bandit parameters), but they hardly have exactly the same ones. For example, Figure 1 shows the twodimensional mapping of 60 users' bandit parameters on MovieLens dataset, and none of them have the same bandit parameters. Second, existing works [15,16,23,24] do not evaluate the quality of the obtained user clusters, and thus are not able to automatically output good user clusters. They maintain either the connected components or sets to represent the current clusters, and update the clusters according to the empirical estimate of bandit parameter in each round. In the clustering process, all the users start in a single cluster, and then gradually partitioned into multiple clusters until each cluster contains one user or a few users with the same bandit parameter (if it exists). Figure 2 shows the varying accuracy of CLUB [16] and SCLUB [23] for identifying user clusters. Although they achieve peak performance at certain rounds, they lack the ability to identify and output the associated user clusters.

arXiv:2103.00063v2 [cs.LG] 18 Jul 2022
To solve the above challenges, in this paper, we aim to cluster users with similar tastes or preferences, formulated by a set of users with close bandit parameters. This problem is crucial and applicable to many applications. First, it can improve the quality of item recommendation (e.g., movie, music, and product). When recommending an item to a user, consider other users' preferences in the cluster to which the user belongs, which has been successfully demonstrated by existing works [15,16,23,24]. Second, identifying clusters can be used for the user recommendation. Connecting two users with similar tastes can help them to discover new items and obtain additional insights in the content curation platforms [32,36], because users can collect existing content and provide insights via comments or reviews. For example, Spotify (or Youtube) allows users to create and share their playlist. A user can follow the recommended users and keep track of their listening activities (songs, albums, and playlist).
To identify user clusters in the contextual MAB framework, we propose a bandit algorithm embedded with a clustering procedure, named LOCB (LOcal Clustering in Bandits). It can be described as two modules. One is the Clustering module to find latent clusters among users. Different from the existing global clustering algorithms [15,16,23,24], the Clustering module starts with a number of seeds and recursively refines neighbors for each seed. To return the clusters at appropriate rounds, we introduce a termination criterion. Once the criterion is met, the clustering stops and returns multiple clusters that allow for sharing users. The other is the Pulling module for the canonical online decision making, which allows the generic integration of user clusters' information. Based on the fact that a user may belong to several clusters, the Pulling module is capable of dealing with overlapping clusters, instead of the hard clustering required by previous works [15,16,23,24]. Therefore, in each round, the Pulling module receives the (overlapping) clusters found by the Clustering module and then utilizes them to select an arm and observe the reward. The key contributions of this paper can be summarized as follows: (1) Problem Definition: We introduce a user clustering problem in the contextual MAB, which needs weaker assumptions and is applicable to many real-world scenarios.
(2) Algorithm: We propose a bandit algorithm, LOCB, embedded with a local clustering procedure. Different from global online clustering, it is more scalable where the computational cost of each round is proportional to the number of given seeds instead of the number of users. Furthermore, we first study the overlapping clusters in the contextual MAB.
(3) Theoretical Analysis: We provide three main theorems. The first is the correctness guarantee with respect to clusters returned by LOCB, in order to solve the clustering problem with high probability. The second is the upper bound of the number of rounds needed for the Clustering module to terminate. This bound is ( log ) to shows the efficiency of the Clustering module, where the number of users. Finally, we provide the regret analysis of LOCB to show a regret bound free of the number of clusters, which enables the learner to adjust the number of seeds with a deterministic bound.
(4) Empirical Performance: We perform extensive experiments on synthetic and real-world datasets from various aspects to evaluate LOCB, including clustering accuracy, regret comparison, and  the effect of parameters. LOCB outperforms the state-of-the-art baselines. The rest of the paper is organized as follows. After briefly introducing the related work in Section 2, we formally present the problem definition in Section 3. The proposed algorithm is introduced in Section 4, and the following theoretical analysis is presented in Section 5. Finally, we show the experimental results on both synthetic and real-world data sets in Section 6. The appendix is placed at the end to include the proofs.

RELATED WORK
The multi-armed bandit first proposed by [34] provides a principled solution for the exploitation-exploration dilemma, which has been adapted to many personalized applications such as advertisement displaying [9,26], recommender system [1,22], search engine system [30,41]. The traditional non-contextual bandit was studied for various problem setting, such as best arm identification [2,4], outlier arm identification [5,15], and Top-K arm problems [8,18]. In contrast, the contextual bandit was first introduced at [3] and then extended by [22], in which the arm is represented by a contextual vector instead of a scalar.
The idea of exploring dependency among users in the contextual MAB has been studied by a series of works [15,16,23,24]. CLUB [16] first considers clustering users based on bandit parameters. It represents the similarity of users by a graph and keeps refining the groups. To dig out more dependencies, the follow-up work [24] clusters both users and items, and leverages the cluster effects together. [15] introduces a context-aware clustering of bandits algorithm that allows each content item to cluster users into groups, where the users from a group have the same reaction to particular items. [13,25] study a variant of clustering in bandit algorithms that allow recommending a list of items to a user. Since the above works all assume the users are drawn from a uniform distribution, [23] presents a framework to deal with users with different frequency. However, as mentioned before, these works do not specify when to return clusters and have no guarantee about the quality of clusters. These limitations will negatively affect the reward estimation, and thus the performance of the overall system. Cluster detection has been studied for decades, and many algorithms were proposed to solve this problem. We refer the reader to several survey papers [29,38]. Existing methods include: local spectral algorithms [27,35], graph-based clustering [20,39], modularity optimization [28], motif-based clustering [14,42,43], and so on. Different from traditional clustering, we cluster users based on the unknown bandit parameters rather than the known links or attributes.

PROBLEM DEFINITION
In this section, we formulate the joint problem of user clustering and contextual MAB, where the learner aims to cluster users with similar bandit parameters. Let = {1, . . . , } be a set of users. At each round = 1, 2, . . . , , the learner receives a user ∈ and observes a set of context vectors X = {x 1, , x 2, , . . . , x , } associated with arms. Then, the learner chooses some x , ∈ X to recommend to the user and obtains the reward . For each x , ∈ X , x , ∈ R , it summarizes the side information of arm at current round . Suppose that the user of each round is drawn uniformly from , and s/he is associated with an unknown bandit parameter ∈ R , reflecting how interacts with the environment. In standard linear contextual bandit problems [16,22,37], the reward is governed by a noisy version of an unknown linear function of x , and : where is a noise with zero-mean and -bounded variance, drawn from a Gaussian distribution N (0, 2 ). The users with similar behaviors are considered to form a cluster. Without any side information of users, we measure their similarity by comparing their associated bandit parameters (unknown). In contrast with using the strict assumption of existing works [15,16,23,24] that the users from a cluster share the same , we allow some deviation in of users from the same cluster. More specifically, the deviation is upper bounded by a threshold predefined by the learner, which is usually a small constant. Formally, we introduce a generic definition, -Cluster.
In this paper, the first objective is to design an efficient algorithm to recover the clusters among users, such that the set of clusters returned by the algorithm are true -clusters with probability 1 − , where is a small constant.
The task of finding -clusters is challenging due to the following reasons.
(1) Whether the return clusters are true -clusters. As the bandit parameter is unknown for each user, the learner needs to use the estimation to cluster after observing rewards in each round. This is a traditional obstacle in the contextual MAB [1,16].
(2) When to return the clusters. Playing too many rounds leads to high costs, but playing only a few rounds introduces serious uncertainties. This is a new exploration-exploitation dilemma in this problem.
(3) Overlapping clusters. It is common that multiple clusters are overlapping, where a user may belong to more than one -clusters. The existing works [15,16,23,24] focus on hard clustering and may fail in the presence of overlapping.
In addition to identifying the user clusters, we also aim to minimize the accumulated regret as the goal in standard bandits. More specifically, after rounds, the accumulated regret for all users is defined as, where is the served user in round , and x is the pulled arm in round in practice.

LOCB: LOCAL CLUSTERING IN BANDITS
In this section, we introduce the proposed algorithm, LOCB, for detecting and exploiting underlying clusters among users in the contextual MAB. It has two cooperative modules: the Clustering and Pulling. In the round − 1, after pulling an arm determined by the Pulling module and observing the reward −1 , the Clustering module updates the membership for each cluster based on −1 . Then, in the round , given the clusters provided by the Clustering module that allows for overlapping, the Pulling module finds the optimal cluster for the serving user and selects an arm, obtaining the reward . Next, we first elaborate on the Clustering module and then the Pulling module.
As the standard contextual bandit [22,37], in each round , LOCB needs to compute the estimationˆ, of for ∈ in round , after pulling an arm x and observing the reward : (1) where I is a × identity matrix and H , represents the historical data of user up to round .

Clustering Module
This module is a seed-based clustering algorithm. It randomly chooses a set of seed users, denoted by = { 1 , . . . , }, ⊆ , and progressively learns the neighbors of each seed user. Supposing in the roundˆ, it terminates and then outputs | | = clusters, denoted by The neighborhood between two users should be determined when it is confident about whether their bandit parameters are close enough. We achieve this goal by using the confidence interval ofˆ, for each user ∈ . If the significance levels of these intervals are carefully set, we can safely terminate the module with a certain criterion while guaranteeing that the cluster returned for each seed is a true -cluster with probability at least 1 − .
The general definition of confidence interval forˆ, is defined as: is an upper confidence bound and , is the number of times that has been served up to . With probability 1 − , to ensure ∀ , ∀ ∈ ,ˆ, is within the confidence interval, the significance level ′ should be set as / (Lemma 5.1). If two users belong to the same -cluster, we call them neighbors. Thus, given a user ∈ and a seed user ∈ , we consider as 's potential neighbor if their confidence intervals are overlapping, which is formally defined as: Cluster module updates and keeps the potential neighbors of each seed in each round, until it is confident that the current potential neighbors are real neighbors. As is predefined by the learner, the number of rounds for exploring clusters varies. Let N , ⊆ denote the set consisting of the seed user and 's potential neighbors. We provide the termination status when the learner is confident that N , is a -cluster and the Clustering module should stop exploring N , . We define the termination status as: return where is a tuning parameter with respect to theoretical criterion in Theorem 5.1. Algorithm 1 Lines 25-34 describe the high-level idea of the Clustering module. Give a set of seeds and to LOCB, where is randomly chosen from and the number of seeds | | will be discussed at end of this section. In the initialization, for each ∈ , we set N , = when = 0 (Lines 3-4), because we consider all the users as the seed user's potential neighbors before we receive any information about them. In each round , after pulling an arm determined by Pulling module and observing the reward,ˆ, of the served user is computed (Line 26). Then, we compareˆ, withˆ, for each ∈ to determine whether is 's potential neighbor (Lines 28-29). If not, we remove from N , (Line 30). Therefore, the potential neighbors of each seed is updated in each round. Cluster module will stop exploring if N , meets the stop criterion (Eq.(3)) and we remove from (Lines 33-34). When is an empty set, the Clustering module terminates and outputs the set of clusters {N , : ∈ } (Lines 20-23). .

Pulling Module
In the last sub-section, we present how the Clustering module finds the cluster for each seed. Given a set of seeds , Clustering module holds a set of clusters in each round , denoted by N , = {N , : ∈ }. In this section, we will present how the Pulling module utilizes N , in the decision making of the contextual MAB.
First, as the standard UCB-based (upper confidence bound) bandit [1,15,16,22], given an arm x , , we need to define a confidence interval for the estimated rewardˆ⊺ , x , of ⊺ x , for each ∈ .
The confidence interval is defined as:  for each ∈ ( ) do 14: pull x and observe reward 15: for each ∈ ∧ ≠ do 18: if | | > 0 then 21: Clustering( , ) ← − { } # N , is ready to return and remove from Consider a current cluster N , (represented by N , −1 in Algorithm 1). We define a bandit parameter N , for N , to represent the integration of the included users' bandit parameters, formally: As N , is also unknown, we compute its estimation as: Based on Lemma 8.3 in Appendix, we have the confidence interval forˆ⊺ N , x , , formally defined as: , . Similar to the existing works [15,16,23,24], given a served user and one of 's clusters N , , we determine the arm byˆN , rather thanˆ, , using the following criteria: However, a user may belong to more than one clusters. In particular, when | | is large, it is highly likely that a user belongs to multiple clusters returned by the Clustering module. To find the optimal cluster from these candidate clusters, we propose the following criterion to find the cluster with maximal potential. Let ( ) represent the clusters that belongs to in round , ( ) = { : ∈ ∧ ∈ N , }. Then, the Pulling module selects an arm by: Note that if the user does not belong to any cluster in round , i.e., ( ) = ∅, then the selection criterion follows the standard UCBbased bandit [22], determined by arg max x , ∈X (ˆ⊺ , x , + , ). This is not shown in Algorithm 1 because of limited space.
Algorithm 1 Lines (1-19) describe the workflow of the Pulling module. Lines 1-4 show the initialization for each user and each seed user. In each round, after observing the served user and context vectors X , it first finds the clusters belongs to among the clusters kept by the Clustering module, represented by ( ) (Lines 5-10). Then, we decide the arm to pull by the criterion Eq.(6) (Lines 11-13). With the observed reward , we update the parameters for each user (Lines [15][16][17][18][19]. At the end of each round, the Clustering module starts to update the clusters for each seed (Lines 20-23). Selection of Seeds. Similar to traditional seed-based clustering algorithms [14,19,40], the number of seeds affects the performance of LOCB. In general, the more seeds the algorithm is given, the higher chance it has to find good clusters. Therefore, it is encouraged for the learner to have a relatively large number of seeds. In many cases, we can simply set = to achieve the best performance the Clustering module may reach. In this case, each user will be treated as a center, and the Module module explores each user's potential neighbors in each round. For the isolated user, one will hold a cluster that only includes him/herself. For those users who are close to each other, they will hold a -cluster respectively in the end, while these clusters are very likely to be overlapping. Therefore, the Pulling module is designed to deal with overlapping clusters. It can find the optimal cluster among candidate clusters for a user. Therefore, the cooperation of the Pulling module with the Clustering module can effectively alleviates the challenge of finding good seeds.

THEORETICAL ANALYSIS
In this section, first, we introduce the two theorems to show LOCB's effectiveness and efficiency for solving -cluster detection problem. Then, we provide the detailed regret analysis of LOCB.
We first provide the theoretical analysis with respect to the detected clusters by LOCB as follows.
Theorem 5.1 (Correctness). Given a threshold and a set of seeds ⊆ , for each ∈ , let N represent the cluster output by LOCB with respect to . The terminate criterion of Clustering module is defined as: Then, with probability at least 1 − , after the Clustering module terminates, for each ∈ , it has ∀ , ∈ N , ∥ − ∥ < .
The details of the proof are provided in Appendix. Before proving Theorem 5.1, we need to set the confidence interval properly for each user in each round, in order to make sure that the estimations are within the confidence interval during the clustering procedure, as shown in Lemma 5.1.
Lemma 5.1. At round = 1, 2, . . . , , suppose that for any user ∈ , we have an upper confidence bound , ( , , ′ ) that satisfies: where ′ is a varying confidence level with respect to and . Define the random event . , ] be the sequence of served users in each round up to . If ′ is defined as then, the probability of E happening is higher than 1 − , Second, we introduce an upper bound on the number of rounds needed for the Clustering module to terminate. First, we need to define , ( , , ′ ), following the upper confidence bound in [16].
Lemma 5.2. [16] For each round , let the context vectors X = {x 1 , · · · , x } be generated i.i.d (conditioned on , and past data { ′ , X ′ , ′ } ′ =1 ) from a random vector X such that |X|| = 1 and E[XX ⊺ ] is full rank with minimal eigenvalue > 0. Then, given a user ∈ , with probability 1 − , for any ∈ [ ], it has With this UCB, we have the following theorem. where = 2 16 3 2 . The above theorem provides the upper bound of the cost for LOCB to output -clusters. Denote this upper bound by¯. In practice, usually is a large number, then¯becomes ( log ). If is also a large number,¯becomes ( log ).
Finally, we provide the regret bound for LOCB.
Theorem 5.3. Suppose that each user is evenly served. Given and a set of seeds , after >ˆrounds, the accumulated regret of LOCB can be upper bounded as follows: This upper bound is composed of two terms. The first term is the usual √ -style term in linear bandit regret analysis [1,3,10]. Note that this bound does not depend on the number of seed | |, as the clusters are allowed to be overlapping. This indicates that even though LOCB is given with plenty of seeds (e.g., = ), the regret bound will not decay . The second term is the accumulated regret caused by the deviation between the cluster center and served user. This bound happens when ∥ N , − ∥ = , ∀ ∈ . However, this is too pessimistic. In practice, there usually exist some -clusters for a user where N , ≈ . If ∀ , ∀ ∈ , ∥ N , − ∥ → 0, the second term will decrease close to zero.
The key difference of the bound in Theorem 5.3 from the regret analysis of existing works [15,16,23,24] is the assumption of clusters. The regret bounds of previous works rely on the number of non-overlapping clusters denoted by in which each user shares the same bandit parameter. This assumption corresponds to linear bandits if is known. However, Unlike this strong assumption, we allow the clusters to overlap, and thus our bound still depends on the number of users.

EXPERIMENTS
To evaluate LOCB from various aspects, we divide experiments into three parts to evaluate its clustering accuracy, accumulated regret, and the effect of input parameters. We compare LOCB with standard bandit algorithms as well as online clustering of bandit algorithms on one synthetic and three real-world datasets. First, we briefly introduce the four datasets used in experiments.
(1) Synthetic. We synthesize a dataset with 100 users and 5 clusters, where the size of each cluster is randomly chosen from [5 : 40]. Each user has a separate parameter and the users within a cluster N satisfy ∀ , ∈ N, ∥ − ∥ < 0.2. Both and context vector x , have = 5 dimensions drawn from a standard Gaussian distribution. Then, they are appended with one more dimension with constant 1, and transformed by ← √ to guarantee that ⟨ , x , ⟩ lies in [0, 1].
(2) Yelp 1 is a dataset released in Yelp dataset challenge. It contains 4.7 million rating records from 1.18 million users to 1.57 ×10 5 restaurants. Each restaurant is represented by a feature embedding vector x , ∈ R 10 with respect to its attributes and categories. We generate the reward by using the restaurant's gained stars scored by the users. In each review record, if the user scores the restaurant more than 3 stars (5 stars totally), the reward = 1; Otherwise, the = 0. We set the user pool | | = 100 by selecting the top 100 users with the most reviews. And we set the arm pool |X | = 10 as follows: given a user , we pick one restaurant with non-zero reward according to the whole records in the dataset, and then randomly pick the other 9 restaurants with zero rewards.
(3) MovieLens [17] is a dataset consisting of 25 million ratings of 6 × 10 4 movies from 1.6 × 10 5 users. Each movie is represented by an embedding vector x , ∈ R 10 with regard to the genres and historical records. Similarly, a rating event is represented by {x , , , }, where the reward is 1 if the movie x , obtains more than 3 stars from the user (Otherwise = 0). We set user pool | | = 100 and the arm pool |X | = 10.
(4) Yahoo [22] is a recommendation dataset containing 45 million user visits to 'Yahho! Today Module' across ten days. Each visit includes one user and ten candidate articles in which both user and article are represented by a six-dimension feature vector. Here, we choose the contextual vector x , of the first article in each visit as the arm. If the user clicks the this article, the reward is 1; Otherwise, is 0. However, this dataset does not provide user identities. Therefore, following the previous works [15,24], we use the -means to cluster user vectors where each cluster is thought of as a user. In the beginning, we set = 500 to determine user identities and select the top 100 users with the most visit records to be the user pool | | = 100. Then, we set the arm pool |X | = 10 following the above selection strategy.
Across the all experiments, we set = 0.1, run each experiments 5 times, and report the average results.

Accuracy of Clustering
In this sub-section, we evaluate the accuracy of LOCB for the user clustering. Since the problem setting is new, there are no existing methods focusing on -cluster detection in the contextual MAB. Therefore, we design four baselines for comparison.
(1) Naive CLUB (N-CLUB). CLUB [16] regards connected components as user groups and refines groups gradually. However, it cannot determine when the group is good enough. Therefore, we terminate it when the found groups have not changed in the last consecutive 10/ rounds. This baseline reflects how well CLUB can solve the problem with a heuristic termination condition. (2) Same Termination CLUB (ST-CLUB). We terminate CLUB when LOCB stops, i.e., ST-CLUB and LOCB have exactly  Similarly, we terminate SCLUB [23] when LOCB stops. This baseline reflects the accuracy of LOCB compared to SCLUB with the same termination condition. (4) Naive LOCB (N-LOCB). We terminate LOCB when the size of detected group has not changed in the last consecutive 10/ rounds. This baseline reflects how well the problem can be solved by the proposed method with a heuristic termination condition.
Obtain ground-truth clusters. As the three real-world datasets do not provide the bandit parameter vector for each user, we need to calculate the expectation of the bandit parameter according to each dataset. Assume in a dataset, a user totally has records represented by {x , , }| =1 . Then, we compute the expectation for by using the standard estimation in contextual MAB, as follows: x .
Here, we calculate all the available records for each user of each dataset. With these known bandit parameters, we apply -means again to finding clusters, where we set = 5. Then for each cluster, we find a set of users satisfying the -cluster criterion with the maximal size as a group-truth cluster. Evaluation Setting. Each algorithm returns multiple sets of users in the end. For each ground-truth cluster, we pick a set with the highest F1 score. Then, we average the F1 scores of all picked sets and consider it as the accuracy of an algorithm. This measurement reflects how well a cluster can be recovered, which has been widely used in clustering [21,40]. For CLUB and SCLUB, the UCB parameter is set as {0.8, 1.0, 1.2}. For LOCB, the UCB of is set as √ , which is the similar form with Lemma 5.2 but with the faster convergence rate. We set = 0.2, = {8, 10, 12} and | | = | | = 100. Next, we report the average accuracy of each methods. Table 1 and Table 2 show LOCB's accuracy of cluster detection in comparison with four baselines. In general, LOCB significantly outperforms all the others. It starts with the seed users and explores their associated neighbors. With the proposed clustering strategy  and termination criterion, LOCB achieves the ideal precision and recall. With the heuristic termination criterion, the clusters detected by N-CLUB are usually extremely large or small, containing a large number of false-positives or false-negatives. Even with the same number of rounds as LOCB, ST-CLUB still cannot reach the desired accuracy because it uses the connected components of a graph to represent clusters, which is influenced significantly by the edges created among user pairs. ST-SCLUB uses the top-down hierarchical clustering while it splits the users into small clusters very quickly . Its performance is better than ST-CLUB while still much worse than LOCB. When N-LOCB terminates in a heuristic way, it either is still exploring the cluster structure or has over-explored, but it still achieves better performance than N-CLUB.

Regret Comparison.
In this sub-section, we evaluate the cumulative regret of LOCB compared to strong baselines. Following [16,23], the UCB of is set as for all algorithms to accelerate the convergence rate. For LOCB, we set = 0.2 and seeds | | = 30 to consider the running time cost. We choose four baselines: (1) linear bandit algorithms: LinUCB-ONE [22], where all the users share one bandit parameters. LinUCB-IND [22], where each user has a separate bandit parameter. (2) clustering of bandit algorithms: CLUB [16] and SCLUB [23]. Figure 3 and Figure 4 show the cumulative regret of all methods on four datasets. As we can see, LOCB achieves the best performance compared to all baselines. With enough seeds, the Clustering module is able to recover each cluster effectively. Although the provided clusters are overlapping, the pulling module can find the best cluster for the observed user in each round. The performance of LOCB demonstrates that utilizing accurate user dependency can boost the performance of a bandit algorithm.
For other baselines, in the beginning, the users' feedback is not enough to make an accurate estimate of , and thus LinUCB-IND (IND) accumulates more regret than LinUCB-ONE (ONE). However,  As CLUB considers all the users as a cluster in the early phase, its performance is similar to ONE. As it learns the clusters progressively, its performance becomes better than ONE. However, the clusters CLUB finds are not accurate, resulting in much worse performance than LOCB. SCLUB uses the set to represent each cluster and merges or splits them accordingly. However, SCLUB only starts clustering from one cluster center, making it incompetent to recover multiple clusters. Since it has higher accuracy than CLUB for finding good clusters, it performs better than CLUB but is still worse than LOCB.

Effects of Parameters
In this sub-section, we evaluate the effect of the two input parameters for LOCB, and . Table 3 describes the variation of the accuracy of LOCB for cluster detection, as the number of seeds varies from [5,100]. We use two datasets, Yelp and MovieLens, as representatives. When the number of seeds is smaller, the performance of LOCB boosts as it increases. Because with more seeds, the more chance LOCB has to find good seeds. For example, when | | = 5, it only can recover 2 out of 5 clusters; when | | = 20, it almost recovers the total five clusters. A good seed for LOCB usually is the center of a ground-truth cluster. Figure 5 reports the variation of regret of LOCB, as the number of seed increases. In accordance with the variation of accuracy of clustering, the performance of LOCB improves with the increasing of the number of seeds. Because the more seeds the Clustering module uses, the more accurate groups it finds. Given the candidate groups, the pulling module can find the optimal group for each user, and thus further decrease the regret. Similarly, when | | becomes large, the improvement becomes small. Empirically, for 100 users, with more than 20 seeds, LOCB can achieve the ideal performance. Table 4 shows the change of clustering accuracy for LOCB with the varying . When is a larger number (e.g., = 0.4), the Clustering module will terminate earlier while with a low precision because each user lacks historical rewards and the confidence interval still is very large. In contrast, when is a smaller number (e.g., = 0.1), the Clustering module will terminate much later to find = 0.1-clusters, where the returned clusters have higher precision but lower recall. Therefore, the variance in accuracy of the gamma parameter becomes unimodal. The regret's change for LOCB with the varying of also shows the unimodal shape, complying with change of clustering accuracy. Due to the limited space, we will not show the regret change.

CONCLUSION
In this paper, we study the problem of detecting user clusters in contextual MAB. We propose LOCB, which utilizes a local procedure to cluster users and then leverages the best suitable cluster to improve the quality of recommendation for the serving user. In the theoretical analysis, we provide three theorems: (1) the returned set of users is a true cluster with probability at least 1 − ; (2) the termination of the Cluster module is bounded by ( log ); (3) the regret upper bound of LOCB is free of the number of seeds. In the experiments, LOCB shows the promising empirical performance compared to strong baselines.

APPENDIX
The proof of Lemma 5.1 is as follows.