acceptodds
Under review as a conference paper at ICLR 2027

Frequency-Agnostic Online Clustering of Bandits via Local Certification

Abstract

For a linear bandit problem, in each sequential decision round, an agent picks an action vector and receives a stochastic reward whose expectation is the inner product of the action vector and an unknown preference vector. Online clustering of linear bandits improves sample efficiency by grouping agents with common preferences into clusters and pooling their observations. However, prior analyses often tie the benefits of collaboration to the identification of the full cluster structure, so rarely observed agents can delay these benefits even for agents whose preferences are already estimated accurately. To address this limitation, we introduce Local Certification for Clustering of Bandits (LC-CLUB), a frequency-agnostic collaboration framework that enables certified sharing before global cluster identification and requires no knowledge of arrival frequencies. Each agent first learns from its own observations and, once its estimate is accurate enough to be certified, begins sharing with certified agents in the same cluster. Our regret analysis separates each agent's pre-certification interactions from its subsequent cluster-level learning, so a rarely observed agent contributes only its own few interactions to the clustering term. With this new algorithm design and analysis, LC-CLUB eliminates the uniform-arrival assumption imposed in prior analyses, has no inverse dependence on the minimum agent-arrival probability, and requires no within-cluster frequency alignment, substantially broadening its applicability to heterogeneous-arrival settings with highly unequal agent arrival rates. It also removes an explicit factor of the linear-bandit dimension from the coefficient of in the clustering term, leaving a horizon-independent remainder. We further show that, under Gaussian-perturbed adversarial contexts, predictable convex action-selection scores, including LinUCB, accumulate information in every direction at a linear rate with high probability, so local certification needs no separate uniform-exploration phase. Experimentally, LC-CLUB-L reduces cumulative regret by 12.8% on average and up to 38% relative to the strongest baseline.

Primary area:
learning theory
Keywords:
Online clustering of bandits, Linear contextual bandits, Local certification, Heterogeneous agent arrivals, Smoothed adversarial contexts

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_LvyvOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies online clustering of linear bandits under heterogeneous agent arrivals. The authors propose LC-CLUB, which enables sharing once an agent has accumulated enough personal observations, without waiting for global cluster identification. The authors conduct asymptotic analysis removes an explicit dimension factor from the logarithmic coefficient of the clustering term. Experiments cover synthetic context distributions and heterogeneous or time-varying arrivals.

Critical strengths
  1. This paper develops a meaningful treatment of heterogeneous arrivals that addresses the statistical issue in historical pooling.

  2. The Theorem 2 provided in this paper is useful since it connects information acquisition needed for certification to reward-directed action selection.

Critical weaknesses
  1. The practical variant lacks validation under its corresponding theorem.

  2. The baseline calibration limits the interpretation of the empirical advantage.

Questions for authors
  1. Under the Gaussian perturbation model of Assumption 3, could you report certification times, erroneous cross-cluster edges, and regret for LC-CLUB-L, comparing the theoretical threshold with Eq. (12)?

  2. Do the main gains remain when UniCLUB, CLUB, SCLUB, and LC-CLUB receive the same independent validation budget?

  3. How sensitive are certification times and regret to conservative gap and diversity lower bounds?

5 comments
AuthorsOpenReview ↗

Response to Reviewer Lvyv (1/4)

Thank you for the detailed questions; they led us to run the theorem's configuration and to tune every method by one search. Below, we discuss each point in detail.

W1 and Q1. The theoretical threshold against Eq. (12), under Assumption 3. In point 2 of the general response, we analyse in detail how the theoretical constant differs from the empirical formula, Eq. (12), and why we use the latter. The theoretical radius has to hold for every user and every round with high probability and rests on a worst-case lower bound on the information a user collects, so its count is designed for a horizon large enough to make it small against TT. As in most papers in this area, Eq. (12) keeps the form of that radius, the noise and dimension scale, the log⁡n/n\sqrt{\log n/n} decay and the ridge term, and sets a fixed coefficient in place of the confidence level. We ran LC-CLUB-L under Gaussian-perturbed contexts with the count of Theorem 3 (δ=T−2\delta=T^{-2}, ridge λ=LT2\lambda=L_T^2) and with Eq. (12), under uniform and Zipf α=1\alpha=1 arrivals, and report, as you ask, its certification times, erroneous cross-cluster edges and regret. The rows compare the full theoretical and empirical configurations, including their certification thresholds and ridge parameters.

At the main scale, with context centers uniform on the unit sphere in H2⊕A4H_2\oplus A_4, independent N(0,0.1I10)N(0,0.1I_{10}) perturbations and N(0,1)N(0,1) reward noise, the theorem's count is 3.26×1093.26\times10^9 own observations, more than T=108T=10^8, so its configuration certifies no agent under any arrival law. Eq. (12) certifies with no cross-cluster pair; the personal error of a certified agent at certification has 99% quantile 0.046–0.052 and maximum 0.050–0.063 across runs, against the cutoff γ/4=0.186\gamma/4=0.186.

ArrivalsEq. (12): first / last certificationEq. (12): certifiedEq. (12): cross-cluster pairsRegret (×103\times10^3), Eq. (12)Regret (×103\times10^3), theorem's configuration (none certified)
Uniform56.9–57.1M / 58.5–58.8M10000748.9 ± 0.541458
Zipf α=1\alpha=10.88M / 98.8–99.8M314–3160635.0 ± 0.581145
Sine54.2–54.3M / 59.2–59.3M10000749.8 ± 0.541458

To see the theorem's configuration at work, we also ran a small instance with a horizon long enough to reach its count: u=10u=10, two equal clusters θ=±e1\theta=\pm e_1 (γ=2\gamma=2), d=K=5d=K=5, T=2×109T=2\times10^9, five fresh seeds; each x=μ+N(0,I)x=\mu+N(0,I), with μ\mu uniform on the unit sphere in span(e2,…,e5)\mathrm{span}(e_2,\dots,e_5), and reward noise N(0,1)N(0,1).

ArrivalsMethodCertification countCertifiedFirst certificationLast certificationLargest error (γ/4=0.5\gamma/4=0.5)RegretLast-quarter increment
UniformLinUCB–––––25,734649.9
LC-CLUB-L, theorem82.5M10825M825M0.000324,151 ± 37133.3
LC-CLUB-L, Eq. (12)93107421,1340.2761,214 ± 629.1
Zipf α=1\alpha=1LinUCB–––––25,266649.1
LC-CLUB-L, theorem82.5M8283M1,700M0.000424,427 ± 24289.4
LC-CLUB-L, Eq. (12)93103133,1260.2981,212 ± 329.4

The theorem's configuration certifies correctly, and no run certifies a cross-cluster pair; under uniform arrivals, once every agent is certified, its regret over the last quarter is a fifth of LinUCB's (133.3 against 649.9). When the theoretical count is reached, however, the estimation error is already far below what certification needs (largest error 0.0003–0.0004 against γ/4=0.5\gamma/4=0.5), so much of the exploration before it is wasted and the regret before certification is high. This is why we use the empirical formula in practice: it keeps the form of the theoretical radius but removes the slack of its worst-case constant.

