acceptodds
Under review as a conference paper at ICLR 2027

Online Clustering of Bandits without Feature Diversity

Abstract

Online clustering of bandits shares information across heterogeneous users by pooling observations within groups of users whose similarity is inferred from observed rewards. Existing methods typically group users when their preference vectors have the same values in all coordinates. To accumulate enough information to infer such groups, these methods rely on either distributional assumptions on feature generation or access to an action set spanning the entire -dimensional feature space; neither requirement is guaranteed to hold in practice. To dispense with such requirements, we group users when their expected rewards are the same for every available action, even if their preference vectors are different. We propose `TRIBE`, which explores a basis of the space spanned by the available actions, groups users through a novel and computationally efficient statistical test, and selects actions using the observations pooled within each inferred group. Over rounds, our algorithm achieves a regret bound with the leading term , where is the number of clusters, matching the rate attainable when the cluster structure is known a priori. Numerical experiments on synthetic and real-world datasets support our theoretical findings and confirm that `TRIBE` outperforms the baselines.

Primary area:
learning theory
Keywords:
online clustering of bandits, observable partition, block-commit exploration, harmonic-mean separation test

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_dHfvOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies online clustering of linear bandits without requiring stochastic feature diversity or an action set spanning the entire feature space. It groups users into observable clusters according to their expected rewards on available actions. The proposed algorithm, TRIBE, combines basis exploration, a harmonic-mean separation test, and neighborhood-pooled UCB selection. The authors establish cluster-recovery and regret guarantees, analyze computational complexity, and extend the approach to IID time-varying action sets. Synthetic and data-derived experiments evaluate regret and runtime against existing methods.

Critical strengths
  1. Removing restrictive assumptions: The paper removes assumptions in previous works that can be difficult to justify in practice, particularly stochastic feature diversity and access to arms spanning the entire feature space. Additionally, its focus on observable clusters is well motivated: differences between users in unobservable directions cannot affect rewards or decision quality. Grouping users according to observable reward equivalence therefore aligns information sharing with the decision-making objective and permits cooperation even when their full latent parameters differ.

  2. Substantial theoretical analysis: The technical analysis is comprehensive and easy to follow. It establishes preservation of within-cluster edges, exact observable-cluster recovery, and a high-probability regret bound with leading term O(dCT)O(d\sqrt{CT}), matching the OFUL benchmark with known clusters. Furthermore, the shared structure of exploration designs also enables separation tests costing O(B)O(B) per user pair after preprocessing, avoiding pair-specific eigendecompositions. The analysis show improved performance of the proposed algorithm compared to prior methods.

Critical weaknesses
  1. Limited experimental evaluation: All reported experiments enforce W=RdW=\mathbb R^d, so observable and latent clusters coincide. Consequently, the evaluation does not directly investigate a central distinction from previous methods: learning when the available actions leave some parameter directions unobservable. Experiments with rank-deficient arm sets, particularly examples where C<ClatC<C_{\mathrm{lat}}, would help establish the practical benefits of the observable-clustering formulation and the behavior of competing methods in this setting. This is the main limitation affecting my assessment.

  2. Limited motivation: Although full latent parameters may differ, useful pooling still relies on users having exactly identical expected rewards for every available action. In practical recommendation settings, users may have similar preferences while retaining small individual differences. The real-data experiments assign each user a cluster centroid as its ground-truth parameter, thereby enforcing this equality rather than evaluating natural within-cluster variation. A clearer practical justification for exact observable equivalence, together with an assessment of sensitivity to approximate equality, would strengthen the paper’s applicability.

Questions for authors
  1. Could you provide experiments with W⊊RdW\subsetneq\mathbb R^d, including instances where distinct latent parameters have identical projections and C<ClatC<C_{\mathrm{lat}}? How does TRIBE compare with suitable baselines in this setting?

  2. What motivates exact equality of expected rewards within a cluster? How sensitive is the algorithm to small differences between users who would naturally be regarded as belonging to the same group?

  3. Could you develop an expected-regret bound and/or provide an internally chosen confidence schedule that removes δ\delta as a user-specified input?

  4. How should pp be selected in practice, given its tradeoff between exploration regret and cluster-recovery costs?

2 comments

We sincerely thank the reviewer for the careful reading and constructive feedback. We are glad to address your questions below. In particular, the revision adds the requested experiments with C<ClatC<C_{\mathrm{lat}} (Appendix F, page 45), which the reviewer identified as the main limitation.

1. Experiments with W⊊RdW\subsetneq\mathbb R^d and C<ClatC<C_{\mathrm{lat}}

  • Setting. N=20N=20 users in d=9d=9 arrive uniformly at random. User ii has θi=ω1e1±ω2e2±ω3e9\theta_i=\omega_1e_1\pm\omega_2e_2\pm\omega_3e_9 with (ω1,ω2,ω3)=(0.6,0.77,0.2)(\omega_1,\omega_2,\omega_3)=(0.6,0.77,0.2), and each of the four sign combinations is shared by five users, so Clat=4C_{\mathrm{lat}}=4. The fixed arm set consists of e1e_1, which pays 0.60.6 to every user, and 25 unit-norm arms x=(0,ζ,1−ζ2 z⊤,0)⊤x=(0,\zeta,\sqrt{1-\zeta^2}\,z^\top,0)^\top with random z∈R6z\in\mathbb R^6, each paying ±ω2ζ\pm\omega_2\zeta depending on the sign along e2e_2. All arms have a zero ninth coordinate and span W=span(e1,…,e8)⊊R9W=\mathrm{span}(e_1,\ldots,e_8)\subsetneq\mathbb R^9, so the sign along e9e_9 affects no reward, and the users form only C=2C=2 observable clusters of ten users each. Parameter-defined clusters are therefore unidentifiable, whereas recovering the two observable clusters suffices to play the optimal arm of every user.
