- 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
-
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.
-
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 , matching the OFUL benchmark with known clusters. Furthermore, the shared structure of exploration designs also enables separation tests costing per user pair after preprocessing, avoiding pair-specific eigendecompositions. The analysis show improved performance of the proposed algorithm compared to prior methods.
Critical weaknesses
-
Limited experimental evaluation: All reported experiments enforce , 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 , 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.
-
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
-
Could you provide experiments with , including instances where distinct latent parameters have identical projections and ? How does TRIBE compare with suitable baselines in this setting?
-
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?
-
Could you develop an expected-regret bound and/or provide an internally chosen confidence schedule that removes as a user-specified input?
-
How should be selected in practice, given its tradeoff between exploration regret and cluster-recovery costs?
2 comments
(continued from the previous comment)
- Empirical sensitivity (Appendix F.4). On the same fixed-arm instance, we perturb every parameter as , where is a random unit vector orthogonal to . Users of the same original group then differ by at most in observable parameter. Regret is measured against each user's own optimal arm under , and precision and recall against the two original groups.
| Algorithm | Regret (mean ± SE) | Precision | Recall | |
|---|---|---|---|---|
| 0.05 | TRIBE | 8,122 ± 123 | 1.000 | 1.000 |
CLUB (Gentile et al., 2014) | 16,546 ± 970 | 1.000 | 0.100 | |
SCLUB (Li et al., 2019) | 14,931 ± 890 | 1.000 | 0.100 | |
PhaseUniCLUB (Li et al., 2025) | 44,920 ± 2,577 | 1.000 | 0.973 | |
BASS (Cherkaoui et al., 2025) | 20,105 ± 4,978 | 0.997 | 0.999 | |
Context-lumpable (Lee et al., 2023) | 208,216 ± 11,542 | 1.000 | 0.108 | |
| 0.075 | TRIBE | 8,626 ± 256 | 1.000 | 1.000 |
CLUB | 16,681 ± 673 | 1.000 | 0.100 | |
SCLUB | 13,917 ± 1,100 | 1.000 | 0.100 | |
PhaseUniCLUB | 49,094 ± 2,817 | 1.000 | 0.968 | |
BASS | 19,391 ± 4,434 | 0.990 | 0.994 | |
Context-lumpable | 207,164 ± 22,833 | 1.000 | 0.106 |
TRIBEattains the lowest regret at both levels, suggesting robustness to within-cluster variation.
3. Expected regret with an internally chosen
- Since (Lemma 9), .
- Let be the right-hand side of Eq. (14).
- The proof of Theorem 2 gives on an event of probability at least , with , hence .
- Since
TRIBEalready uses to set and , the internal choice removes as an input and gives . - As , the orders and are unchanged, so satisfies the bound of Theorem 2.
- The same argument applies to Theorem 3 with .
4. Choice of
- Effect on the bound. affects neither the recovery guarantee of Theorem 1 nor the leading term . Since , the term grows strictly slower than and the identification term only logarithmically, so dominates for every . As the reviewer notes, trades off exploration cost against the cost of pooling before recovery; e.g., gives a exploration overhead, as in the guarantee of
PhaseUniCLUB(Li et al., 2025). - Practical selection. Through , 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, 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 . The tables below report the fixed and IID time-varying arm sets, respectively.
| Algorithm | Regret (mean ± SE) | Precision | Recall |
|---|---|---|---|
TRIBE () | 9,623 ± 312 | 1.000 | 1.000 |
TRIBE () | 9,129 ± 368 | 1.000 | 1.000 |
TRIBE () | 8,030 ± 107 | 1.000 | 1.000 |
TRIBE () | 4,050 ± 81 | 1.000 | 1.000 |
CLUB | 20,136 ± 1,171 | 1.000 | 0.100 |
SCLUB | 16,529 ± 1,057 | 1.000 | 0.100 |
PhaseUniCLUB | 41,684 ± 2,940 | 1.000 | 0.980 |
BASS | 25,584 ± 5,265 | 0.989 | 1.000 |
Context-lumpable | 197,153 ± 11,479 | 1.000 | 0.104 |
| Algorithm | Regret (mean ± SE) | Precision | Recall |
|---|---|---|---|
TRIBE () | 11,636 ± 864 | 1.000 | 1.000 |
TRIBE () | 10,074 ± 316 | 1.000 | 1.000 |
TRIBE () | 8,346 ± 294 | 1.000 | 1.000 |
TRIBE () | 6,086 ± 125 | 1.000 | 1.000 |
CLUB | 18,801 ± 1,083 | 1.000 | 0.100 |
SCLUB | 16,706 ± 574 | 1.000 | 0.147 |
PhaseUniCLUB | 50,499 ± 2,631 | 1.000 | 0.986 |
BASS | 14,889 ± 1,104 | 0.998 | 1.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.
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<Clat (Appendix F, page 45), which the reviewer identified as the main limitation.
1. Experiments with W⊊Rd and C<Clat
TRIBECLUB(Gentile et al., 2014)SCLUB(Li et al., 2019)PhaseUniCLUB(Li et al., 2025)BASS(Cherkaoui et al., 2025)Context-lumpable(Lee et al., 2023)TRIBEattains the lowest cumulative regret and recovers the two observable clusters exactly, whereas no baseline achieves exact recovery on all seeds.CLUB,SCLUB, andContext-lumpablekeep the two clusters apart but split each cluster into small groups, whilePhaseUniCLUBandBASSpool users across clusters for many rounds before separating them.TRIBEagain 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.TRIBECLUB(Gentile et al., 2014)SCLUB(Li et al., 2019)PhaseUniCLUB(Li et al., 2025)BASS(Cherkaoui et al., 2025)2. Motivation and sensitivity to approximate equality
TRIBElearns the resulting partition without stochastic feature diversity, an arm set spanning Rd, or knowledge of C or the cluster separation, and Definition 1 applies to any user population, from C=1 to C=N.TRIBE.LOCB(Ban & He, 2021) allows approximate clustering with a prescribed tolerance γ, and its regret bound contains an additive O(γT) term.TRIBEalso pools users with different observable parameters, but only temporarily: by Theorem 1(i), every edge surviving the update in phase s connects users whose observable parameters differ by at most ρs/Nπmin in ∣⋅∣ΣB, and ρ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 T.(continued in the next comment)
References