acceptodds
Under review as a conference paper at ICLR 2027

Beyond Global Clusters: Objective-Specific User Clustering for Multi-Objective Bandits

Abstract

Clustering of bandits is a common approach to improving the sample efficiency of contextual bandits in recommendation: it adaptively groups users with similar preferences and pools their interaction data. Existing methods, however, group users under a single similarity structure for the whole reward, which fails in multi-objective recommendation, where users who agree on one objective may disagree on another. To fill in this gap, we propose Clustering of Multi-Objective Bandits (CMOB), a framework that maintains one user graph per objective and pools data only within objective-specific clusters, so that two users can share data for one objective while being separated for another. We instantiate the framework as COMOLB for linear rewards; since rewards are often not linear in the context, we further propose COMONB, which applies the same scheme to the gradient features of a neural network. Both algorithms separate two users for an objective only when a confidence test certifies that their preferences differ. Our proposed algorithms are proved to never separate users of the same cluster with high probability, to recover the objective-specific partitions after an identification time that depends on the horizon only logarithmically, and to attain a Pareto regret whose dominant term scales with the number of objective-specific clusters instead of the number of users. Experiments on synthetic instances show that our algorithms outperform existing clustering methods, and on semi-synthetic MovieLens data with objective-specific user clusters, our method nearly halves the regret of learning each user independently.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
multi-objective bandits, online clustering of bandits, contextual bandits, neural bandits, Pareto regret

Reviews

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

The paper studies multi-objective contextual bandits with objective-specific user clusters. It maintains a separate user graph for each objective and pools observations over the arriving user’s neighborhood. The paper proposes COMOLB algorithm and includes its theoretical analysis. Experiments validates the algorithm's effectiveness.

Critical strengths

Objective-specific clustering is a useful modeling idea. The experiments include identification diagnostics, oracle comparisons, and ablations. The paper candidly reports settings where clustering underperforms independent learning and distinguishes the analyzed algorithms from heuristic variants.

Critical weaknesses
  1. The technical novelty beyond objective-wise replication of existing clustering machinery needs clearer justification. The structural formulation is meaningful, but much of the algorithm and proof follows established confidence-based clustering and post-identification UCB analysis. Neighborhood pooling is also present in prior work. A sharper account of the genuinely new technical obstacles would strengthen the contribution.
  2. The baseline evaluation is insufficient to establish competitiveness with existing clustering methods. Particularly relevant missing comparisons include UniCLUB/UniSCLUB and PhaseUniCLUB [1], which address the identification bottleneck through enhanced exploration, and CLUB-HG [2]. The nonlinear evaluation would also benefit from comparison with M-CNB [3], which is cited but not evaluated.
  3. The evaluation uses at most 40 users in the synthetic experiments and only the 50 most active users and 200 most-rated movies from MovieLens. This is substantially smaller than existing evaluations: SCLUB uses 1,000 users, while CLUB-HG evaluates 200 users on both MovieLens and Netflix. The small scale is particularly concerning.

[1] Li, Zhuohua, et al. "Demystifying online clustering of bandits: Enhanced exploration under stochastic and smoothed adversarial contexts." International Conference on Learning Representations. Vol. 2025. 2025.

[2] Cheng, Xiaotong, et al. "Parallel online clustering of bandits via hedonic game." International Conference on Machine Learning. PMLR, 2023.

[3] Ban, Yikun, et al. "Meta clustering of neural bandits." Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.

Questions for authors
  1. How robust is irreversible deletion to approximate clusters, reward-model misspecification, and inaccurate noise or parameter bounds?
  2. Which theoretical step fundamentally requires a new multi-objective argument beyond combining objective-wise clustering guarantees with a Pareto-UCB confidence-width argument?
  3. In experiments, especially the experiments on MovieLens, can the algorithm demonstrate useful learning and identification for both objectives, and evaluate several preference weights and more than two objectives? This would help establish that the benefits extend beyond favorable PSG values.
Reviewer_87aPOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a new bandit setting, three algorithms dedicated to this setting, and the corresponding analysis of the two first. The setting is a multi-user, multi-objective scenario where for each objective the users can be clustered in groups of same preferences for the arms (these clusters being distinct from an objective to another). Each arm is associated to a vector xx and the mean reward per objective and cluster of users is assumed to be a fixed unknown linear combination of the elements of xx. The proposed approaches consider both the situation where the bandit algorithm only aims at playing any pareto optimal arm, and the one where the tradeoff between objectives is fixed.

Both algorithms base their selection on a user graph per objective, where the data collected for the neighbor of current user are used to estimate its linear combination parameters. Hence, two connected users are assumed in the same cluster. The proposed algorithms COMOLB and COMONB-Frozen learn a linear combination of respectively xx and ϕ(x)\phi(x)m, where ϕ\phi is a fixed and known function (typically a neural network (NN)).

