Bayesian Optimization of CVaR with Unknown Hyperparameters

Valentin Margraf; Jonas Hanselle; Viktor Bengs; Serafima Lebedeva; Eyke Hüllermeier; Marcel Wever

cs.LGOct 13, 2026

Bayesian Optimization of CVaR with Unknown Hyperparameters

Authors: Valentin Margraf, Jonas Hanselle, Viktor Bengs, Serafima Lebedeva, Eyke Hüllermeier, Marcel Wever

Organizations: LMU Munich · Munich Center for Machine Learning (MCML) · German Research Center for Artificial Intelligence (DFKI) · RPTU Kaiserslautern-Landau ·

Abstract

We study Bayesian optimization of the Conditional Value-at-Risk (CVaR) of an expensive black-box function that depends on a decision and an environmental variable. Existing no-regret algorithms assume that the correct Gaussian process (GP) kernel and its hyperparameters are known. In practice, however, they must be estimated from limited data, often yielding a misspecified surrogate. This is especially damaging for CVaR because misspecification can distort the estimated tail-risk and thus lead to catastrophic decisions. We propose HE-CV-UCB, the first no-regret algorithm for CVaR Bayesian optimization with unknown GP hyperparameters. Given a finite candidate set containing a well-specified model, HE-CV-UCB adaptively eliminates those inconsistent with the observed data, actively queries where the survivors disagree, and returns a design that is robust across the surviving candidates. We prove that it attains cumulative regret matching the oracle rate of CV-UCB up to a factor depending only on the candidate set's size. Across synthetic benchmarks and three real-world applications, HE-CV-UCB achieves competitive performance and frequently outperforms existing CVaR Bayesian optimization methods.

Figures & tables

Figure 1: Surrogate misspecification distorts CVaR estimation. Left: the objective $f(x,w)$ , with a sharp ridge at $w\approx 0.85$ for $x\lesssim 0.4$ . Right: the true $\mathrm{CVaR}_{\alpha}[f(x,W)]$ over designs $x$ (black). A well-specified surrogate ( $\ell_{w}=0.04$ , blue) resolves the ridge and its CVaR band contains the truth, while the over-smoothed surrogate ( $\ell_{w}=3.0$ , orange) is tail-blind and recommends a near-worst design ( $x\approx 0.22$ ).

Figure 2: Candidate pool of three GPs: the one generating the objective ( $\ell_{w}=0.20$ , oracle) and two oversmoothers ( $\ell_{w}\in\{2.0,8.0\}$ ). Left: the GP sample $f(x,w)$ . Middle: simple regret of the recommended design, averaged over 5 seeds. Right: HE-CV-UCB eliminates both oversmoothers after a median of 4 and 13 iterations, respectively.

Figure 3: CVaR regret on the synthetic spike function averaged over 10 seeds. The baselines select or average high-likelihood source GPs that are tail-blind, HE-CV-UCB removes the oversmoothers and reaches zero regret.

Panel of Figure 4 — Figure 4: CVaR regret of the recommended design vs. budget on robot pushing (left) , the exothermic batch reactor (middle) , and SAT solver configuration (right) . HE-CV-UCB matches the best baselines on robot pushing and reaches substantially lower CVaR regret on the reactor and SAT. Mean $\pm$ 1 SEM over 10 seeds.

Panel of Figure 5 — Figure 5: CVaR regret comparing to from-scratch single-task models (no transfer). Mean $\pm$ 1 SEM over 10 seeds.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	$d_{x}$	$d_{W}$	$\|\Theta\|$	$n_{\mathrm{init}}$	budget	seeds	$\alpha$
Spike (synthetic)	1	1	9	8	30	10	0.90
Robot push (goal-transfer)	3	2	8	10	60	10	0.70
SPEAR (cluster-transfer)	26	10	7	40	80	10	0.70
Reactor (scale-transfer)	3	3	9	16	40	10	0.98

Appendix

Table 1: Benchmark configurations. Budget is BO iterations after the initial design; total evaluations

=n_{\mathrm{init}}+\text{budget}

\alpha

is the confidence-level CVaR parameter (worst

1-\alpha

fraction).

Method	final W/T/L	AUC W/T/L
HE-CV-UCB	4/12/0	6/10/0
$\rho$ KG apx	1/14/1	0/15/1
CV-TS	0/15/1	0/14/2
BMA-UCB	0/15/1	2/13/1
CV-UCB	0/14/2	0/12/4

Appendix

Table 2: Significant wins/ties/losses over every pair of methods that share the transferred candidate pool, pooled over the four benchmarks (spike, robot pushing, reactor and SPEAR. Each entry is a paired two-sided exact Wilcoxon signed-rank test over the shared seeds: a win denotes significantly lower regret (

p<0.05

), a loss significantly higher, and a tie no significant difference.

Figure 6: Reactor under

\mathrm{VaR}_{0.98}

: VaR regret vs. budget. The method ordering matches the CVaR result. Mean

\pm

1 SEM.

Figure 7: Fraction of candidate surrogates surviving over the BO run. On spike and the reactor, HE-CV-UCB prunes source surrogates; on robot push and SPEAR the pool remains essentially intact.

Panel of Figure 8 — Figure 8: SPEAR across targets and pool budgets: $t_{1}$ / $t_{5}$ at snapshot budgets $120$ and $300$ (left to right). Mean $\pm$ 1 SEM.

Panel of Figure 9 — Figure 9: CVaR regret vs. budget on robot push (left), reactor (middle), and SPEAR (right) under the three recommender rules (rows).

Bayesian Optimization

Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.

See all 235 papers

Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization
May 31, 2026Shion TakenoBayesian Optimization Regret Minimization
Nagoya University
On the Generalization and Robustness in Conditional Value-at-Risk
Feb 20, 2026Dinesh Karthik Mulumudi, Piyushi Manupriya, Gholamali Aminian +1Conditional Value-at-Risk Empirical Risk Minimization
Dept. of Mathematics, IISER, Pune. · Dept. of Computer Science and Automation, Indian Institute of Sciecne, Bangalore. · The Alan Turing Institute, Greater London, England, UK.
Continuity-Free Near-Minimax Leading-Order Regret for CVaR-UCBVI
Aug 29, 2026Yuanlong ChenRegret Minimization in RL Risk-Sensitive RL

May 31, 2026J/K move · Enter open · S save

Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization

Shion Takeno

Nagoya University

Bayesian Optimization Regret Minimization Variance Reduction

Open paper AskPDF arXiv

This paper studies theoretical guarantees of a one-step lookahead Bayesian optimization (BO) method. Although the empirical effectiveness of one-step lookahead BO methods, such as entropy search, has been studied extensively, they often rely on computationally intractable approximations, and their regret guarantees remain underdeveloped. Thus, this paper analyzes a one-step lookahead BO method, which we refer to as optimal-point variance reduction (OVR), that requires only posterior sampling and Monte Carlo approximations. We obtain a uniform Monte Carlo estimation error bound over an input domain in an acquisition function computation. Furthermore, we show that the regularized OVR, with a slight modification to facilitate exploration, achieves a vanishing Bayesian expected simple regret upper bound. Finally, we validate the performance of OVR and regularized OVR through numerical experiments.

Abstract

Bayesian Optimization

Explore similar work

Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization

On the Generalization and Robustness in Conditional Value-at-Risk

Continuity-Free Near-Minimax Leading-Order Regret for CVaR-UCBVI