# TS-RSR: A provably efficient approach for batch Bayesian Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 7 Mar 2024.

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

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [Batch Bayesian Optimization via Local Penalization](https://mlsanity.com/paper/1505.08052/) (2015)
- [Constrained Bayesian Optimization with Noisy Experiments](https://mlsanity.com/paper/1706.07094/) (2017)
- [Federated Bayesian Optimization via Thompson Sampling](https://mlsanity.com/paper/2010.10154/) (2020)
- [Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space](https://mlsanity.com/paper/1706.01825/) (2017)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Joint Entropy Search for Maximally-Informed Bayesian Optimization](https://mlsanity.com/paper/2206.04771/) (2022)
- [Predictive Entropy Search for Bayesian Optimization with Unknown Constraints](https://mlsanity.com/paper/1502.05312/) (2015)
- [Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration](https://mlsanity.com/paper/1304.5350/) (2013)
- [Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions](https://mlsanity.com/paper/1511.07130/) (2015)
- [Predictive Entropy Search for Multi-objective Bayesian Optimization with Constraints](https://mlsanity.com/paper/1609.01051/) (2016)
- [Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes](https://mlsanity.com/paper/2110.11665/) (2021)
- [Optimization as Estimation with Gaussian Processes in Bandit Settings](https://mlsanity.com/paper/1510.06423/) (2015)
- [On Batch Bayesian Optimization](https://mlsanity.com/paper/1911.01032/) (2019)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Fully Distributed Bayesian Optimization with Stochastic Policies](https://mlsanity.com/paper/1902.09992/) (2019)
- [SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spaces](https://mlsanity.com/paper/2301.11832/) (2023)
- [Gaussian Max-Value Entropy Search for Multi-Agent Bayesian Optimization](https://mlsanity.com/paper/2303.05694/) (2023)
- [TS-UCB: Improving on Thompson Sampling With Little to No Additional Computation](https://mlsanity.com/paper/2006.06372/) (2020)
- [Sampling Acquisition Functions for Batch Bayesian Optimization](https://mlsanity.com/paper/1903.09434/) (2019)

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

- [Batched Bayesian optimization by maximizing the probability of including the optimum](https://mlsanity.com/paper/2410.06333/) (2024)
- [Distributed Thompson sampling under constrained communication](https://mlsanity.com/paper/2410.15543/) (2024)
- [D-IMPL: A Diffusion-based Solver for Parameterized BBOs](https://mlsanity.com/paper/2609.22752/) (2026)
- [Collaborative Principle Evolution via Evidence Transfer for Scientific Discovery](https://mlsanity.com/paper/2609.35315/) (2026)

## Abstract (arXiv)

This paper presents a new approach for batch Bayesian Optimization (BO) called Thompson Sampling-Regret to Sigma Ratio directed sampling (TS-RSR), where we sample a new batch of actions by minimizing a Thompson Sampling approximation of a regret to uncertainty ratio. Our sampling objective is able to coordinate the actions chosen in each batch in a way that minimizes redundancy between points whilst focusing on points with high predictive means or high uncertainty. Theoretically, we provide rigorous convergence guarantees on our algorithm's regret, and numerically, we demonstrate that our method attains state-of-the-art performance on a range of challenging synthetic and realistic test functions, where it outperforms several competitive benchmark batch BO algorithms.