AlgorithmRegret (mean ± SE)PrecisionRecall
TRIBE8,030 ± 1071.0001.000
CLUB (Gentile et al., 2014)20,136 ± 1,1711.0000.100
SCLUB (Li et al., 2019)16,529 ± 1,0571.0000.100
PhaseUniCLUB (Li et al., 2025)41,684 ± 2,9401.0000.980
BASS (Cherkaoui et al., 2025)25,584 ± 5,2650.9891.000
Context-lumpable (Lee et al., 2023)197,153 ± 11,4791.0000.104
  • TRIBE attains the lowest cumulative regret and recovers the two observable clusters exactly, whereas no baseline achieves exact recovery on all seeds. CLUB, SCLUB, and Context-lumpable keep the two clusters apart but split each cluster into small groups, while PhaseUniCLUB and BASS pool users across clusters for many rounds before separating them.
  • With IID time-varying arm sets on the same users, TRIBE again attains the lowest regret with exact recovery on all seeds. Note that Lee et al. (2023) is excluded from the comparison, because the reward-table model is defined over a fixed finite action set and does not directly apply to time-varying arm sets. The results for time-varying arm sets are given in the table below.
AlgorithmRegret (mean ± SE)PrecisionRecall
TRIBE8,346 ± 2941.0001.000
CLUB (Gentile et al., 2014)18,801 ± 1,0831.0000.100
SCLUB (Li et al., 2019)16,706 ± 5741.0000.147
PhaseUniCLUB (Li et al., 2025)50,499 ± 2,6311.0000.986
BASS (Cherkaoui et al., 2025)14,889 ± 1,1040.9981.000

2. Motivation and sensitivity to approximate equality

  • Sharing without persistent bias. Observable equivalence requires identical expected rewards only on the available arms, so preferences may differ arbitrarily outside WW. TRIBE learns the resulting partition without stochastic feature diversity, an arm set spanning Rd\mathbb R^d, or knowledge of CC or the cluster separation, and Definition 1 applies to any user population, from C=1C=1 to C=NC=N.
  • A fixed tolerance can incur suboptimal decisions. Even arbitrarily small preference differences can change the optimal arm. Consider two arms x1=e1x_1=e_1, x2=e2x_2=e_2 and two equally frequent users with θA=(0.5+η,0.5)\theta_A=(0.5+\eta,0.5) and θB=(0.5,0.5+η)\theta_B=(0.5,0.5+\eta) for small η>0\eta>0, so user AA prefers x1x_1 and user BB prefers x2x_2. A rule that groups users whose parameters differ by at most a fixed tolerance γ\gamma merges the two users whenever ∥θA−θB∥=2η<γ\|\theta_A-\theta_B\|=\sqrt2\eta<\gamma; here ΣB=I2/2\Sigma_{\mathcal B}=I_2/2, so the ℓ2\ell_2 and ΣB\Sigma_{\mathcal B} distances are proportional. If both users then receive the same action distribution, the expected regret is η/2\eta/2 per round, i.e., ηT/2\eta T/2 in total.
  • Temporary pooling in TRIBE. LOCB (Ban & He, 2021) allows approximate clustering with a prescribed tolerance γ\gamma, and its regret bound contains an additive O(γT)O(\gamma T) term. TRIBE also pools users with different observable parameters, but only temporarily: by Theorem 1(i), every edge surviving the update in phase ss connects users whose observable parameters differ by at most ρs/Nπmin⁡\rho_s/\sqrt{N\pi_{\min}} in ∣⋅∣ΣB\\|\cdot\\|_{\Sigma_{\mathcal B}}, and ρs=2−s/2\rho_s=2^{-s/2} shrinks from phase to phase. The cost of temporary pooling is therefore absorbed into the gap-dependent identification term of Theorem 2 rather than appearing as an additive term linear in TT.

(continued in the next comment)


References

  • Lee et al. (2023), Context-lumpable stochastic bandits, NeurIPS.
  • Ban & He (2021), Local clustering in contextual multi-armed bandits, WWW.

(continued from the previous comment)

  • Empirical sensitivity (Appendix F.4). On the same fixed-arm instance, we perturb every parameter as θiε=θi+εui\theta_i^\varepsilon=\theta_i+\varepsilon u_i, where ui∈Wu_i\in W is a random unit vector orthogonal to ΠWθi\Pi_W\theta_i. Users of the same original group then differ by at most 2ε2\varepsilon in observable parameter. Regret is measured against each user's own optimal arm under θiε\theta_i^\varepsilon, and precision and recall against the two original groups.
ε\varepsilonAlgorithmRegret (mean ± SE)PrecisionRecall
0.05TRIBE8,122 ± 1231.0001.000
CLUB (Gentile et al., 2014)16,546 ± 9701.0000.100
SCLUB (Li et al., 2019)14,931 ± 8901.0000.100
PhaseUniCLUB (Li et al., 2025)44,920 ± 2,5771.0000.973
BASS (Cherkaoui et al., 2025)20,105 ± 4,9780.9970.999
Context-lumpable (Lee et al., 2023)208,216 ± 11,5421.0000.108
0.075TRIBE8,626 ± 2561.0001.000
CLUB16,681 ± 6731.0000.100
SCLUB13,917 ± 1,1001.0000.100
PhaseUniCLUB49,094 ± 2,8171.0000.968
BASS19,391 ± 4,4340.9900.994
Context-lumpable207,164 ± 22,8331.0000.106
  • TRIBE attains the lowest regret at both levels, suggesting robustness to within-cluster variation.