AuthorsOpenReview ↗

Response to Reviewer Lvyv (2/4)

W2 and Q2: every method tuned by the same search. CLUB, SCLUB, UniCLUB, LC-CLUB-L and Phase-LC-CLUB-L (general 1.2) are all tuned by the same search on the same validation seeds, with the same budget of 5, 10 or 15 evaluated configurations, and are tested on separate seeds; the selections are then frozen and run at u=1000u=1000. In the constructed space, LC-CLUB-L stays 55–73% below tuned SCLUB at every budget, and on the raw sphere it is level with SCLUB from ten configurations on. LC-CLUB-L with pairwise pools keeps LC-CLUB-L's selections (its own search gives 37.77 / 68.13); it and Phase-LC-CLUB-L are the two lowest in every column.

Protocol. The search is compass search [1]. It starts at the default constants of the released codes (coefficient 1 for CLUB; (1,2)(1,\sqrt2) for SCLUB; (1.75,1.4)(1.75,1.4) for UniCLUB) and at C=0.5C=0.5 for the LC-CLUB variants, evaluates the neighbours obtained by multiplying or dividing one constant by a ratio, and moves to the best one; when no neighbour improves, the ratio shrinks from 2 to 2\sqrt2 to 21/42^{1/4}. The score is mean regret on validation seeds 110–112 (Zipf α=1\alpha=1, u=250u=250, T=25T=25M). The budget is the number of configurations evaluated: we report the best among the first 5, 10 and 15, tested on seeds 210–214. SCLUB and UniCLUB tune two constants within the same budget. LC-CLUB-L also receives the gap and λx\lambda_x as inputs.

Selections. SCLUB: (2,2)(2,\sqrt2), (4,22)(4,2\sqrt2) and (4,42)(4,4\sqrt2) at 5, 10 and 15 configurations, in both spaces. LC-CLUB-L: C=0.0625C=0.0625 on the raw sphere at every budget; 0.0625, 0.0526 and 0.0372 in the constructed space. CLUB stays at LinUCB's level at every budget: it pools users by connected components and never restores a deleted edge, and under Zipf α=1\alpha=1 rarely observed users keep their edges to every cluster and join the clusters into one component, so the search ends where almost all edges are deleted. UniCLUB, tuned the same way, also stays there.

Final regret (×103\times10^3), test seeds5 configs: rawconstr.10 configs: rawconstr.15 configs: rawconstr.
LinUCB84.93369.784.93369.784.93369.7
tuned CLUB83.46369.783.46369.883.46369.8
tuned UniCLUB86.34370.686.34370.185.88370.1
tuned SCLUB81.30297.746.83193.345.82176.0
tuned LC-CLUB-L46.0681.3446.0679.3446.0678.27
tuned LC-CLUB-L + pairwise pools37.7968.5237.7969.3337.7974.29
tuned Phase-LC-CLUB-L39.7473.5838.4370.4538.4370.45

Bold: lowest; italic: second lowest. C=0.0625C=0.0625 certifies two cross-cluster pairs in one raw-sphere run; no other LC-CLUB-L test run does, and Phase-LC-CLUB-L has such pairs only in its first phases. The row + pairwise pools adds the sharing before certification of the reply to Reviewer aGXh (W1.2): 18% lower on the raw sphere and 5–16% lower in the constructed space; before certification, at most 1.7% of its provisional links join two clusters.

Under uniform arrivals, no user is rare, and the same search (10 configurations; u=250u=250, T=25T=25M, test seeds 210–214) brings CLUB and UniCLUB well below LinUCB:

Final regret (×103\times10^3), uniform arrivalsRaw sphereConstructed
LinUCB92.74443.46
tuned CLUB69.56194.87
tuned UniCLUB58.47337.32
tuned SCLUB46.25139.06
tuned LC-CLUB-L49.0886.21
tuned LC-CLUB-L + pairwise pools43.7484.30
tuned Phase-LC-CLUB-L37.2666.65

Under uniform arrivals, the pairwise pools lower LC-CLUB-L's regret by 11% (raw sphere) and 2% (constructed).

Frozen transfer. The 10-configuration selections, moved unchanged to u=1000u=1000 and T=108T=10^8 on seeds 310–314:

Final regret (×103\times10^3), transferRaw sphereConstructed
LinUCB333.01,418
tuned CLUB332.51,418
tuned UniCLUB366.41,423
tuned SCLUB162.4564.1
tuned LC-CLUB-L170.2232.7
tuned LC-CLUB-L + pairwise pools127.2162.3
tuned Phase-LC-CLUB-L139.6198.6

On the raw sphere, at C=0.0625C=0.0625, at most 0.05% of the certified links of a transfer run join two clusters (6–15 of about 28,000); the constructed runs have none. Phase-LC-CLUB-L pools different clusters only in its first phases and ends every run without a cross-cluster pair. With pairwise pools, LC-CLUB-L is the lowest in both spaces (−25% / −30% against LC-CLUB-L); after certification, at most 0.05% of its links join two clusters on the raw sphere and none in the constructed space; before certification, at most 1.7% of its provisional links do on the raw sphere and 0.14% in the constructed space.

References:

  • [1] T. G. Kolda, R. M. Lewis, and V. Torczon. Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods. SIAM Review, 45(3):385–482, 2003.
AuthorsOpenReview ↗

Response to Reviewer Lvyv (3/4)

W2 and Q2, continued. Growth late in the run. Final regret at one horizon rewards sharing early; it does not show which method has learned the clusters. In the transfer runs above, over the last 2×1072\times10^7 of the T=108T=10^8 rounds the regret (×103\times10^3, raw sphere / constructed) grows by 3.35 / 57.9 for tuned SCLUB, by 0.52 / 3.93 for tuned LC-CLUB-L and by 0.21 / 6.71 for Phase-LC-CLUB-L: SCLUB is still growing 6 and 15 times as fast as LC-CLUB-L, and faster in every seed, because its clusters are less accurate: at the end it holds 161–186 groups for 10 true clusters and connects 18–20% and 9–10% of the same-cluster pairs, against 56–59% and 95–96% for LC-CLUB-L and 75–82% for Phase-LC-CLUB-L. As a result, on the raw sphere, where tuned LC-CLUB-L is 4.8% higher at T=108T=10^8, the lead of tuned SCLUB shrinks from 10.6 to 7.8 (×103\times10^3) over this last fifth.

C=0.5C=0.5 and λ^=λx/2\hat\lambda=\lambda_x/2 were set before the reported runs, and the baselines in the submitted tables use the coefficients of their public code (1 for CLUB; 1 and 2\sqrt2 for SCLUB), as in Section 6 of the paper.

