Online Corrupted User Detection and Regret Minimization

Summary

This paper presents an important online learning problem named LOCUD to learn and utilize unknown user relations from disrupted behaviors to speed up learning and identify the corrupted users in an online setting. Also, the authors propose a novel bandit algorithm RCLUB-WCU, and devise a novel online detection algorithm OCCUD based on RCLUB-WCU’s inferred user relations. Extensive experiments demonstrate that the proposed methods can achieve superior performance over previous bandit algorithms and high corrupted user detection accuracy.

Strengths

1. The paper is scientifically sound. 2. The clarity of the presentation is easy to follow. 3. Extensive experiments of the proposed methods have superior performance than other baselines.

Weaknesses

1. The introduction section of the paper lacks sufficient emphasis on the motivation behind the proposed methods. The authors should provide a more comprehensive analysis of the current issues and challenges in the relevant fields, clearly indicating how their research work addresses and improves upon these challenges. This will help readers better understand the significance and contributions of the proposed methodology. 2. The abstract section should be more concise. It should effectively highlight the key innovations and improvements introduced by the proposed methodology. 3. The paper provides limited discussion and summary of the relevant literature. To strengthen the research methodology, the authors should include a more extensive review of existing research methods, along with an analysis of their strengths and weaknesses. 4. The experimental content is not enough to effectively prove the superiority of the method. It is suggested that the authors add more dimensional experiments and give a comprehensive analysis and explanation of the experimental results, thus making the conclusions in the paper more convincing. 5. The dataset used in the experiments is relatively small, which may limit the generalizability of the findings. It is recommended to supplement a large-scale real dataset for performance validation.

Questions

Provided above.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

Yes.

Summary

The paper considers the following bandit setup. There are $u$ users organised into $m\ll u$ clusters. Each cluster has vector $\theta$ attached to it. On step $t$ the learner deals with a user uniformly selected from the pool and picks an arm $a$. If this is a bona fide user, the learner gets average reward $x'_a\theta$, where $x_a$ is the feature vector for the arm and $\theta$ is the vector for the cluster the user belongs to. There is a number of corrupted users though, who give reward $x'_a\theta + \eta + c$, where $\eta$ is noise and $c$ (a bounded quantity) is corruption. We have a twofold problem of minimising the regret and identifying the corrupted users. The paper presents an algorithm based on a graph of connections between users built by observations of their behaviour. The regret upper bound is matched by a lower bound. It is shown that with high probability we identify the corrupted users correctly and after a while end up with correct clusters.

Strengths

I think this is an interesting result and a strong guarantee. The explicit modelling of corrupted user behaviour may seem restrictive at first, but it covers many possibilities. The authors were very careful to relax all the requirements as much as possible (e.g., consider sub-Gaussian noise etc). The algorithm is intuitive.

Weaknesses

No obvious weaknesses. The appeal of the result may be limited for some NeurIPS participants. Some minor suggestions (not reflected in my evaluation of the paper): 1. I do not think quantifiers should be used as in At $\forall t$, for any fixed unit vector $z$ ... (Assumption 3.) Using "every" here will not blow the volume of the paper out of proportions, but will improve readability. 2. Use $\verb!\left(...\right)!$ in formulas like (7) to get larger brackets. 3. I do not find the abbreviations used in the paper convenient and phrases such as CW-OFUL-Ind outperforms LinUCB-Ind because it considers the corruption, but worse than RCLUB-WCU easy to parse.

Questions

None.

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

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

4 excellent

Limitations

Yes.

Summary

The authors introduce an online learning problem called LOCUD (Learning and Online Corrupted Users Detection from bandit feedback) in which the aim is to detect a small fraction of the overall users with corrupt behaviors; corrupt users occasionally perform undesirable actions, but otherwise mimic normal user behavior, making them challenging to detect. The paper then proposes a framework that leverages the relations between users to form semantic clusters, and uses the clusters to identify corrupt users. Specifically, the authors propose RCLUB-WCU (Robust CLUstering of Bandits With Corrupted Users) to progressively prune a fully connected graph of users to clusters of connected components based on user interactions and preferences. Then, OCCUD (Online Cluster-based Corrupted User Detection) estimates a robust and non-robust estimation of each user's preferences, and identifies a user as corrupt if the gap between the two estimates exceeds a carefully designed threshold. OCCUD is repeatedly invoked within RCLUB-WCU to continually prune and refine the relational structure amongst the users. Experiments one on synthetic dataset and three real-world datasets show the proposed approach is able to detect more corrupted users while achieving the least amount of regret over time than competing methods.

Strengths

* The paper introduces a challenging but relevant problem of trying to identify corrupt users despite sporadic behavior in an online dynamic environment. This problem is especially relevant for sites like Amazon and Yelp which often contain users that exhibit corrupt behavior. * The proposed approach of leveraging relational information between users to more effectively detect corrupt users is intuitive, and the experimental results suggest its effectiveness. * Analyses and bounds related to regret are given for the RCLUB-WCU/OCCUD algorithm, with proofs provided in the Appendix. * The paper is generally well-written and follows a logical progression.

Weaknesses

