Online Corrupted User Detection and Regret Minimization
Authors: Zhiyong Wang
Jize Xie
Tong Yu
Shuai Li
John C.S. Lui
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning
online corrupted user detection
clustering of bandits

Abstract: In real-world online web systems, multiple users usually arrive sequentially into the system. For applications like click fraud and fake reviews, some users can maliciously perform corrupted (disrupted) behaviors to trick the system. Therefore, it is crucial to design efficient online learning algorithms to robustly learn from potentially corrupted user behaviors and accurately identify the corrupted users in an online manner.  Existing works propose bandit algorithms robust to adversarial corruption. However, these algorithms are designed for a single user, and cannot leverage the implicit social relations among multiple users for more efficient learning. Moreover, none of them consider how to detect corrupted users online in the multiple-user scenario. In this paper, we present an important online learning problem named LOCUD to learn and utilize unknown user relations from disrupted behaviors to speed up learning, and identify the corrupted users in an online setting. To robustly learn and utilize the unknown relations among potentially corrupted users, we propose a novel bandit algorithm RCLUB-WCU. To detect the corrupted users, we devise a novel online detection algorithm OCCUD based on RCLUB-WCU's inferred user relations. We prove a regret upper bound for RCLUB-WCU, which asymptotically matches the lower bound with respect to $T$ up to logarithmic factors, and matches the state-of-the-art results in degenerate cases. We also give a theoretical guarantee for the detection accuracy of OCCUD. With extensive experiments, our methods achieve superior performance over previous bandit algorithms and high corrupted user detection accuracy.

Online Corrupted User Detection and Regret Minimization
Zhiyong Wang The Chinese University of Hong Kong 2ywang210cse cuhk, edu.hk
Jize Xie
Shanghai Jiao Tong University xjzzjlesj tu. edu. en
Tong Yu
Shuai Li
Adobe Research
Shanghai Jiao Tong University shuaili80a jt euu.ju...uu.ueeu.ee..ee....e edu. cn
worktongyu@gmail.com
John C.S. Lui
The Chinese University of Hong Kong cslui@cse. cuhk, edu.hk
Abstract
In real-world online web systems, multiple users usually arrive sequentially into the system. For applications like click fraud and fake reviews, some users maliciously perform corrupted (disrupted) behaviors to trick the system. There- fore, it is crucial design efficient online learning algorithms robustly learn from potentially corrupted user behaviors and accurately identify the corrupted users in an online manner. Existing works propose bandit algorithms robust adversarial corruption. However, these algorithms are designed for single user, and cannot leverage the implicit social relations among multiple users for more efficient learning. Moreover, none of them consider how to detect corrupted users online the multiple-user scenario. this paper, we present an important on- line learning problem named LOCUD to learn and utilize unknown user relations from disrupted behaviors to speed up learning, and identify the corrupted users online setting. To robustly learn and utilize the unknown relations among po- tentially corrupted users, we propose a novel bandit algorithm RCLUB-W- WCU. To detect the corrupted users, we devise novel online detection algorithm OCCUD based on ACLUB-WCUT inferred user relations. We prove a regret upper bound for CCLUB-WCLL which asymptotically matches the lower bound with respect to T up to logarithmic factors, and matches the state-of-thed ooee-----hh-rrr art results in degen- erate cases. We also give theoretical guarantee for the detection accuracy of OCCUD. With extensive experiments, our methods achieve superior performance over previous bandit algorithms and high corrupted detection accuracy.
Introduction
In real-world online recommender systems, data from many users arrive in a streaming fashion 4
15 7 35
27 26]. There may exist some corrupted (malicious) users, whose behaviors (e.g., click,
rating) can be adversarially corrupted (disrupted) over time to fool the system 22
30
12
10]
9
These corrupted behaviors could disrupt the user preference estimations of the algorithm. As result, the system would easily be misled and make sub-optimal recommendations [4] 23
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

