Online Clustering of Dueling Bandits
Authors: Zhiyong Wang
Jiahang Sun
Mingze Kong
Jize Xie
Qinghua Hu
John C.S. Lui
Zhongxiang Dai
Venue: ICML 2025 poster (2025)
Keywords: Multi-armed bandits
dueling bandits
clustering of bandits
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We introduce the first clustering of dueling bandit algorithms for both linear and neural bandits, which provably benefit from cross-user collaboration in the presence of preference feedback.

Abstract: The contextual multi-armed bandit (MAB) is a widely used framework for problems requiring sequential decision-making under uncertainty, such as recommendation systems. In applications involving a large number of users, the performance of contextual MAB can be significantly improved by facilitating collaboration among multiple users. This has been achieved by the clustering of bandits (CB) methods, which adaptively group the users into different clusters and achieve collaboration by allowing the users in the same cluster to share data. However, classical CB algorithms typically rely on numerical reward feedback, which may not be practical in certain real-world applications.  For instance, in recommendation systems, it is more realistic and reliable to solicit preference feedback between pairs of recommended items rather than absolute rewards. To address this limitation, we introduce the first "clustering of dueling bandit algorithms" to enable collaborative decision-making based on preference feedback. We propose two novel algorithms: (1) Clustering of Linear Dueling Bandits (COLDB) which models the user reward functions as linear functions of the context vectors, and (2) Clustering of Neural Dueling Bandits (CONDB) which uses a neural network to model complex, non-linear user reward functions. Both algorithms are supported by rigorous theoretical analyses, demonstrating that user collaboration leads to improved regret bounds. Extensive empirical evaluations on synthetic and real-world datasets further validate the effectiveness of our methods, establishing their potential in real-world applications involving multiple users with preference-based feedback.

