Online Clustering of Bandits with Misspecified User Models

Summary

This work proposes the clustering bandit problem with misspecified reward functions. It proposes the RCLUMB and RSCLUMB algorithms and their upper bounds match the state-of-the-art ones in some degenerate cases. Numerical results are provided to evaluate the performances of proposed algorithms. ================== The score is updated to 6 after rebuttal.

Strengths

1. It is good to study the 'combination' of clustering bandits and misspecified bandits, as they are both realistic topics. 2. The paper is well organized, and contributions are mostly well described. For instance, Lemma 5.7 is highlighted as a key result to bound the regret due to misclustering users. 3. The intuition of algorithm design of RCLUMB is in great details and easy to understand. Especially, in Section 4, the steps Cluster Detection, Cluster-based Recommendation, Update User Statistic and Update User Statistics are well explained. 4. Section 5 presents a clear description of the analytical analysis of RCLUMB. In detail, the 'Discussion and Comparison' and proof sckech for Theorem 5.3 are easy to follow. 5. The proposed RCLUMB algorithm is evaluated by numerical experiments in both synthetic and real data sets.

Weaknesses

Overall, I believe this work is challenging and it provides a set of meaningful results and I still here is some possible venues for improvement: 1. It is stated that the CB algorithms which were designed for bandits without misspecification will cause a large regret. I believe it is true with high probability and some discussion is provided in Remark 1, but it would be appreciated if an upper bound on the regret of them in bandits with misspecification can be presented in the paper. 2. A lower bound may help us to learn whether the proposed algorithms are efficient, but is not provided in the work.

Questions

Please refer to the *Weakness* section for questions/suggestions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

The paper studies the contextual linear bandit setup with model misspecification in the framework of clustering bandits. This investigation revolves around a particular model misspecification framework, aiming to address the challenge posed by two independent sources of error: model misspecification and the bandit process itself. To tackle this challenge, the paper introduces two algorithms including RCLUMB and RSCLUMB. The former algorithm considers the feature similarity of users as clusters on graphs, while the latter treats it as a set. The authors establish regret upper bounds and present a corresponding lower bound to showcase the theoretical guarantees offered by both the proposed algorithms. Lastly, the paper provides empirical evaluations of the proposed algorithms by employing both synthetic and real-world data. These evaluations serve to validate and assess the effectiveness of the algorithms in practical scenarios.

Strengths

The paper presents a distinctive approach by integrating two previously examined bandit setups, resulting in novel contributions in terms of problem formulation, proposed algorithm, and theoretical insights. The manuscript exhibits exemplary writing, effectively conveying the central idea. While the individual concepts of CB and MLB have been extensively studied, the combination of them as provided in the paper introduces a more practical setup, thereby amplifying the significance of the central problem. The authors of the paper explicitly state the assumptions, which either draw from previously established work or represent a milder version of the same, providing apt discussion concerning the parameters defined in the Theorem, ensuring a comprehensive understanding of their implications. To support the theoretical claims, the manuscript furnishes ample empirical evidence, underscoring the effectiveness of the proposed algorithms.

Weaknesses

Concerns are highlighted with the following points : 1) Comparison between the two proposed algorithms: The main paper does mention two algorithms, but the paper seems to be lacking any discussion surrounding any theoretical comparison between the two. Can they be applied to the same problem? Scenarios to consider for highlighting the pros and cons of using one over another? Sample toy problem to support the claims? Any differences in the meta performance by using set nature over graph nature? 2) Justification of algorithmic choices : i) While 1-hop clusters would provide a more close network, they will also lead to lower number of data points. How is the comparison taken into account? It is possible that the increase in data by considering a 2-hop network could be better aligned with the current user. How does the paper handle this possibility? ii) Line 72 -- we design a more tolerant edge design algorithm. More tolerant in comparison to? iii) In order to ensure the theorem statements, do the model misspecification parameter $\epsilon^*$, noise variance $\sigma^2$, and magnitude of the feature vector need to be in some relation? How is the paper quantifying the relationship between the three? 3) Limitation and Failure: Would really appreciate a discussion on the limitation and failure cases of what the algorithm and problem setup is lacking and future directions of research with literature reference.

Questions

1) Traditional notions of robustness typically involve outliers in data. In the case of the two algorithms mentioned in the paper, which include the term ``Robust'' in the titles, what is robustness tackling here? It is important to clarify what specific aspect of robustness they aim to address in this context. 2) Is there a specific rationale for starting with a complete graph and employing successive elimination rather than an empty graph and successive addition? Intuitively, I would assume the latter approach would yield superior rewards in the initial few rounds, as it would be more focused on the data provided by the sampled arm itself. 3) While the paper engages in a discussion regarding the selection of parameters within the range of (-0.2, 0.2), it is worth exploring other system parameters that influenced this decision-making process. Were there any additional system parameters that contributed to determining the range of parameters chosen?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The paper demonstrates commendable discussions concerning the limitations of the theorem statements and assumptions. However, it would be highly beneficial to have similar discussions regarding the problem setup in relation to the existing landscape of works in the bandit domain. Further, by examining the gaps or areas that have not been sufficiently addressed, and highlighting how the proposed problem formulation fills those gaps, the authors can contextualize their work and reinforce its significance. Additionally, discussing the differences or similarities between the proposed problem setup and the previous approach can contribute to a more comprehensive evaluation of the paper's novelty and the implications of its findings.