which would hurt the user experience. Therefore, it is essential to design efficient online learning algorithms to robustly learn from potentially disrupted behaviors and detect corrupted users in an online manner.
16] However, they have the following limitations. First, existing algorithms are initially designed for robust online preference learning of a single user. In real-world scenarios with multiple users, they cannot robustly infer and utilize the implicit user relations for more efficient learning. Second, none of them consider how to identify corrupted users online in the multiple user scenario. Though there also exist some works on corrupted user detection [34 39 28 [31, they all focus on detection with known user information in an offline setting, thus can not be applied to do online detection from bandit feedback.
There exist some works on bandits with adversarial comuppiion 29
To address these limitations, we propose a novel bandit problem "Learning and Online Corrupted Users Detection from bandit feedback" (LOCUD). To model and utilize the relations among users, we assume there is an unknown clustering structure over users, where users with similar preferences lie in the same cluster 8 19 21). The agent can infer the clustering structure to leverage the information of similar users for better recommendations. Among these users, there exists a small fraction of corrupted users. They can occasionally perform corrupted behaviors fool the agent [22 29 30 9 while mimicking the behaviors of normal users most of the time to make themselves hard to discover. The agent not only needs learn the unknown user preferences and relations robustly from potentially disrupted feedback, balance the
exploitation trade-off to maximize the cumulative reward, but also needs to detect the corrupted users online from bandit feedback.
The LOCUD problem is very challenging. First, the corrupted behaviors would cause inaccurate user preference estimations, which could lead to erroneous user relation inference and sub-optimal recommendations. Second, it is nontrivial to detect corrupted users online since their behaviors are dynamic over time (sometimes regular while sometimes corrupted), whereas, in the offline set- ting, corrupted users' information can be fully represented by static embeddings and the existing can typically do binary classifications offline, which are not adaptive over time.
approaches 18 32
We propose a novel learning framework composed of two algorithms to address these challenges.
RCLUB-WCU. To robustly estimate user preferences, learn the unknown relations from potentially corrupted behaviors, and perform high-quality recommendations, we propose a novel bandit algo- rithm "Robust CLUstering of Bandits With Corrupted Users" (RCLUB-WCU)) which maintains a dynamic graph over users to represent the learned clustering structure, where users linked by edges are inferred to be in the same cluster. RCLUB-WCL WCU adaptively deletes edges and recommends arms based on aggregated interactive information in clusters. We do the following to ensure robust clustering structure learning. (i) To relieve the estimation inaccuracy caused by disrupted behaviors, we use weighted ridge regressions for robust user preference estimations. Specifically, we use the inverse of the confidence radius to weigh each sample. If the confidence radius associated with user le and arm a, is large at t, the learner is quite uncertain about the estimation of i 's preference on a, indicating the sample at t is likely to be corrupted. Therefore, we use the inverse of the confi- dence radius to assign minor importance to the possibly disrupted samples when doing estimations. (ii) We design robust edge deletion rule to divide the clusters by considering the potential effect of corruptions, which, together with (i), can ensure that after some interactions, users in the same connected component of the graph are in the same underlying cluster with high probability.
OCCUD. To detect corrupted users online, based on the learned clustering structure of RCLUB- WCU, we devise novel algorithm named "Online Cluster-based Corrupted User Detection" (OC- CUD). At each round, we compare each user's 's non-robustly estimated preference vector (by ridge regression) and the robust estimation (by weighted regression) of the user's inferred cluster. If the gap exceeds a carcfully-dcsignee follows. With misleading behaviors, the non-robust preference estimations of corrupted users would be far from ground truths. On the other hand, with the accurate clustering of RCLUB- WCU, the ro- bust estimations of users' inferred clusters should be close ground truths. Therefore, for corrupted users, their non-robust estimates should be far from the robust estimates of their inferred clusters.
threshold, we detect this user as corrupted. The intuitions are as
We summarize our contributions follows.
We present a novel online learning problem LOCUD, where the agent needs to (i) robustly learn and leverage the unknown user relations to improve online recommendation qualities under the disruption of corrupted user behaviors; (ii) detect the corrupted users online from bandit feedback.
2

---

We propose a novel online learning framework composed of two algorithms, RCLUB- ACLUB-WCU and OCCUD, tackle the challenging LOCUD problem. RCLUB-W WCC robustly learns and utilizes the unknown social relations among potentially corrupted users to efficiently minimize regret. Based on RCLUB-WCU's inferred user relations, OCCUD accurately detects corrupted users online.
We prove regret upper bound for RCLUB-W -CCU which matches the lower bound asymptotically in T' up to logarithmic factors and matches the state-of-the-art results in several degenerate cases. We also give theoretical performance guarantee for the online detection algorithm OCCUD. Experiments on both synthetic and real-world data clearly show the advantages of our methods.
2 Related Work
Our work is related to bandits with adversarial corruption and bandits leveraging user relations.
The work [29] first studies stochastic bandits with adversarial corruption, where the rewards are corrupted with the sum of corruption magnitudes in all rounds constrained by the corruption level C. They propose robust diminatiion-bssen algorithm. The paper [9] proposes an improved algorithm with a tighter regret bound. The paper [22) first studies stochastic linear bandits with adversarial corruptions. To tackle the contextual linear bandit setting where the arm set changes over time, the work [5] proposes a variant of the OFUL [ that achieves a sub-linear regret. A recent work [12] proposes the CW-OFUL algorithm that achieves a nearly optimal regret bound. All these works focus on designing robust bandit algorithms for a single user; none consider how to robustly learn and leverage the implicit relations among potentially corrupted users for more efficient learning- Moreover, none of them consider how online detect corrupted users in the multiple-user case.
Some works study how to leverage user relations to accelerate the bandit learning process in the multiple-user case. The work (38) utilizes a known user adjacency graph to share context and payoffs among neighbors. To adaptively learn and utilize unknown user relations, the paper g proposes the
clustering of bandits (CB) problem where there is an unknown user clustering structure to be learned by the agent. The work (20] uses collaborative effects on items guide the clustering of users. The paper [19] studies the CB problem in the cascading bandit setting. The work [2]] considers the setting where users in the same cluster share both the same preference and the same arrival rate. The paper (2 studies the federated CB problem, considering privacy and communication issues. All these works only consider utilizing the relations among normal users; none of them consider how to robustly learn the user relations from potentially disrupted behaviors, thus would easily be misled by corrupted users. Also, none of them consider how to detect corrupted users from bandit feedback.
To the best of our knowledge, this is the first work to study the problem to (i) learn the unknown user relations and preferences from potentially corrupted feedback, and leverage the learned relations to speed up learning; (ii) adaptively detect the corrupted users online from bandit feedback.
3 Problem Setup
This section formulates the problem of "Learning and Online Corrupted Users Detection ban- dit feedback" (LOCUDD (illustrated in Fig We denote ||=:|| M = Vx Mæ. [m] {1,..., m). number of elements in set A as [A].
In LOCUD, there are users, which we denote by set U (1, u}. Some of them are corrupted users, denoted by set ú C U. These corrupted users, on the one hand, try to mimic normal users to make themselves hard to detect; on the other hand, they can occasionally perform corrupted behaviors to fool the agent into making sub-optimal decisions. Each user i E U, no matter normal one or corrupted one, is associated with a (possibly mimicked for corrupted users) preference feature vector 0, E IRd that is unknown and ||0.||2 S 1. There an underlying clustering structure among all the users representing the similarity of their preferences, but it is unknown to the agent and needs to be learned via interactions. Specifically, the set of users '/ can be partitioned into (m < u) clusters, Vi, 12.... V.. where UjE[m] V2- U, and VG, n Vy = 0, for j / j'. Users in the same cluster have the same preference feature vector, while users in different clusters have different preference vectors. We use 0 denote the common preference vector shared by users in the j-th cluster Vj, and use j(i to denote the index of cluster user belongs to (i.e., i E V((g). For
3

---

any two users k, i U, if E Vi( then 0₁ = 62 = 0, otherwise 02 + 0g. We assume the arm
set A C Rd is finite. Each arm A associated with a feature vector & Rd with || S 1.
The learning process of the agent as fol- lows. At each round t E [T), a user & E U comes to be served, and the learn- ing agent receives a set of arms A, C A to choose from. The agent infers the cluster V that user is belongs to based on the in- teraction history, and recommends an arm a, E A according to the aggregated in- formation gathered in the cluster V., After receiving the recommended arm a, nor- mal user be will give a random reward with expectation x,, ir to the agent.
L1
t2 E3
Figure Illustration of LOCUD. The unknown user relations are represented by dotted circles, e.g. user 3, have similar preferences and thus can be in the same user segment (i.e., cluster). Users 6 and 8 are corrupted users with dynamic behaviors over time (e.g.. for user 8, the behaviors are normal at t and i3 (blue), but are adversarially corrupted at l2 and l4 (29 [2), making them hard be detected online. The agent needs to learn user relations to utilize information among similar users speed up learning, and detect corrupted users online from bandit feedback.
To model the behaviors of corrupted users, following [29] 9 5 [2], we assume that they can occasionally corrupt the rewards to mislead the agent into recommending sub-optimal arms. Specifically, at each round f, if the current served user is cor- rupted user (i.e., d E (T, the user can cor- rupt the reward by Gt- In summary, model the reward received by the agent at round as
= 2. 2r 0., + T)c + Cr: where c = 0 if i, is a normal user, (i.e., it & (i), and is Suu--aassia random noise.
As the number of corrupted users is usually small, and they only corrupt the rewards occasionally with small magnitudes to make themselves hard to detect, we assume the sum of corruption magni- tudes in all rounds is upper bounded by the corruption level C, i.e., Σ |cel S C 29
5 12
We assume the clusters, users, and items satisfy the following assumptions. Note that all these assumptions basically follow the settings from classical works on clustering of bandits 8 19 25 36).
Assumption (Gap between different clusters). The gap between any two preference vectors for different clusters is at least unknown positive constant 7
00 03 2 > Vj.j' E [m],j
Assumption 2 (Uniform arrival of users). Ar each round t, user in comes uniformly at random from U with probability 1/u, independent of the past rounds. Assumption (Item regularity). At each round t, the feature vector D. of each arm a E A, is drawn independently from a fixed unknown distribution p over (æ E Rdd || 1}, where En- (axee 1 minimal eigenvalue X > At for any fixed unit vector z E Rdd (0 2)² has sub-Gaussian tail with variance greater than o².
Let of E arg max 2. 0,, denote optimal arm with the highest expected reward at round One objective of the learning agent to minimize the expected cumulative regret
R(T)= E (z x 0..).
Another objective is to detect corrupted users online accurately. Specifically, at round the agent will give of users Uhe the detected corrupted users, and we want Ut to be close to the ground-truth set of corrupted users li possible.
4 Algorithms
This section introduces our algorithms RCLUB-WCU (Algo and OCCUD (Algo RCLUB- WCU robustly learns the unknown user clustering structure and preferences from corrupted feed-

---

back, and leverages the cluster- based information to accelerate learning, Based on the clustering structure learned by RCLUB-WCOO WCC, OCCUD can accurately detect corrupted users online.
Algorithm 1 RCCUB-WCCU
I: Input: Regularization parameter X, confidence radius parameter B, threshold parameter a, edge deletion parameter 01, f(T) = v(++ In ()))((1+7))
2: Initialization: M = Oaxd. b,, = 0ax1, M = Oaxd, 6 = Oax1, T,, 0, Vi Vieu;
complete graph Gg (L, Ea) over 24
3: for all 1, 2,............. ,,, T do
4: Receive the index of the current served user in E Ut get the feasible arm set at this round Ar.
5: Determine the connected components in the current maintained graph Gt-1 (41 Ex-1
such that 4 C V..
6: Calculate the robustly estimated statistics for the cluster Vi:
Mv, = AI + Eiev, M i bv, = Eisv, b vv..vvv. = b Select an arm a with largest UCB index Eq. [3] and receive the corresponding reward ry
8: Update the statistics for robust estimation of user te:
M G. M t, 1 + Wi,t Fa, V. b b,,
at 17: Th,, Ti,
M = AI + M 0.,, M
a b,., Wi., min(1, ///a/////aall M
9: Keep robust estimation statistics of other users unchanged:
M = M br, , = Tr,-1, Oz, = 0 for EU, # i6
10: Delete the edge (fe. f) C 1,
| 02.11 2 an ((t,
and get updated graph G. (4, F));
11: Use the OCCUD Algorithm (Algo detect the corrupted users.
12:
end for
4.1 RCLUB-WCU
The corrupted behaviors may cause inaccurate preference estimations, leading to erroneous relation inference and sub-optimal decisions. In this case, how to learn and utilize unknown user relations to accelerate learning becomes non-trivial. Motivated by this, we design RCLUB- WCU as follows.
Assign the inferred cluster V/2 for user it. RCLUB-WCU maintains a dynamic undirected graph G, (21 E.) over users, which is initialized to be a complete graph (Algo Line 2). Users with similar learned preferences will be connected with edges in E,. The connected components in the graph represent the inferred clusters by the algorithm. a feasible arm set A, for the agent to choose from (Line 4.. In Line [S] RCLUB- WCU detects the connected component VA the graph containing user i, to be the current inferred cluster for it.
round t, user in comes be served with
Robust preference estimation of cluster V.. After determining the cluster V,, RCLUB-WCU esti- mates the common preferences for users in V,, using the historical feedback of all users in V, and rec- ommends an arm accordingly. The corrupted behaviors could cause inaccurate preference estimates, which can easily mislead the agent. To address this, inspired by 440 12), we use weighted ridge re- gression to make corruption-robust estimations. Specifically, RCLUB-WCC robustly estimates the common preference vector of cluster V, by solving the following weighted ridge regression
i Ov = arg min Eeeu-1 Wi,,o(rs DERd
TT 0) + X 10112
1.EV,
where À > 0 is regularization coefficient. Its closed-form solution is Ov. M M 1 Σ
where M V2 = AI Σ Ta, IT,, bv.,t1 sev,
se((-1) Wi. Ta.- isV
We set the weight of sample for user i, Ve at round s as Wi,.s = min (in((1ar/ aaaaaal/,,,,, [| (la.: where is coefficient to be determined later. The intuitions of designing these weights The term || al is the confidence radius of arm a, for user i, at s, reflecting how confident the algorithm is about the estimation of i,'s preference on ag at s. If ||æ M is large, means the agent is uncertain of user i, 's preference on 0g, indicating this sample is probably corrupted.
follows.
5

---

whether the inferred i, 's preference similarities with other users are still true, and updates the graph accordingly. Precisely, if gap between the updated estimation i,,, of in and the estimation θz, of user exceeds a threshold in Line 10, RCLUB-WCU will delete the edge (te, E) in G--1 to split them Therefore, we use the inverse of confidence radius to assign small weight to this round's sample if it is potentially corrupted. In this way, uncertain information for users cluster V,, is assigned with less importance when estimating the Vi's preference vector, which could help relieve the estimation inaceuracy caused by corruption. For technical details, please refer to Section 5.1 and Appendix.
Recommend (r with estimated preference of cluster V₁, Based on the corruption-robust pref- erence estimation 0v,,81 of cluster Ví. in Line 7 the agent recommends an arm using the upper confidence bound (UCB) strategy to balance exploration and exploitation
02 argmax Fi Ov, +
|| M - Ra,t + Capt.
where 3 VX+ ( + d'log(1 + xx)+ the confidence radius parameter, Ra, denotes the estimated reward of arm at t, Co.t denotes the confidence radius of arm at t. The design of Ca, theoretically relies on Lemma 2 that will be given in Section 5
Update the robust estimation of user it. After receiving Tt, the algorithm updates the estimation statistics of user 4, while keeping the statistics of others unchanged @nd Linel). Specifically, RCLUB-WE CCUUU-CCUUATE estimates the preference vector of user é, by solving a weighted ridge regression
Oigt = arg min E AEl Wi, Wi,,a(rs xT 0)² + +111012 OERd
(4)
with closed-form solution 0 in
(AI (M ( by.:: where M 1,, M
Σ 20 Wi..s Do Fa, t,
b E xEle) ai, and design the weights in the same way by the same reasoning. fomit Update the dynamic graph. Finally, with the updated statistics of user is RCLUB-WCU checks
Algorithm 2 OCCUD (At round f, used in Line 11 in Algo
1: Initialize i4 6: input probability parameter 5.
Update the statisties for non-robust estimation user i
M i..t M i Fa .. bi., b rz O,,tt (AI M
3: Keep non-robust estimation statistics of other users unchanged
M r. = M br. b dr, = O for all & U, ( it.
4: for all connected component Vi++ C C. do
5: Calculate the robust estimation statistics for the cluster Vy.::
M Mv AI +EEv, M TV, = Eiev, Te,
bv Elev, be.,, 1k.,Ov, V.,,,. M Vy bV
6: for all user E Vi. do
7:
Detect user to be corrupted user and add user to the set Ud, if the following holds:
V dlog(1 + Faf + 2 (og + v Velog(1 + Tree') + 21og()) + v + aC
00.. - @n.nell
V Amiin (M,,) +
Auial (M v....))
(5)
where Amin() denotes the minimum eigenvalue of the matrix argument.
8: end for
9: end for
apart. The threshold is carefully designed to handle the estimation uncertainty from both stochastic noises and potential corruptions. The updated graph G. = (U, Fi.) will be used in the next round.
4.2 OCCUD
Based on the inferred clustering structure of RCLUB-WCU, we devise a novel online detection algorithm OCCUD (A. The design ideas and process of OCCUD follows.

---

Besides the robust preference estimations (with weighted regression) of users and clusters kept by RCLUB-WCU, OCCUD also maintains the non-robust estimations for each user by online ridge regression without weights (Line and Line 3 Specifically, at round 1, OCCUD updates the non- robust estimation of user it by solving the following online ridge regression:
0 i arg min Σ
sclt (rs F fam
2,, 0) A 1111
OER
with solution 0i,,= (AI + M bi.., where Mi,t = Σ xelt] Bay Ba, big.t = Σ xE|t] Ta, Ba,
With the robust and non-robust preference estimations, OCCUD does the following to detect cor- rupted users based on the clustering structure inferred by RCLUB- -CCU First, OCCUD finds the connected components in the graph kept by ACLUB-WCLL which represent the inferred clusters. Then, for each inferred cluster V E G,: (1) OCCUD computes its robustly estimated preferences vector Óv.... (Line 5). (2) For each user whose inferred cluster is Vj (i.e., V2,t), OCCUD computes the gap between user i's non-robustly estimated preference vector 0i,, and the robust es- timation Ōv.... for user i's inferred cluster Vj,r- If the gap exceeds a carefully-designed threshold, OCCUD will detect user as corrupted and add i the detected corrupted user set Ue (Line 7
(a) RCLUB-WCU
OCCUD
Figure 2: Algorithm illustrations. Users 6 and 8 are corrupted users (orange), and the others are normal (green). (a) illustrates RCLUB-WCC WCU, which starts with complete user graph, and adap- tively deletes edges between users (dashed lines) with dissimilar robustly learned preferences. The corrupted behaviors of users 6 and 8 may cause inaccurate preference estimations, lcading to erro- neous relation inference. In this case, how to delete edges correctly is non-trivial, and CILLUB--CU addresses this challenge (detailed in Section I.T.. (b) illustrates OCCUD at some round f, where per- son icons with triangle hats represent the non-robust user preference estimations. The gap between the non-robust estimation of user and the robust estimation of user 6's inferred cluster (circle C1) exceeds the threshold no at this round (Line in Algo 2 so OCCUD detects user to be corrupted.
The intuitions of OCCUD are as follows. On the one hand, after some interactions, RCLUB-WCU will infer the user clustering structure accurately. Thus, at round t, the robust estimation Ov.,.. for user i's inferred cluster should be pretty close to user i's ground-trutte truth preference vector 0, On the other hand, since the feedback of normal users are always regular, at round f, if user is normal user, the non-robust estimation oz., should also be close to the ground-truth 0,- However, the non- robust estimation of a corrupted user should be quite far from the ground truth due to corruptions. Based on this reasoning, OCCUD compares each user's non-robust estimation and the robust esti- mation of the user's inferred cluster to detect the corrupted users. For technical details, please refer to Section 5.2 and Appendix. Simple illustrations of our proposed algorithms can be found in Fig
5 Theoretical Analysis
In this section, we theoretically analyze the performances of our proposed algorithms, RCLUB- WCU and OCCUD. Due to the page limit, we put the proofs in the Appendix.
5.1 Regret Analysis of RCLUB-WCU
This section gives an upper bound of the expected regret (defined in Eq. for RCLUB-WCU.
The following lemma provides a sufficient time (5))), after which RCLUB- WCU can cluster all the users correctly with high probability.
7

---

Lemma 1. With probability at least 1 - 36, RCLUB-WCU will cluster all the users correctly after
To(o) A 16u loglog( ( Au max
288d
log(
U,
logi
Sd
72V
T2aC²
?2a/Ado
8
2 an
for some 8 E (0, 3),, where d a 1o (1-(111 the
212
dr,
A
K, v (T).
After (d), the following lemma gives a bound of the gap between v and the ground-truth 0, direction of action vector za for RCLUB-WCU, which supports the design in (3).
Lemma 2. With probability at least - 46 for some & (0, 2)) Vt 2 To(o), we have:
F (O 0..)) s 1B11aaallM A Ca,t-
With Lemma| 1 and 2 we prove the following theorem on the regret upper bound of RCLUB-WCE -CCU Theorem 3 (Regret Upper Bound of RCLUB-WCU), With the assumptions in Section 3 and picking vdtvA, the expected regret of the RCLUB- BCCUB-WCU algorithm for T rounds satisfies
R(T) S O(( CVa 72
1 X3
]olo((() O(dv OmmCdlo''
(7)
Discussion and Comparison. The regret bound in Eq. has three terms. The first term is the time needed to get enough information for accurate robust estimations such that RCLUB-WE WCCU could cluster all users correctly afterward with high probability. This term is related to the corruption level C. which is inevitable since, there are more corrupted user feedback, it will be harder for the algorithm to learn the clustering structure correctly. The last terms correspond to the regret after To with the correct clustering. Specifically, the second term is caused by stochastic noises when leveraging the aggregated information within clusters to make recommendations; the third term associated with the corruption level C is the regret caused by the disruption of corrupted behaviors.
When the corruption level C' is unknown, we can use its estimated upper bound Ô - /T to replace C' in the algorithm. In this way, if C < Ć, the bound will be replacing C with Ô in Eq. 7 when C> VT, R(T) = OT),, which is already optimal for a large class of bandit algorithms
The following theorem gives a regret lower bound of the LOCUD problem.
Theorem 4 (Regret lower bound for LOCUD). There exists a problem instance for the LOCUD problem such that for any algorithm
R(T) 2 Q(d dC).
Its proof and discussions can be found Appendix D The upper bound in Theorem Jayomomtaaymptooiicalll matches this lower bound in T up to logarithmic factors, showing regret bound is nearly optimal.
We then compare our regret upper bound with several degenerated cases. First, when C i.e., all users are normal, our setting degenerates to the classic CB problem (8] In this case the bound in Theorem becomes O(1 u log((T) + fold///loog"" (T)). perfectly matching the state-of- the-art results in CB
i.e., there is only one user, our setting degenerates to linear bandits with adversarial corruptions (22 [2], and the bound in Theorem 3 becomes (d (T) OCd 1.5 ((T), it also perfectly matches the nearly optimal result
21 Second, when m and
12].
The above comparisons also show the tightness of the regret bound of RCLUB-WCUU
5.2
Theoretical Performance Guarantee for OCCUD
The following theorem gives a performance guarantee of the online detection algorithm OCCUD. Theorem (Theoretical Guarantee for OCCUD). With assumptions in Section 3 at Vt 2 (o))), for any detected corrupted user E Uh with probability at least - 58, i indeed corrupted user.
This theorem guarantees that after RCLUB- -CUU learns the clustering structure accurately, with high probability, the corrupted users detected by OCCUD are indeed corrupted, showing the high detection accuracy of OCCUD. The proof of Theorem 5 can be found in Appendix

---

Experiments
This section shows experimental results synthetic and real data evaluate ACCUB--CCU rec- ommendation quality and OCCUD's detection accuracy. We compare RCLUB-WCU to LinUCB [ with a single non-robust estimated vector for all users, LinUCB-Ind with separate non-robust estimated vectors for each user, CW-OFUL [2] with a single robust estimated vector for all users, CW-OFUL-Ind with separate robust estimated vectors for each user, CLUB and SCLUB More description of these baselines are in Appendix [F] To show that the design of OCCUD is non- trivial, we develop straightforward detection algorithm GCUD, which leverages the same cluster structure as OCCUD but detects corrupted users by selecting users with highest @ Ov. ov.,.
in each inferred cluster. GCUD selects users according to the underlying percentage of corrupted users, which is unrealistic in practice, but OCCUD still performs better in this unfair condition.
need know all the user information in advance to derive the user embedding for classification, so they cannot be directly applied in online detection with bandit feedback thus cannot be directly compared to OCCUD. However, observe the AUC achieved by OCCUD on Amazon and Yelp (in T is similar to recent offline methods Additionally, OCCUD has rigorous theoretical performance guarantee (Section 5.2
Remark. The offline detection methods 39
6
18 32
18
32
6.1 Experiments on Synthetic Dataset
We use u 1, 000 users and m 10 clusters, where each cluster contains 100 users. We randomly select 100 users the corrupted users. The preference and arm (item) vectors are drawn in d (d = 50) dimensions with each entry a standard Gaussian variable and then normalized, added one more dimension with constant 1, and divided by v2 [1]. We fix an arm set with |A| = 1000 items, at each round, 20 items are randomly selected to form set A, to choose from. Following 40 3.
in the first rounds, we always flip the reward of corrupted users by setting rt - 0. 0... + T/--
And we leave the remaining T' k rounds intact. Here we set T 1, 000, 000 and k = 20, 000.
1.2
Cumulaatee Reeret
RCLAM TANE OM-cetLL
SCLLM
SCLER
Latin
0.8
SCLR
Chnotadhee
0.6
CW-CESE CWocecLad
CU-OFIL
0.0
0.0 0.2 0.4 0.6
0.8
1.0
0.0 0.2
0.4
0.6 Round
0.8
1.0
0.0 0.2 0.4 0.6
0.8 1.0
0.0 0.2 0.4
0.6
0.8 1,0
Round
(a) Synthetic
(b) Movielens
(c) Amazon
(d) Yelp
Figure 3: Recommendation results on the synthetic and real-world datasets
3ig (a) shows the recommendation results. RCLUB-WCE CCU outperforms all baselines and achieves sub-linear regret. LinUCB and CW-OFUL perform worst as they ignore the preference differences among users. CW-OFUL-Ind outperforms LinUCB-Ind because it considers the corruption, but worse than RCLUB-WCCE since it does not consider leveraging user relations to speed up learning.
The detection results are shown in Tab We test the AUC of OCCUD and GCUD every 200, 000 rounds. OCCUD's performance improves over time with more interactions, while GCUD's perfor- mance is much worse as it detects corrupted users only relying on the robust estimations. OCCUD finally achieves an AUC of 0.855, indicating it can identify most of the corrupted users.
6.2 Experiments on Real-world Datasets
We use three real-world data Movielens IT. Amazon 31], and Yelp 333. The Movielens data does not have the corrupted users' labels, so following (24], we manually select the corrupted users. On Amazon data, following [39], we label the users with more than 80% helpful votes as normal users, and label users with less than 20% helpful votes as corrupted users. The Yelp data contains users and their comments on restaurants with true labels of the normal users and corrupted users.
We select 1,000 users and 1,000 items for Movielens; 1,400 users and 800 items for Amazon; 2,000 users and 2,000 items for Yelp. The ratios of corrupted users on these data are 10%, 3.5%, and

---

We first construct the binary feedback matrix through the users' ratings: if the rating greater than 3, the feedback is I; otherwise, the feedback is O. Then we use SVD to decompose the extracted binary feedback matrix Ruxm = X where (, E [u] and X = (a:) ). E [m]] and select d = 50 dimensions. We have 10 clusters Movielens and Amazon, and 20 clusters on Yelp. We use the same corruption mechanism as the synthetic data with = 1, 000, 000 and k = 20, 000. We conduct more experiments in different environments to show our algorithms' robustness in Appendix G The recommendation results are shown in (b) RCLUB-WCU outperforms all baselines. On the Amazon dataset, the percentage of corrupted users is lowest, RCLUB-WCU's advantages over base- lines decrease because of the weakened corruption. The corrupted user detection results are provided in Tab[T] OCCUD's performance improves over time and is much better than GCUD, On the Movie- lens dataset, OCCUD achieves an AUC of 0.85; on the Amazon dataset, OCCUD achieves an AUC of 0.84; and on the Yelp dataset, OCCUD achieves an AUC of 0.628. According recent works on offline settings
30.9%, respectively. We generate the preference and item vectors following [7 21
Time
Dataset
Alg
0.2M
0.4M
0.6M
0.8M
IM
Synthetic
OCCUD
GCUD
0.599
0.478
0.651
0.483
0.777
0.812
0,484
0,502
0.855
Movielens
OCCUD
0.65
0.750
0.785
0.83
0.83
GCUD
0.450
0.474
0.485
0.489
0.492
OCCUD
0.639
0.735
0.761
0.802
0.840
Amazon
GCUD
0.480
0.480
0.456
0.500
0.518
Yelp
OCCUD
0.452
0.489
0.502
0.578
0,628
GCUD
0.473
0.481
0.496
0.500
0.510
Table I: Detection results on synthetic and real datasets
[8] 32). our results are relatively high.
Conclusion
In this paper, are the first to propose the novel LOCUD problem, where there are many users with unknown preferences and unknown relations, and some corrupted users can occasionally perform disrupted actions to fool the agent. Hence, the agent not only needs to learn the unknown erences and relations robustly from potentially disrupted bandit feedback, balance the exploration- exploitation trade-off to minimize regret, but also needs detect the corrupted users time. To robustly learn and leverage the unknown user preferences and relations from corrupted behaviors, we propose novel bandit algorithm RCLUB-WCC setting, based on the learned user relations of RCLUB- -CCU, we propose a novel detection algo- rithm OCCUD. We prove a regret upper bound for RCLUB-WCU, which matches the lower bound asymptotically in T up to logarithmic factors and matches the state-of-the-art results in degener- ate cases. We also give theoretical guarantee for the detection accuracy of OCCUD. Extensive experiments show that our proposed algorithms achieve superior performance over previous bandit algorithms and high corrupted user detection accuracy.
pref-
To detect the corrupted users in the online bandit
Acknowledgement
The corresponding author Shuai Li is supported by National Key Research and Development Pro- gram of China (2022ZD01 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 SRFS2122- 4S02.
10

---

References
[1] Yasin Abbasi-Yadkori, Dávid Pál. and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24, 2011.
[2] Charu C Aggarwal et al. Recommender systems, volume 1. Springer, 2016.
[3] Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2021.
[4] 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.
[5] Qin Ding, Cho-Jui Hsieh, and James Sharpnack. Robust stochastic linear contextual bandits under adversarial attacks. In International Conference Artificial Intelligence and Statistics, pages 7111-7123, PMLR, 2022.
[6] Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng. and Philip S Yu. Enhancing graph neural network-based fraud detectors against camouflaged fraudsters. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 315-324, 2020.
[7] Evrard Garcelon, Baptiste Roziere, Laurent Meunier. Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta. Adversarial attacks linear contextual bandits. Ad- vances in Neural Information Processing Systems, 33:14362-14373, 2020.
[8] Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In Interna- tional Conference on Machine Learning, pages 757-765. PMLR, 2014.
[9] Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562-1578. PMLR, 2019.
[10] Mohammad Hajiesmaili, Mohammad Sadegh Talebi, John Lui, Wing Shing Wong, et al. Ad- versarial bandits with corruptions: Regret lower bound and no-regret algorithm. Advances in Neural Information Processing Systems, 33: 1394399--9995, 2020.
[11] F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19, 2015.
[12] Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. In Advances Neural Information Processing Systems (2022), 2022.
[13] Mengda Huang, Yang Liu, Xiang Ao, Kuan Li, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Auc-oriented graph neural network for fraud detection. In Proceedings of the ACM Web Conference 2022, pages 1311-1321, 2022.
[14] Kwang-Sung Jun Lihong Li, Yuzhe Ma, and Jemry Zhu. Adversarial attacks stochastic bandits. Advances in neural information processing systems, 31, 2018.
[15] Pushmeet Kohli, Mahyar Salek, and Greg Stoddard. fast bandit algorithm for recommen- dation to users with heterogenous tastes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, pages 1135- 1141-114,,220 2013.
[16] Fang Kong, Canzhe Zhao, and Shuai Li. Best-of siie--o-tthhe-eeee three-worlds analysis for linear bandits with wwwpww-the-rgularizeeeeee
230.00825, algorithm. arXiv preprint arXiv:2303. 06825, 2023.
[17] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international confer- ence World wide web, pages 661-670, 2010.

---

[18] Qiutong Li, Yanshen He, Cong Xu, Feng Wu, Jianliang Gao, and Zhao Li. Dual-augment graph neural network for fraud detection. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 4188-4192 2022.
[19] Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[20] Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Proceedings of the 39th International ACM SIGIR conference Research and Development in Information Retrieval, pages 339-548,22 2016.
[21] Shuai Li, Wei Chen, and Kwong-Sar Leung. Improved algorithm on online clustering of bandits. arXiv preprint arXiv: /902.09/22 2019.
[22] Yingkai Li, Edmund Y Lou, and Liren Shan. Stochastic linear optimization with adversarial corruption. arXiv preprint arXiv:1909.02100 2019.
[23] Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, pages 4042 4050. PMLR, 2019.
[24] Shenghua Liu, Bryan Hooi, and Christos Faloutsos. Holoscope: Topology-am -nd-sle aware fraud detection. In Proceedings of the 2017 ACM on Conference on Information and Knowl- edge Management, pages 1539-1548, 2017.
[25] Xutong Liu, Haoru Zhao, Tong Yu. Shuai Li, and John CS Lui. Federated online clustering of bandits. In Uncertainty in Artificial Intelligence, pages 1221-1231. PMLR, 2022.
[26] Xutong Liu, Jinhang Zuo, Siwei Wang, Carlee Joe- Wong. John Lui, and Wei Chen. Batch-size independent regret bounds for combinatorial semi- bandits with probabilistically triggered arms or independent arms. Advances in Neural Information Processing Systems, 25:14994-44916 2022.
[27] Xutong Liu, Jinhang Zuo, Siwei Wang, John CS Lui, Mohammad Hajiesmaili, Adam Wier- man, and Wei Chen. Contextual combinatorial bandits with probabilistically triggered arms. In International Conference on Machine Learning, pages 225993 PMLR, 2023.
[28] Yang Liu, Xiang Ao, Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Pick and choose: a gnn-based imbalanced learning approach for fraud detection. In Proceedings of the Web Conference 2021, pages 3168- 1177,,77,0007 2021.
[29] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to ad- versarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1 122, 2018
[30] Yuzhe Ma, Kwang-Sung Jun, Lihong Li, and Xiaojin Zhu. Data poisoning attacks in contextual bandits. In International Conference on Decision and Game Theory for Security, pages 186- 204. Springer, 2018.
[31] Julian John McAuley and Jure Leskovec. From amateurs to connoisseurs: modeling the evo- lution of user expertise through online reviews. In Proceedings of the 22nd international conference World Wide Web, pages 897-908. 2013.
[32] Zidi Qin, Yang Liu, Qing He, and Xiang Ao. Explainable graph-based fraud detection via neural meta-graph search. In Proceedings of the 31st ACM International Conference on Infor- mation& & Knowledge Management, pages 4414-4418, 2022.
[33] Shebuti Rayana and Leman Akoglu. Collective opinion spam detection: Bridging review net- works and metadata. In Proceedings of the 21 acm sigkdd international conference on knowl- edge discovery and data mining, pages 985 985-994, 2015.
[34] Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. A semi- semi-supervised graph attentive network for financial fraud detection. In 2019 IEEE International Conference on Data Mining (ICDM), pages 598- 607. IEEE, 2019.
12

---

[35] Zhiyong Wang, Xutong Liu, Shuai Li, and John CS Lui. Efficient explorative key-term selec- tion strategies for conversational contextual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages (0288-1029)) 2023.
[36] Zhiyong Wang, Jize Xie, Xutong Liu, Shuai Li, and John Lui. Online clustering of bandits with misspecified user models. arXiv preprint arXiv:2310.02711 2023.
[37] Junda Wu, Canzhe Zhao, Tong Yu, Jingyang Li, and Shuai Li. Clustering of conversational bandits for user preference learning and elicitation. In Proceedings of the 30th ACM Intema- tional Conference on Information & Knowledge Management, pages 2129-2139, 2021.
[38] 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 in Information Retrieval, pages 529-538, 2016.
[39] Ge Zhang. Jia Wu, Jian Yang, Amin Beheshti, Shan Xue, Chuan Zhou, and Quan Z. Sheng. Fraudre: fraud detection dual-resistant to graph inconsistency and imbalance. 2021 IEEE International Conference Data Mining (ICDM), pages 867-876. IEEE, 2021.
[40] Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Linear contextual bandits with adversarial corruptions. arXiv preprint arXiv:2110.26615 2021.
[41] Jinhang Zuo, Zhiyao Zhang. Zhiyong Wang, Shuai Li, Mohammad Hajiesmaili, and Adam Wierman. Adversarial attacks on online learning rank with click feedback. arXiv preprint arXiv:2305. 70771, 2023.
13

---

Appendix
A Proof of Lemma
1
We first prove the following result: With probability least 1 for some 8 E (0, 1), at any [T]:
8 ( à)
0l. 0010)
S
Vi Ei
(8)
Amin (,
where B(Ti,,, ) A 2 2log(3) + dlog(1
The
+ v
0r, 00(1) (AI i,) "ii O0(1)
= (AI+ + Σ
Wi, Ca x )-
Σ
Wi La, Vs - 00(1)
eely
eeft
+ Σ
Wi, Ia x 1
Σ
W Ca (x 0, + 17s + +c,)) gi(()
eejy
AE
+
W To 1 Gr
(AI+ Σ
W/, a Ta
x I, (00000 -10(00 + Σ
Wi, sta 17
-Pi(t)
Wi Ta Co
-MM (0(1)
M
Σ
Wi, Da 1s
M Σ
Wa, Ca
BEIE
where we denote M = M + ΛI, and the above equations hold by definition. Therefore, we have
0 - 0000 11, S M
+
M
Σ
wi St !|s
+
M Σ
wi
wa Cs
(9)
We then bound the three terms in Eq.
9 one by one. For the first term:
> M g
||
M
(10)
Arman
M
where we use the Cauchy- inequality, the inequality for the operator norm of matrices, and the fact that Amin( M',,) (,)) A.
For the second term in Eq. 9.. we have
M Σ
Wi, Ce. 17
S
M Σ
Win Fe 17
M M
(11)
2
Σ ne(e) ipmi
Wi, H no
M
(12)
Amian
My,)) (.)
where (T. follows by the Cauchy-Schware inequality and the inequality for the operator norm of matrices, and Eq. 12) follows by the Courant-Fischer theorem.
14

---

Let i. La, 7. oe then we have: ||0.112 I
V Wi .
Laa ll2 S 1, n. is still
l-sub-gaussian (since Vs is -ssub-gaussian and W 1), M AI Σ
Tg and
nominator in Eq. becomes
Σ selt!
T.
Then, following Theorem in M and by union
M
bound, with probability at least - 8 for some ò E (0, 1), for any U, have:
Σ eEit
Σ 1/
Wi, Wa
Ba, Ta
M
det( det(M (, 2 2 logí " 5)) + log( det(A[)
Tia Ad
$ 2 log( ") dllo(11 +
(13)
where det(.) denotes the determinant of matrix arguement, Eq.13 13 is because det(M),.) S
traco(AI MMtoo vcla Wa, aI,)
M and det(AI) Ad.
For the third term in Eq.
we have
M
Σ
Wi, at Co
M i,
Σ
Wi st Co
M
(14)
2
2
Een Wi,, La Co iime
M
(15)
Anmin M';
Σ Eely c,
cco Wi.e |a 1
Amiia (M
aC
(16)
Amin (M',))
where 14) follows by the Sluchy-Schward inequality and the inequality for the operator norm of matrices, Eq. follows by the Courant-Fischer theorem, and Eq.(16) is because by defini-
tion wi.s I 10 MO S
(since M's ž M M M || M 2
T M
|| Il,,; 1. loel C.
Combining the above bounds of these three terms, we can get that Eq. holds.
We then prove the following technical lemma.
Lemma 6. Under Assumption at any time t, for any fixed unit vector O E Rdd
E. T Fo,, )' 7o 2 J/a 1/aa
(As x) 2
-1-e-
K dx
(17)
where is the upper bound of |Ag] for any t.
Proof. The proof of this lemma mainly follows the proof Claim in 81 but with more careful analysis, since their assumption the generation distribution is more stringent than As- sumption 3 by putting more restrictions on the variance upper bound d² (specifically, they require o² )
15

---

Denote the feasible arms at round t by A, { Ft,,,....
L...A. E Consider the corresponding
ii.d. random variables = (e (0'=, x2,)² E,((0' |Ail,,
|A By Assumption
O: are sub-Gaussian random variables with variance bounded by o². Therefore, for any a > 0 and any E ||Ar]], we have:
Pr(O, < -al |A S
20
where we use P((-) Ai.),
be the shorthand for the conditional probability (4-1,, 7 it).
By Assumption
3 we can also get that I[O | = E x2, 0|1Al]
2
Amin (E xx
Ag. With these incqualities above, get
a2 P min (0 (0xx1,)) de - 2 -e- 202 )
Ael
Therefore, get
E. xo. )..) 2 E.
min (0 ||All
/=1,...,|A
P(( min
( xx11)) 2 x Acl))r
0
i=1,. Arl
xi 20
(1
dx A
Note that wi,s min(1, (1, | |
). and we have
a Amin( 2 avā.
Ca, IM
M 5, Da, Amin MM;"'
Since a < typically holds, we have wi, 2 av
Then, with the item regularity assumption stated in Assumption 3 the technical Lemma 6 together
with Lemma 7 in [19], with probability at least - 6, for a particular user i, at any f such that
Ti 2 16 log(
X2 X26 ), we have:
Amin (M, 2 20 Ar, +
(18)
With this result, together with Eq.0 we can get that for any such that Tú, probability least 1 for some d (0, 1), vi U, we have:
16 log(
Sd X
). with
B(Tr,s, 9)
00, gd(1)
v Amin (M'))
B(Ti,t, E
Do +1
B(Tres 4)
V 2T.TT
V 2ogg( (3) + d + 3x)) + V A oC
(19)
2av
Then, we want to find a sufficient time Tú, for fixed user i such that
0 0001
?
(20)
4
16

---

To do this, with Eq. (99) we can get it by letting
VA
7
(21)
LavAhsTi
12
aC
7
(22)
12 1
2 2oog 5) + dlog(1 +
Ad
7
(23)
2av Ni
12
For Eq. 21
we can get
Ti, 72V
(24)
ag22z
For Eq. 22.
22 we can get
T₁ > 72aC2
(25)
For Eq. 23 we have
loog( x3 doog
The
72
(26)
2a 2a
144
Then it is sufficient to get Eq 26 if the following holds
2log(#)
72
(27)
2α DAviX
288
d dlog(1 +
Tha 122
xe
(28)
2a ViiaTi 288
For Eq.(2 we can get
288 log 4)
Tú,
(29)
2ov Adx
For Eq. 28
we can get
144d
Tr Xd
The >
22aVX log(1 +
(30)
Following Lemma 9 in 19 we get the following sufficient condition for Eq. 30
288d
288
Th La
log(
(31)
Then, since typically o/ E1
we can get the following sufficient condition for Eq.
29 and
31
log U ) Pa
288d
Th,
(32)
Together with Eq. 24. Eq. 25). and the condition for Eq. 18 we can get the following sufficient condition for Eq. (20) to hold
288d
u 16 log(
8d
72VA
72aC²
Th > max
) log
(33)
PaVAA
X
VVX
Then, with Assumption 2 on the uniform arrival of users, following Lemma 8 in 19. and by union bound, we can get that with probability at least 8, for all
288d >avxXx
16
8d
72V
72aC2
2 To A 16 logl
{ ( + 4u max(
log( 8
log
X 22 - }, (34)
A2
2
a
17

---

(2) holds for all i E U. and therefore (0) holds for all i E U. With this, we can show that RCLUB- WCU will cluster all the users correctly after To. First, if CCCLBB-CCU deletes the edge
(i, 1), then user i and user belong to different ground-truth clusters, i.e., |0; 01ll2 > 0. This
because by the deletion rule of the algorithm, the concentration bound, and triangle inequality,
110 0:l12 = || |²(0) 0300
Z |0.. 0c: 1 -10000 OL.:
o 0.. 0. Sec-
2
ond, we show that if |10; 0.l 2 7, RCLUB-WCU will delete the edge (i,1). This is because
if 110. 0ell 2 7, then by the triangle inequality, and |0... 0000)
O 0001 1
0, 0)))) 02 oz we have 10.. - 000/11 2 110; - 0rll 0,, 0
1
0 0il!)
7 1 vX+ / +dlog(1+ TEA
+ vX+ logt 4) loggl "o
which will trigger the
VA-2Ź_ T..
VA+27. Ti.
deletion condition Line 10
Algo
B Proof of Lemma 2
After To, if the clustering structure is correct, i.e., V, = Vilie) then we have
0v,,-11 0i -M V,,t-
-AI+
Σ
Wiy, Sio 20))-
Σ
Wi WB, raa) Os.
(AI + Σ
Wh Ca Da. 1-1
Σ
Wi, so, (2 0i + 17s + co)) -.. (35)
sc( 1
st 1 v
(AI
Σ
Wi Wi La Feae T-1-1
(Wi Da Da + XI)O; -A0in
sE[t-1]
KE[t-a]
LeVV
LeVV
+ Σ
Ta 7 + Σ
Win Da Ca) -0:-
Win
-E|t-1|
nE(r-1)
Lev
1M Vi, 0i, - -M
Ve,t-1
Wa 1l + M
V..1-
Σ
Wi, Wa, Cs
xE[t-1]
1E2-11
where we denote M M = Mv + AI, and Eq. 35 is because V22 = Vi(ia) thus 0,, = 0,,, Vi, E V₁. Therefore, we have
x (0v,t-1- - -0t) S x M
+
x
M 1-1
Vi,-1
Σ
Wi tt
+
8 M
Vi-1-1
Σ
Wi W
st 11 %,V%
ucle 1] EvEVe
< Lall M
Vx+
Σ .cl 1 LEVV
Wi Co
+ Σ
Wi, Lo Co
ac 11 MEV
M
1
M Myy
(36)
where Eq. 36) is by Sauchy-Schwer inequality, matrix operator
inequality, and
ao M v,,t- 0i S
MM v,, 2
1
ll
10,1l2 VV since
Vaui( (M v..
Amin (v 2 and 110,,112 1
Let T. A Wa 1he A / /ls then we have: ||ãa|l2 S 11 Wi 112 |aa ll2 S 1, 7h is
still ssub-gaausiian (since no is -ssub-gaussin and / W I 1). M', = AI + E
18

---

and Eegnn!!! scc
ai 77s
becomes
Σ Eely
Then, following Theorem
M Ve---
kame
v.e-
in with probability at least - 8 for some å E (0, 1), we have:
Σ
Σ Jo
Ba, fs2
1E|t-11 1o
nell
MV
M -
V4.t-1
2 (oo85)) 2 logl det(M V2,e-1)
det(Al)
( u log(
+ dloog1+ + T
(37)
Ad
Σ -et-r Wi, Wi Col
And for
we have
M ( 12
Wi Wa, Co
Wie, |cal 1 M S saC,
(38)
=C[(-1]
SEV
M
where we use Σ
|el
C. Wi,.s
Io M
Plugging Eq. 38 and Eq. into (q.3 together with Lemma Lemma
we can complete the proof of
2
C Proof of Theorem 3
After To, define event
= (the algorithm clusters all the users correctly for all To}
(39)
Then, with Lemma and picking 8 7 we have
R(T)
P() 1 <1(E)R(TT +4x T
T
(40)
= =[(E)R(T) +4.
Then it remains to bound I{E) For the first rounds, we can upper bound the regret in the first To rounds by To- After To, under event & and by Lemma 2 we have that with probability at least 1 5, for any F..:
x 10v, -0.) s s 1|alallllnn My & Ca.
(41)
Therefore, for the instantaneous regret Ri round t, with E, with probability at least 1 8, at Vt To:
R₂ = 0 0i, x 2T,0.. 0..
x o (fi, -vi.t-1) + (2 0v Caja) - (xr Ov. 1 + Co.t)
(42)
+ T v - 0².) + Cou, - Cap.1
< 2Ca,t
where the last inequality holds by the UCB arm selection strategy in Eq. and Eq.441
19

---

Therefore, for [[E))(T))
[(ER(TT) & R(TO) + B[H{}
Rd
t=
T
To + 28[[(E}
Σ
Ca.ll
(43)
TTTo1
Then it remains bound [[[(E) Ei=To+1 Cani. For E Ei=To+1 Casse can distinguish it into two cases:
T
T
Σ
Ca,t S
Dat Laell MaillMy
C= To+1
1=1
Da llM +
Σ
| lollll
(44)
(e()) <1
Then, we prove the following technical lemma. Lemma 7.
T
T
(in E V2) || lireyy .1 S 2dg + Xd
Vj E [m]
(45)
Proof.
lliir Vaz oo del del(Mv,,7) del Mv (els)))deeMM,,na
de I E VyJ V3J V - Lay M vT
1+ 1iir Vi} || li
T
Ve,(M
II t=oo1
(1+Iie E Il li
det(AI)
II
[++Ife Vi} || li
(46)
To+1
Va E [0, 1), we have < 2og( + x)) Therefore
Σ
min(Ifie E Vg} |x I M va-=
52 Σ log 1 II E V/J | | Parl
tmm T1
t To+1
T II
2 log
(1 (1+ E VUJ} || Pn Vile-
1=To+1
< [[log(de((Mv,
log(det(AI))
(trace(AI + ET ET=, llfir ViJaa, 21
< 2lo
Ad
T
< 2d Ad
(47)
20

---

Denote the rounds with Whe, 1 as {ti..... ft, }. and gram matrix G -. _ XI +
E delel Laz, Pag, denote the rounds with wiat < 1 as (f th h. gram matrix GVgg. #4-1 -
LeVi,
X+E
eeir! VVV
Wig eg Bag Way.
Then we have
m7 4
m
4
Σ
Ta. DaallMii
Mi, Vil Toir M tritg-1
Hi, vii pai, Gv, 3
TE| TE
j=1==1
(48)
Hig EV} Σ min 1 VVi Iatr 1 Dv
(49)
T
TV5T x 2d 2ogo +
(50)
Xd
m
T
T
2m
Tog
V
2mdT log(1
(51)
Ad
Xd
j=1
where Eq.448) is because G v b--1 2 M F.-1 in Eq. 49 we use Cauchy-Schward inequality,
7 and Dtm Ihi, E VV} s Tv Tu,, in Eq. 51
in Eq. 50 we use Lemma inequality and ΣØ= Tv, =
we use Cauchy-Schwar
For the second part in Eq. (4.4444, Let a'ay. A WWig 2y Bogg then
| MM vin-1
Wast ||xae
11 ve
Σ
|:aay [waellMai
(52)
|aay M
C
E <1
t <1
m 1
Wiggtt
Dayz 1|
Hús E VV}
a
M
E min(1, Tii E Vi}
(53)
a
2d logol1 + 2d
2md log(1 +
T
xa
(54)
a
a
where in Eq. 52 we use the definition of the weights, in E3) we use G!-1
M
16-
Vig
-1-
and Eq. uses Lemma 7
21

---

Then, with Eq. p 51
Eq.(44). Eq. Eq.40)
Eq. 43
8
7.
and
B = va +
/ 2 + dllo(1 + T.) + aC, we can get
T R(T) 44+ + (2VÁ+ + V (1og(T)) + d'lo(11 + Ad
+ aC) x (V2máT log(+
T
Ad
2md log(1 + I Ad
288d FavAi,
SdT 72VA 72aC²
= 4 + 16u log(uT) + 4u max
log(ul)
log(
)
X2
X2
arpix 22v
+ (2V + v / 21og(T) + dlog(1 + Ad) + =a0)= x (V2mdT log(1 +
T
T
Ad
Ad
2md + T
Picking a v
we can get
0
Cvd 1
R(T) S O(1
(T)) + +((VVmTlog(T) ((mCdlo'''(T)) (55)
X2
Thus we complete the proof of Theorem
D Proof and Discussions of Theorem
Table of the work [12] gives lower bound for linear bandits with adversarial corruption for single user. The lower bound of R(T)) is given by: R(T) R(dvT dC). 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 independent linear bandit algorithms to leverage the common information of clusters, the best they get is R(T)= dC Ligim) dvT,. For special case where T; Vi [m], we can get
R(T)) 2 dC + Eie(m) d d mT dC', which gives lower bound of R(dv + dC') for the LOCUD problem.
Recall that the regret upper bound of RCLUB-WCU shown in Theorem 3 is of o
(c cva
72
+
x/ )ool))())) + (dv (idvmmTan log(T)) + ( asymptotically matching this lower
bound with respect to T up to logarithmic factors and with respect to C up to O(ym) factors, showing the tightness of our theoretical results (where m are typically very small for real applica- tions).
We conjecture that the gap for the factor in the mC term of the lower bound is due the strong assumption that cluster structures are known to prove our lower bound, and whether there exists tighter lower bound will be left for future work.
E Proof of Theorem 5
We prove the theorem using the proof by contrapositive. Specifically, in Theorem 5 we need to prove that for any > To. the detection condition Line 7 of Algo for user then with probability at least 1 - 58, user is indeed a corrupted user. By the proof by contrapositive, we can prove Theorem by showing that: for any / > To. if user normal user, then with probability least 1 56, the detection condition in Line 7 of Algo will not be satisfied for user i.
If the clustering structure is correct then for any normal user i
0,6 Ov...t = 0 0 + 0, 0v....
(56)
22

---

where o,,, is the non-robust estimation of the ground- truth 8,, and Ov.,.t-1 is the robust estimation of the inferred cluster Vi, for user at round Since the clustering structure is correct f, 0 v is the robust estimation of user i's ground-truth cluster's preference vector @z(i) 0 at round f.
We have
0..- 0: - (MI + Ma,)
-ib, - 0:
=AI +
Daa T )-1(
Ta, v's) - A;
(AI +
Da n, )-1
Da. (2 0: mn))) 0;
(57)
fymi
= (AI + Σ
La x a,,
((I
Σ
Ta. x. )0; 20; + Σ
La, Mo)) - 0;
scle
1x
= AM 1, 0, M 1.t
Σ
Lo 7s
where we denote M, - AI + E
ve10
Da. Fa T. and Eq. because since user is normal, we
have C, Vs = i.
Then, we have
0 0:
<
0: 2
+
M
Σ
Ta.
AE(C] sami
1
<
A
M 1,1
110:112 +
M Σ
Da, 17
M
1,8
7
(58)
VX
Σ scty Fa. No
M
(59)
Amio (M 2.,)
where Fq.
follows by the Cauchy-Soon -Schhy---crarz..cc inequality and the inequality for the operator norm
of matrices, and Eq. 59h follows by the Courant-Fischer theorem and the fact that Amin (M 2 A. [ for fixed normal user i, with probability least for some
Following Theorem
5 E (0, 1) we have:
Σ Ca, Ts
S v 2 logt 1 { + log(
det( det(M det(A
KE(e]
1ir-11
S 2 logg( 1 8) + log(1
Ti,
(60)
Xd
(race(>I+>... scll Ba, TT))
where (q.) is because det( (M,) <
Toi and det(AI)
dd.
Plugging this into Eq. 59), we can get
Vx+ + v 2 2log(3)
d d + Ted)
@0.. 0. <
(61)
Amiin (M
23

---

Then we need bound 0.. Vv...
With the correct clustering, V4, V3(i). we have
1 Visst 0 = -M byeet
=AI + Σ
Wi La x
Σ
W Fa, - [x) -0:
.ejt]
sevio (0
1yEV (())
= -M + Σ
W a. Ca
W W ua (1 0, + 1/8 + +c,))) 0, (62)
aEId ixE 5(1)
(M + Σ
W Da Fnn) (2,))1(0 ((I
Sa, 20, )0 20,
(EV()) X0
(()
Wi Ca +
Σ
Wi Wi Da ca)) 0:
AM Vr,, 0 M M
Vesa
Σ
Wi, Da, 1s
M
Veset
Σ
aa, Cs. (63)
Therefore, we have
|0o -vveeel SA M Minn +
M Mv.i
Vi,est
Σ
to 17s
+ M MVi..t
Vesstt
Σ
W/, sa,
2C(0 5,1
$
M 5 12
Vi,e, 2
1101112 +
M
M
Vi
Σ
Wi Da 77s
M x
Mrnee 11/
2
M M
Vani
Σ
Wi 17
|
(64)
+ #/I
Vā+ Σ refe
Wi, Fa D7
SEly] VecVi(e)
Winn Co
M Vi
M Vi
(65)
Ammin M (v.ett
Let T, da,, 7 v We, then we have: || S |1 V
[2a, 1l2 S 1, 7/ is still
1 1-sub-gause sub--gaussian (since 7) is --sub-gaussin and Wii.. S 1), M Vieet AI Σ
seld 8.Ø and 4 EV
Σ scid Wa, 7s S.c 500)
becomes
Σ
2010 .c10 ExtV30
3.
Then, following Theorem in
M Veatt
M
Vi..
11 with probability at least 1 8 for some 5 E (0, 1), for fixed normal user i, we have
2 log( ) + +log( det(M
Σ
Wi, Ca, no
det(AI)
M Vy
Vele
1 () + dllo(1 + Triee
$ V 2 log(
(66)
trace(
(X+
Bay I.
(e and
where Eq. is because det M (v,a) 5
<
det(AA)= =
24

---

For Σ seltl (0)
Wi wi Co
we have
M Vi
Σ
Wi La, Cs
lesl wis || ll A Ve,es
.ejl Fo 200
AE/9
C
MV Vigeie
S aC
(67)
where (4. is because wa,s 1 A
(since M Vi,at 7
1 Ne
M se
M ž M in.s M 1218 = M. = M Vireer Exefy lca S C. Therefore, we have
11 M 2 | Ml 2 | ll M 1
) and
Vi,es
VX+ V 2 !)) dlog(1 +
Iraeed Ad
+ aC
0. Vva. S
(68)
Vanin M vi,.st)
and (5. together with Lemmal 1 we have that for a normal user i, for any t To. with probability least I 56 for some (0, 5)
With (6)) Eq.
@0.. - Ōv... $ @o.. 0. + 00. Ov....
VĀ+ + 2 ) + doog + THd)
VA+ 12 log( + d log(1 + "id")) + aC
V Amiia M,,,. (,)
Amin (M (v...)t)
(69)
which is exactly the detection condition Line of Algo
Therefore, by the proof by contrapositive, we complete the proof of Theorem 5
Description of Baselines
We compare RCLUB-WCU the following five baselines for recommendations.
L7] A state-of-the-art bandit approach for a single user without corruption.
LinUCB-Ind: Use a separate LinUCB for each user.
CW-OFUL A state-of-the-art bandit approach for single user with corruption.
CW-OFUL-Ind: Use separate CW-OFUL for each user.
CLUB A graph-based clustering of bandits approach for multiple users without corrup- tion.
SCLUB 21 A set-based clustering of bandits approach for multiple users without corrup-
tion.
G More Experiments
G.1 Different Corruption Levels
To see our algorithm's performance under different corruption levels, we conduct the experiments under different corruption levels for RCLUB-WCU, CLUB, and SCLUB on Amazon and Yelp datasets. Recall the corruption mechanism in Section 6. we set k as 1,000; 10,000; 100,000. The results are shown Fig 4 All the algorithms' performance becomes worse when the corruption level increases. But CCUB--CCU is much robust than the baselines.
25

---

RCLUB-WCU
RCLUB BLUUB-WCU
Camulative Regret
5
CLUB
Cumulative Regret
CLUB
SCLUB
SCLUB
6
2
0
1K
10k Corruption Level
100K
1k
10k
100k
Corruption
(a) Amazon Corruption Level
(b) Yelp Corruption Level
Figure 4: Cumulative regret in different corruption levels
RCLUB-WCL -CUB
1.0
RCLUB- WCU
Comulative Regret
CLUB
Comulative Regret
CLUB
0.8
SCLUB
SCLUB
0.6-
3
0.4
0.2
0.0
5
10
20
50
10
20
50
Cluster Number
Cluster Number
(a) Amazon Cluster Number
(b) Yelp Cluster Number
Figure 5: Cumulative regret with different cluster numbers
G.2 Different Cluster numbers
Following we test the performances of the cluster-based algorithms (RCLUB-WCU, CLUB, SCLUB) when the underlying cluster number changes. We set m as 5, 10, 20, and 50. The results are shown 5 All these algorithms' performances decrease when the cluster numbers increase, matching our theoretical results. The performances of CLUB and SCLUB decrease much faster than RCLUB-WE UCUUU, indicating that RCLUB WCU is more robust when the underlying user cluster number changes.
26


Reviews:
[{"review_id": "uGHoIwiwAQ", "reviewer": "Reviewer_wNgt", "summary": "This research paper introduces an innovative method for learning and utilizing unknown user relations from disrupted behaviors to enhance the learning process and identify corrupted users in an online setting. To achieve this, a new bandit algorithm (RCLUB-WCU) is proposed, along with an online detection algorithm that leverages user relations inferred by RCLUB-WCU. The paper also presents a regret upper bound for RCLUB-WCU, which closely matches the lower bound with respect to T (the number of rounds) up to logarithmic factors and performs well even in degenerate cases. The experiments conducted on synthetic and real-world datasets demonstrate significant improvements in performance compared to previous bandit algorithms", "questions": "1. Page 9, lines 341-345: Authors claim that the performance of the proposed algorithm improves with proportion of corrupted users in the dataset. Seems like this argument is made based on the three datapoints (from three real-world datasets). This argument could be potentially strengthened by evaluating all algorithms while varying the number of corrupted users in one of the datasets.\n\n2. Page 6: Line 220: It says that the threshold is carefully designed to handle the estimation uncertainty... How difficult/easy it is to tune this threshold? How critical this threshold is to the performance of the approach?\n\n3. Pages 4-5, Lines 188-204: It seems like the subscript `t` is used to denote both timestamp (bandit round) as well as the cluster? Also I see subscript `s` to indicate the bandit iteration which should ideally be denoted by t ?\n\n4. In Equation (2), are you considering data from all t -1 previous rounds? Or are you using iterative update and only include the data from previous round, i.e. (t -1)^{th} round?", "limitations": "Authors should cover any other limitations of this work in addition to potential limitations I highlighted above:", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a novel application to learn unknown user relations in their preferences from potentially corrupted feedback. At the same time, the paper shows how to leverage the learned relations to speed up learning as well as adaptively detect the corrupted users online from bandit feedback. Overall I think this paper makes a significant contribution to the literature on online learning from corrupted feedback as well as detection of adversarial users in multi-user online learning setting. \n\n2. Experiments on synthetic and real-world datasets clearly indicate  lower reward regret of proposed approach in comparison to five other baselines from the past literature on online clustering of bandits. At the same time, the algorithm is able to identify corrupted users with higher accuracy than a simple baseline that directly compares the robust-estimators of preference vectors of a user and its corresponding cluster.\n\n3. The authors back up their results with theoretical analysis and guarantees on the performance of the proposed algorithm.", "weaknesses": "1. It seems to me that the performance of proposed approach could potentially be sensitive to the nature of underlying user relations in their preferences and the tightness of the detected clusters. For example, to my understanding, this algorithm might not work well if there are too many tight clusters. However, if one chooses too big clusters, then the solution might compromise on personalization as users in a loose cluster might not be represented accurately by a common preference vector defined for the cluster. The paper does not provide any discussion on the impact of cluster sizes on the algorithm. \n\n2. The approach requires multiple parameters to be specified. (e.g. regularization parameter, confidence radius parameter, threshold parameter, edge detection parameter). There is no discussion provided on the sensitivity of the results to the choices of these parameters (in the main draft at least).\n\n3. The results in Table 1 on detection of corrupted users are not very clear. To begin with, it's not clear what do numbers in the table indicate? I assume they indicate recall of true corrupted users. If so, where are the precision numbers? Where are F1 scores given that thre is class imbalance? Authors need to clearly indicate what they are measuring and also provide an explanation in case they aren't measuring both precision and recall. Also it would be nice to have comparison with multiple baselines. Further, authors could potentially enrich the results with other variants of the baseline, e.g. another baseline variant could simply compare the non-robust estimators of cluster and user. (I believe the current baseline compares the robust estimators of a user and its cluster).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer wNgt:\nWe appreciate the reviewer for the positive comments and valuable advice. We will incorporate the suggestions into the final version. \n## A. Responses to the Weakness:\n### 1. Impact of the cluster number and sizes:\nThanks for your suggestion of adding discussions on the impact of the cluster number and sizes. \n\nAs you noted, the performance of our algorithm is influenced by the cluster number $m$. As shown in Theorem 3, the regret upper bound of our algorithm increases with a larger $m$. The performance decreases with larger $m$ is inevitable for all clustering of bandits (CB) algorithms. The regret lower bound in Theorem 4 also supports this claim, theoretically indicating that no CB algorithms can avoid decreasing the performance with a larger $m$. \nOur empirical evaluations on different problem instances with different $m$ also validate this statement: (i) as detailed in Figure 5 and also mentioned in [18], the performance decreases with larger $m$ is observed for all CB algorithms. (ii) With different $m$, our algorithm outperforms the baselines (as detailed in Appendix G.2). \n\nFor the second comment on the concern of ``big loose\" clusters, our algorithm automatically learns the cluster sizes over time. Our algorithm clusters users adaptively during the learning process, and it will cluster all users correctly after some interactions (theoretically supported by Lemma 1), where users in each ground-truth tight cluster share the same preference vector. Therefore, the sizes of the clusters are not chosen by our algorithm but determined by the underlying problem instance. As shown in Theorem 3, the regret upper bound depends on the cluster number $m$ and does not depend on the sizes of the clusters. We will provide some discussions in the final version.\n\n### 2. About the parameters:\nFollowing the publicly available code of the previous works on the clustering of bandits and bandits with corruption [12, 20], we set the regularization parameter $\\lambda=1$, the confidence radius parameter $\\beta=1.5$, the threshold parameter $\\alpha=0.2$, and the edge deletion parameter $\\alpha_1=1$. These are classic parameters in the previous clustering of bandits and linear bandits with corruption works [8, 12, 18, 20, 24]. To ensure the robustness, our algorithm does not introduce additional parameters compared to previous approaches [8,12,18,20,24]. And we use the same values for these parameters as in previous works to make fair comparisons with the baselines. We will specify these parameters in the experiment section and add more experiments to show the sensitivity of the parameters.\n### 3. (a) About Table 1:\nFollowing the previous works on offline corrupted user detection [6, 17, 29, 34], we use AUC as the metric for online detection. We mentioned it in lines 349-351, and we will make it clearer by giving more descriptions and specifying AUC in the caption of Table 1.\n### 3. (b) About more baselines:\nWe compare OCCUD with one baseline when reporting the detection results in Table 1, because our paper is the first work to study the online corrupted user detection from bandit feedback, and no previous baselines exist. Thanks for the valuable suggestion on adding more baselines. We have done some experiments on the proposed baseline by simply comparing the non-robust estimators of cluster and user (GCUD2). The results (AUC) are shown in Table 2 in the global PDF. The results show the superior outperformance of our OCCUD algorithm. We shall consider adding more feasible baselines in a future version. Besides, please note that when we report the recommendation results (where there are more baselines applicable) in Figure 3, we compare our approach with several baselines.\n\n## B. Answers to the questions:\n### 1. About the relation between algorithm performance and proportion of corrupted users:\nThanks for your valuable comment. We have done some experiments on the Movielens dataset with different proportions of corrupted users (10\\%, 20\\%, and 50\\%). We compare our algorithm with CLUB and SCLUB (they perform the best among baselines on Movielens). The results are shown in Figure 1 in the global PDF. We can see that when there are more corrupted users, RCLUB-WCU's regret increases less than CLUB and SCLUB and gains a larger advantage. This is consistent with our argument in Line 341-345 of the paper. We will add these experimental results in the final version to strengthen the argument.\n\n### 2. About the threshold:\nAs mentioned in the above response, in this threshold, we do not introduce additional parameters to be tuned than previous works on the clustering of bandits and bandits with corruption [8, 12, 18, 20, 24], which ensures that our method is robust. And in empirical evaluations, we do not tune the threshold parameter $\\alpha$ and the edge deletion parameter $\\alpha_1$; we set them to be the same as the previous works to make fair comparisons [12, 20]. \n### 3. About the subscripts t and s:\nYes, $t$ is used to denote both timestamps and clusters; we use $V_t$ to denote the cluster for user $i_t$ inferred by the algorithm at round $t$. We will change $s$ to $t$ and make the notations clearer following your comments.\n### 4. About the iterative update:\nEq.(2) shows that the estimated cluster vector is the solution of a weighted ridge regression considering data from all t -1 previous rounds. But in the algorithm, we can use the iterative update at each round that only includes the (t-1)-th data (Line 8 in Algo.1) thanks to the nice closed-form solution (Lines 194-195) of Eq.(2), which makes the algorithm computationally efficient.\n\nThanks again for the reviewer's appreciation and the suggestions on improving our work.\n"}, {"review_id": "D0DDlXVW81", "reviewer": "Reviewer_HbaT", "summary": "The authors introduce an online learning problem called LOCUD (Learning and Online Corrupted Users Detection from bandit feedback) in which the aim is to detect a small fraction of the overall users with corrupt behaviors; corrupt users occasionally perform undesirable actions, but otherwise mimic normal user behavior, making them challenging to detect.\n\nThe paper then proposes a framework that leverages the relations between users to form semantic clusters, and uses the clusters to identify corrupt users. Specifically, the authors propose RCLUB-WCU (Robust CLUstering of Bandits With Corrupted Users) to progressively prune a fully connected graph of users to clusters of connected components based on user interactions and preferences. Then, OCCUD (Online Cluster-based Corrupted User Detection) estimates a robust and non-robust estimation of each user's preferences, and identifies a user as corrupt if the gap between the two estimates exceeds a carefully designed threshold. OCCUD is repeatedly invoked within RCLUB-WCU to continually prune and refine the relational structure amongst the users.\n\nExperiments one on synthetic dataset and three real-world datasets show the proposed approach is able to detect more corrupted users while achieving the least amount of regret over time than competing methods.", "questions": "* Why are the dataset sizes so small (e.g., 1,400 users and 800 items for Amazon)? What are the original sizes of the datasets used in the experiments?\n\n* Where are the error bars for Table 1, and Figures 4 and 5?", "limitations": "No, the authors have not addressed the limitations or the potential negative societal impact of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "* The paper introduces a challenging but relevant problem of trying to identify corrupt users despite sporadic behavior in an online dynamic environment. This problem is especially relevant for sites like Amazon and Yelp which often contain users that exhibit corrupt behavior.\n\n* The proposed approach of leveraging relational information between users to more effectively detect corrupt users is intuitive, and the experimental results suggest its effectiveness.\n\n* Analyses and bounds related to regret are given for the RCLUB-WCU/OCCUD algorithm, with proofs provided in the Appendix.\n\n* The paper is generally well-written and follows a logical progression.", "weaknesses": "* Experiments are performed on a small number of small datasets, potentially limiting the generalizability of the proposed approach. Performing experiments with a wider range of larger datasets would significantly benefit the claims made in the paper.\n\n* No empirical runtime analysis is provided for the proposed approach or any of the competing methods. Runtime analysis can help practitioners decide what method is likely to work best for their particular problem.\n\n* Only one baseline method is compared to the proposed approach for the AUC results (Table 1). Where are the results for the other methods?\n\n* Additional experimental results including different corruption levels and number of clusters are provided in the Appendix, but those results (Figures 4 and 5) only shows regret, and only compares the proposed approach with two baseline methods. Can the authors provide results for the other baseline methods, as well as AUC results for these additional and potentially insightful experiments?\n\n* Minor clarity improvements:\n    * Use authors' names to cite previous work. \"The work [5] proposes...\" -> \"Ding et al. (2022) propose...\".\n    * The legends in Figure 5 make the subplots hard to read. Figure 5 is also not color-blind friendly, consider adding markers or using different line styles for different methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer HbaT:\nThanks for the positive comments and valuable suggestions for improving our work. We will revise the paper in the final version following your advice. Our responses are as follows.\n## A. Responses to the Weakness:\n### 1. About the small dataset:\nPlease refer to the response to your first question later about the dataset.\n\n### 2. About the runtime analysis\n\nThanks for the valuable suggestion. We give the run time results with $T=1,000,000$ on our computer with CPU of Intel(R) Xeon(R) Gold 6240C CPU @ 2.60GHz, which has 36 cores and 2 threads in each core\n in Table 1 in the global PDF. Overall there are no large differences since all the algorithms are computationally efficient. \n\n### 3. About the baseline for online detection\nWe compare OCCUD with one baseline when reporting the detection results in Table 1, because our paper is the first work to study the online corrupted user detection from bandit feedback, and no previous baselines exist. The baselines used to compare the online recommendations with RCLUB-WCU (in Figure 3) can not detect corrupted users, so they can not be compared with OCCUD. Also, the offline detection methods [34, 6, 17, 29] need to know all the user information in\nadvance to derive the user embedding for classification, so they cannot be directly applied in online detection with bandit feedback.\nTherefore, we compare our OCCUD algorithm with a straightforward GCUD algorithm (which is proposed by us as a baseline to show that the design of OCCUD is non-trivial). Thanks for the valuable suggestion on adding more baselines. We add another straightforward baseline named GCUD2 which compares the non-robust estimators of clusters and users. We have added this GCUD2 baseline to Table 2 in the global PDF. The results also show the superior outperformance of our OCCUD algorithm. We will also consider adding more feasible baselines in a later version.\n### 4. About experimental results with different corruption levels and number of clusters:\nThanks very much for this valuable suggestion. In Figures 4 and 5 in the paper, we only compare with two baselines because these two baselines perform the best among all the baselines. The regret results of all the recommendation algorithms can be found in Figure 2 in the global PDF. The AUC results for online detection algorithms can be found in Figure 3 in the global PDF.\nThese additional results also clearly show the good performance of our proposed algorithms. We will add these results in the final version following your valuable advice.\n### 5. About the minor clarity improvements:\nThanks for giving these detailed suggestions; we will do the revisions accordingly.\n## B. Responses to the questions\n### 1. About the size of the dataset:\n(1) In the previous works of clustering of bandits and bandits with corruption [8, 18, 24, 32], the sizes of datasets in most works are usually not very large and are close to ours. Therefore, following these works [8, 18, 24, 32], we extract a proportion of the large dataset to be the dataset used for experiments. We agree that performing experiments with a wider range of larger datasets would significantly benefit our claims. We also have some results on an enlarged dataset extracted from Yelp (the same rule of extraction, 20000 users and 20000 items, 10 times larger than the dataset used in our paper). The results are shown in Figure 4 and Table 3 in the global PDF. We can see our proposed algorithms also outperform baselines in this larger dataset. \nWe will conduct more experiments on more and larger datasets in a later version following your valuable advice.\n\n(2) The original data sizes are: Movielens: 2,113 users and\n10,197 items; Amazon: 1,429 users and 900 items; and Yelp: 1,987,929 users and 150,346 items. \n\n### 2. About the error bars:\nThanks for this valuable suggestion. Table 1, Figures 4 and \n 5 with error bars can be found in Table 2 and Figures 2 in the global PDF, respectively. We will add these error bars in the final version.\n\nAgain, we thank the reviewer for the positive comments, the time spent on reviewing our paper, and the valuable advice on further improving our work."}, {"review_id": "barxiZRg8P", "reviewer": "Reviewer_GoSQ", "summary": "The paper considers the following bandit setup.\n\nThere are $u$ users organised into $m\\ll u$ clusters. Each cluster has vector $\\theta$ attached to it. On step $t$ the learner deals with a user uniformly selected from the pool and picks an arm $a$. If this is a bona fide user, the learner gets average reward $x'_a\\theta$, where $x_a$ is the feature vector for the arm and $\\theta$ is the vector for the cluster the user belongs to. There is a number of corrupted users though, who give reward $x'_a\\theta + \\eta + c$, where $\\eta$ is noise and $c$ (a bounded quantity) is corruption.\n\nWe have a twofold problem of minimising the regret and identifying the corrupted users. The paper presents an algorithm based on a graph of connections between users built by observations of their behaviour. The regret upper bound is matched by a lower bound. It is shown that with high probability we identify the corrupted users correctly and after a while end up with correct clusters.", "questions": "None.", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I think this is an interesting result and a strong guarantee. The explicit modelling of corrupted user behaviour may seem restrictive at first, but it covers many possibilities. The authors were very careful to relax all the requirements as much as possible (e.g., consider sub-Gaussian noise etc). The algorithm is intuitive.", "weaknesses": "No obvious weaknesses. The appeal of the result may be limited for some NeurIPS participants.\n\nSome minor suggestions (not reflected in my evaluation of the paper):\n\n1. I do not think quantifiers should be used as in \n\nAt $\\forall t$, for any fixed unit vector $z$ ...\n\n(Assumption 3.) \n\nUsing \"every\" here will not blow the volume of the paper out of proportions, but will improve readability.\n\n2. Use $\\verb!\\left(...\\right)!$ in formulas like (7) to get larger brackets.\n\n3. I do not find the abbreviations used in the paper convenient and phrases such as\n\nCW-OFUL-Ind outperforms LinUCB-Ind because it considers the corruption, but worse than RCLUB-WCU\n\neasy to parse.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer GoSQ\nWe are very grateful for your strongly positive comments and appreciation. Below are our responses to your minor suggestions.\n\n## 1. About the minor suggestions 1-2 on improving the format and readability:\nThanks for giving these detailed suggestions. We will revise these two points following your valuable advice.\n## 2. About the abbreviations:\nThanks for your valuable suggestion. We will add a table to make it more convenient for the readers to find the abbreviations.\n\nFinally, thanks again for your positive feedback, time to review our paper, and detailed and valuable suggestions on improving our work."}, {"review_id": "hJIFX7q21G", "reviewer": "Reviewer_Lisv", "summary": "This paper presents an important online learning problem named LOCUD to learn and utilize unknown user relations from disrupted behaviors to speed up learning and identify the corrupted users in an online setting. Also, the authors propose a novel bandit algorithm RCLUB-WCU, and devise a novel online detection algorithm OCCUD based on RCLUB-WCU’s inferred user relations. Extensive experiments demonstrate that the proposed methods can achieve superior performance over previous bandit algorithms and high corrupted user detection accuracy. ", "questions": "Provided above.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is scientifically sound.\n2. The clarity of the presentation is easy to follow.\n3. Extensive experiments of the proposed methods have superior performance than other baselines.", "weaknesses": "1. The introduction section of the paper lacks sufficient emphasis on the motivation behind the proposed methods. The authors should provide a more comprehensive analysis of the current issues and challenges in the relevant fields, clearly indicating how their research work addresses and improves upon these challenges. This will help readers better understand the significance and contributions of the proposed methodology.\n2. The abstract section should be more concise. It should effectively highlight the key innovations and improvements introduced by the proposed methodology.\n3. The paper provides limited discussion and summary of the relevant literature. To strengthen the research methodology, the authors should include a more extensive review of existing research methods, along with an analysis of their strengths and weaknesses. \n4. The experimental content is not enough to effectively prove the superiority of the method. It is suggested that the authors add more dimensional experiments and give a comprehensive analysis and explanation of the experimental results, thus making the conclusions in the paper more convincing.\n5. The dataset used in the experiments is relatively small, which may limit the generalizability of the findings. It is recommended to supplement a large-scale real dataset for performance validation.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Responses to Reviewer Lisv\nThanks for the positive comments and valuable suggestions for further improving our work. Our responses are listed below.\n\n## 1. About the improving the writing and contents of the introduction, abstract, and related work sections:\n\nThanks for giving these detailed and valuable suggestions on improving the writing and contents of our paper. For the introduction section, we will follow your advice to illustrate more on the motivations behind our proposed methods by providing more discussions on the current issues, challenges, and how we address these challenges. For the abstract section, we will highlight our contributions more concisely. For the related works, we will follow your suggestion to add more extensive discussions on existing relevant works with a more detailed analysis of their strengths and limitations in the Appendix.\n\n## 2. About the experimental content:\nIn our experiments, the number of datasets and the exploration of different settings are richer or comparable to related works [3, 7, 17, 18, 20, 24].\nIn the previous works of clustering of bandits, [20] uses one synthetic dataset and two real-world datasets, and they do not conduct any studies in different settings. In [24], they employ one synthetic dataset and one real-world dataset with parameter study only on the synthetic dataset. In [18], they use one synthetic dataset and two real-world datasets and explore the influence of cluster numbers. In the previous works of bandits robust to corruption, [3] uses one synthetic dataset and one real-world dataset, and test both contextual and non-contextual settings only on the synthetic dataset; in [7], they use one synthetic dataset and two real-world datasets with study about the difference caused by attacking on a single context or more than one contexts. In the previous works of offline corrupted user detection, [17] uses two real-world datasets with one ablation study to explore how the components in their model influence the performance. Compared to the above previous works, our work includes the results on one synthetic dataset and three real-world datasets. And we add two additional experiments in two real-world datasets to observe the algorithm's performance with different corruption levels and cluster numbers. The number of datasets and the exploration of different settings are richer or comparable to related works. \n\nApart from the experimental contents, we also give solid theoretical performance guarantees to prove the superiority of our proposed methods. We would add more experiments with more discussions and explanations. We would appreciate it if the reviewer could provide more specific suggestions on adding some experiments that could further improve our study.\n\n\n## 3. About the size of the dataset for experiments:\n\nIn the previous works of clustering of bandits and bandits with corruption, the sizes of datasets in most works are not very large and are close to ours [8, 18, 24, 32]. Therefore, following these works [8, 18, 24, 32], we extract a proportion of the large dataset to be the dataset used for experiments. We agree that performing experiments with a larger dataset would enhance the generalizability of our findings. Following your valuable advice, we have done some experiments on an enlarged dataset extracted from Yelp (the same rule of extraction, 20000 users and 20000 items, 10 times larger than the dataset used in our paper). The results are shown in Figure 4 and Table 3 in the global PDF. We can see our proposed algorithms also outperform baselines on this larger data set. We will conduct more experiments on larger datasets in a later version following your valuable advice.\n\n\nFinally, we thank the reviewer again for the positive feedback, the efforts in reviewing our paper, and giving valuable advice to further improve our work."}]

Author rebuttal:
We sincerely appreciate all the reviewers for the positive comments, the time spent on reviewing our paper, and the valuable advice for improving our work. We have done some experiments for your reference. Please refer to the global PDF.

Meta-review: The authors introduce a novel learning problem called for Online Learning and Online Corrupted Users Detection from bandit feedback. The paper proposes a new framework for leveraging the relations between users to form semantic clusters, and uses the clusters to identify corrupt users.

The problems as well as the a the approach are novel and interesting, and the paper is well written. I am happy to recommend for acceptance.
Decision: Accept (poster)