  In many real-world problems, we want to infer some property of an expensive
black-box function $f$, given a budget of $T$ function evaluations. One example
is budget constrained global optimization of $f$, for which Bayesian
optimization is a popular method. Other properties of interest include local
optima, level sets, integrals, or graph-structured information induced by $f$.
Often, we can find an algorithm $\mathcal{A}$ to compute the desired property,
but it may require far more than $T$ queries to execute. Given such an
$\mathcal{A}$, and a prior distribution over $f$, we refer to the problem of
inferring the output of $\mathcal{A}$ using $T$ evaluations as Bayesian
Algorithm Execution (BAX). To tackle this problem, we present a procedure,
InfoBAX, that sequentially chooses queries that maximize mutual information
with respect to the algorithm's output. Applying this to Dijkstra's algorithm,
for instance, we infer shortest paths in synthetic and real-world graphs with
black-box edge costs. Using evolution strategies, we yield variants of Bayesian
optimization that target local, rather than global, optima. On these problems,
InfoBAX uses up to 500 times fewer queries to $f$ than required by the original
algorithm. Our method is closely connected to other Bayesian optimal
experimental design procedures such as entropy search methods and optimal
sensor placement using Gaussian processes.