Q3. Conservative gap and diversity inputs. Both inputs act through the certification count. For the diversity input, the paper uses λ^=λx/2\hat\lambda=\lambda_x/2 because in practice only a lower bound on λx\lambda_x is known; at every CC the row with the true λx\lambda_x is at or below ours. We ran LC-CLUB-L on the six main-text settings, on the same streams and seeds, over C∈0.25,0.5,1C\in\\{0.25,0.5,1\\} and λ^∈λx/4,λx/2,λx\hat\lambda\in\\{\lambda_x/4,\lambda_x/2,\lambda_x\\}. The table gives the change in mean final regret against LinUCB and, in parentheses, the mean number of certified agents out of 1,000; the paper's constants are in bold:

Change vs. LinUCB (%), certifiedUniform, C=0.25C=0.250.51Zipf α=1\alpha=1, C=0.25C=0.250.51Sine, C=0.25C=0.250.51
Raw sphere, λ^=λx/4\hat\lambda=\lambda_x/4−15.7 (1,000)0 (0)0 (0)−8.0 (530)−1.6 (150)−0.2 (28)−15.6 (1,000)0 (0)0 (0)
Raw sphere, λ^=λx/2\hat\lambda=\lambda_x/2−25.3 (1,000)−6.8 (1,000)0 (0)−15.4 (823)−3.9 (315)−0.6 (70)−25.3 (1,000)−6.7 (1,000)0 (0)
Raw sphere, λ^=λx\hat\lambda=\lambda_x−35.2 (1,000)−16.3 (1,000)0 (0)−25.8 (1,000)−8.4 (546)−1.6 (150)−35.1 (1,000)−16.2 (1,000)0 (0)
Constructed, λ^=λx/4\hat\lambda=\lambda_x/4−50.3 (1,000)−19.3 (1,000)0 (0)−36.1 (802)−14.8 (332)−3.6 (76)−50.3 (1,000)−19.3 (1,000)0 (0)
Constructed, λ^=λx/2\hat\lambda=\lambda_x/2−63.6 (1,000)−38.5 (1,000)0 (0)−52.3 (1,000)−25.7 (572)−7.8 (167)−63.6 (1,000)−38.5 (1,000)0 (0)
Constructed, λ^=λx\hat\lambda=\lambda_x−76.1 (1,000)−53.3 (1,000)−20.6 (1,000)−68.8 (1,000)−39.5 (865)−15.4 (342)−76.1 (1,000)−53.3 (1,000)−20.5 (1,000)

No tested cell certifies a cross-cluster pair in any seed or has higher regret than LinUCB. A conservative diversity input, λ^=λx/4\hat\lambda=\lambda_x/4 instead of λx/2\lambda_x/2, raises mean regret at C=0.5C=0.5 by 2.4–31%. A larger CC or a smaller λ^\hat\lambda raises the count that certification needs; the counts are:

Certification countC=0.25C=0.250.51
Raw sphere, λ^=λx/4\hat\lambda=\lambda_x/428,165123,871554,979
Raw sphere, λ^=λx/2\hat\lambda=\lambda_x/213,05057,859261,363
Raw sphere, λ^=λx\hat\lambda=\lambda_x6,00426,875122,573
Constructed, λ^=λx/4\hat\lambda=\lambda_x/413,77553,822235,340
Constructed, λ^=λx/2\hat\lambda=\lambda_x/26,41925,067110,372
Constructed, λ^=λx\hat\lambda=\lambda_x2,97311,60351,513