Summary

This paper considers a new bandit problem setting, clustering of bandits with misspecified user models. Here, the misspecified user model means the expected reward does not follow a perfect linear model. Authors give a regret upper bound of $O(\epsilon_*T\sqrt{d\log{T}}+d\sqrt{T}\log{T})$, which is basically a combination of cost from regular CB and the cost from bounded deviation, which is not surprising. And then authors also provide a "desperate" and linear lower bound due to the bounded deviation.

Strengths

The only strength I can find is the lower bound, which conveys the message that this problem do not have any value as it will result in a linear lower bound. If I miss anything, please notify me.

Weaknesses

1. The presentation is poor. i) the notation system is chaotic, ii) lack of description when introducing the algorithm. 2. Lack of novelty in problem setting and result. At least for me, this paper considers an A (CB) + B (MLB) problem, so as the result (upper bound). 3. The proof is, as well, a simple combination of CB and MLB.

Questions

1. Could you provide some recent literature review about CB? The most related work [25] you mentioned was published 4 years ago, and there is a huge gap. 2. In line 123, for the matrix norm, the matrix $M$ should be PD. Otherwise, you should not call it a norm. See ref: https://en.wikipedia.org/wiki/Norm_(mathematics). 3. Could you please improve your notations, for example, in line 131 and 132, $j(i)$, $i$, and $\ell$? Please check the consistency. 4. In line 133, since it is a contextual bandit problem, can it be extend to infinite arm set? 5. Line 146, what if the user do not come uniformly? For example, for social network, some users are heavy user, whereas some are not. 6. Line 152, I found the assumption of the bounded misspecification is useless, because the most worse case of this misspecification is a uniform distribution. Consequently, it is sub-Gaussian, and then can be absorbed into $\eta$. Please provide explanation.

Rating

1: Very Strong Reject: For instance, a paper with trivial results or unaddressed ethical considerations

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

1 poor

Presentation

1 poor

Contribution

1 poor

Limitations

See weakness before.

Summary

This paper studies multi-agent linear bandits with cluster-structure and mis-specification. At each time, an user is chosen independently and an arm from a finite set of arms is to be recommended for this user. Subsequently, the decision maker observes a noisy and mis-specified reward. The users are assumed to have an underlying latent cluster structure with well separated clusters. The goal of the decision maker is to minimize the total regret of all the decisions made over time. The main result of the paper is an algorithm in which the decision maker has a running estimate of the clustering of users which is used to make recommendations. The regret bound scales sub-linearly in the number of agents (which indicates the learning algorithm is able to exploit the underlying cluster structure) and optimally in the mis-specification bound.

Strengths

1) The paper combines in a non-trivial manner, works on mis-specified linear bandits and clustered multi-agent bandits. 2) Technically, the paper moves past a restrictive technical assumption on the distribution of the arms first adopted by Gentile at.al. and followed by all subsequent works. This is a good contribution just in the study of clustered multi-agent bandits.

Weaknesses

The only weakness is that the mis-specification upper bound \epsilon^* is both 1. needed for the algorithm as an input, and 2. The regret scales as this upper bound \epsilon^* as opposed to the true unknown mis-specification upper bound of the problem.

Questions

Comment on the weakness in terms of knowledge of \epsilon^* can help elucidate why the assumption is needed or is non-trivial to overcome.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA

Summary

This paper proposes the clustering of bandits with misspecified user models problem. Clustering of bandits combines collaborative filtering with standard contextual bandits in order to cluster users into groups which share a common reward $\theta$. This paper modifies the setting by allowing users to have deviation vectors $ \epsilon^{i_t, t}$ so that the reward is $r_t = x_{a_t}^T\theta_{i_t} + \epsilon_{a_t}^{i_t, t} + \eta_t$. They then propose two algorithms for this setting, prove their performance, and do experiments to show the improved results.

Strengths

1) Model misspecification is a problem in online clustering bandits 2) Experimental comparison is quite favorable towards the developed algorithms 3) The developed algorithms have proven regret guarantees

Weaknesses