The experiments also consider COMONB-Adam variant of COMONB-Frozen which trains ϕ\phi along recommendations.

Critical strengths

Novelty and completeness of the setting The setting is new, interesting, and make sens. The paper properly handles both faces of the setting: pure pareto-optimality, and optimisation of a fixed tradeoff.

Critical weaknesses

Limited challenge It looks like the new setting did not lead to any technical challenge. The algorithm simply consists in building a clustering graph per objective (which is obvious given the setting), and the theoretical analysis probably follows the same path.

No clear evidence of the interest of the COMONB variants COMONB-Frozen does not learn the representation and is therefore of smaller interest, especially while COMOLB stands for a similar mission.

COMONB-Adam caries high expectations as one hopes it would adapt to non-linear settings. However, the theoretical analysis only stands for COMONB-Frozen with no evidence on the possibility to extend it to COMONB-Adam, and the only experiments with COMONB-Adam are on simple synthetic data.

Questions for authors

I only have one question: please point toward new challenges arising from the setting.

remarks ans suggestions

Section 2 would benefit from a few transition sentences, typically right before Assumptions (A1) and (A2), and at the start of Section 2.2.

In the experiments behind Table 1, the distance between each pair of user is the same. Therefore it's hard to disclose a setting where COMOLB really shines:

  • when the arms are close, a unique arm is almost as efficient as COMOLB,
  • when the arms are far away, considering each arm independently is the best option. Currently COMOLB is the only approach adapting itself to both extreme, but another distribution where some arms are close and others far away may better sell the interest of COMOLB.

It's frustrating that Table 8 was in the Appendix, while it's the only one displaying results of COMONB-Adam.

It's also disappointing that the only experiment on "real"/semi-synthetic data was on MovieLens expressed as a linear problem, it does not allow COMONB-Adam to shine.

Typo, L460-461: "...by the centERs ..."

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

This paper studies user clustering in multi-objective contextual bandits. Existing clustering-of-bandits methods use a single global similarity structure for all objectives, which causes negative transfer when users are similar on one objective but differ on another. The authors propose the CMOB framework, which maintains one user graph per objective and pools data only within objective-specific clusters. Two instantiations are given: COMOLB (linear rewards, parameter-space deletion test) and COMONB-Frozen (frozen random-network gradient features, prediction-space deletion test). Theoretical guarantees: (i) no same-cluster edge is ever deleted w.h.p., (ii) the objective-specific partitions are recovered after an identification time logarithmic in T, and (iii) Pareto regret whose dominant term scales with the number of clusters m_c rather than the number of users (Õ(d√(m_c T))).

Critical strengths
  1. The new setting with non-trivial theory. Finite-time guarantees for per-objective graphs under a Pareto selection rule — no false separation, partition recovery, and regret scaling with m_c — are new, and the analysis must control confidence bounds across multiple graphs simultaneously.
  2. Insightful experimental analysis. The paper explicitly identifies when the method is worse than independent learning (large γ, approximate clusters) and explains why (pre-recovery mis-pooling dominates), which is valuable for practitioners and increases the credibility of the results.
Critical weaknesses
  1. The identification cost Õ(u/κ·(1+d/γ²)) involves κ_{x,K}, which is worst-case over selection rules (exponentially small in K in general; only K⁻² for spherical contexts), and the method only pays off when clusters share a large common component. In the raw MovieLens version (approximate clusters), even the oracles lose to independent learning and COMONB is 16% worse than Ind — the structural gain is not yet realized in realistic, non-exactly-clustered settings.
  2. Small-scale, semi-synthetic evaluation only. All experiments run in environments constructed to satisfy the paper's assumptions. In Section 5.3, the MovieLens rewards are defined to be linear in the context (satisfaction = SVD affinity, novelty = genre dissimilarity), so the linear/fixed-feature model holds by construction and there is no model misspecification.
  3. In the exact version, users are replaced by k-means cluster centers, artificially imposing the γ-separated objective-specific structure. There is no evaluation with real feedback (e.g., actual ratings/clicks) and no test of robustness when the modeling assumptions are violated. The multi-objective dimension is essentially limited to m_o = 2.
Questions for authors
  1. The theoretical identification time is conservative by orders of magnitude: is there a data-driven threshold or adaptive radius that preserves part (i) (no false separation) while recovering some of the practical gain?
  2. The α-scaled rule (α = 0.3) achieves the lowest PSG but deletes ~1/4 of same-cluster edges. Are deleted edges ever restored? If not, would a soft-merging mechanism be a viable guaranteed alternative to permanent deletion?
  3. How does the approach scale to m_o > 2 objectives, given the O(m_o·u²) graph memory and per-round deletion tests? Any approximation schemes?
  4. The main text contains no figures: could the rebuttal/revision include (a) cumulative-regret curves in the main text illustrating the two-phase behavior (pre-recovery mis-pooling vs. post-recovery learning), and (b) a plot of recovery time vs. γ and K against the theoretical bound? Both datasets already exist in the appendix.

