Bayesian Optimization of CVaR with Unknown Hyperparameters

1 Introduction

• Surrogate misspecification can distort CVaR estimates and produce unsafe decisions, while existing CVaR BO regret guarantees assume a correctly specified GP.Kernel families are often selected heuristically, and hyperparameters estimated from limited observations can yield misspecified surrogates.Source: §1 · pp. 1–2
• HE-CV-UCB maintains a finite set of candidate models, eliminates those inconsistent with observations, queries where survivors disagree, and recommends a design robust across them.The candidate set is assumed to contain the true model.Source: §1 · p. 2
• The regret guarantee recovers CV-UCB’s oracle rate up to a multiplicative factor of |Θ|.The bound is described as cumulative regret.Source: §1 · p. 2
• Across synthetic benchmarks and three real-world applications, HE-CV-UCB significantly improves on competing methods while never being significantly outperformed.Source: §1 · p. 2

Risk-averse Bayesian optimization

• CV-UCB and CV-TS provide sublinear regret for CVaR BO, but their guarantees rely on a correctly specified GP with known kernel hyperparameters.Earlier CVaR acquisition-function work did not provide regret guarantees.Source: §2 · p. 2

Unknown kernel hyperparameters

• Unknown-hyperparameter methods for expectation-based BO include posterior marginalization, bounded-misspecification analysis, adaptive lengthscales, and elimination among GP learners.These approaches focus on expectation-based objectives.Source: §2 · p. 2
• Hyperparameter uncertainty in risk-averse BO remained unexplored; HE-CV-UCB extends Ziomek et al.’s [2025] elimination framework to CVaR, where surrogate uncertainty affects a tail-risk functional.Source: §2 · p. 2

3 CVaR Bayesian Optimization

• The objective is to minimize CVaR over environmental uncertainty, represented by a known or estimated distribution through a finite set of scenarios.Large function values are treated as undesirable, including loss, runtime, or prediction error.Source: §3 · p. 2
• CVaR averages outcomes in the worst (1 − α)-fraction, and larger α corresponds to greater risk aversion.As α approaches 0, CVaR recovers the expectation.Source: §3 · p. 3
• CV-UCB lifts pointwise GP confidence bands into CVaR bounds, selects the optimistic design, and queries an environmental value whose pointwise band gap controls the CVaR gap.Under a well-specified surrogate, CV-UCB achieves sublinear regret.Source: §3 · p. 3
• In practice, unknown kernels and hyperparameters estimated from finite data can invalidate confidence guarantees, allowing misspecified surrogates to produce inaccurate CVaR estimates and poor decisions.Source: §3 · p. 3

4 CVaR BO with Unknown Hyperparameters

• HE-CV-UCB assumes a finite candidate set containing the correct GP model and eliminates candidates statistically inconsistent with observations.Its acquisition uses surviving candidates to construct CVaR bounds; optimistic and pessimistic bounds may come from different candidates.Source: §4 · p. 3

4.1 Proposed algorithm

• The algorithm selects the most optimistic surviving candidate for the design and the most pessimistic candidate to bound that design’s CVaR.The candidates defining these bounds need not coincide.Source: §4.1 · p. 3
• Its lacing query maximizes the cross-surrogate confidence gap, which captures both within-candidate posterior uncertainty and disagreement between candidates.The gap may be negative because its defining functions need not be pointwise ordered, yet the selected query controls instantaneous regret.Source: §4.1 · p. 4
• Elimination tests candidates defining the current bounds against residual errors; the guarantee does not require uniquely identifying the true model, only that a correctly specified candidate survives with high probability.Residual errors combine observation noise and model error; the correctly specified candidate is not eliminated with high probability.Source: §4.1 · p. 4

4.2 Regret guarantee

• With a fixed finite candidate set and the stated well-specified-candidate condition, the cumulative regret bound is sublinear, yielding no-regret learning without known hyperparameters.The candidate-set factor arises from two-sided elimination and interruptions to residual histories.Source: §4.2 · p. 5
• The regret guarantee concerns queried designs, so sublinear cumulative regret ensures that the best queried design has vanishing instantaneous regret.Source: §4.2 · p. 5
• After optimization, the recommendation is the explored design minimizing worst-case posterior mean CVaR across surviving candidates.This Γ-maximin recommendation is conservative about remaining model uncertainty, unlike the optimistic acquisition rule.Source: §4.2 · p. 5

