Online Clustering of Bandits with Misspecified User Models
Authors: Zhiyong Wang
Jize Xie
Xutong Liu
Shuai Li
John C.S. Lui
Venue: NeurIPS 2023 poster (2023)
Keywords: online clustering of bandits

Abstract: The contextual linear bandit is an important online learning problem where given arm features, a learning agent selects an arm at each round to maximize the cumulative rewards in the long run. A line of works, called the clustering of bandits (CB), utilize the collaborative effect over user preferences and have shown significant improvements over classic linear bandit algorithms. However, existing CB algorithms require well-specified linear user models and can fail when this critical assumption does not hold. Whether robust CB algorithms can be designed for more practical scenarios with misspecified user models remains an open problem. In this paper, we are the first to present the important problem of clustering of bandits with misspecified user models (CBMUM), where the expected rewards in user models can be perturbed away from perfect linear models. We devise two robust CB algorithms, RCLUMB and RSCLUMB (representing the learned clustering structure with dynamic graph and sets, respectively), that can accommodate the inaccurate user preference estimations and erroneous clustering caused by model misspecifications. We prove regret upper bounds of $O(\epsilon_*T\sqrt{md\log T}  + d\sqrt{mT}\log T)$ for our algorithms under milder assumptions than previous CB works, which match the lower bound asymptotically in $T$ up to logarithmic factors, and also match the state-of-the-art results in several degenerate cases. Our regret analysis is novel and different from the typical proof flow of previous CB works. The techniques in proving the regret caused by misclustering users are quite general and may be of independent interest. Experiments on both synthetic and real-world data show our outperformance over previous algorithms.

