  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.
