Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs: Supplementary Material

The approximation ratios provided by the EI and EI-PUC policies are unbounded. We prove the result in two parts, first focusing on EI-PUC, and then on EI. To show the result for EI-PUC, we construct a problem instance with a discrete finite domain and no observation noise. One feasible policy for the problem is to "measure the high-variance point once." Let us consider the EI-PUC policy.