Simple Extensions of Single-Objective Acquisition Functions and Hedge Strategies for Multi-Objective Bayesian Optimization

Conference: NeurIPS 2026
arXiv: 2609.31940
Area: Optimization & Theory
Keywords: multi-objective Bayesian optimization, acquisition functions, hypervolume, Pareto candidates, acquisition portfolios

TL;DR

The paper generates candidates through Pareto search over a vector of single-objective acquisitions, selects queries using posterior-mean hypervolume, and adaptively chooses acquisitions with MO-Hedge; results are competitive on nine benchmarks, but the runtime advantage is mainly evident in batch mode rather than uniformly across settings.

Background & Motivation

Expensive black-box optimization often seeks a set of nondominated trade-offs rather than a single scalar optimum. Multi-objective Bayesian optimization must learn unknown functions under a limited query budget while covering the Pareto front. ParEGO scalarizes multiple objectives, EHVI methods compute expected hypervolume improvement, HVKG considers the value of information for the next iteration, and JES targets information about Pareto structures. Each has a rationale, but scalarization, integration, fantasy samples, or entropy estimation can introduce implementation and computational overhead.

Instead of deriving a complex multi-objective acquisition, the author separates two decisions: existing EI or UCB determines exploration for each objective, while hypervolume ranking over a candidate set determines which trade-offs warrant evaluation. This is neither direct summation of objectives nor inexpensive evolutionary search over the true objectives. The evolutionary optimizer searches acquisition values supplied by surrogate models; the expensive true function is called only at the selected points.

Acquisition choice is itself problem dependent. Fixed EI can become prematurely exploitative, while fixed UCB need not suit every task, motivating an extension of the single-objective GP-Hedge portfolio approach. Core Idea: generate exploration–exploitation trade-off candidates with an acquisition vector, select current queries using predicted hypervolume, and use the predicted hypervolume of historical candidates to decide which acquisition to trust subsequently.

Method

Overall Architecture

qHAX stands for Parallel Hypervolume-ranked Acquisition Extension. Each iteration first fits independent Gaussian processes for the objectives using existing observations, then constructs a query batch through “Acquisition-Vector Candidates,” “Mean-Hypervolume Ranking,” and “Within-Batch Greedy Deduplication.” MO-Hedge is an optional outer acquisition selector: every portfolio member first proposes a batch, and the selector samples a member's nominee for each query position using historical performance. It does not run only the acquisition ultimately selected.

Three spaces must be distinguished: input space contains design variables, acquisition space contains per-objective EI/UCB values, and objective space contains predicted or true objective values. Candidates are nondominated in acquisition space, whereas final ranking operates in predicted objective space. Only after actual observations return are query data and the next iteration's surrogate models updated.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    D["Existing observations"] -->|Fitting update| G["Per-objective GPs"]
    G --> A["Acquisition-Vector<br/>Candidates"]
    A --> B["Mean-Hypervolume<br/>Ranking"]
    B --> C["Within-Batch Greedy<br/>Deduplication"]
    C -->|Each member's nominated batch| H["Historical-Hypervolume<br/>Hedge"]
    C -->|Direct query with a fixed strategy| E["True-function queries"]
    H -->|Sample nominees by position| E
    E -.->|Refit after new observations| G
    G -.->|Recompute predicted rewards for old candidates| H

Key Designs

1. Acquisition-Vector Candidates: retain trade-offs between per-objective acquisition values first

The same type of single-objective acquisition is constructed separately for each objective, and the resulting values are assembled into a vector. Each qHAX-UCB component adds an uncertainty bonus to the predictive mean, whereas each qHAX-EI component measures expected improvement relative to the corresponding objective's current best value. Existing acquisitions govern exploration and exploitation for their respective objectives without first collapsing all objectives into a scalar.

\[ \boldsymbol{\alpha}_{t}(\mathbf{x})=\big(\alpha^{1}_{t}(\mathbf{x}),\ldots,\alpha^{M}_{t}(\mathbf{x})\big),\qquad \alpha^{m}_{t,\mathrm{UCB}}(\mathbf{x})=\mu^{m}_{t}(\mathbf{x})+\sqrt{\beta_t}\,\sigma^{m}_{t}(\mathbf{x}). \]

