Online Corrupted User Detection and Regret Minimization
Not on the map. Why?
Abstract (arXiv)
In real-world online web systems, multiple users usually arrive sequentially into the system. For applications like click fraud and fake reviews, some users can maliciously perform corrupted (disrupted) behaviors to trick the system. Therefore, it is crucial to design efficient online learning algorithms to robustly learn from potentially corrupted user behaviors and accurately identify the corrupted users in an online manner. Existing works propose bandit algorithms robust to adversarial corruption. However, these algorithms are designed for a single user, and cannot leverage the implicit social relations among multiple users for more efficient learning. Moreover, none of them consider how to detect corrupted users online in the multiple-user scenario. In this paper, we present 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. To robustly learn and utilize the unknown relations among potentially corrupted users, we propose a novel bandit algorithm RCLUB-WCU. To detect the corrupted users, we devise a novel online detection algorithm OCCUD based on RCLUB-WCU's inferred user relations. We prove a regret upper bound for RCLUB-WCU, which asymptotically matches the lower bound with respect to T up to logarithmic factors, and matches the state-of-the-art results in degenerate cases. We also give a theoretical guarantee for the detection accuracy of OCCUD. With extensive experiments, our methods achieve superior performance over previous bandit algorithms and high corrupted user detection accuracy.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 24 of its 39 references that are in the map. First posted on arXiv 7 Oct 2023.
Builds on
24 of 39 references.
References · 24
- 2020Enhancing Graph Neural Network-based Fraud Detectors against Camouflaged Fraudsterscited by 248
- 2020A Semi-supervised Graph Attentive Network for Financial Fraud Detectioncited by 150
- 2018Stochastic bandits robust to adversarial corruptionscited by 118
- 2013From Amateurs to Connoisseurs: Modeling the Evolution of User Expertise through Online Reviewscited by 107
- 2014Online Clustering of Banditscited by 99
- 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
- 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
- 2018Adversarial Attacks on Stochastic Banditscited by 56
- 2019Data Poisoning Attacks on Stochastic Banditscited by 52
- 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
- 2019Improved Algorithm on Online Clustering of Banditscited by 38
- 2020Adversarial Attacks on Linear Contextual Banditscited by 34
12 more
- 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
- 2017Online Clustering of Contextual Cascading Banditscited by 24
- 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 23
- 2018Data Poisoning Attacks in Contextual Banditscited by 22
- 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
- 2023Contextual Combinatorial Bandits with Probabilistically Triggered Armscited by 18
- 2022Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Armscited by 15
- 2023Efficient Explorative Key-term Selection Strategies for Conversational Contextual Banditscited by 12
- 2023Online Clustering of Bandits with Misspecified User Modelscited by 12
- 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
- 2022Federated Online Clustering of Banditscited by 10
- 2017HoloScope: Topology-and-Spike Aware Fraud Detectioncited by 7
Built on by
Citing papers per year: 2025: 3.
3 papers.