  Bayesian optimization (BO) is a popular method for optimizing
expensive-to-evaluate black-box functions. BO budgets are typically given in
iterations, which implicitly assumes each evaluation has the same cost. In
fact, in many BO applications, evaluation costs vary significantly in different
regions of the search space. In hyperparameter optimization, the time spent on
neural network training increases with layer size; in clinical trials, the
monetary cost of drug compounds vary; and in optimal control, control actions
have differing complexities. Cost-constrained BO measures convergence with
alternative cost metrics such as time, money, or energy, for which the sample
efficiency of standard BO methods is ill-suited. For cost-constrained BO, cost
efficiency is far more important than sample efficiency. In this paper, we
formulate cost-constrained BO as a constrained Markov decision process (CMDP),
and develop an efficient rollout approximation to the optimal CMDP policy that
takes both the cost and future iterations into account. We validate our method
on a collection of hyperparameter optimization problems as well as a sensor set
selection application.