5 Experiments

• For real-world transfer tasks, the authors fit one GP per source task and compare methods using the same transferred candidate pool for RQ2 and RQ3.For RQ4, they compare against single-task surrogates fitted from scratch on the target.Source: §5 · p. 5

5.1 Toy example (RQ1)

• With the data-generating GP in the candidate pool, HE-CV-UCB eliminates both oversmoothers while retaining the oracle and converges to its simple-regret performance.The oversmoothers are eliminated after median 4 and 13 iterations, respectively.Source: Figure 2 · p. 6, §5.1 · p. 6

5.2 Synthetic experiment (RQ2)

• On the synthetic spike function, HE-CV-UCB reaches near-zero CVaR regret while likelihood-based baselines favor regions with poor CVaR performance.Its disagreement-based queries concentrate in the tail, where the candidates differ.Source: Figure 3 · p. 6, §5.2 · p. 6

5.3 Real-world experiments (RQ3)

• HE-CV-UCB matches the strongest baseline on robot pushing and achieves the lowest final CVaR regret on the reactor and SAT tasks.The three tasks span mild to severe misspecification.Source: §5.3 · pp. 6–7, Figure 4 · p. 7

5.4 Value of transfer models (RQ4).

• Against from-scratch models, HE-CV-UCB reaches substantially lower final CVaR regret on the reactor and SAT, while CV-TS performs best on robot pushing.The benefit of transfer depends on how difficult the target's tail structure is to identify.Source: Figure 5 · p. 7, §5.4 · p. 7

• Misspecification can distort CVaR tail estimates and lead to poor risk-sensitive decisions, while existing CVaR BO methods typically assume the correct surrogate and hyperparameters are known.Source: §6 · p. 8
• HE-CV-UCB maintains plausible GP candidates, eliminates those inconsistent with observations, queries where survivors disagree, and returns a decision robust to remaining model uncertainty.Its cumulative regret bound matches the oracle rate of CV-UCB up to a factor linear in candidate-set size.Source: §6 · p. 8
• The theoretical guarantee assumes a correctly specified surrogate is in the candidate set; regret guarantees that degrade with the best candidate's misspecification remain open.The regret bound also incurs a factor |Θ| from two-sided elimination, whose necessity is unresolved.Source: §6 · p. 8

A Proofs

• The proof keeps the true candidate θ⋆ in the pool, uses its valid confidence bands to bound per-round regret, and charges at most |Θ| critical elimination rounds at 2B each.The residual sums on non-critical rounds are controlled by elimination thresholds and GP uncertainty widths.Source: A Proofs · pp. 10–12
• Two-sided elimination can interrupt a candidate’s residual stream when the opposite criterion eliminates another candidate, requiring an additional threshold charge for those gaps.The proof controls the omitted residuals individually; there can be up to |Θ| such rounds.Source: A Proofs · pp. 11–13
• For a fixed finite candidate set, regret is sublinear when γT = o(T), with βT = O(√γT + 1) and ξT = O(log T) for standard kernels.The theorem’s bound includes a factor depending on |Θ|; the two-sided elimination proof adds a charge for residual-stream gaps.Source: A Proofs · pp. 12–13

B.1 Environmental distribution PW

• The environmental distribution is represented by fixed shared Sobol atoms, uniform by default and truncated-normal for disturbances concentrated near a nominal operating point.The same atoms define the empirical tail average across designs and iterations.Source: §B.1 · p. 13

B.2 Computing the posterior CVaR bands

• Posterior CVaR bands are computed analytically from per-atom GP means and standard deviations, so acquisition and elimination comparisons use no posterior sampling or Monte Carlo noise.Each candidate has frozen kernel and hyperparameters; the bands use the empirical CVaR of shifted posterior means over the atoms.Source: §B.2 · p. 13

B.3 Benchmark suite

• The four benchmarks compare HE-CV-UCB with CV-UCB, CV-TS, ρ-KGapx, and BMA-UCB using the same transfer method set.The reported settings include β=3.0 and ξ=0.5.Source: §B.3 · p. 13
• The suite covers a synthetic spike testbed and three transfer applications: robot pushing, reactor scale-up, and SPEAR solver configuration.The robot-push sources vary goal location; reactor sources vary scale; SPEAR sources are instance clusters, with one cluster held out as the target.Source: §B.3 · pp. 13–14

B.4 Computational cost