The author uses pymoo's NSGA-II to approximately solve multi-objective maximization of this acquisition vector and retain nondominated inputs. One candidate may have a high acquisition value for the first objective and a lower value for the second, with another candidate showing the reverse pattern; both can remain in the pool. “Pareto” here refers to acquisition values. It does not imply that these inputs are Pareto-optimal for the unknown true objectives or that their predicted mean vectors are nondominated.

This stage avoids prematurely removing trade-off directions through random scalarization and allows acquisition uncertainty to influence search. It is not free, however: each iteration still performs population-based multi-objective optimization, and candidate quality depends on adequate inner search. Candidate count and NSGA-II population and iteration settings cannot be fully recovered from the cached implementation description, so “plug-and-play” does not mean parameter-free.

2. Mean-Hypervolume Ranking: compare candidates' geometric utility in predicted objective space

Once candidates exist, the method no longer directly compares EI/UCB vectors. It predicts the means at all evaluated inputs with the current surrogates and applies nondominated filtering to obtain a denoised front. Each candidate is also mapped to a predictive mean vector, and the hypervolume after adding that vector to the current front is calculated. Maximizing this total hypervolume is equivalent to maximizing its increment relative to the same baseline.

For clarity, the equation below expresses the paper's total-hypervolume ranking as an equivalent increment; this is not a derivation of a separate acquisition. Hypervolume is the volume of the union of axis-aligned boxes extending from a dominated reference point to the objective vectors. Overlapping coverage is not counted twice.

\[ \mathcal{P}_t=\mathrm{ND}\!\left(\{\boldsymbol{\mu}_t(\mathbf{x}_i):\mathbf{x}_i\text{ has been evaluated}\}\right),\qquad \Delta_t(\mathbf{c})=HV\!\left(\mathcal{P}_t\cup\{\boldsymbol{\mu}_t(\mathbf{c})\};\mathbf{r}_t\right)-HV(\mathcal{P}_t;\mathbf{r}_t). \]

This is not EHVI: ranking does not take an expectation over random candidate outcomes under the posterior, but substitutes the mean into hypervolume. Exploration comes from acquisition-vector candidate generation, while final geometric selection is deterministic. This removes nested integration and lookahead optimization, but can discard uncertain candidates whose means are currently unattractive. “Preserving single-objective acquisition semantics” does not mean final queries fully preserve those acquisitions' uncertainty preferences.

The reference point must be dominated by the relevant objective vectors in the same coordinate system as the predictions. Algorithm 1 specifies coordinatewise minima minus 0.01, but its notation directly combines an objective front with an input candidate set, omitting the mapping from candidates to predicted objectives. The interpretation here follows the predicted-objective-space meaning in the prose rather than reproducing that type-inconsistent equation. Reference-point choice is not completely irrelevant to ranking. Ties are resolved using the Pareto optimizer's ordering, typically involving crowding distance.

3. Within-Batch Greedy Deduplication: avoid concentrating the batch in the same predicted region

Taking the highest-ranked candidates from an initial hypervolume ranking can select several points covering almost identical objective regions. After selecting each point, qHAX adds its predicted mean to a temporary front, removes that input, and reranks the remaining candidates. Later points are therefore selected according to what they add beyond the region already predicted to be covered, rather than independently competing for the same largest-gain region.

GPs are not refitted during batch construction, and the method does not pretend to have received true observations. Only a temporary predicted set is updated. The true function is evaluated in parallel after batch construction, and the resulting observations augment the dataset. If candidates are exhausted, the prose specifies uniform sampling within the input domain to fill the batch. Algorithm 1 does not clearly express control flow that skips the subsequent empty-set argmax in this branch, which requires implementation-level handling.

Hypervolume is monotone and submodular. With a fixed candidate set, fixed predicted vectors, and a fixed reference point, greedy cardinality-constrained batch selection obtains a \((1-1/e)\) approximation to the best single-iteration predicted hypervolume increment. This guarantee neither assesses inputs outside the candidate set nor controls prediction error, and it is not a cumulative regret guarantee for the entire Bayesian optimization process. The fixed-candidate-set argument also cannot be applied unconditionally when random fallback points enter the batch.

4. Historical-Hypervolume Hedge: reassess every strategy's past nominees with the current posterior

