  We study the problem of Robust Outlier Arm Identification (ROAI), where the
goal is to identify arms whose expected rewards deviate substantially from the
majority, by adaptively sampling from their reward distributions. We compute
the outlier threshold using the median and median absolute deviation of the
expected rewards. This is a robust choice for the threshold compared to using
the mean and standard deviation, since it can identify outlier arms even in the
presence of extreme outlier values. Our setting is different from existing pure
exploration problems where the threshold is pre-specified as a given value or
rank. This is useful in applications where the goal is to identify the set of
promising items but the cardinality of this set is unknown, such as finding
promising drugs for a new disease or identifying items favored by a population.
We propose two $\delta$-PAC algorithms for ROAI, which includes the first
UCB-style algorithm for outlier detection, and derive upper bounds on their
sample complexity. We also prove a matching, up to logarithmic factors, worst
case lower bound for the problem, indicating that our upper bounds are
generally unimprovable. Experimental results show that our algorithms are both
robust and about $5$x sample efficient compared to state-of-the-art.