• Each iteration conditions frozen GP candidates on the observations, with cost growing linearly in candidate-pool size and no per-iteration hyperparameter refit.The stated work includes an O(t^3) Cholesky and O(Mt^2) per-atom posterior evaluations, plus acquisition optimization.Source: §B.4 · p. 14

B.5 Final hyper-parameters

• Experimental values are fixed across seeds; the default recommender is pessimistic (Γ-maximin), with medoid and Borda-rank alternatives also reported.The listed kernels are Matérn-3/2, Matérn-5/2, and RBF, fitted on offline tasks.Source: §B.5 · p. 14

B.6 Software and hardware

• Experiments used 2 CPU cores and 8 GiB of RAM, on HPC nodes with two AMD Milan 7763 processors and 256 GiB of memory.Source: §B.6 · p. 14

C.1 Significance tests

• The tests compare final recommended-design CVaR regret and anytime CVaR regret, the average regret of recommended designs over the BO phase.All methods used matched initial designs and GP conditioning on each seed.Source: §C.1 · p. 14
• 4 final-regret wins and 6 anytime-regret wins: HE-CV-UCB was never significantly outperformed and accumulated the most significant wins across the four benchmarks.Tests were paired two-sided exact Wilcoxon signed-rank tests over seeds 0–9 at α=0.05, without multiplicity correction; BMA-UCB was the strongest baseline overall.Source: §C.1 · p. 14, Table 2 · p. 15
• Under Reactor VaR0.98, method ordering by VaR regret versus budget matches the CVaR result.The figure reports mean ± 1 SEM.Source: Figure 6 · p. 15

C.2 Robustness to the recommender rule

• The Γ-maximin, medoid, and Borda-rank rules score queried designs by aggregating posterior mean CVaR across the surviving candidates.The main-text read-out is pessimistic Γ-maximin; changing the post-hoc recommendation does not change which designs were queried.Source: §C.2 · p. 15
• Across all three recommender rules, HE-CV-UCB matches baselines on robot push and reaches lower CVaR regret on reactor and SPEAR.The advantage is reported regardless of read-out rule.Source: §C.2 · p. 15
• HE-CV-UCB prunes source surrogates on spike and reactor, while the candidate pool remains essentially intact on robot push and SPEAR.Source: Figure 7 · p. 15

C.3 Ablation over targets and pool budgets (SPEAR)

• HE-CV-UCB attains the lowest final CVaR regret in all four SPEAR target-cluster and snapshot-budget combinations.The margin is stable across the two target clusters and two budgets.Source: §C.3 · p. 15
• Single-selection baselines sometimes commit to a source that times out on held-out instances, while HE-CV-UCB hedges over the surviving pool.The reported ablations find that neither target choice nor source-data amount changes this qualitative comparison.Source: §C.3 · p. 15

C.4 Elimination dynamics

• Elimination prunes confidently tail-blind sources on the spike and reactor, but remains essentially inert on SPEAR and robot push, where every candidate is reasonable for the target.Candidates are removed only when accumulated residuals are statistically inconsistent with the data; a correctly specified candidate is not discarded with high probability.Source: §C.4 · pp. 15–16
• When elimination is inert, HE-CV-UCB recommends the design that is best in the worst case across survivors, avoiding the commitment required by single-selection baselines.On the spike and reactor, pruning further removes candidates that would otherwise affect the worst-case recommendation.Source: §C.4 · p. 16

C.5 An alternative risk measure: VaR

• VaRα is the α-quantile threshold, while CVaRα averages the worst (1 − α) fraction of outcomes conditional on exceeding that threshold.Unlike VaR, CVaR is sensitive to tail shape and is coherent, including subadditivity.Source: §C.5 · p. 16
• The confidence bands, elimination criteria, and robust recommendation extend to VaR because the risk read-out needs only monotonicity and translation invariance.The paper applies the machinery by replacing CVaRα with VaRα in the bands and acquisition rule.Source: §C.5 · p. 16
• HE-CV-UCB attains the lowest final VaR regret in the reactor experiment and separates from the baselines.The experiment replaces CVaR0.98 with VaR0.98 while holding other settings fixed.Source: §C.5 · p. 16
• The regret guarantee is established for CVaR; a VaR analogue is available through V-UCB analysis, but a unified guarantee across risk measures remains future work.The paper attributes the additional guarantee step to a lacing-value construction.Source: §C.5 · p. 16