No-Regret Bayesian Optimization with Stochastic Observation Failures

Shogo Iwazaki, Tomohiko Tanabe, Mitsuru Irie, Shion Takeno, Kota Matsui, Yu InatsuAISTATS 2025 · OpenReview

Abstract

We study Bayesian optimization problems where observation of the objective function fails stochastically, e.g., synthesis failures in materials development. For this problem, although several heuristic methods have been proposed, they do not have theoretical guarantees and sometimes deteriorate in practice. We propose two algorithms that have a trade-off relation between regret bounds and practical performance. The first one is the first no-regret algorithm for this problem. The second one shows superior practical performance; however, we need some modification of the algorithm to obtain a no-regret guarantee, which is slightly worse than the first one. We demonstrate the effectiveness of our methods in numerical experiments, including the simulation function motivated by quasi-crystal synthesis.

Introduction

In standard Bayesian Optimization (BO), it is typically assumed that every query at a point $x$ yields a noisy observation of the objective function $f(x)$. However, real-world applications often involve stochastic observation failures. For instance, in chemical synthesis, a specific composition might fail to produce a measurable sample, or in robotics, a trial might terminate prematurely due to a hardware failure.

When the probability of success $g(x)$ is unknown and varies across the search space, standard BO algorithms often fail to converge. If an algorithm repeatedly queries a point with a high failure probability, it may fail to gather sufficient information about the objective function, leading to linear regret. This paper addresses this gap by introducing the first algorithms with theoretical "no-regret" guarantees for environments with stochastic failures.

Proposed Algorithms

The authors propose two novel algorithms to handle unknown success probabilities:

  1. SF-GP-UCB (Stochastic Failure-aware GP-UCB): This algorithm maintains Gaussian Process (GP) models for both the objective function $f(x)$ and the success probability $g(x)$. It restricts its search to a "super-level set" where the success probability is likely above a threshold $h_t$. By adaptively decaying this threshold over time, the algorithm ensures it eventually explores riskier regions while maintaining a sub-linear regret bound.
  2. SF-CBI (Stochastic Failure-aware Confidence Bound-based Improvement): While SF-GP-UCB provides strong theoretical guarantees, it can be overly conservative in early iterations. SF-CBI utilizes a multiplicative acquisition function that balances potential improvement in $f(x)$ with the estimated probability of success $g(x)$. This approach allows for more fluid exploration and typically yields better practical performance in finite-step scenarios.
Comparison of SF-GP-UCB and SF-CBI query strategies over multiple steps. SF-GP-UCB (top) remains focused on high-confidence regions, while SF-CBI (bottom) explores more dynamically.

Key Insights and Theoretical Contributions

The core challenge in stochastic failure settings is the "stuck" problem: standard algorithms like GP-UCB do not update their belief about the objective function when an observation fails. Consequently, if a point is perceived as optimal but has a 0% success rate, the algorithm might query it indefinitely.

The theoretical breakthrough in this work is the use of adaptive thresholding. By starting with a conservative success threshold and slowly lowering it, the algorithm guarantees it will collect enough successful observations to converge to the true optimum. The authors prove that SF-GP-UCB achieves sub-linear regret, a first for this problem class.

Experimental Evaluation

The algorithms were evaluated against synthetic benchmarks and a high-fidelity simulation of quasi-crystal synthesis (Al-Cu-Mn alloys). In the quasi-crystal task, the goal is to maximize phonon thermal conductivity despite uncontrollable experimental errors that lead to synthesis failures.

Regret performance of proposed algorithms against standard BO baselines across synthetic benchmarks. SF-CBI and SF-GP-UCB consistently outperform heuristic methods.

Empirical results demonstrate that SF-CBI and SF-GP-UCB consistently outperform existing heuristics like EFIGPC and PenalizedEI. Specifically, SF-CBI shows superior performance in early iterations, while SF-GP-UCB provides the robustness promised by its theoretical foundations.

Conclusion

This work provides a rigorous framework for Bayesian Optimization under stochastic failures. By balancing the search for high objective values with the probability of successful observation, the proposed SF-GP-UCB and SF-CBI algorithms offer both theoretical reliability and practical efficiency. Future research may explore the fundamental limits of regret rates in these settings and address the computational scaling of GP-based methods for long-horizon experiments.

Summary updated

Abstract

We study Bayesian optimization problems where observation of the objective function fails stochastically, e.g., synthesis failures in materials development. For this problem, although several heuristic methods have been proposed, they do not have theoretical guarantees and sometimes deteriorate in practice. We propose two algorithms that have a trade-off relation between regret bounds and practical performance. The first one is the first no-regret algorithm for this problem. The second one shows superior practical performance; however, we need some modification of the algorithm to obtain a no-regret guarantee, which is slightly worse than the first one. We demonstrate the effectiveness of our methods in numerical experiments, including the simulation function motivated by quasi-crystal synthesis.
BibTeX
@inproceedings{iwazaki2025no,
  author = {Shogo Iwazaki and Tomohiko Tanabe and Mitsuru Irie and Shion Takeno and Kota Matsui and Yu Inatsu},
  title = {{No-Regret Bayesian Optimization with Stochastic Observation Failures}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=IEHddwHTIx},
}
Figure