- 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
-
This paper develops a meaningful treatment of heterogeneous arrivals that addresses the statistical issue in historical pooling.
-
The Theorem 2 provided in this paper is useful since it connects information acquisition needed for certification to reward-directed action selection.
Critical weaknesses
-
The practical variant lacks validation under its corresponding theorem.
-
The baseline calibration limits the interpretation of the empirical advantage.
Questions for authors
-
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)?
-
Do the main gains remain when UniCLUB, CLUB, SCLUB, and LC-CLUB receive the same independent validation budget?
-
How sensitive are certification times and regret to conservative gap and diversity lower bounds?
5 comments
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 . 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; for SCLUB; for UniCLUB) and at 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 to . The score is mean regret on validation seeds 110–112 (Zipf , , M). 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 as inputs.
Selections. SCLUB: , and at 5, 10 and 15 configurations, in both spaces. LC-CLUB-L: 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 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 (), test seeds | 5 configs: raw | constr. | 10 configs: raw | constr. | 15 configs: raw | constr. |
|---|---|---|---|---|---|---|
| LinUCB | 84.93 | 369.7 | 84.93 | 369.7 | 84.93 | 369.7 |
| tuned CLUB | 83.46 | 369.7 | 83.46 | 369.8 | 83.46 | 369.8 |
| tuned UniCLUB | 86.34 | 370.6 | 86.34 | 370.1 | 85.88 | 370.1 |
| tuned SCLUB | 81.30 | 297.7 | 46.83 | 193.3 | 45.82 | 176.0 |
| tuned LC-CLUB-L | 46.06 | 81.34 | 46.06 | 79.34 | 46.06 | 78.27 |
| tuned LC-CLUB-L + pairwise pools | 37.79 | 68.52 | 37.79 | 69.33 | 37.79 | 74.29 |
| tuned Phase-LC-CLUB-L | 39.74 | 73.58 | 38.43 | 70.45 | 38.43 | 70.45 |
Bold: lowest; italic: second lowest. 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; , M, test seeds 210–214) brings CLUB and UniCLUB well below LinUCB:
| Final regret (), uniform arrivals | Raw sphere | Constructed |
|---|---|---|
| LinUCB | 92.74 | 443.46 |
| tuned CLUB | 69.56 | 194.87 |
| tuned UniCLUB | 58.47 | 337.32 |
| tuned SCLUB | 46.25 | 139.06 |
| tuned LC-CLUB-L | 49.08 | 86.21 |
| tuned LC-CLUB-L + pairwise pools | 43.74 | 84.30 |
| tuned Phase-LC-CLUB-L | 37.26 | 66.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 and on seeds 310–314:
| Final regret (), transfer | Raw sphere | Constructed |
|---|---|---|
| LinUCB | 333.0 | 1,418 |
| tuned CLUB | 332.5 | 1,418 |
| tuned UniCLUB | 366.4 | 1,423 |
| tuned SCLUB | 162.4 | 564.1 |
| tuned LC-CLUB-L | 170.2 | 232.7 |
| tuned LC-CLUB-L + pairwise pools | 127.2 | 162.3 |
| tuned Phase-LC-CLUB-L | 139.6 | 198.6 |
On the raw sphere, at , 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.
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 of the rounds the regret (, 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 , the lead of tuned SCLUB shrinks from 10.6 to 7.8 () over this last fifth.
and 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 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 because in practice only a lower bound on is known; at every the row with the true is at or below ours. We ran LC-CLUB-L on the six main-text settings, on the same streams and seeds, over and . 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 (%), certified | Uniform, | 0.5 | 1 | Zipf , | 0.5 | 1 | Sine, | 0.5 | 1 |
|---|---|---|---|---|---|---|---|---|---|
| Raw sphere, | −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, | −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, | −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, | −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, | −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, | −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, instead of , raises mean regret at by 2.4–31%. A larger or a smaller raises the count that certification needs; the counts are:
| Certification count | 0.5 | 1 | |
|---|---|---|---|
| Raw sphere, | 28,165 | 123,871 | 554,979 |
| Raw sphere, | 13,050 | 57,859 | 261,363 |
| Raw sphere, | 6,004 | 26,875 | 122,573 |
| Constructed, | 13,775 | 53,822 | 235,340 |
| Constructed, | 6,419 | 25,067 | 110,372 |
| Constructed, | 2,973 | 11,603 | 51,513 |
Under uniform and Sine arrivals, each agent has about observations by . Every cell whose count exceeds certifies nobody (0 of 1,000), and the run then equals LinUCB exactly: these are the entries 0. Under Zipf 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 agents at , each agent has about 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):
| Raw: | 0.5 | 1 | Constructed: | 0.5 | 1 | |
|---|---|---|---|---|---|---|
| −31.4 | −18.4 | −5.1 | −65.6 | −56.4 | −35.8 | |
| −38.3 | −25.2 | −11.7 | −69.3 | −62.5 | −47.9 | |
| −45.5 | −31.9 | −18.5 | −73.1 | −66.4 | −56.8 |
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 T. As in most papers in this area, Eq. (12) keeps the form of that radius, the noise and dimension scale, the logn/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, ridge λ=LT2) and with Eq. (12), under uniform and Zipf α=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⊕A4, independent N(0,0.1I10) perturbations and N(0,1) reward noise, the theorem's count is 3.26×109 own observations, more than T=108, 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.
To see the theorem's configuration at work, we also ran a small instance with a horizon long enough to reach its count: u=10, two equal clusters θ=±e1 (γ=2), d=K=5, T=2×109, five fresh seeds; each x=μ+N(0,I), with μ uniform on the unit sphere in span(e2,…,e5), and reward noise N(0,1).
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), 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.