  We study a variant of the thresholding bandit problem (TBP) in the context of
outlier detection, where the objective is to identify the outliers whose
rewards are above a threshold. Distinct from the traditional TBP, the threshold
is defined as a function of the rewards of all the arms, which is motivated by
the criterion for identifying outliers. The learner needs to explore the
rewards of the arms as well as the threshold. We refer to this problem as
"double exploration for outlier detection". We construct an adaptively updated
confidence interval for the threshold, based on the estimated value of the
threshold in the previous rounds. Furthermore, by automatically trading off
exploring the individual arms and exploring the outlier threshold, we provide
an efficient algorithm in terms of the sample complexity. Experimental results
on both synthetic datasets and real-world datasets demonstrate the efficiency
of our algorithm.
