MOBO-CAPS: Multi-Objective Bayesian Optimization with Cardinality-Aware Pareto Selection

Hanyang Wang, Juergen Branke, Matthias PoloczekarXiv 2026 · arXiv

TL;DR

Standard multi-objective optimization often wastes effort mapping out an entire Pareto front when a decision-maker only needs a handful of representative solutions. This paper introduces MOBO-CAPS, a framework that bakes this "cardinality constraint" directly into the search process using two new algorithms, REHVI and CHO-UCB, which significantly outperform traditional methods that select subsets only after the optimization is finished.

What Problem Does This Paper Address?

In Multi-Objective Bayesian Optimization (MOBO), we try to find the "Pareto front"—the set of solutions where you can't improve one objective (like car speed) without hurting another (like fuel efficiency).

Traditionally, MOBO algorithms try to approximate the entire front. However, in the real world, a company might only have the budget to manufacture three car models or test two drug formulations. Currently, engineers usually run a standard MOBO to find the whole front and then pick the best $M$ points afterward (post-hoc selection).

The authors argue this is inefficient. If you know you only need $M$ points, why spend expensive function evaluations exploring parts of the trade-off space that will never make it into your final small set? The paper formalizes this as Multi-objective Bayesian Optimization with Cardinality-aware Pareto Selection (MOBO-CAPS).

Methods

The authors propose two distinct strategies to make the optimization "aware" of the final set size $M$:

  1. REHVI (Replacement-aware Expected Hypervolume Improvement): This builds on the classic EHVI algorithm. Instead of calculating how much a new point improves the entire observed set, REHVI calculates the expected improvement gained by adding a new point and removing the least useful point from the current best $M$-sized set. It essentially asks: "If I can only keep $M$ points, does this new candidate deserve a spot on the team?"
  2. CHO-UCB (Collective Higher-dimensional Optimization with Upper Confidence Bound): This method treats the entire set of $M$ points as a single, high-dimensional decision variable. It uses a Gaussian Process to create an "optimistic" version of the objectives (using Upper Confidence Bounds) and then jointly optimizes all $M$ points to maximize their collective hypervolume.

A major theoretical contribution is a sublinear simple regret bound for a batched version of CHO-UCB, providing a mathematical guarantee that the algorithm will eventually converge to the optimal $M$-point set.

Datasets

The researchers evaluated their methods against nine benchmarks across 45 different test cases (varying the set size $M$ from 1 to 5):

  • Synthetic Functions: BraninCurrin, DTLZ1, DTLZ2, VLMOP2, and VLMOP3. These are standard mathematical "torture tests" for optimizers.
  • Real-World Engineering Tasks:
    • VehicleSafety: Designing car structures for mass and collision safety.
  • Truss Design: Optimizing structural volume vs. joint displacement.
  • SnAr: Optimizing a chemical reaction for yield and environmental impact.
  • Penicillin: Optimizing the production process for yield, emissions, and time.

Key Insights and Ideas

  • The "Wasted Effort" Gap: Standard MOBO tends to spread its evaluations thin to cover the whole Pareto front. By focusing only on the best $M$ points, REHVI and CHO-UCB concentrate evaluations in the most promising regions, leading to much higher quality final sets for the same evaluation budget.
  • Exploitation vs. Exploration: The authors found that REHVI is particularly "exploitative." While standard EHVI spreads evaluations along the front, REHVI clusters them around the specific points that maximize the hypervolume of a small set.
  • Theoretical Bridge: Proving regret bounds for set-valued objectives is hard because standard distances don't apply. The authors used a "matching distance" on multisets to prove that the hypervolume indicator is Lipschitz continuous, allowing them to adapt standard Bayesian Optimization proofs to this new setting.
  • Initialization Matters: The paper highlights that "Sample-around-Pareto Initialization" (SPI) is crucial for REHVI to prevent the acquisition function from getting stuck in flat regions of the search space.

Key Results

  • Superior Performance: REHVI achieved the strongest overall performance, ranking first in 30 out of 45 experimental settings.
  • Efficiency: Both REHVI and CHO-UCB consistently outperformed the "standard MOBO + post-hoc selection" baseline across almost all benchmarks.
  • Computational Trade-offs: While REHVI is often the most accurate, CHO-UCB is faster to optimize because it avoids expensive Monte Carlo simulations, making it an attractive alternative when computational time for the optimizer itself is limited.
  • Coverage: Even with a very small $M=3$, the CAPS-sets identified by these methods covered between 69% and 99.7% of the total possible hypervolume of the full Pareto front.

Limitations and Future Work

  • Small Cardinality Focus: The experiments focused on small sets ($M \leq 5$). As $M$ grows larger, the advantage over standard MOBO diminishes because the problem starts to look like approximating the full front again.
  • Dimensionality: The study was limited to relatively low objective counts ($K \leq 3$) and moderate input dimensions ($d \leq 10$). Scaling to "many-objective" problems remains an open challenge.
  • Batching: While CHO-UCB has a batched version, extending REHVI to support parallel evaluations (evaluating multiple points at once) is a suggested avenue for future research.
  • Preference Integration: The current work uses hypervolume as a proxy for quality, but future versions could incorporate specific human preferences (e.g., "I care more about safety than cost").

Summary updated

Abstract

Multi-objective Bayesian optimization (MOBO) traditionally aims to approximate the entire Pareto front, but, due to resource constraints, real-world deployment is often limited to testing a small, representative subset of solutions. Hence current methods first approximate the full front before selecting solutions, potentially wasting costly evaluations. We formalize this problem as Multi-objective Bayesian Optimization with Cardinality-aware Pareto Selection (MOBO-CAPS), where the goal is to identify a set of exactly M solutions with high hypervolume. We propose two practical cardinality-aware acquisition strategies: REHVI, a replacement-aware approximation to expected hypervolume improvement, and CHO-UCB, which constructs an optimistic M-point set by optimizing a collective UCB-based hypervolume objective. We prove a sublinear simple regret bound for the batched version of CHO-UCB, and empirically show that cardinality-aware acquisition design improves over standard MOBO followed by post-hoc subset selection across nine benchmarks.
BibTeX
@misc{wang2026mobo,
  author = {Hanyang Wang and Juergen Branke and Matthias Poloczek},
  title = {{MOBO-CAPS: Multi-Objective Bayesian Optimization with Cardinality-Aware Pareto Selection}},
  year = {2026},
  eprint = {2611.19999},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19999},
}
Figure