3. Expected regret with an internally chosen δ\delta

  • Since 0≤rt≤20\le r_t\le2 (Lemma 9), Reg(T)≤2T\mathrm{Reg}(T)\le2T.
  • Let RT(δ):=2β2dCTlog⁡(1+T/(λd))+8C0pT1−p+8C0(4/(Nπmin⁡ΔB2))1/(1−p)R_T(\delta):=2\beta\sqrt{2dCT\log(1+T/(\lambda d))}+8C_0^pT^{1-p}+8C_0(4/(N\pi_{\min}\Delta_{\mathcal B}^2))^{1/(1-p)} be the right-hand side of Eq. (14).
  • The proof of Theorem 2 gives Reg(T)≤RT(δ)\mathrm{Reg}(T)\le R_T(\delta) on an event of probability at least 1−(JT+2)δ1-(J_T+2)\delta, with JT=1+⌈log⁡2(T+1)⌉J_T=1+\lceil\log_2(T+1)\rceil, hence E[Reg(T)]≤RT(δ)+2(JT+2)Tδ\mathbb E[\mathrm{Reg}(T)]\le R_T(\delta)+2(J_T+2)T\delta.
  • Since TRIBE already uses TT to set β\beta and C0C_0, the internal choice δT:=1/((JT+2)T)\delta_T:=1/((J_T+2)T) removes δ\delta as an input and gives E[Reg(T)]≤RT(δT)+2\mathbb E[\mathrm{Reg}(T)]\le R_T(\delta_T)+2.
  • As log⁡(N/δT)=O(log⁡(NT))\log(N/\delta_T)=O(\log(NT)), the orders β=O~(d)\beta=\widetilde O(\sqrt d) and C0=O~(Nd)C_0=\widetilde O(Nd) are unchanged, so E[Reg(T)]\mathbb E[\mathrm{Reg}(T)] satisfies the bound of Theorem 2.
  • The same argument applies to Theorem 3 with δT:=1/T\delta_T:=1/T.

4. Choice of pp

  • Effect on the bound. pp affects neither the recovery guarantee of Theorem 1 nor the leading term O~(dCT)\widetilde O(d\sqrt{CT}). Since 1−p<1/21-p<1/2, the term (Nd)pT1−p(Nd)^pT^{1-p} grows strictly slower than T\sqrt T and the identification term only logarithmically, so dCTd\sqrt{CT} dominates for every p∈(1/2,1)p\in(1/2,1). As the reviewer notes, pp trades off exploration cost against the cost of pooling before recovery; e.g., p=2/3p=2/3 gives a T1/3T^{1/3} exploration overhead, as in the guarantee of PhaseUniCLUB (Li et al., 2025).
  • Practical selection. Through Ls=⌈C02s/(1−p)⌉L_s=\lceil C_02^{s/(1-p)}\rceil, pp sets how long adaptive selection runs between graph updates and hence the total forced exploration. Since the balance depends on the unknown gap and the horizon, pp can be selected on validation runs at the intended horizon and then fixed, as exploration-related hyperparameters often are in bandit algorithms (Auer et al., 2002; Li et al., 2010; Zhou et al., 2020).
  • Experiments (Appendix F.5). We conduct an experiment for each p∈{0.7,0.75,0.8,0.9}p\in\{0.7,0.75,0.8,0.9\}. The tables below report the fixed and IID time-varying arm sets, respectively.
AlgorithmRegret (mean ± SE)PrecisionRecall
TRIBE (p=0.7p=0.7)9,623 ± 3121.0001.000
TRIBE (p=0.75p=0.75)9,129 ± 3681.0001.000
TRIBE (p=0.8p=0.8)8,030 ± 1071.0001.000
TRIBE (p=0.9p=0.9)4,050 ± 811.0001.000
CLUB20,136 ± 1,1711.0000.100
SCLUB16,529 ± 1,0571.0000.100
PhaseUniCLUB41,684 ± 2,9401.0000.980
BASS25,584 ± 5,2650.9891.000
Context-lumpable197,153 ± 11,4791.0000.104
AlgorithmRegret (mean ± SE)PrecisionRecall
TRIBE (p=0.7p=0.7)11,636 ± 8641.0001.000
TRIBE (p=0.75p=0.75)10,074 ± 3161.0001.000
TRIBE (p=0.8p=0.8)8,346 ± 2941.0001.000
TRIBE (p=0.9p=0.9)6,086 ± 1251.0001.000
CLUB18,801 ± 1,0831.0000.100
SCLUB16,706 ± 5741.0000.147
PhaseUniCLUB50,499 ± 2,6311.0000.986
BASS14,889 ± 1,1040.9981.000

Every configuration recovers the partition exactly and attains lower empirical regret than every baseline.


References

  • Auer et al. (2002), Finite-time analysis of the multiarmed bandit problem, Machine Learning.
  • Li et al. (2010), A contextual-bandit approach to personalized news article recommendation, WWW.
  • Zhou et al. (2020), Neural contextual bandits with UCB-based exploration, ICML.
