On Thompson Sampling and Bilateral Uncertainty in Additive Bayesian Optimization

Nathan WycoffarXiv 2025 · DOI · arXiv

In Bayesian Optimization (BO), high-dimensional search spaces present a significant challenge. As dimensionality increases, the volume of the search space grows exponentially, making accurate modeling of the objective function difficult. A common mitigation strategy is Additive BO, which assumes the objective function $f(x)$ can be decomposed into a sum of lower-dimensional sub-functions: $f(x) = \sum_{i=1}^M f_i(x_i)$.

The Challenge of Bilateral Uncertainty

While the additive assumption simplifies the mean of the Gaussian Process (GP) surrogate, it complicates the uncertainty modeling. Because we only observe the total sum of the sub-functions, the individual components $f_i$ become statistically coupled. This correlation is known as Bilateral Uncertainty (BU).

Most existing Additive BO frameworks ignore BU to maintain computational tractability, treating sub-functions as independent during the acquisition phase. This research investigates whether accounting for these correlations—untangling the sub-functions—leads to better optimization performance.

Methodology: Exact vs. Approximate Sampling

The research focuses on Thompson Sampling (TS), an acquisition rule where a function is drawn from the posterior and minimized to find the next sample point. Two primary approaches are compared:

  1. Exact Method (ts): Uses an autoregressive sampling scheme that respects BU by conditioning each sub-function sample on the residuals of the others. This method is computationally efficient, with a complexity of $O(M(N + B^*)^3)$.
  2. Approximate Method (ats): The standard baseline that ignores BU, sampling each sub-function independently from its marginal posterior.
Comparison of predictive mean, variance, and posterior draws for Bilateral vs. Additive models. Note how bilateral variance "vanishes" more effectively near sampled points (red dots).

As visualized above, accounting for bilateral uncertainty significantly alters the predictive variance and the resulting posterior draws. Theoretically, the exact method provides a more faithful representation of the search space, which should lead to a better exploration-exploitation trade-off.

Empirical Findings

The methods were evaluated across 15 test functions, ranging from synthetic benchmarks (Ackley, Rastrigin) to complex simulators like Robot Push (14D) and cosmological inference problems (up to 25D).

The results yielded a surprising insight: despite the mathematical elegance and theoretical superiority of the exact method, the approximate method performs nearly as well in practice. Across 1,500 trials, the exact method showed only a slight statistical edge in sequential sampling, which vanished entirely in batch settings (batch size 10). The extra information provided by bilateral uncertainty is often drowned out by general noise and model mismatch inherent in BO.

Conclusion

The study concludes that while bilateral uncertainty is a real phenomenon in additive modeling, the common practice of ignoring it is "sufficient for BO in practice," even with small evaluation budgets. For practitioners, this suggests that simpler, independent sampling methods remain a robust and computationally efficient choice for high-dimensional additive optimization.

Summary updated

Abstract

In Bayesian Optimization (BO), additive assumptions can mitigate the twin difficulties of modeling and searching a complex function in high dimension. However, common acquisition functions, like the Additive Lower Confidence Bound, ignore pairwise covariances between dimensions, which we'll call \textit{bilateral uncertainty} (BU), imposing a second layer of approximations. While theoretical results indicate that asymptotically not much is lost in doing so, little is known about the practical effects of this assumption in small budgets. In this article, we show that by exploiting conditional independence, Thompson Sampling respecting BU can be efficiently conducted. We use this fact to execute an empirical investigation into the loss incurred by ignoring BU, finding that the additive approximation to Thompson Sampling does indeed have, on balance, worse performance than the exact method, but that this difference is of little practical significance. This buttresses the theoretical understanding and suggests that the BU-ignoring approximation is sufficient for BO in practice, even in the non-asymptotic regime.
BibTeX
@misc{wycoff2025thompson,
  author = {Nathan Wycoff},
  title = {{On Thompson Sampling and Bilateral Uncertainty in Additive Bayesian Optimization}},
  year = {2025},
  eprint = {2510.11792},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.11792},
}
Figure