Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts
Authors: Zhuohua Li
Maoli Liu
Xiangxiang Dai
John C.S. Lui
Venue: ICLR 2025 Poster (2025)
Keywords: clustering of bandits
linear bandits
online learning
Primary area: learning theory
TL;DR: We introduce improved algorithms for online clustering of bandits by incorporating a novel exploration phase, resulting in better regret upper bound while using substantially weaker assumptions.

Abstract: The contextual multi-armed bandit (MAB) problem is crucial in sequential decision-making. A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters, utilizing shared features to improve learning efficiency. However, existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters. As a result, their theoretical analyses require several strong assumptions about the "diversity" of contexts generated by the environment, leading to impractical settings, complicated analyses, and poor practical performance. Removing these assumptions has been a long-standing open problem in the clustering of bandits literature. In this work, we provide two partial solutions. First, we introduce an additional exploration phase to accelerate the identification of clusters. We integrate this general strategy into both graph-based and set-based algorithms and propose two new algorithms, UniCLUB and UniSCLUB. Remarkably, our algorithms require substantially weaker assumptions and simpler theoretical analyses while achieving superior cumulative regret compared to previous studies. Second, inspired by the smoothed analysis framework, we propose a more practical setting that eliminates the requirement for i.i.d. context generation used in previous studies, thus enhancing the performance of existing algorithms for online clustering of bandits. Extensive evaluations on both synthetic and real-world datasets demonstrate that our proposed algorithms outperform existing approaches.

Published as a conference paper at ICLR 2025
DEMYSTIFYING ONLINE CLUSTERING OF BANDITS: ENHANCED EXPLORATION UNDER STOCHASTIC AND SMOOTHED ADVERSARIAL CONTEXTS
Zhuohua L Maoli Liu"; Xiangxiang Dai',John John C.S. Lui²
1 Guangzhou Institute of Technology, Xidian University Department of Computer Science and Engineering, The Chinese University of Hong Kong {zhli, ml mlliu, xxdai23, cslui caluilecssseeeee fcss.. cuhk. edu. hk
ABSTRACT
The contextual multi-armed bandit (MAB) problem is crucial in sequential decision-making. A line of research, known as online clustering of bandits, ex- tends contextual MAB by grouping similar users into clusters, utilizing shared features to improve learning efficiency. However, existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statis- tical information to accurately identify unknown user clusters. As a result, their theoretical analyses require several strong assumptions about the "diversity" of contexts generated by the environment, leading to impractical settings, compli- cated analyses, and poor practical performance. Removing these assumptions has been long-standing open problem in the clustering of bandits literature. In this work, we provide two partial solutions. First, we introduce an additional explo- ration phase to accelerate the identification of clusters. We integrate this general strategy into both graph-based and set-based algorithms and propose two new algorithms, Uni CLUB and Un SCLUB. Remarkably, our algorithms require sub- stantially weaker assumptions and simpler theoretical analyses while achieving superior cumulative regret compared previous studies. Second, inspired by the smoothed analysis framework, we propose a more practical setting that eliminates the requirement for i.i.d. context generation used previous studies, thus en- hancing the performance of existing algorithms for online clustering of bandits. Extensive evaluations on both synthetic and real-world datasets demonstrate that our proposed algorithms outperform existing approaches.
INTRODUCTION
The stochastic multi-armed bandit (MAB) problem is an online sequential decision-making problem, where each time step, the learner selects an action (a.k.a. arm) and observes reward generated from an unknown probability distribution associated with that arm. The goal of the learner is to maximize cumulative rewards (or equivalently, minimize cumulative regrets) in the long run. The contextual linear bandit problem (Li et al., 2010; Chu et al., 201 I) extends the MAB framework by associating each action with a feature vector and corresponding unknown linear reward function.
Online clustering of bandits, first introduced by Gentile et al. (2014), generalizes contextual linear bandits by utilizing preference relationships among users. adaptively partitions users into clusters and leverages the collaborative effect of similar users to enhance learning efficiency. This approach has many applications in computational advertising, web page content optimization, and recommen- dation systems (Li & Zhang, 2018). Different from conventional MAB problems that focus solely on regret minimization, online clustering of bandits has two simultaneous goals. Firstly, it infers the underlying cluster structures among users by sequentially recommending arms and receiving user feedback. Secondly, based on the inferred clusters, it minimizes the cumulative regret along
"Zhuohua Li and Maoli Liu contributed equally this work. Maoli Liu is the corresponding author. An updated version of this paper is available aixiv at htwps:tpp........... //axiiv www./oor//abaa abg/ /2501 00891.

---

Published as a conference paper at ICLR 2025
the learning trajectory. These dual goals significantly influence the algorithm design, the learner must balance the accurate cluster inference and effective regret minimization.
Most existing studies such Gentile et al. (2014); Li & Zhang (2018) employ Upper Confidence Bound (UCB)-based) strategy (Abbasi- Yadkori et al., 2011) to balance exploration (for cluster in- ference) and exploitation (for regret minimization). While this strategy is intuitive and standard for stochastic linear bandits, the least squares estimator used in the UCB strategy does not directly yield a precise estimation of underlying parameters, leading to insufficient statistical information for clus- ter inference. As result, to ensure correct cluster inference, existing algorithms for clustering of bandits require several strong assumptions on "data diversity" for their regret analysis, such as con- texts being independently generated from a fixed random process (we refer to it as stochastic context setting) with lower bounded minimum eigenvalue of covariance matrix and upper bounded vari- ance (See Section 3.2 for details). Unfortunately, these assumptions result in impractical settings, overly complicated theoretical analysis, suboptimal regret incurred by cluster inference, and more importantly poor performance in practice. Based on these challenges, a natural question arises:
Can we design new algorithms or propose new settings for the online clustering of bandits that eliminate the restrictive assumptions while achieving similar regrets?
Several efforts have been made to relax these assumptions. However, previous attempts have not addressed the fundamental issues, and some have resulted in deteriorated regret that grows exponen- tially with the number of arms, in exchange for milder assumptions (See details in Section 2).
In this paper, we demystify the process of cluster inference and provide two (partial) solutions to the aforementioned open problem. We show that merely employing a UCB algorithm is insufficient for simultaneously achieving both cluster inference and regret minimization. Specifically, the lack of sufficient exploration in UCB-like strategy hinders efficient inference of the underlying cluster structures. To tackle this problem, we propose two approaches, one focusing on algorithmic design and the other on problem setup:
Algorithmic Design Perspective: We maintain the stochastic context setting as in Gentile et al. (2014) (with some minor changes, see Section 3.1), and propose new algorithms with an additional pure exploration phase before applying UCB, leading to more reasonable settings, significantly re- laxed assumptions, simpler proofs, and improved cumulative regret. Intuitively, the additional ex- ploration phase gathers more information about the underlying clusters, preventing the subsequent UCB strategy from exploiting inaccurate clusters. This technique is quite general and applicable to both graph- graph-based based (Gentile et al., 2014) and set-based (Li et al., 2019) algorithms. It may also be of independent interest to other research on multi-objective MAB problems.
Problem Setup Perspective: We eliminate the need for stochastic context generation by proposing a new setup based on the smoothed analysis framework (Spielman & Teng, 2004), where the con- texts can be chosen by a "smoothed" adversary. This setting interpolates between two extremes: the i.i.d. context generation used in Gentile et al. (2014) and the adversarial context generation used in Yadkori et al. (2011). We show that with some minor changes, existing algorithms (such as CLUB proposed by Gentile et al. (2014)) achieve better performance in this setting.
To the best of our knowledge, our work the first to clarify the inferior results due to the restric- tive assumptions in the clustering of bandits literature (Gentile et al., 2014), propose new algo- rithms/settings to eliminate the assumptions, and obtain improved cumulative regrets.
Main contributions. Our contributions are highlighted as follows:
Following the stochastic context setting established in Gentile et al. (2014), we propose two algo- rithms: a graph-based algorithm UniCLUB based on CLUB (Gentile et al., 2014) and a set-based algorithm Uni SCLU based on SCLUB (Li et al., 2019). Both algorithms incorporate an initial exploration phase before the conventional UCB strategy. Benefiting from our design and novel analysis techniques, we substantially relax the assumptions required in our theoretical analysis.
We show that úni CLUB and UniUCU enjoy a regret bound of Ō [ (w=A, + ddmT). where
the first term improves the of-te- regret in existing literature (Gentile et al., 2014; Li & Zhang, 2018; Li et al., 2019; Liu et al., 2022: Wang et al., 2023a;b), and the second term matches the minimax near-optimal regret bound of contextual linear bandits (Abbasi- Yadkori et al., 2011) 1).
2

---

