qPOTS: Efficient Batch Multiobjective Bayesian Optimization via Pareto Optimal Thompson Sampling

AISTATS 2025

TL;DR

This paper introduces qPOTS, a novel Bayesian optimization (BO) approach for efficiently finding optimal solutions in problems with multiple, expensive-to-evaluate objectives. By leveraging Pareto optimal Thompson sampling and a cheap evolutionary optimization on GP posteriors, qPOTS achieves superior sample efficiency and handles constraints and batch acquisitions more effectively than existing methods.

What Problem Does This Paper Address?

Many real-world problems involve optimizing several objectives simultaneously, where evaluating each objective is costly (e.g., running complex simulations or experiments). Classical evolutionary algorithms can find good solutions but require a vast number of evaluations, making them impractical. Bayesian Optimization (BO) offers a sample-efficient alternative by building surrogate models (typically Gaussian Processes or GPs) of the objectives and intelligently selecting the next points to evaluate. However, extending BO to multiple objectives (MOBO) introduces a significant challenge: optimizing the "acquisition function" – a function that guides where to sample next – becomes computationally very hard, especially when acquiring multiple points at once (batch sampling). This difficulty hinders the sample efficiency of existing MOBO methods, particularly when dealing with complex objective landscapes or constraints.

Methods

The core innovation of qPOTS lies in its adaptation of Thompson Sampling (TS) for the multiobjective setting. Instead of selecting points based on the probability of being the optimal solution (as in single-objective TS), qPOTS selects points based on their probability of being Pareto optimal. This is achieved by:

  1. GP Surrogates: Fitting independent GP models for each of the K objectives.
  2. Pareto Optimal Thompson Sampling: Drawing sample paths from the posterior GPs and then solving a cheap multiobjective optimization problem on these sampled paths using evolutionary algorithms (like NSGA-II). This yields a set of candidate Pareto optimal points for the sampled paths.
  3. Batch Acquisition with Maximin Distance: To select a batch of q points, qPOTS uses a maximin distance criterion to ensure diversity among the chosen candidates, promoting exploration.
  4. Constraint Handling: The method seamlessly extends to constrained optimization by fitting GPs for the constraints as well and incorporating them into the evolutionary optimization step.
  5. Nyström Approximation: For high-dimensional problems, qPOTS employs a Nyström approximation to speed up the computation of GP posteriors without significant loss of accuracy.

Datasets

The paper evaluates qPOTS on a variety of synthetic and real-world datasets:

Synthetic Experiments: * Branin-Currin * ZDT3 (known for disjoint Pareto frontiers) * DTLZ3 * DTLZ7 * OSY problem (constrained, 6 constraints)

Real-world Experiments: * Vehicle Safety problem * Penicillin production problem * Car side-impact problem

The authors do not introduce new benchmarks but use established test functions and problems to compare against state-of-the-art methods.

Key Insights and Ideas

  • Thompson Sampling for Pareto Optimality: The key insight is that Thompson sampling, typically used for finding a single optimum, can be adapted to find the Pareto front by sampling from the posterior and identifying Pareto optimal points within those samples. This elegantly bypasses the need for a complex, hard-to-optimize acquisition function.
  • Cheap Inner Optimization: By performing the "inner optimization" (finding candidate Pareto points) on sampled GP paths using evolutionary algorithms, the computational cost is significantly reduced compared to optimizing a complex acquisition function directly. This is a major win for sample efficiency.
  • Natural Exploration-Exploitation Balance: The approach inherently balances exploration and exploitation. Under low posterior uncertainty, sampled Pareto fronts are likely close to the true front (exploitation), while under high uncertainty, they are likely further away, encouraging exploration.
  • Seamless Constraint Handling: The method's ability to incorporate constraints by simply adding more GP models and including them in the evolutionary optimization is a significant advantage over methods that struggle with constraints.
  • Batch Acquisition Efficiency: The cost of acquiring a batch of q points is nearly the same as acquiring a single point, a substantial improvement over many existing batch MOBO methods.

Key Results

  • Superior Performance: qPOTS consistently outperforms or matches state-of-the-art methods (TSEMO, PESMO, MESMO, qNEHVI, qPAREGO, Sobol) across various synthetic and real-world problems, especially in terms of hypervolume achieved.
  • Efficiency Gains: The paper demonstrates significant computational efficiency, particularly in higher dimensions and for batch acquisitions, where qPOTS is much faster than many competitors.
  • Constraint Handling: qPOTS successfully handles constrained problems, a capability lacking in several competing methods (e.g., TSEMO, entropy-based methods). qNEHVI struggled with memory overflow on constrained problems.
  • Scalability: The Nyström approximation allows qPOTS to scale to higher dimensions (up to d=20) without substantial performance degradation.

Limitations and Future Work

  • Assumption of Exact Inner Optimization: The theoretical proofs rely on the assumption that the inner multiobjective optimization problem (finding Pareto points from sampled paths) is solved exactly. The authors note that this is reasonable in practice by using sufficiently large population sizes and generations for the evolutionary algorithm.
  • Nyström Approximation Choice: The paper mentions that the choice of the subset for the Nyström approximation is an open research question, though they found using the current Pareto set to work well.
  • Future Work: The authors suggest exploring nonstationary GPs (like deep GPs) and multitask GPs to better model complex objective relationships and correlations. They anticipate that qPOTS would require minimal structural changes to accommodate these advanced GP models.

Summary updated

BibTeX
@inproceedings{2025qpots,
  title = {{qPOTS: Efficient Batch Multiobjective Bayesian Optimization via Pareto Optimal Thompson Sampling}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
}
Figure