  Bayesian optimization is a technique for efficiently optimizing unknown
functions in a black-box manner. To handle practical settings where gathering
data requires use of finite resources, it is desirable to explicitly
incorporate function evaluation costs into Bayesian optimization policies. To
understand how to do so, we develop a previously-unexplored connection between
cost-aware Bayesian optimization and the Pandora's Box problem, a decision
problem from economics. The Pandora's Box problem admits a Bayesian-optimal
solution based on an expression called the Gittins index, which can be
reinterpreted as an acquisition function. We study the use of this acquisition
function for cost-aware Bayesian optimization, and demonstrate empirically that
it performs well, particularly in medium-high dimensions. We further show that
this performance carries over to classical Bayesian optimization without
explicit evaluation costs. Our work constitutes a first step towards
integrating techniques from Gittins index theory into Bayesian optimization.