* Experiments are performed on a small number of small datasets, potentially limiting the generalizability of the proposed approach. Performing experiments with a wider range of larger datasets would significantly benefit the claims made in the paper. * No empirical runtime analysis is provided for the proposed approach or any of the competing methods. Runtime analysis can help practitioners decide what method is likely to work best for their particular problem. * Only one baseline method is compared to the proposed approach for the AUC results (Table 1). Where are the results for the other methods? * Additional experimental results including different corruption levels and number of clusters are provided in the Appendix, but those results (Figures 4 and 5) only shows regret, and only compares the proposed approach with two baseline methods. Can the authors provide results for the other baseline methods, as well as AUC results for these additional and potentially insightful experiments? * Minor clarity improvements: * Use authors' names to cite previous work. "The work [5] proposes..." -> "Ding et al. (2022) propose...". * The legends in Figure 5 make the subplots hard to read. Figure 5 is also not color-blind friendly, consider adding markers or using different line styles for different methods.

Questions

* Why are the dataset sizes so small (e.g., 1,400 users and 800 items for Amazon)? What are the original sizes of the datasets used in the experiments? * Where are the error bars for Table 1, and Figures 4 and 5?

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

3 good

Contribution

4 excellent

Limitations

No, the authors have not addressed the limitations or the potential negative societal impact of their work.

Summary

This research paper introduces an innovative method for learning and utilizing unknown user relations from disrupted behaviors to enhance the learning process and identify corrupted users in an online setting. To achieve this, a new bandit algorithm (RCLUB-WCU) is proposed, along with an online detection algorithm that leverages user relations inferred by RCLUB-WCU. The paper also presents a regret upper bound for RCLUB-WCU, which closely matches the lower bound with respect to T (the number of rounds) up to logarithmic factors and performs well even in degenerate cases. The experiments conducted on synthetic and real-world datasets demonstrate significant improvements in performance compared to previous bandit algorithms

Strengths

1. The paper presents a novel application to learn unknown user relations in their preferences from potentially corrupted feedback. At the same time, the paper shows how to leverage the learned relations to speed up learning as well as adaptively detect the corrupted users online from bandit feedback. Overall I think this paper makes a significant contribution to the literature on online learning from corrupted feedback as well as detection of adversarial users in multi-user online learning setting. 2. Experiments on synthetic and real-world datasets clearly indicate lower reward regret of proposed approach in comparison to five other baselines from the past literature on online clustering of bandits. At the same time, the algorithm is able to identify corrupted users with higher accuracy than a simple baseline that directly compares the robust-estimators of preference vectors of a user and its corresponding cluster. 3. The authors back up their results with theoretical analysis and guarantees on the performance of the proposed algorithm.

Weaknesses

1. It seems to me that the performance of proposed approach could potentially be sensitive to the nature of underlying user relations in their preferences and the tightness of the detected clusters. For example, to my understanding, this algorithm might not work well if there are too many tight clusters. However, if one chooses too big clusters, then the solution might compromise on personalization as users in a loose cluster might not be represented accurately by a common preference vector defined for the cluster. The paper does not provide any discussion on the impact of cluster sizes on the algorithm. 2. The approach requires multiple parameters to be specified. (e.g. regularization parameter, confidence radius parameter, threshold parameter, edge detection parameter). There is no discussion provided on the sensitivity of the results to the choices of these parameters (in the main draft at least). 3. The results in Table 1 on detection of corrupted users are not very clear. To begin with, it's not clear what do numbers in the table indicate? I assume they indicate recall of true corrupted users. If so, where are the precision numbers? Where are F1 scores given that thre is class imbalance? Authors need to clearly indicate what they are measuring and also provide an explanation in case they aren't measuring both precision and recall. Also it would be nice to have comparison with multiple baselines. Further, authors could potentially enrich the results with other variants of the baseline, e.g. another baseline variant could simply compare the non-robust estimators of cluster and user. (I believe the current baseline compares the robust estimators of a user and its cluster).

Questions

1. Page 9, lines 341-345: Authors claim that the performance of the proposed algorithm improves with proportion of corrupted users in the dataset. Seems like this argument is made based on the three datapoints (from three real-world datasets). This argument could be potentially strengthened by evaluating all algorithms while varying the number of corrupted users in one of the datasets. 2. Page 6: Line 220: It says that the threshold is carefully designed to handle the estimation uncertainty... How difficult/easy it is to tune this threshold? How critical this threshold is to the performance of the approach? 3. Pages 4-5, Lines 188-204: It seems like the subscript `t` is used to denote both timestamp (bandit round) as well as the cluster? Also I see subscript `s` to indicate the bandit iteration which should ideally be denoted by t ? 4. In Equation (2), are you considering data from all t -1 previous rounds? Or are you using iterative update and only include the data from previous round, i.e. (t -1)^{th} round?

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

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central 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

Authors should cover any other limitations of this work in addition to potential limitations I highlighted above:

Thank You

I thank the authors for addressing the majority of my concerns and have increased my score accordingly.

Read author's rebuttal

I would like to thank authors for the detailed response to my original review. I have read author's rebuttal and will consider their arguments in my final rating.

Read author's rebuttal

I appreciate the authors' detailed feedback on my comments. I would like to consider the rebuttal in my final comments.