Identifying Outlier Arms in Multi-Armed Bandit *
We study a novel problem lying at the intersection of two areas: multi-armed bandit and outlier detection. Multi-armed bandit is a useful tool to model the process of incrementally collecting data for multiple objects in a decision space. Outlier detection is a powerful method to narrow down the attention to a few objects after the data for them are collected. However, no one has studied how to detect outlier objects while incrementally collecting data for them, which is necessary when data collection is expensive. We formalize this problem as identifying outlier arms in a multi-armed bandit. We propose two sampling strategies with theoretical guarantee, and analyze their sampling efficiency. Our experimental results on both synthetic and real data show that our solution saves 70-99% of data collection cost from baseline while having nearly perfect accuracy.
This work is concerned with a variant of the multi-armed bandit problem, and more specifically a pure exploration, fixed confidence problem. Here, the objective is to identify with probability at least 1-\delta the arms that are over a threshold, using as few samples as possible. The twist, compared to a setting introduced in [1], is that this threshold is not known a priori by the learner, and instead depends on the means of the arms (unknown to the learner) and an outlier parameter k (known to the learner). With respect to the existing literature, this game can be seen as a pure exploration bandit problem with a double exploration trade-off: first, pulling arms in a balanced way as to estimate each mean to improve the estimate of the (unknown) threshold \hat \theta and second, pulling arms whose means are close to \hat \theta in order to determine whether they belong to the set of outliers. If \theta were known to the learner, it is well understood that one would require roughly 1/(y_i - \theta)^2 samples to determine to which set arm i belongs. To solve this problem, two algorithms are introduced. The first one is a simple uniform exploration algorithm, that comes down to a test (making use of confidence intervals on the estimated threshold and means) as to discover which arms are outliers with high probability. The second algorithm is a distorted version of this algorithm, which overpulls (with respect to the uniform sampling) arms that are still active (i.e. we have not yet identified in which set they belong). The analysis shows that careful tuning of this distortion parameter \rho leads to improved performances over the uniform sampling algorithm. The tuning of this parameter with respect to the complexity measures H_1 (worst case complexity) and H_2 (which is similar to the usual complexity measure in pure exploration problems) is discussed. Extensive experiments are conducted to validate the theoretical results, on both a synthetic and real dataset.
I believe there is a typo in the definition of \sigma_y (there should be a sum). Some references are missing see e.g. [1] and [2,3]. In [2,3] the objective is to estimate as well as possible all the means. On the other hand [1] introduced the thresholding bandit problem. Though the lower-bound construction therein does not apply trivially (it is harder to construct problems for the lower-bound given all the interdependencies between the means in this setting), in spirit the complexity terms seem very related, as one should not expect to have a complexity for this problem lower than H_2 (as defined in this work). It would be interesting to see an even more adaptive strategy to tackle this problem, maybe with a different definition for the (problem dependent) threshold if this one proves too difficult for natural adaptivity. I don’t understand the 99% claim in the abstract, you should tone it down or explain it better in the experiments section. 
Regarding the experiments, I believe that \delta should be set to a much lower value (0.01) and correspondingly they should be repeated at least 1000 times (even if \delta is not changed, experiments should be averaged over many more than 10 runs). I believe that an interesting baseline could be one where the threshold is given a priori to the learner, and it can simply successively accept or reject arms with confidence parameter \delta/n (to account for the union bound). This strategy should be the hardest baseline (which we don’t expect to beat, but it shows the possible improvement).  Some further: they could be repeated with different values of \rho, and the \rho parameter used here should be discussed. It would be interesting to see how the “worst-case” \rho parameter as described in (6) performs against a perfectly tuned \rho, on different problems. The synthetic experiments could be run instead on carefully crafted instances that correspond to different extreme problems.
Overall, I believe this new problem is well motivated, and the two algorithms introduced are natural strategies to tackle this problem which should serve as strong baselines for future work. The paper is written in a very clear and clean fashion, and it is easy to follow. One weakness is that the algorithms and techniques used are rather basic as the problem itself is hard to tackle. Moreover, a fixed budget transposition of the setting seems like challenging problem to solve in the future.
[1] Locatelli, Andrea, Maurilio Gutzeit, and Alexandra Carpentier. "An optimal algorithm for the thresholding bandit problem." Proceedings of the 33rd International Conference on International Conference on Machine Learning-Volume 48. JMLR. org, 2016.
[2] Carpentier, Alexandra, A Lazaric, M Ghavamzadeh, R Munos, Peter Auer
 "Upper-confidence-bound algorithms for active learning in multi-armed bandits." International Conference on Algorithmic Learning Theory. Springer, Berlin, Heidelberg, 2011.
[3] Antos, A., Grover, V., Szepesvári, C.: Active learning in heteroscedastic noise. Theoretical Computer Science 411, 2712–2728 (2010)