MO-Hedge is not restricted to qHAX; it only requires portfolio members capable of proposing query batches. Every member generates nominees at each iteration and maintains its own history of nominated inputs, including points never actually queried. The current shared surrogate posterior then predicts the old candidates for each member again. The hypervolume of that member's entire predicted history serves as its gain, and exponential weights produce selection probabilities.

\[ g_t^k=HV\!\left(\{\boldsymbol{\mu}_t(\mathbf{x}):\mathbf{x}\in\mathcal{H}_t^k\};\mathbf{r}\right),\qquad p_t^k=\frac{\exp(\eta_t g_t^k)}{\sum_{j=1}^{K}\exp(\eta_t g_t^j)}. \]

No extra true-function calls are made for each unselected strategy. Every member receives full-information-style predicted rewards from the surrogate, not full-information feedback about every member's true performance. When new observations obtained through another strategy correct a candidate's prediction, its historical reward changes as well. The gain is a recomputed historical-set hypervolume, not a sum of actual per-iteration hypervolume improvements or an independent reward for a single candidate.

The paper adds current nominees to the next-time history while computing rewards from the current history. Algorithm 2's indices therefore point to old nominees and should not be interpreted as rewarding current true outcomes already observed. For each batch position, a member is sampled using the same selection probabilities, and that member's nominee at the corresponding position is selected. A batch can thus mix strategies. The paper does not specify deduplication of overlapping nominees across strategies or a new joint hypervolume-greedy selection over the mixed batch.

This approach can reduce the risk of selecting an unsuitable fixed acquisition when task structure is unknown, but its cost includes candidate generation for every member and prediction and hypervolume computation over every history. Parallelism reduces latency for parallelizable work; it does not remove total computation. The author explicitly acknowledges that the actual whole-history recalibration variant does not satisfy standard Hedge conditions based on accumulated frozen rewards. A theoretically bounded alternative is not evidence that the reported variant has the same guarantee.

A Worked Example

Consider two objectives, both to be maximized. Two GPs fitted to existing data let NSGA-II propose acquisition-vector-nondominated points, possibly favoring a high UCB for the first objective, a high UCB for the second, or a compromise. These inputs are then mapped to predictive means, and the method asks which input expands current predicted-front coverage rather than which has the largest sum of UCB values.

For a batch of size 3, suppose the first point expands one end of the front. After its predicted vector enters the temporary front, a previously second-ranked point covering the same region may lose its utility, and a candidate extending the middle of the front may rise in rank. The process continues until three points are selected, followed by true-function evaluation. This example explains why within-batch reranking matters; it does not imply that the paper reports specific candidate coordinates or hypervolume values for this scenario.

With MO-Hedge enabled, each qHAX member independently performs this procedure, while other members use their own batch-generation routines. Hedge samples nominees by position using historical hypervolume under the current posterior. Only the final mixed batch is queried, and the observations revise the predicted value of all members' histories at the next iteration.

Loss & Training

The paper introduces no new neural-network training loss. All model-based strategies use BoTorch's ModelListGP and SumMarginalLogLikelihood, normalize input domains, and standardize objective observations before fitting. Within-batch temporary-front updates are part of decision making, not additional training samples.

Most baselines use optimize_acqf with default settings num_restarts=10, raw_samples=500, batch_limit=5, and maxiter=100. qHVKG uses num_fantasies=10, num_pareto=10, and only one optimization start; Sobol batch search serves as a fallback for numerical failures. Comparisons therefore hold under the particular optimizers and numerical safeguards used, rather than comparing mathematical acquisition definitions alone.

The cache provides no verifiable code-repository link and does not fully specify qHAX's NSGA-II configuration, UCB exploration coefficient, or MO-Hedge learning-rate settings. These details remain necessary for reproduction.

Key Experimental Results

Main Results

The nine tasks are ZDT2, ZDT4, ZDT6, DTLZ1, DTLZ2, DTLZ3, Branin–Currin, Welded Beam, and Vehicle Crash. Their input dimensions are respectively 9, 6, 6, 8, 6, 4, 2, 4, and 5, with respectively 2, 2, 2, 3, 3, 2, 2, 2, and 3 objectives. The final two are engineering design test functions, with Welded Beam using an unconstrained formulation rather than online physical experiments.