Published as a conference paper at ICLR 2025
Besides the stochastic context setting, we propose a setting called the smoothed adversarial context setting, where in each round, the context is chosen by an adversary but is then randomly perturbed. This setup is more practical and aligns more closely with the original setting of con- textual linear bandits (Abbasi- Yadkori et al., 2011). We give two associated algorithms SACLUB,
SASCLUB and prove that they enjoy a regret of Ö Ö( - ( + ddmmT) where X₂ =0 log K
We perform extensive evaluations both synthetic and real-world datasets. The results demon- strate that our algorithms outperform all the baseline algorithms, validating their effectiveness and practical applicability in various settings.
Table summarizes the comparison between our algorithms and existing studies with different as- sumptions and cumulative regrets. Detailed explanations of the diversity conditions and regret anal- ysis are given in Section 3.2 and Section
Table 1: Comparison between algorithms and existing studies with different design choices.
Context
Regret incurred
Algorithms
Diversity Assumption
Constants
Generation
by clustering
CLUB (Gentile et al., 2014).
I)) A..
CLUB-cascutee (Li & Zhang, 2018),
Lid.
(x X is Guussnnnn
C("(Tle + +)) A ==
SCLUB (Li et al., 2019),
PCLUB (Liu 2019), al., 2022)
S NES.RT
RCLUMB, RSCLUMB (Wang et 2025a).
RCLUB-WCU (Wang et al., 20236),
Lid.
(E|XX|X As.
6(v(,At 1 (e)) 3o -lata))
(= X'j is Gamssinnn
FCCCHUCH- (Yang et al., 2024)
(x|xX]] A,-
UniCLUB, UniSCLUB (Ours, Theorems and 2)
Lid.
The minimam gup between clusters
A 0(H)
has a known lower bound 5.
SACLUG, GASCLUB (Ours, Theorem 4)
Adversarial
Gaussian noise perturbation
i, ure dedined Assumption
number users, dimension, respectively.. 7 are defined Assumpiin R2" represents in arbitrary unit vector.
The rest of the paper is organized as follows. In Section 2, we review related work, emphasizing the restrictive assumptions the original setting and discussing prior attempts eliminate these assumptions. In Section 3, we present our solution for removing these assumptions in the orig- inal setting. In Section 4, we introduce an alternative approach based on the smoothed analysis framework, which aligns more closely with the original linear bandits setting (Abbasi-Yadkorii et al., 2011). Finally, Section and Section 6, we present the theoretical analysis and experiment results.
RELATED WORK
Our work is closely related the literature of online clustering of bandits. Since the seminal work by Gentile et al. (2014), which first formulated the clustering of bandits problem and proposed graph- based algorithm, there has been line of follow-up studies. For example, Li et al. (2016) considers the collaborative effects that arise from user-item interactions. Gentile et al. (2017) implements the underlying feedback-sharing mechanism by estimating user neighborhoods in a context-dependent manner. Li & Zhang (2018) consider the clustering of bandits problem in the cascading bandits setting with random prefix feedback. Li al. (2019) propose set-based algorithm and consider users with non-uniform arrival frequencies. Ban & He (2021) introduce local clustering which does not assume that users within the same cluster share exactly the same parameter. Liu al. (2022) extend the clustering of bandits problem to the federated setting and consider privacy preservation. Wang et al. (2023a;b) investigate clustering of bandits under misspecified and corrupted user models.
However, all of these studies adhere to Gentile et al. (2014)'s original setting and theoretical analy- sis framework, which imposes several restrictive assumptions on the generation process of contexts, such as (a) the feature vector of each arm is independently sampled from fixed distribution; (b) the covariance matrix constructed on specific context-action features is full rank with the minimum eigenvalue greater than 0; and (c) the square of contexts projected in fixed direction is sub- Gaussian with bounded conditional variance. Constructing a natural context generation distribution that sat- isfies all these assumptions simultaneously is highly challenging (if not impossible), and none of
3

---

Published as a conference paper at ICLR 2025
the aforementioned papers provide any concrete examples. There have been some attempts to relax these assumptions. For example, Wang et al. (2023a:b); Yang et al. (2024) propose a more relaxed assumption regarding the variance of contexts. However, these approaches result in a regret that grows exponentially with the number of arms K (as shown in Table I). We refer interested readers to more related works about leveraging similar assumptions in Appendix A.
Our smoothed adversarial setting and algorithms SACLUB, SASCLUB are inspired by the smoothed analysis framework, introduced by Spielman & Teng (2004). This framework studies algorithms where some instances are chosen by an adversary, but are then perturbed randomly, representing an interpolation between worst-case and average-case analyses. It was originally proposed to analyze the rumning time of algorithms. Kannan et al. (2018) first introduce the "smoothed adversary" setting in multi-armed bandits and study how the regret bound of greedy algorithms behave on smoothed bandit instances. This setting has been extended to structured linear bandits (i.e., the unknown pref- erence vector has structures such as sparsity, group sparsity, or low rank) (Sivakumar et al., 2020), linear bandits with knapsacks (Sivakumar et al., 2022), and Bayesian regret (Raghavan et al., 2023). All these studies show that the greedy algorithm almost matches the best possible regret bound. The core idea is that the inherent diversity in perturbed data (contexts) makes explicit exploration unnec- essary. In contrast to the analysis of greedy algorithms, our work introduces the smoothed analysis framework into the clustering of bandits setting, where the UCB strategy lacks sufficient exploration for identifying unknown user clusters. We demonstrate that the inherent diversity of contexts in the smoothed adversary setting climinates the impractical requirement for i.idd. context generation and enhances the cumulative regrets of existing algorithms (c.g.. CLUB (Gentile et al., 2014)).
3 STOCHASTIC CONTEXT SETTING
In this section, we study the online clustering of bandits problem under the stochastic context setting. building upon the seminal work of Gentile et al. (2014) but with substantially relaxed assumptions and improved cumulative regrets. We begin by introducing the problem setting, which largely fol- lows Gentile et al. (2014) with the stringent assumptions replaced by a mild assumption that the minimum gap between clusters has known lower bound. Then we provide the intuition of our key techniques. Finally, we present our proposed algorithms.
3.1 PROBLEM SETTING
In the following, we use boldface letters for vectors and matrices. We denote [M] == (1..... M} for M E N For any real vector y and positive semi-definite (PSD) matrix V. ||=|| denotes the f2 norm of æ, (x, = x y denotes the dot product of vectors, (a, y)v = x Vy y denotes the weighted inner product, and ||z/|v denotes the Mahalanobis norm V Vv.. Z. We use Xmin and (.ax(-) to denote the minimum and maximum eigenvalue.
In the online clustering of bandit problem, there are u users, denoted by set [u] = {1. 21....... u). Each user E [u] is associated with an unknown preference feature vector O; E R2 with |0,112 I 1. There is an underlying cluster structure among all the users. Specifically, the users are separated into m clusters I, Ig....,, .., I' (m < u), where Ule(m) I = [u] and I, N., = 0 for i + j. such that users lying in the same cluster share the same preference feature vector (i.c., they have similar behavior) and users lying in different clusters have different preference feature vector (i.e., they have different behavior). Formally, let l dennne the common preference vector for cluster I and j(i [m]] denote the index of the cluster that user belongs to. In other words, for any user i E Ir, we have 0, l go(()_ The underlying partition of users and the number of clusters m are unknown to the learner, and need to be learned during the algorithm.
The learning procedure operates as follows: At each round t 1,2...., T, the learner receives user index i, E [u] and finite set of arms A, C A where |A, = K. Each arm a E A is associated with a feature vector X,, Rd, and we denote D. {#a)aEA, C Rd. D, is also called context.
When we need to emphasize the index of arms, we also denote A.- {a..)] and D. ( J==1 Then the learner assigns an appropriate cluster V, for user i and recommends an arm ag E A, based on the aggregated data gathered from cluster Vi. After receiving the recommended arm, user sends a random reward r, E [-1, 1] back to the learner. The reward is assumed to have a linear structure: r. Tr. 0, + me, where ne zero-mean, Lsub-Gaussian noise term.
4

---

Published as a conference paper at ICLR 2025
Let aj arg aEA, 0 be the optimal arm with the highest expected reward time step t. The goal of the learner is to minimize the expected cumulative regret defined as follows:
T
E R(T)] = E
Da
0s, x 0:
where the expectation is taken over both the arms (at) and users (it) chosen during the process.
We assume the users and clusters satisfy the assumptions as follows:
Assumption (User uniformness). At each time step I, the user is drawn uniformly from the set of all users [u], independently over the past.
Assumption sell--sppaat among clusters). All users in the same cluster I, share the same preference vector 02, For users different clusters, there is a fixed but wnknown gap y between their preference vectors, with known lower bound 5. Specifically, for any cluster indices j.
0 - 0' 1l112
2 0.
Unlike the original setting in Gentile et al. (2014), where the gap y is completely un- known, we assume that y has known lower bound 7. We emphasize that this adjustment natural and results in more practical setting. On the one hand, the clustering of bandits problem intrinsi- cally requires a lower bound for 7. Specifically, to ensure successful clustering. have 77 < T, where T is the total time horizon. Without this condition, algorithm can effec-
Remark 1.
necessary to
tively identify the underlying clusters within time T. ! On the other hand, in world clustering tasks, y is usually a pre-defined parameter used to determine whether two items belong to the same cluster (Ban & He, 2021; Ban et al., 2022). Therefore, incorporating a known lower bound for is both reasonable and aligned with practical scenarios.
We also consider the where is completely unknown. In this scenario, without the stringent assumptions used in previous studies, algorithms are unable to determine whether cluster- ing has been successful. As result, have deal with the additional regret incurred by misclus- tering, similar to the misspecified linear bandits setting (Ghosh et al., 2017), which typically leads regret that grows linearly with 7 (Lattimore et al., 2020). To overcome this challenge, lever- age the structure of the clustering problem and propose phase-based algorithm, P PhaseUni CLUB, with carefully designed phase lengths. We demonstrate that our algorithm achieves sublinear regret of order Ö (see details in Appendix D).
Remark 2.
In the stochastic context setting, we assume the feature vectors (i.e., contexts) are independently sampled from a fixed distribution, but we completely remove the restricted assumptions on the sub- Gaussian distribution and variance of the arm generation process as mentioned in prior works.
Assumption 3 (Context diversity for stochastic contexts), At each time step the feature vectors in D, are drawn independently from a fixed distribution X with ||| < L. and E|X is of full rank with minimum eigenvalue X >
Remark 3. Intuitively, the minimum eigenvalue indicates how "diverse" the distribution X is, de- picting how certain the feature vectors span the full R space. Having a lower bound on the min- imum eigenvalue means that X has non-zero variance in all directions, which is necessary for the least squares estimator to converge to the true parameter. Note that Assumption 3 only maintains the minimum eigenvalue assumption' and completely removes the additional stringent assumptions as in previous studies (Gentile et al., 2014; Li & Zhang, 2018; Li et al., 2019; Wang et al., 2023a;b; Liu et al., 2022; Yang et al., 2024).
3.2 DIVERSITY CONDITIONS IN PREVIOUS STUDIES AND KEY TECHNIQUES
Before delving into detailed algorithms, we first examine the stringent statistical assumptions in previous studies (Gentile et al., 2014; Li & Zhang, 2018; Li et al., 2019; Wang et al., 2023a;b; Liu
'To distinguish hetween two hypotheses about the hias of coin with difference in their probabilities of heads, approximately 1 1/4² samples are needed. "This assumption is inevitable, since if the minimum eigenvalue is zero, the covariance matrix is not of full rank, and thus cannot be uniquely determined.
5

---

Published as a conference paper at ICLR 2025
et al., 2022; Yang et al., 2024) and explain their necessity for the theoretical analysis of the existing UCB-based algorithms. Then we provide insights on how these assumptions can be eliminated.
The key requirement of online clustering of bandits is the precise estimation of the preference vectors 0 for each user i, which is essential for correctly identifying the unknown user clusters. However, the convergence of the least squares estimator relies sufficiently diverse data. Intuitively, when data points span a broad range of values and cover the spectrum of possible predictors, the model can better capture the true underlying relationships, leading to more reliable parameter estimates. Mathematically, diverse data help ensure that user i's design matrix S = =x La, %y is well-conditioned, resulting in a more stable matrix inverse, which in turn reduces the variance of the estimated preference vector 0, S > [ Ma Therefore, all the previous studies rely on the diverse stochastic context assumption (Assumption 3), which states that the feature vector of each arm is drawn independently from a fixed distribution X with Amin (E) XXX = X > O. However, diverse contexts do not necessarily lead to well-conditioned design matrix because Assumption 3 only guarantees the diversity of arm set Dr, but not that the arms selected by the UCB strategy are diverse. As result, previous studies impose an additional assumption, requiring that for any fixed unit vector E R random variable (= X)² has sub-Gaussian tails with variance
parameter o² 8 Ing(4 This assumption, however, contradicts the diverse stochastic context assumption (Assumption 3), as the bounded variance condition restricts the diversity of X. In fact, it extremely difficult construct natural example of X such that all these assumptions are satisfied simultancously, and the aforementioned papers also do not provide any.
X
In summary, the key insight for eliminating the additional assumption design matrix S.,, i.e., the selected arms are sufficiently diverse. To this end, we introduce an additional pure exploration phase which uniformly selects arms the arm set D,. Lemma we will show that this explicit exploration guarantees that the minimum eigenvalue of the design matrix S.. grows linearly with the number of times user appears.
ensure a well-conditioned
3.3 ALGORITHMM FOR STOCHASTIC CONTEXT SETTING
For the stochastic context setting, we introduce two algorithms: a graph-based algorithm called Uniform Exploration Clustering of Bandits (UniCLUB, Algorithm 1) and a set-based algorithm called Uniform Exploration Set-based Clustering of Bandits SCLUE, Algorithm 2). Due to space constraints, we focus on Un i CLUB in the main paper, leaving the details and regret analysis of UniSCLUB in Appendix C.
As shown in Algorithm 1, inspired by the CLUB algorithm proposed in Gentile et al. (2014), UniCLUB maintains a dynamic undirected graph G. = ([u], E.) representing the current estimated cluster structures of all users. The main difference is that UniCLUB includes an additional uniform exploration phase to promote cluster identification. At the beginning, G, is initialized as a complete graph, indicating that all users considered in single cluster. Then at each round user E [M] comes to be served with a feasible arm set A, from which the learner has to choose. The algorithm operates in the following arm selection strategy differs between these phases.
phases depending whether the current time step f < To, and the
Pure exploration phase. In the first To rounds, the algorithm uniformly select arm o, from Ar (Line 4). This arm selection strategy ensures selecting sufficiently diverse arms so that the minimum eigenvalue of the design matrix grows linearly time (Lemma 2). In Lemma 3. we will show that the phase length To is chosen to guarantee that this phase gathers sufficient statistics to estimate each user's preference vector and correctly infer the underlying user clusters with high probability.
Exploration-exploitttio phase. After To. the algorithm constructs the connected component V. containing user i, in the graph G.- (Line 6), and computes the estimated preference vector @v.,.-1 based on historical information associated with Vi using the least squares estimator with regulariza- tion parameter X > 0 (Line 8). The algorithm then recommends bound (UCB) strategy (Abbasi- Yadkori et al., 201 ) to balance exploration and exploitation (Line 9):
using the upper confidence
a₂ = arg max 0V, 1 Fa + By xo. M V.t- Bay aE,A,

---

Published as a conference paper at ICLR 2025
Algorithm 1: UniCLUR: Uniform Exploration Clustering of Bandits
Input: A, 8, Ag. 6, L, 7
Initialization: Let Go ([u) Eb) be complete graph.
Let S = Odxd; 6i,0 = 0ax1, To = O, E [u].
Define f(Ta,) - (v 2 2log(u/0) dllog11 + 8r. X
T2,
+ V\) VA/VV-+ 12.
Ad
Define To 16u log + 4u max
log
ud 5124 7d
log }
for t = 1. do
Receive user index in and arm set At
if < To then
Select a, uniformly at random from Ar
else
6
Find the connected component Vú for in Gt-1
Mv,,0-1 = Eiev. S1,-1, M AI + Mv,1-1, bv, = Σiev, bi,-1
7
-v,,t-1= = M My bv..-bbiit-
8
Select arm 04 = arg max 01
1.t-1 To + 8 1a
10
Receive reward
11
Update statistics for user it, others remain unchanged:
Sind S 1 + V bi.t = bi,,-1 + Ty
Tht +x,+-++1 0g (AI Si,,)) bi..t -b...
Delete edge (it, () E Fq-1 if
12
0 0 0r.11 > f(Ti(t) ((Te.)
and obtain an updated graph G. ([u), Ex)
where the first term the estimated reward of arm a at time t and the second term is the confidence radius of arm at time t with parameter 3 v [ogo[1
TLa 2 log( ( + VÀ.
dA
After receiving the feedback r. from user it, the learner updates the statistics for user i, while keeping other users' statistics unchanged. Note that the estimated preference vector 0,, is computed using historical information associated with user i, (Line 11). Finally, the algorithm updates the inferred clusters by deleting edges in graph G if it determines that two users belong to different clusters. Specifically, for every user [u] that has edge to user i, the algorithm checks if the distance between the estimated preference vectors of users and i, exceeds a specific threshold (Line 12). If so, the algorithm deletes the edge i,, to split them apart and update the graph.
SMOOTHED ADVERSARIAL CONTEXT SETTING
Although UniCLUB offers significant theoretical improvements, it requires a change in the arm selection strategy during its execution, which might be desirable some circumstances. Ad- ditionally, the stochastic context setting necessitates an i.i.d. context generation process, which might be impractical in real-world applications. To overcome these limitations, based on the in- tuition in Section 3.2, we propose the smoothed adversarial context setting to eliminate the need for explicit pure exploration. This setting interpolates between the two extremes: the i.i.d. context generation in Gentile et al. (2014) and the adversarial context generation in Abbasi-Yadkort et al. (2011). The intrinsic diversity of contexts makes explicit exploration unnecessary, thereby ensuring well-conditioned design matrix (Lemma 11). This approach allows existing algorithms in previ- ous studies, such as CLUB (Gentile et al., 2014) and SCLUB (Li et al., 2019), which consistently employ the UCB strategy, to perform more effectively.
7

---

Published as a conference paper at ICLR 2025
4.1 PROBLEM SETTING
In the smoothed adversarial setting, we retain Assumption 1, while replacing Assumptions 2 and 3 with Assumptions 4 and 5, respectively. As detailed below, since there is no need to switch arm selection strategies during execution, Assumption 4 follows the original assumption in Gentile et al. (2014), which does not require knowledge of lower bound for y. Mcanwhile, Assumption allows feature vectors (i.c., contexts) to be arbitrarily chosen by an adversary. but with some random pertur- bation ensure the resulting contexts remain sufficiently diverse. This approach maintains enough data diversity to support effective learning while avoiding the need for explicit pure exploration.
Assumption (Well-separatedness among clusters). All users the same cluster I share the same preference vector 0², For users different clusters, there is a fixed but unknown gap y between their preference vectors. Specifically, for any cluster indices i + j.
|10 0* 27> 0.
Assumption (Context diversity for adversarial contexts). At each time step i, the feature vector Ta E DD for each arm E A, is drawn by "smoothed" adversary, meaning that the adversary first chooses an arbitrary vector 14a E Id with || S 1, then samples noise vector e, E R from truncated multivariate Gaussian distribution where each dimension is truncated within [- R, i...
Ea ~ (N, o² conditioned on [(oa)) I R, Vj E [d]. And the feature vector Ia = Pa + Ea-
Remark 4. The truncation in Assumption is used guarantee that the length of each feature vector is bounded, which is a standard requirement in the linear bandits literature. In fact, if we are only concerned with high-probability regret, we can also use a Gaussian distribution (without truncation) and show that the length of each feature vector is bounded with high probability. Note that Assumption is more similar to the original linear bandit setting (Abbasi- Yadkori al., 201 I), except that require each arm to be perturbed by Gaussian noise. It remains open problem whether fully adversarial setting can be achieved.
4.2 ALGORITHMS FOR SMOOTHED ADVERSARIAL CONTEXT SETTING
Our proposed algorithms for the smoothed adversarial context setting, SACLUR and SASCLUP, essentially CLUB (Gentile al., 2014) and SCLUB (Li et al., 2019) with A, replaced by X and replaced by + VdR in the edge deletion threshold. Due space constraints, we omit the full details of SACLUB and SASCLUB here, but the complete proofs are provided in Appendix E.
5 THEORETICAL ANALYSIS
In this section, we present the theoretical results of our algorithms, with detailed proofs provided in Appendices B, C, D, and E. For clarity, we ignore the constants but they are fleshed out in the proofs. Note that A, appears in the denominator of the regret expressions. This is due to the assumption of bounded contexts (|X||2 is bounded) the stochastic context setting, resulting in X = O(1d)). and therefore it is important track the dependency of our regret bounds on Xz-
Theorem (Regret of UniCLUB). Under the stochastic context setting (Assumptions 1, 2, 3). the expected regret of the UniCLUB (Algorithm 1) satisfies:
E [[R(T)) = O ud
log(T) + dv (VmmTlogTT)
x22x
Theorem 2 (Regret of UniSCLUB), Under the stochastic context setting (Assumptions 1, 2, 3), the expected regret of the UniSCLUB (Algorithm 2) satisfies:
E E[R(T)) = o ud
log(T) + d dV log(T))
loVmTlog(T))
Remark 5. Our results comprise two components: the first term is associated with cluster identifica- tion, and the second term aligns with the minimax near-optimal regret of linear contextual bandits. Notably, thanks to the careful design of UniCLUB and UnisCIUP our results enhance the first term by ((u/X2). offering significant improvement over existing studies, detailed in Table 1.
8

---

We compare our algorithms against the following state-of-the-ar algorithms for clustering of ban- dits: (I) LinUCB-One: LinUCB (Li et al., 2010) with a single preference vector shared across all Published as a conference paper at ICLR 2025
Theorem 3 (Regret of PhaseUnicLUB), Under the stochastic context setting (Assumptions 1, 2, 3), but 7 is unknown, the expected regret of algorithm PhaseUnicLUp (Algorithm 5) satisfies:
B[R(T)) = o ud 2
( (ud) (ud) Ax
lTg(T)
T log+(T) dv dVmTTogg()
Remark 6. Without knowledge of 7 (i.e., lower bound of 7), PhaseUn.cIUE suffers regret of order Od d's då).). As noted in Remark 2, this deteriorated result is expected since the algorithm has to contend with the issue of misclustering, similar to the challenges seen in misspeci- fied linear bandits (Ghosh et al., 2017: Lattimore et al., 2020). Despite this challenge, we carefully design the phase lengths to exploit the property of clustering and achieve sublinear regret, which is significant improvement over the linear regret typically expected in misspecified linear bandits. We emphasize that, as discussed in Remark 1, y not only has an intrinsic lower bound but also is typi- cally predefined in real-world applications. Therefore, our study the scenario where 7 unknown is primarily of thcoretical interest. Further details about the algorithm can be found in Appendix D.
Theorem 4 (Regret of SACLUB and SASCLUB). Under the smoothed adversarial context setting (Assumptions 1, 4, 5), the expected regrets of SACLUB and SASCLUB both satisfy:
[[R(T)] = O ud log(T) + dv dvmm (VmmllogTT) log(T))
where X C1 log K for some constant C1.
o²
Remark 7. For the smoothed adversarial context setting, prove that the intrinsic diversity of contexts guarantees a lower bound on the minimum eigenvalue of E. xa, x, (Lemma 11). This allows us apply techniques similar to those used in the stochastic context setting get this result.
PERFORMANCE EVALUATION
In this section, we present the evaluation results of our algorithms. We focus on the stochastic context setting in the main paper since the smoothed adversarial setting serves mainly for theoreti- cal analysis, and algorithms SACLUS/SASCIUB are minor modifications of CLUB (Gentile et al., 2014)/SCLUB (Li et al., 2019). Nonetheless, we provide detailed evaluations of the smoothed ad- versarial setting and an ablation study on different arm set sizes and user numbers in Appendix G.
6.1 EXPERIMENT SETUP
users. (2) LinUCB-Ind: LinUCB (Li et al., 2010) with separate preference vectors estimated for each user. (3) CLUB (Gentile et al., 2014): graph-based algorithm that consistently employs the UCB strategy. (4) SCLUB (Li et al., 2019): A set-based algorithm with improved practical performance. In addition to these clustering-bart based baselines, we also evaluate our approach against two graph- based algorithms from related but distinct setting in Appendix G: GOB.Lin (Cesa-Bianchi al., 2013), which incorporates user similarities using Laplacian regularization, and GraphUCB (Yang al., 2020), which utilizes the random-wa walk Laplacian matrix encode user relationships. Note that neither GOB Lin nor GraphUCB explicitly performs clustering. All the experiments were con- ducted on device equipped with 3.60 GHz Intel Xeon W-2223 CPU and 32GB RAM. Each experiment was repeated over 5 random seeds, and the results are reported with confidence intervals calculated by dividing the standard deviation by the square root of the number of seeds.
6.2 DATASETS GENERATION AND PREPROCESSING
In our experiments, we employ one synthetic dataset and three real-world datasets, MovieLens- 25M (Harper & Konstan, 2015), Last.fm (Cantador al., 2011), and Yelp (Yelp, 2023). We generate the synthetic dataset and preprocess the real-world datasets following the same method in previous studies (Zhang al., 2020; Li et al., 2024; 2025; Dai et al., 2024a:b).

---

Published as a conference paper at ICLR 2025
To generate the synthetic dataset, set the dimension d 50, the number of users 200, and the total number of arms | = 5. 000. The feature vector Da E R of each arm a E A and the preference vector 02 Ia for each user i [u]] are generated by independently sampling each dimension from a uniform distribution U (-1,1) and then normalizing to unit length.
datasets, MoVIeLLns-22MM, Last.fm, and Yelp, we regard movies/arrists/businsssss as arms. We extract a subset of |A| = 5. 000 arms with the most quantity of user-assigned rat- ings/tags, and subset of u 200 users who assign the most quantity of ratings/tags. Using the data extracted above, we create a feedback matrix R of size u x [A], where each element R represents the user i's feedback to arm j. We assume that the user's feedback is binary. For the MovieLens and Yelp datasets, a user's ' feedback for a movie/business is if the user's 's rating is higher than 3. For the Last. fmm dataset, a user's feedback for an artist is the user assigns a tag to the artist. We generate feature vectors and preference vectors by decomposing R using Singular Value Decompo- sition (SVD) as OSA where + = {0: {0.) jeto) and A {#a) Then the top d 50 dimensions of these vectors associated with the highest singular values S are extracted.
For the
6.3 EXPERIMENT RESULTS
In the experiment, to incorporate user clustering, we randomly select 50 users and partition them into 10 clusters. For each cluster j. we calculate the mean preference vector across all users within that cluster to serve as 05, Note that the number of clusters unknown the algorithms. At each round t, we uniformly draw user & from the 50 users, and randomly select 100 arms from A to form the arm set A,. The results are presented in Figure
As shown in Figure 1, the algorithms that employ user clustering significantly outperform LinUCB- Ind and LinUCB-One One, which do not consider the similarity among users or cluster users. More importantly, our graph- based algorithm EniCLUB consistently outperforms the graph-based base- line CLUB, and our set-based algorithm Un SCLUB better than the set-based baseline SCLUB across all four datasets. It is important to note that the modest advantage of CiniCLLBBUnnS. over CLUB/SCLUB is both expected and reasonable, given the logarithmic improvement in the re- gret upper bound. The results demonstrate the effect of uniform exploration and the robustness of our proposed algorithms across various datasets. More evaluation under the smoothed adversarial context setting and ablation study can be found in Appendix G.
Synthete
Chirateoiv Begie
Reurds
Rearnch
Ruardh
Raards
UNISCLUB
---
USKLUR
"BB CLUB
SCLUB
LiUCB-Ird
-. LHUUCB-DN Oite
Figure I: Comparison of cumulative regrets in the stochastic context setting.
CONCLUSION
In this paper, proposed two new algorithms for online clustering of bandits, UniCLUB and Uni UnLSC,U, which incorporate an additional pure exploration phase to enhance the identification of user clusters. Notably, algorithms require significantly weaker assumptions while achieving superior cumulative regret compared to previous studies. Furthermore, we introduced the smoothed adversarial context setting, which interpolates between i.i.d. and fully adversarial context gener- ation. We showed that with minor modifications, existing algorithms perform better in this new setting. Finally, we conducted extensive evaluations validate the effectiveness of our methods.
ACKNOWLEDGMENTS
The work of John C.S. Lui was supported in part by the RGC's SRFS2122-4S02.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Proceedings of the 24th International Conference Neural Information Processing Systems, NIPS'11, 11, pp. 2312-2320, 2011.
Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Yikun Ban and Jingrui He. Local clustering in contextual multi-armed bandits. In Proceedings of the Web Conference 2021, WWW '21, pp. 2335-2346, 2021. ISBN 978145038318
Yikun Ban, Yunzhe Qi, Tianxin Wei, and Jingrui He. Neural collaborative filtering bandits via meta learning, 2022.
Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration-fire algorithms for contextual bandits. Management Science, 63(3):1329-133333 March 2021. ISSN 1526-5501.
Ivan Cantador, Peter Brusilovsky, and Tsvi Kuflik. Second workshop on information heterogeneity and fusion in recommender systems (hetrec201 I). In Proceedings of the Fifth ACM Conference on Recommender Systems, RecSys '11, pp. 387-388, 2011.
Nicolò Cesa-Bianchi. Claudio Gentile, and Giovanni Zappella. A gang of bandits. In Advances in Neural Information Processing Systems, volume 26, 2013.
Niladri Chatterji, Vidya Muthukumar, and Peter Bartlett. Osom: A simultancously optimal algo- rithm for multi-armed and linear contextual bandits. In Proceedings of the Twenty Third Interna- tional Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp.
PMLR, 26 28 Aug 2020.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Xiangxiang Dai, Zhiyong Wang, Jize Xie, Xutong Liu, and John C.S. Lui. Conversational rec- ommendation with online learning and clustering on misspecified users. IEEE Transactions on Knowledge and Data Engineering, pp. 1-14, 2024a.
Xiangxiang Dai, Zhiyong Wang, Jize Xie, Tong Yu, and John CS Lui. Online learning and detecting corrupted users for conversational recommendation systems. IEEE Transactions on Knowledge and Data Engineering, 2024b.
Claudio Gentile, Shuai Li, and Giovanni Zappella. Online clustering of bandits. In Proceedings of the 31st International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 757-765. PMLR, 22-24 Jun 2014.
Claudio Gentile, Shuai Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, and Evans Etrue. On context-dependent clusten of bandits. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1253-1262. PMLR, 06-11 Aug 2017.
Avishek Ghosh and Abishek Sankararaman. Breaking the VT barrier: Instance-indeppndent log- arithmic regret in stochastic contextual linear bandits. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 7531-7549. PMLR, 17-23 Jul 2022.
Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits. In Pro- ceedings of the Thirty-First AAAI Conference Artificial Intelligence, AAAI'17, pp. 3761-3767.
AAAI Press, 2017.
Avishek Ghosh, Abishek Sankararaman, and Ramchandran Kannan. Problem-complexity adaptive model selection for stochastic linear bandits. In Proceedings of The 24th International Confer- ence on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 1396-1404, PMLR, 13-15 Apr 2021a.

---

Published as a conference paper at ICLR 2025
Avishek Ghosh, Abishek Sankararaman, and Kannan Ramchandran. Collaborative learning and personalization in multi-agent stochastic linear bandits. stat, 1050:15, 2021b.
Botao Hao, Tor Lattimore, and Csaba Szepesvari. Adaptive exploration in linear contextual bandit. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statis- tics, volume 108 of Proceedings of Machine Learning Research, pp. 3536-3545. PMLR, 26-28 Aug 2020.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), dec 2015.
Sampath Kannan, Jamie Morgenstemn Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu. A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Proceed- ings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 2231 2241, 2018
Tor Lattimore, Csaba Szepesvári, and Gellért Weisz. Learning with good feature representations in bandits and in with a generative model. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JML..org. 2020.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, WWW '10, pp. 661-670, 2010.
Shuai Li and Shengyu Zhang. Online clustering of contextual cascading bandits. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applica- tions of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence,
AAA'188/AAA'18//EAAA 18, 2018
Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Proceed- ings of the 39th International ACM SIGIR Conference on Research and Development in Informa- tion Retrieval, SIGIR '16, pp. 3339,548,77 2016. ISBN 9781 9781450340694.
Shuai Li, Wei Chen, Shuai Li, and Kwong-Sak Leung. Improved algorithm on online clustering of bandits. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, 19. pp. 2923-2929. International Joint Conferences on Artificial Intelligence Organization, 7 2019.
Zhuohua Li, Maoli Liu, and John C.S. Lui. Fedcompe: Efficient federated conversational bandits with heterogeneous clients. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, IJCAI-24. International Joint Conferences on Artificial Intelligence Orga- nization, 2024.
Zhuohua Li, Maoli Liu, Xiangxiang Dai, and John C.S. Lui. Towards efficient conversational recom- mendations: Expected value of information meets bandit learning. In THE WEB CONFERENCE 2025, 2025.
Xutong Liu, Haoru Zhao, Tong Yu,, Shuai Li, and John Lui. Federated online clustering of bandits. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022.
Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu. Greedy algorithm almost dominates in smoothed contextual bandits. SIAM Journal on Computing, 52(2): 487-524, 2023.
Vidyashankar Sivakumar, Steven Wu, and Arindam Banerjee. Structured linear contextual bandits: A sharp and geometric smoothed analysis. In Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pp. 9026-9035. PMLR, 13-18 Jul 2020.
Vidyashankar Sivakumar, Shiliang Zuo, and Arindam Banerjee. Smoothed adversarial linear contex- tual bandits with knapsacks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepes- vari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. PMLR, 17-23 Jul 2022.
12

---

Published as a conference paper at ICLR 2025
Daniel A. Spielman and Shang-Hur Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385 463, may 2004. ISSN 0004-5411.
Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computa- tional Mathematics, 12(():389-433 August 2011. ISSN 1615-3383.
Zhiyong Wang, Jize Xie, Xutong Liu, Shuai Li, and John C.S. Lui. Online clustering of bandits with misspecified user models. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023a.
Zhiyong Wang. Jize Xie, Tong Yu, Shuai Li, and John C.S. Lui. Online corrupted user detection and regret minimization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023b.
Weiqiang Wu, Jing Yang, and Cong Shen. Stochastic linear contextual bandits with diverse contexts. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statis- tics, volume 108 of Proceedings of Machine Learning Research, pp. 2392-2401. PMLR, 26-28 Aug 2020.
Hantao Yang, Xutong Liu, Zhiyong Wang, Hong Xie, John C. Lui, Defu Lian, and Enhong Chen. Federated contextual cascading bandits with asynchronous communication and heterogeneous users. Proceedings of the AAAI Conference on Artificial Intelligence, 38(18):20596-2063 Mar. 2024.
Kaige Yang, Laura Toni, and Xiaowen Dong. Laplacian-reguulriized graph bandits: Algorithms and theoretical analysis. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 3133- 3143. PMLR, 26-28 Aug 2020.
Yelp. Yelp Dataset yelp.com. https: http://wwwwell.....c/aaaaaeettte 20-40.
wwt.dataa//atteooececcccc 2023, [Accessed 21-
Xiaoying Zhang, Hong Xie, Hang Li, and John C.S. Lui. Conversational contextual bandit: Algo- rithm and application. In Proceedings of The Web Conference 2020, WWW '20, pp. 662-672, 2020.
13

---

Published as a conference paper at ICLR 2025
A MORE DISCUSSIONS ON RELATED WORK
Leveraging data diversity (i.e., conditions refer to the minimum eigenvalue of a design matrix) in stochastic linear contextual bandits has two lines of research. The first line involves using additional "diversity conditions" to improve cumulative regrets. For example, Bastani et al. (2021) introduce condition for the disjoint-paramett case, and prove that non-explorative greedy algorithm achieves Ollog 2') problem-dependent regret on a 2-arm bandit instance. Hao et al. (2020) give a condition and prove constant
regret for UCn the shared-par parem-parrmettr case. Wu al. (2020) show that under some diversity conditions, LinUCB achieves constant expected regret in the (2014) and achieve
case. Ghosh Sankararaman (2022) use condition similar to Gentile et al. logarithmic regret for linear contextual bandits. The second line of research focuses on achieving concurrent statistical inference and regret minimization (i.e., multi-objective MAB). This involves performing additional tasks on top of regret minimization, such as clustering (Gentile et al., 2014), model selection (Chatterji et al., 2020; Ghosh et al., 2021a) personalization (Ghosh et al., 2021b), and exploration under safety constraints (Amani et al., 2019).
B THEORETICAL ANALYSIS OF UNICLUB
Lemma 1. With probability at least 8 for any 8 E (0, VL [T] and Vi E [u].
(0) + dlog
Ti, Ad
+ VX
00..
8000 -
VA + Amiu (Si,)
Proof. Fix a user i E [u]. for all t E [2], we have
012- - = AI +
Ca. Ia
Σ
Tar (2 0iti) + nr)) +m²)
- 0011)
=i
rE
XI
La, Da ve
A++ Σ
Da. Far
T
(0(1) +
Fo. th 205(1)
Oo(()
rE(t),i,
rE
-00(1) + (AI + St.e)
X(X St.)) - -g0(())
-00())
Fa, 1/
TE|
=5,1 1t
Ta. - -3 (1(
where we denote 3,, A AI + St, = AI A Er
Lo, w.
For any vector E Rd.
x (0., - (8(()) = x 15,11 i,t
Ax 3 0)(1)
Ea. 17
re(t]aa,
>X (x, 0
Fa, 1/7
ST
rE(tJ mi
5T1
Therefore, by the
inequality,
To (0..t (0x.)) s |,0||==:
Da. nT
ST
r
Next, we bound the two terms in the parenthesis. For the first term, consider the o-algebra Fc (ii, Pay my.... ie, Bays Thi fe41, (e,)) where i, and La, are -measuuure,, and me F,- measurable. Let (Free be filtration. By applying Theorem of Abbasi- Yadkori Abbasi-Yadkori al. (2011)
14

---

Published as a conference paper at ICLR 2025
and using the union bound over all users E [u], we have that for all i [u] and for all E [T7, with probability 2 1-6. 6,
u udee(S det(Ar)
Da !/7
S
2 log
TE|t =i
3
S
11 2og
(
7)
+ dloo
1
Ti
Ad
where we use the standard derivation due Lemma 16: det(S:;)) S and the fact that dct(AI) X² For the second term, by the property of the Rayleigh quotient, for any invertible PSD matrix V and non-zero vector w, we have
[ir(3,,c)
()
d
|
VV-lw w w
1
I Amax (V Amin (V)
w 1
Therefore, by the fact that Amin (St.) 2 X, and the assumption that |10:00)|2 S 1, we have
llolll ड.. S vxllo 12 S VA.
(2)
Plugging in B..(( Q5(1)) Equation (I), we have
x (0.. )x())
|0,. Q01() 2
B..
3 0,, ) 1010))1 ||
/2108 ②) + d'log 1+ Ti,L?
+ +Vā
Ad
o.. 0o(i)
210s ( + dog
1
Ti,eL²
+ vX
Se.
Ad
Again, by the property of the Rayleigh quotient, for any PSD matrix V and non-zero vector w,
w VVw
|
1wllv
Amin (V) <
||
w T
w
Amin (V)
Therefore, dividing @ 0i(1)
both sides and applying the above inequality, get
B,,
log 4) + d log (I 1+
Thrts Xd
+ VA
10.. 80(0)
<
(S.1)
log llog()) (4) + d dlog (1
Pirk2 Ad
+ VT
VA Amin Amin(Sa..)
where in the last inequality we use Amin (MI Sy,)) 2 Amin Amin(A Amin (St)), due to Weyl's inequality.
Lemma 2. In the uniform exploration phase of Algorithm 1, with probability at least 1 - 5 for any
5 E 1), Tr, 2 8L2
A. log( ud) for all users E [ui), we have
NoT
Amin Amin (St.) 2
Vi E [u].
2
15

---

Published as a conference paper at ICLR 2025
Proof. To apply the matrix Chernoff bound (Lemmaa 12), first verify the required two condi- tions for the self-adjoint matrices Ta, 2n, for any T E [t]. First, due to the generation process of feature vectors, La x is independent and obviously positive semi-definite. Second, by the Courant-Fischer theorem, have
Amax (Ta, D
max w La a w w:||=||11
max w
aa' xa,)² )
max
11 1 L22
According to Algorithm 1, in the uniform exploration phase, for all T E [t] a is uniformly selected in Ar. Also, by Assumption all the feature vectors A, are independently sampled from X, therefore by Lemma 15, Za. follows the same distribution as X.
So for a fixed user E [ul] we can compute
Mmin
Amin
Σ r
E( A(Da,
=mmin Amia (T,, Tiiss:
where the last equality due to the minimum eigenvalue in Assumption 3. Now applying Lemma 12, get for any (0,
- Pr Amin (S S (1 e1 d
(1 - =)
Choosing 2. we get
Tr,ed
< d 1i <<
Trcdoll? ))
Pr Amin (St,)
2
Letting the RHS be $. we get Ti, L log( 44)
Therefore, for any fixed user i E [u].
A=(2 -lg())
Amin (min(Sa,)) 2 Ti.da holds with probability at least when Tú, 2 sL² 2
log( The proof
(nd))
follows by union bound over all users E [u].
Lemma 3. With probability at least 36, Algorithm can cluster all the users correctly after
182
(ud''
512d log
7) }
To A 16u log 7 4u max
log
(3)
xxz
Proof. Combining Lemma 1 and Lemma 2, have with probability at least 25, when TG, 2 812 log(2e) ud for all users E [u].
A.
2 (x) dlog TiaL2
VX
@ - 0u303|
Ad
s
Vd+ + Amin (Stz)
2 log( + dlog 1
To.6
VA
Ad
f(T..), Vi [u].
V Ti,dde/2
Next, we find sufficient time step Ti, such that the following holds:
2 2 () dlog 1 Ti
VX
f(T),) A
VA + Trcde//
We assume X < 2 ()g + dlog for Equation (4) is
1+
T,,L²²) Ad
which typically holds. Then sufficient condition
2 (4) + dlog
1+
Ti, Ad
72
<
A + T, Tr,dhe/2
64
16

---

Published as a conference paper at ICLR 2025
To make the above equation hold, it suffices to let
2 log 5 Ti 2
dlog
1+
Teat.
Ad
72
and
128
T2,12
128'
512 log( #1
The first inequality holds when Ti, 2
For the second inequality, by some basic arithmetic
(Lemma 14), sufficient condition is Tu, 2
512d log 256L2
7² By choosing such that ă 7
256
we get sufficient condition for Equation (4): Tue
lg)
7
In summary, in the uniform exploration phase of Algorithm with probability least 28 for some 6 > 0, when
8L2 Am
ud δ
512d A2
u log
} Vi e [w] 8
Túe 2 max
log
(5)
have 0,, 80(1)) S (T - / for all users i [u].
Because of Assumption 1, users arrive uniformly, so by Lemma 13 and a union bound over all users i [u]. Equation (5) holds for all i E [u] with probability at least when
2 To e
u 16u log :
+ 4u max
8L2
log
ud
512d
log
u }
A
8
22
Therefore, with probability 1 - 35, we have
00,,
(0(1)
22 S f(T()) & 7. Vi E [u] when 2 Tu-
Next, we show that under this condition, the algorithm will cluster all the users correctly. To guar- antee this, need to verify two aspects: (1) if users k l are in the same cluster, then the algorithm will not delete edge (k, f); (2) if users k, l are not in the same cluster, then the algorithm will delete edge (k, E). We show the contrapositive of (1): if edge (k:, () is deleted, then users l are in the same cluster. Due to the triangle inequality and the deletion rule in Algorithm 1, we have
|00000 - -0/00) 2 Øn.c 02.0 0 00(k)// - 10... ei(1) 1
0 Ōc.r 112 -(Thke) f(Te,e) O.
So by Assumption 2, ||0v(0)
05(09 1|2 > implies that users k, l are not in the same cluster. For
(2), we show that if [ii(k)) 00(0 112 2 7. the algorithm will delete edge (k:, f). By the triangle inequality,
0n. 0e.1]
2 |0(00) - -0((0
- -100, -
80(K)|
0o, - o5(e)
2
7
7
2
2 [(Th,e) + [(Tr.))
4
2
which triggers Algorithm 1 to delete edge (k:, f).
Lemma 4. With probability at least - for all >> To. we have
T | (Ovi,t-1- -0((t,) < 3 3| My A Catt
where B = V dlo((1 + _ + 21og(3) + VX.
Proof. Assume that after To, the underlying clusters are identified correctly, meaning that V, the true cluster that contains user iz, i.c., V4 = Iz(i.) then we have
Ov,,-1 - 9860) = AI+
Σ
Σ Tt
- gi(()
Le, Car
rE(t-Ilit-EV
17

---

Published as a conference paper at ICLR 2025
AI +
Σ
Ba-wer
Σ rEjt-I]jr,EV
Bar (o 0n m+)
Oc(())
(6)
rEjt-I]ji-E
-M V
AI+
Σ
La, For
T
Oi: 20:; +
E
Ba, 1/7
(i(ie)
rElt 1Jss, eV
- -M + M MV
Σ
Lo, 1/,
TE(r I|,i, ev
where we denote MV..-1 = AI + Mv. Equation (6) is because Vi is the true cluster that contains de, thus by Assumption 0,, 0r Vi, E V2. Therefore, we have
x (Ovi,-11 -
S A x M Vi,t 0 + x M Vi,1-1
Σ
Ba, 7/
=> =>(220 Ba. (i(t))
Cu. Σ
+
Br
M vele-1
TEll
EE]t-1];,EV
M v1--1
<>|[<a 1 M
||orrwo
+
|| M ve.t
Σ
Ba-!l
(7)
M
rEjt-IlaiEV
M
< <1 Myl
VĀ+
Σ
Fa, 1/r
(8)
V
where Equation (7) is by the Cauchy-Schwarz Schwarz inequality and Equation (8) is derived by Equa- tion (2). Following Theorem 1 in Abbasi- Abbasi-Yadkori al. (2011), with probability at least 6, for fixed user E [u], we have
det (M (e v,, (,, det
1)
Σ
Ia, Br
2
8
rE(t-I]:i.EV
M M
v
dct(MVv... v2.e-1)
2 log
+ log
det(AL
(1+
TL2
2 log
+ d
1
(9)
Xd
where in Equation (9), use det((A) xd and by Lemma 16, we get
d
(tr(A))+ + tr
T Ere(e-1] Ca, Lo EVV.
tr (v,
Xd + TL
det det(MM.. (vv.c-1)
Since the clusters are correctly identified after To with probability at least 1 35 (Lemma 3), and
Equation (9) holds with probability least 1 d. By plugging Equation (9) into Equation (8) and collecting high probability events, we conclude the proof.
Lemma 5. Under the high probability event in Lemma 3, for any cluster j [m], we have
}
TL2
min 1, ||a
2d
MM zj.
Ad 413
T= E,
where M I, A AI + Grett-lji,ez, Ba. IT. XI ErE(-1 1iir E Iz) T..
18

---

Published as a conference paper at ICLR 2025
Proof. The proof mainly follows Lemma 9 in Abbasi- al. (2011), but improve the bound by leveraging Lemma
Consider the covariance matrix of cluster Ij after time T, we have
det (M,
det MI,.T T- + LsT E EIJ
ddel
M 1 [I M M2 1,,T-1 E In)
M
M I M
I
M M 12ar
det ( (22,2-11 det
I I+
I I 11
= det x-1
1+ 1
M 1 13 In}
(10)
det M [M 1-1 1)
1 1 E Iiillaar 1 23
(dde(MM,,,aa
II T=To++1
(1 || MZz).-))
(11)
where Equation 10 is due to the property that all the eigenvalues of matrix of the form I + wx are one except one eigenvalue, which 1 + || And Equation is by telescoping.
Since we assume the high probability event in Lemma 3 happens, when & To, we have
182 X
udd
512d gp
log (4)
8L2
uud
Tú, 2 max
log
log
vi E [u].
8
Note that M M,,1 = AI + To
La, La = AI + EiEI, Si So by Lemma 2, we have
tr (I,
XI
St.To İEI,
> 8L2
ud Xd 4L log
uud
Ad
log
(12)
2
A
8
Therefore, taking logarithms on both sides of Equation (11), we have
log(det( (effdet(M,,,7)) (Mr,r)) log(det ( (T,TT)) +
log 1 + |10
(13)
1=
Since < 2log(1 (1 x)) for x E [0, 1]. by Equation 13, we get
Σ
min 1, ||, I 2
2 Σ log 1 || 11 Mz).e-1)
t=
1=o++1
2 loog det
M MI,T))
- -log det
M II,
(14)
tr tr(M,,
tr tr(MI,
< 2 dlog
d dlog
(15)
Ad + TT,2
Ad 41, log o
< 2 d
dlog
(16)
d
d
TL2
< 2d log
1
1+
Xd 4L2
where Equation (14) uses Equation (13).
Equation (15) uses the determinant cectminnant-race inequality
Lemma 16. Equation (16) uses Equation (12).
19

---

Published as a conference paper at ICLR 2025
Theorem (Regret of UniCLUB). Under the stochastic context setting (Assumptions 2, 3), the expected regret of the Uni CLUB (Algorithm 1) satisfies:
E [[R(T)) = ( ud
log(T) + dv dVmTlog(T))
7
Proof. Define events:
ε₁ all users correctly clustered after To
& x (Ov,.-1 (0,,1-1--it)) 3 5 m. Vt 2 Toj
Let = & En& &2. By Lemma and 4, & happens with probability at least -5. Then let and by the law of total expectations:
7
E[R(T)] = E(R(T) 8l Pr [8] + E[R(T) Pr
4 T
E[R(T) 8 x 11x+77
(17)
It remains bound E(R(T) i.., the expected cumulative regret conditioned event E.
Assume happens, by the bounded reward assumption, we can upper bound the regret in the first To rounds by To. After To. the instantancous regret at round & satisfies:
R2 ,, (0( x1,00(11 (o(())
= ((((i)) Byi,e11 + I 00. + Cazer) (x,1,6 0va,e-1 + Cac,t)
+ w (gitt)) - -vv,--1 - Caze + Cass
I Caj.t + Caist Cat,t + Cai, = 2Cartt
where the inequality is due to Lemma 4 and the UCB arm selection strategy of our algorithm. Therefore, bound the cumulative regret conditioned on event & as follows:
To
R(T)-
R
R
R
1=1
t=1
t=
T Σ
To +
min(2. R,}
(18)
T=
< To + Σ
Σ
min minn2,, 2,3 xa. M F2
(19)
jml
To TT +ET
< To + 28
Σ
min 1, [ee M
/=1 TOSEST deET,
To 2,
Ti, Σ
min 1, ||E 112
(20)
TaStST ,,
1+ TI2
To + 28
TI,
2d od
(21)
Ad 41
1=1
TI2
Too + 2,V mT
2d
1
(22)
Ad 41,3
1- TL2
1
TL2
< To +
/dlog
+ 2 log
+ V.)
2dml log
1
(23)
d,
Xd + 41.2
20

---

Published as a conference paper at ICLR 2025
where Equation (18) uses R, I 2. Equation (19) uses Lemma 4. Equation (20) uses the Cauchy- Schwarz inequality, and we denote the number of times cluster j is selected as Tz, Equation (21) uses Lemma 5. And Equation (22) is due to the Cauchy-Schward inequality and ΣØ=1 Tı = T.
Let 6 $ and plug Equations (23) and (3) into Equation (17), we have
TL2
TL2 Ad + 41,2
B[R(T)) s 4+ To +2
(1 I
1+
2og((T) + VA
2dmi log
1+
dd
8L? log(udT),,
512d
< 4 + 16u log(o)) + 4u max
log( og(u())
d
72
TL2 +
(lgg(T) + v3) 2dm
TL2 1+
+
dlog
+
dx
Ad + 4T2
= o
ud
log(T) + (VmTlog(T))
72
C THE SET-BASED ALGORITHM UNISCLUB
C.I DETAILS OF THE UNIUC ALGORITHM
In this section, introduce set-based algorithm named Uniform Exploration Set-based Clustering of Bandits (Un SCLUU), which inspired by SCLUB Li et al. (2019). Instead of using graph structure to maintain the clustering information, SCLUB uses a structure for the same purpose. UniSCLUB inherits the set structure from SCLUB, but incorporates the uniform exploration to enhance its performance. The set structure not only supports the split operations which are similar to those in the graph structure, but also enables the merging of two clusters when the algorithm identifies that their estimated preference vectors are closely aligned. By allowing for both split and merge operations, SCLUB can adapt to the underlying clusters more flexibly and expedite the overall clustering process.
The details of Un iSCLUE are shown in Algorithm 2. The algorithm maintains information two levels. At the cluster level, a cluster index J contains the indices of currently existing clusters, and for each cluster E J, the algorithm maintains the set of users C in this cluster and other corresponding information such the estimated preference vector 0' Initially, there only single cluster containing all users. At the user level, for each user i, the algorithm maintains the estimated preference vector Ō,, at round /. and other corresponding information. Additionally, all users and clusters are associated with "checked" or "unchecked" status to indicate the estimation accuracy of their preference vectors. UniSCLUE proceeds in phases (Line 1) and each phase N4 consists of 2 rounds. At the beginning of each phase, all users revert to the "unchecked" status (Line 2). When user first appears in a phase, it will be marked as "checked" (Line 14). A cluster is marked as "checked" once all its users are checked. The algorithm will only consider merging checked clusters, so avoid premature merging because of inaccurate preference vector estimation. At round a user it comes with set A, of items (Line 4), If t < 2To (with To defined in Equation (24)), Uni SCLUB uniformly selects the arm de from A, (Line 9). Otherwise, determines the cluster j to which the user i belongs and selects the item based on the cluster information (Lines 6 and 7). The algorithm updates the corresponding information of both the user and the cluster after receiving the feedback of the selected item (Lines 10 to 12). Then the algorithm determines whether any split or merge operations are necessary (Lines 13 and 15). If the estimated preference vector of any user within the cluster j diverges from that of user i, the algorithm will split i, from the cluster (Algorithm 3). the estimated preference vectors two checked clusters are closely aligned, a merge operation will be performed (Algorithm 4).
Since no clustering information utilized during the uniform exploration period, Uni can only update the user-level information. Then the algorithm clusters all users round 2Tg, and continues updating both user and cluster information subsequently. This implementation makes Uni SCLUB more efficient and robust compared SCLUB.
21

---

Published as a conference paper at ICLR 2025
Algorithm 2: UniSCIJR: Uniform Exploration Set-based Clustering of Bandits
Input: X, 8, Ags 6, 7
Initialization: Initialize the cluster indexes by 7 {1}.
Let M Odxd, M AI bo = 0ax 7 = =0 = [u].
Let St,0 Odxd; bı,0 0ax1, T,0 0, Vi [u].
Define /(T,,) = (v 2 (2lg(u/0) / + dloog(1 + Ticke
+ / + Piede/2.
Ad
Define To A 16u log( :) + 4u max 8L
A log( ud
512d log (²)
7
for ... do
Mark every user unchecked for each cluster. for = ..... 2 1 (terminate when t >> T) do
Receive user index i and arm set At
ift > 2To then
Find the cluster j E I satisfying is E E
Select arm ar = arg max (0') + BV x (M' -'a
7
else
Select a, uniformly random from A₁
Receive reward
I1
Update statistics for user is, others remain unchanged:
S S + Fa, x bi.t = bi, + Ti
Th.: T,,,-1
0.,, (AI + s.,)) b...
Update statistics for cluster others remain unchanged:
M M Lo, x1. b' b + Tiaa:
T = 7 11, M' = M AI, 0 = (M')-10
13
Run Split
Mark user as checked
15
Run Merge
Algorithm 3: Split
if 3i' E C s.t.
Ō Ōr.r [(Tiee)) + ((Tr..)) then
2
Split user it from the cluster j:
M = M St,tt b² bi bi.
T = T
Thale Ci = Ci {ir)
M' M AI, O (M') (M')-bb b²
Generate new cluster j' containing only user iz:
M St.te b' bi.ts T -ig,, C/ (ir) M MD +AI, Ø = =
J J-J
C.2 THEORETICAL ANALYSIS OF UNISCLUB
Theorem 2 (Regret of Uni SCLUB). Under the stochastic context setting (Assumptions 1, 2, 3), the expected regret of the Un SCLUB (Algorithm 2) satisfies:
E [[((T) = O ud
log(T) + dVdddm (VmTlog(T))
Proof. From Lemma 6, Algorithm 2 will have correct clusers after 27, with probability - 35.
22

---

Published as a conference paper at ICLR 2025
Algorithm 4: Merge
for any two checked clusters J1, E I do
@ @ < [(T + [(T))) then
Merge clusters and j2:
M M M 6 = 6) + bi,
T T TT,, Ch = Ch UC
M = M AI, 0 = )
J J {52)
Based on Lemma 6 and with To replaced by 2Tb. we can derive the counterparts of Lemma 4 and Lemma 5. Then, similar to the proof of Theorem we have
TL
2 log((T) + vz) 2dm' log
TL2 Ad + 4L2
B[R(T)] - 4 + 2To + (
Vdlog
1+
1+
dA
8T, log(udT),
512d
log(uT)
S 4 + 32m log(uT) + 8u max
A
72
2L
+ 2log(T) + vz) 2dmiT log
TL2 Ad + 4T2
+ 2
V dlog
1+
1+
dA
o ud
log(T)) + dv mT dv log(T))
R2
Lemma 6. With probability at least 1 - 35, Algorithum 2 can cluster all the users correctly after 2Tg where
To 2 16u 16
ạ 4u max
{ 18L2 Ax
log
uud
512d
log
)
σ )
(24)
8
72
Proof. From Lemma 3, with probability at least 1 - 35, we have 00,0
S f(Ti,) s
2, Vi E [u], when 2 To-
We now show that under this condition, Algorithm will split well, i.c, the current clusters are subsets of true clusters. To guarantee this, round I, for the user i, and the corresponding cluster j. we need to verify that: (1) if the current cluster j is a subset of the ground-truth cluster of user i, then user i, will not be split from the cluster j. (2) if the current cluster contains users that not in the same ground-truth cluster as user i, then user i, will be split from the cluster j.
To prove (I), show the contrapositive of (I): if user it split from the cluster j. the cluster contains users such that is and these users are from different ground-truth clusters.
If user is is split from the cluster by Algorithm 3, i.e., there exists some user i' E C such that 0 0v. [(Ti,.)) (T)r.)), due to the triangle inequality, we have
- 00001112 10,1-0'00112 |100((0)) 00((() 112 2 110,,t 0v. 10,,,t - (0(())) 1|2 - 10,,- 0 0vr,ll2 f(T....) f(Tv.)) 0.
By Assumption 3, (oslit) gili') -
||
0 implies that users iz, i' are not in the same true cluster.
To prove (2), we show that if there exists some user C. and - - 7, we have
|0_. 0v.s| B,.e/1 2 (g)(h)) ( gg((e)
0 - Balhil| - -110r. -x)l0) 11,
2
7
7
7
2 (TTr..) +((T.)),
4
2
23

---

Published as a conference paper at ICLR 2025
which satisfies the condition of splitting. Thus, user in will be split out from the current cluster j. Therefore, when t >> To. each existing cluster at will not contain users from different true clusters.
Now show that Algorithm 2 will merge well so that only correct clusters remain. For two checked clusters j1 and j2, we need to verify that: (1) if ji and je are not merged, they are from different true clusters. (2) if and j2 merged, they are from the same true cluster.
We only consider the case where the existing clusters are subsets of ground-truth clusters because of splitting. For convenience, denote the true preference vectors of clusters j1 and je by @ and 0 which is reasonable since each of they only contains users with the same preference vector.
To prove (I), if ji and je are not merged, i.e.. inequality, we have
| @:*|
2 f(Tă) + f(TTt), by the triangle
1000 0 2 100h 0 112 100 0 || 1 00
2 0 0 |l2 f(T - f(T52) > 0,
which implies that j1 and j2 are from two different true clusters.
To prove (2), we show a contraction: ji and j2 are merged, but they are from different true clusters,
i... |10 002l1 1|2 7. we have
| م0 112 |000
0²0 1|2 110 - 0³ 112 10 002
7 2 (f(T )(T
2 f(T f(T 2
v 3. However, this contradicts the condition of merging. Therefore, if ji and j2 are merged, they are from the same true cluster.
because that f(Th) +
f(T)) f(T
We double the time To to 2T, to ensure that all users in each cluster can be checked and provide sufficient time for the split and merge operations. Therefore, after 2T,, all the clusters the ground-truth clusters with probability at least 36.
D THE PHASE-BASED ALGORITHM WITHOUT KNOWLEDGE OF
D.1 DETAILS OF THE IEFASRNNTCLAN ALGORITHM
In this section, we provide an algorithm PhaseUniCLUE (in Algorithm 5) for the online clustering of bandits when the preference vectors' distance between clusters is completely unknown. We also theoretically provide an upper bound of its regret Theorem 3.
For convenience, we first define the following notations used in PhaseUniCLUB:
giinit A 16u log ( + 4u
8L2
log
ud
( A
4u
2 2-*x log
512d
U
(25)
Same as UniCLUB (in Algorithm 1), PhaseUniCLUR also maintains a dynamic undirected graph G, ([u), Ee) over all users for the purpose of clustering. However, to cope with the unknown 7 PhaseUni CLUB leverages the idea of the doubling trick. Specifically, as depicted in Algorithm 5, the algorithm first runs for Tiiit rounds with uniform exploration (Line I to Line 5). Then, proceeds in phases. For each phase = 0, l, we divide it into two subphases: (1) the first subphase (named the exploration subphase), consisting of (()) rounds, where PhaseUni CLUB selects an item uniformly from the item for each coming user (Line 11); (2) the second subphase (named the UCB subphase), containing (2'/2 1 1)T(>) rounds, where P PhaseUni CLUB identifies the cluster of each coming user (Line 13) and selects an item based on the estimated preference vector of the cluster (Line 16). Meanwhile, in each round, after receiving the reward feedback (Line 17), the algorithm updates statistics for user & (Line 18), and determine whether to delete any edge between and its neighbors (Line 19).
Due to insufficient information about the distance gap 7, PhaseUniCLUB keeps uniformly ex- ploring users' item sets. Unlike UniCIUB, PhaseUni CLUB distributes the uniform exploration
24

---

Published as a conference paper at ICLR 2025
Algorithm 5: PhaseUni Phase-based Uniform Exploration Clustering of Bandits
Input: X, 8, Ag 8, I.
Initialization: Let Go ([u), F be complete graph.
Let S 0xxd: 0i,0 1 7o = 0, E [u].
Define f(T,t) (v log(u/8) /) d log(1 + Ti Ad
for = 1,2...., Trimi do
Receive user index is and arm set A
Select ar uniformly at random from Ar
Receive reward
Update statistics for user ig: Stn, bi Thet Oiet
for 5 = 0, 1....
for r = 1.,....,22 2 T(*) (terminate when > T) do
{= +=1+1
Receive user index is and arm set A,
i S. ('ss) then
Select a, uniformly random from At
else
Find all neighbors of user in G,-1 and include i, form the cluster V,
Mv Eiev, St,-1, M Vv,t-1 = AI + Mv
bv,,-1 = Eiev, bi,-11, Ov, = M Vi,t bV, Tv,,-1 Σiev, The
Select arm az = arg aa 0% 0/ + 3 x.. S...v.ae Vi.1-1
Receive reward
Update statistics for user i,; Si,,, bir,,, Ton,e Oi.. Delete edge (fe, E Eç-1 if
18
Øn,t - 02.1| [(Ture)) + f(Te.)
and obtain an updated graph G, = ([u), Ex)
across all phases. During the exploration subphase each phase 8, PhaseUn CLUB focuses on estimating the users' preference vectors a precision level of 7/s In the subsequent UCB subphase, it clusters users based on the current precision level. If 7, there is risk of users being incor- rectly assigned clusters they are not belonging user appears, PhaseUni CLUB only identifies the neighbors of the user to form a cluster, rather than finding the user's entire connected component in UniCLUB. Additionally, with carefully chosen phase lengths, the regret of F hasseUni CasUBBnnnUUBB can be bounded sublinearly. The approach of identifying only neighbors also applied Wang et (2023a), but to avoid misclustering due to model misspecification. Moreover, PhaseUn CLUB achieves better regret bound compared to that in Wang et al. (2023a). While their regret term associated with this error lincar with respect to T, ours scales 2/3
To mitigate this risk of misclustering, when
D.2 THEORETICAL ANALYSIS OF PHASEUNICLUB
To bound the cumulative regret of PhaseUni iCLUP we present the following lemmas.
Lemma 7. Denote 7ss 2 and Cp
With probability at least 1
102
3 logz (Cpiog (u705 + 1)6, after the exploration subphase in any phase 0, 0..... for all users i [u], we have
0 05(1)
<
4
25

---

Published as a conference paper at ICLR 2025
Proof. According to Lemma 3, with probability 2 1 - -3,, after the exploration subphase in phase
$ = 0, ., for any user E [u], we have
0510)
Te 4
S
Denote the number of phases for PhaseUniCLUB by Np. Since phase contains 2*/27((s) rounds, Np is the maximum integer satisfying
N--1
T
20/2 4u
512d
log 8
( 11
S T.
2 2~
By some calculations, we have
V2 Tinit)
(Cp(T (Cp(T-TTmy -Tint) log 8
+1 1)
Np S 3
log2
1024ud +1] = =log2
where we denote C₂
VZA
I024ud
Applying union bound over all phases. we have that with probability at least
3 loga2 (Cplog
T (u/5) +1 +1)6, after the exploration subphase in any phase 0, o......, for all users (u/5)
i E [w]. |00,, - Q0(()) 21 S 3/ holds.
Lemma 8. With probability at least 3 3log2 (Cp Tog (u/8)
T + 1)0, in any phase s, for two users
1,, f2 E Ve, we have
( gilbs)
S S700
Proof. In phase 8, for any two i2 Ve, it satisfies
@ Shit--iipk 01g11 S ((T + ((Ti
By the triangle inequality and Lemma 8, with probability least 1- 3ogg (Cp + 1) 1)0, we
have
S | - 0.g-1 + +1100s. - + -10011-002111
0ig.1
I 7s
+ 7s f(T(ne)) + f(Teer) S 7/.
4
4
Lemma 9, With probability at least 4 olog2
(Cptog (1/oo + 1)66, in any phase s, we have
2L'r/
x (0v,t11-00 -Bi(t)) S Ca,t+
117- 7}. Am
where Ca.t A 3|| My
and V /log(1
+
TL2) dA
+ 2log( + VX.
Proof. In phase s, the confidence radius for users' preference vectors is 1. If 7s > user is may be mistakenly grouped into the wrong cluster, i.e., V, + Vi(i.) Accounting for this error, we analyze the following two cases:
Case 1: user i correctly clustered, i.e., V, Vi(te)- Same as Lemma 4, we have
xJ_ (0v,,t11-8(t14 -
< B11 M M.
with probability 1 4 loga (Cpiog To (1705 + 1) 1)0
Case 2: user i, is mistakenly clustered, i.c., V₁ * Vi(a which happens when % > 7. Then,
0v. (0())) = A
Σ
Σ
g((s))
Lz. Car
T+
EEi
rE|t-I]:LEV.
26

---

Published as a conference paper at ICLR 2025
AI +
Σ
Ta Fer
Σ
Tar (x 01 n1))
rEjt-I]ai.Ve
rE(t-I]:i-EV
-M -M
V2,-1
Σ
Ca, aar (0i, - 02,) +
Σ
Da 16 Oi +
E
Da, 11
00(1))
rE|t-1]i,EV.
TE(t IJsi,
rElt 1]si, EV
-M -Mv.t-
Vi,t-1
AI+
Σ
Da v T
F/a7
0i - -00;, +
Σ
Ta, 1/
-gil(e)
FE|t-IliiEV
TE[t-I]a,EV
+ M Mv.--1
Σ
Da, or (Bir - -ii))
T
EV
AM 1
+ V.,1-
Σ
Fa, Tr M V/,t-1
E
Te, we (0,, 0.)).
EE(t_Ilit,E,
Eelt-IjiiEV,
where we denote M VV,--1 = Al + Mv
Then from Lemma have
x!! (Ov.,t11-0 -Ui6)) s 31| My
+
x M
Vi--1
Σ
T La. Se (0t, - Oc.) (26)
Felt-IJiiev
Now we bound the second term in Equation (26).
x. M
V1,1-1
Σ
Ba, x T (0,, - -ii)
rEit-
EV,
<
xalla
M
Vi,
Σ
La, x. (0;, (0;; 0i,)
(27)
2
7Efe-I]iLEE.
<6
M
M
1/2
Σ
(ar x 112110:. - -1il12
(28)
2
TELt- EV
STrysdmax M Vi-e-1)
Σ
| 202
(29)
Ere(t-Ili,ev. L <L7
(30)
Amio (Vi,t-1)
Tv.,t-I. 11
<1/ Tv.,v.e-1 +
(31)
21273
Xx
where || vi lle and [a, x 11 are the spectral norm of matrix M My,t-1 and La, x Equa- tion (27) is because the Beuchy-Schwarz inequality and the induced matrix norm incquality. Equation (28) is due to || L and the induced matrix norm inequality. Equation (29) fol-
lows Lemma 8 and that M Vi is PSD. Equation (30) is because of [a, x__ lla = T. and Equa-
tion (31) follows Lemma
Therefore, we have
21 (rys 7).
M
v
d
Combining the two cases, finish the proof of Lemma 9.
27

---

Published as a conference paper at ICLR 2025
Now prove the regret upper bound of PhaseUniCLUB.
Theorem (Regret of PhaseUniCLUB), Under the stochastic context setting (Assumptions 1, 2,
3), but is unknown, the expected regret of algorithm PhaseUniCLUB (Algorithm 5) satisfies:
B[R(T) = ( ( ud ?
[ud Ax
lTg(T)
T
log (T) dVmTlog(T)
Proof. For any round 1. in the UCB subphase of any phase with probability at least 1 T Cp log (u/5j + 1 8, we have
4 logg
R = x gi(+t) x², ,1 @((ia)
z (gilit) -v,,e11) 0v, -az.e)
(x (2 Bv, + Carst)
(f((te) -vv.t-1) Cais Casst
was
21,21s 177s > > + Cau,t +
2D2 11% 7} Cop + Casit
S Cay +
A
No
4L²7, d
2C
1l4 > 7}.
where the inequality is due to Lemma 9 and the UCB arm selection strategy of our algorithm.
Denote the regret in phase s by R(s), With the same probability, for any phase s, we have
pitil E 22/2g((0))
R(0) < ((,)
Σ
R
t=T >2 20/22(1)--
Tiol E. pzz 22/27(p)
< <(() +
dx I (76 > 7) (2e/2 - 1)7( +
2C
t= + 2p 28 (+)))
Summing up the regret over all phases, we obtain
N
R(T) < Tinks
R(*)
< Tinit
N
(++) +
AL'ra
1 > >7 (25/2 -1)7(0) +
I Σ
2Coet
==0
T=
< iiit
N₂ -1
T()) +
11.273
1(7s > 7) 7 -1)T(0)) -277)) +2 2m 2mTddog
1+
TT2
d
Xd 4I2
==0
(32)
where Equation (32) follows Lemma and the proof Theorem 1.
Now bound the second term in Equation (32),
T(0) + AL2ra (2 - -))((s)
N₂
4L2
5
((s)
+
11% > 73 22/2
==0 Xa
Xu
8=
N₂-1
4L2
Σ
1
194s > 7/ I(a)
(33)
Axz
Cp - Fini
8L2
Bogudlog((
+1)
+
log( x
28

---

Published as a conference paper at ICLR 2025
where Equation (33) is due to "/ 2-
Then, with probability at least 1 - -44 loga (Cp ( (w] T + +1)6, we have
TL3
+ ((211 log(
)
Tinnt
8L² 72
2048udlog('
R(T) S Tini + 23 2mTdlog 1+
+1
+
Xd + 4L2
d
Recall that 7 = 16u log ( total expectations, we have
+ 4u SL Ax
log( ud and Cp
Let å } and by the law of 1024nd
V22=
TL2
+ ((orre
- -
DL 72
2048ud log (
E[R(T)] < Tinit + 1
2mTdlog
1+
+ 1
+
Ad + 412
log( (t)
Ag
T
+ 18877 +1)8.7
+ 4loz2 Cp
log
log (u/6)
8L?
TL? Ad + 4L2
< 16u log(uT) + tu
log(udd) (uddT + +33
2mTdlog 1
A
Cp("T (
+1
SL2 Am
2048ud log(u(T)
4 4log2
C log (uT) +1
T
log(%) 11)
ud
ud
= =0
log(T) +
T log (T) + dv mll mmT log(T)
X2
E THEORETICAL ANALYSIS OF SACLUB AND SASCLUB
Lemma 10. Under the smoothed adversary setting. SACLUB and SASCLUB have the following lower bound on the expected minimum eigenvalue of v.
Amin (E[ 21,]) 2
Ax
log K
where Cj is some constant.
Proof. Fix a time t. Let Q be a unitary matrix that rotates o.,, to align it with the x-axis, retain- ing its magnitude but zeroing out all components other than the first component, i.e., Q+ (IIO,, O,.. Such Q always exists because just rotates the space. According to the UCB arm selection strategy, Ea, = arg max 0 0 + Co.t). where Ca.e = 3 aal Denote the i-th arm in A, as or we have
0).
Ø. Da + Ccat))
Amin EE [2 = =Amin
E
m.r
x
arg max aeA,
min
E
arg max dE.A
①T (T, + Caatt)
min
(w T x
x arg max aEAL
0J 1i Caait)
2
min
Var w x
arg max aeA.
ØJ 1 + +a.s)
w:
min
Var
(Qw)
Qu
arg max atd.
(QQ0...) TQx. Cut))
(34)
w: w =1
min
Var
Qu
arg max aEA.
0 (Qxa)) Ca.t)
(35)
w:
29

---

Published as a conference paper at ICLR 2025
(Qui. + Qeia) + Carui
min
Var
E arg max [ un Qe
(36)
w: we =1
110
(Qui + Ex,)) Courit
min
Var
w
arg max (
(37)
wn: 10: W0
110
where Equation (34) uses the property of unitary matrices: Q'Q matrix Q so only the first component is non-zero and we use the fact that minimizing over Qw is equivalent to over w. Equation (36) follows because each arm I f + e and adding constant to random variable does not change its variance. Equation (37) is due to the rotation invariance of symmetrically truncated Gaussian distributions.
Equation (35) applies
Since Êt,: ((0, o² T) conditioned on (Et,))) < R, E [d]. by the property of (truncated) multi- variate Gaussian distributions, the components of Er, can be equivalently regarded as d independent samples from (truncated) univariate Gaussian distribution, i.e., (E1,)) NN o²) conditioned on ((E,,))) - R. Vj E [d]. Therefore, we have
Var ww
Var
W
Σ
i Var (e:),
i=1
i=1
where the exchanging of variance and summation is due to the independence of e,. Therefore, let Pt. = (Qu4a) +
Car.ut
we can write
min
Var w &
arg (Ex(() + pr.s) E
min
wj Var
Ej
arg (( pr.s) e.,ciE[K]
w:
j=1
min
w Var
E1
E arg max ((e,,) + De,s) (
w:
|=1
w Var
Ej
arg max max (EI,)) + PP.s)) [
j=2
min
w Var
E
arg max Pc.)) [k]]
Σ w/ Varle,l
w: tw |=
5=2
min
wi Var
arg max + Pe.))
(1 wioo²
w: to
|
min
Var
E1
arg max ((t,)) pt.))) 00 [.,
C1
log K'
where in the last inequality, we use Lemma 15 and Lemma 14 Sivakumar et al. (2020) and get
2²
Var E1 E arg max((E + pr,s) 2 Var E1 arg mag((x)).))) [
C1 log K
Lemma 11. Under the smoothed adversarial setting, for algorithms SACLUB and SASCLUB,
8(1+ log(() log ad
with probability at least 1 for any E 10, if Tı, 2
=
8(1+ log( ud 3 for all users E [u], we have A,
AoT 2
Amin (St,)) 2 2 K
E [u],
where C1 is some constant and X₂
log lo
30

---

Published as a conference paper at ICLR 2025
Proof. The proof follows the same techniques Lemma' 2. The main difference lies in two aspects: (1) in the smoothed adversary setting, the length of feature vectors is bounded by 1 + vdR instead of L. Therefore, Amax (Da, x I (1 + vdR)². (2) the computation of Mmin needs to refer to Lemma 10.
Specifically, to compute Mmins by the super-additivity of the minimum eigenvalue (due to Weyl's inequality) and Lemma 10, we have
o² log
Mminn
Amin
Σ r
Σ
Amin (Kl [x,
x._1) 2 ci
TE((]it,=
On the other hand, we have
Umax
Amax
Σ
E a 2o.
rE]t],i,=i
So by Lemma 12, we have for any E E (0, 1),
Pr Amin (St,) $ (1 =TTTi, σ²
< Pr Amin (St,) S (1 E) {m
log K
Mmin (imin/[1+//R))
c
d
8)1-8
<d -
where the last inequality is because e 2 is decreasing. Then the proof follows by the same derivation
as Lemma 2, except that dr is replaced by X.
c10²
log K
Theorem 4 (Regret of SACLUB and SASCLUB). Under the smoothed adversarial context setting
(Assumptions I, 4, 5), the expected regrets of SACLUB and SASCLUB both satisfy:
E[R(T)] =0 ud
2xx log(T) + d.dvdTfloo lVmmllo()))
a² where Xy = C1 log K for some constant Cj.
Proof. For algorithm SACLUB, similar to the proof Theorem 1 under the stochastic context set- ting, we need to derive the counterparts of Lemma 3, Lemma 4, and Lemma 5 under the smoothed adversary setting according to Lemma 10 and Lemma 1.. The proofs use almost the same techniques with X replaced by X. Similarly, the proof for algorithm SASCLUB requires the counterparts of Lemmas used in the proof of Theorem 2, thus we skip the details.
F TECHNICAL INEQUALITIES
We present the technical inequalities used throughout the proofs. For inequalities from existing literature, we provide detailed references for readers' convenience.
Lemma 12 (Matrix Chernoff, Corollary 5.2 in Tropp (201 1)) Consider a finite sequence {Xx} of independent, random, self-adjoint matrices with dimension d. Assume that each random matrix satisfies
X Z
and Amac (xs) S R almost surely.
Define
Y
Σx
Xx and Amin Amiu )minn(E(Y) Amiu
B(XA]
Then, for any E (0,
e- (1 8)1-8
Mmin/ R
Pr
Amiu
Σx, X <1 - 5) Id
31

---

Published as a conference paper at ICLR 2025
Lemma 13 (Lemma 8 in Li & Zhang (2018)). Let 21, , be independent Bernoulli random
variables with mean 0 < p _ 2' Let 0, B 0, then with probability at least 6,
16
4B
Σ
2 B, 14
log
+
P
P
sml
Lemma 14. For 0,b 0, ab 2 1, if 2 2a log(ab), then
2 a log + bt).
Proof. Since t increases faster than a logg(1 + bt). suffices to prove t 2 a alog(1 + bt) for 2a log(ab). Equivalently, we only need to show:
2a log(ab) 2 aloo(1 [1 2ab log(ab)) = (ab) + a log (2 log( 1o0-2obaaa 2b))a))) 1 which follows by observing that ab 2 2 2log(e 2ab ab) = ah + 2 log(ab) holds when ab z 1.
Lemma 15. Let X1, X2y..., Xn be a sequence of independent and idenfically distributed (i.i.d.)
random variables, each following a distribution P. Let Y be a random variable that is uniformly XnJ, then Y follows the same distribution P.
selected from the set
Proof. It suffices to show Pr|Y A] = Pr[X, E A]] for any measurable set A. By the law of total probability, we can express the probability that Y falls into the set as:
Pr|Y E A = Σ Pr(y EAIY X,JPr[Y Xi]
Σ Pr[X A = X.)
=11
= Pr [x E A],
where we use the fact that X, are i.i.d and Pr Pr(Y- = X.] = 1/n. Lemma 16 (Determinant-trace inequality, Lemma 10 in Abbasi Yadkori et al. (2011)). Suppose X1. X2... Xt E Rd for any 1 S S t. X 2 - L. Let V AI A E X.X for some
0. Then,
11. del(V,) A
d
G MORE EXPERIMENTS
G.1 EVALUATION UNDER THE SMOOTHED ADVERSARIAL CONTEXT SETTING
To implement the smoothed adversarial contexts, for each arm in the synthetic dataset and three real- world recommendation system datasets, add Gaussian noise vector sampled from A I I/10). As illustrated in Figure 2, for all the datasets, SACLUR and SASCLUB (which are essentially adapted versions of CLUB and SCLUB) outperform LinUCB-Ind and LINUCB-Onc. Additionally, under the smoothed adversaria setting, LinUCB-Ind and LINUCB-One exhibit more significant fluctua- tions compared SACLUB and SASCLUP, highlighting the increased complexity of the smoothed adversarial setting relative to the stochastic setting. This corroborates our theoretical results, show- ing that with some minor changes, the existing algorithms CLUB and SCLUB can be extended to the more practical smoothed adversarial setting, which is closer to the original setting of contextual linear bandits (Abbasi-Yadkori et al., 2011).
G.2 CUMULATIVE REGRET WITH DIFFERENT ARM SET SIZES
Under the stochastic context setting, we evaluate the impact of the arm set size [A,] K by ad- justing K = 80, 100, 120, 140 using the Yelp dataset, since it has the largest number of users. As demonstrated in Figure 3, there is substantial amplification of the cumulative regrets the arm set size increases. This observation validates our theoretical results (Theorems and 2), where the regret upper bounds of Uni CLUB and Un SCLUB do not involve K.
32

---

Published as a conference paper at ICLR 2025
Complrow Regge
200
0000
SACLUB
SASCLUB
-B-
LisUCB-Ial
LinLCB-One
Figure Comparison cumulative regrets under the smoothed adversarial context setting.
10
Nurther of samee 30
Sumber of ama:: 100
Nurteer smm: 120
Narchrr of same 140
Chrnntatiee Regan
0800
1000
112.0
1001
10000
1980
Rrurch
Brariss
Reards
UNiSCLUB
DaKCLUI
CLUB
SCLLU
LaaUCB-
LiKUCB-00
Figure 3: Comparison of cumulative regrets with different sizes.
-107
of carre
tom::
Namber
of sume:
30
Canitimee Regien Regiet
3000
1000
5000
5000
10000
3000
1000
1300
2000
100.0
2000
400
1000
9000
17000
300
1300
(200
5000
1000
UaiSCLUB
UaCLUU
LaaDCB
Figure 4: Comparison of cumulative regrets with different numbers of users.
33

---

Published as a conference paper at ICLR 2025
G.3 CUMULATIVE REGRET WITH DIFFERENT USER NUMBERS
To examine the effect of the number of users, we adjust the number of users a = 40, 50, 60, 70 while keeping the number of clusters
10 using the Yelp dataset. As shown in Figure 4, our proposed algorithms exhibit significant advantages compared to the baselines. Additionally, as the number of users increases, the cumulative regrets also increase. This is expected because a larger number of users poses greater challenge in learning their preference vectors and identifying the cluster structures.
G.4 COMPARISON WITH NON- WWw.CCUSSTRRGGGG BASED BASELINES
In this subsection, compare our algorithms with two additional graph-based baseline algorithms, GOB.Lin (Cesa-Biane Bianchi et al., 2013) and GraphUCB (Yang et al., 2020), within the stochastic con- text setting. While both GOB.Lin and GraphUCB leverage user similarities to enhance preference estimation, their methodologies fundamentally differ from ours (and all the other clustering algorithms) in two aspects: (1) Neither GOB. Gin nor GraphUCB assume the existence of user clus- ters or explicitly perform clustering, and (2) both algorithms assume prior knowledge of a user relationship graph. Additionally. worth noting that both GiB and GraphUCB have signif- icantly higher computational complexity compared to clustering- based algorithms, as they require operations such as multiplication and inversion of high-dimensional matrices of size TR. quudxu ud for item recommendation, where is the number of users and d is the feature dimension. In contrast, clustering- based algorithms (including ours) only involve matrix manipulations of size Rdxd
For the experiments, due to the high computational overhead of GOB.Lin and GraphUCB, ran- domly select 20 users (instead of 50 as in other experiments) and divide them into 4 clusters. At each round t. user is uniformly drawn from the 20 users, and 20 items randomly sampled from the full set of arms to form the arm set A,. For GOB.Lin and GraphUCB, the user graph is constructed by connecting users within the same cluster.
The cumulative regret results are shown in Figure 5. Both LinUCB-One and LinUCB-Ind exhibit significantly higher cumulative regret than the other algorithms that incorporate Among all the clustering baaseeiin--baeed algorithms, our algorithms UniCLUB and UniSCLUB consistently outperform their respective counterparts, CLUB and SCLUB, across all four datasets, demonstrating the effectiveness of our proposed uniform exploration strategy. When compared to the new base- lines, UniSCLUB achieves superior performance compared to Gin and GraphUCB across all four datasets, and UniCLUB also outperforms GOB. Lin. Although GraphUCB slightly surpasses Uni CLUB on the Last.fm dataset and achieves competitive results on the synthetic dataset, it incurs higher regret on the Movielens and Yelp datasets compared to Un i CLUB. These results align with expectations, as our setting assumes that users are clustered, which allows clustering based methods to explicitly exploit this structure for improved performance.
similarity.
Syntheric Totret
Moviel ens Dassott
Yelp Davnet
fin Datsvet
Corculan Hegen
82.0
1244
2340
40.01
12:00
Rounds
Boands
Roands
UnISC3.A JUR
--- UnCCLU
-1t. C1.UR
S(3/JB
cob.. Lit
-
GrapMiCC
GONlin
Figure Comparison of cumulative regrets with more baselines.
To demonstrate computational complexity, we also measure the average running time of all algo- rithms across datasets, with the results summarized in Table 2. As shown in the table, GOB. and GraphUCB exhibit significantly higher average running times, exceeding those of other baselines by more than an order of magnitude. In contrast, our algorithms, UniCLUB and UniSCLUB, achieve computational efficiency comparable to that of the other baseline methods.
34

---

Published as a conference paper at ICLR 2025
Table Comparison of average running time (in seconds).
Time(s)
Algorithms
LinUCB-One
LinUCB-Ind
CLUB
SCLUB
UnICLUB
UniSCLUB
GraphUCB
GOB.Lin
Datasets
Synthetic
2.79
2.61
3.02
7.70
3.02
8.28
128.32
204.55
MovieLens
9.78
9.62
10.11
16.96
9.96
16.80
117.25
214.96
Yelp
15.05
12.13
119.86
216.35
4.66
12.18
106.04
35


Reviews:
[{"review_id": "ObNbWFIb6E", "reviewer": "Reviewer_sepG", "summary": "The paper proposes an algorithm for the linear bandits with clustered users, relaxing assumption on the data diversity and achieving less regret incurred by mis-clustering under both stochastic and smoothed adversarial context settings. Empirical performances of the proposed algorithms shows the efficacy and practicality on the real datasets.", "questions": "1. Could the authors explain on the novelty of the theoretical analysis?\n2. What happens when $\\tilde{\\gamma}$ is very small but $\\gamma$ is large? Can $\\tilde{\\gamma}$ be estimated in some ways?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper improves the practicality of the algorithms for the clustering bandit problem by relaxing the strong assumption and analyzing the adversarial context setting.\n2. Experiments are abundant to validate the performance of the proposed algorithms.", "weaknesses": "1. The theoretical analysis seems to have limited novelty and heavily relies on the previous theoretical results.\n2. Some parts of the presentation is hard to read, i.e., variables are defined under Table 1, the regret bounds are stated before defining the variables $\\tilde{\\gamma}$, $u$, and etc...\n3. It would be better to prove an $\\tilde{O}(T^{2/3})$ lower bound to show the impossibility results when the $\\tilde{\\gamma}$ is unknown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Z6rxN6F4yj", "reviewer": "Reviewer_KU8f", "summary": "This paper studies online clustering of bandits, with the goal of relaxing the strong context regularity condition adopted in prior works like Gentile, et al. (2014). \nFor this purpose, the authors first added a uniform exploration phase to the existing algorithms. With the additional knowledge about the gap parameter $\\gamma$, an appropriate value for the uniform exploration length $T_{0}$ can be chosen to ensure accurate cluster estimation.\nOn a parallel direction, the authors adopted the perturbed adversary assumption as Kannan, et al. (2018), and showed that CLUB and SCLUB algorithms by Gentile, et al. (2014) and Li, et al. (2019) now incurs less regret due to failed cluster detection (the first term in regret upper bound).", "questions": "Please see my questions above.\n\nAdditionally, could the authors provide more details on the application of the self-normalized bound from Abbasi-Yadkori et al. (2011) to the first term in Equation 1? Specifically, I would appreciate a clearer explanation of how the filtration is defined in this context, given that the summation is taken over a set of time steps corresponding to the cluster, which is itself random (cluster estimation is based on observed noisy feedback).", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Relaxation of the strong context regularity assumption adopted in online clustering bandits is a well-motivated and important problem.\n\nThe paper is technically sound and easy to follow.", "weaknesses": "1. My primary concern with this paper is its contribution, as it may overstate the extent to which it relaxes the assumptions used in prior works. I wouldn’t consider adding the gap parameter as a relaxation. With this parameter as input, we can incorporate a dedicated uniform exploration phase of sufficient duration (determined by the gap parameter) to ensure accurate cluster estimation. Gentile et al. (2014) required the additional assumption on variance precisely because they did not have access to such information. Without knowledge of the gap, it is impossible to determine the adequate amount of uniform exploration, necessitating a stronger assumption to ensure that the minimum eigenvalue of the design matrix grows rapidly enough, even under UCB exploration.\n\n2. The use of the perturbed adversary assumption in the context of online clustering of bandits appears to be novel, and I believe it represents a meaningful contribution of this paper. However, the discussion on the technical innovation here is limited, and I would appreciate more clarity on this aspect from the authors.\nFor instance, since a key part of the proof involves demonstrating that the minimum eigenvalue of the design matrix grows sufficiently under the perturbed adversary assumption (as shown in Lemma 11), how does this approach differ technically from Lemma 3.2 of Kannan et al. (2018)? Could the authors elaborate on the primary differences in the proof structure when applied to online clustering of bandit algorithms as opposed to greedy algorithms?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "5oWCVbgsCI", "reviewer": "Reviewer_BvdA", "summary": "This paper explores the clustering of contextual bandits in both stochastic and adversarial context settings, introducing a new set of assumptions that improve upon some unrealistic assumptions in existing work. The two proposed algorithms are modifications of existing ones, incorporating pure exploration periods. Regret bounds for these algorithms for two setups are also provided.", "questions": "This work provides slightly looser regret bounds for both algorithms. The reviewer conjectures that the regret bounds can be tighter by revising the existing proof techniques. \n\nLogarithmic regrets are known to be attainable for standard contextual bandits under some assumptions. Do the authors think that the regret bounds can be improved to logarithmic ones under some specific assumptions? If not, could we have a square root lower bound? \n\nIt is possible that UCB-based algorithms cannot have logarithmic ones. Is it possible for other types of algorithms?\n\nIf logarithmic regret bounds are not attainable, could the authors please explain what differences between standard contextual bandits and this work make it infeasible?\n\nL219: Could the authors please clarify with respect to which variables the expectation is taken? \n\nFor typical adversarial setups, as contexts are not random, they cannot have expectation and variance. Could you explain more specifically about the adversarial setup that the authors suggest?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "This paper is presented well so that uninitiated readers can understand the work. Also, this work removes the nonsense assumptions in the existing literature and suggests a new set of assumptions for better analysis.", "weaknesses": "The statement in L54-61 should be revised as it can be misleading. This is because the iid and minimum eigenvalue assumptions are still chosen in this work. (The assumptions for adversarial setup should be separately stated.) In addition, this work adopts the bounded context ||X||\\leq L, which is stronger than the subGaussian assumption for contexts. Lastly, this work has additional assumptions about the parameters, which\\|\\theta_i - \\theta_j\\|>gamma. Even though the reviewer acknowledges that the subGaussian assumption (\\sigma^2 < lambda_x/8log 4K) in the existing literature does not make sense, the reviewer believes that more substantive contributions beyond introducing new assumptions with an initial pure exploration period are necessary to be sufficiently impactful.\n\nL198-207: the indices should be corrected.\n\nAs accurate clustering is a crucial topic in this work, the authors should state the algorithm for clustering, rather than simply referring to it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "h47VAXctBA", "reviewer": "Reviewer_wksx", "summary": "The paper provides novel algorithms to solve the online clustering of bandits problem. Their setting relies on a slightly different set of assumptions w.r.t. the state-of-the-art. They provide theoretical analysis of their algorithms and also provide a proper experimental analysis to show the performance of their approach. Their approach shows little improvement over the performance of state-of-the-art algorithms in the experiments.", "questions": "Why didn't you test the performance of your algorithms for the synthetic data experiment against benchmarks such as  Gob.Lin [Cesa-Bianchi et al., 2013] and GraphUCB [Yang et al., 2020]?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The writing and presentation of the paper is done with a high quality. The paper highlights an interesting theoretical change w.r.t. the state-of-the-art. It can be even interesting from a practical point of view for real-world applications in large scale.", "weaknesses": "I am not sure if it is a weakness of the approach, but it seems [from the experiments] that the presented algorithms do not improve upon state-of-the-art significantly. In addition, I believe the authors could test the performance of their algorithms against more benchmarks such as Gob.Lin [Cesa-Bianchi et al., 2013] and GraphUCB [Yang et al., 2020], but it is not done.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)