Online Clustering of Bandits with Misspecified User Models
Zhiyong Wang The Chinese University of Hong Kong zywang21@cse cuhk, edu.hk
Jize Xie Shanghai Jiao Tong University xjzzj1esj edu. en
Xutong Liu The Chinese University of Hong Kong liuxt@cse. cuhk. edu. hk
Shuai Li"
Shanghai Jiao Tong University shuaili80sj tu. edu. cn
John C.S. Lui
The Chinese University of Hong Kong cslui@cse. cuhk, edu.hk
Abstract
The contextual lincar bandit is important online learning problem where given arm features, a learning agent selects an arm at each round to maximize the cu- mulative rewards in the long run. A line of works, called the clustering of bandits (CB), utilize the collaborative effect over user preferences and have shown signifi- cant improvements algorithms require well-specified linear user models and can fail when this critical assumption does not hold. Whether robust CB algorithms practical scenarios with misspecified user models remains an open problem. In this paper, the first present the important problem of clustering of bandits with misspecified user models (CBMUM), where the expected rewards in user models can be perturbed away from perfect linear models. We devise robust CB algo- rithms, RCLUMB and RSCLUMB (representing the learned clustering structure with dynamic graph and sets, respectively), that can accommodate the inaccurate user preference estimations and erroneous clustering caused by model misspec- ifications. We prove regret upper bounds of O mmd T + dymI log T) for our algorithms under milder assumptions than previous we move past restrictive technical assumption on the distribution of the arms), which match the lower bound asymptotically in 7 up logarithmic factors, and also match the state-of-the-art results in several degenerate cases. The techniques in proving the regret caused by misclustering users are quite general and may be independent interest. Experiments on both synthetic and real-world data show our outperformance over previous algorithms.
classic linear bandit algorithms. However, existing CB
be designed for
works (notably,
Introduction
Stochastic multi-armed bandit (MAB) 2 22 where the learning agent selects an action and receives corresponding reward at each round, so as to maximize the cumulative reward in the long run. MAB algorithms have been widely applied in
an online sequential decision- problem,
*Corresoondigg author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

recommendation systems and computer networks to handle the exploration and exploitation trade-off
20
30
38 51.
To deal with large-scale applications, the contextual linear bandits 24
21 have been studied,
where the expected reward of each arm is assumed to be perfectly linear in their features. Leveraging the contextual side information about the user and arms, linear bandits can provide more personalized recommendations [[6]. Classical linear bandit approaches, however, ignore the often useful tool of collaborative filtering. To utilize the relationships among users, the problem of clustering of bandits (CB) has been proposed [12]. Specifically, CB algorithms adaptively partition users into clusters and utilize the collaborative effect of users to enhance learning performance.
Although existing CB algorithms have shown great success in improving recommendation qualities, there exist two major limitations. First, all previous works on CB [12 each user, the expected rewards follow perfectly linear model with respect the user preference vector and arms' feature vectors. In many real-world scenarios, due to feature noises or uncertainty [15], the reward may not necessarily conform perfectly linear function, or even deviates lot from linearity [14]. Second, previous CB works assume that for users within the same cluster, their preferences are exactly the same. Due to the heterogeneity users' personalities and interests, similar users may not have identical preferences, invalidating this strong assumption.
25
27 39 assume that for
To address these issues, we propose novel problem of clustering of bandits with misspecified user models (CBMUM). In CBMUM, the expected reward model of cach user does not follow a perfectly linear function but with possible additive deviations. We assume users in the same underlying cluster share a common preference vector, meaning they have the same linear part in reward models, but the deviation parts are allowed to be different, better reflecting the varieties of user personalities.
The relaxation of perfect linearity and the reward homogeneity within the same cluster bring many challenges to the CBMUM problem. In CBMUM, we not only need to handle the uncertainty from the unknown user preference vectors, but also have to tackle the additional uncertainty from model misspecifications. Due to such uncertainties, it becomes highly challenging to design a robust algorithm that can cluster the users appropriately and utilize the clustered information judiciously. On the one hand, the algorithm needs to be more tolerant in the face of misspecifications so that more similar users can be clustered together to utilize the collaborative effect. On the other hand, it has to be more selective to rule out the possibility of misclustering users with large preference gaps.
1.1 Our Contributions
This paper makes the following four contributions.
New Model Formulation. We are the first to formulate the clustering of bandits with misspecified user models (CBMUM) problem, which is more practical by removing the perfect linearity assumption in previous CB works.
Novel Algorithm Designs. We design two novel algorithms, RCLUMB and RSCLUMB, which robustly learn the clustering structure and utilize this collaborative information for faster user prefer- ence elicitation. Specifically, RCLUMB keeps updating a dynamic graph over all users, where users connected directly by edges are supposed to be in the same cluster. RCLUMB adaptively removes edges and recommends items based on historical interactions. RSCLUMB represents the clustering structure with sets, which are dynamicly merged and split during the learning process. Due to the page limit, we only illustrate the RCLUMB algorithm in the main paper. We leave the exposition, illustration, and regret analysis of the RSCLUMB algorithm in Appendix K
To overcome the challenges brought by model misspecifications, we do the following key steps in the RCLUMB algorithm.
(i) To ensure that with high probability, similar users will not be partitioned apart, we design a more tolerant edge deletion rule by taking model misspecifications into consideration. (ii) Due to inaccurate user preference estimations caused by model misspecifications, trivially following previous CB works [12 25 28
directly use connected components in the maintained graph as clusters would miscluster users with big preference gaps, causing a large regret. To be discriminative in cluster assignments, we filter users directly linked with the current user in the graph to form the cluster used in this round. With these careful designs of (i) and (ii), we can guarantee that with high probability, information of all similar users can be leveraged, and only users with close enough preferences might be misclustered, which will only mildly impair the
2

---

learning accuracy. Additionally: (iii) we design an enlarged confidence radius to incorporate both the exploration bonus and the additional uncertainty from misspecifications when recommending arms. The design of RSCLUMB follows similar ideas, which we leave in the Appendix dju to page limit.
Theoretical Analysis with Milder Assumptions. We prove regret upper bounds for our algorithms of D(e.Tymmdoog + dymmT wlllmmToo22 in CBMUM under much milder and practical assumptions (in arm generation distribution) than previous CB works, which match the state-of-the-art results in degenerate cases. Our proof is quite different from the typical proof flow of previous CB works (details in Appendix C. One key challenge is to bound the regret caused by misclustering users with close but not the same preference vectors and use the inaccurate cluster-based information to recommend arms. To handle the challenge, we prove a key lemma (Lemma (.7) to bound this part of regret. We defer its details in Section 5 and Appendix G The techniques and results for bounding this part are quite general and may be of independent interest. We also give a regret lower bound of Mc..T / d) for CBMUM, showing that our upper bounds are asymptotically tight with respect to T up to logarithmic factors. We leave proving a tighter lower bound for CBMUM as an open problem.
Good Experimental Performance. Extensive experiments on both synthetic and real-world data show the advantages of our proposed algorithms over the existing algorithms.
2 Related Work
Our work is closely related to two lines of research: online clustering of bandits (CB) and misspecified linear bandits (MLB). More discussions on related works can be found in Appendix A
The paper 12 first formulates the CB problem and proposes graph- based algorithm. The work 226 further considers leveraging the collaborative effects on items to guide the clustering of users. The work (25 considers the CB problem in the cascading bandits setting with random prefix feedback. The paper 227 also considers users with different arrival frequencies. A recent work (2X proposes the setting of clustering of federated bandits, considering both privacy protection and communication requirements. However, all these works assume that the reward model for each user follows a perfectly linear model, which is unrealistic in many real-world applications. To the best of our knowledge, this paper is the first work to consider user model misspecifications in the CB problem.
The work 14 first proposes the misspecified linear bandits (MLB) problem, shows the vulnerability of linear bandit algorithms under deviations, and designs an algorithm RLB that is only robust to non-sparse deviations. The work (23] proposes two algorithms to handle general deviations, which are modifications of the phased elimination algorithm [22 and LinUCB [. Some recent works [ use model selection methods to deal with unknown exact maximum model misspecification level. Note that the work [1] has an additional assumption on the access to an online regression oracle, and the paper [31 still needs to know an upper bound of the unknown exact maximum model deviation level. None of them consider the CB setting with multiple users, thus differing from ours.
We are the first to initialize the study of the important CBMUM problem, and propose a general framework for dealing with model misspecifications in CB problems. Our study is based on funda- mental models on CB 27 and MLB 23 the algorithm design ideas and theoretical analysis are pretty general. We leave incorporating the model selection methods [I into our framework to address the unknown exact maximum model misspecification level an interesting future work.
3 Problem Setup
This section formulates the problem of "clustering of bandits with misspecified user models" (CB- MUM). We use boldface lowercase and boldface CAPITALIZED letters for vectors and matrices. We use |A] to denote the number of elements in A, [m] to denote (1..... m) and || M = vx Mæ to denote the matrix norm of vector æ regarding the positive semi-definite (PSD) matrix M.
In CBMUM, there are u users denoted by U = {1, 2,,,,..,,uu .... unknown preference vector 0; E Rdd with |00.1l < 1. We assume there is an unknown underlying clustering structure over users representing the similarity of their behaviors. Specifically, U/ can be partitioned into a small number m (i.e., m < u) clusters, V1, V.,... V.., where U/a(m] V/ U, and
Each user i E U is associated with an
V,, n Vy+ = 0, for j + j'. We call these clusters ground- clusters and use V = (Vi, 1/2, .., Vm to denote the set of these clusters. Users in the same ground truth cluster share the same preference vector, while users from different ground -ruth clusters have different preference vectors. Let 0²
3

---

denote the common preference vector for Vú and j(i) E [ml] denote the index of the ground-truth cluster that user belongs to. For any é E U, if E Vj(j, then 0; go
At each round t E [T], user i, E 2 comes to be served. The learning agent receives a finite arm set A, S A to choose from (with |Ac| f C, vt), where each arm a E A is associated with feature vector I. RR, and || < 1. The agent assigns T
appropriate cluster V, for user is and recommends an item ar é Ag based on the aggregated historical information gathered from cluster V.. After receiving the recommended item dt, user is gives a random reward rt E [0, 1] the agent To better model real-world scenarios, we assume that the reward r, follows a misspecified linear function of the item feature vector Ta, and the unknown user preference vector i... Formally,
(1) [ E RIAd denotes the unknown deviation in the expected rewards of arms in A, from linearity for user in at t, and f/. is the 1 I-sub-Gaussian noise. We allow the deviation vectors for users in the same ground-Iruth cluster to be different.
Ts = Wa. 0i, + Eot n/
where gh = (eq". 62
We assume the clusters, users, items, and model misspecifications satisfy the following assumptions. Assumption 3.1 (Gap between different clusters). The gap between any two preference vectors for different ground-truth clusters is least unknown positive constant
| 0² 27 2.>0,,j.J E [m] #
Assumption 3.2 (Uniform arrival of users). At each round t, user is comes uniformly at random from 24 with probability 1/u, independent of the past rounds.
Assumption 3.3 (Item regularity). At each time step f. the feature vector æ, of each arm a A is drawn independently from a fixed but unknown distribution over {æ E Id ||æ||2 S 11, where Eæ=p[æ== | is full rank with minimal eigenvalue Ae- > O. Additionally, at any time i, for any fixed unit vector 0 E gd (0 )²² has sub-Gaussian tail with variance upper bounded by o².
Assumption 3.4 (Bounded misspecificatiion level). We assume that there is a pre-specified maximum misspecification level parameter c, such that || S G., Vi E u t E [T].
Remark 1. All these assumptions basically follow previous works on CB 12 25
28 and MLB
23.. Note that Assumption 3.33 is less stringent and more practical than previous CB works which also the variance upper bound o². For Assumption 3.2) our results easily generalize to the case where the user arrival follows any distributions with minimum arrival probability greater than Pmii- For Assumption 3.4 note that e, can be an upper bound on the maximum misspecification level, not the exact maximum itself. In real-world applications. the deviations are usually small [14), and can set relatively big e, as an upper bound. For more discussions please refer to Appendix B
put restrictions
Let af E arg max x Or, + ei denote an optimal arm which gives the highest expected reward The goal of the agent is to minimize the expected cumulative regret
R(T) E (x
( P., + Ex xT, 0., -4:
4 Algorithm
This section introduces our algorithm called "Robust CLUstering of Misspecified Bandits" (RCLUMB) (A. RCLUMB is a graph-based algorithm. The ideas and techniques of RCLUMB can be easily generalized to set-based algorithms. To illustrate this generalizability. we also design a set-based algorithm RSCLUMB. We leave the exposition and analysis of RSCLUMB in Appendix K
For ease of interpretation, we define the coefficient
2 A
2 26
where X A 10x0(1 preference vectors that algorithm can distinguish with high probability, as supported by (5) in the proof of Lemma H.T in Appendix H Note that the algorithm does not require knowledge of We also make the following definition for illustration.
2 20
dr. ( theoretically the minimum gap between two users'

---

Algorithm Robust Clustering of Misspecified Bandits Algorithm (RCLUMB)
1: Input: Deletion parameter a1, 02 > 0, f(T)
+++(1++)
X, B, f. 0.
1+7
2: Initialization: ;0 Oaxds 6,, = 0ax1. Tio 0, Vi U; complete Graph Go = (L,, Eo)
over 24.
for all L 1, ..
4: Receive the index of the current user in E it, and the current feasible arm set Ar;
5: Filter user 4 and users E Ul that are directly connected with user in via edge (i. it) E B
to form the cluster Vi;
6: Compute the estimated statistics for cluster V.
M V AI Eiev, M 1, 1.e-1.by,,. . Eiev, bir-1 V Mv
7: Recommend an arm de with the largest UCB index (Eq. ), and receive the reward ra [0. 1];
8: Update the statistics for user i, M = M + Ca. Ta bist b Tei Tu.t
Th,--1 1, . . (A + M Ma.e))
Keep the statistics of other users unchanged
Me. M be, bL.-1,T2e 1e,1-1.0.1 1.. for all Euu,
10: Delete the edge (1.,)) E E1-1.
| -0000ll 2 as
+ azen:
and get an updated graph G, (21 E,):
Definition 4.1 (C-close users and Ç-good clusters). Two users i, E U are Ç-close if |00 02112 S S. Cluster V is Ç-good cluster at time f, v E V, user i and the coming user i, are (-close.
We also say that two ground-truth clusters are "ç-close" if their preference vectors' gap is less than Ç.
Now we introduce the process and intuitions of RCLUMB (Algo The algorithm maintains an undirected user graph G, = (2, E,). where users are connected with edges if they are inferred to be in the same cluster. We denote the connected component in G containing user in at round / as V.
Cluster Detection. Go initialized to be complete graph, and will be updated adaptively based on the interactive information. At round t, user i, E 24 comes to be served with a feasible arm A, (Line 4 Due to model misspecifications, same preference vector 0, but similar users whose preference vectors are within the distance of Ç. According to the proof of Lemma H.I. after sufficient time, with high probability. any pair of users directly connected by an edge in 1 are Ç-close. However, if we trivially follow previous CB works to directly use the connected component VÚ as the inferred cluster for user i, at round t, it will cause large regret. The reason is that in the worst case, the preference vector 0 of the user in V/2 who is h-hop away from user i, could deviate by hç from o:.. where can be as large as VzJ- Based on this reasoning, our key point is to select the cluster V. as the users at most I h-hop away from i, in the graph. In other words, after some interactions, V. forms (-good cluster with high probability: thus, RCLUMB can avoid using misleading information from dissimilar users for recommendations.
impossible cluster users with exactly the
112
25
28
Cluster-based Recommendation. After finding the appropriate cluster V, for i, the agent estimates the common user preference vector based on the historical information associated with cluster V, by
0 arg min Σ - (r. x.1, 0)0 + 11
(4)
OER
GeV,
where À > 0 is regularization coefficient. Its closed- form solution is 0 M MT... by b Do,
where M Mv Al E -ste-1]
by,
E
-)tt-1) Pa, Ta.
..eV.
ee
Based on this estimation, in Line 7 the agent recommends an arm using the UCB strategy
de argmax,eA4 min(1, 00 0
| My)..1
+ e, E elt-
D. M
V. Do }.
VeV.
(5)
Ba.
Co.
5

---

where V 22gg(()) + d + Σ2) Ra. denotes the estimated reward of arm a at t, Ca.t denotes the confidence radius of arm a at round
Due to deviations from linearity, the estimation Ra, computed by linear function is no longer accurate. To handle the estimation uncertainty of model misspecifications. we design an enlarged confidence radius Ca.t- The first term of Ca.: in (5) captures the uncertainty of online learning for the linear part, and the second term related to e, reflects the additional uncertainty from deviations from linearity. The design of Ca,t theoretically relies on Lemma 5.6 which will be given in Section 5
Update User Statistics. Based the feedback rt, in Line 8 and 9 the agent updates the statistics for user 4. Specifically, the agent estimates the preference vector 0, by
ii.,t arg min Σ sclt (r' - 2,, 0) + A 1
OER
with solution 0z, = (AT M. b,,,, where My,, = E aCl] Tee Tne b... by 1i
E vC(()
Ta,
Dn.
Update the Graph Gt- Finally, in Line 10 the agent verifies whether the similarities between user it and other users are still true based on the updated estimation 0s,,- For every user E U connected with user it via edge () E Et-1. if the gap between her estimated preference vector og, and ir. is larger than a threshold supported by Lemma H.1 the agent will delete the edge (i,, e) to split them apart. The threshold in Line 10 is carefully designed, taking both estimation uncertainty in linear model and deviations from linearity into consideration. As shown in the proof of Lemma H.T (in Appendix H). using this threshold, with high probability, edges between users in the same ground-truth clusters will not be deleted, and edges between users that are not Ç-close will always be deleted. Together with the filtering step in Line with high probability, the algorithm will leverage all the collaborative information of similar users and avoid misusing the information of dissimilar users. The updated graph G. will be used in the next round.
Theoretical Analysis
In this section, we theoretically analyze the performance of the RCLUMB algorithm by giving an upper bound of the expected regret defined Eq. (2) Due to the space limitation, we only show the main result (Theorem 5.3), key lemmas, and a sketched proof for Theorem 5.3) Detailed proofs, other technical lemmas, and the regret analysis of the RSLUMB algorithm can be found in the Appendix.
To state our main result, we first give two definitions as follows. The first definition is about the minimum separable gap constant )/1 of CBMUM problem instance.
Definition 5.1 (Minimum separable gap 71). The minimum separable gap constant " of a CBMUM problem instance is the minimum gap over the gaps among users that are greater than Ç (Eq.
n1 = min (110: - 0ell2 : |10. 0zl12 > C, Vi, E EU), with min 0 = oc.
Remark 2. In CBMUM, the role of 71 - < is similar to that of y (given in Assumption 3.1 in the previous CB problem with perfectly linear models, quantifying the hardness of performing clustering on the problem instance. Intuitively, users are casier to cluster if ? is larger, and the deduction of ( shows the additional difficulty due to model diviations. If there are no misspecifications, i.c..
< =2 / 2
O, then 7 7, recovering the minimum separable gap between clusters in the
classic CB problem 12
25
without model misspecifications.
The second definition is about the number of
users" ū.
Definition 5.2 (Number of "hard-to-cluste users" ū). The number of thard-to-cluster users" ä the number of users in the ground-truie clusters which are Ç-close to some other ground-truth clusters
Σ
<V e [m]. $ I|o - -0') +c
jE(m)
where 11-} denotes the indicator function of the argument, [Vy] denotes the number of users in Vj-
Remark 3. â captures the number of users who belong to different ground-trath clusters but their gaps are less than Ç. These users may be merged into one cluster by mistake and cause certain regret.
The following theorem gives upper bound on the expected regret achieved by RCLUMB.

---

Theorem 5.3 (Main result on regret bound). Suppose that the assumptions in Section Then the expected regret of the RCLUMB algorithm for T rounds satisfies
3
are satisfied.
R(T) S R(T)s O("
(1.(i (o - c)2
d
ū Ve.
log T
+ eeT / log T dv dvmmTll mm
Ve.Tvmal
(7)
x
XIo
/ S O(E.T md log T dvmm log'),
(8)
where ?/1 is defined in Definition 5.7 and û is defined in Definition 5.2
Discussion and Comparison. The bound in Eq. has four terms. The first term is the time needed to gather enough information to assign appropriate clusters for users. The second term is the regret caused by misclustering Ç-close but not precisely similar users together, which is unavoidable with model misspecifications. The third term is from the preference estimation errors caused by model deviations. The last term is the usual term in CB with perfectly linear models
25
Let us discuss how the parameters affect this regret bound.
" - S is large, the gaps between clusters that are not "Ç-close" are much greater than the minimum gap Ç for the algorithm to distinguish, the first term in Eq.(7) will be small as it is easy to identify their dissimilarities. The role of 71 - Ç in CBMUM is similar to that of y in the previous CB. If ū is small, indicating that few ground-truth clusters are "Ç-close", RCLUMB will hardly miscluster different ground-rruth clusters together thus the second term in Eq.(7) will be small. If the deviation level e, is small, the user models are close to linearity and the misspecifications will not affect the estimations much, then both the second and third term in Eq will be small. The following theorem gives a regret lower bound of the CBMUM problem.
Theorem 5.4 (Regret lower bound for CBMUM). There exists a problem instance for the CBMUM problem such that for any algorithm R(T) 2 VVc.VV).
The proof can be found in Appendix F The upper bounds in Theorem 5.3 asymptotically match this lower bound with respect to T up logarithmic factors (and a constant factor of v'm where m is typically small in splaapplicttions) showing the tightness of our theoretical results. Additionally, we conjecture the gap for the m factor is due to the strong assumption that cluster structures are known to prove this lower bound, and whether there exists tighter lower bound is left for future work.
We then compare our results with two degenerate cases. First, when m 1 (indicating ū = 0), our setting degenerates to the MLB problem where all users share the same preference vector. In this case, our regret bound is O /d log T + d log 7'), exactly matching the current best bound of MLB 23 Second, when e, O, our setting reduces to the CB problem with perfectly linear user models and our bounds become (dd/mml mtd//mTloggl
also perfectly match the existing best bound of the CB problem [7) The above discussions and comparisons show the tightness of our regret bounds. Additionally, we also provide detailed discussions on why trivially combining existing works on CB and MLBB would not get any non-vacuous regret upper bound in Appendix D
We define the following "good partition" for ease of interpretation.
Definition 5.5 (Good partition). RCLUMB does "good partition" at t, if the cluster V, assigned to & is a <-good cluster, and it contains all the users in the same ground-truth cluster as i,, i.c.
00:- 03l12 < C, vl E V,, and Vi(G.) Cv..
Note that when the algorithm does a "good partition" at f, V, will contain all the users in the same ground-truth cluster as i, and may only contain some other Ç-close users with respect 4, which means the gathered information associated with V, can be used to infer user is 's preference with high accuracy. Also, it is obvious that under a "good partition". if V, E V. then V. = Vi(i.) by definition.
Next, we give sketched proof for Theorem 5.3
Proof. [Sketch for Theorem 5.3 The proof mainly contains two parts. First, we prove there is a sufficient time Tu for RCLUMB to get "good partition" with high probability. Second, we prove the regret upper bound for RCLUMB after maintaining a "good partition". The most challenging part is to bound the regret caused by misclustering (-close users after getting a "good partition".
Sufficient time to maintain a "good partition". With the item regularity (Assumption 3.3) we can prove after some To (defined in Lemma H.I in Appendix H). RCLUMB will always have
7

---

"good partition". Specifically, after t 2 O(u
d A=(m- + 1 log T). for any user E U. the gap 23
between the estimated a. and the ground-truth 0 0)()) is less than 7 with high probability. With this, we can get; for any two users i and E, if their gap is greater than Ç, it will trigger the deletion of the edge (i, E) (Line 10 of A with high probability; on the other hand, when the deletion condition
of the edge (i, E) satisfied, then ga00) -gte) 0, which means user i and belong to different 2 ground-truth clusters by Assumption 3.1 with high probability. Therefore, we can get that with high probability, all those users in the same ground-truit cluster as it will be directly connected with it and users directly connected with must be (-close i, By filtering users directly linked with is as the cluster V. (Algo [ Line 5) and the definition of "good partition", we can ensure that RCLUMB will keep a "good partition" afterward with high probability.
2. Bounding the regret after getting a "good partition". After To, with the "good partition". we can prove the following lemma that gives bound of the difference between 0 Vv.r-, and ground-truth 0, in direction of action vector Ca. and supports the design of the confidence radius Ca,t in Eg 55)
Lemma 5.6. With probability at least 1 - 55 for some E (0, f)) Vt 2 To
x (0., 2v (v.--))
e. 2d IV V) +e xE(e Ve
x M 1 + 3 I|e lapp
To prove this lemma, we consider the following two situations.
(i) Assigning a perfect cluster for i, In this case, V. E V, meaning the cluster assigned for user in is the same as her ground-truth cluster, i.e., V, = Vi(G,) Therefore, we have that V E Vv, - 0z.-
With careful analysis, we can bound x= (O., 0v..e-)) by Ca, (defined in 5g.
(ii) Bounding the term of misclustering it's Ç-close users. this case, V. $ V. meaning the algorithm misclusters user it. i.e., V. Vi())) Thus, we do not have Vl V. r, 02 = 0,, anymore, but we have all the users in V. are (-close to it (by "good partition "), i... ||0,, 0 S V. V.- Then an additional term can be caused by using the information of ig Ç-close users in V. lying in different ground-truth clusters from é, to estimate Oi,- is highly challenging to bound this part.
We will get an extra term
x. M V. E og La xI (O., 0.)) when bounding the regret in SeV,
this case, where 1|0 0,112 S C, V V.. It an easy-to- masy-to-be-mand be-made mistake to directly drag 10,,- O., ll out to bound it by
x M M Ecc T
x With subtle analysis, we
2
propose the following lemma to bound the above term.
Lemma 5.7 (Bound of error caused by misclustering). Vt 2 To. if the current partition by RCLUMB is a "goo partition", and V, & V, then for all va E Rd, || l22 S 1, with probability at least - 6:
x M VV,
Eeer-n Fn. T (0,, 0,.) S s,v,
s. v2d
x
This lemma quite general. Please see Appendix G for details about its proof.
The expected occurrences of (V, V} is bounded by LT'' with Assumption 3.2 Definition 5.2 and 5.5 The result follows by bounding the expected sum the bounds for the instantancous regret using Lemma with delicate analysis due to the time-varying clustering structure kept by RCLUMB. 0
with
Experiments
This section compares RCLUMB and RSCLUMB with CLUB 12) SCLUB 27 LinUCB with a single estimated vector for all users, LinUCB-Ind with separate estimated vectors for each user, and two modifications of LinUCB in 23 which we name as RLinUCB and RLnnUCB-Ind. We use averaged reward as the evaluation metric, where the average is taken over ten independent trials.
8

---

DELLMB
ELLACO
KILACE
1.
(a) Synthetic
(b) Yelp Case
(c) Yelp Case 2
ROCLUM
CLUB
CLUB
Time
Time
(d) Movielens Case 1
(c) Movielens Case
Figure I: The figures compare RCLUMB and RSCLUMB with the baselines. (a) shows result on synthetic data, (b) and (c) show the results on Yelp datasct, (d) and (c) show the results on Moviclens datasct. All experiments are under the sctting of u = 1, 000 users, m 10 clusters, and d = 50. All results are averaged under random trials. The error bars are standard deviations divided by v10.
6.1 Synthetic Experiments
We consider a setting with 1, 000 users, m = 10 clusters and T 10 rounds. The preference and feature vectors are d 50 dimension with each entry drawn from a standard Gaussian distribution, and are normalized to vectors with ||-1|2 1 [27]. We fix an arm set with |.A| = 1000 items, at each round t, 20 items are randomly selected to form a set A, for the user to choose from. We construct a matrix
IR' 1210000x1.000 in which each element e(i,j) is drawn uniformly from the range (-0.2, 0.2) to represent the deviation. At f, for user is and the item ae, <(i,, a+) will be added to the feedback as the deviation, which corresponds to the c/ defined in Eq.1
The result is provided in Figure T a). showing that our algorithms have clear advantages: RCLUMB improves over CLUB by 21.9% LinUCB by 194.8%, LinUCB-Ind by 20.1%, SCLUB by 12.0%, RLinUCB by 185. 185.2% and RLinUCB-Ind by 10.6%. The performance difference between RCLUMB and RSCLUMB is very small as expected. RLinUCB performs better than LinUCB; RLinUCB-Inn performs better than LinUCB-Ind and CLUB, showing that the modification of the recommendation policy is effective. The set-based RSCLUMB and SCLUB separate clusters quicker and have advantages in the early period, but eventually RCLUMB catches up with RSCLUMB, and SCLUB is surpassed by RLinUCB- Ind because it does not consider misspecifications. RCLUMB and RSCLUMB perform better than RLinUCB-Ind, which shows the advantage of the clustering. So it can be concluded that both the modification for misspecification and the clustering structure critical to improving the algorithm's 's performance. We also have done some ablation experiments on different scales of e* in Appendix PP. and we can notice that under different e* our algorithms always outperform the baselines, and some baselines will perform worse as e increases.
6.2 Experiments on Real-world Datasets
We conduct experiments on the Yelp data and the 20m MovieLens data [17]. For both data, we have two cases due to the different methods for generating feedback. For case 1, we extract 1,000 items with most ratings and 1,000 users who rate most; then we construct a binary matrix H 1,000x1,,000 based the user rating 40 42]: if the user rating is greater than 3, the feedback is 1; otherwise, the feedback is O. Then we use this binary matrix to generate the preference and feature vectors by singular- value decomposition (SVD) [27 25 40). Similar to the synthetic experiment, we construct a matrix E E |00000 1,000 in which each element is drawn uniformly from the range (-0.2,0.22 0.2). For case 2, extract 1,100 users who rate most and 1000 items with most ratings. We construct binary feedback matrix H 11,100x1,000 based on the same rule as case 1. Then we select the first 100 100x 1,000 to generate the feature vectors by SVD. The remaining 1,000 rows F 11,000x1,000
rows H

---

is used as the feedback matrix, meaning user receives F(,,j) as feedback while choosing item j. In both cases, time t, we randomly select 20 items for the algorithms to choose from. case the feedback is computed by the preference and feature vector with misspecification, in case 2, the feedback is from the feedback matrix.
The results on Yelp are shown in Fig (b) and Fig c). In case 1, RCLUMB improves CLUB by 45. 1%, SCLUB by 53.4%, LinUCB-O One by 170.1% Lin by 46.2%, RLinUCB by 171.0% and RLinUCB-Ind by 21.5%. In case 2, RCLUMB improves over CLUB by 13.9 13.9% SCLUB by 5.1% 1%, LinUCB-One by 135.6% LinUCB-Img by 10.1%, RLinUCB by 138.6% and RLinUCB by 8.5%. is notable that our modeling assumption 3.4]is violated in case 2 since the misspecification range is unknown. We set c. 0.2 following our synthetic dataset and it can still perform better than other algorithms. When the misspecification level is known as in case 1, our algorithms' improvement is significantly enlarged, e.g.. RCLUMB improves over SCLUB from 5. % to 53.4%.
The results on Movielens are shown in Fig d and Te). In case 1, RCLUMB improves CLUB by 58.8%, SCLUB by 92. %. LinUCB-Oni One by 107.7%. Lnn by 61.5 %. RLinUCB by 109.5%, and RLinUCB-Ind by 21.3%. In case 2. RCLUMB improves over CLUB by 5.5%. SCLUB by 2.9%, LinUCB-One by 28.5%. LinUCB-Ind by 6.1%, RLinUCB by 29.3% and RLinUCB-Ind by 5.8%. The results are consistent with the Yelp data, confirming our superior performance.
7 Conclusion
We present a new problem of clustering of bandits with misspecified user models (CBMUM), where the agent has to adaptively assign appropriate clusters for users under model misspecifications. We propose two robust CB algorithms, RCLUMB and RSCLUMB. Under milder assumptions than previous CB works, we prove the regret bounds of our algorithms, which match the lower bound asymptotically in T up to logarithmic factors, and match the statc-of-the-an results in several degenerate cases. is challenging to bound the regret caused by misclustering users with close but not the same preference vectors and use inaccurate cluster-based based information to select arms. Our analysis to bound this part of the regret is quite general and may be of independent interest. Experiments on synthetic and real-world data demonstrate the advantage of our algorithms. We would like to state some interesting future works: (1) Prove tighter regret lower bound for CBMUM, (2) Incorporate recent model selection methods into our fundamental framework to design robust algorithms for CBMUM with unknown exact maximum model misspecification level, and (3) Consider the setting with misspecifications in the underlying user clustering structure rather than user models.
8 Acknowledgement
The corresponding author Shuai Li is supported by National Key Research and Development Program of China (20227D01 14804) and National Natural Science Foundation of China (62376154, 62006151, 62076161). The work of John C.S. Lui was supported in part by the RGC's GRF 14215722.
10

---

References
[1] Yasin Abbasi- Yadkki, Dávid Pál. and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Peter Auer, Nicolo Cesa-Bianchi. and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[3] Yikun Ban and Jingrui He. Local clustering in contextual multi-armed bandits. Proceedings of the Web Conference 2021, pages 2335-22330 2246, 2021.
[4] Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
[5] Kechao Cai, Xutong Liu, Yu-Zhen Janice Chen, and John CS Lui. An online learning approach to network application optimization with guarantce. IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pages 2006-2014. IEEE, 2018.
[6] Leonardo Cella and Massimiliano Pontil. Multi-task and meta-learning with sparse linear bandits. In Uncertainty in Artificial Intelligence, pages 1692-1702, PMLR, 2021.
[7] Leonardo Cella, Alessandro Lazaric, and Massimiliano Pontil. Meta-learning with stochastic linear bandits. In International Conference Machine Learning, pages 160-1370. PMLR, 2020.
[8] Leonardo Cella, Karim Lounici, Grégoire Pacreau, and Massimiliano Pontil. Multi-task rep- resentation learning with stochastic linear bandits. In International Conference Artificial Intelligence and Statistics, pages 4822-4847. PMLR, 2023.
[9] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proceedings, 2011.
[10] Aniket Anand Deshmukh, Urun Dogan, and Clay Scott. Multi-task learning for contextual bandits. Advances in neural information processing systems, 30, 2017.
[11] Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting mis- specification in contextual bandits. Advances in Neural Information Processing Systems, 33: 11478-1 14478-1148,, 2020.
[12] Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering bandits. In International Conference on Machine Learning, pages 757-765. PMLR, 2014.
[13] Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, and Evans Etrue. On context-dependent clustering of bandits. In International Conference on machine learning. pages 1253-1262. PMLR, 2017.
[14] Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
[15] Jens Hainmueller and Chad Hazlett. Kernel regularized least squares: Reducing misspecification bias with flexible and interpretable machine learning approach. Political Analysis, 22(2): 143-168, 2014.
[16] Negar Hariri, Bamshad Mobasher, and Robin Burke. Context adaptation in interactive recom- mender systems. In Proceedings of the 8th ACM Conference on Recommender Systems, pages 41-48, 2014.
[17] Maxwell Harper and Joseph Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis, 5(4):1-19, 2015.
[18] Joey Hong, Branislav Kveton, Manzil Zaheer, and Mohammad Ghavamzadeh. Hierarchical bayesian bandits. International Conference on Artificial Intelligence and Statistics, pages 7724-7741. PMLR, 2022.

---

[19] Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances neural information processing systems, 34:27057-27068, 2021.
[20] Pushmeet Kohli, Mahyar Salek, and Greg Stoddard. A fast bandit algorithm for recommenda- tion to users with heterogenous tastes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 1135-1141, 2013.
[21] Fang Kong. Canzhe Zhao, and Shuai Li. Best-of-three- -hrdoo analysis for linear bandits with follow-the-ree wew.ttrrrguuliaie-eeeeeeeee algorithm. arXiv preprint wrXiv22303.06825 2023.
[22] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[23] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International Conference on Machine Learning, pages 5662-5670. PMLR, 2020.
[24] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[25] Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[26] Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages
2016.
[27] Shuai Li, Wei Chen, Shuai Li, and Kwong Sak Leung. Improved algorithm on online clustering of bandits. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, IJCAL 19, page 2923-2929. AAAI Press, 2019. ISBN 9780999241141
[28] Xutong Liu, Haoru Zhao, Tong Yu, Shuai Li, and John Lui. Federated online clustering of bandits. In The 38th Conference Uncertainty in Artificial Intelligence, 2022.
[29] Xutong Liu, Jinhang Zuo, Siwei Wang. John CS Lui, Mohammad Hajiesmaili, Adam Wierman, and Wei Chen. Contextual combinatorial bandits with probabilistically triggered arms. In International Conference on Machine Learning, pages 22559-22599 PMLR, 2023.
[30] Xutong Liu, Jinhang Zuo, Hong Xie, Carlce Joe-Wong, and John CS Lui. Variance-adaptive al- gorithm for probabilistic maximum coverage bandits with general feedback. In IEEE INFOCOM 2023-IEEE Conference on Computer Commumications, pages 1-10. IEEE, 2023.
[31] Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic bandit problems. Advances in Neural Information Processing Systems, 101000228813333 2020.
[32] Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 9603-9611, 2021.
[33] Marta Soare, Ouais Alsharif, Alessandro Lazaric, and Joelle Pineau. Multi-task linear bandits. In NIPS2014 workshop on transfer and multi-task learning: theory meets practice, 2014.
[34] Runzhe Wan, Lin Ge, and Rui Song. Metadata-based multi-task bandits with bayesian hi- erarchical models. Advances in Neural Information Processing Systems, 34:29655-29663 2021.
[35] Runzhe Wan, Lin Ge, and Rui Song. Towards scalable and robust structured bandits: meta- learning framework. In International Conference on Artificial Intelligence and Statistics, pages 1 1144-117.. PMIR, 2023.
[36] Zhi Wang, Chicheng Zhang, Manish Kumar Singh, Laurel Riek, and Kamalika Chaudhuri. Mul- titask bandit learning through heterogeneous feedback aggregation. International Conference on Artificial Intelligence and Statistics, pages 1531-1539. PMLR, 2021.
12

---

[37] Zhi Wang, Chicheng Zhang, and Kamalika Chaudhuri. Thompson sampling for robust transfer multi-task bandits. arXiv preprint arXiv:2206.0855 08556, 2022.
[38] Zhiyong Wang, Xutong Liu, Shuai Li, and John CS Lui. Efficient explorative key-term selection strategies for conversational contextual bandits. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 10288, 2023.
[39] Zhiyong Wang. Jize Xie, Tong Yu, Shuai Li, and John Lui. Online corrupted user detection and regret minimization. arXiv preprint arXiv:2310.04700 2023.
[40] Junda Wu, Canzhe Zhao, Tong Yu, Jingyang Li, and Shuai Li. Clustering of conversational ban- dits for user preference learning and elicitation. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2129-2139, 2021.
[41] Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in collaborative environment. In Proceedings of the 39th International ACM SIGIR conference on Research and Development Information Retrieval, pages 329-538, 2016
[42] Shi Zong, Hao Ni, Kenny Sung, Nan Rosemary Ke, Zheng Wen, and Branislav Kveton. Cas- cading bandits for large-scale recommendation problems. arXiv preprint 2016.
13

---

Appendix
A More Discussions on Related Work
In this section, we will give more comparisions and discussions on some previous works that are related to our work to some extent.
There
other works bandits leveraging user (or task) relations, which have some relations with the clustering of bandits (CB) works to some extent, but are in different lines of research from CB, and quite different from our work. First, besides CB, the work [1 also leverages user relations. Specifically, it utilizes a known user adjacency graph to share context and payoff's among neighbors, whereas in CB, the user relations are unknown and need be learnt, thus the setting differs lot from CB. Second, there are lines of works on multi-task learning 6 33
S 37 36].
meta-learning 35 |8 7 and federated learning 32 19], where multiple different tasks are solved jointly and share information. Note that all of these works do not assume an underlying unknown user clustering structure which needs be inferred by the agent speed up learning. For works on multi-task learning [6] 10] 33, 8 337 36), they assume the tasks are related but no user clustering structures, and to the best of our knowledge, none of them consider model misspefications, thus they propose general Bayesian hierarchical models to share knowledge across tasks, and design Thompson-Samplinn based algorithms to optimize the Bayes regret, which are quite different from the line of CB works, and differ a lot from ours. And additionally, as supported by the discussions in the works [7 36). multi-task learning and meta-learning are different lines of research from CB. For the works on federated learning [32 19], they consider the privacy and communication costs among multiple servers, whose setting is also very different from the previous CB works and our work.
differing a lot from ours. For some recent works on meta-learning [5 18
Remark. Again, we emphasize that the goal of this work is initialize the study of the important CBMUM problem, and propose general design ideas for dealing with model misspecifications in CB problems. Therefore, our study is based on fundamental models on CB [2 27 and MLB (3) and the algorithm design ideas and theoretical analysis are pretty general. We leave incorporating the more recent model selection methods [1 into our framework to address the unknown exact maximum model misspecification level as interesting future work. It would also be interesting to consider incorporating our methods and ideas of tackling model misspecifications into the studies of multi-task learning, meta learning and federated learning.
B More Discussions on Assumptions
All the assumptions (Assumptions 3.1 3.2 3.3,in this work are natural and basically follow (or less strigent than) previous works on CB and MLB 12
25 27 28
B.1 Less Strigent Assumption on on the Generating Distribution of Arm Vectors
We also make some contributions to relax widely-used but stringent assumption on the generating distribution arm vectors. Specifically, our Assumption 3.3 on item regularity relaxes the previous one used in previous CB works
25 27 28 by removing the condition that the variance should be upper bounded by A. For technical details on this, please refer to the theoretical analysis and discussions Appendix
12
x²
B.2 Discussions on Assumption 3.4 about Bounded Misspecification Level
This assumption follows 23 Note that this e, can be an upper bound on the maximum misspeci- fication level, not the exact maximum itself. In real-world applications, the deviations are usually small 14, and we can set a relatively big c, (e.g., 0.2) to be the upper bound. Our experimental results support this claim. As shown in our experimental results on real-data case 2, even when c, is unknown, our algorithms still perform well by setting e.. = 0.2. Some recent studies [1] use model selection methods to theoretically deal with unknown exact maximum misspecification level in the single-user case, which is not the emphasis this work. Additionally, the work [IT] assumes that the learning agent has access to regression oracle. And for the work (3I,, though their regret bound
14

---

is dependent on the exact maximum misspecification level that needs not to be known by the agent, an upper bound of the exact maximum misspecification level is still needed. We leave incorporating their methods to deal with unknown exact maximum misspecification level as an interesting future work.
B.3 Discussions on Assumption 3.2 about the Theoretical Results under General User Arrival Distributions
The uniform arrival in Assumption 3.2 follows previous CB works [2 25 28 it only affects the To term, which is the time after which the algorithm maintains a "good partition" and is of Ou log T). For an arbitrary arrival distribution, To becomes ((1 /Pmin log TT), where pmii is the minimal arrival probability of a user. And since it is a lower-order term (of Ollog 7)), it will not affect the main order of our regret upper bound which is of Dlc.TVmdloo T + dy'TT log T). The work (27] studies arbitrary arrivals and aims to remove the 1/Pmin factor in this term, but their setting is different. They make an additional assumption that users in the same cluster not only have the same preference vector, but also the same arrival probability, which is different from our setting and other classic CB where we only assume users in the same cluster share the same preference vector.
works 12
25
28
C Highlight of the Theoretical Analysis
Our proof flow and methodologies are novel in clustering of bandits (CB), which are expected to inspire future works on model misspecifications and CB. The main challenge of the regret analysis in CBMUM that due to the estimation inaccuracy caused by misspecifications, it is impossible to cluster all users exactly correctly, and it is highly non-trivial to bound the regret caused by "misclustering" Ç-close users.
To the best of our knowledge, the common proof flow of previous CB works (e.g., 12 251 28 be summarized in two steps: The first is to prove sufficient time Tý after which the algorithms can cluster all users exactly correctly with high probability, Note that the inferred clustering structure remains static after TV making the analysis easy. Second, after the correct static clustering, the regret can be trivially bounded by bounding m (number of underlying clusters) independent linear bandit algorithms, resulting in a Old mT log 7') regret.
can
The above common proof flow is straightforward in CB with perfectly linear models, but it would fail to get a non-vacuous regret bound for CBMUM. In CBMUM, it is impossible to learn an exactly correct static clustering structure with model misspecifications. In particular, we prove that can only expect the algorithm to cluster Ç-close users together rather than cluster all users exactly correctly. Therefore, the previous flow can not be applied to the more challenging CBMUM problem.
We do the following to address the challenges in obtaining a tight regret bound for CBMUM. With the carefully-designed novel key components of RCLUMB, we can prove sufficient time To after which RCLUMB can get a "good partition" (Definition 5.5) with high probability, which means the cluster V. assigned to i, contains all users the same ground-trun -trutth cluster as ét, and possibly some other i i Ç-close users. Intuitively. after To. the algorithm can leverage all the information from the users' ground-truth clusters but may misuse some information from other Ç-close users with preference gaps up to Ç. causing a regret of "misclustering" Ç-close users. It is highly non-trivial to bound this part of regret, and the proof methods would be beneficial for future studies CB in challenging cases when it is impossible to cluster all users exactly correctly. For details, please refer to the discussions "(ii Bounding the term of misclustering it's Ç-close users" in Section the key Lemma 5.7 (Bound of error caused by misclustering), its proof and tightness discussion in Appendix G Also, a more subtle analysis is needed to handle the time- varying inferred clustering structure since the "good partition" may change over time, whereas in the previous CB works, the clustering structure remains static after Tg. For theoretical details on this, please refer to Appendix
D Discussions on why Trivially Combining Existing CB and MLB Works Could Not Achieve a Non-vacuous Regret Upper Bound
We consider discussing regret upper bounds for CB without considering misspecifications for three cases; (1) neither the clustering process nor the decision process considers misspecifications (previous
15

---

CB algorithms); (2) the decision process does not consider misspecifications; (3) the clustering process does not consider misspecifications.
For cases (1) and (2), the decision process could contribute to the leading regret. We consider the case where there m underlying clusters, with each cluster's arrival being 7/m, and the agent knows the underlying clustering structure. For this case, there exist some instances where the regret upper bound R(T") strictly larger than e.Tvm log T asymptotically in T. Formally, in the discussion of "Failure of unmodified algorithm" in Appendix E in [23]. they give an example to show that in the single-user case, the regret R3 (T) of the classic linear bandit algorithms without considering misspecifications
(T)
will have:
lim
+oc. In our problem with multiple users and underlying
T-+++00 c, vm log
clusters, even if we know the underlying clustering structure and keep m independent linear bandit algorithms with T; for the cluster E [mi] to leverage the common information of clusters, the best we can get is R2 (T) Eie(m] R1 (T,). By the above results, if the decision process does not consider
(R1(T/m) T-+00 e.TvmlogT T-+ e, C.T logT too. Recall that the regret upper bound R(T") of our proposed algorithms of (e,T /md dymm log T") (thus, we have lim 00 c,T' v
misspecifications, we have lim R2(T))
lim
R(T)
+o0), which gives proof that that the regret upper bound of our proposed algorithms is asymptotically much better than CB algorithms in cases (1)
For case (3), if the clustering process does not use the more tolerant deletion rule in Line of Algo the gap between users linked by edges would possibly exceed ( (C = 2t. v even after To, which
will result in regret upper bound no better than O(E.uvdT') As the number of users is usually huge in practice, this result is vacuous. The reasons for getting the above claim are as follows. Even if the clustering process further uses our deletion rule considering misspecifications, and the users linked by edges are within ( distance, failing to extract 1-hop users (Line 3 in A would cause the leading ( (e.uuddT) regret term, as in the worst case, the preference vector of the user in V. who is h-hop away from user it could deviate by hc from Oi where h can be large u, and it would make the second term Eq. O(c.vv term. If we completely do not consider the misspecifications in the clustering process, the above user gap between users linked by edges would possibly exceed Ç, which will cause a regret upper bound worse than O(E.uVdT).
E Proof of Theorem 5.3
We first prove the result in the case when ?i defined in Definition 5.1 is not infinity, i.e., 4e, / < Y1 < cc. The proof of the special case when 71 = oo will directly follow the proof this case.
For the instantancous regret RG at round t, with probability at least 1 - 58 for some d E (0, f) at Vt To:
R₁ = (2x 0i, + 6xj
4nd ) (xt, 0i + +
= n. (0:, -0 0v, + (I Vv + Caazt) (2r T Vv + Cayt))
+ w. (0v - 00.) + +Caat - Cois + (e/1 E
(10)
2e, v2d
$ 20,,t +
11V, $ V} + 2E,,
where the last inequality holds by the UCB arm selection strategy in Eq. the concentration bound given in Lemma 5.6 and the fact that e Il I <G, E. VL.
We define the following events. Let
2E Vd
En RR. < 2Ca,,t
I(V, V) + 2e,, for all (1: (.:6 2 To, and the algorithm maintains "good partition" at (})
A
Σ = {the algorithm maintains "good partition" for all t > To},
È Eo E
16

---

P(E)) > - 26. According to Lemma H.1 P(E1) 2 1 - 35. Thus, P(E) 2 1 - 56 for some
8 E (0, 7) Take 8 J. we can get that
B[R(T)] = P(E)) + (())(())((T)
- [(E)A(T))+ + x T
XT
(11)
= (T) +,,
where & denotes the complementary event of &, 1LEE (R(T) denotes R(T) under event E, ((T)(TT)
denotes R(T) under event &, and we use R(T) S ' to bound R(T)) under event E
Then it remains bound [[E)
((E)R(T) & R(T)) B[(EE}
Σ
Ry
To+1
2c 2d
T
To 2E[LEE
Σ Coca +
Σ
EIIE V, & VJ] 2E.T (12)
1=
1o
De, 2d
= To +2E111))
Σ Cocel +
P(IEE V. & V)) -
t=
16+1
2c. 2d
2d
$ To 2E[[(E)
Σ
Cartel +
T
2,,T,
(13)
u
To
where Eq.(12 (12 follows from (O).
13) holds since under Assumption about user arrival
uniformness and by Definition 5.5 "good partition", P(]E,, V, & V)) S 5. 1. 2 To, where
defined in Definition 5.2
Then we need bound [[[(E] Ei=To+1 Can,):
I(E)
Σ
Cua,t = (VX+ (2 () dlog(1 T
)
[TE)
E (=To+1
||aa, ll Mp
Xd
T=
T
+ +11Ef
Σ
Σ
x T
M V.,-11 1a.
(14)
(=
-clo-11
SeV.
Next, we bound the 1{E} J
To=To+1
||
M M
term in Eq.
T
[(E)
Σ
Tay
= [{{}}
Σ
T(i E V.le |a M vi
M
[=To+1 k=1
T
Σ
Mi E V3} | Myj..
(15)
(=To +1 j=1
T
<1{88)
Σ
Ih E V2J Σ
Iftr E V/) l vyre-
To
To
(16)
< <{{8} Σ j=1
2T Tdggo + Xd
(17)
T.
T
< <[{E),
2 2
T Tv log(1 + xd) - I(8) = ( log(1
Ad'
1=1
(18)
17

---

where we use my to denote the number of connected components partitioned by the algorithm at t, V & E [me] denote the connected components partitioned by the algorithm at t, V f S Vi,x to denote the subset extracted to be the cluster V, for i, from V conditioned on is E V and TV, to denote the number of times that the served users lie in the ground-truth cluster V, up to time T, i... Tv, Eierr] ir E ViJ.
The reasons for having Eq. (1) are follows. Under event &, the algorithm will always have a "good partition" after To. By Definition 5.5 and the proof process of Lemma H.l about the edge deletion conditions, we can get I m and if is E ViAA, 4s E V₁, then V, S Ve, since Ve contains V/ and possibly other ground-truth clusters Vn, E [m]] whose prefer- ence vectors are Ç-close to 0¹ Therefore, by the definition of the regularized Gramian matrix, we can get Mv V = Mv,,0-1, Vt 2 To 1. Thus by the above reasoning. Σx=1 If E
Vi || (Baalllm) IM 1-
ンー l( V3} || M 4 To + 1. 16) holds by the
Cauchy-Schwee -chwwrz incquality: Eq. (7) follows by the following technical Lemma J.2
Eq. 18 is
from the Cauchy-Schwarz inequality and the fact that ΣØ= Tv, T.
We then bound the last term in Eq. (4.
[(E}, Σ
Σ
To.
T
M V,, Da
= -[EE,
Σ
Σ
I(i V.n
Σ
Fa. T M
V Ve Fo.
(=To+1
sE|t-1| 1.EV
[=To+1 k=1
-E|t-1| fe
Mi Σ
$ <I(E)e,
Σ
Ii V.
E
x
M 1 1 Co.
T=
selt NeVV
(19)
mi Etli The Vine To: -
S <T(E)G
|
2
MTp
[To++1#=1
(20)
T
mc
my
$ <1{8,,
Σ k=1
li E Viat
Σ k=1
Iiss E V/ VT
1
M
[=To+1
(21)
m,
<T(8)G.T VT
Σ A=1
The E Vi
|| 11 M
[=To+1
(22)
T
m2
<((8)GVT
Σ E
Σ
T(i ViAe)
||a
11
M
t=Ta+1 (=To+1k=1
(23)
S1EEAVT
T Σ
Σ
li V/}} ||
MyJ...
f=1++//=1
(24)
= =[EJTT
Hi E ViJ
||
11
M vz.e-
j=1 T+
$ $1(8Je,T v log(1 + Xd
(25)
18

---

where Eq. 19
Eq.
2 and Eq. (23)
hold because of the Cauchy Cauchy-Schwarz inequality, (q) holds
since M
=
Σ
acle Ta T
Eq. 22 is because
S 7, Eq. (24) follows from the
same reasoning as Eq. (1). and Eq (25) comes from the following technical Lemma J.2
Finally, plugging Eq. 18 and Eq
25
into Eq.
14 take expectation and plug it into Eq. we can
get:
2e 2dT
2c. T ( (+
T
R(T) 55 To
2md log(1 (1 + Ad
T xa
T
+
Vx
( + dlogg(
x 22mdTlog +
Ad
(26)
where
u To 16u log
8d
16
8d
+ 4u max max
log(
log(
Ae
21
1
)
x
i20
Exy
2h.
is given in the following Lemma H. in Appendix
F Proof and Discussions of Theorem 5.4
In the work [23, they give lower bound for misspecified linear bandits with single user. The lower bound of R(T) given by: R2(T) 2 e.TVd. Therefore, suppose our problem with multiple users and m underlying clusters where the arrival times are T; for each cluster, then for any algorithms, even if they know the underlying clustering structure and keep m indepen- dent linear bandit algorithms to leverage the common information of clusters, the best they can get is R(T)- Eiemi (T( e, Exe(m Tivd e,Tvd, which gives lower bound of VVc.TVd) for the CBMUM problem. Recall that the regret upper bound of our algorithms is of Vie.T/mlooy + mí log 7),, asymptotically matching this lower bound with respect to T up to logarithmic factors and with respect to m up to (mm)) factors, showing the tightness of our thcoretical results (where
typically very small for real applications).
We conjecture that the gap for the m factor is due to the strong assumption that cluster structures are known to prove our lower bound, and whether there exists a tighter lower bound will be left for future work.
G Proof of the key Lemma 5.7
In Lemma 5.7 we want to bound the term
By the definition "good partition", we have |0O,, 0.,112 S <. Vi, V.. It an easy-to-be- mistake
o Mr..-1 E =e Ia, xT, 0,.))
v.V.
to directly drag 0, 0; out to upper bound by then proceed. We need more careful analysis.
x M
Σ
Ecc 1: aa TT, Gev,
x ( and
2
We first prove the following general lemma.
Lemma G.I. For vectors 11, 22 ..., 2g Rd || S 1, [k], and vectors 02, Oz,...,, O2
Fd 0 S C, Vi [k). where C' is a constant, we have:
k Σ
0 0:
<ovd
32 x
1=1
19

---

Proof.
Let X E Rdxk
be a matrix such that it has as its columns, i.e., X [x1,.... xz.]
421
0k1
112
T22
422
[idd
T2d
Lkd
Let y Rxx1 be vector that has xz.6 as its elements, i.c. y |x] ...... x/ 0x] Then we
have:
k
a.
0
X 2
X
(27)
k = =| Σ
(z)) 0,)²
k
$ X 2
Σ
|| 11 10:112
(28)
< C ||
Ca 11
1
X
1
< 1
x 1/
(29)
c2d
xx
(30)
2
= ccd
Σ
(31)
$
i=1
where Eq. 27 follows by the matrix operator norm inequality, Eq.
28 follows by the
Cauchy-Schware inequality, Eq. (29 follows by |
S vd
X
ll. Eq.
30 follows from
X 1 xx
The above result is tight. We can show that the lower bound of E 2..0 0: under the conditions
the lemma exactly Cvd Σ i- x. Specifically, let = 2, C 1, = 2, x = [0, T
[1,0] 0 = [1 02 = [0, T] then we have | x 0.112 = 1||11, 1 22, and
22
Cva Σ 2.
x 22 1. 1 = V2. Therefore, we have that the upper bound
given in Lemma
G. matches the lower bound.
We are now ready prove the key Lemma
5.7 with the above Lemma G.I
20

---

At any 2 To. if the current partition is a "good partition", and V. & V. then for all E
Rd | ll S with probability at least 8:
Lo MV.M.. V,,--1
Σ
La. La (0,, -0a)
$ Dull2
M M
Σ
Bay Da Fon (0,, (0,, - )
(32)
sE 21 V
[c[(-1]
ieEVi
M V
v1,t-1
Σ
La, Fa, T
10 -
(33)
L.V,
2d
I 2E, 2
x
M M
Σ scli-1) GEE
Da La T
(34)
Amaz E
relt inVV
Da 2
2d
S 26,
Amin (M v,tt-1)
2d
Tv,,-11
$ 2E,
X
(35)
Am
2T V +1
6. 2d
where Eq. 32 follows by the Cauchy-Schwar inequality, Eq. 33 follows from the inequality of
matrix's operator norm, Eq. follows from fact that "good partition", ||0,, 01l12 S
20, vl E V. and Lemma G.1 Eq. follows by Eq. with probability 2 1 5.
H Lemma H.1 of the sufficient time To and its proof
The following lemma gives a sufficient time To for the algorithm to get "good partition". Lemma H.1. With the carefully designed edge deletion rule, after
To A 16u 16u log(5) u + 4u max max
8d
16
8d
log
log
evy
)2
27.
=0(1 (
d
1
1
+
log
" 2)2
X2
rounds, with probability least 1 36 for some partition".
(0, 2)) RCLUMB can always get a "good
Below the detailed proof Lemma H.l
Proof. We first prove the following result:
With probability at least 1 å for some å E (0, 1), at any E [T]:
3(T 3 + Ex The Vieu,
|| 0 0010)
<
(36)
V + Amin (M
21

---

where 3(Ti,: = _ +X+ (2)) + dloog11 + Tit).
Oi, 00(1))
+ + L 2 T
Σ
E. (z 00(00 + =x + maa) O0(1)
(37)
a,
ccl ty
Pa
Ba a da
X1) 111
Ni T (1) -x0100
Lo aa
Sa.t + Σ
Fa Aal - 00
sEtt
-M i, (2(1) M,
S.. Da a,
Mi,
Σ
Ta As
where we denote M = M,, + XI, and 37 37 Therefore,
holds by definition.
0
0500
M 02(33)
+
M
1,c
Σ
Fa,
Cas
Last
+
M 1,8
Ba
118
(38)
We then bound the three terms Eq.
38
one by one. For the first term:
> M 1,1 0
M 1.8
0000
(39)
Amin (M..))
where we use the Cauchy-Schwarz inequaalty, the inequality for the operator norm of matrices, and the fact that Amin (,,,) A.
For the second term in Eq. 38):
M i Σ
tei Ha,
max #ES
Σ x M,, Du, ctei Ea,
Σ
x T M 1,1 Bn, E tane
max
Ca.
#ES4-1
max
Σ
x T M
i, Ee. || [ 11.0
(40)
WES4-1
6 max
Σ *E[t]
x M i, Ca.
#ES4-1
C.
M i,t Dt.
(41)
WESM
xE f
Fams
e, Tigy
max #ES2-1
T M 1
(42)
(43)
Amin' M.
where we denote 5d-1 {x E Rd: ||m||| 1}. Eq. follows from Holder's inequality, Eq.
41
follows by the Cauchy-Schwar inequality, Eq. 42 holds because M s,c Σ vete Ca, x Eq. follows from the Courant-Fisched theorem.
43
22

---

For the last term in Eq.
M 1.2
Σ
La ?
Mi 1.
Σ
Lo, ?7
M
1.8
(44)
xE(e]
ve(t /x
2
1
Co. 7o
Mi
(45)
Amia M 2,t)
where Eq. (44) follows by the Cauchy-Schward inequality and the inequality for the operator norm of matrices, and Eq. (45) follows by the Courant-Fischer theorem.
Following Theorem in with probability at least - 8 for some å (0, 1), for any i U. we
have:
2 log u 8 + log( det(M,,)) det(A()
Σ La ?e aE(e]
$
M
Tú,
2 log 8 + d log(1 + Ad
(46)
where dct(M) denotes the determinant of matrix M, E6) is because det(M -
trace(AT+ sele T.) Ad+23. and det(AT) =
Plugging Eq. into Eq. (45). then plugging Eq. that Eq. 73 holds with probability 2
Eq. and Eq. (45) into Eq.388., we can get
Then, with the item regularity assumption stated in Assumption 3.3 the technical Lemma J.I together with Lemma 7 in (25), with probability at least 1 6, for a particular user i, at any & such
that Ti, 2 16 log( 8d ). we have:
x2 $28
Amin (Mer) 2 Ti. X.
(47)
Based on the above reasoning, we have: Ti, 2
16 X2
log(
8d ), then with probability 2 1 - 25, we X38
have:
B(TiL, () + C..
0.., 05(0)
AAmin (M,,))
B(Ti,, 2 + tev/Tix
V 22 +
VA v 222220 2log()) dlog(1 Fid
1
+ +ca
(48)
for any i E U.
Let
V + 2 log(() + +d logg(1 +
Tee Ad
1
7
+ +
<
(49)
2
2)x
4
which is equivalent to
VX + 2 (l) + dloo(1
Ted
Ad
21
1
Ex
(50)
2dx +
4
2x
23

---

where is given in Definition 5.1
Assume À < 2 log( x) + d log + The Ad
which is typically held, then a sufficient condition for Eq.
(50 is:
2 log + d log(1 +
Tue Ad
1
1 )² c/
(51)
2x, The
4
22
To satisfy the condition in Eq. 51 it is sufficient to show
log
1 71
1
ev/
)²
(52)
Tiet
4
2xx
and
d dllo(1 + 2i
1
1
Ad
co1
)2
(53)
8
27d
From 52.. we can get:
8 (l
Th Z
(54)
Aa Eo /V/2 21
Following Lemma 9 in 25 we can get the following sufficient condition for (5.
8d log(
A c.
Te
(55)
\0 6, v 2x
Assume 2
4 Nd. ( - 2h.
which is typically held, we can get that
8d
T5.
log(
(56)
a sufficient condition for Eq.44) (49). Together with the condition that Tie 2 X Ag8
log(
we can get
that if
Trt 2 max
Sd
log(
U
16
log(
8d
},, Vi EM,
(57)
Xz 2
6n
2h.
then with probability 2-22.
[0,t
gi(1)
'1
Vieu.
By Lemma 8 in 25 and Assumption
3.2 of user arrival uniformness, we have that for all
t 2 To 16u log( " ) + 4u maxf
8d
u
16
8d
log
log
}}
(58)
X Cx
)2
8
X
21.
with probability at least 6, condition in (7) is satisfied.
Therefore we have that for all t 2 To, with probability 2 - 36:
@ go(1)
< 21 Vieu.
(59)
2 4
Next, we show that with (5) we can get that the RCLUMB keeps "good partition". First, if we delete the edge (i. (). then user and user j belong to different ground-truth truth clusters, i.e., ||0, 0,l12 0. This is because by the deletion rule of the algorithm. the concentration bound.
and triangle inequality, ||:: - 0
(e00))
2
10.. 0
(gi()) 01,1
24

---

(000) 0z. 0. Second, we show that 110,
0rl
2 71
2c, V X
the RCLUMB
algorithm will delete the edge (i, I).
This because if ||0; 0:1
2 71, then by the trian-
gle inequality, and |0.. g011)
0c. 0001
21 0,
0000) 0: 0000
2
2
have 00., - 01. 110 0ill
0o.
0
Olt
00
> 71 21 21 21
va+ 2log( # Hog((1 XF
VA+y v 2 logg( # + 11g 244
+ +Ev 2
+ E 2
which will trigger
2A+2A the deletion condition Line i0 in Algo |
VA+22=Ti.
From the above reasoning, can get that at round t, any user within V. is Ç-close to it, and all the users belonging to Vi are contained in Vr, which means the algorithm has done "good partition"
at t by Definition 5.5
I Proof of Lemma 5.6 5.6
We prove the result in two situations: when V, V and when V. V.
(I) Situation 1: for any & > To and V. E V. which means that the current user i, is clustered completely correctly, i.e., V. = Vi(t,) therefore 0 = o.., VI E V., then we have:
V,,--1
0 = Σ
La a u. X Σ
La ra) U..
-E|t-11 I| VV
-E
Eo. Da, XI)
Σ
Da. (I Oi + t,e,"" + nol) O..
sc[(-1
5,V,
LEV,
Σ
La Ba, XI)
Σ
Ca (Ir Oi + Sas + m/o) O.. t,,,
*E|-11
-E[t-1]
SeV,
Ca x a.
-X) Σ
Va x a. + +1)0;, - -20; + Σ
Ba, d,
2218 +
Σ
La, Fay 0:.
- TeV
xE(t-1)
xE(e-11 1eeV
-e|t-1]
LeV
AM V,t-1
0
Σ
M
Ve.t Ba, Ca.
+
Σ
M Vett-1 Fa, 11s
--|--1
E T.V,
T.
Therefore we have
F.1 IT (0v,.-1 - 0..) s > x M
Mv...100 0i +
Σ F MV.---Iaa
Ca, 2.id
+ x3 M
Σ
Da, No
AE|t-1] NeV
rE(r-1]
(60)
Next, we bound the three terms in Eq.60)). For the first term:
A x M MV, 0i, s A ||
M v..-i
Vmmax (M (Amx(MM
(M 114 S VA |xc M -
(61)
where use the inequality of matrix norm, the Cauchy- Cauchy-Schwarz inequality, |00,112 S 1, and the fact that Amax (M vi,--)) Mnie X
25

---

For the second term in Eq. (6):
Σ
v Mv...- Coa Enn x
Dg M ve,t11 La 2o13
-E(c-1 LxCV
ve 11
Σ
Da T
M M v.
6r 10
eE(r-1]
S 6, Σ
x M V
(62)
-E|t-1 'ee,
where in the second inequality we use the Holder's 's inequality. For the last term, with probability at least - ō:
M V,,-1
Σ
Lo, 1/3
5 Ca M v
Σ
To, 119
(63)
scll-1 1] e,
LEI SeV,
M v
2 2oog( ) + +log(
det det(M (M.
< Da M v..-1
det(Al)
T Fa MM MPl.- V (2 } dlog(1
(64)
Xd
where the second inequality follows by Theorem in [ Eq.644 is because det M Vi,--1) S
traco(AT+
*E Ma. ai.
Ad+Iv ) and det (AT) Ad.
Eq. 62) and Eq.64 into Eq. 68.660.. we can prove Lemma 5.6 in situation 1, i.c., for Plugging Eq. 66
any 2 To and V. V. with probability least d:
x (0 - Ozx) 01:)s SE
Σ -E/t-1 TeEV
x; M V 17,1-17. Ca
+||
v (Vity2 21og( + d logg(1 + Aad
M
(65)
(2) Situation 2: for any 2 To and V. & V, which means that the current user is misclustered by the algorithm, i.c., V. * Vy(a), but with Lemma H.l with probability at least 36, the current
26

---

partition is "good partition", i.c., 100--1 - 22, V 2 14 Ve. we have:
P V,,--1
0i =
Daa a aa
11)
Σ
Da r's) - i:.
1E/--11
Vo
Ve
Σ
Da, x T
xI)
La. (2 Os ch,"" + m1o) Ui.
#Ejt=1]
=e[t-1]
LeEV
M V
Σ
Da, o2
M M
Σ
Da, nls
M Mv Σ
Da Fo, 0: 0i
1]
ve(e-1)
PeEV
LeEV
-M
Σ
Ba, 3
M
Σ
Ca Bs
M M
Σ
Da, 2. a, (0:, 0:.)
cil 1]
ailt 11
scit 1]
+ M v,,-1
Σ
La a + 11)0,
AM V V.1-1 Oz. - -0
-E|t-1]
M M
Da c. M V,,-1
Σ
Ta M V
Σ
La vo, (0;, -0:0-a)) -0.)
=E[t-1]
=E[t-1] L
L.EV
1xEV
AM V. o:.
Thus, with Lemma 5.7 and with the previous reasoning, with probability least 56, we have:
x/_ 1e.(077..) (0v,.-1 0x.) s \ x. MV..- 0n|+
Σ -E|c-11 ieEV
I, MV. V. 1 Ca C.,
+ x. M
V
V
Σ
Da n
[E[e-1] i
+
8 M Mv
Σ
La, x a.
T (0:, - Oie)
<ett-1
LeV,
1 (3) + dlog(1 + Ad (VA+ / 22
I 4
L. M V,t- 1,t-1 Ca.
La.
+ | M M
4E|t-1|
6, V 2d
Therefore, combining situation 1 and situation 2, the result of Lemma 5.6 then follows.
Technical Lemmas and Their Proofs
We first prove the following technical lemma which is used to prove Lemma H.l
Lemma J.l. Under Assumption 3.3 at any time I, for any fixed unit vector 0 E Rd
[
T Vay 2 [AN X
Au (1 -1
-2)
20
cd
(66)
Proof. The proof of this lemma mainly follows the proof of Claim in 12]. but with more careful analysis, since their assumption is more stringent than ours.
Denote the feasible arms at round f. by A. = { [ F1,2, I.. Consider the corresponding ii.d. random variables 0, (0 x2 2- - E, x2,) |A i = 2,....., |Arl. By Assumption
3.3 0 sub- lub-Gaussian random variables with variance bounded by o², Therefore, we have that
27

---

for any > and any i E ||A
Pr(0; < -al [Ael) S e
2xd
where Pi(-)) is the shorthand for the AI,
conditional
probability
We also have that E, or.;) [AA1 E. ot, ot, [A:1] 2 Amin (Bo- (20 1) 2 A by As- sumption 3.3
With the above inequalities,
get
(0" xt,,))² 2 d all 2 (1 - - o2 2-2 2c
PA min Aeel
where the upper bound of [Ar]. Therefore, we have
E,[(0T To. 1 2 E,
min (0T x1,)) |
Y=1...., [A]
000
P
min
( D'xt;)2 x (tl))
i= Arl
x) 20
(1 - e
C dr & d
Finally, we prove the following lemma which is used in the proof of Theorem 5.3 Lemma J.2.
T
T
min (T E V2) || lirr,,.. 11 S 2d log(1 + Xd ) Vj E [m]
(67)
70+1
Proof.
det(Mv,,r) = det M Mv, V, 1fir E Vj car
det(M v2.2 -deet I I+if Vj)M,, V₁.T T- Bay T M My 11
det(M V3, 1-1)
1 I E Vj} | M
II (1+1fic E V3} [1 11 12 1=oo11
dee(MV,,nn
T
2 det
II t=
T Vi) || | lirri,.-))
(68)
Vr E [0, 1]. we have x S 2og (1 + x). Therefore
T
Σ minfIfit E V3} [.. 2 v
1 log
1 1+ Ifie E VúJ | 11 vyle-
My
T
(= To+1
2 log
II (=To+1
(1 Iiie ViJ} || M Mirien
< 2[oog(de vv,))) - log(det(AI)))
trace(AT + ΣT I(i E Vj Va)
< 2 2og
Ad
T
< 2d log(1 + Xd
(69)
28

---

K Algorithms of RSCLUMB
This section introduces the Robust Set-based Clustering of Misspecified Bandits Algorithm (RSCLUMB). Unlike RCLUMB, which maintains a graph-based clustering structure, RSCLUMB maintains set-based clustering structure. Besides, RCLUMB only splits clusters during the learning process, while RSCLUMB allows both split and merge operations. A brief illustration is that the agent will split user out of its current set(cluster) it finds an inconsistency between the user and its set, and if there are two clusters whose estimated preferences are close enough, the agent will merge them. A detailed discussion of the connection between the graph structure and the set structure can be found in [27].
Now we introduce the details RSCLUMB. The algorithm first initializes single set S1 containing all users and updates it during the learning process. The whole learning process consists of phases Line 3), where the
the beginning of each phase, the agent marks all users as "unchecked", and if a user comes later, it will be marked as "checked". If all users in a cluster are checked, then this cluster will be marked as "checked" meaning is accurate cluster in the current phase. With this mechanism, every phase the agent can put the accurate clusters aside and focus on exploring the inaccurate ones. For each cluster V,, the algorithm maintains two estimated vectors 0v, and Vy,, where the 0y, is similar to the 0r, in RCLUMB and is used for the recommendation, while the θv, is the average of all the estimated user preference vectors in this cluster and is used for the split and merge operations.
(Algo. 2
phase contains
rounds.
maintain an accuracy level, and
At time in phase s, the user i, comes with the item set D,, where T represents the index of total time steps. Then the algorithm determines the cluster and makes cluster-based recommendation. This process is similar to RCLUMB. After updating the information (Algo. 2 Line 12), the agent checks if split merge is possible (Algo. 2 1i7e
By our assumption, users in the same cluster have the same vectors. So cluster can be regarded as good cluster only when all the estimated user vectors are close to the estimated cluster vector. We call a user consistent with the cluster their estimated vectors are close enough. If user inconsistent with its current cluster, the agent will split it out. Two clusters are consistent when their estimated vectors are close, and the agent will merge them.
RSCLUMB maintains two sets of estimated cluster vectors: (i) cluster-level estimation with integrated user information, which is for recommendations (Line and Line 10 in Algo 2 (ii) the average of estimated user vectors, which is used for robust clustering (Line 3 in Algo 3 and Line in 4). The previous set-based CB work [27] only uses (i) for both recommendations and clustering, which would lead to erroneous clustering under misspecifications, and cannot get any non non-vacuous regret bound CBMUM.
L Main Theorem and Lemmas of RSCLUMB
Theorem L.1 (main result on regret bound for RSCLUMB). With the same assumptions in Theorem 5.3 the expected regret of the RSCLUMB algorithum for T rounds satisfies:
R(T) s sO(v
d
1 12
&VTT
Jelm - (5
+
logT+
+.T /md dV mT log T
md log + dv
E J
-222
1 m
X
2 (0 T + dd'mT log
(70)
Lemma L.2. For RSCLUMB, we use Ti to represent the corresponding To of RCLUMB. Then
Ti 16u 16ulog(
) 4u max
16
log(
Sd
8d
log( " 1)
22 z
228
21
Evv
22
=o(u (i
( +
log
-2
12
29

---

Algorithm 2 Robust Set-based Clustering of Misspecified Bandits Algorithm (RSCLUMB)
1: Input:
Deletion parameter a1, 02 > O. f(T) ++(((++)
I4T X,B,
2: Initialization:
Mi = Odxd: 0i = Oax Tw.0 = 0 E e
Initialize the set of cluster indexes by J = {1} and the single cluster S1 by M1 0dx
b1 = 0dx1, Ti 0, C1 = U. j(1) = 1, vi.
3: for all s = 2... do
4:
Mark every user unchecked for each cluster.
Eiev 0:
5: For each cluster 5, compute TV, = Tv, Ov, (MI + M1; Ov;
[V.
6: for all 1,
..,,' ,'' do Compute T = -
7:
Receive the user i, and the decision set D, Determine the cluster index j jii) Recommend item a, with the largest UCB index as shown in Eq. 11: Received the feedback r..
8:
9:
Update the information:
M M,,,7-1 + Ta, T.T b,., = b;,.7-1 + Ta,
Ti.- Tir,r-1 1, 0... (AI + M...r) birst
Mv,,r -V Ia, a. bv,, bv, + 1,
Tv.r TVş,T-1 + 01,, = (M + -v,,r)) -b,,,T
ΣiEV, 0,,7
0v,,- [Vg]
if i, unchecked then
14:
Run Split
15:
Mark user i, has been checked
16:
Run Merge
Algorithm Split
1: Define F(T) ++n(1177
1+T
2: if 10..r - 0v5,r
> a1 (F(T,, F(TV,.)) + aze, then
3: Split user i, from cluster Vg and form new cluster Vij of user it
Mv,,r MV,, Mi. bv, by; b,...:
Tv, Tvg, Tirs Cjt Cj.t {ir}
Myj.- M byg, binTo
Tyz.r Tin. Cg.r {ir}
Lemma L.3. For RSCLUMB, after 2T' + 1 rounds: in each phase, after the first rounds, with probability at least 56:
x (0:, 0 Ov.e-1)/
5
3c,
23
22
+ GE,
27x
1
Mu, VJ + + M. Veit-1
E. Σ
M
v..-1
1
- GeV.
3e, 22d
+ be
Vv V} Ca.t
21
27
30

---

Algorithm 4 Merge
I: for any two checked clusters vt, V22 satisfying
0 0,2
02 01 (P(TV,) F(TV,))
2 c,
2
do
2: Merge them:
Mv, = M, + M bv,, = bV,, + 2v
Tv, Tv3, + Tv,, CVn, = CV,, UC
3: Set j(i) fi, Vi E j2, delete V22
M Proof of Lemma L.3
1 (0; vv,,)) = =1xi 0v:)]l + |2/ ( vv;)
I | |0: - Ovill + 1xo (0v,. 0v:))
(71)
1 1oo (0 (v,, 0v:)
S / 2²
where the last inequality holds due to the fact For | (Ōv..) - Ov:)l:
||aa||| S and the condition of "split" and "merge".
V,,1-1 Ov.- = Σ
Na, F + x1) -1
Ta) - Ov:
-][t-1)
.E[t-1]
4eV.
GeV,
La (x T Oi, + chu + +ni)) Ov,
Σ
Da, Do. T
+ AT)-
Σ
xE[t-1]
xE|t-1|
v.V.
T.
-V.,t-1
Fa ao
M M Vet-1
Σ
Fa 1ss + M MV..-11 Σ
Da D. 0i, Ov.
T
4E|--1
1e|t-1]
-E/--11
G,V,
-Mv,t-1 Σ
Co Sa.8 a
+ M V
Σ
La, 1/4 + M Mv,c-1 Σ
Ca Fn (0:, - Ov.)
sE|--11
-ER-111
GeV,
L,V.
GeV.
My MV..-1
Σ
Lo x a, + A1)0v;
XM A...I-10v Ov. - -Ov.
se(t-1 1]
Gev,
MM Mv.1-1
Ta. Ca. + +M +Mv V
Σ
Ta, 77 + M -V
Σ
Fa. Fa, 2T, - 0v.)
sel G.T,
aclt 11 G.7,
Jcl 1 GeV,
AM
Thus, with the same method in Lemma 5.7 but replace (= 4=4c, with C1 = Gr. the previous reasoning, with probability at least - 56, we have:
1 and with
2h.
27,
T:.T ( 0v:)1 S Co, + 3e.v2d
(72)
2x
The lemma can be concluded.
31

---

N
Proof of Lemma L.2
With the analysis in the proof of Lemma H.1 with probability least 8:
[(T,,t ( 6a Tie ViEu,
0 - 0060)
S
(73)
VA+ Amin (,,))
| 0010) also satisfies this inequality. For
and the estimated error of the current cluster
set-based clustering structure, to ensure for each user there is only Ç-close cluster, we let:
B(T 9)) 6, Ti. S Y1
(74)
V Amin (1)
6
By assuming X < ( + d loog(1 + Ad
Tel) we can simplify to
2 lo ) + d dogg(1 +
Tr Ad
1 h1
6. V 2)x
)²
(75)
2i
2log( 3 which be proved by 27,
2 VVV
/ 1 )² and dlog( Txp
(
- 2x_ It's
V
2h,
obvious that the former one can be satisfied by Ti, 2
8 (l/g(1/))
As for the latter one, by
A. (
1/22x,
8dlog( A, - 1/22,)))
25 Lemma 9, we can get Ti, 1.. -c. 11/22.)
By assuming #/4
4h.2 -c. 2/
the lemma is proved.
O Proof of Theorem L.1
After 27, rounds, in each phase, at most u times split operations will happen, we use log( (T) to bound the regret generated in these rounds. Then in the remained rounds the cluster num will be no more than m. For the instantaneous regret RS at round I, with probability at least 25 for some E (0, :):
R₂ (x,;; O., E;;
(x 0t. + +eu.')
T (0., v,, + (ir; 0 Vv,--1 + Caf.t) (2 T 2 vv..v + Caii)
+ x,, (0v - -O..) Cau, - Coj. + (e -ey,")
(76)
3E, V2. 2d
$ 2C,, + + (12c,
IV, V)
x
where the last inequality holds due to the UCB arm selection strategy, the concentration bound given in Lemma L.3 and the fact that ||e**|| 0o I E..
Define such events. Let:
& (All clusters V, only contain users who satisfy |0, 16,-077 07.
+ log(1 + T;,))
+ log(1 + -TV..)
S a1
+aze,
1 Tu,
1 + Tv..
1
3e, 2d
&g (r. S 2Ca, + 2c. + 12c,
V
27x
+
A
E' ='= n
From previous analysis, we can know that ((2)) 2 35 and P(Ex) 2 1 1 25, thus PPE 2 1 1-55). By taking 8 t. we can get:
E(R,))
P(E))(E)R, + P(E)
< R1 +5
(77)
36. Vd.
2d
2T, 2c,T + (12c,)
TT 2
Ca,
32

---

Now we need to bound 2 Eir, Ca. We already know that after 27, rounds, in each phase ls after the first u thunds,there will be at most m clusters Consider phase k, for simplicity, ignore the fist rounds. For the first term in Ca.:
Th
Ta
MR
La. M
((EV.s)
|a Mr.
[=T2-1
(= (=Tx-12 1=1
m
Th
Σ
Ki
Σ
Hi V2,)
|
1 IM
Var
j=1
(=T--1
1=Ix-1
(78)
T
2T 2Tk. (l +
Ad
T
$ V 2m(Tk -T- Id-))d
Xd
For all phases:
2m((T Te)dlog(1 + Xd
S
2 Σ (Te+1 - Tm)mmllog( + Xd
k=1
k=1
k=
(79)
T
V 2md'T lTg(T) log(1 + Xd
Similarly, for the second term in Car:
me
Σ
Σ
c.
c, M
vi.
Faal
Σ
Σ
DieV
Σ
c,12% M v-ltaal
t=
t=T, 11=1
sE|t-11
GeV.
SEV.
Tx my
S 6
Σ
VieVos
Σ
x M
v To
-===1
sele V
GEV
To Σ
S6.
Σ
HiEV
Teis || 122 M
Ve,s
1=1 f=1
Tp
mh
SG
Σ
Σ
IiiEV T(iEV Σ j=1
|| [ I
1=Tx-1
1=1
Th
my
S S6 STV - -Tk-))
Tii E V.s) ||a 1
(=T
A=1
log(1 2 T
$ (T 1k-1) 2md
Xd
(80)
Then for all phases this term can be bounded by e.T 2m + 2t) Thus the total regret can be bounded by:
T
T
R₂ s
2 2mTdlog(T) log(1 + Ad (V (og((T) + dlog(1 +
222))
Xd
T
1
3c, 2d
+ 2e, log(1
+ 2e,T + 12exg
T
+
2T; + u log(()) +
Xd
27
X
where Ti 16ulog()) ) + 4u max
16 log(
Sd
8d
log 4)}
x
X25
24
33

---

RSCLUMB
RSCLUMB
Camulative Regret
RCLUMB
Cannalativ Regret
200909
RCLUMB
200933
RLinUCB-Ind
RLinUCB-Ind
SCLUB
CLUB
50933
50500
Misspecification Level
Misspecification
Known Misspecification Level
(b) Unknown Misspecification Level
Figure 2: The cumulative regret of the algorithms under different scales of misspecification level.
P More Experiments
For ablation study, we test our algorithms' performance under different scales of deviation. We test RCLUMB and RSCLUMB when e" 0.05, 0.1, 0.2, 0.3 and 0.4 in both misspecification level known and unknown cases. In the known case, we set e* according to the real misspecification level, and we compare our algorithms' performance the baselines except LinUCB and CW-OFUI. which perform worst; in the unknown case, we keep e" = 0.2,, and we compare our algorithms to RLinUCB-IIn as only it has the pre-spicified parameter e" among the baselines. The results are shown in Fig 2 We plot each algorithm's 's final cumulative regret under different misspecification levels. All the algorithms' performance get worse when the deviation gets larger, and our two algorithms always perform better than the baselines. Besides, the regrets in the unknown case are only slightly larger than the known case. These results can match our theoretical results and again show our algorithms' effectiveness, as well as verify that our algorithm handle the unknown misspecification level.
34


Reviews:
[{"review_id": "fGg8nT4Y8m", "reviewer": "Reviewer_1JFu", "summary": "This paper introduces the problem of clustering of bandits with misspecified user models (CBMUM), where the expected rewards in user models can deviate from perfect linear models. The paper presents two robust CB algorithms, RCLUMB and RSCLUMB, that aim to deal with inaccurate user preference estimations and erroneous clustering caused by model misspecifications. The regret upper bounds of the algorithms are provided under introduced assumptions, and experiments show their outperformance over previous linear bandit algorithms.", "questions": "Please refer to the weaknesses I mentioned above.", "limitations": "I'm not aware of any potential negative societal impact in the paper.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper studied a practical and important problem of clustering of bandits with misspecified user models, which is a more realistic scenario than assuming perfect linearity.\n- The theoretical analysis provides regret upper bounds for the algorithms under introduced assumptions.", "weaknesses": "- The paper's theoretical results are significantly undermined by the inclusion of impractical assumptions. The analysis relies on the existence of a pre-specified maximum misspecification level, denoted as $\\epsilon^*$, which is used as a hyper-parameter. However, in real-world scenarios, such prior knowledge is generally unavailable. Furthermore, the paper fails to offer any insights on how to determine this parameter and how it affects the model. As a result, the practical relevance and applicability of the findings are considerably weakened.\n- The motivation behind the proposed algorithm is insufficient. The paper suggests clustering bandits with misspecified user models as a solution to handle situations where the reward function does not necessarily adhere to linearity. However, it fails to discuss the extensive research conducted on non-linear bandits in recent years, as mentioned in [1,2]. Moreover, the existing work on clustering in the non-linear setting, as discussed in [3], significantly undermines the perceived contribution and novelty of this paper.\n- The experimental evaluation is limited. Only 1000 items and users are selected to perform the experiments, which is far from practical. The paper also fails to compare the proposed clustering algorithm with other recommender system algorithms [4]. Furthermore, the paper lacks an analysis of the learned clustering strategy, which could offer valuable insights into the practical pattern of clustering. Including such comparisons and analyses would enhance the overall quality and applicability of the experimental evaluation.\n\n[1] Neural Contextual Bandits with UCB-based Exploration. ICML 2020\n\n[2] Neural Thompson Sampling. ICLR 2021\n\n[3] Neural Collaborative Filtering Bandits via Meta-Learning.\n\n[4] Neural Collaborative Filtering. WWW 2017\n\n\n/****************/\n\nI couldn't include the authors in the comments below, so I've commented here. Thanks for the rebuttal. After carefully reading the points and others’ reviews, I‘m still not satisfied with the motivation, experimental evaluation, and the empirical selected misspecification level. For the motivation, the main benefit of the proposed bandit among neural bandits to handle non-linearity is efficiency. However, the efficiency of the proposed algorithm among other linear or non-linear bandits is not verified in the paper. The scalability of the used datasets is also quite small (maximum 10000 users only), which is difficult to support the claim of efficient. For the experimental evaluation, despite the dataset size, the choice to only rank a subset of items of each user is far from practical. The discussion with the recommender system literature is also insufficient as the online recommendation with the same setting are ignored. Furthermore, the significance of deriving the bound involving the term O(T) does not appear substantial. My rating will remain unchanged.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer 1JFu:\nThanks for reviewing our paper and giving some suggestions. Below are our responses.\n## 1. About the maximum misspecification level:\nAssumption 3.4 of a pre-specified max misspecification level $\\epsilon_*$ follows the standard work in MLB literature [21]. $\\epsilon_*$ can be an upper bound on the max misspecification level, not the exact maximum. In real-world applications, the deviations are usually small [13], and we can set a relatively big $\\epsilon_*$ (e.g., 0.2) to be the upper bound. Our experimental results on real-data case 2 (Lines 363-365) show that even when $\\epsilon_*$ is unknown, our algorithms still perform well by setting $\\epsilon_* = 0.2$. We have done more experiments on the Movielens data with unknown $\\epsilon_*$. The results can be found in Figure 1 in the global PDF. We can notice that if the exact maximum is unknown, we can choose some small $\\epsilon_*$, and our RCLUMB outperforms the baselines with all chosen small values of $\\epsilon_*$ on the real-world data.\n\nSome recent studies [27, 10] use model selections to deal with an unknown exact max misspecification level in the single-user case, which is not the emphasis of this work. The work [10] assumes access to a regression oracle; though the regret bound in [27] depends on the unknown exact max misspecification level, an upper bound of the exact max misspecification level is still needed. We are the first to initialize the study of the important CBMUM problem, and propose a general\nframework for dealing with misspecifications in CB. Our study is based on fundamental models on CB [11, 25] and MLB [21]; the algorithm designs and theoretical analysis are pretty general. We leave incorporating model selections to deal with unknown $\\epsilon_*$ as an interesting future work.\n\nWe have many discussions on $\\epsilon_*$ (Lines 114-118, 158-160, 341-343, 363-366, and Appendix B.2). We also provide ablation studies with respect to $\\epsilon_*$ in Appendix P.\n\n\n## 2. About the distinctions of misspecified linear bandit (MLB) from neural bandit (NB):\n\nWe agree that MLB and NB are both non-linear. However, we strongly disagree that these two lines of research are conflicted. We will cite these works, but we do not think they can undermine our contributions to any extent. Reasons are as follows.\n\nFirst, the settings are completely different. In MLB, reward models are almost linear with slight deviations. In many real-world applications, the reward models are indeed close to linearity [13, 21]. Therefore, MLB is an important and practical problem. On the other hand, NB aims to deal with situations where reward models are very complex and far from linearity. Though both are non-linear, they are two distinct research fields.\n\nSecond, we emphasize NB's computation costs are very high. Therefore, all previous works on MLB [10, 13, 21, 27] do not consider NB because they are unnecessary and computationally heavy. Also, many recent works below on MLB contradict the claim that MLB lacks sufficient motivation given NB.\n\n(1) Does Sparsity Help in Learning Misspecified Linear Bandits? ICML 2023\n\n(2) No-Regret Linear Bandits beyond Realizability. UAI 2023\n\n## 3. About the differences between [3] and ours:\nWe claim the work [3] given by the reviewer can not undermine our contributions. First, as mentioned above, the setting of [3] is very different, and our methods are far more computationally efficient in CBMUM. Second, their theory relies on an additional ``Arm Separability\" assumption on over-parameterized neural networks, which is not needed in ours. Further, their regret upper bound has a term of $\\tilde{O}(\\sqrt{uT})$, where $u$ is the number of users that can be huge, whereas the corresponding term in ours is $\\tilde{O}(\\sqrt{mT})$ ($m\\ll u$ is the number of clusters), significantly less than $\\tilde{O}(\\sqrt{uT})$. Our contributions to the theoretical analysis in CB are significant and pretty general (detailed in Appendix C), which are not covered in [3].\n\n## 4. About the experiments:\nFirst, we would like to stress our most significant contributions are theoretical analysis and algorithm designs. Second, our experimental evaluations are comparable to previous works in CB literature.\n### 4.1 Size of the dataset:\nIn CB literature, the data sizes in most works are not large and close to ours [23, 25, 26]. Following these works, we extract a proportion of the large datasets to be the data for experiments. The experiments are mainly used to verify the theoretical results. We agree performing experiments with a larger dataset would better reflect our outperformance.  We have done some experiments on an enlarged dataset extracted from Yelp (10,000 users and items). The results are shown in Figure 2 in the global PDF. Our algorithm outperforms the well-performed methods among all baselines on this larger dataset. We will conduct more experiments on larger data in a later version following your advice.\n\n\n### 4.2 About the baseline in [4]:\nThe baseline in [4] is completely an offline algorithm, lying on offline training of deep neural networks, and can not be applied in the online bandit setting. None of the previous CB works [11, 12, 23, 25, 26] compare with this baseline. We will cite it for discussions, but we respectfully disagree that including it as a baseline is necessary.\n### 4.3 About the analysis of the learned clustering strategy:\nIn Lemma H.1, we give a theoretical guarantee showing that after some iterations $T_0$, our algorithms can learn a good clustering strategy (``good partition\"). Following previous CB works [11, 12, 23, 25, 26], we do not conduct experiments on the learned clustering strategy. We agree that adding more experimental results on the clustering strategy would give a better understanding. We will consider adding them in a future version.\n\nFinally, thanks again for taking the time to review our paper. We hope our clarifications are clear and address your concerns. \n"}, {"review_id": "hYWocM4QM1", "reviewer": "Reviewer_oJ3g", "summary": "This paper proposes the clustering of bandits with misspecified user models problem. Clustering of bandits combines collaborative filtering with standard contextual bandits in order to cluster users into groups which share a common reward $\\theta$. This paper modifies the setting by allowing users to have deviation vectors $ \\epsilon^{i_t, t}$ so that the reward is $r_t = x_{a_t}^T\\theta_{i_t} + \\epsilon_{a_t}^{i_t, t} + \\eta_t$. They then propose two algorithms for this setting, prove their performance, and do experiments to show the improved results.", "questions": "1) Does $\\epsilon_{a}^{i_t, t}$ vary over time? The $t$ superscript and line 141 make it seem like it does, but it's not clear to me how the algorithm could learn a user's deviation vector which is unknown and different at each timestep. If it varies over time, how does  $\\epsilon_{a}^{i_t, t}$ differ from the noise $\\eta_t$?\n2) Why do we talk about RCLUMB and RSCLUMB?\n3) How do your algorithms compare to the baseline of just learning a reward $\\theta$ for each user separately?", "limitations": "The authors have not discussed the limitations, though they are similar to those for other bandit papers", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1) Model misspecification is a problem in online clustering bandits \n2) Experimental comparison is quite favorable towards the developed algorithms\n3) The developed algorithms have proven regret guarantees", "weaknesses": "1) ~~RSCLUMB is not well motivated~~\n2) Writing is a bit tricky to follow at times. For example, lines 309-310 are unclear to me are we moving the $\\|\\theta_{i_s} - \\theta_{i_t}\\|_2$ out and bounding it by the term on line 310? Or are we using the term from Lemma 5.7? Is the term from 5.7 substantially better?\n3) ~~The experiments are missing the baseline of learning a reward $\\theta$ for each user separately~~", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer oJ3g:\n\nThanks for reviewing our paper. Our responses are listed below.\n## A. Reponses to the weaknesses:\n### 1. About the RSCLUMB:\nIn the clustering of bandits literature, graph-based algorithms [11, 23, 26] and set-based algorithms [3, 25] are two standard approaches. Graph-based CB algorithms and set-based CB algorithms share the same order of regret upper bound, but set-based algorithms usually perform better in empirical evaluations. This is because graph-based algorithms use connected components to represent clusters. As a result, the learner may split two dissimilar users into two clusters only\nwhen it cuts every path between these two users. Even when\nthe edge between two users is\ncut, the two users might still need to stay in the same cluster\nfor a long time, making the clustering process longer than the set-based algorithms, which directly split dissimilar users into different clusters. More discussions of these two approaches can be found in [25]. Both of these two approaches are widely studied in CB literature since they share the same theoretical guarantees and similar design ideas. Therefore, to conduct systematic research on the CBMUM problem, we propose both graph-based RCLUMB and set-based RSCLUMB, showing that our ideas and techniques to deal with model misspecifications in CB are pretty general. We have some discussions on the motivation for proposing RSCLUMB in Lines 165-167 and Appendix K. We will add more discussions and illustrations following your valuable advice.\n### 2. About the writing:\nIn Lines 309-310, what we mean is that to upper bound the extra term in Line 308 (\\\\[\\left|x_a^{\\top}\\overline{M}\\_{\\overline\\{V}\\_t,t-1}^{-1}\\sum\\_{s\\in[t-1]\\atop i_s\\in \\overline{V}\\_t}x_{a_s}x_{a_s}^{\\top}(\\theta_{i_s}-\\theta\\_{i_t})\\right|\\\\]) with condition $\\left\\\\|\\theta_{\\ell}-\\theta_{i_t}\\right\\\\|\\_2\\\\leq\\zeta\\,,\\forall{\\ell\\in \\overline{V}\\_t}$, we can not trivially bound the term by \\\\[\\left|x_a^{\\top}\\overline{M}\\_{\\overline{V}\\_t,t-1}^{-1}\\sum\\_{s\\in[t-1]\\atop i_s\\in \\overline{V}\\_t}x_{a_s}x_{a_s}^{\\top}(\\theta_{i_s}-\\theta_{i_t})\\right|\\leq\\left\\\\|x_a^{\\top}\\overline{M}\\_{\\overline{V}\\_t,t-1}^{-1}\\sum\\_{s\\in[t-1]\\atop i_s\\in \\overline{V}\\_t}x_{a_s}x_{a_s}^{\\top}\\right\\\\|_2\\times \\zeta\\\\], which is wrong and we should not do that. Therefore, we prove Lemma 5.7 with subtle theoretical analysis to bound the term. We will add more explanations to make it clearer.\n### 3. About the baseline of learning a reward for each user separately:\n\nWe kindly remind you that we have compared two baselines of learning a reward for each user separately: LinUCB-Ind and RLinUCB-Ind. LinUCB-Ind is the baseline that uses LinUCB to learn a reward for each user independently, and RLinUCB-Ind is the baseline that uses the RLinUCB that is robust to model misspecifications in the single-user case to learn a reward for each user independently. Please kindly refer to Lines 319-321, Figure 1, and all the discussions of experimental results.\n\n## B. Responses to questions:\n\n### 1. About the deviation:\nWe use the t superscript to represent that the model deviations can be either time-varying or fixed; as long as the deviations are bounded, whether they are fixed or time-varying will not affect the algorithm designs and theoretical results, showing that the generalizability of our proposed methods. In misspecified linear bandits, the algorithms try to learn the $\\theta$ accurately with the existence of deviations \n instead of learning the deviation vectors [10, 13, 21, 27]. We kindly remind you that when the deviations vary with time, they are still completely different from the subgaussian noises. The reason is that the subgaussian noises must satisfy that the expectations are 0; however, the expectations of the deviations do not need to be 0, as long as they are not 0, they would make the expected reward model perturbed from linearity. The only common thing is that they can be time-varying. Hope this clarification addresses your concerns.\n\n### 2. About RCLUMB and RSCLUMB:\nPlease kindly refer to our response to the weakness above.\n\n### 3. About the baseline of learning a reward for each user separately:\nPlease kindly refer to our response to the weakness above.\n\nFinally, we thank you again for your effort in reviewing our paper and giving some comments and questions. We hope our clarifications and explanations are clear and well address your concerns."}, {"review_id": "rZVNtjHs1J", "reviewer": "Reviewer_ANNG", "summary": "This paper studies multi-agent linear bandits with cluster-structure and mis-specification. At each time, an user is chosen independently and an arm from a finite set of arms is to be recommended for this user. Subsequently, the decision maker observes a noisy and mis-specified reward. The users are assumed to have an underlying latent cluster structure with well separated clusters. \n\nThe goal of the decision maker is to minimize the total regret of all the decisions made over time. The main result of the paper is an algorithm in which the decision maker has a running estimate of the clustering of users which is used to make recommendations. The regret bound scales sub-linearly in the number of agents (which indicates the learning algorithm is able to exploit the underlying cluster structure) and optimally in the mis-specification bound. ", "questions": "Comment on the weakness in terms of knowledge of \\epsilon^* can help elucidate why the assumption is needed or is non-trivial to overcome. ", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper combines in a non-trivial manner, works on mis-specified linear bandits and clustered multi-agent bandits.\n\n2) Technically, the paper moves past a restrictive technical assumption on the distribution of the arms first adopted by Gentile at.al. and followed by all subsequent works. This is a good contribution just in the study of clustered multi-agent bandits.  ", "weaknesses": "The only weakness is that the mis-specification upper bound \\epsilon^* is both \n1. needed for the algorithm as an input, and \n2. The regret scales as this upper bound \\epsilon^* as opposed to the true unknown mis-specification upper bound of the problem. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer ANNG:\nWe are very grateful for your strongly positive comments and valuable suggestions. Below are our responses.\n## 1. About the misspecification upper bound:\nThanks for your valuable suggestions for adding more comments and discussion of the known misspecification upper bound. We will add more discussions for further improvement.\n\nThe Assumption 3.4 of a pre-specified maximum misspecification level $\\epsilon_*$ follows the standard work on misspecified linear bandits [21]. This $\\epsilon_*$ can be an upper bound on the maximum misspecification level, not the exact maximum itself. In real-world applications, the deviations are usually small [13], and we can set a relatively big $\\epsilon_*$ (e.g., 0.2) to be the upper bound. Our experimental results support this claim. As shown in our experimental results on real-data case 2 (Lines 363-365), even when $\\epsilon_*$ is unknown, our algorithms still perform well by setting $\\epsilon_* = 0.2$. We have done more experiments on the Movielens dataset with unknown $\\epsilon_*$. The results can be found in Figure 1 in the global PDF. We can clearly notice that even when the exact maximum is unknown, we can choose relatively small $\\epsilon_*$, and our proposed RCLUMB outperforms the baselines with all chosen small values of $\\epsilon_*$ in real-world applications. \n\nSome recent studies [27, 10] use model selection methods to theoretically deal with an unknown exact maximum misspecification level in the single-user case, which is not the emphasis of this work. The work [10] also assumes that the learning agent has access to a regression oracle. And for the work [27], though their regret bound depends on the exact maximum misspecification level that needs not to be known by the agent, an upper bound of the exact maximum misspecification level is still needed. We are the first to initialize the study of the important CBMUM problem, and propose a general\nframework for dealing with model misspecifications in CB problems. Our study is based on fundamental models on CB [11, 25] and MLB [21], the algorithm design ideas and theoretical analysis are pretty general. We leave incorporating their methods to deal with an unknown exact maximum misspecification level but achieve the regret upper bound depending on the exact maximum as an interesting future work.\n\nFinally, thank you again for taking time to carefully review our paper, the strong appreaciation of our work, and valuable suggestions."}, {"review_id": "yrfi5Jnvey", "reviewer": "Reviewer_ovwY", "summary": "This paper considers a new bandit problem setting, clustering of bandits with misspecified user models. Here, the misspecified user model means the expected reward does not follow a perfect linear model. Authors give a regret upper bound of $O(\\epsilon_*T\\sqrt{d\\log{T}}+d\\sqrt{T}\\log{T})$, which is basically a combination of cost from regular CB and the cost from bounded deviation, which is not surprising. And then authors also provide a \"desperate\" and linear lower bound due to the bounded deviation.", "questions": "1. Could you provide some recent literature review about CB? The most related work [25] you mentioned was published 4 years ago, and there is a huge gap.\n2. In line 123, for the matrix norm, the matrix $M$ should be PD. Otherwise, you should not call it a norm. See ref: https://en.wikipedia.org/wiki/Norm_(mathematics).\n3. Could you please improve your notations, for example, in line 131 and 132,  $j(i)$, $i$, and $\\ell$? Please check the consistency. \n4. In line 133, since it is a contextual bandit problem, can it be extend to infinite arm set?\n5. Line 146, what if the user do not come uniformly? For example, for social network, some users are heavy user, whereas some are not.\n6. Line 152, I found the assumption of the bounded misspecification is useless, because the most worse case of this misspecification is a uniform distribution. Consequently, it is sub-Gaussian, and then can be absorbed into $\\eta$. Please provide explanation. \n", "limitations": "See weakness before.", "rating": 1, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 1, "strengths": "The only strength I can find is the lower bound, which conveys the message that this problem do not have any value as it will result in a linear lower bound. If I miss anything, please notify me.", "weaknesses": "1. The presentation is poor. i) the notation system is chaotic, ii) lack of description when introducing the algorithm.\n2. Lack of novelty in problem setting and result. At least for me, this paper considers an A (CB) + B (MLB) problem, so as the result (upper bound).\n3. The proof is, as well, a simple combination of CB and MLB.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer ovwY\nThanks for reviewing our paper. Our responses are as follows.\n## Responses to strengths and weaknesses:\n### A. About the strengths and novelty of the work:\nWe strongly disagree our only strength is the lower bound and the argument that this is a trivial A (CB) + B (MLB) problem. Trivially combining previous CB and MLB works could not achieve a non-vacuous regret in the CBMUM problem. Note that in CB, misspecifications can cause erroneous clustering, which is not considered in previous MLB works. Detailed theoretical analysis of these claims is provided in Appendix D ``Discussions on why Trivially Combining Existing CB and MLB Works Could Not Achieve a Non-vacuous Regret Upper Bound\".\n\nRCLUMB introduces 3 novel components to tackle the challenges: (1) extracting 1-hop users (Line 5 in Algo.1); (2) a tolerant edge deletion rule (Line 10 in Algo.1); (3) an enlarged confidence radius (Eq.(5)). We also propose a novel set-based algorithm RSCLUMB (Algo.2). Moreover, our most significant contribution is the novel theoretical analysis with less stringent assumptions. Below are our detailed contributions.\n\n**1. New problem formulation.** We are the first to study the CBMUM problem, which is more practical by removing the perfect linearity assumption in CB.\n\n**2. Novel algorithm designs.** \nWe discuss the novelty of the above (1)-(3) key components in detail:\n\n(1) Extracting 1-hop users can avoid estimation error aggregation. Due to the estimation inaccuracy caused by deviations, users connected in the graph may not have exactly the same preferences. Following previous CB works to use connected components to form clusters would cause estimation inaccuracy aggregation in clusters. Detailed discussions are in ``Cluster Detection\" in Section 4. \n\n(2)  Without the tolerant edge deletion rule considering deviations, the algorithm would delete edges erroneously, causing inaccurate user clustering. Theoretical details are in Appendix H.\n\n(3) The UCB index in previous CB works only considers the exploration bonus and would fail to fully capture the uncertainty in CBMUM. Therefore, we design a new UCB index in Eq.(5) incorporating additional uncertainties from misspecifications. Details can be found in Lemma 5.6 and Appendix I.\n\n**3. Novel theoretical analysis (most challenging).** This is our most significant contribution. Our proof techniques are novel in CB and MLB. The main challenge of the regret analysis in CBMUM is that due to the estimation inaccuracy caused by misspecifications, it is impossible to cluster all users exactly correctly, and it is non-trivial to bound the regret caused by misclustering  $\\zeta$ -close users, whose techniques can not be found in any previous works on CB and MLB. Please refer to Appendix C ``Highlight of the Theoretical Analysis\" for details.\n\n**4. Less stringent assumption.** We move a stringent assumption on the arm distribution in all previous CB works, which is an important novel contribution to CB research. We propose a relaxed assumption (Assumption 3.3) by removing the condition that the variance must be bounded by $\\frac{\\lambda^2}{8\\log (4C)}$. Details can be found in Appendix B.1 and J.\n\n\n**5. Experimental outperformance.** Extensive experiments show superior performances of our algorithms.\n\n### B. About the lower bound:\nWe strongly disagree a linear lower bound means the problem has no value. In MLB literature, the lower bound is linear [21], but MLB is still an important hot topic (see the two recent works below), disproving the claim. \n\n(1) Does Sparsity Help in Learning Misspecified Linear Bandits? ICML 2023\n\n(2) No-Regret Linear Bandits beyond Realizability. UAI 2023\n### C. About the presentation:\nWe respectfully disagree that our presentation is poor. We have enough descriptions of our algorithm in Sections 1 and 4. We will further polish the writing in the final version.\n## Responses to the questions:\n### A. About the literature review about CB:\nWe kindly remind you that the most recent CB works we mentioned are [3] and [26] (published in 2021 and 2022). To the best of our knowledge, no CB works consider model misspecifications. We will add more related CB works in the final version following your advice.\n### B. About the matrix norm in Line 123:\nThanks for the detailed comment. We will revise it to be just a notation instead of calling it a norm.\n### C. About the notations:\nWe will check the notations. However, in Lines 131 and 132, $j(i)$ denotes the index of the ground-truth cluster of user $i$; $i$ and $l$ denote two different users; we do not think there exists any inconsistency.\n### D. About infinite arm set:\nYes, our results can be directly extended to the infinite arm set since the regret bound in Theorem 5.3 does not depend on the size of the arm set but only depends on d.\n### E. About general arrival distribution:\nPlease refer to the discussions in Lines 156-158 and Appendix B.3. The uniform arrival only affects the $T_0$ term. For any arrival distribution with $p_{min}$ the minimal arrival probability of a user, $T_0$ becomes $O(1/p_{min} \\log T)$. Since it is a lower-order term, it will not affect the main order of our regret bound. \n### F. Explanation on the difference between misspecifications and noises:\nWe disagree the assumption of the bounded misspecification is useless. This is a standard assumption in the MLB literature [10, 21, 27]. The uniform distribution is the best rather than the worst case, as it makes the expectation be 0 and can thus be absorbed into the sub-Gaussian noise, making the expected reward models perfectly linear. In general, the expectations of deviations are not 0 and can not be regarded as noises. \n\nFinally, thanks again for your effort in reviewing our paper and giving some advice. We hope our clarifications and explanations are clear and well address your concerns."}, {"review_id": "3fc0ufBshn", "reviewer": "Reviewer_AnqL", "summary": "The paper studies the contextual linear bandit setup with model misspecification in the framework of clustering bandits. This investigation revolves around a particular model misspecification framework, aiming to address the challenge posed by two independent sources of error: model misspecification and the bandit process itself. To tackle this challenge, the paper introduces two algorithms including RCLUMB and RSCLUMB. The former algorithm considers the feature similarity of users as clusters on graphs, while the latter treats it as a set. The authors establish regret upper bounds and present a corresponding lower bound to showcase the theoretical guarantees offered by both the proposed algorithms. Lastly, the paper provides empirical evaluations of the proposed algorithms by employing both synthetic and real-world data. These evaluations serve to validate and assess the effectiveness of the algorithms in practical scenarios. ", "questions": "1) Traditional notions of robustness typically involve outliers in data. In the case of the two algorithms mentioned in the paper, which include the term ``Robust'' in the titles, what is robustness tackling here? It is important to clarify what specific aspect of robustness they aim to address in this context.\n2) Is there a specific rationale for starting with a complete graph and employing successive elimination rather than an empty graph and successive addition? Intuitively, I would assume the latter approach would yield superior rewards in the initial few rounds, as it would be more focused on the data provided by the sampled arm itself. \n3) While the paper engages in a discussion regarding the selection of parameters within the range of (-0.2, 0.2), it is worth exploring other system parameters that influenced this decision-making process. Were there any additional system parameters that contributed to determining the range of parameters chosen? ", "limitations": "The paper demonstrates commendable discussions concerning the limitations of the theorem statements and assumptions. However, it would be highly beneficial to have similar discussions regarding the problem setup in relation to the existing landscape of works in the bandit domain.\nFurther, by examining the gaps or areas that have not been sufficiently addressed, and highlighting how the proposed problem formulation fills those gaps, the authors can contextualize their work and reinforce its significance. Additionally, discussing the differences or similarities between the proposed problem setup and the previous approach can contribute to a more comprehensive evaluation of the paper's novelty and the implications of its findings.\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper presents a distinctive approach by integrating two previously examined bandit setups, resulting in novel contributions in terms of problem formulation, proposed algorithm, and theoretical insights. The manuscript exhibits exemplary writing, effectively conveying the central idea. While the individual concepts of CB and MLB have been extensively studied, the combination of them as provided in the paper introduces a more practical setup, thereby amplifying the significance of the central problem. The authors of the paper explicitly state the assumptions, which either draw from previously established work or represent a milder version of the same, providing apt discussion concerning the parameters defined in the Theorem, ensuring a comprehensive understanding of their implications. To support the theoretical claims, the manuscript furnishes ample empirical evidence, underscoring the effectiveness of the proposed algorithms. ", "weaknesses": "Concerns are highlighted with the following points : \n1) Comparison between the two proposed algorithms: The main paper does mention two algorithms, but the paper seems to be lacking any discussion surrounding any theoretical comparison between the two. Can they be applied to the same problem? Scenarios to consider for highlighting the pros and cons of using one over another? Sample toy problem to support the claims? Any differences in the meta performance by using set nature over graph nature?\n2) Justification of algorithmic choices : \n i) While 1-hop clusters would provide a more close network, they will also lead to lower number of data points. How is the comparison taken into account? It is possible that the increase in data by considering a 2-hop network could be better aligned with the current user. How does the paper handle this possibility?\n ii) Line 72 -- we design a more tolerant edge design algorithm. More tolerant in comparison to?\n iii) In order to ensure the theorem statements, do the model misspecification parameter $\\epsilon^*$, noise variance $\\sigma^2$, and magnitude of the feature vector need to be in some relation? How is the paper quantifying the relationship between the three?\n3) Limitation and Failure: Would really appreciate a discussion on the limitation and failure cases of what the algorithm and problem setup is lacking and future directions of research with literature reference. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer AnqL:\nThanks for taking the time to review our paper, the positive comments, and valuable suggestions. Our responses are as follows.\n## A. Responses to the weaknesses:\n### 1. About the comparisons of our proposed algorithms:\nIn the clustering of bandits literature, graph-based algorithms [11, 23, 26] and set-based algorithms [3, 25] are two standard approaches. Graph-based CB algorithms and set-based CB algorithms share the same order of regret upper bound, but set-based algorithms usually perform better in empirical evaluations. This is because graph-based algorithms 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\nthe edge between two users is cut, the two users might still need to stay in the same cluster for a long time, making the clustering process longer than the set-based algorithms, which directly split dissimilar users into different clusters. More discussions of these two approaches can be found in [25]. Both of these two approaches are widely studied in CB literature since they share the same theoretical guarantees and similar design ideas. Therefore, to conduct systematic research on the CBMUM problem, we propose both graph-based RCLUMB and set-based RSCLUMB, showing that our ideas and techniques to deal with model misspecifications in CB are pretty general. As shown in Theorem 5.3 and Theorem L.1, both of these two proposed algorithms share the same nearly-optimal order of regret upper bounds. And in Section 6, RSCLUMB performs slightly better than RCLUMB, which is consistent with previous CB works. Both can be applied to the CBMUM problem and achieve outperformance theoretically and numerically. We will add more discussions and comparisons following your valuable advice.\n### 2. About justification of algorithm choices:\n(i) About the choice of 1-hop:\n\nThanks for this valuable comment. Theoretically, if we consider the worst-case regret upper bound, we do not need to worry that considering more hops than one hop would be better. In our work, we prove that by using this one-hop extraction, after some iterations, the algorithms can get a ``good partition\" (Definition 5.5, which means the inferred cluster contains all the users with the same preference vector and users that are $\\zeta$-close) with high probability. If we change the 1-hop to k-hop, then the second term in the regret upper bound shown in Eq.(7) will be k times worse because with k-hop, in the worst case, the algorithms might miscluster users with gaps of $k\\zeta$. We will add more illustrations and discussions on this point.\n\n(ii) About the tolerant edge design:\n\nWe mean that the edge deletion rule is more tolerant than previous CB works that do not consider model misspecifications [11, 23, 26]. We will make this clearer following your valuable advice.\n\n(iii) About the parameters:\nThese parameters need not be in some relation to ensure the theoretical results in the theorem statements. Therefore, following previous works on MLB [10, 21, 27], we do not quantify the relation between them since it will not affect the theoretical results. We will make this point clearer following your suggestion.\n\n### 3. About the limitation, failure cases, and future directions:\nThanks very much for this valuable suggestion. One failure case we would think of is when the $\\epsilon_*$ is not pre-specified, which could possibly be addressed by incorporating recent model selection methods [10, 27], but it is not the emphasis of this work as we are considering fundamental models on CB and MLB, so we rely on the typical previous assumption on MLB (Assumption 3.4). \n\nFor future directions, we have mentioned 3 interesting aspects in the Conclusion (Lines 381-385), we list them here for your convenience: (1) Prove a tighter regret lower bound for CBMUM, (2) Incorporate recent model selection methods into our fundamental framework to design robust algorithms for CBMUM with unknown exact maximum model misspecification level, and (3) Consider the setting\nwith misspecifications in the underlying user clustering structure rather than user models.\n## B. Responses to the questions:\n### 1. About the ``Robust\":\nThanks for the valuable comment. Following the first work on misspecified linear bandits [13], we use the same word ``robust\" to mean that the algorithms are robust to model misspecifications. We will clarify that following your advice.\n### 2. About starting with an empty graph:\nThanks for this valuable question. The first work on CB [12] provides a detailed discussion of why we do not start with an empty graph and successive addition. In brief, this approach would fail to achieve a good regret upper bound without the prior knowledge of the minimum gap $\\gamma$ between different clusters in Assumption 3.1. For more detailed discussions, please refer to Remark 2 of the paper [12]. We will add some discussions on this point following your advice.\n\n### 3. About the selection of parameters:\nWe select the deviations in the range of (-0.2, 0.2) in experiments is because, according to the work [13], the misspecifications from linearity are usually small, so we choose a relatively small range of deviations to test our algorithms' performance. We have also done some ablation studies on the parameter $\\epsilon_*$ in Appendix P. The results clearly show the advantages of our methods in all cases. There are not any additional system parameters that contribute to determining the range of parameters chosen.\n\nFinally, we thank the reviewer again for the positive comments, detailed review, and valuable suggestions.\n"}, {"review_id": "WI3i8PZGAE", "reviewer": "Reviewer_TDwD", "summary": "This work proposes the clustering bandit problem with misspecified reward functions. It proposes the RCLUMB and RSCLUMB algorithms and their upper bounds match the state-of-the-art ones in some degenerate cases. Numerical results are provided to evaluate the performances of proposed algorithms.\n\n\n\n==================\n\nThe score is updated to 6 after rebuttal.", "questions": "Please refer to the *Weakness* section for questions/suggestions.", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. It is good to study the 'combination' of clustering bandits and misspecified bandits, as they are both realistic topics.\n2. The paper is well organized, and contributions are mostly well described. For instance, Lemma 5.7 is highlighted as a key result to bound the regret due to misclustering users.\n3. The intuition of algorithm design of RCLUMB is in great details and easy to understand. Especially, in Section 4, the steps Cluster Detection, Cluster-based Recommendation, Update User Statistic and Update User Statistics are well explained.\n4. Section 5 presents a clear description of the analytical analysis of RCLUMB. In detail, the 'Discussion and Comparison' and proof sckech for Theorem 5.3 are easy to follow.\n5. The proposed RCLUMB algorithm is evaluated by numerical experiments in both synthetic and real data sets.", "weaknesses": "Overall, I believe this work is challenging and it provides a set of meaningful results and I still here is some possible venues for improvement:\n1. It is stated that the CB algorithms which were designed for bandits without misspecification will cause a large regret. I believe it is true with high probability and some discussion is provided in Remark 1, but it would be appreciated if an upper bound on the regret of them in bandits with misspecification can be presented in the paper.\n2. A lower bound may help us to learn whether the proposed algorithms are efficient, but is not provided in the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer TDwD:\n\nThanks very much for the positive comments for improving our work. \n## 1. About the regret upper bound of previous CB algorithms under model misspecifications:\nThanks for giving this suggestion, which would strengthen the claim of theoretical outperformance of our algorithms. We have provided some discussions on this point; please kindly refer to Lines 269-270 and Appendix D: ``Discussions on why Trivially Combining Existing CB and MLB Works Could Not Achieve a Non-vacuous Regret Upper Bound\". We also provide the discussions below.\n\nWe consider discussing regret upper bounds for CB without considering misspecifications for three cases: (1) neither the clustering process nor the decision process considers misspecifications (previous CB algorithms); (2) the decision process does not consider misspecifications; (3) the clustering process does not consider misspecifications.\n\nFor cases (1) and (2), the decision process could contribute to the leading regret. We consider the case where there are $m$ underlying clusters, with each cluster's arrival being $T/m$, and the agent knows the underlying clustering structure. For this case, there exist some instances where the regret upper bound $R(T)$ is strictly larger than $\\epsilon_{*}T\\sqrt{m\\log T}$ asymptotically in $T$. Formally, in the discussion of ``Failure of unmodified algorithm\" in Appendix E in [21],\n they give an example to show that in the single-user case, the regret $R_1(T)$ of the classic linear bandit algorithms without considering misspecifications will have: $\\displaystyle\\lim_{T \\rightarrow + \\infty}\\frac{R_1(T)}{\\epsilon_*T\\sqrt{m\\log T}}=+ \\infty$. In our problem with multiple users and $m$ underlying clusters, even if we know the underlying clustering structure and keep $m$ independent linear bandit algorithms with $T_i$ for the cluster $i \\in [m]$ to leverage the common information of clusters, the best we can get is $R_2(T)=\\sum_{i \\in [m]}R_1(T_i)$. By the above results, if the decision process does not consider misspecifications, we have $\\displaystyle\\lim_{T \\rightarrow + \\infty}\\frac{R_2(T)}{\\epsilon_*T\\sqrt{m\\log T}}=\\displaystyle\\lim_{T \\rightarrow + \\infty}\\frac{mR_1(T/m)}{\\epsilon_*T\\sqrt{m\\log T}}=+ \\infty$. Recall that the regret upper bound $R(T)$ of our proposed algorithms is of $O(\\epsilon_*T\\sqrt{md\\log T}  + d\\sqrt{mT}\\log T)$ (thus, we have $\\displaystyle\\lim_{T \\rightarrow + \\infty}\\frac{R(T)}{\\epsilon_*T\\sqrt{m\\log T}}<+ \\infty$), which gives a proof that that the regret upper bound of our proposed algorithms is asymptotically much better than CB algorithms in cases (1)(2).\n\nFor case (3), if the clustering process does not use the more tolerant deletion rule in Line 10\n of Algo.1, the gap between users linked by edges would possibly exceed $\\\\zeta$ ($\n\\zeta = 2\\epsilon_{*} \\sqrt{\\frac{2}{\\tilde{\\lambda}\\_{x}}}$) even after $T_0$, which will result in a regret upper bound no better than $O(\\epsilon_*u\\sqrt{d}T)$. As the number of users $u$ is usually huge in practice, this result is vacuous. The reasons for getting the above claim are as follows. Even if the clustering process further uses our deletion rule considering misspecifications, and the users linked by edges are within $\\zeta$ distance, failing to extract $1$-hop users (Line 5 in Algo.1) would cause the leading $O(\\epsilon_*u\\sqrt{d}T)$ regret term, as in the worst case, the preference vector $\\theta$ of the user in $\\tilde{V}\\_t$ who is $h$-hop away from user $i_t$ could deviate by $h\\zeta$ from $\\theta_{i_t}$, where $h$ can be as large as $u$, and it would make the second term in Eq.(8) a $O(\\epsilon_*u\\sqrt{d}T)$ term. If we completely do not consider the misspecifications in the clustering process, the above user gap between users linked by edges would possibly exceed $\\zeta$, which will cause a regret upper bound worse than $O(\\epsilon_*u\\sqrt{d}T)$.\n\n## 2. About the lower bound:\n\nWe also think a lower bound could help us to learn whether the proposed algorithms are efficient. Therefore, we have provided a lower bound for the CBMUM problem in Theorem 5.4, and we have made some discussions on the optimality of our regret upper bounds. Please kindly refer to Lines 255-262 and Appendix F ``Proof and Discussions of Theorem 5.4\" for detailed discussions and proofs of the lower bound. We also list Theorem 5.4, the proof, and the discussions below. \n\n \n**Theorem 5.4** There exists a problem instance for the CBMUM problem such that for any algorithm $R(T)\\geq \\Omega(\\epsilon\\_*T\\sqrt{d})\\,.$\n\n**Proof and discussions**\n\nIn the work [21], they give a lower bound for misspecified linear bandits with a single user. The lower bound of $R(T)$ is given by:\n$R_3(T)\\geq \\epsilon\\_* T\\sqrt{d}$. Therefore, suppose our problem with multiple users and $m$ underlying clusters where the arrival times are $T_i$ for each cluster, then for any algorithms, even if they know the underlying clustering structure and keep $m$ independent linear bandit algorithms to leverage the common information of clusters, the best they can get is $R(T)=\\sum_{i \\in [m]}R_3(T_i)\\geq \\epsilon_*\\sum_{i \\in [m]}T_i\\sqrt{d}=\\epsilon_*T\\sqrt{d}$, which gives a lower bound of $O(\\epsilon_*T\\sqrt{d})$ for the CBMUM problem. Recall that the regret upper bound of our algorithms is of $O(\\epsilon_*T\\sqrt{md\\log T}  + d\\sqrt{mT}\\log T)$, asymptotically matching this lower bound with respect to $T$ up to logarithmic factors and with respect to $m$ up to $O(\\sqrt{m})$ factors, showing the tightness of our theoretical results (where \n $m$ are typically very small for real applications).\n \n We conjecture that the gap for the $m$ factor is due to the strong assumption that cluster structures are known to prove our lower bound, and whether there exists a tighter lower bound will be left for future work.\n\n Finally, we thank you again for taking the time to review our paper, the strongly positive feedback, and the valuable suggestions for further improvements."}]

Author rebuttal:
We appreciate all reviewers' effort in reviewing our paper and giving some comments and questions. We have done some experiments for your reference, please refer to the global pdf.

Meta-review: Based on the discussions, the reviewers acknowledged that the main strengths were:

- The paper relaxes some assumption in prior Cluster of Bandits works
- The combination of techniques for Cluster of Bandits and Misspecified Linear Bandits is nontrivial
- A lower bound is given

The main remaining concerns were:
- Motivation: why considering using misspecified linear bandits instead of nonlinear bandits
- Dataset size in evaluation: experiments with 10000 users may not be large-scale enough
- Algorithm needs to know upper bound of misspecification level

Reviewers ovwY and 1JFu had some concerns on the O(T) term in the regret bound. However, from the AC (and Reviewer ANNG's) point of view, a $\epsilon \sqrt{d} T$-like term in the regret bound is totally expected in misspecified linear bandits. First, it is a standard term that appears in single-task misspecified linear bandit settings; second, such bound is meaningful: it can be significantly smaller than the trivial bound of O(R T), where R is the range of the expected reward. 

Given the overall feedback from the reviewers, it seems that the main strengths outweigh the concerns.
Decision: Accept (poster)