Reviewer_Rv2POpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online clustering of linear bandits without requiring stochastic feature diversity or an action set spanning the ambient feature space. The proposed algorithm, TRIBE, combines forced exploration over a spanning basis, block-committed exploration statistics, a harmonic-mean separation test, and neighborhood-pooled UCB selection. The analysis establishes observable-cluster recovery and a regret bound whose leading term matches the OFUL benchmark with known cluster memberships.

Critical strengths

The paper addresses a meaningful limitation of parameter-based clustering: differences in directions orthogonal to the available action span are neither identifiable nor relevant to decision-making. Observable clustering provides an appropriate target in this setting.

The algorithmic components fit together well. Complete exploration blocks give users’ design matrices a common eigenbasis, enabling an efficient separation test despite unequal sample counts. Combining this construction with phased graph updates and pooled action selection is a substantive contribution.

Critical weaknesses
  1. I found the algorithm description somewhat hard to follow on the first reading. The purposes of the two sets of statistics, the complete-block commitment rule, and the phase schedule become clear only after consulting several parts of the paper. A short overview before the pseudocode would help. Besides, the subscript (e) in Alg 3 is also confusing, I guess it should be exploration but there is no explicit definition.
  2. The relationship to reward-table clustering and subspace reduction should be made more explicit. For a fixed action-feature matrix XX, each user has a mean-reward vector μi=Xθi\mu_i=X\theta_i, and observable clustering is exactly clustering users with identical mean-reward vectors. This connects directly to context-lumpable stochastic bandits. A concise explanation in the main text would help clarify what the known linear feature structure contributes beyond reward-table clustering. Likewise, because the complete fixed action set is known, its span WW can be computed before interaction. Expressing actions and parameters in an orthonormal basis of WW converts observable clustering into ordinary parameter clustering in B=dim⁡(W)B=\dim(W) dimensions. The paper should therefore distinguish the standard subspace reduction from its contributions to exploration, testing, and regret analysis. In addition, a brief comparison with hidden low-rank linear bandits would also clarify the boundary.
  3. The recovery guarantee depends on ΔB\Delta_{\mathcal B}, which varies with the selected basis. Although an arbitrary basis suffices for identifiability, different bases may have very different statistical efficiency. How sensitive is recovery to this choice, and could a better exploration design improve performance?
Questions for authors
  1. Could the authors more explicitly discuss the relationship to low-rank linear bandits, such as [1], and to [2]? In particular, what additional benefits arise from combining known linear action features with unknown user clusters? Where the assumptions are compatible, could the experiments include representative methods or suitable adaptations from these settings?
  2. Could the authors discuss the algorithm's applicability with time-varying arm sets? Which recovery guarantees and computational advantages survive in these settings? An experiment with time-varying candidate sets would help illustrate the extension’s practical behavior.

[1] Lale, Sahin, et al. "Stochastic linear bandits with hidden low rank structure." arXiv preprint arXiv:1901.09490 (2019).

[2] Lee, Chung-Wei, et al. "Context-lumpable stochastic bandits." Advances in Neural Information Processing Systems 36 (2023): 77915-77941.

3 comments

We sincerely thank the reviewer for the positive assessment of our work and the constructive feedback. We are glad to address your questions below.

1. Description of Algorithm 1

  • Subscript ee. The subscript ee denotes "exploration." The revision defines the subscript explicitly (Line 241) and adds a short overview of the algorithm before the pseudocode (Line 245).
  • Two sets of statistics. Exploration statistics store only forced-exploration observations and exclusively drive the separation test, since UCB-selected arms vary across users and would otherwise make the design matrices user-specific. Main statistics store every observation and are pooled for UCB selection.
  • Complete-block commitment. Committing only complete blocks of all basis arms gives every exploration design matrix the common form Vi,e,t=λId+ni,e,tΣBV_{i,e,t}=\lambda I_d+n_{i,e,t}\Sigma_{\mathcal B} (Lemma 1), so the harmonic-mean test runs coordinate-wise in one shared eigenbasis.
  • Phase schedule. The phases follow a doubling schedule without restarts: forced-exploration subphases double in length, the graph is updated once per phase, and the shrinking fraction of exploration rounds yields the O~((Nd)pT1−p)\widetilde{O}((Nd)^pT^{1-p}) term in Theorem 2.

2. Relation to reward-table clustering, low-rank bandits, and subspace reduction

We have moved the comparison with [2], previously in Appendix A, to Section 2 (Lines 102–128).

Reward-table clustering [2]. The reward-table model is a special case of our setting: one-hot features xk=ek∈RKx_k=e_k\in\mathbb R^K give X=IKX=I_K and d=B=Kd=B=K, so that, after rescaling the rewards, μi=Xθi=θi\mu_i=X\theta_i=\theta_i can encode any row of the reward table, and TRIBE runs on such instances without modification.

  • Whenever B<KB<K, μi\mu_i lies in the BB-dimensional column space of XX, so the mean rewards of all KK arms follow from the mean rewards of the BB basis arms, and only BB coordinates per cluster need to be estimated, whereas [2] treats all KK mean rewards per group as free parameters.
  • Moreover, the online algorithm of [2] requires the number of groups as input and attains O~(C3(N+K)T)\widetilde{O}(\sqrt{C^3(N+K)T}) in our notation, whereas TRIBE requires no knowledge of CC, and its leading term, O~(BCT)\widetilde{O}(B\sqrt{CT}) when the UCB coefficient is computed from BB (Section 5.1), depends on the arms only through B≤KB\le K and does not grow with NN up to logarithmic factors.
  • Our framework also extends to time-varying arm sets with possibly infinite support (Appendix D), where the reward-table model does not directly apply.

