Extreme bandits
In many areas of medicine, security, and life sciences, we want to allocate limited resources to different sources in order to detect extreme values. In this paper, we study an efficient way to allocate these resources sequentially under limited feedback. While sequential design of experiments is well studied in bandit theory, the most commonly optimized property is the regret with respect to the maximum mean reward. However, in other problems such as network intrusion detection, we are interested in detecting the most extreme value output by the sources. Therefore, in our work we study extreme regret which measures the efficiency of an algorithm compared to the oracle policy selecting the source with the heaviest tail. We propose the EXTREMEHUNTER algorithm, provide its analysis, and evaluate it empirically on synthetic and real-world experiments.
This paper formulates an “extreme bandit” problem. An algorithm sequentially samples from among K distributions with the goal of observing a very extreme (i.e. large) realization. They propose a UCB-type algorithm for this problem, and establish a bound on its “extreme regret.”  This bound grows more slowly with the time horizon than the expected value of the most extreme observations of the optimal action, which implies that the algorithm concentrates on the best action asymptotically. This paper generalizes and strengthens prior results provided by [9,21]. The full parametric assumptions made in those works are replaced by more general assumptions about the tail behavior of reward distributions. In addition, this paper provides finite time rather than asymptotic guarantees. These are valuable extensions, but they feel like incremental progress. I think the paper is slightly below the acceptance threshold.I don’t find the motivation given in the introduction to be completely satisfying (see below), but in spite of this, it’s possible that there are many very important applications of these techniques with which I am not familiar. (Obviously anomaly detection is very important.)  I am somewhat uncertain of my review for this reason. Mathematical statements in the paper should be more carefully organized and presented in a clearer way. Section 5 tries to simultaneously define the algorithm and introduce a variety of constants that will be used in the theoretical analysis. I recommend defining the algorithm in a clear, self-contained way. You can move some analysis to the appendix if you need more space. Assumptions should be given in the problem formulation, or clearly set aside so the reader can keep track of them. Instead, a key technical assumption is added in the text in lines 213-215. It’s hard to track down all the constant terms, some of which are given only by looking at the paper [6] (right?). Further comments- By studying extreme regret, the paper does not precisely focus on identifying the distribution with the heaviest tails so much as on observing large realized values. Obviously these are related objectives, but they are not the same. Why choose to focus on extreme regret?- What are some natural examples where (1) the goal is to find extreme observations, (2) bandit feedback is a clear obstacle, (3) adaptive sampling is feasible, and (4) observations are costly enough that it’s worth designing very smart sampling schemes. - In the experiments, which estimator for h_{k,t} did you use?- The experimental results are averaged over only 100 trials, which seems particularly low given the focus on rare events. You should either increase the number of trials, or include some measure of the variability in the estimates. - Much of the motivation is that past work makes parametric assumptions that are too restrictive to be practical. It would be nice if the experiments then demonstrated the practical benefit of instead considering a semi-parametric approach.