To overcome the shortcomings of existing approaches, we propose the budgeted multi-step expected improvement, a non-myopic acquisition function that generalizes classical expected improvement to the setting of heterogeneous and unknown evaluation costs.

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.