We added [2], given the true number of clusters, as a baseline in experiments (Appendix F.2, page 47). The instance has N=20N=20 users in d=9d=9 and a fixed arm set of 26 arms spanning an 8-dimensional subspace, with C=2C=2 observable clusters and Clat=4C_{\mathrm{lat}}=4 latent parameters.

AlgorithmRegret (mean ± SE)PrecisionRecall
TRIBE8,030 ± 1071.0001.000
CLUB (Gentile et al., 2014)20,136 ± 1,1711.0000.100
SCLUB (Li et al., 2019)16,529 ± 1,0571.0000.100
PhaseUniCLUB (Li et al., 2025)41,684 ± 2,9401.0000.980
BASS (Cherkaoui et al., 2025)25,584 ± 5,2650.9891.000
Context-lumpable (Lee et al., 2023)197,153 ± 11,4791.0000.104

TRIBE attains the lowest cumulative regret with perfect precision and recall. Context-lumpable keeps perfect precision but reaches a recall of only 0.104, indicating incomplete pooling within the observable clusters, and incurs substantially higher regret.

Low-rank linear bandits [1]. [1] assumes that both the action vectors and the parameter lie in a hidden mm-dimensional subspace, takes mm as input, and estimates the subspace by PCA on perturbed actions.

  • We impose no such condition: rewards depend on θi∈Rd\theta_i\in\mathbb R^d only through ΠWθi\Pi_W\theta_i (Eq. (3)), and the component orthogonal to WW affects no reward, yet makes parameter-defined clusters unidentifiable. Observable clusters are defined so that the orthogonal component plays no role, and no subspace is estimated statistically, because arm features are observed exactly; even with time-varying arm sets, the observed span lies inside the population feature span WPW_{\mathcal P} (Lemma 12).
  • TRIBE also takes no subspace dimension as input: BB is computed from the known arm set, and the time-varying extension needs to know neither dim⁡(WP)\dim(W_{\mathcal P}) nor whether WP⊊RdW_{\mathcal P}\subsetneq\mathbb R^d. In addition, [1] learns a single parameter without sharing information across users.

(continued in the next comment)

(continued from the previous comment)

Subspace reduction. A standard subspace reduction neither resolves the challenges we address nor yields our guarantees.

  • Exploration. The reduced arm set is still fixed, so optimistic selection need not grow each user's design matrix in every direction of WW. Our block exploration gives every exploration design matrix a common structure covering WW (Lemma 1) without stochastic feature diversity.
  • Separation test. The harmonic-mean test (Algorithm 2) certifies disjoint confidence ellipsoids (Lemma 2) and, with high probability, never splits an observable cluster (Corollary 1). After the reduction alone, each pairwise test still requires solving a B×BB\times B linear system, i.e., O(B3)O(B^3) operations; the eigenbasis shared through Lemma 1 reduces the cost to O(B)O(B), and the phase schedule limits graph updates to O(log⁡T)O(\log T).
  • Regret analysis. Theorems 1 and 2 establish recovery and regret guarantees without prior knowledge of the number of clusters, the cluster gap, or the arrival probabilities. Theorem 2 states the leading term in dd for comparison with prior work. Since every arm lies in WW, the revision further shows that computing only the UCB coefficient with BB in place of dd sharpens the leading term to O~(BCT)\widetilde{O}(B\sqrt{CT}), without any change of coordinates (Section 5.1 (page 8) and Remark 1 in Appendix C.5 (page 29)).

3. Sensitivity to the choice of basis