Under uniform and Sine arrivals, each agent has about T/u=105T/u=10^5 observations by T=108T=10^8. Every cell whose count exceeds 10510^5 certifies nobody (0 of 1,000), and the run then equals LinUCB exactly: these are the entries 0. Under Zipf α=1\alpha=1 the frequent agents still reach those counts, so the same cells are below LinUCB, with 28–167 agents certified. A longer horizon, or fewer agents at the same horizon, reaches every count: with u=100u=100 agents at T=108T=10^8, each agent has about 10610^6 observations, and all nine cells certify every agent, with no cross-cluster pair and below LinUCB in every seed. Change in mean final regret against LinUCB (%), uniform arrivals (Sine within one percentage point; bold: the paper's constants):

λ^\hat\lambdaRaw: C=0.25C=0.250.51Constructed: C=0.25C=0.250.51
λx/4\lambda_x/4−31.4−18.4−5.1−65.6−56.4−35.8
λx/2\lambda_x/2−38.3−25.2−11.7−69.3−62.5−47.9
λx\lambda_x−45.5−31.9−18.5−73.1−66.4−56.8
Reviewer_FzKLOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The author(s) studies online clustering of linear bandits in multi-agent setting where agents can have heterogeneous arrival frequencies. The main motivation is that existing clustering-based approaches rely on global cluster identification before fully benefiting from collaboration. Consequently, infrequently arriving agents can delay the exploitation of shared information by frequently arriving agents, even when the latter have already accumulated sufficient evidence to identify their clusters. To overcome these limitations, the authors introduce LC-CLUB-U
and LC-CLUB-L two online algorithms. The main idea is local certification, which allows agents to identify similar peers and share information without requiring global synchronization. The paper provides regret guarantees under some assumptions and establishes an information-growth result for Gaussian-perturbed contexts. Experiments shows improvements over existing clustering baselines for synthetic data.

Critical strengths
  1. The paper is well written.

  2. The proposed algorithms works under heterogeneous and potentially skewed agent arrivals is a new contribution. Local certification idea is very interesting a kind of decentralized approach to identifying similar agents.

  3. Provide the regret guarantee for the proposed algorithm and experimentally showcase the improvement for the available baseline.

Critical weaknesses
  1. Assumptions: The dependence of the guarantees on the minimum cluster separation and its practical availability require further discussion.

  2. Theorem 2 depends on finite-valued convex scoring functions under Gaussian-perturbed adversarial contexts. Does this result extend to standard confidence-bound widths without altering the theoretical guarantees?

  3. Can the authors establish a regret guarantee when agents within a cluster have slightly different preference vectors? For instance, how does the resulting pooling bias affect the benefit of collaboration?

Questions for authors

Please see the weaknesses noted above.

4 comments
AuthorsOpenReview ↗

Response to Reviewer FzKL

Thank you for the careful review. Your questions improved the paper: the revision adds a variant without a gap input and a regret bound, with experiments, for slightly different preferences within a cluster. Below, we discuss each point in detail.

W1. The gap and its availability. The guarantees depend on the gap through the certification count: for fixed dd and KK and fixed noise and context parameters, nL=O~(log⁡(uT)/(αKσ−2γ~2))n_L=\tilde O(\log(uT)/(\alpha_K\sigma_-^2\tilde\gamma^2)). Up to logarithms, the pre-certification terms scale as 1/γ~1/\tilde\gamma for LC-CLUB-L and 1/γ~21/\tilde\gamma^2 for LC-CLUB-U; the certified term does not depend on the gap. Availability. A lower bound on the gap is not always available in practice, but some such prior information is essential for a rule that shares for good, and for the case without it we give a variant that does not need it. Point 1 of the general response discusses this in detail. In 1.1 we show that correct grouping needs a stopping condition for exploration, and that a lower bound on the gap is one sufficient condition. For an unknown gap, 1.2 gives a variant, Phase-LC-CLUB-L, that removes the gap input at the price of lower-order terms, with the leading term unchanged, and 1.3 analyses it in experiments. Table 4 of the revised PDF adds the comparison with every method tuned by the same search; there, Phase-LC-CLUB-L has lower regret than every baseline in every column.

W2. Standard confidence-bound widths. Yes, under the same Assumption 3. For V≻0V\succ0 and β≥0\beta\ge0, β∥x∥V−1=β∥V−1/2x∥2\beta\Vert x\Vert_{V^{-1}}=\beta\Vert V^{-1/2}x\Vert_2 is convex, and adding x⊤θ^x^\top\hat\theta preserves convexity. When these quantities are fixed before the current menu, and ties use the smallest index, Theorem 2 applies unchanged. Theorem 3 already uses it in this way, for personal and pooled LinUCB.

W3. Slightly different preferences within a cluster. Yes. Proposition 3 (Appendix A.10) establishes regret bounds for both variants under within-cluster heterogeneity, using the misspecification-analysis technique of RCLUMB [1]. For LC-CLUB-L, with a known ε\varepsilon below γ~/4\tilde\gamma/4, certification uses γ~−4ε\tilde\gamma-4\varepsilon in place of γ~\tilde\gamma and stays correct with high probability, and the regret bound is that of Theorem 3 at this count plus a pooling-bias term 4εLT2Q/ν4\varepsilon L_T^2Q/\sqrt\nu, where QQ is the number of rounds after certification and ν\nu the information rate of Theorem 2; like the misspecification term of RCLUMB, it is linear in QQ. So the bound favours pooling only while ε\varepsilon is small compared with the error an agent would have alone. The experiment below evaluates the original empirical certification rule under within-cluster perturbations; Proposition 3 gives the guarantee for the rule above that certifies with γ~−4ε\tilde\gamma-4\varepsilon in place of γ~\tilde\gamma. We perturbed each user of a cluster on the raw sphere by ε⋅ri⋅vi\varepsilon\cdot r_i\cdot v_i, with viv_i a random unit direction and rir_i uniform on [0,1][0,1] (u=250u=250, T=25T=25M, C=0.5C=0.5, five seeds; Appendix C.9). Final regret (×103\times10^3) and change against LinUCB:

ε\varepsilonUniform: LinUCBLC-CLUB-LZipf α=1\alpha=1: LinUCBLC-CLUB-L
092.7486.68 (−6.5%)84.9381.56 (−4.0%)
0.0193.0086.99 (−6.5%)85.1381.84 (−3.9%)
0.02592.5187.04 (−5.9%)84.9782.28 (−3.2%)
0.0593.1889.63 (−3.8%)84.6784.02 (−0.8%)

The gain shrinks as ε\varepsilon grows but remains: LC-CLUB-L is below LinUCB in every seed, certifies all 250 users under uniform arrivals and 94 under Zipf α=1\alpha=1, and no run certifies a pair across clusters.

We hope these clarifications and additional results address your concerns, and we are happy to answer any further questions.

References:

  • [1] Zhiyong Wang, Jize Xie, Xutong Liu, Shuai Li, and John C. S. Lui. Online Clustering of Bandits with Misspecified User Models. In Advances in Neural Information Processing Systems (NeurIPS), 2023.

Dear Reviewer FzKL,

Thank you again for your review. As today is the final day of the discussion phase, we wanted to kindly follow up on our rebuttal.

Your main concerns were the availability of the gap input and whether the guarantees hold when preferences within a cluster differ slightly. In our response, we explained that prior guarantees (CLUB, SCLUB, UniCLUB) also depend on this gap, and that a phase schedule removes the input at the cost of only lower-order terms (Theorems 6 and 7). For within-cluster differences, we added a regret bound with an explicit bias term (Proposition 3, Appendix A.10); in experiments, the gain shrinks as the differences grow but remains, with regret below LinUCB in every seed (Appendix C.9). Both are standard bandit techniques, and they combine naturally with our analysis: the certification argument is unchanged.

We would greatly appreciate it if you could let us know whether our response resolves your concerns.

Best regards,

Authors

I would like to thank the authors for their detailed rebuttal. My concerns have been addressed, and I am satisfied with the clarifications provided. Therefore, I would like to maintain my original score.

Dear Reviewer FzKL,

Thank you for your response and for confirming that your concerns have been addressed. We sincerely appreciate your time and constructive feedback. We will keep these clarifications in the final version.

Best regards, Authors

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

This paper discuss about how to efficiently share data among users with similar preference but different activity levels in recommendation systems. Previous theoretical analyses require identifying user clusters first, which makes rarely active users potentially a bottleneck. They propose LC-CLUB. In LC-CLUB, each user initially learn from their own feedback. Once their preference estimate is accurate enough and locally certified, the certified users can share data without waiting for everyone else. In synthetic experiments, LC-CLUB-L can reduce cumulative regret by 10%+ compared with baseline. However, the method relies on assumptions, e.g., sufficiently separated preference groups, and its effectiveness in real-world settings remains to be validated.

Critical strengths
  1. The local certification removes the bottleneck of collaboration caused by those rare users. The users who have enough observations can share before full cluster recovery. Its guarantee also avoids inverse dependence on the minimum arrival probability.
  2. The LC-CLUB-L variant simultanuously seeks reward and collect information. It avoids a separate uniform-exploration phase under Gaussian perturbations, which is well supported by theory and experiments.
Critical weaknesses
  1. Certification replies on restrictive prior information, which I think is hard to determine in reality. We must know a lower bound for cluster separation, which is difficult in practice. Besides, rare users also lack enough personal observations before benefiting from collaboration. 2. Experiments are synthetic with an empirical certification radius, which is not practical in real-world data settings.
Questions for authors

Without prior knowledge of cluster separation, can we determine certification from observed data (while not pooling users from different clusters)?

3 comments
AuthorsOpenReview ↗

Response to Reviewer aGXh (1/2)

Thank you for your valuable comments. Your questions on the gap, rare users and the empirical radius improved the paper: the revision adds a variant without a gap input, sharing before certification, and a comparison of the radii. Below, we discuss each point in detail.

W1 (prior information) and Q: certification without a known gap. To your question: from observed data alone, without an assumption such as a lower bound on the gap, no rule can stop after finitely many observations and still share correctly with high probability. Without such an assumption, sharing has to stay revisable, and the phase schedule shows that this costs only lower-order terms in theory and performs well in experiments. Point 1 of the general response discusses your question in detail: (1.1) ruling out a difference ε\varepsilon takes on the order of 1/ε21/\varepsilon^2 observations, so a rule needs a stopping condition, and a lower bound on the gap is one. (1.2) a phase schedule removes the gap input: it guesses the gap and shrinks the guess from phase to phase, so early phases may pool different clusters and later ones are correct; the price is lower-order terms, and the leading term is unchanged. (1.3) In experiments, with every method tuned by the same search, Phase-LC-CLUB-L, which needs no gap, has lower regret than every baseline and than LC-CLUB-L, in both arm spaces, under Zipf α=1\alpha=1 and uniform arrivals, and after the transfer to u=1000u=1000 (Table 4 of the revised PDF; reply to Reviewer Lvyv, W2).

W1, second point: rare users. With only its own data, a user can be placed in its cluster after about 1/γ21/\gamma^2 of its own observations (general response, 1.1), and this holds for any method that does not pool users of different clusters. If TT is large, the rounds before certification are a lower-order term and waiting costs little; but a rare user that arrives fewer times by TT than the certification count is never certified. By running its own LinUCB before certification, LC-CLUB-L incurs no extra loss compared with LinUCB. In the two Zipf α=1\alpha=1 main-text settings (u=1000u=1000, T=108T=10^8), the users that do not certify, about 685 of 1,000 on the raw sphere and 429 in the constructed space, have exactly LinUCB's regret, user by user, while the certified users lower the total regret from 333.3 to 320.4 and from 1,417 to 1,053 (×103\times10^3; table below).

Regret per 1,000 own rounds (users by arrival frequency, rarest first)0–25%25–50%50–75%75–100%Total (×103\times10^3)
Raw sphere: CLUB––––328.4
Raw sphere: SCLUB––––331.9
Raw sphere: LinUCB24.6613.877.021.28333.3
Raw sphere: LC-CLUB-L24.66 (0%)13.87 (0%)6.99 (26%)1.12 (100%)320.4
Raw sphere: + pairwise pools22.1311.225.130.84253.9
Constructed: CLUB––––1,432
Constructed: SCLUB––––1,393
Constructed: LinUCB76.2049.2229.257.221,417
Constructed: LC-CLUB-L76.20 (0%)48.68 (29%)23.37 (100%)3.57 (100%)1,053
Constructed: + pairwise pools36.3018.778.931.87464.0

In parentheses: share of the group's users that LC-CLUB-L certifies.

Going further, a rare user can also gain from its cluster before it certifies, and so does better than LinUCB before certification, because finding one's own cluster among users that are already estimated accurately is easier than identifying the clusters from nothing. An uncertified user ii pools with every user jj for which ∣θ^i−θ^j∣+ρi+ρj<γ~\\|\hat\theta_i-\hat\theta_j\\|+\rho_i+\rho_j < \tilde\gamma; with valid confidence radii, the test implies ∣θi−θj∣<γ~≤γ\\|\theta_i-\theta_j\\| < \tilde\gamma\le\gamma on the confidence event of Lemma 1, so by Assumption 1 the two users are in one cluster. Unlike CLUB, which pools users until a test separates them, this rule pools two users only once they are shown to be in one cluster, and the frequent users of the cluster let a rare user pass it long before it can certify. In both settings (row "+ pairwise pools"; Appendix C.7), with Eq. (12) at C=0.5C=0.5, the test links about 36,000 of the 49,500 same-cluster pairs on the raw sphere and 48,000 in the constructed space and never links two users of different clusters (at the smaller tuned constants, at most 1.7% of its links join two clusters; Appendix C.7); the total regret falls by 21% on the raw sphere and 56% in the constructed space against LC-CLUB-L, and it falls in every frequency group and every seed, the least-active quarter included (by 10.3% and 52.4% per 1,000 own rounds).

In theory, the sharing is one-way: certification uses only the user's own records, and LinUCB on a provisional pool is still a convex score, so Theorem 2 still applies, and certification, its correctness, and the certified pools are those of LC-CLUB-L. Proposition 2 (Appendix A.9, with proof) bounds the regret with the same leading term as Theorem 3.

AuthorsOpenReview ↗

Response to Reviewer aGXh (2/2)

W2. Synthetic experiments and the empirical radius.

The radius is addressed in point 2 of the general response. In short: the experiments use Eq. (12), an empirical radius of the same form as the theoretical one. It keeps the noise and dimension scale and the log⁡n/n\sqrt{\log n/n} decay but uses a fixed coefficient in place of the confidence level, so the theorems cover the theoretical configuration and Eq. (12) is evaluated by experiments. The theoretical constant is a worst-case one, and the count it gives exceeds what an agent observes within the horizon, so at the main scale the theoretical radius never certifies. We also compared Eq. (12) with the empirical radii that the compared methods run in their released code, and compared all methods under the same tuning budget; the results are in point 2 of the general response.

We also evaluate LC-CLUB on a PersonalLLM task constructed from real LLM responses (Appendix C.10 of the revised PDF): 10,402 prompts, each with 8 responses scored by 10 public reward models. The responses to a prompt are the arms (d=10d=10, K=8K=8), and a user of persona jj prefers responses by reward model jj, so there are ten exact clusters; users, binary feedback, and arrivals are simulated. T=108T=10^8, five seeds, baselines at the coefficients of their public code:

Final regret (×103\times10^3)u=200u=200, uniformZipf α=1\alpha=1Sineu=1000u=1000, uniformZipf α=1\alpha=1Sine
LinUCB497.2416.7498.31,5091,1241,511
CLUB496.7415.6496.51,5041,1171,494
SCLUB495.3416.2497.31,4831,1141,486
LC-CLUB-L350.3342.6351.51,5091,0711,511
+ pairwise pools231.8199.6230.91,085752.41,083
Phase-LC-CLUB-L316.8298.0324.31,1691,1271,177

Bold: lowest; italic: second lowest.

With u=200u=200, LC-CLUB-L has 18–29% lower mean regret than the best baseline, with no false certified pairs. With u=1000u=1000, an agent has about 10510^5 observations under uniform and Sine arrivals, which is below the certification count on this task; nobody certifies, and LC-CLUB-L equals LinUCB, while under Zipf α=1\alpha=1 the frequent agents certify and it is 3.9% below the best baseline. With the pairwise pools of Appendix C.7, LC-CLUB-L is 52–54% below the best baseline with u=200u=200 and 27–32% with u=1000u=1000, with no cross-cluster link. Phase-LC-CLUB-L (ζ=2\zeta=2), which needs no gap input, is 28–36% below the best baseline with u=200u=200 and 21% with u=1000u=1000 under uniform and Sine arrivals; under Zipf α=1\alpha=1 at u=1000u=1000 it is level with SCLUB (+1.1%).

We hope these clarifications and additional results address your concerns, and we are happy to answer any further questions.

Dear Reviewer aGXh,

Thank you again for your review. As today is the final day of the discussion phase, we wanted to kindly follow up on our rebuttal.

Your main concern was whether a lower bound on the cluster gap is available in practice, and whether rare users benefit from collaboration. In our response, we showed that without such a bound, a phase schedule removes this input at the cost of only lower-order regret terms (Theorems 6 and 7, Appendix A.8); this standard technique combines naturally with our certification analysis. We also showed that rare users lose nothing by waiting, and with pairwise pools they can share before certification without changing the certification rule (Proposition 2).

We would greatly appreciate it if you could let us know whether our response resolves your concerns.

Best regards,

Authors

Comments on the paper

4 comments
AuthorsOpenReview ↗

General Response (1/4)

We thank the reviewers. We are glad that the reviews recognise the two novel contributions of the paper: local certification removes the bottleneck that rare users create, with a guarantee that has no inverse dependence on the minimum arrival probability, and LC-CLUB-L collects reward and information at the same time, without a separate uniform-exploration phase. This response answers the two concerns that more than one reviewer raised. (1) LC-CLUB takes as input a lower bound γ~≤γ\tilde\gamma\le\gamma on the gap γ\gamma, the smallest distance ∥θj−θj′∥2\Vert\theta^j-\theta^{j'}\Vert_2 between the preference vectors of two clusters, and the question is whether such a bound is available in practice. (2) The experiments certify with an empirical radius, Eq. (12), rather than with the threshold of the theorems, and the question is whether the experiments then still support the theory and compare the methods fairly.

1. A lower bound on the gap and its availability in practice (Reviewer aGXh: W1 and Q; Reviewer FzKL: W1). Short answer: a lower bound on the gap is not always available in practice, but some such prior information is essential for a rule that shares for good, and for the case without it we give a variant, Phase-LC-CLUB-L, that does not need it. (i) Some prior information is unavoidable for a rule that shares for good: telling apart two users whose preferences differ by ε\varepsilon takes on the order of 1/ε21/\varepsilon^2 observations [1], so a rule that, with high probability, never pools different clusters needs a stopping condition, and a lower bound on the gap is one (see 1.1 below). This condition is not specific to our algorithm: the guarantees of CLUB, SCLUB and UniCLUB also depend on the gap. (ii) When no bound is known, one can use Phase-LC-CLUB-L, which removes this input: it guesses the gap and refines the guess from phase to phase. Early guesses may pool different clusters and every phase certifies again, but both cost only lower-order terms; the leading term is that of the known-gap bound (see 1.2 below). (iii) In experiments, without any gap input, Phase-LC-CLUB-L has lower regret than every baseline in every column after equal tuning (Table 4 of the revised PDF), and is below CLUB and SCLUB in five of the six main settings even untuned (see 1.3 below). At the tuned constants, a conservative bound is also cheap: with half the true gap, every agent still certifies, and LC-CLUB-L stays 28–35% (raw sphere) and 71–76% (constructed) below LinUCB (reply to Reviewer Lvyv, Q3).

1.1 Why a stopping condition is needed. It is well known that telling apart two parameters at distance ε\varepsilon takes on the order of 1/ε21/\varepsilon^2 observations [1], so the amount of exploration that clustering needs depends on the smallest gap between clusters. With no prior information, an algorithm does not know when it may stop exploring: whenever it stops, a smaller gap could still be undetected. Prior information is therefore needed to give a stopping condition. The lower bound γ~\tilde\gamma on the gap that our algorithm uses is such a condition: it fixes how many own observations an agent needs, on the order of 1/γ~21/\tilde\gamma^2, and once an agent has them it is certified, and its sharing is final. Without prior information, the other solution is the phase schedule of 1.2, which spreads exploration over the whole horizon: it keeps refining the gap that it can resolve, and this repeated exploration costs lower-order terms.

Why CLUB and SCLUB do not require this input. Clustering needs an accurate estimate for every user, and this needs the selected arms to be diverse. CLUB and SCLUB select arms by UCB and have no exploration phase; to show that the arms UCB selects are still diverse, their analyses assume that for every unit vector zz, (z⊤X)2(z^\top X)^2 is sub-Gaussian with variance at most λx2/(8log⁡(4K))\lambda_x^2/(8\log(4K)). Under this assumption, the UCB policy alone collects enough information to identify the clusters, and no exploration length has to be chosen. The UniCLUB paper [2] states that this assumption contradicts the diversity of the contexts that is also assumed, and that it is extremely difficult to construct a natural distribution satisfying both. They remove it by adding uniform exploration. Under the general Assumptions 1 and 2 alone, exploration and exploitation then become two decisions for these algorithms: the number of exploration rounds has to be set in advance, and it has to be guaranteed to suffice. UniCLUB and LC-CLUB therefore both use a lower bound on the gap to decide when exploration stops.

References:

  • [1] Shie Mannor and John N. Tsitsiklis. The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. Journal of Machine Learning Research, 5:623–648, 2004.
  • [2] Zhuohua Li, Maoli Liu, Xiangxiang Dai, and John C. S. Lui. Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts. In ICLR, 2025. arXiv:2501.00891.
AuthorsOpenReview ↗

General Response (2/4)

1.2 A phase schedule that keeps refining the gap when no lower bound is known (Theorems 6 and 7). This is the standard way to handle an unknown gap in bandits [3], which PhaseUniCLUB [2, Appendix D] brought to clustering; we apply it to LC-CLUB-U and to LC-CLUB-L and call the results Phase-LC-CLUB-U and Phase-LC-CLUB-L. Phase ss runs the submitted algorithm with a guess γs\gamma_s in place of γ~\tilde\gamma. The guess starts at the largest possible gap, 2S2S, and shrinks by a factor 2\sqrt2 from one phase to the next; the certified graph and the pools are rebuilt in each phase, and every agent keeps its own records. While the guess is larger than the gap γ\gamma, agents of different clusters may be pooled; the first term of the bound below accounts for these phases. Once it is below γ\gamma, every certified pool is correct with high probability (on the confidence event of Theorems 6 and 7), and each later phase only raises the count and certifies again.

Appendix A.8 proves the regret bounds of this schedule. Let the phase lengths grow by a factor 2ζ+12^{\zeta+1} for a fixed ζ>0\zeta > 0; for fixed problem parameters as T→∞T\to\infty, with γ\gamma unknown: for LC-CLUB-U under Assumption 2, the setting of PhaseUniCLUB (Theorem 6), E[Reg(T)]=O(udlog⁡Tλxγ2ζ+2+(udlog⁡Tλx)ζ/(ζ+1)T1/(ζ+1)+dmTlog⁡T)\mathbb{E}[\mathrm{Reg}(T)]=O\big(\frac{ud\log T}{\lambda_x\gamma^{2\zeta+2}}+(\frac{ud\log T}{\lambda_x})^{\zeta/(\zeta+1)}T^{1/(\zeta+1)}+d\sqrt{mT}\log T\big); for LC-CLUB-L under Assumption 3 (Theorem 7), for fixed dd, E[Reg(T)]=O~(ulog⁡TαKσ−2γ2ζ+2+u,(ulog⁡TαKσ−2)ζ/(2ζ+2)T1/(2ζ+2)+dmTlog⁡T)\mathbb{E}[\mathrm{Reg}(T)]=\tilde O\big(\frac{u\log T}{\alpha_K\sigma_-^2\gamma^{2\zeta+2}}+\sqrt{u}\\,(\frac{u\log T}{\alpha_K\sigma_-^2})^{\zeta/(2\zeta+2)}T^{1/(2\zeta+2)}+d\sqrt{mT}\log T\big). With ζ=2\zeta=2, as in PhaseUniCLUB, the third term is the leading term of the known-gap bound and the first two, the price of not knowing it, are of lower order: the second grows as T1/3T^{1/3} for LC-CLUB-U, as for PhaseUniCLUB, and as T1/6T^{1/6} for LC-CLUB-L, whose uncertified agents run LinUCB instead of exploring uniformly. No arrival frequency enters either bound.

1.3 Experiments with Phase-LC-CLUB-L. Unless stated otherwise, the experiments below follow the setup of the main paper and report the mean final regret over five seeds. We ran Phase-LC-CLUB-L, with Eq. (12) as its radius, in the main-text settings (final regret ×103\times10^3):

Final regret (×103\times10^3)Raw: uniformZipf α=1\alpha=1SineConstructed: uniformZipf α=1\alpha=1Sine
LinUCB375.8333.3376.11,8161,4171,816
CLUB, public code371.3328.4386.81,8161,4321,846
SCLUB, public code376.2331.9376.01,7971,3931,798
LC-CLUB-L350.3320.4350.81,1161,0531,116
Phase-LC-CLUB-L354.7449.5358.1903.51,018915.4

Bold: lowest; italic: second lowest.

Without a gap input, the schedule has lower regret than CLUB and SCLUB in five of the six settings, by 4.5–50.4%; the exception, Zipf α=1\alpha=1 on the raw sphere, comes from early phases whose guesses exceed the gap, and with tuned constants the schedule is below every baseline there as well (see 2.2 below).

Against LC-CLUB-L, the schedule starts sharing earlier: its first phase certifies an agent after 3,047 own observations in the constructed space, where LC-CLUB-L waits for 25,067. This makes its regret 13% lower on average there. In general, however, whether earlier and more aggressive sharing helps or hurts depends on the gap: while the guesses are larger than it, a pool may join users of different clusters, and only later phases, with smaller guesses, separate them. Moreover, without the gap, the schedule keeps refining and exploring, late in the run. For a user that is already identified correctly, LC-CLUB-L spends no more rounds on identification: from then on, the user acts on its certified pool. The schedule identifies it again in every phase: each new phase raises the count, and a user below it goes back to exploring on its own. This repeated identification produces the second term of its regret bound. With every method tuned by the same search, Phase-LC-CLUB-L has the lowest or second-lowest regret in every column; the tuned results are analysed in Table 4 of the revised PDF and in our reply to Reviewer Lvyv (W2 and Q2).

References:

  • [2] Zhuohua Li, Maoli Liu, Xiangxiang Dai, and John C. S. Lui. Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts. In ICLR, 2025. arXiv:2501.00891.
  • [3] Peter Auer and Ronald Ortner. UCB Revisited: Improved Regret Bounds for the Stochastic Multi-Armed Bandit Problem. Periodica Mathematica Hungarica, 61(1–2):55–65, 2010.
AuthorsOpenReview ↗

General Response (3/4)

2. The empirical radius Eq. (12): support for the theory and a fair comparison (Reviewer aGXh: W2; Reviewer Lvyv: W1, Q1 and W2). Short answer: the theorems cover the theoretical radius, while the empirical radius Eq. (12) used in the experiments is, as in the compared papers, a deliberate trade-off: the theoretical constant is a worst-case one, and at our scale it would never certify, since its count exceeds the observations an agent receives within the horizon, while Eq. (12) keeps the structure and scaling of the theoretical radius and calibrates its constants empirically (see 2.1 below). The experiments quantify the certification errors of this trade-off and show that the gains persist under equal tuning. (i) At the paper's constant C=0.5C=0.5, no run certifies a cross-cluster pair; at the smaller tuned constants, at most 0.12% of the certified links of LC-CLUB-L and its pairwise version join two clusters, on the raw sphere only. (ii) Where the theorem's count is reachable, the theoretical configuration behaves as the theory predicts, and Eq. (12) certifies far earlier without error (reply to Reviewer Lvyv, W1). (iii) With every method tuned by the same search, LC-CLUB-L is 55–73% below tuned SCLUB in the constructed space under Zipf α=1\alpha=1 and level with it on the raw sphere, and its two extensions have the two lowest regrets in every column (see 2.2 below).

2.1 The empirical radius. To the best of our knowledge, like ours, the experiments of the papers in this area run an empirical constant rather than the radius of their analysis. This is a shared insight of the area: the constant that is run trades the delay of a large radius against the errors of a small one at the given horizon. The table lists each paper's edge-deletion test, the radius of its analysis, and the constant its released code runs. Each radius of an analysis is a constant, set by noise, dimension and context diversity, times log⁡(⋅)/n\sqrt{\log(\cdot)/n}, the order of r(n)r(n). Notation: θ^i\hat\theta_i (written wiw_i in CLUB) is user ii's own estimate and TiT_i its number of observations. In SCLUB, θ~\tilde\theta and T~\tilde T are the estimate and the number of observations of the user's current cluster. In LOCB, ss is a seed user and TsT_s its number of observations. In UniCLUB's code, θˉi=θ^i/∣θ^i∣\bar\theta_i=\hat\theta_i/\\|\hat\theta_i\\|. ε∗\varepsilon^\ast is RCLUMB's misspecification level; the α\alpha's are tuning coefficients.

PaperDeletion testRadius in the analysisValue run
CLUB (Gentile et al., 2014)∥wi−wj∥>α2(r(Ti)+r(Tj))\Vert w_i-w_j\Vert > \alpha_2(r(T_i)+r(T_j))(σ2dlog⁡t+2log⁡(2/δ)+1)/1+Aλ(Ti)(\sigma\sqrt{2d\log t+2\log(2/\delta)}+1)/\sqrt{1+A_\lambda(T_i)}, AλA_\lambda linear in TiT_iα2\alpha_2 tuned on the first 5,000 rounds; 1 in the code released with SCLUB
SCLUB (Li et al., 2019)∥θ^i−θ~∥>αθ(r(Ti)+r(T~))\Vert\hat\theta_i-\tilde\theta\Vert > \alpha_\theta(r(T_i)+r(\tilde T))αθ=4Rd/λx\alpha_\theta=4R\sqrt{d/\lambda_x}αθ=1\alpha_\theta=1
LOCB (Ban and He, 2021)∥θ^i−θ^s∥>r(Ti)+r(Ts)\Vert\hat\theta_i-\hat\theta_s\Vert > r(T_i)+r(T_s)(σ2dlog⁡t+2log⁡(2/δ′)+1)/1+h(Ti)(\sigma\sqrt{2d\log t+2\log(2/\delta')}+1)/\sqrt{1+h(T_i)}, hh linear in TiT_icoefficient 1
FCLUB (Liu et al., 2022)∥θ^i−θ^j∥>α1(r(Ti)+r(Tj))\Vert\hat\theta_i-\hat\theta_j\Vert > \alpha_1(r(T_i)+r(T_j))βi(Ti,α/n)/λ+Tiλx/8\beta_i(T_i,\alpha/n)/\sqrt{\lambda+T_i\lambda_x/8}, βi\beta_i its confidence coefficientα1=1.5\alpha_1=1.5
RCLUMB (Wang et al., 2023)∥θ^i−θ^j∥>α1(r(Ti)+r(Tj))+α2ε∗\Vert\hat\theta_i-\hat\theta_j\Vert > \alpha_1(r(T_i)+r(T_j))+\alpha_2\varepsilon^\ast(λ+2log⁡(u/δ)+dlog⁡(1+Ti/(λd)))/λ+2λ~xTi+ε∗/2λ~x(\sqrt\lambda+\sqrt{2\log(u/\delta)+d\log(1+T_i/(\lambda d))})/\sqrt{\lambda+2\tilde\lambda_x T_i}+\varepsilon^\ast/\sqrt{2\tilde\lambda_x}α1=1\alpha_1=1, α2ε∗=0.3\alpha_2\varepsilon^\ast=0.3
UniCLUB (Li et al., 2025)∥θˉi−θˉj∥>α(r(Ti)+r(Tj))\Vert\bar\theta_i-\bar\theta_j\Vert > \alpha(r(T_i)+r(T_j))(2log⁡(u/δ)+dlog⁡(1+TiL2/(λd))+λ)/λ+Tiλx/2(\sqrt{2\log(u/\delta)+d\log(1+T_iL^2/(\lambda d))}+\sqrt\lambda)/\sqrt{\lambda+T_i\lambda_x/2}α=1.75\alpha=1.75

Papers and code:

AuthorsOpenReview ↗

General Response (4/4)

Our radius is Eq. (12), ρ(n)=C⋅Rd/λ^⋅r(n)+λS/(λ+nλ^)\rho(n)=C\cdot R\sqrt{d/\hat\lambda}\cdot r(n)+\lambda S/(\lambda+n\hat\lambda), with r(n)=(1+ln⁡(1+n))/(1+n)r(n)=\sqrt{(1+\ln(1+n))/(1+n)}. The theoretical radius has the same two terms. By Lemma 1 with δ=1/T\delta=1/T, after nn own observations of uniform exploration (Theorem 1) it is R2log⁡(uT)+dlog⁡(1+nL2/(dλ))/λ+nλx/2+λS/(λ+nλx/2)R\sqrt{2\log(uT)+d\log(1+nL^2/(d\lambda))}/\sqrt{\lambda+n\lambda_x/2}+\lambda S/(\lambda+n\lambda_x/2), once n≥(8L2/λx)log⁡(2udT)n\ge(8L^2/\lambda_x)\log(2udT). The theoretical constant has to hold, in the worst case, for every user and round with high probability, and it rests on a worst-case lower bound on the information a user collects, so the count it requires is too conservative. In some settings this count exceeds the observations an agent receives within the horizon, and the extra exploration raises the regret: on the raw sphere of our main setting (u=1000u=1000, T=108T=10^8), the count of Theorem 1 is 141,310 own observations, more than the T/u=105T/u=10^5 that an agent receives under uniform arrivals, so the theoretical configuration would explore through the whole run and never certify. We therefore run an empirical formula: Eq. (12) keeps the structure of the theoretical radius, the noise and dimension scale, the log⁡n/n\sqrt{\log n/n} decay and the ridge term, and replaces its confidence level with a fixed coefficient; the experiments compare the two complete configurations. In form, it is therefore closer to the theoretical radius than the radii that the released codes in the table run. It needs 15,685 own observations for LC-CLUB-U and 57,859 for LC-CLUB-L, both below 10510^5, so agents certify within the run. The reply to Reviewer Lvyv (W1) reports how Eq. (12) behaves in our runs: when agents certify, whether any certified pair crosses clusters, and the regret.

2.2 Experimental results (Reviewer Lvyv: W2 and Q2). For a fair comparison, every method is tuned by one compass search [4] on validation seeds, and the selections are tested on separate seeds and transferred, frozen, to u=1000u=1000 (reply to Reviewer Lvyv, W2, comment 2/4). After tuning, Phase-LC-CLUB-L is below tuned SCLUB, the strongest baseline, in both arm spaces at every budget, and under Zipf α=1\alpha=1 LC-CLUB-L is 55–73% below it in the constructed space; on the raw sphere it is level with it at u=250u=250 from ten configurations on and 4.8% above it after the transfer to u=1000u=1000; under Zipf α=1\alpha=1, tuned CLUB and UniCLUB stay at or above LinUCB's level. The paper's constants, C=0.5C=0.5 and λ^=λx/2\hat\lambda=\lambda_x/2, were fixed generic values before the runs; λ^=λx/2\hat\lambda=\lambda_x/2 stands for λx\lambda_x being known only through a lower bound. Neither is the best choice: in a 3×33\times3 study over C∈0.25,0.5,1C\in\\{0.25,0.5,1\\} and λ^∈λx/4,λx/2,λx\hat\lambda\in\\{\lambda_x/4,\lambda_x/2,\lambda_x\\} on the six main-text settings, the three cells with C=0.25C=0.25 and the cell (C=0.5,λ^=λx)(C=0.5,\hat\lambda=\lambda_x) have lower regret than the paper's constants in every setting and seed (reply to Reviewer Lvyv, Q3, comment 3/4). Nor are they aggressive compared with the baselines: the released codes of CLUB and SCLUB, which our submitted tables run, put a bare coefficient of 1–1.75 on r(n)r(n), while Eq. (12) has 7.1 on the raw sphere and 4.7 in the constructed space at C=1/2C=1/2.

The changes in the revised PDF. New material is marked in blue.

  • Extensions of the theory, in answer to the reviews. Theorems 6 and 7 (A.8): the phase schedule, which needs no gap, for LC-CLUB-U and LC-CLUB-L; Proposition 2 (A.9), a direct consequence of Theorem 2: sharing before certification leaves certification unchanged; Proposition 3 (A.10): a regret bound when preferences differ slightly within a cluster.
  • New experiments. Section 6.3 and Table 4: every method tuned by the same search, on test seeds and after a frozen transfer to u=1000u=1000; Appendix C.11 gives the search and its selections; Appendix C.6: the theoretical threshold against Eq. (12) under Assumption 3; Appendix C.7 and a row of Table 4: pairwise pools before certification, which lower LC-CLUB-L's regret by 17–21% (raw sphere) and 39–56% (constructed) in the six main settings at C=1/2C=1/2 and by 25–30% after the transfer to u=1000u=1000 at the tuned constants; Appendix C.8: the 3×33\times3 study of the constants and a conservative gap input; Appendix C.9 and C.10: within-cluster differences, and the PersonalLLM task.
  • Abstract and introduction: we also added short descriptions of the phase schedule and the pairwise pools.

Supplementary material. We have updated the supplementary code, which reproduces all experiments, tables, and figures in Section 6 and Appendix C, including the new ones.

We hope these clarifications and the additional results address the reviewers' concerns, and we are happy to answer any further questions.

References:

  • [4] T. G. Kolda, R. M. Lewis, and V. Torczon. Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods. SIAM Review, 45(3):385–482, 2003.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.