Every strategy runs 20 times per task, sharing 30 initial inputs within each run and receiving 75 additional function evaluations. Independent Gaussian noise is added to each objective with standard deviation equal to 1% of the absolute mean of that objective over the initial design. Batch mode uses \(Q=3\) for 25 iterations, while sequential mode uses \(Q=1\) for 75 iterations. Total evaluation budgets match; batch mode does not receive more data.

HV measures dominated-region volume, while IGD measures the mean Euclidean nearest-neighbor distance from reference-front points to the current front. A high-budget NSGA-II run supplies an approximate reference front. The reported log-normalized indicator gap divides current error by initial error:

\[ \log\!\left(\frac{|I(\mathcal{P}_{\mathrm{opt}})-I(\mathcal{P}_{\mathrm{curr}})|}{|I(\mathcal{P}_{\mathrm{opt}})-I(\mathcal{P}_{\mathrm{init}})|}\right). \]

Lower values are better, and the value is 0 when the initial-error ratio is 1. This is neither raw HV nor known regret relative to an exact optimal front. Curves show means over 20 runs with one standard deviation above and below, not confidence intervals. The cache contains figure captions and discussion but no pointwise curve values, so final HV/IGD ranking margins are not invented.

The following table preserves verifiable values from Table 1: mean wall-clock time for one complete optimization run in batch mode, in seconds. qMOJES is the table's abbreviation for qLB-MOJES.

Task	qHAX-UCB	qHAX-EI	qMOJES	qHVKG	qLNParEGO	qLNEHVI
ZDT2	230.41	226.79	1834.78	268.04	454.05	673.54
ZDT4	214.38	219.12	2817.48	296.25	506.43	680.57
ZDT6	221.89	214.73	8092.44	321.96	799.51	953.11
DTLZ1	254.31	246.49	4636.83	424.22	372.96	711.56
DTLZ2	243.24	243.02	4089.77	390.18	352.85	886.75
DTLZ3	220.59	218.35	2943.21	229.57	507.18	506.37
Branin–Currin	246.04	242.39	2319.57	211.54	371.63	467.71
Welded Beam	226.48	223.13	3394.43	272.27	434.10	519.02
Vehicle Crash	242.42	235.32	4111.98	339.72	353.80	753.87

Experiments ran on an AMD EPYC 9654 CPU cluster, with 12 cores and 160 GB of shared memory allocated per experimental run. MO-Hedge is absent from this table, so it cannot establish that the portfolio is as fast as a single qHAX method. qHVKG is also explicitly faster than both qHAX variants on Branin–Currin.

Ablation Study

The paper does not provide quantitative ablations individually removing candidate generation, hypervolume ranking, or greedy selection. Table 3's sequential runtimes are used here for a setting analysis rather than a fabricated module ablation. Units remain seconds, averaged over 20 runs per entry.

Task	qHAX-UCB	qHAX-EI	qMOJES	qHVKG	qLNParEGO	qLNEHVI
ZDT2	676.62	715.49	2945.64	558.25	126.52	185.74
ZDT4	797.93	613.77	4469.76	668.50	265.70	186.82
ZDT6	597.61	612.06	17750.69	817.01	228.30	523.60
DTLZ1	685.13	717.91	6884.48	1074.03	378.68	453.49
DTLZ2	668.83	684.98	6523.09	959.74	270.95	574.83
DTLZ3	667.09	647.52	4010.11	615.54	167.90	127.60
Branin–Currin	721.12	729.20	3190.28	420.43	148.63	176.83
Welded Beam	576.17	584.69	4946.90	708.45	232.74	138.66
Vehicle Crash	775.76	674.66	5859.59	792.02	352.50	510.71

In the sequential table, qLNParEGO and qLNEHVI are faster than both qHAX variants on all nine tasks. This qualifies the low-overhead conclusion: qHAX is cheaper than entropy search and can amortize candidate generation within a batch, but is not a universal speed winner in sequential optimization. The paper describes runtime as largely insensitive to batch size, whereas the tables show shorter complete runs in batch mode under the same total evaluation budget. Per-iteration candidate-generation cost must be distinguished from complete-run cost.