Our guarantees hold for any spanning basis B⊆A\mathcal B\subseteq\mathcal A, and the basis enters only through ΔB\Delta_{\mathcal B}. We further show that ΔB\Delta_{\mathcal B} can be bounded by a basis-free gap ΔA:=min⁡c≠c′max⁡x∈A∣x⊤(ϑc⋆−ϑc′⋆)∣\Delta_{\mathcal A}:=\min_{c\neq c'}\max_{x\in\mathcal A}|x^\top(\vartheta^\star_c-\vartheta^\star_{c'})|.

  • Upper bound. Since ΔB\Delta_{\mathcal B} is a root-mean-square over B⊆A\mathcal B\subseteq\mathcal A, every spanning basis satisfies ΔB≤ΔA\Delta_{\mathcal B}\le\Delta_{\mathcal A}.
  • Lower bound. Suppose TRIBE uses a κ\kappa-approximate barycentric spanner as B\mathcal B, i.e., every x∈Ax\in\mathcal A equals ∑b∈Bαbb\sum_{b\in\mathcal B}\alpha_b b with ∣αb∣≤κ|\alpha_b|\le\kappa; such a spanner is computable efficiently for any κ>1\kappa>1 (Awerbuch & Kleinberg, 2004). For v:=ϑc⋆−ϑc′⋆v:=\vartheta^\star_c-\vartheta^\star_{c'}, the Cauchy–Schwarz inequality gives ∣x⊤v∣≤κ∑b∣b⊤v∣≤κB∣v∣ΣB|x^\top v|\le\kappa\sum_{b}|b^\top v|\le\kappa B\\|v\\|_{\Sigma_{\mathcal B}}, hence ΔA/(κB)≤ΔB≤ΔA\Delta_{\mathcal A}/(\kappa B)\le\Delta_{\mathcal B}\le\Delta_{\mathcal A}. A spanner chosen from A\mathcal A alone is therefore within a factor κB\kappa B of the best basis.
  • Other designs. Any fixed spanning cycle of arms, e.g., one following a G-optimal design, also preserves the common structure of Lemma 1, with ΣB\Sigma_{\mathcal B} replaced by the average outer product of the cycle, and hence the coordinate-wise test.

4. Time-varying arm sets

Appendix D (page 29) extends the setting to arm sets drawn IID from an unknown distribution P\mathcal P. The extension (Algorithm 4) expands a basis of the observed feature span online and replaces block exploration with uniform exploration, retaining the phase schedule and the harmonic-mean test.

  • Recovery. With high probability, no within-cluster edge is deleted, and from a finite phase onward the neighborhoods coincide with the population observable clusters defined through WPW_{\mathcal P}. Theorem 3 gives a regret bound of the same three-term form.
  • Computation. Graph updates still occur only at the O(log⁡T)O(\log T) phase transitions with the closed-form test, but without the shared eigenbasis, each pairwise test costs O(d^t3)O(\hat d_t^3) instead of O(B)O(B), where d^t≤dim⁡(WP)\hat d_t\le\dim(W_{\mathcal P}) is the dimension of the observed span.

We also evaluate TRIBE with the same users and IID time-varying arm sets (Appendix F.2): in every round, K=100K=100 arms are drawn with replacement from a 32-arm catalogue. We exclude [2] from the comparison, because the reward-table model is defined over a fixed finite action set and does not directly apply to time-varying arm sets.

AlgorithmRegret (mean ± SE)PrecisionRecall
TRIBE8,346 ± 2941.0001.000
CLUB (Gentile et al., 2014)18,801 ± 1,0831.0000.100
SCLUB (Li et al., 2019)16,706 ± 5741.0000.147
PhaseUniCLUB (Li et al., 2025)50,499 ± 2,6311.0000.986
BASS (Cherkaoui et al., 2025)14,889 ± 1,1040.9981.000

TRIBE again attains the lowest cumulative regret with perfect precision and recall, supporting the practical effectiveness of the extension in recovering and exploiting the population observable clusters.


References

  • Awerbuch & Kleinberg (2004), Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. STOC.

Thank you for the response. I will keep my current score.

Reviewer_mLQnOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies online clustering of linear bandits without assuming stochastic feature diversity. The paper introduces observable clusters, which group users whose expected rewards agree on all available actions. It then proposes TRIBE, combining round-robin basis exploration, a harmonic-mean separation test, and neighborhood-pooled UCB. The paper proves a cumulative regret of O~(dCT)\tilde{O}(d\sqrt{CT}), where CC is the number of observable clusters.

Critical strengths
  1. The studied problem is well-motivated and the theoretical result is solid. The regret indeed achieve the SOTA order.
  2. The paper proposed a computationally efficient design that only requires O(B)O(B) pairwise separation tests.
Critical weaknesses
  1. The experiments do not cover the setting where CC can be potentially smaller than ClatC_{lat}, which can strengthen the proposed algorithm.
  2. The experiments do not evaluate cluster recovery, even though this is one of the paper's main theoretical contributions.
Questions for authors

Given that TRIBE already performs balanced exploration over a common basis, what is the theoretical or empirical advantage of the harmonic-mean separation test over a simpler test based on empirical reward differences across basis arms?

3 comments

We thank the reviewer for positive assessment of our work and for your thoughtful questions. We are pleased to have the opportunity to address your concerns.

1. Theoretical and empirical advantages of the harmonic-mean test

Our harmonic-mean test offers two theoretical advantages over a reward-based test: (i) improved sufficient sample complexity for cluster separation when reward gaps are distributed across multiple basis arms, and (ii) applicability without repeated observations of the same arms. Our ablation further demonstrates lower regret and earlier cluster recovery.

Alternative reward-based test

Let qi(ts)=ni,e,ts/Bq_i(t_s)=n_{i,\mathsf e,t_s}/B denote the number of committed pulls of each basis arm by user ii, and let μ^i,a,ts\widehat\mu_{i,a,t_s} be the corresponding one-dimensional ridge estimate for arm a∈{b1,…,bB}a\in\{b_1,\ldots,b_B\}. Then, we can consider the following reward-based test, which deletes edge between user ii and jj when (μ^i,a,ts−μ^j,a,ts)2(λ+qi(ts))−1+(λ+qj(ts))−1>(βi,e,ts(1))2+(βj,e,ts(1))2,\frac{(\widehat\mu_{i,a,t_s}-\widehat\mu_{j,a,t_s})^2}{(\lambda+q_i(t_s))^{-1}+(\lambda+q_j(t_s))^{-1}} > (\beta^{(1)}_{i,\mathsf e,t_s})^2+(\beta^{(1)}_{j,\mathsf e,t_s})^2, where βi,e,ts(1):=2log⁡(BN/δ)+log⁡(1+qi(ts)/λ)+λ\beta^{(1)}_{i,\mathsf e,t_s}:=\sqrt{2\log(BN/\delta)+\log(1+q_i(t_s)/\lambda)}+\sqrt{\lambda}. Thus, separation relies on the largest reward gap on a single basis arm.

Theoretical advantages

  1. Sample effciency. For a cross-cluster pair (i,j)(i,j), define the expected-reward gap ga:=xa⊤(ϑm(i)⋆−ϑm(j)⋆)g_a:=x_a^\top(\vartheta^\star_{m(i)}-\vartheta^\star_{m(j)}) and nmin⁡:=min⁡{ni,e,ts,nj,e,ts}n_{\min}:=\min\{n_{i,\mathsf e,t_s},n_{j,\mathsf e,t_s}\}. Lemma 7 (Line 1082) guarantees separation by the harmonic-mean test under the sufficient condition nmin⁡>(2+22)2Bβ2∑aga2n_{\min}>\frac{(2+2\sqrt 2)^2B\beta^2}{\sum_a g_a^2}. Applying the argument of Lemma 7 to the one-dimensional ridge estimates yields the following sufficient condition for the reward-based test: nmin⁡>(2+22)2B(β(1))2max⁡aga2n_{\min}>\frac{(2+2\sqrt 2)^2B(\beta^{(1)})^2}{\max_a g_a^2}, on the corresponding arm-wise confidence event, where β(1)\beta^{(1)} is a common upper bound on the one-dimensional confidence radii.

    • Comparing this with the harmonic-mean bound, the ratio of the two sufficient sample thresholds is ∑aga2max⁡aga2(β(1))2β2\frac{\sum_a g_a^2}{\max_a g_a^2}\frac{(\beta^{(1)})^2}{\beta^2}, where (∑aga2)/(max⁡aga2)∈[1,B](\sum_a g_a^2)/(\max_a g_a^2) \in [1, B]. Thus, the harmonic-mean test can achieve a smaller sufficient sample threshold by aggregating squared reward gaps across basis arms, whereas the reward-based test relies on the largest individual gap.
  2. Extension to time-varying arm sets. Our harmonic-mean test uses parameter estimates and their design matrices Vi,e,tsV_{i,\mathsf e,t_s} without requiring repeated observations of individual arms. Appendix D retains this test under IID time-varying arm sets, while replacing fixed-basis exploration with uniform exploration and adapting the recovery analysis to random design matrices. In contrast, the reward-based test above relies on repeated observations of fixed basis arms and therefore does not directly extend to this setting.

Empirical validation

We performed an ablation replacing only the separation test, while keeping the remaining algorithmic components unchanged. We compare the harmonic-mean test with the reward-based test defined above and an isotropic test based on the ℓ2\ell_2 distance, as commonly used in prior clustering-of-bandits methods such as CLUB (Gentile et al., 2014) and PhaseUniCLUB (Li et al., 2025). We have added this experiment in Appendix F.3 (pages 47–48, Figure 5) of the revised manuscript.

Separation testRegret (mean ± SE)PrecisionRecall
Harmonic-mean8,760 ± 6111.0001.000
Reward-based14,221 ± 581.0001.000
Isotropic137,016 ± 30.5001.000

As shown in the table, the harmonic-mean test achieves the lowest mean cumulative regret and exact cluster recovery; the reward-based test also achieves exact recovery, but requires later graph updates, ended up with higher cumulative regret. In contrast, the isotropic test fails to recover the correct clustering on any seed and incurs substantially higher regret.

2. Additional experiments on observable cluster recovery

We have added experiments in Appendix F (page 45) to evaluate TRIBE in settings where the number of observable clusters is smaller than the number of distinct latent parameters, i.e., C<ClatC<C_{\mathrm{lat}}. We also report precision and recall to directly evaluate observable cluster recovery, addressing your second concern.

Setting. We consider N=20N=20 users in dimension d=9d=9, and the arriving user is drawn uniformly from [N][N] in every round. Each standard basis vector plays a single role: e1e_1 is a direction that every user values equally, e2e_2 separates the observable clusters, e3,…,e8e_3,\ldots,e_8 only diversify the arm directions, and e9e_9 separates latent parameters that no arm can observe.

  • Latent parameters. User ii has θi=ω1e1±ω2e2±ω3e9\theta_i=\omega_1e_1\pm\omega_2e_2\pm\omega_3e_9 with (ω1,ω2,ω3)=(0.6,0.77,0.2)(\omega_1,\omega_2,\omega_3)=(0.6,0.77,0.2), so that ∥θi∥≤1\Vert{} \theta_i\Vert{} \le 1. Each of the four sign combinations is shared by five users, yielding Clat=4C_{\mathrm{lat}}=4.
  • Arm set. The arm set consists of 26 unit-norm arms: the arm e1e_1, which pays ω1=0.6\omega_1=0.6 to every user, and 25 arms of the form x=(0,ζ,1−ζ2,z⊤,0)⊤x=(0,\zeta,\sqrt{1-\zeta^2}\\,z^\top,0)^\top, where ζ∈(−1,1)\zeta\in(-1,1) and zz is drawn uniformly from the unit sphere in R6\mathbb R^6. Arm xx pays ω2ζ\omega_2\zeta to users with +ω2e2+\omega_2e_2 and −ω2ζ-\omega_2\zeta to users with −ω2e2-\omega_2e_2, so each such arm serves one group and pays a negative reward to the other. Each group has one optimal arm with ∣ζ∣=0.95|\zeta|=0.95, which pays 0.7315>0.60.7315>0.6 to the group served and −0.7315-0.7315 to the other group.
  • Observable clusters. All arms have a zero ninth coordinate and span W=span(e1,…,e8)⊊R9W=\mathrm{span}(e_1,\ldots,e_8)\subsetneq\mathbb R^9. Since x⊤θi=x⊤ΠWθix^\top\theta_i=x^\top\Pi_W\theta_i for every arm xx, the sign along e9e_9 does not affect any expected reward, and the four latent groups cannot be distinguished through any arm. The projection ΠWθi=ω1e1±ω2e2\Pi_W\theta_i=\omega_1e_1\pm\omega_2e_2 takes only two values, so the users form C=2C=2 observable clusters of ten users each, distinguished by the sign along e2e_2. Users in the same observable cluster share every expected reward and hence the optimal arm, so recovering the two observable clusters suffices for small regret.
AlgorithmRegret (mean ± SE)PrecisionRecall
TRIBE8,030 ± 1071.0001.000
CLUB (Gentile et al., 2014)20,136 ± 1,1711.0000.100
SCLUB (Li et al., 2019)16,529 ± 1,0571.0000.100
PhaseUniCLUB (Li et al., 2025)41,684 ± 2,9401.0000.980
BASS (Cherkaoui et al., 2025)25,584 ± 5,2650.9891.000
Context-lumpable (Lee et al., 2023)197,153 ± 11,4791.0000.104

As shown in the table, TRIBE achieves the lowest cumulative regret among all evaluated algorithms and exactly recovers the two observable clusters on all 10 seeds, whereas none of the baselines achieves exact recovery on all seeds. These results demonstrate that TRIBE recovers and exploits the reward-relevant observable partition even when distinct latent parameters cannot be distinguished through the available arms (Appendix F.2, Figure 4).


References

  • Lee et al. (2023), Context-lumpable stochastic bandits, NeurIPS2023.

Thanks for the responses. I do not have further questions and will keep my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Final summary and Remarks

We thank the reviewers for the careful reading and constructive feedback, and we are encouraged by the positive assessments. The discussion helped us present our work more clearly and articulate the core contribution.

In this work, we proposed a notion of observable clusters, which group users with the same mean rewards across a given arm set, i.e., the same parameter projected onto the subspace WW spanned by the arm set. Our notion requires neither stochastic diversity of features nor an arm set spanning Rd\mathbb{R}^d, the conditions typically assumed in prior studies of online clustering of bandits. Our common-shape exploration matrices enable harmonic-mean tests with O(d)O(d) cost per pairwise comparison. The resulting recovery of the observable clusters yields a O~(dCT)\widetilde{O}(d\sqrt{CT}) leading regret term, matching the rate obtained by running an OFUL-type algorithm within each observable cluster when the cluster structure is known. Our algorithm, TRIBE, also extends to time-varying arm sets generated IID from an unknown distribution.

In response to the reviewers, we clarified the following points:

  1. Empirical performance. We added experiments on cluster recovery when the arm set does not span Rd\mathbb{R}^d and C<ClatC < C_{\mathrm{lat}}, comparison with context-lumpable bandits (Lee et al., 2023), and robustness to within-cluster variation. TRIBE achieved the lowest cumulative regret and recovered the observable clusters more accurately than the baselines, and these results also held under IID time-varying arm sets.
  2. Advantages of the harmonic-mean test. Unlike a reward-based test that relies on the largest reward gap on a single basis arm, the harmonic-mean test aggregates reward gaps across all basis arms and therefore can separate different observable clusters with fewer samples. The test also requires no repeated observations of individual arms and thus extends to time-varying arm sets. An ablation that replaces only the separation test confirms that the harmonic-mean test incurs lower regret than a reward-based test and an isotropic test.
  3. Relation to prior work. The reward-table model of context-lumpable bandits is a special case of our setting with one-hot features (Section 2). Its online algorithm requires the number of groups and attains O~(C3(N+K)T)\widetilde{O}(\sqrt{C^3(N+K)T}), whereas TRIBE requires no knowledge of CC and its leading term O~(BCT)\widetilde{O}(B\sqrt{CT}), with B=dim⁡(W)≤KB = \dim(W) \le K, does not grow with NN (Section 5.1). Unlike low-rank linear bandits, TRIBE takes no subspace dimension as input, and a subspace reduction alone yields neither the common exploration structure, the O(B)O(B) separation test, nor our recovery and regret guarantees.
  4. Robustness to design choices. Our guarantees hold for any spanning basis chosen from the arm set, and the basis enters only through the cluster gap ΔB\Delta_{\mathcal B}. We have further shown that the pre-recovery pooling cost, which depends on ΔB\Delta_{\mathcal B}, is bounded by the gap-dependent term. Finally, pp affects neither the recovery guarantee of Theorem 1 nor the leading term, and Appendix F.5 reports experiments for p∈{0.7,0.75,0.8,0.9}p \in \{0.7, 0.75, 0.8, 0.9\}.
  5. Expected regret. Choosing δT:=1/((JT+2)T)\delta_T := 1/((J_T+2)T) internally, with JT=1+⌈log⁡2(T+1)⌉J_T = 1 + \lceil \log_2(T+1) \rceil, removes δ\delta as an input and gives E[Reg(T)]≤RT(δT)+2\mathbb{E}[\mathrm{Reg}(T)] \le R_T(\delta_T) + 2, where RT(δ)R_T(\delta) is the high-probability bound of Theorem 2; the orders of β\beta and C0C_0 remain unchanged, and the same argument applies to Theorem 3.
  6. Presentation. We defined the subscript ee ("exploration") and added an overview of Algorithm 1 before the pseudocode, explaining the two sets of statistics, complete-block commitment, and the phase schedule.

We hope these clarifications, all reflected in the revised manuscript, address the reviewers' concerns, and we thank the reviewers and the AC again for their time and engagement.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.