Practical Bayesian Algorithm Execution via Posterior Sampling

Abstract

We consider the Bayesian algorithm execution framework, where the goal is to select points for evaluating an expensive function to best infer a property of interest. By making the key observation that the property of interest for many tasks is a target set of points defined in terms of the function, we derive a simple yet effective and scalable posterior sampling algorithm, termed PS-BAX. Our approach addresses a broad range of problems, including many optimization variants and level-set estimation. Experiments across a diverse set of tasks show that PS-BAX achieves competitive performance against standard baselines, while being significantly faster, simpler to implement, and easily parallelizable. In addition, we show that PS-BAX is asymptotically consistent under mild regularity conditions. Consequently, our work yields new insights into posterior sampling, broadening its application scope and providing a strong baseline for future exploration.