[KDD 2020] Generic Outlier Detection in Multi-Armed Bandit
Aug 13, 20200 views
In this paper, we study the problem of outlier arm detection in,multi-armed bandit settings, which finds plenty of applications in,many high-impact domains such as finance, healthcare, and online,advertising. For this problem, a learner aims to identify the arms,whose expected rewards deviate significantly from most of the,other arms. Different from existing work, we target the generic,outlier arms or outlier arm groups whose expected rewards can be,larger, smaller, or even in between those of normal arms. To this end,,we start by providing a comprehensive definition of such generic,outlier arms and outlier arm groups. Then we propose a novel,pulling algorithm named,GOLD,to identify such generic outlier,arms. It builds a real-time neighborhood graph based on upper,confidence bounds and catches the behavior pattern of outliers,from normal arms. We also analyze its performance from various,aspects. In the experiments conducted on both synthetic and realworld data sets, the proposed algorithm achieves 98% accuracy,while saving 83% exploration cost on average compared with stateof-the-art techniques.