Online Clustering of Dueling Bandits
Zhiyong Wang' Jiahang Sun? 2 Mingze Kong²
Jize X
Qinghua Hu
John C.S. Lui"
Zhongxiang Dai
Abstract
1. Introduction
The contextual multi-armed bandit (MAB) is a widely used framework for problems requiring se- quential decision- under uncertainty, such as recommendation systems. In applications in- volving a large number of users, the performance of contextual MAB can be significantly improved by facilitating collaboration among multiple users. This has been achieved by the clustering of ban- dits (CB) methods, which adaptively group the users into different clusters and achieve collabo- ration by allowing the users in the same cluster share data. However, classical CB algorithms typ- ically rely numerical reward feedback, which may not be practical in certain real-world applica- tions. For instance, in recommendation systems, it is more realistic and reliable to solicit preference feedback between pairs of recommended items rather than absolute rewards. To address this lim- itation, we introduce the first "clustering of du- cling bandit algorithms" to enable collaborative decision-making based on preference feedback. We propose two novel algorithms: (1) Cluster- ing of Linear Dueling Bandits (COLDB) which models the user reward functions as linear func- tions of the context vectors, and (2) Clustering of Neural Dueling Bandits (CONDB) which uses a neural network to model complex, non-linear user reward functions. Both algorithms are supported by rigorous theoretical analyses, demonstrating that user collaboration leads to improved regret bounds. Extensive empirical evaluations on syn- thetic and real-world datasets further validate the effectiveness of our methods, establishing their potential in real-world applications involving mul- tiple users with preference-basee feedback.
The contextual multi-armed bandit (MAB) is a widely used method in real-worh applications requiring sequential decision- making under uncertainty, such recommenda- tion systems, computer networks, among others (Li et al., 2010; Wang et al., 2023; Dai et al., 2024b). In contextual MAB problem, a user faces a set of K arms (i.e., context vectors) in every round, selects one of these K arms, and then observes a corresponding numerical reward (Lattimore & Szepesvári, 2020). order to select the arms to maxi- mize the cumulative reward (or equivalently minimize the cumulative regret), we often need consider the trade-off between the exploration of the arms whose unknown re- wards are associated with large uncertainty and exploitation of the available observations collected so far. To carefully handle this trade-off, we often model the reward function using surrogate model, such as a linear model (Chu et al., 201 1) neural network (Zhou et al., 2020).
Some important upplications of contextual MAB, such as recommendation systems, often involve a large number (e.g.. in the scale of millions) of users, which opens up the pos- sibility of further improving the performance of contextual MAB via user collaboration. To this end, the method of online Clustering of Bandits (CB) has been proposed, which adaptively partitions the users into a number of clusters and leverages the collaborative effect of the users in the same cluster to achieve improved performance (Gentile al., 2014; Wang et al., 2024a; Li et al., 2019).
Classical CB algorithms usually require an absolute real- valued numerical reward as feedback for each arm (Wang et al., 2024a). However, in some crucial applications of con- textual MAB, it is often more realistic and reliable request the users for preference feedback. For example, in recom- mendation systems, it is often preferable to recommend a pair of items to user and then ask the user for relative feedback (i.e., which item is preferred) ( (Yue et al., 2012). As another example, contextual MAB has been successfully adopted to optimize the input prompt for large language models (LLMs), which is often referred to as prompt opti- mization (Lin et al., 2024a;b). In this application, instead of requesting an LLM user for a numerical score as feedback, it is more practical to show the user pair of LLM responses generated by two candidate prompts and ask the user which
'The Chinese University of Hong Kong 'Tongji University "The Chinese University of Hong Kong. Shenzhen 'Hong Kong University Science and Technology 'Tianjin University. Corre- spondence to: Zhongxiang Dai <daizhongxiang @ www.....uuccc.....
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Online Clustering of Ducling Bandits
response is preferred (Lin al., 2024a; Verma et al., 2024). A classical and principled approach to account for prefer- ence feedback in contextual MAB is the framework of con- textual dueling bandit (Saha, 2021; Bengs et al., 2022; Saha & Krishnamurthy, 2022; Li et al., 2024). In every round of contextual dueling bandits, a pair of arms are selected, af- ter which a binary observation is collected reflecting which arm is preferred. However, classical dueling bandit algo- rithms are not able to leverage the collaboration of multiple users, which leaves significant untapped potential to further improve the performance in these applications involving preference feedback. In this work, we bring together the merits of both approaches, and hence introduce the first clustering of dueling bandit algorithms, enabling multi-user collaboration in scenarios involving preference feedback.
letters for vectors and boldface uppercase letters for ma- trices. The number of elements in set A is denoted as [A], while [m] refers to the index set {1, .......
21, m_, and | M = vx M x represents the matrix norm of vector with respect the positive semi-definite (PSD) matrix M.
Clustering Structure. Consider a scenario with users, indexed by U = {1. u}. where each user i E 2 is associated with a unknown reward function fi : IR. + R which maps an arm æ E X C Itd to its corresponding re- ward value fz)z). We assume that there exists an underlying. yet unknown, clustering structure over the users reflecting their behavior similarities. Specifically, the set of users 24 is partitioned into m clusters C1 C2, . Cm, where m < and the clusters are mutually disjoint: Uj = U and Cj n = 1 for j + j'. These clusters are referred to as ground-truth clusters, and the set of clusters is denoted by C ( C2,..... ,m) Let f denote the common reward function of all users in cluster j and let j(i) E [m]] be the index of the cluster to which user i belongs. If two users i and 7 belong to the same cluster, they have the same re- ward function. That is, for any & E U, if & E Cj()- then Se = f: = fo(0) Meanwhile, users from different clusters have distinct reward functions.
We firstly proposed our Clustering Of Linear Dueling Ban- dits (COLDB) algorithm (Sec. I), which assumes that the latent reward function of each user is linear function of the context vectors (i.e., the arm features). In addition, to handle challenging world scenarios with complicated non-lineat reward functions, we extend our COLDB algo- rithm use a neural network to model the reward function, hence introducing our Clustering Of Neural Dueling Ban- dits (CONDB) algorithm (Sec. 3.2). Both algorithms adopt a graph to represent the estimated clustering structure of all users, and adaptively update the graph to iteratively refine the estimate. After receiving a user in every round, our both algorithms firstly assign the user to its estimated cluster, and then leverage the data from all users in the estimated cluster to learn linear model (COLDB) or a neural network (CONDB), which is then used to select pair of arms for the user to query for preference feedback. After that, we update the reward function estimate for the user based on the newly observed feedback, and then update the graph to remove its connection with users who are estimated to belong to a different cluster.
Modeling Preference Feedback. At each time step E [T], a user in E LI is served. The learning agent observes a set of context vectors (i.e., arms) X, C X C Rd where [&,] K S C for all t. Each arm x E X, a feature vector in Ed with || S 1. The agent assigns the cluster C, to user and recommends two arms 2t,1, F E Xg based on the aggregated historical data from cluster C.. After receiving the recommended pair of arms, the user provides a binary preference feedback Y/ E (0, 1}, in which yr = 1 if æ4,1 is preferred over 2t,2 and ye = 0 otherwise. We model the binary preference feedback following the widely used Bradley-Temy-Luee (BTL) model (Hunter, 2004; Luce, 2005). Specifically, the BTL model assumes that for user it, the probability that the first arm xt,1 is preferred over the second arm 21,2 is given by
We conduct rigorous theoretical analysis for both our COLDB and CONDB algorithms, and our theoretical results demonstrate that the regret upper bounds of both algorithms are sub-linear and that a larger degree of user collaboration (i.e., when a larger number of users belong to the same cluster on average) leads to theoretically guaranteed im- provement (Sec. 4). In addition, we also perform both synthetic and real-world experiments to demonstrate the practical advantage of our algorithms and the benefit of user collaboration in contextual MAB problems with preference feedback (Sec. 5).
Pe(21,1 > x1,2) = (lfi, - fr, (xx,2));
where μ : E - [0, 1] is the logistic function: u²z)) = Ite In other words, the binary feedback ye is sampled from the Bernoulli distribution with the probability Pr > xx,2).
We make the following assumption about the preference model:
Assumption 2.1 (Standard Dueling Bandits Assumptions). 1. [n([(=))) - -m((())) S L,, - g(x)), Ya E X for any functions f,g Rd + IR.
2. Problem Setting
2. mingex V)(f(z)) 2 Kpp kk 0.
This section formulates the problem of clustering of duel- ing bandits. In the following, we use boldface lowercase
Assumption 2. is the standard assumption in the analysis of linear bandits and dueling bandits (Li et al., 2017: Bengs
2

---

Online Clustering of Ducling Bandits
al., 2022), and when j is the logistic function, I = 1/4. The regret incurred by the learning agent is defined as:
2.2. Clustering of Neural Dueling Bandits
Here we allow the reward functions fi's to be non-linear functions. To estimate the unknown reward functions f. 's we use fully connected neural networks (NNs) with ReLU activations, and denote the depth and width (of every layer) of the NN by L 2 2 and VNN, respectively (Zhou et al., 2020; Zhang et al., 2021). Let h(æ;; ()) represent the output of an NN with parameters 0 and input vector æ, which is defined as follows:
T
T
RT= = Σ re = Σ (2f,(2;) - (1 - Sú, (2x,,))) 1=1
where x² = arg x. (z) represents the optimal arm at round t. This is a commonly adopted notion of regret in the analysis of dueling bandits (Bengs et al., 2022; Saha & Krishnamurthy, 2022).
2.1. Clustering of Linear Dueling Bandits
11(2;; 0) = Wr.ReLU (W,, -- -..IRRLUUU (...
(.........L. ReLUU (i))))
For the linear setting, we assume that each reward function J is linear in a fixed feature space ((-), such that f(( = 0 ((x), Va E X. The feature mapping Φ IRd + Rd fixed mapping with [|o())]l2 I 1 for all x E X. In the special case of classical linear dueling bandits. we have that ((xx)= æt, i.e., <6()) is the identity mapping. The use of d(xx) enables us to potentially model non-linear reward functions given an appropriate feature mapping.
in which ReLU(2) = max(x, 0}, W1 E Rd Wi e R moN X man for 2 S 1 < L, WT E R RIxms, We denote the parameters of NN by 0 (vec (Wi);... vec (W r)), where vec (A) converts an M x N matrix A into a MN- dimensional vector. We use p to denote the total number of NN parameters: p = dNnNN + m [- 1) + mNN. and use g xx; 0) to denote the gradient of (a:; 9) with respect to O.
The algorithmic design and analysis of neural bandit algo- rithms make use of the theory of the neural tangent kernel (NTK) (Jacot et al., 2018). We let all users use the same initial NN parameters 0,, and assume that the value of the empircal NTK is bounded: - (g(2;; 00),g(2; Oo)) < 1, Va E X. This is a commonly adopted assumption in the analysis of neural bandits (Dai et al., 2023; Kassraie & Krause, 2022). Let T denote total number of rounds in which the users in cluster j is served. We use H2 to denote the NTK matrix (Zhou et al., 2020) for cluster j. which is (T₃K) x (i,K)dimmeniion matrix. Similarly, we de- fine h, as the (T₃ x 1-dimensional vector containing the reward function values of all T,K arm feature vectors for cluster j. We provide the concrete definitions of H, and hy in App. C.I. We make the following assumptions which are commonly adopted by previous works on neural bandits (Zhou et al., 2020; Zhang al., 2021), for which we provide justifications in App. C.I.
In this case, the reward function of every user i is repre- sented by its corresponding preference vector 0g, and all users in the same cluster share the same preference vector while users from different clusters have distinct preference vectors. Denote 0 as the common preference vector of users in cluster Cj. and let j(i) E [m] be the index of the cluster to which user i belongs. Therefore, for any f E U, if É E C5te), then 02 = 0, = (1())
The following assumptions are made regarding the cluster- ing structure, users, and items:
Assumption 2.2 (Cluster Separation). The preference vec- tors of users from different clusters are at least separated by a constant gap 7 > 0, i...
0i 00' 1, 2 for all j E [m].
Assumption 2.3 (Uniform User Arrival). At each time step the user i, is selected uniformly random from U, with probability 1/u, independent of previous rounds.
Assumption 2.5. The reward functions for all users are bounded: [f(()] & Vr E X, Vi E U. There exists A > 0 s.t. H2 > Aol, Vj E C. All arm feature vectors satisfy ||</||2 = and xy- = 4/24 Vo E X, VI E (T].
Assumption 2.4 (Item regularity). At each time step f, the feature vector d(xr) of each arm æ E X, is drawn inde- pendently from a fixed but unknown distribution p over (ő(x) E Rd [|x(=)]l2 < 1), where E0,,<<<pp ( ((((z) (((x)) () (z) - ól ) T is full rank with minimal eigen- value X2 >0 O. Additionally, at any time t, for any fixed unit vector 0 E Rdd (0 (δ(x1) - o(æ²))) j22 has sub-Gaussian tail with variance upper bounded by o².
Denote by fó the common reward function of the users in cluster Cj. and let j(i) E [m] be the index of the cluster to which user i belongs. Same as Sec. 2.1, here all users in the same cluster share the same reawrd func- tion. Therefore, for any l E U, if E E C5to), then fe(z) f((x) = fo(0 Vo E X. The following lemma shows that when the NN is wide enough (i.e., msN is large), the reward function of every cluster can be modeled by a linear function.
Remark 1. All these assumptions above follow the previous works on clustering of bandits (Gentile et al., 2014; 2017; Li & Zhang, 2018; Ban & Hc, 2021b; Liu et al., 2022; Wang et al., 2024a;b). For Assumption 2.3, our results can easily generalize to the case where the user arrival follows any distribution with minimum arrival probability 2 Pmiin
Lemma 2.6 (Lemma B.3 of (Zhang et al., 2021)). As long as the width mgx of the NN is large enough: mxn 2
3

---

Online Clustering of Ducling Bandits
Poly(T, L, K, 1/Kiss Lu 1/ 1/2, 1o)(1/6)), then for all clusters j [m], with probability of at least 1 - 6, there exits a Oz such that
Estimating Shared Statistics for Cluster C2 (Line 6-Line 7). Once the cluster C2 is identified, COLDB estimates common preference vector O, for all users within this cluster by aggregating the historical feedback from all members of
f(x) (g(2; 0o), 87- -0)),
C. Specifically, in Line 6, the common preference vector is determined by minimizing the following loss function:
VMNN 02 0 0u v 22g H h1 B, for all æ E Nr, E [T] with it E Cj.
0, = arg min
Σ
(v. log μ (0T [0(2,,1) -0(xx,2))
0
-E/--1 CEE,
We provide the detailed statement of Lemma 2.6 in Lemma C.I (App. C.2). For a user i belonging to cluster jX), we let f @g(0), then we have that f((x) = (g(x;; 0o). f, o Va: X. As result of Lemma 2.6, for any 8 E 21, if E Cj(),, we have that f.t f,a 00((), yo E X.
+ (1 Us) log / (0T [0(2r.)2) ((Ba))))) + > 11101
which corresponds to the Maximum Likelihood Estima- tion (MLE) using the data from all users in the cluster C₂. Additionally, in Line 7, COLDB computes the aggregated information matrix for Ct which is subsequently utilized in selecting the second arm 22,2
The assumption below formalizes the gap between different clusters in a similar way to Assumption 2.2.
A Assumption 2.7 (Cluster Separation). The reward functions of users from different clusters are separated by a constant gap y/:
Σ #E[t-11
=
i,EC,
[(()) 1 (((()) 27' 0, Vi.i' E [m].. +
f V' N.
(2)
Arm Recommendation Based on Cluster Statistics (Line 8-Line 9). Leveraging the estimated common preference
In neural bandits, we adopt / (x;; 0g) the fea- ture mapping. Therefore, our item regularity assumption (Assumption 2.4) is also applicable here after plugging in <(x)) = (1///NN))gf (x;; 0o).
vector 0, and the aggregated information matrix V2-1, COLDB proceeds to recommend two arms as follows:
First Arm Selection (æx,,). 1). In Line 8, COLDB selects the first arm by greedily choosing the arm that maximizes the estimated reward according to 0,:
3. A Algorithms
3.1. Clustering Of Linear Dueling Bandits (COLDB)
Ft.1 = arg max O. (xx). xE
(3)
Our Clustering Of Linear Dueling Bandits (COLDB) algo- rithm is described in Algorithm 1. Here elucidate the underlying principles and operational workflow of COLDB. COLDB maintains dynamic graph G. = (2, E₂) encom- passing all users, whose connected components represent the inferred user clusters in round t. Throughout the learning process, COLDB adaptively removes edges to accurately cluster the users based their estimated reward function parameters, thereby leveraging these clusters to enhance line learning efficiency. The operation of COLDB proceeds as follows:
Second Arm Selection (z. Following the selection of ær,1, in Line 9, COLDB selects the second arm by maximizing an upper confidence bound (UCB):
Be Ky
2².2 = arg max 0, (xx)) 2E
+
[k(())) - ((
(4)
Intuitively, (q. encourages the selection of the arm which both (a) has large predicted reward value and (b) is different from It,1 and the arms selected in the previous t 1 rounds when the served user belongs to the currently estimated cluster C, In other words, the second arm æ1,² is chosen by balancing exploration and exploitation.
Cluster Inference C. for User in (Line 2-Line 5). Ini- tially, COLDB constructs a complete undirected graph Go = (U, Ev) over the user set (Line 2). As learning pro- gresses, edges are selectively removed to ensure that only users with similar preference profiles remain connected. At each round I, when user i, comes to the system with fea- sible arm set X₂ (Line 4), COLDB identifies the connected component C, containing & in the maintained graph Gr-1+ which serves as the current estimated cluster for this user (Line 5).
Updating User Estimates and Interaction History (Line 10-Line 11). Upon recommending 21,1 and 2t,2, the user receives binary feedback y: ( > 22,2) from user é. and then updates the interaction history D; = {i,, D,,1, F,,2 V.m (Line 10). Moreover, COLDB up- dates the preference vector estimate for user i, while keep- ing the estimates for the other users unchanged (Line 11).
4

---

Online Clustering of Ducling Bandits
Specifically, the preference vector estimate o.,,e is updated via MIEE using the historical data from user de:
trained NN with parameters Og and the aggregated infor- mation matrix Vi-1 to select the pair of arms. The first arm is selected by greedily maximizing the reward prediction of the NN with parameters 0, (Line 8):
0 = arg min
Σ
Us log loggug (66()))))))))) - (b)x,))))
0
1
G=
Ft,1 arg max ((:;; 0z). a
(10)
+ (1 yo) ( (0(2..2) ((.,)))) + 1101.
The second arm is then selected optimistically (Line 9):
(5)
2t.2 = arg max h(x; 0.) + VT ((((z) - -( 1 (1I) ΦEA,
Dynamic Graph Update (Line 12). Finally, based the updated preference estimate ,,,, for user 4, COLDB reassesses the similarity between i, and the other users. If the discrepancy between i and oz., for any user surpasses a predefined threshold (Line 12), the edge (ie: E) removed from the graph G effectively separating them into distinct clusters. The resultant graph G, = (4, F,) is then utilized in the subsequent rounds.
V d 2 log log(u/0) (u/0) and B is defined in Lemma 2.6. Here denotes the effective dimenision which we will introduce in detail in See. 4.2.
in which PT e BT+BV Kpp
A
+1, Br
Updating User Estimates and Interaction History (Line 10-Line 11). After recommending the pair of arms F1,1 and 24 we collect the preference feedback y/ [(,,,1 > xx,2) and update interaction history: Dr (1z. (1..2,,1 1,, 2. Yz V= (Line 10). Next, we update the pa- rameters of the NN used to predict the reward for user in by minimizing the following loss function (Line 11):
3.2. Clustering Of Neural Dueling Bandits (CONDB)
Our Clustering Of Neural Dueling Bandits (CONDB) algo- rithm is illustrated in Algorithm 2 (App. A), which adopts neural networks to model non-linear reward functions. Sim- ilar to COLDB, our CONDB algorithm also maintains a dynamic graph G2 = (24, Fa)) in which every connected component denotes an inferred cluster, and adaptively re- moves the edges between users who are estimated belong to different clusters.
(0)
1
Σ xE(t-1]
(y. log e (H( 0) h( 0)) +
TANN
(1 y.) log μ (h(xx,, h(xx,,;;)))
110 0ull
(12)
to yield parameters 0,,.. The NN parameters for the other users remain unchanged.
Cluster Inference T, for User in (Line 5). Similar to COLDB (Algo. 1), when new user i, arrives, our CONDB firstly identifies the connected component C₁ in the main- tained graph G:-1 which contains the user is and then uses it as the estimated cluster for ét (Line 5).
Dynamic Graph Update (Line 12). Finally, we use the updated NN parameters 0z,; for user it to reassess the simi- larity between user i, and the other users. We remove the edge between (iz. L) from the graph GG-1 if the difference between Ó.,r and 0z,, : is large enough (Line 12). Intuitively, if the estimated reward functions (represented by the re- spective parameters of their NNs for reward prediction) between two users are significantly different, we separate these two users into different clusters. The updated graph G = (4t E,) is then used in the following rounds.
Estimating Shared Statistics for Cluster C. (Line 6). Af- ter the cluster C, is identified, our CONDB algorithm uses the history of preference feedback observations from all users in the cluster C₁ to train a neural network (NN) to minimize the following loss function (Line 6):
(,) 1
Σ
yo μ (h( 0) - h(x,,22 0)) +
-E(e-1] 2] 1.
4. Theoretical Analysis
A 110 00112
(1 log / (h(xx [k - 01)
2 (9)
In this section, we present the theoretical results regarding the regret guarantees of our proposed algorithms and provide detailed discussion of these findings.
to yield parameters 0.. In addition, similar to COLDB (Algorithm 1), our CONDB computes the aggregated infor- mation matrix for the cluster C, following (2) . Note that here we replace (xx) from (2) by the NTK feature repre- sentation (xx) (1 / /m)g (x; 0o), in which Og represents the initial parameters of the NN (Sec. 2.2).
4.1. Clustering Of Linear Dueling Bandits (COLDB)
The following theorem provides an upper bound on the expected regret achieved by the COLDB algorithm (Algo. I) under the linear setting.
Arm Recommendation Based on Cluster Statistics (Line 8-Line 9). Next, our CONDB algorithm leverages the
Theorem 4.1. Suppose that Assumptions 2.1, 2.2, 2.3 and 2.4 are satisfied. Then the expected regret of the COLDB
5

---

Online Clustering of Ducling Bandits
Algorithm I Clustering Of Linear Dueling Bandits (COLDB)
1: Input: f(Ta,) // 2lg(l//)) Ld 11+-1; (xpp)
regularization parameter
0, confidence parameter
Kp V 2.
Be - (21/) + dog (1 11.2 n [dx)), Kp >
2: Initialization: Vo V1,0 A I, 0.00 0, vi U. complete Graph Go (u, Eo) over U.
Ag
for = l..t...... do
4: Receive the index of the current user it U, and the current feasible set X2;
5: Find the connected component Ct for user i in the current graph Gt-1 as the current cluster;
6: Estimate the common preference vector 0, for the current cluster C,:
0. = arg min
Σ -f Ce
Us log (0 [ō(x,,1) - of (2x2,)))) + (1 y.) log (0 [ō( - ((xx,11))
2 11012:
0
(6)
Calculate aggregated information matrix for cluster Ct: Vi-1 Vo + E eeten (6(x,,)) ((0x;2))
kec
T
8: Choose the first arm æt,1 arg m 0, p(x);
9: Choose the second arm 24,2 arg max 0, (Ø(x)) - ((xr,1)) + f l1(()))) (b ))l,;
10: Observe the preference feedback: = ( > 2x,2), and update history: Dj = {is, Cs 22,22 Uo Mamss1,.... I......
11:
Update the estimation for the current served user 4,:
O.tt arg min
Σ
yy log (0 [o( 6( +11 Uo) log (0 [0(x.,2) o(...)))) + 11112
keep the estimations of other users unchanged; Delete the edge (iz, {) E E, if
12:
0 - d2. > 00:1]>/(TTan
S(Tr,))+
(8)
13: end for
algorithm (Algo. f)r I rounds satisfies
only sub-linear in but also becomes tighter when there smaller number of clusters m, i.e., when a larger number of users belong to the same cluster on average. This pro- vides a formal justification for the advantage of cross-user (13) collaboration in our problem setting where only preference feedback is available.
R(T) = (u(
1
+
log T
dv mT
22
X2
Ki
=0 (0 dv dvmT)
(14)
Kap Kap
Based prior techniques (Wang et al., 2024a; Liu al., 2022) and the single-user dueling bandit lower bound (Saha, 2021), can get lower bound of O( ddmI') for the linear setting. Our Algo. achieves an upper bound of ((d which is tight up to a d factor-a common gap in linear bandits (c.g.. LinUCB). Thus, our upper bound is tight and optimal in m for the linear case.
where 2n (
(p 202
) is the problem in-
stance dependent constant (Wang et al., 2024a;b).
The proof of this theorem can found in Appendix B. The regret bound in (13) consists of two terms. The first term accounts for the number of rounds required to accumulate sufficient information to correctly cluster all users with high probability, and it scales only logarithmically with the num- ber of time steps T. The second term captures the regret after successfully clustering the users, which depends on the number clusters m, rather than the potentially huge total number of users u. Notably, the regret upper bound is not
In the special case where there is only one user (m 1), the regret bound simplifies to O(dvT) kR)), which aligns with the classical results in the single-user linear dueling bandit literature (Saha, 2021; Bengs et al., 2022: Li et al., 2024). Compared to the previous works on clustering of bandits
6

---

Online Clustering of Ducling Bandits
with linear reward functions (Gentile al., 2014; Wang al., 2024a; Li al., 2019), our regret upper bound has extra dependency on 1/Ky- Since Ky < 0.25 for the logistic function, this dependency makes our regret upper bound larger and hence captures the more challenging nature of the preference feedback compared to the numerical feedback in classical clustering of linear bandits.
4.2 also shows that the regret upper bound of CONDB is sub-linear in T, and becomes improved the number of users belonging to the same cluster is increased on average (i.e., when the number of clusters m is smaller). Moreover, in the special case where the number of clusters is m = 1, the regret upper bound in (17) becomes the same as that of the standard neural dueling bandits (Verma et al., 2024).
4.2. Clustering Of Neural Dueling Bandits (CONDB)
5. Experimental Results
Let H' = E'= (t)() Mags" in which 2)(t)= = g 0o) (z 0o) and CR denotes all pair- wise combinations of K arms. Then, the effective dimension d is defined as follows (Verma et al., 2024):
We use both synthetic and real-world experiments to evalu- ate the performance of our COLDB and CONDB algorithms. For both algorithms, we compare them with their corre- sponding single-user variant as the baseline. Specifically, for COLDB, we compare it with the baseline of LDB IND, which refers Linear Dueling Bandit (Independent) (Bengs et al., 2022), meaning running independent classic linear dueling bandit algorithms for each user separately; simi- larly, for CONDB, we compare it with NDB IND, which stands for Neural Dueling Bandit (Independent) (Verma et al., 2024).
d = log det
A H' 11). A
(15)
The definition of d considers the contexts from all users and in all 7 rounds. The theorem below gives an upper bound on the expected regret of our CONDB algorithm (Algo. 2). Theorem 4.2. Suppose that Assumptions 2.1,
2.4, 2.5 and 2.7 are satisfied (let ((x:)
mmNN (aAN))((r)) (xx; 0o) in Assumption 2.4). As long MANN 2 Poly(T, L, K, 1/m I,,.1/ 1/,o, 1/2,log(1 log(1/5)),
Our experimental settings mostly follow the designs from the works on clustering of bandits (Wang et al., 2024a: Li et al., 2019). In our synthetic experiment for COLDB, we design a setting with linear reward functions: 200 users, K 20 arms and feature dimension of d 20, and construct two settings with m and m = 5 groundtruth clusters, respectively. In the experiment with the MovieLens dataset (Harper & Konstan, 2015), we follow the experimental setting from Wang et al. (2024a), a setting with 200 users. Same as the synthetic experiment, we choose the number of arms in every round to be K = 20 and let the input feature dimension be d 20. We construct setting with m 5 clusters. We repeat each experiment for three independent trials and report the mean + standard error.
COLDB.
then the expected regret of the CONDB algorithm (Algo. 2)
for T rounds satisfies
RT 0
0
u(
d
1
log T+
f((x) = 0. x. We choose
R2
22
X2
Vil
+ BV
v ddmT
(16)
K6
K6p
Vā
= =0((
+ B
v dmT)
(17)
Ky
Ky
The proof of this theorem can be found in Appendix C. The first term in the regret bound in Eq. 16 has the same form as the first term in the regret bound of COLDB in (13),,) except that the input dimension d for COLDB (13) is replaced by the effective dimension d for CONDB (E6.(16)). As discussed in Verma et al. (2024), d is usually larger than the effective dimension in classical neural bandits (Zhou et al., 2020; Zhang et al., 2021). This dependency. together with the extra dependency on 1/ 1/Ki,, reflects the added diffi culty from the preference feedback compared to the more informative numerical feedback classical neural bandits.
Fig. I plots the cumulative regret of our COLDB and the baseline of LDB IND. The results show that our COLDB al- gorithm significantly outperforms the baseline of LDB IND in both the synthetic and real-world experiments. Moreover, Fig. (a) demonstrates that when m (i.e., when larger number of users belong to the same cluster on average), the performance of our COLDB is improved, which is consisent with our theoretical results (Sec. 4.1).
Similar to COLDB (Theorem 4.1), the first term in the re- gret upper bound of CONDB (Theorem 4.2) results from the number of rounds needed to collect enough observations to correctly identify the clustering structure. The second term corresponds to the regret of all users after the correct clustering structure is identified, which depends on the num- ber of clusters m instead of the number of users u. Theorem
We also construct both a synthetic and real- world experiment to evaluate our CONDB algorithm. Most of the experimental settings are the same as those of the COLDB algorithm described above. The major difference is that instead of using linear reward functions, here we adopt a non-linear reward function, i.c., a square function: f((x) = (0) x)². The results in this setting are plotted
CONDB.
7

---

Online Clustering of Ducling Bandits
1238
recently, papers by (Wang et al., 2024a; Dai et al., 2024a) and (Wang et al., 2024h; Dai al., 2022) examine the design of robust CB algorithms in the presence of model mis- specifications and adversarial data corruptions, respectively.
COLOR (m=1, sum)
COLDS Joars)
11:9
COLOB (m sun)
LO5,
340
1039
300
230
All these works in CB assume the agent recommends a sin- gle arm per round, with a real-valued reward reflecting user satisfaction. However, this does not apply to scenarios such as large language models seeking user preference feedback to improve the model, where users provide binary feedback comparing two responses. To the best of our knowledge, this paper is the first to consider ducling binary feedback in the CB problem.
25000
100033
200
150000
1h 0e-90aas
(a) Synthetic
(b) MovieLenn
Figure 1. Experimental results for our COLDB algorithm with linear reward function.
1600
CONDE inn2, sum
1750
CONIE (aan))
Cumu lastvvavve Regrok
1200
6.2. Dueling Bandits and Neural Bandits
+250
Cumulative
800-
Dueling bandits has been receiving growing attention over the years since its introduction (Yue & Joachims, 2009; 2011; Yue et al., 2012) due to the prevelance of preference or relative feedback in real-world applications. Many earlier works on dueling bandits have focused on MAB problems with finte number of arms (Zoghi et al., 2014b; Ailon et al., 2014; Zoghi et al., 2014a; Komiyama et al., 2015; Gajane et al., 2015; Saha & Gopalan, 2018; 2019a;b; Saha & Ghoshal, 2022: Zhu et al., 2023). More recently, con- textual dueing bandits, which model the reward function using a parametric function of the features of the arms, have attracted considerable attention (Saha, 2021; Saha & Krish- namurthy, 2022; Bengs et al., 2022; Di et al., 2023; Li et al., 2024; Verma et al., 2024).
750
.000
2000
3000
5000
250
4000
6000 Rerations
8000 10000
(a) Synthetic
(b) MovieLens
Figure 2. Experimental results for our CONDB algorithm with non non-linear (square) reward function.
in Fig. 2. Our CONDB algorithm achieves significantly smaller cumulative regrets than the baseline algorithm of NDB IND in both the synthetic and real-world experiments. Moreover, Fig. 2 (a) shows that the performance of our CONDB is improved when a larger number of users are in the same cluster on average, i.e., when m = 2. These results demonstrate the potential of our CONDB algorithm to excel in problems with complicated non-linear reward functions.
To apply MABs to complicated real-world applications with non-linear reward functions, neural bandits have been pro- posed which use a neural network to model the reward function (Zhou et al., 2020; Zhang et al., 2021). Recently, we have witnessed significant growing interest in further improving the theoretical and empirical performance of neu- ral bandits and applying it to solve real-world problems (Xu et al., 2020: Kassraie & Krause, 2022; Gu et al., 2021; Nabati et al., 2021; Lisicki et al., 2021; Ban et al., 2022; Ban & He, 2021a; Jia et al., 2021;
6. Related Work
Our work is closely related to: online clustering of bandits (CB), dueling bandits, and neural bandits.
Souyen--Tag& et al., 2022; Zhu
6.1. Clustering of Bandits
et al., 2021; Kassraie et al., 2022; Salgia et al., 2022; Dai
et al., 2022; Hwang et al., 2023; Qi et al., 2023; 2024). In particular, the work of Ban et al. (2024) has adopted neural network meta-learner for adapting to users in different clusters within the framework of clustering of bandits, and the work of Verma et al. (2024) has combined neural bandits with dueling bandits.
The concept of clustering bandits (CB) was first introduced in (Gentile et al., 2014), where a graph-based approach was proposed for solving the problem. In subsequent work, (Li et al., 2016) explored the incorporation of collaborative effects among items to aid in the clustering of users. Further extending this idea, (Li & Zhang, 2018) tackled the CB problem in the context of cascading bandits, where feedback is provided through random prefixes. Another direction of this research, presented in (Li et al., 2019), investigates the scenario where users have varying arrival frequencies. In (Liu et al., 2022; Yang et al., 2024), federated settings for CB are proposed, which addresses both privacy concerns and the communication overhead in distributed environments. More
7. Conclusion
In this work, we introduce the first clustering of dueling bandit algorithms for both linear and non-linear latent re- ward functions, which enhance the performance of MAB with preference feedback via cross-user collaboraiton. Our
8

---

Online Clustering of Ducling Bandits
algorithms estimates the clustering structure online based on the estimated reward function parameters, and employs the data from all users within the same cluster to select the pair of arms to query for preference feedback. We derive upper bounds on the cumulative regret of our algorithms, which show that our algorithms enjoy theoretically guaran- teed improvement when a larger number of users belong to the same cluster on average. We also use synthetic and real-world experiments validate theoretical findings.
Intelligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
Dai, X., Wang, Z., Xic, J., Liu, X., and Lui, J. C. Con- versational recommendation with online learning and clustering on misspecified users. IEEE Transactions on Knowledge and Data Engineering, 2024a.
Dai, X., Wang, Z., Ye, J., and Lui, J. C. Quantifying the merits of network-assist online learning in optimizing network protocols. In 2024 IEEE/ACM 32nd Interna- tional Symposium on Quality of Service (IWQoS), pp. 1-10. IEEE, 2024b.
Acknowledgement
The work of Qinghua Hu is supported by the National Natu- ral Science Foundation of China (Key Program under Grant
Dai, Z., Shu, Y., Low, B. K. H., and Jaillet, P. Sample- then-optimize batch neural Thompson sampling. In Proc. NeurIPS, 2022.
No. U23B2049).
Impact Statement
Dai, Z., Shu, Y., Verma, A., Fan, F. X., Low, B. K. H., and Jaillet, Federated neural bandits. Proc. ICLR, 2023.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Di, Q., Jin, T., Wu, Y., Zhao, H., Farnoud, F,, and Gu, Q Variance- awwre regret bounds for stochastic contextual dueling bandits. arXiv:2310.00968 2023.
Gajane, P., Urvoy, T., and Clérot, F. A relative exponential weighing algorithm for adversarial utility- dueling bandits. In Proc. ICML, pp. 218-222 2015.
References
Abbasi-Yadiee Yadkor,, Y., Pál, D., and Szepesvári, C, Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Gentile, C., Li, S., and Zappella, G. Online clustering of ban- dits. In International Conference on Machine Learning, pp. 757-765, PMLR, 2014.
Ailon, N., Karnin, Z., and Joachims, T. Reducing dueling bandits to cardinal bandits. Proc. ICMI., pp. 856-864. 2014.
Gentile, C., Li, S., Kar, P., Karatzoglou, A., Zappella, G., and Etrue, E. On context-dependent clustering of bandits. In International Conference on machine learning, pp. 1253-1262. PMLR, 2017.
Ban, Y. and He, J. Convolutional neural bandit: Provable al- gorithm for visual- advertising. arXiv:2107.07438 2021a.
Gu, Q., Karbasi, A., Khosravi, K., Mirrokni, V., and Zhou, D. Batched neural bandits. arXiv:2102. 130288 2021.
Ban, Y. and He, J. Local clustering in contextual multi- armed bandits. In Proceedings of the Web Conference 2021, pp. 2335-2346, 2021b.
Harper, F. M. and Konstan, J. A. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19, 2015.
Ban, Y., Yan, Y., Banerjee, A., and He, J. Be-net: Exploitation-exploraiio neural networks in contextual bandits. In Proc. ICLR, 2022.
Hunter, D. R. Mm algorithms for generalized bradley-terry
models. Annals of Statistics, pp. 384-406, 2004.
Ban, Y., Qi. Y., Wei, T., Liu, L., and He, J. Meta clustering of neural bandits. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 95-106, 2024.
Hwang, T., Chai, K., and Oh, M.-h. Combinatorial neural bandits. In International Conference on Machine Learn- ing, pp. 14203-14236. PMLR, 2023.
Bengs, V., Saha, A., and Hüllermeier, E. Stochastic con- textual dueling bandits under linear stochastic transitivity models. In Proc. ICML, pp. 1764-1281 1764-1786, 2022.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Proc. NeurIPS, 2018.
Chu, W., Li, L.., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial
Jia, Y., Zhang, W., Zhou, D., Gu, Q., and Wang, H. Learning neural contextual bandits through perturbed rewards. In Proc. ICLR, 2021.

---

Online Clustering of Ducling Bandits
Kassraie, P. and Krause, A. Neural contextual bandits with- out regret. In Proc. AISTATS, pp. 240-278, 2022.
Nabati, O., Zahavy, T., and Mannor, S. Online limited memory neural-linear bandits with likelihood matching. In Proc. ICML, 2021.
Kassraic, P., Krause, A., and Bogunovic, I. Graph neural network bandits. Proc. NeurlPS, 2022.
Nguyen-Tang, T., Gupta, S., Nguyen, A. T., and Venkatesh, S. Offline neural contextual bandits: Pessimism, opti- mization and generalization. In Proc. ICLR, 2022.
Komiyama, J., Honda, J., Kashima, H., and Nakagawa, H. Regret lower bound and optimal algorithm in dueling bandit problem. In Proc. COLT, pp. 1141-1154, 2015.
Qi, Y., Ban, Y., and He, J. Graph neural bandits. In Proceed- ings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
2023.
Qi, Y., Ban, Y., Wei, T., Zou, J., Yao, H., and He, J. Meta- learning with neural bandit scheduler. Advances in Neural Information Processing Systems, 36, 2024.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th interna- lional conference on World wide web, pp. 661-670, 2010.
Saha, A. Optimal algorithms for stochastic contextual pref- erence bandits. In Pruc. NeurIPS, pp. 30050-30062, 2021.
Li, L., Lu, Y., and Zhou, D. Provably optimal algorithmss for generalized linear contextual bandits. In Proc. ICMI. pp. 2071-2080 2017.
Saha, A. and Ghoshal, S. Exploiting correlation to achieve faster learning rates in low-rank preference bandits. In Proc. AISTATS, pp. 456-482, 2022.
Li, S. and Zhang. S. Online clustering of contextual cascad- ing bandits. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Saha, A. and Gopalan, A. Battle of bandits. In Proc, UAI, pp. 805-814, 2018.
Li, S., Karatzoglou, A., and Gentile, C. Collaborative fil- tering bandits. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 539 0399548,777 2016.
Saha, A. and Gopalan, A. Active ranking with subset-wise preferences. In Proc. AISTATS, pp. 3312-3321, 20
Saha, A. and Gopalan, A. Pac battling bandits in the plackett- luce model. In Proc. ALT, pp. 700-737, 2019b.
Li, S., Chen, W., Li, S., and Leung, K.-S. Improved algo- rithm on online clustering of bandits. In Proceedings of the 28th International Joint Conference on Artificial In- telligence, IJCAI'19, pp. 2923-2929, AAAI Press, 2019. ISBN 9780999241 141.
Saha, A. and Krishnamurthy, A. Efficient and optimal algo- rithms for contextual dueling bandits under realizability. Proc. ALT, pp. 968 994, 2022.
Li, X., Zhao, H., and Gu, Q. Feel-good thompson sampling for contextual dueling bandits. S44::22044000033, 2024.
Salgia, S., Vakili, S., and Zhao, Q. Provably and practically efficient neural contextual bandits. arXiv:2206.00099, 2022.
Lin, X., Dai, Z., Verma, A., Ng. S.-K., Jaillet, P., and Low, B. K. H. Prompt optimization with human feedback. arXiv preprint ar 2rvvv22405. /7346, 2024a.
Verma, A., Dai, Z., Lin, X., Jaillet, P., and Low, B. K. H. Neural dueling bandits. arXiv preprint arXiv:2407.171 12 2024.
Lin, X., Wu, 7.,, Dai, 7., Hu, W., Shu, Y., Ng, S.-K., Jaillet, P., and Low, B. K. H. Use your INSTINCT: Instruction optimization using neural bandits coupled with transform- ers. In Proc. ICML. 2024b.
Wang, Z., Liu, X., Li, and Lui, J. C. Efficient explorative key-term selection strategies for conversational contex- tual bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 2023.
Lisicki, M., Afkanpour, A., and Taylor, G. W. An empirical study of neural kernel bandits. In NeurIPS Workshop Bayesian Deep Learning, 2021.
Wang, Z., Xie, J., Liu, X., Li, S., and Lui, J. Online cluster- ing of bandits with misspecified user models. Advances in Neural Information Processing Systems, 36. 2024a.
Liu, X., Zhao, H., Yu, T., Li, S., and Lui, J. Federated online clustering of bandits. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
Wang, Z., Xie, J., Yu, T., Li, S., and Lui, J. Online corrupted user detection and regret minimization. Advances in Neural Information Processing Systems, 36, 2024b.
Luce, R. D. Individual choice behavior: theoretical analysis. Courier Corporation, 2005.
10

---

Online Clustering of Ducling Bandits
Xu, P., Wen, Z., Zhao, H., and Gu, Q. Neural contextual bandits with deep representation and shallow exploration. arXiv:2012.01780, 2020.
Yang. H., Liu, X., Wang, Z.,, Xie, H., Lui, J. C., Lian, D., and Chen, E. Federated contextual cascading bandits with asynchronous communication and heterogeneous users. In Proceedings of the AAAI Conference Artificial In- telligence, volume 38, pp. 15596-20603, 2024.
Yue, and Joachims, T. Interactively optimizing informa- tion retrieval systems as dueling bandits problem. In Proc. ICML, pp. 1201-1208, 2009.
Yue, Y. and Joachims, T. Beat the mean bandit. In Proc. ICML, pp. 241-248, 2011.
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences, pp. 1538-1556, 2012.
Zhang, W., Zhou, D., Li, L., and Gu, Q. Neural Thompson sampling. In Proc. ICLR, 2021.
Zhou, D., Li, L., and Gu, Q Neural contextual bandits exploration. In Proc. ICML, pp. 11492-
with
11502, 2020.
Zhu, B., Jordan, M., and Jiao, J. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In Proc. ICML, pp. 133337-43065 2023.
Zhu, Y., Zhou, D., Jiang, R., Gu, Q., Willett, R., and Nowak, R. Pure exploration kernel and neural bandits. In Proc. NeurIPS, volume 34, pp. 11618-11630 2021.
Zoghi, M., Whiteson, S., Munos, R., and Rijke, M. Relative upper confidence bound for the k-armed dueling bandit problem. Proc. ICML, pp. 10-18, 2014a.
Zoghi, M., Whiteson, S. A., De Rijke, M., and Munos, R. Relative confidence sampling for efficient on-line ranker evaluation. In Proc. WSDM, pp. 73-82, 2014b.

---

Online Clustering of Ducling Bandits
A. Clustering Of Neural Dueling Bandits (CONDB) Algorithm
Here we provide the complete statement our CONDB algorithm.
Algorithm 2 Clustering Of Neural Dueling Bandits (CONDB)
1: Input: f(Tr,)) Br+By ++1
regularization parameter confidence parameter Br Aip V d 2log(u/8).
Te,,Tr.
((x) -mmax glx; 0o) where On denotes the NN parameters at initialization.
2: Initialization: Vo V1, I..0. 0 0, vi U. complete Graph Go (u, Eo) over U.
Ag
3: for =ort=1,, 1...,,.., do
4: Receive the index of the current user it U, and the current feasible set X;;
5: Find the connected component C. for user i, in the current graph Gt-1 as the current cluster;
6: Train the neural network using {( 2, Mo)3 we(t- IJs,e,, by minimizing the following loss function:
1
0, arg min
Σ m
p 0) h(x,22 0)) + (1 (1- log (h(2,,2; h( ()))
(18)
A
0 00112:
2
7: Calculate the aggregated information matrix for cluster C₁: V,-1 Vo ( (ddx.))
te0
((xx,)))T
8: Choose the first arm Lt,1 arg maX h(x;
9: Choose the second arm øt,2 arg max h(:;;;; 0z) + (Br +
BB++B/22 BV 1pp + +1) [[((()) ((x,,)))
10: Observe the preference feedback: = ( > 21,2), and update history: Dj = {is, C., Cs,2, Us 3sm
11: Train the neural network using all data for user it: {(x,,11 2,,2, be)) by minimizing the following loss function:
0 0, arg min
Σ
(ys log p (M(a),,1;)) h(ar,,2 2; 0)) (1 y*) log (h(,,,2; 0) h( 0)))
TONN
A
0 0
2
(19)
keep the estimations of other users unchanged; 12: Delete the edge (ie, E) E.-1 if
@ 00.0122 f(Ti,)) + f(Te.)
VMNN
(20)
13: end for
B. Proof of Theorem 4.1
First, we prove the following lemma.
Lemma B.1. With probability at least for some E (0, 1), at any E [T]:
| - 00(00 < AA + (2log(u/6) + d log(1 + T. Tr /d))
Vi U,
(21)
Ky Ami (v,e-1)
where Vit-1= A I+ E Eueue u (o(a,)) -om:: - o(xx,2)) T, and Tú denotes the number of rounds of seeing user in the first rounds.
12

---

Online Clustering of Ducling Bandits
Proof. First, prove the following result. For fixed user i, with probability at least 1 - d for some å E (0, at any t E [2]:
0... - 03(1)
v Any /2 d log(1
4Ti, dd))
(22)
Vi.-1
Ky
Recall that f((x)) 0 o(x). In iteration s, define o, 0((x,,1) - 2(x,,2)) And we define Fi.s fi( f((2 0. 0. For any 0y Rd define
Get(0r)= Σ (u(0)05)-100) -10 (1) T. + 20 nE((-1)
For X (0, 1), setting 0, X00 + +(1 12 and using the mean-van value theorem, we get:
Gr,(0p;)) (0,((0))==
vp(0 vpl0f 1100)000000 0.000 + +AI (0 -0p)
(0, constant)
(23)
Define M E>er= Vu(0) + +XI and recall that Va,-1 = Eejs-!!: ~.क. + A. Then we have that b-:
M ł Ky Vi,-1 and that Vi-11 Kr semi-definite matrix. Then we have
M, 1,1- where use the notation M 2 V to denote that M V is positive
(),(( 10 -
GL.((0) G.(O
V M 0..) V
(O,) 20, by definition)
V.
(0: - 0..1) MMM Mi,-MM 10: - Ō...)
2 (0, 11)) M,,
M i11-1 i 0,.)
N. (0; 0,0) Mi.-- (0: 0.t)
2 Nr (0: 01,)) Kp V 0,,))
= x², 00 0,,)) Vi, 0..))
2
N 0, 0.
(as || TT Axx)
Vi.-11
The first inequality is because V ž Ki M M and the second inequality follows from M 2 K2 Vi,--
Note that the V,,t-1 which allows us to show that
A
|A0 Iv = /VO. 5 ANO
Ky X
= /xE 10:l22 S / Aky..
(24)
Using the two equations above, we have that
0, 0n.ll s Kp
(r.( 10
S K₁
Gr
+
1
|
Vi
Kp
(25)
1
A
+V
VVxg
Kyy
Kip
13

---

Online Clustering of Ducling Bandits
Then, let fi. 0r we have:
1
|Gu(00.0|
Σ - p(0, -(0,,0))00 10
by definition of (
1,t-1
Σ
(u(fie)) -m(Fi))) + 2d,
(sce definitions of fi, and fi.s)
x2
sclt 1/: ix=1
6,-11
Σ (u(Si,e) - (Us- - <x)))a + 20
(as ys = =(((,, + +,,i is i= =1)
2
R
*E|t-11:
V
(ulSé.e) vs) Σ
G + x0=,t
E||t-11:
<E(t-1)
Cs
n22
EE|t-11 H:
The last step holds due to the following reasoning. Recall that Oi. is computed using MLE by solving the following equation:
0r. = arg min 0
Σ
Uo log ((( ()xx,)))) + - ys) log / (0T (Bxs))) + 101
(26)
-
Setting its gradient to 0, the following is satisfied:
Σ (N (0TT0))) - va) Ze 20 =0, =0.
(27)
=E(e-3
which is used in the last step.
Now we have
G.
(0.e))
Σ
(28)
v.
-E|t-11
Denote V A A Note that the sequence of observation noises {ex} is Subb-Gaussian. Ky,
Next, we can apply Theorem from (Abbasi-Yadkori al., 2011), obtain
det((V..-1)//2
< 2og
(29)
dott(V)).
sclt 1b: cam
V
which holds with probability of at least
1 8. 8.
Next, based on our assumption that -- < 2, according to Lemma 10 from (Abbasi- Yadkori al., 2011), we have that
det (V,t.1) S (N/K, + /d)
(30)
14

---

Online Clustering of Ducling Bandits
where T3 denotes the number of rounds of serving user i in the first / rounds. Therefore,
det Vit--1 dVt(V)
(N/Kg + 4T/ (1 + 4T, (8/p (2/Kz)d
(31)
This gives us
(det(V..-11122 (V))(
Σ G
S 2 log
S 2log(1/6) + dloo (1 (dx)))
(32)
=E(t-1] fy
Vi
Then, with the above reasoning, have that with probability at least 1-6 8 for some (0, 1), at any t e [T]:
Vdnu + /2log(1/0) + dllog(1 + (f,,e
0.. 00(0) I
(33)
Vi--1
Taking union bound over users, we have that with probability at least 8 for some & E (0, 1), at any / E (T]:
VAK + 22log(u/0) + d
[ -:000 g:00)
Vi E u
(34)
Vi,.-
Rp
Then we have that with probability at least
for all E (T] and all Eu
0.. - o0(0)
0r. (0(6) 00(0)
V..-1
v Aminll Vie-1)
Arp + / llg((u/)) + d dlog(1 + x K2 / Aminn(V....))
(35)
Then, we prove the following lemma, which gives a sufficient time To for the COLDB algorithm to cluster all the users correctly with high probability.
Lemma B.2. With the carefully designed edge deletion rule, after
128d
16
Sud
To 16u log( + 4u max
log(
log
122
8
X2
= =0(u
1
1
+
log
K2
22
8
rounds, with probability least 36 for some 8 (0, 1)) COLDB can cluster all the users correctly.
Proof. Then, with the item regularity assumption stated in Assumption 2.4, Lemma J.1 (Wang et al.. 2024a), together with Lemma 7 in (Li & Zhang, 2018), and applying union bound, with probability at least 1 5, for all U, any t 16
such that Tg log( Sud ). we have:
x X28
Amia Vi.e) 2 27.Te..
(36)
Then, together with Lemma B.1, we have: if Ti, 2 da
log( Sud ). then with probability 2 28, we have:
V An, + / log // 6) log(1 + 1T
[0,,
0000
<
Aminn Vi..-1)
15

---

Online Clustering of Ducling Bandits
/ag + 22log(u/0) + d log(1 + 4Tt,sp/dA
Ky v Ti.
Now, let
ARp + /2loggu/// + dllog11 + 4Tt,kp/d 7
(37)
Kip VnV22
4
Let ANς & 2log(u/0) + dlog(1 + 4T, std/////))) which typically holds (Ne, is typically very small), we can get
2 llog(u/0) - d dlog(1 + 4T, (T //d)
2
(38)
2x 2n²AATi Tia
and sufficient condition for it to hold is
2 log (2/8)
72
(39)
2x da The
128
and
dlog(( + 4 dd)
72
(40)
2n7, NoT
128
Solving (39), we can get
128 (og(
Tu N
(41)
Following Lemma 9 in (Li & Zhang, 2018), we can get the following sufficient condition for Eq.(40):
128d
512
The
log(
(42)
A
AR 2
Let u/6 2 512/ 2o72 which is typically held. Then, combining all together, we have that if
Túe 2 max
128d
log
))
U1
16
log
Sud
}. Vi,,
(43)
X2
X25
then with probability at least 1 - 26, we have
0 o
<</4
(44)
By Lemma in (Li & Zhang, 2018), and Assumption 2.3 of user arrival uniformness, we have that for all
128d
log( " 16
Sud.
To 16u log(
5
+ 4u maxt
log
}}
2
220
=0(u R2 (o(n(1
1
+
log
X2
8
the condition in (43) is satisfied with probability at least - 8.
Therefore we have that for all / 2 To. with probability 2 - 36:
1 0i(0)
Vi Eu.
(45)
Finally, we only need to show that with 00. (o(1)
3 Vi E U, the algorithm can cluster all the users correctly. First,
when the edge (i, I) is deleted, user and user j must belong to different ground-truth clusters, i.e,, |10 0,112 > 0. This because by the deletion rule the algorithm, the concentration bound, and triangle inequality
| 01l12 = |0000 0001)
16

---

Online Clustering of Ducling Bandits
00.t 01,3
0i00) 0..11/ - | - 0
|0.t 01,3
f(Tix)) -((Tia) > 0.
(46)
Second, show that if ||0; 011 7 meaning that user and user I are not in the same ground-truth cluster, COLDB
will delete the edge (i,1) 1) after To. This is because
|0.. 01.5
2 110; - 0:11
0.. (2(1))
- 0 0001)
7 --7 Y 7
4
f(Tr,)) f(Ti.))
(47)
which will trigger the edge deletion rule delete edge (i. 1). Combining all the reasoning above, can finish the proof.
Then, prove the following lemmas for the cluster-based statistics.
Lemma B.3. With probability least 46 for some d 1/41 at any t To:
0, -0:liillvi I VAK + v /2oog(u/0) + dllog1 + 4Txx//d))
(48)
Kp
Proof. First, by Lemma B.2, we have that with prohability at least 1 - 36, all the users are clustered correctly, i.e.,
C. = -jjo), Vt 2 To. Recall that f((x) = 0 Ø(z). In iteration s, define ø. = Φ(x.,1) - 2(x,,2). And we define Fr.s =((o,)) - (2x,2) = 0. S..
For any 0y Fd define
G((0p)= = Σ
3. + 20
i.c0
For X' (0, 1), setting 0 100; + (1 X)) and using the mean-vale theorem, we get:
Σ -E(r-1)
vu(0 71(0 + AI (0) - 0,;))
=
(49)
Define M Σ Ei 71(070))000 AI and recall that V E -ele-1) 6.6. + I. Then we have that GET,
e,
M 2 Kp V and that V 2 K. M, Then we have
(. - 10; 11 V [0,,(0,,) G, MM D.l1
(G. =x0,, by definition)
(0,, T V. - O,)
(0,, 0.) M, 1 M,- 1 0.)
(O.. 0.) Mc-1(0. 0,)
Ni (O.. 0,)T. V-1(0,,. 0₂)
(0, 0.) 0. VV 0.) N 0. 0, V--1
(as || 122 = x -Ax)
The first inequality is because V 2 Ky Mr and the second inequality follows from M Z Kp V--1
17

---

Online Clustering of Ducling Bandits
Note that I Vi-1, which allows us show that
| |! > 0 V, s sAy " tr,
VMi 10 VMSy-
(50)
Using the two equations above, have that
A0illv; 1 |G;l0))-0;,llvv3
1 ||G((:))lv + 1
110: - 0rllvi., I Kip
_
11 1l
Kip
Kip
(51)
- ||G.(B))llv]t +
A
Kp
Then, let fe,- 0 o.. we have:
$
Σ (1(0, - + +x0
(by definition of G. ()))))
xE|t-1]:
2
Σ (u(fe,)) ((F.,)))) +0
(see definitions of Se, and Fi.))
<E|t-1|: 1,002
V-1
1
(u(Je,e) (ys +x,)) + 20;
Kit
<E/t-11:
bEc,
V,
U. = m(Fr.s) + Cgiff = andi, = i4. Vig E C2 Vt 2 To
Σ
(u(Fro)-ua)) -
Σ
c. Ao
xE|--1]
=E((-1)
1
Σ
AE|t-1j:
4EC,
The last step holds due to the following reasoning. Recall that 0, is computed using MLE by solving the following equation:
arg min-
Σ
(ys log (0T (á(x.,1) ((xx,,))) + (1 ys) log (0 [0(2,,2) ((xx,,)))) + 1011 (52)
xE(r-1)
Setting its gradient to 0, the following is satisfied:
Σ -E 6.002
4
3/ 3. + 10 0. 0, 25)
(53)
which is used in the last step.
Now we have
10, -B.lly.n < Kp
1
Σ G
+
V
(54)
Kp
-e|t-1)
V.
18

---

Online Clustering of Ducling Bandits
Denote V I. Note that the sequence of observation noises {+a} is 1-sub-Gaussian. from (Abbasi- Yadaori et al., 2011), to obtain
Ai
Next, we can apply Theorem
det (Ve
Σ
S 2 log
(55)
8 det do)((V)
<Ejt-1]: 6,0
V
which holds with probability of at least - 8.
Next, based on assumption that 6
s 2, according to Lemma 10 from (Abbasi- Yadkori et al., 201 1), we have that
det(VV-1) S (N/K,, + 4T/d)"
(56)
Therefore,
del V.-1 dct(V)
(D/ + 4T//)) (A/Rig))
(1 47 /Tkp/(dA))
(57)
This gives us
<et((V, (
Σ a
< 2lg
S 2 log((1/)) + +dlog (1 + 4TK, (dA))
(58)
deel
+E((-11 II LEC,
Combining together, we have with probability at least for some ó E (0,1/4) at any 2 To:
0. 0..llv., Amp + (oo((u/0) + d dlog(1 4T'K /dAA)
(59)
Then, prove the following lemma with the help of Lemma B.3.
Lemma B.4. For any iteration 1 for all x, x' E Nr with probability of least 46, we have
3T
(t. - 0, (p(x)) ((x'))
[(<(ar)) <lx ((aa'))l 1lv.
Kp
where 3r = AAR, + log(uu/0) + log(1 + 4T'k..dd))
Proof.
(f), (xx)) 0² (x(x)) o(x'))
10,, [(((x) x(x') 0. (d(x) 6(x')]
(0,, 0.) [0(x) o(z'))
0:. 0. fllvi_, (1((x) s(x' )
(60)
Br [10(x) o(x')ll=3)
Ky
in which the last inequality follows from Lemma B.3.
We also prove the following lemma to upper bound the summation of squared norms which will be used proving the final regret bound.
19

---

such that 4kg X Online Clustering of Ducling Bandits
Lemma B.S. With probability least 46, we have
T
The E ((m.))) S 2d (1 + 47 (dx)) Vjj E [m]]
t=
where II denotes the indicator function.
Proof. We denote T. ((x1,1) 6(x1.2). Recall that we have assumed that [10(,111) 0(x122) S 2. It is easy to verify that Vi-1 -/2 Ki I and hence V 3 Re I. Therefore, we have that 0 !
*
Φb
4kg X
We choose À
< 1. which ensures that 0 v
< Our proof here mostly follows from Lemma 11 of (Abbasi-Yadkori Yadkori
et al., 2011) and Lemma J.2 of (Wang et al., 2024a). To begin with, note that log(11 + x) for E 00, 1]. Denote
Vi, = == -et--) Ccc;
~. À I. Then we have that
Ap
Σ 1=
life E Cj) 1
2 log (1+ (1+ liñe E C3} |00 10:1 v,
T=
(log det VT,i log det V)
det VrJ
(61)
2
det V
2 (1 + 4Tkp (dA))
2d log + 4T (dx))
The second inequality follows the same reasoning as equation (57). This completes the proof.
Now we are ready to prove Theorem 4.1. First, we have
R Σ
ST
+
Σ rt>
(62)
t=T
where we use that the reward at each round is bounded by 1.
Then, we only need to upper bound the regret after To. By Lemma B.2, we know that with probability at least 1 - 48, the algorithm can cluster all the users correctly, C, Cj(.)) and the statements all the above lemmas hold. We have that for
20

---

Online Clustering of Ducling Bandits
any 2 To:
Ft = fr, (x/) - (x),) + fr (xt) - fú (2x1,)
(2) 0. (0(=;) - ()),,))) +
ST [[{(=;] ((am)))lv + +0, (x(=z)) - 2(x),2)) + OT
||)(2;;) (62x22))
Ki
Kip
ST [0((x) - -b(at.1)llv
0, (d(z)) - o(2r,1)) +
Kip
8. (o(x)) ((x1,1)) + 0, (6(x)11) - ((x1,2) + BT [lo(z;) 6(x111) + ((x111) - +(x1;2)lv==
Ky
BT 110(x") ((xr,))ll, +
20, (Ø(x*) i() + 2
Ky
Br [10( 0(x112) v=l
0. (0(1),1) - 2(x1,2)
(0)
20: (0(2).2) 1))),.1)) + 2 BT (
((a,,))ll
Rip
BT (10( -2(212) v
0. (0( 2((x122)
Kip
BT
< 0, (0(x).2) - -0(x1,1)) + 3 (1 - -
(d) 3 10( 0(22,2)l
3T
Ki
(63)
Step (a) follows from Lemma B.4. Step (b) makes use of the triangle inequality. Step (c) follows from the way in which we choose the second arm Z,,2 Σ1,2 = arg max o, (Ø(x) - .(x1,1)) + &r |(((z) - ((xx,1)))))))))))) 11l Step (d) results from the way in which we select the first arm: 2t,1 = arg m 0, Φ(x).
Then we have
T
3T
Σ t=
rt
3
((
Kip.
(=To
3T
T
3
Σ
T(i E C3} (1)(01))) ((.22)llv:)
Ki
(= jE[m]
< 3
3r
ΣΣ
Hu E C Σ Σ To JE[m]
T
His E C)Hll((z)1) - -(
Kpp
To JE(m]
< 3 3r
TT. m 2d log (1 + (TTx,/(dd)),
(64)
where in the second inequality we use the Swarchz inequality, and in the last step we use Σts,, Eyem lie e C₁} < T and Lemma B.5.
Therefore, finally, we have with probability at least 46
Rr $ To + +3 Br
V T.m. m log (1 + 4T (d2))
Ki
d
1
5 0(uu
+
log T + dVmmit)
x2
Kp
= 0
dv (VmT).
(65)
Kp
21

---

Online Clustering of Ducling Bandits
C. Proof of Theorem 4.2
C.1. Auxiliary Definitions and Explanations
Denifition of the NTK matrix H, for cluster j. Recall that we use Tÿ to denote the total number of iterations in which the users in cluster served. For cluster j. let ( K be set of all T3 x K possible arm feature vectors: ( sessss,,,,,,s KS where = K (tt-1)+ +a. Firstly, we define h, = | (2(0))) x i.e. he the Tý K -ddimennionaal
vector containing the reward function values of the arms corresponding to cluster j. Next, define
Σ p-q
H P.
=(1 (z(p)) ((()) Apg =
=
Σ
(2)
Σ (t)
P.T
[1++) ))
= 2
(V. [maxfu, u, 0} max ( 0,,
P.9
(a.v)) (1 2 0)1(;: 2 0)] + [(++1) With these definitions, the NTK matrix for cluster j is then defined as H = (A (D) + 1/2
H = 2H (1)
P-g
p.j
The Initial Parameters oy. Next, we discuss how the initial parameters 0g are obtained. We adopt the same initialization
W
0
method from Zhang et al. (2021); Zhou et al. (2020). Specifically, for each | L 1, let Wi-
in
0
W
which every entry of W is independently and randomly sampled from (0, 4/msw), and choose WL = (w" -W in which every entry of w is independently and randomly sampled from (0, 2/ 2/mNN).
Justifications for Assumption 2.5. The last assumption in Assumption 2.5, together with the way we initialize Gu as discussed above, ensures that the initial output of the NN is O: h(r; 0o) = 0, Vr E X. The assumption of x; = d//+d/2 from Assumption 2.5 is a mild assumption which is commonly adopted by previous works on neural bandits (Zhou et al., 2020; Zhang et al., 2021). To ensure that this assumption holds, for any arm æ, we can always firstly normalize it such that ||ر||| = 1, and then construct a new context x' (x x TT /T/2 to satisfy this assumption (Zhou et al., 2020).
C.2. Proof
To begin with, we first list the specific conditions we need for the width mNN of the NN:
INNN 2 K L log (2))T//KK///// m m) 2 CR 2 1
(66)
mNN 3 > 3xp31111 2 x mNN (log m 2 CT 18 -8
for some absolute constant > O. To ease exposition, we express these conditions above as miN >
poly(T, K, 1/Kp: Ly, 1/>o, (og(/)))..
In our proof here, we use the gradient of the NN at On derive the feature mapping for the arms, i.e., we let Φ(x)) g(x: /MNN. We use θ., denote the paramters of the NN after training in iteration t (see Algorithm 2).
We use the following lemma to show that for every cluster j E C, its reward function f can be expressed as linear function with respect to the initial gradient g 0o).
Lemma C.1 (Lemma B.3 of (Zhang et al., 2021)), As long as the width m of the NN is large enough:
mNN 2 CVT L 2 L/8)//
then for all clusters j E [m], with probability of at least 1 8, there exits 8) such that
f((x) = (o) 03 00),
v V
07 0 < 22h H h $ B.
for all x E Xr 1 E (T] with i, E C,,.
22

---

Online Clustering of Ducling Bandits
Lemma C.1 is the formal statement of Lemma 2.6 from Sec. 2.2. Note that the constant B is applicable all m clusters.
The following lemma converts our assumption about cluster separation (Assumption 2.7) into the difference between the linearized parameters for different clusters.
Lemma C.2. If users i and belong different clusters, then we have that
VmNN |10 - f 2 7
Proof. To begin with, Lemma C.I tells us that
(f())) - fi())) = O,); -0,,)1 5 (1; 110 - 0-,1l
(67)
This leads
(f(()) - fi(æ))
- - 2
(68)
11 0o)l
VnNN
in which we have made use of Assumption 2.7 and our assumption that This completes the proof.
(g(x; 0o). ga;; 0o)) S in the last inequality.
The following lemma shows that for every user, the output of the NN trained using its own local data can be approximated by linear function.
C2mii -1/6 'log mANL3 3 (+) 4/3 where C2 > 0 is an absolute constant. Then
Lemma C.3. Let mm
[g([;; On), Oi. Oo) h(w; 0c.))l S E em Vt [T), x x' X.
Proof. This lemma can be proved following a similar line of proof as Lemma from Verma et al. (2024). Here the & in E'msuut can in fact be replaced by Ti, I t, however, we have simply used its upper bound for simplicity.
Lemma C.4. Let 37 & 1 Kp v d log(u/6). Assuming that the conditions on myN from Equation (66) are satisfied. With
probability of at least we have that
BT B
A
+1
/mn |0 1
E [T].
Amin ((.e-1)
where Vi,-1
g 0o). and Tr, denotes the AI E (0x (0((())))) 2(xx,2)) 6(x)
Ky number of rounds of seeing user in the first t rounds.
Proof. In iteration I, for any user E U, the user leverages its current history of observations ((x,,1, Ø2 se)) to train the NN by minimizing the loss function (equation (19)), to obtain the NN parameters 0..-- Note that the NN has been trained when the most recent observation in {(.r,,1, 22,2, Ms. (x)))=tte (=j])))))___-=== was collected, i.e., the last time when user was encountered. Of note, according to Lemma C.I. the latent reward function of user i can be expressed as fz( = (g(x; 0o), f, 0o). Therefore, from the perspective of each individual user i, the user is faced with neural dueling bandil problem instance. As a result, we can modifying the proof of Lemma from Verma et al. (2024) to show that with probability of at least 1 - 5,
A Ky
MNN
00 0,,
< Br
+
B
+
VE E
Vi,--1
d 2 log(u/5), we have replaced the error probability 8 (from Verma et al. (2024)) by 8/u a account for the use of an extra union bound over all u users.
Here in our definition of Br A 1
My
23

---

Online Clustering of Ducling Bandits
This allows to show that
VINNN 0 Os.e Vi.e-
00.5 0..0 x
MNN
Vamin (iic-1)
(69)
BT +
Amin (v,--))
This completes the proof.
Lemma C.5. With the carefully designed edge deletion rule in Algorithm 2, after
32 [ 2log(u/0)
24udm² (I. 111
To - 16u log( ")) + 4u max
log(
i07222
X3
X2.
=0
d
log log(z)
K2t
X3
rounds, with probability at least 1 - 36 for some 8 E (0, }) CONDB can cluster all the users correctly.
Proof. Recall that we use p == dmNN + (L -) 1) + mNN to denote the total number of parameters of the NN. Similar to the proof of Lemma B.2, with the item regularity assumption stated in Assumption 2.4, Lemma J.1 in (Wang al., 2024a), together with Lemma 7 in (Li & Zhang, 2018) (note that when using these technical results, use g(:; 0)/ VINNN the feature vector to replace the original feature vector of æ;), and applying union bound, with probability least 1 5, for all we have:
i U, at any such that T5 2
16
log(
Sup
X
X25
Amii Vi,1) 2 2A.
(70)
Note that compared with the proof of B.2, in the lower bound on Ti, here, we have replaced the dimension d by p. This has led to logarithmic dependence on the width miN of the NN. To simplify the exposition, using the fact that 3dm [L 1),
we replace this condition on T.e by slightly stricter condition: Th 2 16
log( 3dm (f-
16
log( 24ndmn (T.
XX
X
X2
X
Then, together with Lemma C.4, we have: if Ti 2
16 X2
log
3dm (I.-1) 1)
then with probability 2 1 - 25, we have:
X25
BT B +1
BT B
+1
VNNN Ōu. 0510
<
V Amiu Vi,c-1)
22
Now, let
Br + BV
X +1 Gr
2
(71)
/ 25 Ti,t Ti.t.
Note that in Algorithm 2, we have defined the funciton f as
3r + B 2 +1
f(T..) 2
(72)
12,TT..
This immediately leads to
MNN 10.. g0(0)
< {T(T.)) < 2
(73)
24

---

Online Clustering of Ducling Bandits
For simplicity, now let BV
A Mp
+ < BT which is typically satisfied. This allows us to show that
32
V d 2log(u/6)
32 (d+ 2log(u/0))
32
Ap
T
(74)
2x?
227
Combining both conditions on T together, we have that
32 d 2log(u/6)
16
24udm (L
Tu 2 max
log(
(75)
2 k2.
X
125
By Lemma in (Li & Zhang, 2018) and Assumption 2.3 of user arrival uniformness, we have that for
32 ( 2 2log(u/0)
16
24udm (L 1)
To
16u log(
4u max
log(
2
1
235
=0
d
log( 1 8
122
72
X2
the condition in (74( is satisfied with probability at least
5.
Therefore we have that for all & To. with probability 1-130 30:
v MNN
< Vi Eu.
(76)
Finally, we show that as long as the condition MINN 0,, - 0066) correctly.
2/2 E U, our algorithm can cluster all the users
First, show that when the edge (i, is deleted, user i and user j must belong to different ground-truth clusters, i.e., |0 0اuرر2 > O. This is because by the deletion rule of the algorithm, the concentration bound, and triangle inequality
/mux// 10
05.112 = VINN (266) (:(1)
2
0,,1 01,1
VINNN @0(0)
01.4
V (0()) 01.0
MNNN
N MINN
0.. θ,,1 [(T:.)) [(Ti,)) 0.
(77)
Second, we can show that if [.f((x) - f((x)) 2 7,, Vx E X. meaning that user i and user I are not in the same ground-truth cluster, CONDB will delete the edge (i,, 1) after To- Note that when user and user I are not in the same ground-truth cluster, Lemma C.2 tells us that VIINN O0 اار r/ Then we have that
VINN 02.. 00.
v MNN
00
f
VINN
Qi(()
VITNNN [O.. O001)
7
2
>
4
7
f (T.,)) + (TT.))
(78)
2
which will trigger the edge deletion rule to delete edge (i, l). This completes the proof.
Then, we prove the following lemmas for the haase statistics.
25

---

Online Clustering of Ducling Bandits
Lemma C.6. Assuming that the conditions on m from Equation (66) are satisfied. With probability at least 1 46 for some ō E (0, 1/4), at any t. 2 To:
A Ky
Vmww 1,,5 Bellv- S 5
B
11
VA E
Proof. To begin with, note that by Lemma C.5, we have that with probability of at least 1 - 36, all users are clustered correctly, i.e., C₁ = C)6,) vt 2 To. Note that according to our Algorithm 2, in iteration t, we select the pair of arms using all the data collected by all users in cluster C, That is, 0g represents the NN parameters trained using the data from all users in the cluster C₁ (i.e., {I..1, 22, yo ())),,)t-1,, ) and V; also contains the data from all users in this cluster C2. Therefore, in iteration t, are effectively following neural dueling bandit algorithm using { 22,2 Me)] sejt as the current observation history. This allows us to leverage the proof of Lemma 6 from Verma et al. (2024) to complete the proof.
Lemma C.7. Let emmmt - C2
1/6 Vlgg mAx (4) 4/3 where C2 > O is an absolute constant. Then
Kg(æ; 0o) - g(0'; On), 0. 0o) (h(æ;; 0.) h(<'; 0,)1 s 2 2 E aT) E N..
Proof. This lemma can be proved following similar line of proof Lemma I from Verma et al. (2024).
Lemma C.8. Let 8 E 10, emmi, = C2mmiN -1/ Vlog mANLL (4) (4) for some absolute constant C2 > 0. As long as MAN 2 poly(T, L, K, u, 1/ Lux 1/ 1/,, 1og(1/8), then with probability of at least 1 - 6, at any t 2 To.
(x) - fx,(x') (x') [M(:; 0.) l1(2; =aa S OTO 120, x') + 2
for all v, x' E & (T).
Proof. Denote ((x) = ViTNn (xx; On). Recall that Lemma C. tells us that fú, (ax) - (o) Oss. -0o) = =(6(x), 5
0o) for all K, E [T]. To begin with, for all æ, x' E Nr, [T] we have that
(x) fú, (a') (g(2; 0o) g(0'; 0o), O. 0o3l
Kg(æ; 0o) g(a': 0u), fy. Go) (g(x; Qu) - g(0'; 00). D. -oo)
= =K((2;; 0n) g(æ0; On), 0y. O.)I
=Ko(x) - o(x'), VINN (0,,., B.)I
(79)
S [1(((z) - <(x')))l 1 VINNN 110 0.ll
< [l(((2)) - ((x')) (()')))]==
(1 (8x+B) B Kp
++11
in which we have used Lemma C.6 in the last inequality. Now making use of the equation above and Lemma C.7, we have that
(x) (x') (h(x; 0₂) h(x';0)))
(z) f(,('') (g(2; 0o) g(x'; 0o), 0. -0o)
+ (g(x;; 0v) - g(x': 0o), 0, 0.) - (h(x:; D.) - -h(x'; (.))
< (x)) - [1('))) (g(;;; 0o) g( 0o), O: -0o)
(80)
+ (g 0o) g( 0o), O2 Oo) (1(x:; 0.) hhla': 0.))
<
(o(x) - 6(x'))
Br + B
+ 1
+ 2 '
TINN
Kp
This completes the proof.
26

---

Online Clustering of Ducling Bandits
We also prove the following lemma upper bound the summation of squared norms which will be used in proving the final regret bound.
Lemma C.9. With probability at least 46, we have
T
((212)l) $ 16d, vj E [m],
To
where denotes the indicator function.
Proof. We denote कe = ((27,1) ((x+22) Note that we have defined (6xx) /inws 7i v(:; On). Here we assume that [ (xx,,))l Virani [19(2 Bb) g 00)ll2 S 2. Replacing 2 by an absolute constant co would only
change the final regret bound by constant factor, omit it for simplicity.
easy to verify that V.-1 z A and hence V 3 x
Therefore, we have that
c
We choose such that 48p X S 1, which ensures that
S Our proof here mostly follows from Lemma 11 of
v,
(Abbasi- Yackor- al., 2011) and Lemma J.2 of (Wang et al., 2024a). To begin with, that s log(1 1 +x) for x e [0, 1].
Denote Vi, = Σ -en-1 0.O, + Then we have that
T
T S
Σ t=
The E
Σ 2log
1 C3) (3)
T=
(81)
Ki H +1)
16 log del
A
- 16d.
The second inequality follows from the proof in Section A.3 from Verma et al. (2024). This completes the proof.
Now we are ready to prove Theorem 4.2. To begin with, we have that Ry = -E S To Σ Tt.
Then, we only need to upper-bound the regret after To. By Lemma C.5, we know that with probability at least 1 - 48, the algorithm can cluster all the users correctly, C, = Cj(c.)- and the statements all the above lemmas hold. We have that for any 2 To:
27

---

Online Clustering of Ducling Bandits
To simplify exposion here, denote 34 _ BT B///FF +
T2 (x;) fú. 11), + (x]) fú, (x).2)
( S (o(0;;; 00) - g( 0o), 0: - 0o) + B7 [1)();; - ((2).1) )1l v, +
(g(x);; 8o) 2( 00), 0 - 8o) + B7 [0(2;) 6(22,2) [,
(a(=;; On) s( 0o), 0 - 0o) + 8y [0(x)) -6(0),1)) v, 1
(g(0)); 0o) g( 0o), 0, - 0o) (3( g(002 On), 0. 00)+
B/r [((()) ((x(11) + ( - ) vi
(6)
- 2(g(2]; 0o) g( 0o), 0. 0o) + lld(x;) - 6(2m,))l +
(g( 0o) g( 0()),2;00). B - 0o) + Br (()(x)11) 0(21,2))ll
(82)
2
2 2h(x;; 0t) 2 0z) + 4 m . + 2 [(((a;) -00r, +
h( 0.) h( 0.) + 22 msn. + 8/ 11)(2.11) o(0r,))llv
(4)
S 21(2022 0c) 21( 0.) + 2,3// [ - o (x., || +
h( 0,) - h(xr,2; 0.) + 6E 6e t + 8 ( - (
h(xr,2 0.) h(xx,,1 0.) + 3,5 1 - o (2),2))lv; + 6GEmNN
2 3,3 (1)( (( + Germsn.
Step (a) follows from Equation 79, step (b) results from the triangle inequality, step (c) has made use of Lemma
C.7. Step (d) follows from the way in which we choose the second arm Z4,2 24,2 = arg max Mæ:;) 0.) +
V arg m h(2; 0.).
(Br + B A +11 [(((z)) - (ar,))ll Step (e) results from the way in which we select the first arm: Tt,1 =
Then we have
T
T
Σ To
ri
S 38/
Σ
-0(x)))))l v + 67's -6T'emmw mon,
t=
T
= -3 Σ
Hie E Czb1lo(az.)) - ((2,,))ll + +6T 6TT''msnT Σ
S 3,4
Σ
Σ Tfir EC, Σ Σ
Tii (o)) - Ma.2)) + 6T T
(=To jE[m)
TE/m]
$ 3, / TT.mmm.m... m 16d + 6T''muu.
(83)
< 128 VT m d+ 6T'
(84)
where in the second inequality we use the Cauchy-Swarchz. inequality, and the last step we use Σ Eje(m T(e E J3} < T and Lemma C.9. It can be easily verified that as long as the conditions on m specified in Equation (66) are satisfied
(i.c., as long as the NN is wide enough), we have that 67 67 < 1.
Recall that By 2 BT + B/A/F + and 3T A 1 V / 2 2lo(u//). Therefore, finally, we have with probability at least 1-48 46
Rr & To 12(37 By A/Eg 1) T m 7+1
28

---

Online Clustering of Ducling Bandits
Vd
1 +
A
V dmnl
0
u(
log T
+
B
72
X
Kip
Kija
Vd
A
Vāmr
B
(85)
Kip
Kip
29


Reviews:
[{"review_id": "KISKwbOoku", "reviewer": "Reviewer_WQTH", "summary": "The paper introduces the first algorithms for clustering users in dueling bandit settings where feedback is based on preferences between pairs of items rather than absolute numerical rewards. The authors propose two novel approaches: \n\n- Clustering of Linear Dueling Bandits (COLDB) for linear reward functions \n\n- Clustering of Neural Dueling Bandits (CONDB) for non-linear reward functions modeled by neural networks. \n\nBoth algorithms adaptively group users with same preferences into clusters, allowing collaboration by sharing data within clusters.\n\nThe authors provide theoretical analysis showing that both algorithms achieve sub-linear regret bounds that improve when more users belong to the same cluster. Their analysis quantifies the benefits of cross-user collaboration in preference-based feedback scenarios. Experimental results on both synthetic and real-world (MovieLens) datasets demonstrate that the proposed methods outperform independent dueling bandit baselines, validating the theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable suggestions. Our responses are as follows. We will incorporate them after revision.\n\n**Q1**: Lemma B.2, C.5, and more robust deletion: \n\n**A1**: We will emphasize these lemmas in the main text. Our edge deletion mechanism and analysis follow prior clustering of bandits (CB) works. For stronger early-stage robustness, the algorithms can be modified to restart with a complete graph each round and re-check edges involving previously served users. This ensures correct clustering w.h.p. after $T_0$, mitigating early-stage misclusterings. \n\n**Q2:** Definition of f: \n\n**A2**: We have defined f at the Input of Algo.1 (top of page 6) it's used in the proof without restating. We will redefinie f in the proof.\n\n**Q3:** Setting of similar preference in clusters: \n\n**A3:** As the first to study preference feedback in CB, we focus on standard assumptions to address its core challenges. While similar-preference settings with numerical feedback have been studied (Ban & He, 2021b; Wang et al., 2024b), extending our results to that setting is an independent direction which we leave for future work.\n\n**Q4:** Terminology of \"user collaboration\" and the question about the limited shared information setting: \n\n**A4**:\n- We will replace “user collaboration” with clearer terms like “user relation” or “user similarity” as per your advice.\n- For scenarios without centralized coordination or with limited shared information, these fall within the scope of federated bandits. Since our work follows the standard CB setting, such extensions are beyond our current scope, but we view this as a promising future direction.  \n\n**Q5**: Assumptions (particularly uniform arrival): \n\n**A5**: Our assumptions follow standard practice in CB and are used solely for theoretical analysis. The uniform arrival assumption can be relaxed to general distributions (Lines 161–164). \n\n\n**Q6:** Computation of CONDB: \n\n**A6:** Even in the baseline where each user runs NDB independently, an NN must still be trained per iteration—yet this incurs higher regret (scaling with $\\sqrt u$). Our CONDB trades off computation for better performance. To reduce computational overhead, we can adopt batched training strategies (e.g., \"Batched Neural Bandits\" (Gu et al., 2024)), updating the NN only every few iterations.\n\n**Q7:** Techinical challenges\n\n**A7:** The dueling (and neural) feedback introduces new technical challenges to the classic CB study. Please kindly refer to our **A1 in response to Reviewer AU83** for details.\n\n**Q8:** Lower bounds: \n\n**A8:** Following Wang et al. (2024a) and Saha (2021), we can derive a lower bound of $O(\\sqrt{dmT})$ for linear case. Algo.1 achieves an upper bound of $O(d\\sqrt{mT})$, which is tight up to $\\sqrt d$—a common gap in linear bandits (e.g., LinUCB). So our upper bound is tight and optimal in $m$ for the linear case.\n\nFor the neural case, lower bounds remain open even in the single-user setting. However, we hypothesize that our bound is also optimal in $m$ in the neural setting, as clustering naturally introduces a $\\sqrt m$ scaling over the single-user case.\n\n**Q9:** Experiments:\n\n**A9**: Our main contribution is theoretical, but we have added experiments as per your advice to support our findings. Due to time constraints, we leave more extensive experiments as future work.\n\n**(1) Only two datasets**: We added an experiment with the Yelp dataset (see [figure](https://postimg.cc/QHS7rsbP)). \n\n**(2) Ablation for m**: We added an additional value of m=4 (see [figure](https://postimg.cc/qg74j037)), the results are consistent.\n\n**(3) Non-uniform arrival**: We included experiments under non-uniform arrivals, which show consistent performance gains (see [figure](https://postimg.cc/pyr3wNjd)). The user arrival probabilities are randomly sampled from a Dirichlet distribution with a concentration parameter of 10.\n\n**(4) Baselines beyond independent dueling bandits**: Prior CB methods do not handle preference feedback, so direct comparisons are not applicable. Second, following standard CB practice, it is common to use independent per-user algorithms as baselines when introducing a new setting.\n\n**(5) More complex non-linear functions**: We tested a more complex function: $ (\\theta^T x)^4 + cos(\\theta^T x)$. CONDB still consistently outperforms the baseline (see [figure](https://postimg.cc/1gpyVkBS)).\n\n**(6) Confidence intervals**: We have indeed included confidence intervals (Lines 369-371 and the figures).\n\n**Q10:** NTK: \n\n**A10:** The NTK assumption follows standard practice in neural bandit theory and is used only for analysis; in practice, very wide networks are not needed. Our experiments indeed use small NNs—1 hidden layer with 32 nodes—which already achieve strong performance.\n\n**Q11:** LLM application: \n\n**A11:** The recent work \"Prompt Optimization with Human Feedback\" uses neural dueling bandits for prompt optimization. Our methods can be directly applied to extend their method to the multi-user setting.", "claims_and_evidence": "Most claims are supported by theoretical analysis and empirical evaluation, but with some limitations:\n\nThe theoretical regret bounds for both algorithms are well-established with detailed proofs. The authors show that when clustering works correctly, the regret scales with the number of clusters (m) rather than the number of users (u), providing a formal justification for clustering benefits.\n\nHowever, the empirical evidence is somewhat limited. While the experiments show improved performance over independent baselines, the paper only evaluates two datasets with a small number of simulation settings. The experimental section lacks ablation studies to understand the contribution of different algorithm components, sensitivity analyses for key parameters, and comprehensive evaluations across diverse scenarios.\n\nThe claim of correct clustering convergence is supported theoretically (Lemma B.2 for COLDB and Lemma C.5 for CONDB), but these critical lemmas are barely mentioned in the main paper. Additionally, there is confusion around the edge removal mechanism and its notation, as the function 'f' is not clearly defined when discussing step 8 in both algorithms yet plays a central role in the proofs.\n\nNot sure if this is the right place to mention : \n- The problem setup of Same preference seems is quite restricted and may limit real-world applicability. A setup with similar preference (same preference with some error tolerance) might be more lucrative. \n- The paper repeatedly refers to \"cross-user collaboration,\" \"user collaboration,\" and similar terms, but this terminology is seems slightly misleading. What the paper actually describes is centralized information pooling and model sharing managed by a single algorithm, not active communication between users. Users are passive participants, and all \"collaboration\" is implicitly facilitated through the central algorithm. The authors should clarify this distinction to avoid misrepresenting the nature of their contribution, especially since true cross-user communication would involve different theoretical and practical challenges. \n- The algorithms assume a central entity with access to all user data, uniform user arrivals, discrete and fixed clusters of users, and the ability to run potentially expensive computations for every interaction. Many practical applications, especially those involving privacy concerns or distributed systems, would violate these assumptions. The paper would be strengthened by discussing these limitations and how the approach might be adapted to more realistic constraints.", "methods_and_evaluation_criteria": "The proposed methods -- CONDB and COLDB -- build upon established techniques in bandits literature and make sensible extensions to the preference-feedback setting. The graph-based clustering approach with adaptive edge deletion is reasonable for identifying user groups with ***same*** preferences.\n\nHowever, there are substantial concerns about practicality. The paper's motivation mentions scenarios with large numbers of options, but CONDB requires running neural networks for each round twice for every round of the for-loop, which is computationally expensive and not scalable for real-world applications. This mismatch between motivation and implementation raises questions about real-world applicability.\n\nThe evaluation criteria involving cumulative regret is standard and appropriate for the bandit setting, but the experimental evaluation is limited in several ways:\n- Only two cluster configurations (m=2 and m=5) are tested, which doesn't fully validate the algorithms' performance across varying clustering structures.\n- The uniform user arrival assumption in the theoretical analysis is unlikely to hold in real applications. Atleast for the simulations, maybe a broader user arrival strategy could be showcased. \n- The paper lacks comparison against additional baselines beyond independent dueling bandits.\n- No evaluation of computational efficiency is provided, which is particularly concerning for the neural network approach. (minor point)", "theoretical_claims": "I skimmed over the main theoretical results (Theorems 4.1 and 4.2) and their supporting lemmas. I did give more focus on Lemma B.2, C.5 since they seem central to the paper. \n\nThe proofs appear technically sound in deriving the regret bounds, but there are notable limitations:\n\n- The paper provides upper bounds on regret but no lower bounds. Without lower bounds, it's unclear whether the derived regret rates are optimal in terms of dimensionality dependence.\n\n- The edge deletion mechanism's theoretical guarantees (Lemma B.2 and C.5) don't fully address how the algorithms recover from incorrect edge deletions that may occur early in the process when estimates have high uncertainty. In the worst case of incorrect deletions (early in the algorithmic run or out of high probability zone), what is the worst to expect?\n\n- The notation for the function 'f' used in the edge deletion criteria (step 8 in both algorithms) is inconsistently defined between the main text and proofs, creating confusion about this critical component.\n\n- For CONDB, the NTK approximation in Lemma C.1 requires neural networks to be extremely wide (equation 66 specifies polynomial dependencies on multiple parameters), raising concerns about theoretical vs. practical guarantees.\n\n- The regret decomposition in equation (82) assumes correct clustering but doesn't fully account for potential cascading effects from early misclassifications.", "experimental_designs_or_analyses": "Potential Concerns: While the simulations serve as a great PoC with a limited setup. I would add the following critique:\n\n- The experiments only test two cluster configurations (m=2 and m=5) in the synthetic setting, which doesn't sufficiently validate the algorithms' performance across varying clustering structures.\n\n- The neural network experiments use only a simple square reward function (f(x) = (θᵀx)²). Testing more complex non-linear functions would better demonstrate CONDB's capabilities. At this point, the simulations seem to serve a PoC rather than to verify that the algorithm is behaving as expected. \n\n-  No sim results focussing on the convergence of the clusters. \n\n- There's no analysis of how algorithm parameters (like edge deletion thresholds) affect performance or clustering accuracy.\n\n- The paper doesn't report confidence intervals or statistical significance of the results, making it difficult to assess the reliability of the performance differences.\n\n- There's no evaluation of computational efficiency, which is especially concerning for the neural network-based approach that requires retraining models repeatedly.\n\n- The setup may be unrealistic for practical applications - particularly CONDB's requirement to run neural networks twice per round, which would be computationally prohibitive in many real-world settings.\n\nAny addressing of the above points would be a great help to any reader.", "relation_to_broader_scientific_literature": "The paper appears to largely combine existing approaches from different areas rather than introducing fundamentally new techniques. It bridges previously separate research areas:\n\n- The clustering of bandits approach builds on the work of Gentile et al. (2014) -- CLUB algorithm, which introduced graph-based user clustering for standard (non-dueling) contextual bandits.\n\n- The dueling bandits aspect draws from recent work on contextual dueling bandits which established theoretical foundations for linear dueling bandits.\n\n- The CONDB algorithm integrates ideas from neural bandits literature and recent work on neural dueling bandits (Verma et al., 2024).\n\nWhile the paper cites relevant literature and contributes by combining these existing approaches.", "essential_references_not_discussed": "The paper has a comprehensive literature review covering most relevant work. There are few plus minuses which can happen, but that is largely an author's choice.", "other_strengths_and_weaknesses": "**Strengths:**\n\n- The paper addresses a practically relevant problem of enabling collaboration among users in preference-based feedback settings.\n\n- The theoretical analysis provides insight into the benefits of clustering in dueling bandit settings.\n\n- The extension to neural networks for handling non-linear reward functions acknowledges the need for more expressive modeling of application setups.\n\n**Weaknesses:**\n\n- The paper appears to deriving a lot of the existing techniques from different areas rather than introducing fundamentally new algorithmic approaches.\n\n- The edge deletion mechanism lacks sufficient analysis on its robustness, particularly in early stages when estimates have high uncertainty.\n\n- The practical implementation of CONDB might face computational challenges that aren't addressed. Training neural networks twice per round is typically expensive for real-world applications.\n\n- The motivation discussing large-scale recommendation systems with many options conflicts with the proposed methodology's computational requirements.\n\n- Missing lower bounds make it difficult to assess whether the derived regret rates are optimal.\n\n- The experimental section lacks depth and breadth needed to fully validate the practical performance of the proposed algorithms.\n\n- The NTK-based theoretical guarantees require extremely wide neural networks. Atleast a simulation which shows it works with smaller nets would go a long way", "other_comments_or_suggestions": "**Suggestions/ Comments:**\n\n- Mentioning Lemmas B.2 and C.5 (on edge deletion) to the main text would be very beneficial. These are critical for algorithm correctness but barely mentioned.\n\n- Would it be possible to clarify the notation for the threshold function 'f' used in the edge deletion criteria, as it is inconsistently defined.\n\n- The introduction mentions applications to prompt optimization for large language models. This is very interesting use case but isn't explored further.\n\n- Ablation studies (this would include other non-linear reward structures) to understand the contribution of different algorithm components would be a crucial add.\n\n- Please Provide confidence intervals or statistical significance for experimental results.", "questions_for_authors": "Would like the authors to expand on just one point:\n\n- Your paper frames the approach as enabling \"cross-user collaboration,\" but all information sharing is mediated through a central algorithm with no direct user-to-user communication. How would your approach change if users could only share limited information, had privacy constraints, or were distributed across different systems without centralized coordination?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DQDgWYLSK7", "reviewer": "Reviewer_epsw", "summary": "This paper primarily investigates dueling bandits in an online clustering setting, where clusters of arms share a reward function. It examines cases where the reward function is linear or modeled by a deep neural network. The authors propose algorithms with sub-linear regret bounds and demonstrate their effectiveness through experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive feedback and valuable suggestions, our responses are as follows.\n\n**Q1:** Lower bounds: \n\n**A1:** Thanks for the helpful suggestion. Based on prior techniques (Wang et al., 2024a; Liu et al., 2022) and the single-user dueling bandit lower bound (Saha, 2021), we can derive a lower bound of $O(\\sqrt{dmT})$ for the linear setting. Our Algo.1 achieves an upper bound of $O(d\\sqrt{mT})$, which is tight up to a $\\sqrt d$ factor—a common gap in linear bandits (e.g., LinUCB). Thus, our upper bound is tight and optimal in $m$ for the linear case, and we will include this lower bound in the final version.\n\nFor the neural case, even the single-user non-dueling setting lacks a known lower bound, making it an open problem. However, we hypothesize that our upper bound is also optimal in $m$ for the neural setting, as clustering naturally introduces a $\\sqrt m$ scaling compared to the single-user case.\n\n**Q2:** Technical challenges involved in the algorithm design and its analysis:\n\n**A2:**\n\n**Novel Algorithm Design:**\n- Cluster Estimation under Dueling Feedback: Our setting does not allow direct use of prior cluster vector estimation methods in classical CB with numerical feedback. With numerical feedback, closed-form ridge regression enables simple updates of user-level covariance matrices and regressors, followed by cluster vector computation using aggregated statistics (e.g., Lines 6–8 in Algo.1 of Wang et al., 2024a). In contrast, dueling feedback lacks closed-form MLE, making direct adaptation infeasible. To address this, we maintain a history buffer $\\mathcal{D}_t$ (e.g., Line 10, Algo.1) recording user indices, arm choices, and dueling feedback. We then filter data for users in inferred clusters and estimate cluster vectors via MLE (e.g., Line 6, Algo.1).\n\n- Carefully Designed Edge Deletion Thresholds: Threshold design under dueling feedback is more intricate than in absolute feedback settings and relies on refined calculations (Lemmas B.2 and C.5) to ensure correctness. In the neural setting, this is further complicated by the non-linear reward function. The required Cluster Separation assumption (Assumption 2.7) deviates from those in prior CB works, making its integration into the edge deletion rule for CONDB particularly challenging.\n\n**Novel Theoretical Analysis**:\nWe highlight the main technical challenges for CONDB as an example:\n- Incorporating the novel Cluster Separation assumption (Assumption 2.7) for CONDB into the analytical framework of linear CB poses substantial difficulties. We address this by leveraging a linear approximation of the neural net as the analytical basis (Lemmas C.1 and C.2).\n- Deriving $T_0$ after which all users are correctly clustered (Lemma C.5), is particularly challenging due to the **non-linear and dueling nature of the reward**. Classical CB analysis bounds the L2 distance between true and estimated **linear parameters**, which is not applicable here. To overcome this, we use neural network linearization and rigorously analyze the resulting approximation error (Lemmas C.3, C.4, and C.5).\n- A key challenge in proving a sub-linear bound lies in the proper use of the effective dimension $\\widetilde d$ (Eq.(16)). Direct extensions of Lemma B.5 from the COLDB (linear rewards) analysis would yield a bound linearly dependent on $p=O(m_{\\text{NN}}^2)$, which becomes vacuous as $m_{\\text{NN}}$ grows polynomially with $T$. To address this, we adopt techniques from neural bandits to reformulate Lemma B.5 for CONDB, allowing us to express the regret in terms of $\\widetilde d$ (Lemma C.9).\n\n**Q3:** Is it necessary for the algorithm to know the number of clusters in advance?\n\n**A3:** No, our algorithms can adpatively cluster the users during the learning process, the number of clusters $m$ does not need to be known.", "claims_and_evidence": "The claim of achieving sub-linear regret bounds is substantiated by theoretical proofs.", "methods_and_evaluation_criteria": "The proposed method maintains the clustering structure of users and estimates the reward function using information from users within the same cluster, which is appropriate for the clustering bandits problem.", "theoretical_claims": "I have reviewed the proof, which appears to be correct.", "experimental_designs_or_analyses": "The experimental designs are reasonable, and the experimental results are promising.", "relation_to_broader_scientific_literature": "Clustering bandits have been extensively studied in the literature, while this paper is the first to explore clustering bandits with dueling feedback.", "essential_references_not_discussed": "The references sufficiently cover the relevant literature.", "other_strengths_and_weaknesses": "Strengths: The paper is well-organized, and the proposed algorithm is straightforward to comprehend. The authors demonstrate that the algorithm can achieve sub-linear regret bounds and provide clear intuition for the two terms in the regret bound. The experimental results further confirm the algorithm's effectiveness.\n\nWeaknesses: It is unclear whether the regret bounds are nearly optimal, as no lower bounds have been established.", "other_comments_or_suggestions": "I would suggest elaborating on the technical challenges involved in the algorithm design and its analysis beyond the application of known results from dueling bandits and clustering bandits.", "questions_for_authors": "Is it necessary for the algorithm to know the number of clusters in advance?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "shgGZJBRhC", "reviewer": "Reviewer_AU83", "summary": "The work studies the integrated setting of clustering and dueling bandits. The clustering bandit setting assumes the arms are clustered where each cluster shares the same reward function. The dueling bandit setting assumes that the learner chooses two arms in each iteration and obtains the preference feedback as reward. The paper proposes algorithms for two variants of the problem, linear and neural contextual setting, together with regret bound analysis. Experiments under both synthetic and real-world data are conducted to verify the empirical effectiveness of the proposed approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the valuable advice. Our responses are as follows. We will add the discussions.\n\n**Q1:** Technical challenges:\n\n**A1:**\n\n**Novel Algorithm Design:**\n- Cluster Estimation under Dueling Feedback: Our setting does not allow direct use of prior cluster vector estimation methods in classical CB with numerical feedback. With numerical feedback, closed-form ridge regression enables simple updates of user-level covariance matrices and regressors, followed by cluster vector computation using aggregated statistics (e.g., Lines 6–8 in Algo.1 of Wang et al., 2024a). In contrast, dueling feedback lacks closed-form MLE, making direct adaptation infeasible. To address this, we maintain a history buffer $\\mathcal{D}_t$ (e.g., Line 10, Algo.1) recording user indices, arm choices, and dueling feedback. We then filter data for users in inferred clusters and estimate cluster vectors via MLE (e.g., Line 6, Algo.1).\n\n- Carefully Designed Edge Deletion Thresholds: Threshold design under dueling feedback is more intricate than in absolute feedback settings and relies on refined calculations (Lemmas B.2 and C.5) to ensure correctness. In the neural setting, this is further complicated by the non-linear reward function. The required Cluster Separation assumption (Assumption 2.7) deviates from those in prior CB works, making its integration into the edge deletion rule for CONDB particularly challenging.\n\n**Novel Theoretical Analysis**:\nWe highlight the main technical challenges for CONDB as an example:\n- Incorporating the novel Cluster Separation assumption (Assumption 2.7) for CONDB into the analytical framework of linear CB poses substantial difficulties. We address this by leveraging a linear approximation of the neural net as the analytical basis (Lemmas C.1 and C.2).\n- Deriving $T_0$ after which all users are correctly clustered (Lemma C.5), is particularly challenging due to the **non-linear and dueling nature of the reward**. Classical CB analysis bounds the L2 distance between true and estimated **linear parameters**, which is not applicable here. To overcome this, we use neural network linearization and rigorously analyze the resulting approximation error (Lemmas C.3, C.4, and C.5).\n- A key challenge in proving a sub-linear bound lies in the proper use of the effective dimension $\\widetilde d$ (Eq.(16)). Direct extensions of Lemma B.5 from the COLDB (linear rewards) analysis would yield a bound linearly dependent on $p=O(m_{\\text{NN}}^2)$, which becomes vacuous as $m_{\\text{NN}}$ grows polynomially with $T$. To address this, we adopt techniques from neural bandits to reformulate Lemma B.5 for CONDB, allowing us to express the regret in terms of $\\widetilde d$ (Lemma C.9).\n\n**Q2:** Setting Importance and LLM applications: \n\n**A2:**\n- Motivation: Leveraging user relations to accelerate learning is well-established in CB literature (e.g., Gentile et al., 2014), particularly in recommender systems where users naturally form groups [1]. Preference-based feedback is also more aligned with human behavior and common in applications like RLHF, motivating the use of user relations under dueling feedback.\n- Extension to More General Settings: Some works have explored similar-but-not-identical user preferences under numerical feedback (Ban & He, 2021b; Wang et al., 2024b). As the first to study preference feedback in CB, we focus on standard assumptions to address core challenges. Extending to those settings is left for future work. \n- LLM Applications: Our methods can directly extend recent work on neural dueling bandits for prompt optimization [2] to the multi-user setting.\n\n**Q3:** Optimality in $m$ and lower bounds: \n\n**A3:**\n- Following Wang et al. (2024a) and Saha (2021), we can derive a lower bound of $O(\\sqrt{dmT})$ for linear case. Algo.1 achieves an upper bound of $O(d\\sqrt{mT})$, which is tight up to $\\sqrt d$—a common gap in linear bandits (e.g., LinUCB). Thus, our upper bound is optimal in $m$ for the linear case. For the neural case, lower bounds remain open even in the single-user setting. However, we hypothesize that our bound is also optimal in $m$ in the neural setting, as clustering naturally introduces a $\\sqrt m$ scaling over the single-user case.\n- While adversarial bandit algorithms can achieve $O(\\sqrt T)$ regret, **the regret definition differs**: adversarial regret compares to the best fixed arm, while stochastic regret compares to the optimal dynamic policy. Direct comparisons are not meaningful.\n\n\n**Q4:** Real-world data natively following clustering and dueling assumptions:\n\n**A4:** Our dataset and clustering setup follow standard practice in prior CB works using common benchmarks. We added a real-world dataset (Yelp), where COLDB continues to outperform baselines (see [figure](https://postimg.cc/QHS7rsbP)). We'll explore other datasets in future work.\n\nReference\n\n[1] ClustKNN: a highly scalable hybrid model-& memory-based CF algorithm, KDD 2006.\n\n[2] Prompt Optimization with Human Feedback, 2024.", "claims_and_evidence": "- Originality: It is claimed that the work is the first to integrate the setting of clustering and dueling bandits. To my knowledge, the claim is true.\n\n- Theoretical guarantee: The proposed approach is companioned with regret bound analysis with complete proofs. On the other hand, the optimality of the algorithm is not sufficiently justified, in particular w.r.t. the information on the clusters, such as cluster number.\n\n- Experiments: In my view, the experimental results are solid.", "methods_and_evaluation_criteria": "- The proposed algorithm utilizes relative standard techniques to handle clustering and dueling bandits. In my view, the method makes sense and is technically sound.\n\n- The major performance metric is regret bound, which is a standard one for online learning.", "theoretical_claims": "I have checked the proofs, which is correct in my view.", "experimental_designs_or_analyses": "The experimental part is solid.", "relation_to_broader_scientific_literature": "The work involves the clustering and dueling bandit learning scenarios, which have both received thorough studies. The work majorly studies the integration of both settings. From technical perspective, the paper utilizes relative standard techniques in algorithm design and theoretical analysis from the both scenarios.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n\n- The paper is technically sound. The proposed algorithm builds upon mature techniques. The technical proofs are complete.\n\n- The paper is clearly written.\n\nWeaknesses:\n\n- The technical challenge to integrate the clustering and dueling bandits lacks clear explanations. It would be not satisfactory to integrate the two setting without discovering more in-depth technical insights.\n\n- From practical perspective, it remains unclear why the proposed scenario is important in practice. In the introduction part, the example of LLM is discussed. While it remains unclear if the clustering assumption widely appears in real situations.", "other_comments_or_suggestions": "- It would be better to further discuss the optimality of the order of $m$ in Theorem 4.1 and 4.2. In the current results, if $m$ is very large, such as achieving the order of $O(T)$, the regret bound would be significantly worse, which can be worse than without considering the clustering assumption and only assume the adversarial setting. So I wonder whether there is the room of improvement on the term of $m$.\n\n- It would be better to introduce real-world datasets that natively follows the clustering and dueling assumptions.", "questions_for_authors": "1. It would be desirable to better highlight the technical challenges in algorithm design and theoretical analysis.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a new clustering of dueling bandit problem to model the collaborative decision-making scenarios, and proposes two algorithms to solve the problem. The author rebuttals have addressed most of the reviewers' concerns and all reviewers are in favor of accepting this paper. Although we don't have active discussion among reviewers, I recommend acceptance.
Decision: Accept (poster)