1) ~~RSCLUMB is not well motivated~~ 2) Writing is a bit tricky to follow at times. For example, lines 309-310 are unclear to me are we moving the $\|\theta_{i_s} - \theta_{i_t}\|_2$ out and bounding it by the term on line 310? Or are we using the term from Lemma 5.7? Is the term from 5.7 substantially better? 3) ~~The experiments are missing the baseline of learning a reward $\theta$ for each user separately~~

Questions

1) Does $\epsilon_{a}^{i_t, t}$ vary over time? The $t$ superscript and line 141 make it seem like it does, but it's not clear to me how the algorithm could learn a user's deviation vector which is unknown and different at each timestep. If it varies over time, how does $\epsilon_{a}^{i_t, t}$ differ from the noise $\eta_t$? 2) Why do we talk about RCLUMB and RSCLUMB? 3) How do your algorithms compare to the baseline of just learning a reward $\theta$ for each user separately?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors have not discussed the limitations, though they are similar to those for other bandit papers

Summary

This paper introduces the problem of clustering of bandits with misspecified user models (CBMUM), where the expected rewards in user models can deviate from perfect linear models. The paper presents two robust CB algorithms, RCLUMB and RSCLUMB, that aim to deal with inaccurate user preference estimations and erroneous clustering caused by model misspecifications. The regret upper bounds of the algorithms are provided under introduced assumptions, and experiments show their outperformance over previous linear bandit algorithms.

Strengths

- The paper studied a practical and important problem of clustering of bandits with misspecified user models, which is a more realistic scenario than assuming perfect linearity. - The theoretical analysis provides regret upper bounds for the algorithms under introduced assumptions.

Weaknesses

- The paper's theoretical results are significantly undermined by the inclusion of impractical assumptions. The analysis relies on the existence of a pre-specified maximum misspecification level, denoted as $\epsilon^*$, which is used as a hyper-parameter. However, in real-world scenarios, such prior knowledge is generally unavailable. Furthermore, the paper fails to offer any insights on how to determine this parameter and how it affects the model. As a result, the practical relevance and applicability of the findings are considerably weakened. - The motivation behind the proposed algorithm is insufficient. The paper suggests clustering bandits with misspecified user models as a solution to handle situations where the reward function does not necessarily adhere to linearity. However, it fails to discuss the extensive research conducted on non-linear bandits in recent years, as mentioned in [1,2]. Moreover, the existing work on clustering in the non-linear setting, as discussed in [3], significantly undermines the perceived contribution and novelty of this paper. - The experimental evaluation is limited. Only 1000 items and users are selected to perform the experiments, which is far from practical. The paper also fails to compare the proposed clustering algorithm with other recommender system algorithms [4]. Furthermore, the paper lacks an analysis of the learned clustering strategy, which could offer valuable insights into the practical pattern of clustering. Including such comparisons and analyses would enhance the overall quality and applicability of the experimental evaluation. [1] Neural Contextual Bandits with UCB-based Exploration. ICML 2020 [2] Neural Thompson Sampling. ICLR 2021 [3] Neural Collaborative Filtering Bandits via Meta-Learning. [4] Neural Collaborative Filtering. WWW 2017 /****************/ I couldn't include the authors in the comments below, so I've commented here. Thanks for the rebuttal. After carefully reading the points and others’ reviews, I‘m still not satisfied with the motivation, experimental evaluation, and the empirical selected misspecification level. For the motivation, the main benefit of the proposed bandit among neural bandits to handle non-linearity is efficiency. However, the efficiency of the proposed algorithm among other linear or non-linear bandits is not verified in the paper. The scalability of the used datasets is also quite small (maximum 10000 users only), which is difficult to support the claim of efficient. For the experimental evaluation, despite the dataset size, the choice to only rank a subset of items of each user is far from practical. The discussion with the recommender system literature is also insufficient as the online recommendation with the same setting are ignored. Furthermore, the significance of deriving the bound involving the term O(T) does not appear substantial. My rating will remain unchanged.

Questions

Please refer to the weaknesses I mentioned above.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

I'm not aware of any potential negative societal impact in the paper.

Thank you for your response.

I would encourage the authors to add the discussion from this response in the revised version of the draft. In addition, I will also encourage the authors to state that they do NOT need a restrictive assumption on the conditional variance that Gentile et.al. (2014) require which all subsequent works on clustering of multi-agent bandits employ. **It was shown by Lattimore et.al., that no distribution can satisfy the conditional variance assumption!** In this light, moving past that assumption can be bubbled up as a contribution of the paper.

Response to Rebuttal

Ah, thanks! I had misunderstood some important aspects of the paper, and I found this response to be helpful. In light of this, I am revising my previous score. I would now summarize the core contribution of this paper as showing that where Clustering Bandits previously grouped users in order to pool data and get higher reward sooner, this paper shows that grouping strategies can also in fact help to overcome model misspecification, and attain a regret bound that agrees with the lower bound on misspecified bandit problems up to a logarithmic factor.