# Practical Bayesian Algorithm Execution via Posterior Sampling

arXiv: https://arxiv.org/abs/2410.20596 · HTML: https://mlsanity.com/paper/2410.20596/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 48 references that are in the map.
- First posted on arXiv 27 Oct 2024.

## Builds on (most cited first, 29 of 29)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Federated Bayesian Optimization via Thompson Sampling](https://mlsanity.com/paper/2010.10154/) (2020)
- [Pathwise Conditioning of Gaussian Processes](https://mlsanity.com/paper/2011.04026/) (2020)
- [Adversarially Robust Optimization with Gaussian Processes](https://mlsanity.com/paper/1810.10775/) (2018)
- [Joint Entropy Search for Maximally-Informed Bayesian Optimization](https://mlsanity.com/paper/2206.04771/) (2022)
- [Bayesian Optimization of Risk Measures](https://mlsanity.com/paper/2007.05554/) (2020)
- [Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information](https://mlsanity.com/paper/2104.09460/) (2021)
- [On the Performance of Thompson Sampling on Logistic Bandits](https://mlsanity.com/paper/1905.04654/) (2019)
- [Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization](https://mlsanity.com/paper/2006.11267/) (2020)
- [Bayesian Active Learning with Fully Bayesian Gaussian Processes](https://mlsanity.com/paper/2205.10186/) (2022)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [A supermartingale approach to Gaussian process based sequential design of experiments](https://mlsanity.com/paper/1608.01118/) (2016)
- [Bayesian Quadrature for Multiple Related Integrals](https://mlsanity.com/paper/1801.04153/) (2018)
- [Posterior Sampling for Deep Reinforcement Learning](https://mlsanity.com/paper/2305.00477/) (2023)
- [Robust Super-Level Set Estimation using Gaussian Processes](https://mlsanity.com/paper/1811.09977/) (2018)
- [Probabilistic Numerical Method of Lines for Time-Dependent Partial Differential Equations](https://mlsanity.com/paper/2110.11847/) (2021)
- [DiscoBAX: Discovery of Optimal Intervention Sets in Genomic Experiment Design](https://mlsanity.com/paper/2312.04064/) (2023)
- [Probabilistic Solutions to Differential Equations and their Application to Riemannian Statistics](https://mlsanity.com/paper/1306.0308/) (2013)
- [Evaluating Gaussian Process Metamodels and Sequential Designs for Noisy Level Set Estimation](https://mlsanity.com/paper/1807.06712/) (2018)
- [SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spaces](https://mlsanity.com/paper/2301.11832/) (2023)

## Built on by (most cited first, 2 of 2)

- [Efficient Nudged Elastic Band Method using Neural Network Bayesian Algorithm Execution](https://mlsanity.com/paper/2512.14993/) (2025)
- [NeuronSifter: An Agent-in-Twin for Prioritizing Central Nervous System Interventions with World Action Models](https://mlsanity.com/paper/2609.35445/) (2026)

## Abstract (arXiv)

We consider Bayesian algorithm execution (BAX), a framework for efficiently selecting evaluation points of an expensive function to infer a property of interest encoded as the output of a base algorithm. Since the base algorithm typically requires more evaluations than are feasible, it cannot be directly applied. Instead, BAX methods sequentially select evaluation points using a probabilistic numerical approach. Current BAX methods use expected information gain to guide this selection. However, this approach is computationally intensive. Observing that, in many tasks, the property of interest corresponds to a target set of points defined by the function, we introduce PS-BAX, a simple, effective, and scalable BAX method based on posterior sampling. PS-BAX is applicable to a wide range of problems, including many optimization variants and level set estimation. Experiments across diverse tasks demonstrate that PS-BAX performs competitively with existing baselines while being significantly faster, simpler to implement, and easily parallelizable, setting a strong baseline for future research. Additionally, we establish conditions under which PS-BAX is asymptotically convergent, offering new insights into posterior sampling as an algorithm design paradigm.