MO-Hedge 1 combines qHAX-UCB, qLNParEGO, and random sampling; MO-Hedge 2 combines qHAX-UCB, qHAX-EI, qHVKG, and qLNEHVI. The discussion reports that the former can track stronger members despite weak constituents and that the latter is consistently competitive. It does not report selection-probability trajectories or numerical ablations comparing whole-history reward recalibration with frozen rewards.

Key Findings

• The author's qualitative interpretation of the main figure and appendix is that qHAX-UCB is more robust, while qHAX-EI is more problem dependent and remains competitive on engineering tasks. These statements are not reconstructed task-specific final numerical rankings.
• Discussions of batch HV, batch IGD, sequential HV, and sequential IGD are consistent, supporting benefits beyond batch selection alone. No single strategy is uniformly optimal on every task.
• qMOJES incurs substantially higher runtime in both settings. Lightweight design has a real benefit, but speed comparisons must identify the setting and baseline.
• Hedge results suggest improved portfolio stability. They do not establish negligible unreported parallel end-to-end overhead or validate a standard Hedge regret bound for the actual variant.

Highlights & Insights

• Separating where to explore from which trade-offs warrant queries leaves room to reuse classical acquisitions. The transferable contribution is the interface design, not a guarantee that replacing any task's decision rule with mean hypervolume yields the same properties.
• Predicted within-batch coverage reduces competition for the same objective region without repeated model fitting. It applies submodular set-selection structure to decisions over finite candidates rather than claiming a theory for complete black-box optimization.
• Reassessing old nominees provides feedback even to strategies that were not selected, avoiding sparse observed rewards. However, that feedback depends on the shared surrogate's accuracy, propagating model bias along with potential stability benefits.

Limitations & Future Work

• Inner NSGA-II search does not directly exploit common gradient-based optimization tools; the author suggests combining evolutionary search with local gradient refinement. Search-budget changes should be evaluated jointly for sample efficiency and wall-clock cost.
• Mean HV does not integrate uncertainty, while standardization and reference points influence geometric ranking. Comparing mean, posterior-sample, and confidence-bound ranking could test whether final filtering suppresses valuable exploration.
• Experiments involve at most three objectives, nine input dimensions, and 75 additional evaluations, so they do not establish scalability to high-dimensional or many-objective problems. The reference front is a high-budget approximation, not an exact solution.
• Component ablations, Hedge end-to-end timing, and history-growth costs are missing. Portfolio size, truncated histories, and reward calibration should be compared under equal resources, with the recalibrated variant's theoretical limits stated explicitly.
• Algorithm 1's reference-point notation and empty-candidate branch, along with Algorithm 2's history indices, require implementation-level clarification. These do not prevent understanding the overall mechanism but limit complete reproduction from the text alone.

Related Work & Insights

• vs ParEGO / qLNParEGO: These methods select trade-offs using randomized scalarization; qHAX first retains trade-offs in acquisition-vector space, then filters by objective-space coverage. Sequential timings nevertheless show a substantial speed advantage for simple scalarization.
• vs EHVI / qLNEHVI: These methods incorporate posterior uncertainty into expected hypervolume improvement. qHAX uses acquisition uncertainty during candidate generation but ranks final candidates by mean HV. This computational simplification makes a different approximation to posterior value and is not an equivalent implementation of EHVI.
• vs HVKG / JES: These target lookahead information value and Pareto information gain, respectively. The paper replaces such complex calculations with local geometric selection over finite candidates. Comparisons should account for numerical settings, runtime, and sample efficiency rather than theoretical complexity alone.
• vs GP-Hedge: The paper replaces single-objective predictive rewards with historical predicted-set hypervolume and repeatedly recalibrates it under the current posterior. Frozen, discounted, or sliding-window rewards are potential extensions, but acquisition-selection regret must remain distinct from regret in optimizing the unknown objectives.

Rating

• Novelty: 4/5, primarily a lightweight composition and decision interface rather than new surrogate-modeling theory.
• Experimental Thoroughness: 3/5, nine tasks and 20 repeats are useful, but module ablations, complete reproduction settings, and Hedge cost measurements are missing.
• Writing Quality: 3/5, the main pipeline is clear, but algorithm notation and sequential-runtime generalizations require careful interpretation.
• Value: 4/5, offers an implementable route to reusing mature acquisitions, particularly for small-batch multi-objective optimization.