Comments on the paper

1 comment

Dear Area Chair,

Thank you very much for your time and service in handling our submission (#36904).

Early in the discussion period (Nov 10), we posted a comprehensive rebuttal comprising 19 new experimental settings (690 runs) under a unified protocol to address every theoretical and empirical question raised by Reviewers Qcvx, 87aP, and LGa3. As the discussion period is closing without post-rebuttal reviewer responses yet, we respectfully summarize our key resolutions and main takeaways below (with full numerical tables available in our Nov 10 rebuttal comments):

1. Theoretical Novelty & Algorithmic Design (R-87aP, R-LGa3)

  • Multi-objective clustering is fundamentally non-reducible to single-objective analyses: Joint action selection across mom_o graphs couples data trajectories across incompatible partitions, whereas maintaining per-objective graphs avoids combinatorial cluster fragmentation (∑kmc(k)\sum_k m_c^{(k)} vs. ∏kmc(k)\prod_k m_c^{(k)}). We resolve this coupling via a policy-agnostic subspace lower-tail bound, fixed-group martingale transfer, decoupled bias–noise deletion, and pathwise PSG vs. scalarized-regret guarantees.
  • Subspace prediction testing overcomes feature collinearity (COMONB-Frozen vs. COMOLB): When features are overparameterized (pk>rkp_k > r_k) or nearly collinear (e.g., MovieLens or NTK representations), parameter-space confidence radii stall; in contrast, COMONB-Frozen tests in prediction space over the active context subspace, remaining well-conditioned with an exact ∣S∣×∣S∣|S|\times|S| kernelized form.

2. Modern SOTA Baselines (2023–2025) & Threshold Calibration (R-LGa3, R-Qcvx, R-87aP)

  • We implemented four recent SOTA baselines—UniCLUB (ICLR'25), PhaseUniCLUB (ICLR'25), CLUB-HG (ICML'23), and online neural clustering M-CNB (KDD'24)—and verified that COMONB-Frozen's earlier gap on MovieLens Raw stemmed solely from overly conservative worst-case radii (α=1\alpha=1) prolonging initial mis-pooling.
  • With a validation-calibrated scale α\alpha (selected on held-out seeds per task family and fixed across all test runs, weights, and scales), our methods consistently and substantially outperform both Ind and all 2023–2025 linear/neural clustering baselines across MovieLens and nonlinear benchmarks (e.g., cutting scalarized regret by 79%–94% vs. Ind).

3. Genuine User Feedback & Heterogeneous Cluster Geometries (R-Qcvx, R-87aP)

  • Evaluated directly on chronological actual observed MovieLens ratings (without synthetic reward generation), COMONB-Frozen forms effective collaboration pools and consistently outperforms both Ind and neural M-CNB across preference weights, confirming that our gains hold on noisy real-world user feedback.
  • In R-87aP's diagnostic scenario where close and distant clusters coexist, COMOLB adaptively separates distant clusters while keeping close clusters pooled, achieving large regret reductions over both Ind and single-graph I-CLUB.

4. Scalability in Users, Objectives, and Graph Maintenance (R-LGa3, R-Qcvx)

  • Scaling up to u=1,000u=1,000 users (T=500kT=500\text{k}) and mo=5m_o=5 objectives, our performance gains remain stable with user scale and grow even more pronounced as the number of objectives increases, empirically confirming that per-objective graphs prevent the refinement collapse suffered by single-graph baselines (I-CLUB, PhaseUniCLUB).
  • Per-objective diagnostics confirm lower estimation MSE and high intra-cluster edge retention, while sparse seed-graph and component-caching approximations reduce graph maintenance to O(moulog⁡u)O(m_o u \log u).

5. Robustness Beyond Ideal Assumptions & Manuscript Updates (R-Qcvx, R-87aP, R-LGa3)

  • Under stress tests with approximate clusters (ε>0\varepsilon>0), 4×4\times underestimated noise, and nonlinear reward misspecification (Quadratic/Cosine), our framework degrades gracefully and maintains consistent regret improvements over Ind and M-CNB; we also provided concrete extensions (edge restoration and soft pooling) for non-stationary settings.
  • Moving Fig. 1 (regret curves), Table 6 (recovery time vs. γ,K\gamma, K), and Table 8 (nonlinear results) from the appendix into the main text and refining transitions in Section 2 are straightforward edits; we fully commit to incorporating all of these presentation improvements and new experimental results into the revised manuscript.

We sincerely thank you again for your time and thoughtful consideration of our work.

Best regards,

Authors of Submission #36904

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.