Improving the Expected Improvement Algorithm
The expected improvement (EI) algorithm is a popular strategy for information collection in optimization under uncertainty. The algorithm is widely known to be too greedy, but nevertheless enjoys wide use due to its simplicity and ability to handle uncertainty and noise in a coherent decision theoretic framework. To provide rigorous insight into EI, we study its properties in a simple setting of Bayesian optimization where the domain consists of a finite grid of points. This is the so-called best-arm identification problem, where the goal is to allocate measurement effort wisely to confidently identify the best arm using a small number of measurements. In this framework, one can show formally that EI is far from optimal. To overcome this shortcoming, we introduce a simple modification of the expected improvement algorithm. Surprisingly, this simple change results in an algorithm that is asymptotically optimal for Gaussian best-arm identification problems, and provably outperforms standard EI by an order of magnitude.
The authors propose a new best arm identification algorithm called TTEI that is an extension of "expected improvement" (EI), a known heuristic from the Bayesian optimization community. The motivation for the extension is to match the asymptotic optimalities (rate of posterior convergence & expected stopping time), which are important properties of an algorithm. The authors analyze the asymptotic property of TTEI, show its (near)-optimality, and present its superior empirical performance in synthetic datasets.
Overall, well-written paper on an interesting problem. I highly rate the novelty of the algorithm. On the other hand, the asymptotic guarantee often does not capture the reality well in my opinion (described later, though I think this isn't a reason for rejection). I think the experiment part is the weakest in that they do not describe how and why their algorithm work better. Also, I would like to see how much TTEI behaves differently from TTTS since they share many asymptotic properties. This was not captured in the experiments.
Question on the rate of posterior convergence: The authors claim at line 97 that the analysis takes place in a frequentist setting. That is true, but isn't the analysis on posterior convergence essentially on the posterior probability "computed by the algorithm"? Sure, we can talk about a quantity that is computed by the algorithm, but if one considers a frequentist setting then what is the meaning of Theorem 2 and how it is solving the problem in the frequentist setting? That is, shouldn't one also talk about what it means to have (1-\alpha_{n,1}) approach to 0 in the frequentist setting?
One weakness would be that the guarantee is limited to Gaussian (unlike other papers like the lil' ucb paper that applies to sub-Gaussian RVs), so it does not apply to bernoulli case that is very popular in practice. I wonder if one can relax the random variables to be sub-Gaussian whose scale parameter is bounded below a known constant. What is the authors' opinion on this? I wonder if there are critical steps in the proof that works for Guassian but not for generic sub-Gaussian.
Any moderate-confidence regime results? Recent analysis on the top arm identification (such as Chen and Li On the Optimal Sample Complexity for Best Arm Identification, 2016) tells us that there are some important terms that does not depend on \log(1/\dt), so there might be some practically relevant terms the asymptotic analysis is missing. I appreciate the asymptotic optimality, but what happens in practice is that no one wants to use \delta that is too small and in most cases \log(1/\delta) can be treated as constants in the set of problems we care about. I also wonder whether this fact can affect the practical performance.
Still, I like to emphasize that I don't think the lack of non-asymptotic analysis should be the reason for rejection in any ways as such analysis is often hard and I believe people should go beyond that to explore new algorithms.
Could you provide a more detailed comparison between Russo'16? Are there any difference in the asymptotic optimality? Any different sampling behavior that one can observe in practice?
Below L194, why do we need |mu_n,i - \mu_i| \le \epsilon there? If so, what is the key mathematical reason for that? (or, is it for convenience of mathematical derivation?) As far as intuition goes, it seems like if N is large and the sampling proportion is controlled, then one should be able to control |mu_n,i - \mu_i|. Let me know what the authors think.
In experiments, why do we use "max_i \alpha_{n,i} \ge c" as the stopping criterion? I thought the good stopping criterion is the one from Garivier & Kaufmann. How is this stopping rule used for the experiments justified in the frequentist setting? Also, I think the authors must have compared the actual probability of misidentification, especially as a graph in P(misid.) vs the # of samples, which measures 'anytime' performance that I think is practically relevant. Could the authors comment on this?
Also, I was expecting the reason why we see RSO works worse than TTEI. 
L274: f => of
L219: allocation => allocate
L260: guarantees -> guarantee
L294: what is the definition of the bold-faced numbers in Table 2? Does that coloring involves some statistical significancy test?