# Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2019.

## Built on by (most cited first, 30 of 51)

- [Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges](https://mlsanity.com/paper/2107.05847/) (2021)
- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Pareto Set Learning for Expensive Multi-Objective Optimization](https://mlsanity.com/paper/2210.08495/) (2022)
- [When Large Language Models Meet Evolutionary Algorithms: Potential Enhancements and Challenges](https://mlsanity.com/paper/2401.10510/) (2024)
- [Multi-fidelity Bayesian Optimization: A Review](https://mlsanity.com/paper/2311.13050/) (2023)
- [Revisiting Bayesian Optimization in the light of the COCO benchmark](https://mlsanity.com/paper/2103.16649/) (2021)
- [LLaMEA-BO: A Large Language Model Evolutionary Algorithm for Automatically Generating Bayesian Optimization Algorithms](https://mlsanity.com/paper/2505.21034/) (2025)
- [A portfolio approach to massively parallel Bayesian optimization](https://mlsanity.com/paper/2110.09334/) (2021)
- [Bayesian Optimization-based Combinatorial Assignment](https://mlsanity.com/paper/2208.14698/) (2022)
- [Epsilon-Greedy Thompson Sampling to Bayesian Optimization](https://mlsanity.com/paper/2403.00540/) (2024)
- [Exploring Exploration in Bayesian Optimization](https://mlsanity.com/paper/2502.08208/) (2025)
- [Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation](https://mlsanity.com/paper/2410.16893/) (2024)
- [CLEAR: Calibrated Learning for Epistemic and Aleatoric Risk](https://mlsanity.com/paper/2507.08150/) (2025)
- [How Bayesian Should Bayesian Optimisation Be?](https://mlsanity.com/paper/2105.00894/) (2021)
- [MBORE: Multi-objective Bayesian Optimisation by Density-Ratio Estimation](https://mlsanity.com/paper/2203.16912/) (2022)
- [Towards Futuristic Autonomous Experimentation--A Surprise-Reacting Sequential Experiment Policy](https://mlsanity.com/paper/2112.00600/) (2021)
- [Mastering the exploration-exploitation trade-off in Bayesian Optimization](https://mlsanity.com/paper/2305.08624/) (2023)
- [Multi-objective optimisation via the R2 utilities](https://mlsanity.com/paper/2305.11774/) (2023)
- [Bayesian Optimisation Against Climate Change: Applications and Benchmarks](https://mlsanity.com/paper/2306.04343/) (2023)
- [Accelerating material discovery with a threshold-driven hybrid acquisition policy-based Bayesian optimization](https://mlsanity.com/paper/2311.09591/) (2023)
- [A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization](https://mlsanity.com/paper/2501.18756/) (2025)
- [Deterministic Global Optimization of the Acquisition Function in Bayesian Optimization: To Do or Not To Do?](https://mlsanity.com/paper/2503.03625/) (2025)
- [PyRelationAL: a python library for active learning research and development](https://mlsanity.com/paper/2205.11117/) (2022)
- [A Parallel Technique for Multi-objective Bayesian Global Optimization: Using a Batch Selection of Probability of Improvement](https://mlsanity.com/paper/2208.03685/) (2022)
- [Batched Energy-Entropy acquisition for Bayesian Optimization](https://mlsanity.com/paper/2410.08804/) (2024)
- [Wasserstein Barycenter Gaussian Process based Bayesian Optimization](https://mlsanity.com/paper/2505.12471/) (2025)
- [CoTune: Co-evolutionary Configuration Tuning](https://mlsanity.com/paper/2509.24694/) (2025)
- [Uncertainty quantification and exploration-exploitation trade-off in humans](https://mlsanity.com/paper/2102.07647/) (2021)
- [Automated Machine Learning for Positive-Unlabelled Learning](https://mlsanity.com/paper/2401.06452/) (2024)
- [Variational Entropy Search for Adjusting Expected Improvement](https://mlsanity.com/paper/2402.11345/) (2024)

## Abstract (arXiv)

The performance of acquisition functions for Bayesian optimisation to locate the global optimum of continuous functions is investigated in terms of the Pareto front between exploration and exploitation. We show that Expected Improvement (EI) and the Upper Confidence Bound (UCB) always select solutions to be expensively evaluated on the Pareto front, but Probability of Improvement is not guaranteed to do so and Weighted Expected Improvement does so only for a restricted range of weights. We introduce two novel ε-greedy acquisition functions. Extensive empirical evaluation of these together with random search, purely exploratory, and purely exploitative search on 10 benchmark problems in 1 to 10 dimensions shows that ε-greedy algorithms are generally at least as effective as conventional acquisition functions (e.g., EI and UCB), particularly with a limited budget. In higher dimensions ε-greedy approaches are shown to have improved performance over conventional approaches. These results are borne out on a real world computational fluid dynamics optimisation problem and a robotics active learning problem. Our analysis and experiments suggest that the most effective strategy, particularly in higher dimensions, is to be mostly greedy, occasionally selecting a random exploratory solution.