Efficient Heteroscedastic Bayesian Optimization for Risk-Aware AutoRL

# Efficient Heteroscedastic Bayesian Optimization for Risk-Aware AutoRL
Source: [https://arxiv.org/html/2607.26680](https://arxiv.org/html/2607.26680)
Efficient Heteroscedastic Bayesian Optimization for Risk\-Aware AutoRL

Mingxuan Che, Tsung\-Yuan Tseng, Theresa Eimer,

Marius Lindauer, Alexander von Rohr

Keywords:Bayesian optimization, reinforcement learning, AutoRL

SummaryReinforcement learning \(RL\) learning outcomes can be highly stochastic, and both expected performance and variability often depend strongly on hyperparameter \(HP\) configurations\. This makes HP optimization \(HPO\) brittle: outcome variability translates into a practical risk of unsuccessful training after HPO\.We propose risk\-aware HPO through a mean\-variance objective, dubbed efficient and risk\-averse heteroscedastic Bayesian optimization \(ERAHBO\)\. It models both mean and variance, and improves sample efficiency via adaptive re\-sampling rather than a fixed replication budget per HP configuration\. We show that our adaptive strategy improves efficiency and HPO performance across a wide range of RL environments\. We additionally provide an offline dataset of RL learning outcomes mapping HP configurations to post\-training policy returns across 50 repeated runs per HP configuration to evaluate risk\-aware HPO methods\.

Contribution\(s\)1\.We propose efficient and risk\-averse heteroscedastic Bayesian optimization \(ERAHBO\), an adaptive re\-sampling formulation of RAHBO\(makarova2021risk\)that improves practical sample efficiency in HPO for RL\. We provide sublinear regret guarantees along with an empirical comparison to common Bayesian optimization \(BO\) baselines\. Context:To integrate risk into the optimization process, we need to repeatedly evaluate each hyperparameter configuration\. RAHBO sets a fixed number of evaluations for each configuration, which makes it computationally expensive on a runtime\-intense domain like reinforcement learning\.2\.We provide a dataset of RL learning outcomes mapping hyperparameters to post\-training policy returns for 50 runs, enabling reproducible benchmarking of risk\-aware hyperparameter optimization methods\. Context:Recent HPO performance datasets such as those provided in HPO\-RL\-Bench\(shala\-automl24a\)and ARLBench\(becktepe2024arlbench\)include repeated evaluations for each configuration, but the number of seeds \(up to ten\) per hyperparameter configuration can be insufficient for a reliable estimation of heteroscedastic variance across the hyperparameter space\. Our dataset addresses this by providing 50 seeds per configuration\.

###### Abstract

Reinforcement learning \(RL\) has shown remarkable success across a wide range of complex tasks\. However, RL outcomes can be highly stochastic, and both expected performance and variability often depend on hyperparameter \(HP\) configurations\. We propose efficient and risk\-averse heteroscedastic Bayesian Optimization \(ERAHBO\), a Bayesian optimization method that models both the mean and variance of learning outcomes as functions of the HP configurations\. ERAHBO aims to identify HP configurations that achieve high average return while reducing variability across training runs, and it improves the sample efficiency of the HP optimization via adaptive re\-sampling rather than a fixed budget per HP\. Empirical evaluations across diverse RL algorithms and environments demonstrate that ERAHBO generally outperforms both risk\-neutral and risk\-averse baselines, delivering improved sample efficiency for risk\-averse returns\.

## 1Introduction

The performance of reinforcement learning \(RL\) algorithms is often highly dependent on the choice of hyperparameters \(HPs\)\(berkenkamp2016safe;islam2017reproducibility;henderson\-aaai18a;zhang\-aistats21a;eimer\-icml23a;obandoceron\-rlj24\)\. Moreover, in most RL experiments, inherent randomness arises from e\.g\., stochastic task behavior, exploratory choices, or hardware nondeterminism\(zhuang2022randomness\)\. Recent work shows that even very good HP configurations may still lead to a high degree of randomness in learning outcomes\(dierkes\-ewrl25\)\.

Automated RL \(AutoRL\) aims to make RL work reliably out\-of\-the\-box by automating, for example, the setting of HPs\. However, the stochasticity of RL training makes automated hyperparameter optimization brittle: the configuration that appears best during HPO can fail to reproduce its performance in subsequent runs, and high\-variance HP configurations can yield poor policies with nontrivial probability, requiring costly retraining\. In practice, we would like HPO to return configurations that*reliably*achieve strong performance across runs, supporting reproducible and cost\-effective RL experimentation\. Therefore, it is an important research question how we can efficiently extract HP configurations that consistently lead to good performance, i\.e\., high average return with low variability across repeated training runs\.

Bayesian optimization \(BO\) is a sample\-efficient, model\-based approach to HPO that is well suited to expensive black\-box objectives and is widely used as an automated alternative to manual tuning and search heuristics\(bischl\-dmkd23a\)\. However, classical BO approaches typically optimize the mean of the objective function, in RL typically the expected final return\. This ignores training stability across runs for each hyperparameter configuration, i\.e\., its*risk*\.

A natural way to incorporate this notion into HPO is to use*risk\-aware*Bayesian optimization methods that explicitly model both the mean performance and the input\-dependent variability of outcomes, and optimize a risk\-sensitive objective\. In particular, risk\-averse heteroscedastic Bayesian optimization \(RAHBO;makarova2021risk\) provides a principled sequential BO approach that maintains separate surrogate models for the mean and variance of the return, and uses a risk\-aware acquisition function\. RAHBO can therefore be used for risk\-aware HP tuning\. However, in its original form, estimating the variance model relies on a*static*number of evaluations \(replications\) per HP configuration, which can be inefficient in RL where each run is computationally costly\.

We propose a novel adaptive replication strategy for RAHBO that determines when to acquire more samples of a configuration\. The key idea is to allocate runs where they matter most: configurations that are promising under a risk\-aware objective but still ambiguous due to uncertainty, rather than spending a uniform replication budget everywhere \(see Fig\.[1](https://arxiv.org/html/2607.26680#S2.F1)\)\. Our resulting method is anefficient risk\-averse heteroscedastic Bayesian optimization \(ERAHBO\)algorithm, designed for the high degrees of variance and simultaneously high computational loads we see in RL\.

To support the study of risk in AutoRL, we curate a new dataset of RL learning outcomes for different algorithms and environments which enables systematic analysis of heteroscedasticity in RL hyperparameters and benchmarking of risk\-aware HPO methods\.

## 2Problem formulation

![Refer to caption](https://arxiv.org/html/2607.26680v1/x1.png)Figure 1:Adaptive re\-sampling in ERHABO\.Left:Example objective with two maxima at different noise levels, and the MV objective \(dashed\)\.Middle:Upper and lower confidence bounds for the MV objective \(dotted\) together with the incumbent LCB \(blue dash\-dot\) after three configurations; the next queryxtx\_\{t\}\(chosen via UCB\) is shown by the green vertical line\.Right:After two additional samples atxtx\_\{t\}, the UCB falls below the incumbent LCB, so ERHABO does not need to re\-sample\.We consider a discounted Markov decision process \(MDP\)\. A \(stochastic\) policyπ​\(a∣s\)\\pi\(a\\mid s\)induces a distribution over trajectoriesτ∼π​\(τ\)\\tau\\sim\\pi\(\\tau\)\. The performance of a fixed policyπ\\piis its expected discounted returnJ​\(π\):=𝔼a∼π​\[∑t=0∞γt​r​\(st,at\)\]J\(\\pi\):=\\mathbb\{E\}\_\{\{\\color\[rgb\]\{0,0,0\}\\definecolor\[named\]\{pgfstrokecolor\}\{rgb\}\{0,0,0\}\\pgfsys@color@gray@stroke\{0\}\\pgfsys@color@gray@fill\{0\}a\}\\sim\\pi\}\\Big\[\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}r\(s\_\{t\},a\_\{t\}\)\\Big\], whereγ∈\(0,1\)\\gamma\\in\(0,1\)is the discount factor andr​\(s,a\)r\(s,a\)is the reward function\.

In HPO for RL, the decision variable is a hyperparameter configurationx∈𝒳⊂ℝdx\\in\\mathcal\{X\}\\subset\\mathbb\{R\}^\{d\}of a learning algorithm𝒜\\mathcal\{A\}, and the outcome is the trained policy produced by running𝒜\\mathcal\{A\}withxx\. Because RL training is inherently stochastic \(e\.g\., random initialization, exploration, and stochasticity encountered during training\), running𝒜\\mathcal\{A\}with a fixed configurationxxinduces a distribution over learned policies\. We model the learning outcome asπ∼𝒜​\(π;x\)\.\\pi\\sim\\mathcal\{A\}\(\\pi;x\)\.Crucially, the randomness we consider is the randomness of the*learning outcome*π\\pi\(and thus ofJ​\(π\)J\(\\pi\)\) induced by training\. We formulate risk\-aware HPO as maximizing expected learning outcome while penalizing variability across learning outcomes:

x∗∈argmaxx∈𝒳​𝔼π∼𝒜​\(π;x\)​\[J​\(π\)\]−α​𝕍​a​rπ∼𝒜​\(π;x\)​\[J​\(π\)\],\\displaystyle x^\{\*\}\\in\\underset\{x\\in\\mathcal\{X\}\}\{\\mathrm\{argmax\}\}\\ \\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{A\}\(\\pi;x\)\}\\big\[J\(\\pi\)\\big\]\-\\alpha\\mathbb\{V\}ar\_\{\\pi\\sim\\mathcal\{A\}\(\\pi;x\)\}\\big\[J\(\\pi\)\\big\],\(1\)whereα≥0\\alpha\\geq 0defines the trade\-off between mean and variance\. For notational simplicity, define the mean performance

f​\(x\):=𝔼π∼𝒜​\(π;x\)​\[J​\(π\)\]\.\\displaystyle f\(x\):=\\mathbb\{E\}\_\{\\pi\\sim\\mathcal\{A\}\(\\pi;x\)\}\\big\[J\(\\pi\)\\big\]\.\(2\)
In Bayesian optimization \(BO\), we consider a sequential interaction problem with unknown objectivef:𝒳→ℝf:\\mathcal\{X\}\\to\\mathbb\{R\}\. In each BO roundtt, the algorithm choosesxt∈𝒳x\_\{t\}\\in\\mathcal\{X\}, runs training once to obtainπt∼𝒜​\(π;xt\)\\pi\_\{t\}\\sim\\mathcal\{A\}\(\\pi;x\_\{t\}\), and observes one realization of the learning outcome

yt:=J​\(πt\)=f​\(xt\)\+ξ​\(xt\),\\displaystyle y\_\{t\}:=J\(\\pi\_\{t\}\)=f\(x\_\{t\}\)\+\\xi\(x\_\{t\}\),\(3\)whereξ​\(xt\)\\xi\(x\_\{t\}\)is a zero\-mean noise term capturing the stochasticity of the learning algorithm𝒜\\mathcal\{A\}when trained with hyperparametersxtx\_\{t\}\(i\.e\., variability across independent executions of the RL training with the same HPsxtx\_\{t\}\), and is independent across roundstt\. In the following, we drop the subscriptttwhen referring to a generalxxor when its meaning is clear from the context\. Consequently,

𝕍​a​r​\[ξ​\(x\)\]=𝕍​a​rπ∼𝒜​\(π;x\)​\[J​\(π\)\]\.\\displaystyle\\mathbb\{V\}ar\\\!\\left\[\\xi\(x\)\\right\]=\\mathbb\{V\}ar\_\{\\pi\\sim\\mathcal\{A\}\(\\pi;x\)\}\\big\[J\(\\pi\)\\big\]\.\(4\)
Followingmakarova2021risk, we assume thatffbelongs to a reproducing kernel Hilbert space \(RKHS\)ℋκ\\mathcal\{H\}\_\{\\kappa\}induced by a kernelκ​\(⋅,⋅\)\\kappa\(\\cdot,\\cdot\)satisfyingκ​\(x,x′\)≤1\\kappa\(x,x^\{\\prime\}\)\\leq 1for allx,x′∈𝒳x,x^\{\\prime\}\\in\\mathcal\{X\}, and that‖f‖κ≤ℬf\\\|f\\\|\_\{\\kappa\}\\leq\\mathcal\{B\}\_\{f\}for someℬf\>0\\mathcal\{B\}\_\{f\}\>0\. We further assumeξ​\(x\)\\xi\(x\)is sub\-Gaussian with a \(possibly input\-dependent\) variance proxyρ2​\(x\)\\rho^\{2\}\(x\)uniformly bounded asρ​\(x\)∈\[ρ¯,ρ¯\]\\rho\(x\)\\in\[\\underline\{\\rho\},\\overline\{\\rho\}\]for constantsρ¯≥ρ¯\>0\\overline\{\\rho\}\\geq\\underline\{\\rho\}\>0\.

Followingsani2012risk,makarova2021riskanddai2023batch, the mean\-variance objective with variance proxyρ2​\(x\)\\rho^\{2\}\(x\)is

MV​\(x\)=f​\(x\)−α​ρ2​\(x\),\\displaystyle\\mathrm\{MV\}\(x\)=f\(x\)\-\\alpha\\rho^\{2\}\(x\),\(5\)where a fixedα≥0\\alpha\\geq 0expresses a user defined risk aversion\.

We seek a sequence of evaluations\{xt\}t=1T\\\{x\_\{t\}\\\}\_\{t=1\}^\{T\}that attains high values of the risk\-averse objectiveMV​\(x\)\\mathrm\{MV\}\(x\)overTTBO rounds\. Since each roundttcollectsktk\_\{t\}independent samples \(training runs\) usingxtx\_\{t\}, we evaluate performance via the sample\-count cumulative regret

RT:=∑t=1Tkt​\(MV​\(x∗\)−MV​\(xt\)\),wherex∗∈arg⁡maxx∈𝒳⁡MV​\(x\)\.\\displaystyle R\_\{T\}:=\\sum\_\{t=1\}^\{T\}k\_\{t\}\\Big\(\\mathrm\{MV\}\(x^\{\*\}\)\-\\mathrm\{MV\}\(x\_\{t\}\)\\Big\),\\quad\\text\{where\}\\quad x^\{\*\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\mathrm\{MV\}\(x\)\.\(6\)

## 3Related work

This section gives a brief overview of BO for hyperparameter optimization \(HPO\), focusing on settings with stochastic and configuration\-dependent outcomes, and then connects these ideas to HPO for RL, where training variability is often substantial\.

Grid search and random search are simple baselines for HPO, but they become inefficient as the dimensionality of the HP space grows\(bergstra\-jmlr12a\)\. Bayesian optimization\(garnett\-book23a\)improves sample efficiency for costly black\-box objectives by fitting a surrogate model and selecting evaluations sequentially\(bergstra\-nips11a;snoek\-nips12a\-replace;springenberg\-nips16a\)\. It is the backbone of many widely used HPO approaches\(akiba\-kdd19a;lindauer\-jmlr22a;song2024vizier\)\.

The substantial run\-to\-run variability of RL training has been documented in prior work\(henderson\-aaai18a;obandoceron\-rlj24\)and motivates systematic and efficient approaches to HPO\. HPO for RL is an emerging field \(seeparkerholder\-jair22afor an overview\), but poses challenges due to high computational overhead and stochastic learning outcomes\(agarwal2021deep;eimer\-icml23a\)arising from training instabilities\(dierkes\-ewrl25\)\. In this context, optimizing expected performance alone, often approximated via a small number of training runs\(parkerholder\-neurips20a;wan\-automl22a\), may not capture reliability across runs\. Our goal is to provide an objective and optimization strategy that better targets reliable HP configurations in RL\.

Many classical BO methods assume homoscedastic noise and mismatched noise assumptions can degrade BO performance\. Heteroscedastic Gaussian process models capture input\-dependent noise explicitly\(binois2018practical;binois2019replication\), but modeling variance alone does not prevent BO from selecting configurations with undesirable high variability in the learning outcomes\. To address this, risk\-aware BO methods optimize objectives that explicitly trade off mean performance and variability\. Prior work considers mean\-variance objectives for heteroscedastic BO\(makarova2021risk;dai2023batch\)\. In particular, RAHBO\(makarova2021risk\)uses a fixed evaluation budget per configuration to estimate variability, which is inefficient since it allocates significant resources to evaluate under\-performing configurations\.dai2023batchaddresses adaptive evaluation in a batch setting\. In this paper, we evaluate RAHBO for HPO for RL problems and extend it with an adaptive evaluation strategy that speeds up the optimization process across many HPO tasks\.

## 4Method

This section describes our approach for risk\-aware HPO under heteroscedastic training outcomes\. We begin with the essential modeling and acquisition components of RAHBO\(makarova2021risk\), and then present ERAHBO, an adaptive resampling strategy, together with a corresponding sublinear regret bound\.

### 4\.1RAHBO: risk\-averse heteroscedastic Bayesian optimization

We briefly summarize the components of risk\-averse heteroscedastic Bayesian optimization \(RAHBO\)\(makarova2021risk\)that we build on\. The key idea of RAHBO is to model both the performanceffand variance proxyρ2\\rho^\{2\}as separate Gaussian processes \(GPs\) to derive confidence bounds for a risk\-averse variant of the Gaussian process upper confidence bound \(GP\-UCB\) algorithm\(srinivas\-icml10a\)\.

RAHBO obtains mean and variance estimation to condition the GPs by repeatedly evaluating a configuration\. In iterationtt, it selects a configurationxtx\_\{t\}and performs a fixed numberkkof independent evaluations, yielding observations\{yti\}i=1k\\left\\\{y\_\{t\}^\{i\}\\right\\\}\_\{i=1\}^\{k\}\. The sample mean and variance are estimated as

m^​\(xt\)=1k​∑i=1kyt\(i\),s^2​\(xt\)=1k−1​∑i=1k\(yt\(i\)−m^​\(xt\)\)2,\\hat\{m\}\(x\_\{t\}\)=\\frac\{1\}\{k\}\\sum\_\{i=1\}^\{k\}y\_\{t\}^\{\(i\)\},\\quad\\hat\{s\}^\{2\}\(x\_\{t\}\)=\\frac\{1\}\{k\-1\}\\sum\_\{i=1\}^\{k\}\(y\_\{t\}^\{\(i\)\}\-\\hat\{m\}\(x\_\{t\}\)\)^\{2\},\(7\)which serve as noisy observations off​\(xt\)f\(x\_\{t\}\)andρ2​\(xt\)\\rho^\{2\}\(x\_\{t\}\)to condition the two GPs\.

LetUCBtf​\(x\)\\mathrm\{UCB\}\_\{t\}^\{f\}\(x\)denote an upper confidence bound forf​\(x\)f\(x\), andLCBtvar​\(x\)\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{var\}\}\(x\)a lower confidence bound forρ2​\(x\)\\rho^\{2\}\(x\), constructed from the two GP posteriors with appropriately chosen confidence parameters as inmakarova2021risk\. RAHBO selects the next query by maximizing an upper bound onMV​\(x\)\\mathrm\{MV\}\(x\),

xt∈arg⁡maxx∈𝒳⁡UCBtf​\(x\)−α​LCBtvar​\(x\)\.\\displaystyle x\_\{t\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\ \\mathrm\{UCB\}\_\{t\}^\{f\}\(x\)\\;\-\\;\\alpha\\,\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{var\}\}\(x\)\.\(8\)
Under standard regularity assumptions, RAHBO achieves sublinear regret for the mean\-variance objective with a fixed sample budgetkkper iteration\. For more details, see Appendix[A](https://arxiv.org/html/2607.26680#A1)\.

Our method retains the same modeling and risk\-aware acquisition structure, but replaces the fixed budgetkkwith an adaptive re\-sampling strategy that allocates evaluations based on estimated uncertainty, improving practical efficiency in high\-cost settings such as RL\.

### 4\.2ERAHBO: efficient risk\-averse heteroscedastic Bayesian optimization

To resolve the limitation of RAHBO, we propose a confidence\-based adaptive rule to automatically determine replications fork∈\[km​i​n,km​a​x\]k\\in\[k\_\{min\},k\_\{max\}\]in each BO iteration\.

#### 4\.2\.1Confidence\-based resampling

While repeated sampling improves the estimation accuracy of both the mean and variance, it is not necessary to improve the estimate of the configuration once it can be certified as suboptimal\. We construct the high\-probability confidence bounds for the MV objective as

UCBtMV​\(x\)\\displaystyle\\mathrm\{UCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\):=UCBtf​\(x\)−α​LCBtvar​\(x\),LCBtMV​\(x\)\\displaystyle:=\\mathrm\{UCB\}\_\{t\}^\{f\}\(x\)\-\\alpha\\,\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{var\}\}\(x\),\\quad\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\):=LCBtf​\(x\)−α​UCBtvar​\(x\)\.\\displaystyle:=\\mathrm\{LCB\}\_\{t\}^\{f\}\(x\)\-\\alpha\\,\\mathrm\{UCB\}\_\{t\}^\{\\mathrm\{\\mathrm\{var\}\}\}\(x\)\.\(9\)The core idea of ERAHBO is to stop re\-sampling a configuration once we know it is worse than the incumbent with high probability\.

##### Incumbent lower bound

We define the incumbent lower bound at iterationttas

Bt:=maxx∈𝒟t−1⁡LCBtMV​\(x\),B\_\{t\}:=\\max\_\{x\\in\\mathcal\{D\}\_\{t\-1\}\}\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\),\(10\)where𝒟t−1\\mathcal\{D\}\_\{t\-1\}denotes the set of previously evaluated configurations\. The quantityBtB\_\{t\}represents a high\-confidence lower bound on the best MV value observed so far and serves as a conservative benchmark against which newly queried configurations are compared\.

##### Stopping criterion

At iterationtt, the algorithm selects a configuration

xt∈arg⁡maxx∈𝒳⁡UCBtMV​\(x\),x\_\{t\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\mathrm\{UCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\),\(11\)and begins collecting repeated evaluations atxtx\_\{t\}\. Letkkdenote the current number of samples collected atxtx\_\{t\}\. Askkincreases, the uncertainty of the mean\-variance estimate decreases due to the effective observation noise scaling asρ2​\(xt\)/k\\rho^\{2\}\(x\_\{t\}\)/k, leading to progressively tighter confidence bounds\.

Sampling atxtx\_\{t\}is terminated once the following condition is satisfied:

UCBtMV​\(xt;k\)≤Bt,\\mathrm\{UCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\_\{t\};k\)\\leq B\_\{t\},\(12\)or once a predefined maximum number of evaluationskmaxk\_\{\\max\}is reached\. This stopping rule admits a clear interpretation\. If even the optimistic estimate of the MV objective atxtx\_\{t\}is no larger than the pessimistic estimate of the best competing configuration, then with high probability,xtx\_\{t\}cannot outperform the incumbent and further replication is unnecessary\. Conversely, as long as the confidence interval ofMV​\(xt\)\\mathrm\{MV\}\(x\_\{t\}\)overlaps with the incumbent lower bound, additional evaluations may be informative and are therefore allocated\. Appendix[B](https://arxiv.org/html/2607.26680#A2)shows that if a configuration is suboptimal relative to the incumbent lower bound, then ERAHBO will stop sampling it after finitely many samples\.

#### 4\.2\.2Sublinear regret guarantee

We show that the sublinear regret guarantees of RAHBO\(makarova2021risk\)carry over to a setting with varying replication counts\. Under the standard RKHS smoothness and sub\-Gaussian noise assumptions used in RAHBO, ERAHBO preserves the sublinear regret guarantees of RAHBO when the number of replications per BO round is allowed to vary but remains uniformly bounded,kt∈\[kmin,kmax\]k\_\{t\}\\in\[k\_\{\\min\},k\_\{\\max\}\]\. In particular, with high probability, the sample\-count cumulative regret satisfies

RT=O~​\(kmax​T​γT\+α​kmax​T​ΓT\),R\_\{T\}=\\tilde\{O\}\\\!\\left\(k\_\{\\max\}\\sqrt\{T\\gamma\_\{T\}\}\+\\alpha k\_\{\\max\}\\sqrt\{T\\Gamma\_\{T\}\}\\right\),\(13\)whereγT\\gamma\_\{T\}andΓT\\Gamma\_\{T\}are the information\-gain terms for the mean and variance surrogate models, respectively\. Thus, bounded adaptive replication does not change the no\-regret behavior: whenever the corresponding RAHBO information\-gain terms are sublinear, ERAHBO has vanishing average sample\-count regret\. Appendix[A](https://arxiv.org/html/2607.26680#A1)gives the full theorem statement, assumptions, and proof\.

## 5Experiments

We validate our approach on three popular RL algorithms \(DQN\(mnih\-nature15a\), SAC\(haarnoja\-icml18a\), and PPO\(schulman\-arxiv17a\)\) on Brax\(freeman\-neurips21a\), XLand\-Minigrid\(nikulin2023\-neurips23\)and Classic Control environments\(gymnax2022github\)\.

BO baselines\.\\textbf\{BO baselines\}\.We compare our method against two baselines\. GP\-UCB\(srinivas\-icml10a\)implemented by the work ofmakarova2021riskis our risk\-neutral baseline\. RAHBO\(makarova2021risk\)is the state\-of\-the\-art risk\-averse BO algorithm in our problem setting\. For GP\-UCB, we usek=20k=20observations per configuration; for RAHBO, we use two variants,k=2k=2andk=20k=20; and ERAHBO starts withkmin=2k\_\{\\min\}=2and resamples each configuration until \([12](https://arxiv.org/html/2607.26680#S4.E12)\) is satisfied orkmax=20k\_\{\\max\}=20is reached\. For RAHBO and ERAHBO, we use a heteroscedastic GP for modelingf​\(x\)f\(x\)and a homoscedastic GP forρ2​\(x\)\\rho^\{2\}\(x\)\. We follow common practices by settingβt=2\.5\\beta\_\{t\}=2\.5\. We preprocess the dataset using the outcome processing proposed insong2024vizierand chooseα=1\\alpha=1for the processed data to have a meaningful mean–variance trade‑off\. Generally, the MV objective is scale sensitive \(multiplying the performance by a positive scalar will change the optimal configuration\) which makes online outcome processing more difficult\. For confidence\-based resampling, we setβstop=1\\beta\_\{\\text\{stop\}\}=1for \([12](https://arxiv.org/html/2607.26680#S4.E12)\) to allow optimistic stopping\. Before the BO procedure, we determine the GP hyperparameters by maximizing the marginal likelihood over55Sobol\-sampled initial points that are the same for all experiments\. We repeat each experiment2020times with new initial points for every repetition\. To tackle the high\-dimensional search space, we apply the GP kernel hyperparameter prior that scales with the dimensionality of the search space, as proposed inhvarfner2024vanilla\.

RL Tasks\.We use ARLBench\(becktepe2024arlbench\)to produce performance datasets on which we run our experiments\. In total, we use 5 environments for DQN, 10 for PPO and 4 for SAC\. For each environment, we compute a dataset consisting of512512configurations with5050seeds each for more repeatable experimentation\.111The code and the dataset can be found at[https://github\.com/LUH\-AI/Efficient\-Risk\-Averse\-BO](https://github.com/LUH-AI/Efficient-Risk-Averse-BO)\.The full algorithm\-environment combination is documented in Appendix[C\.1](https://arxiv.org/html/2607.26680#A3.SS1)\. We use the configuration spaces proposed in ARLBench and its default network architectures\. As the performance objective, we use the mean evaluation return across 128 evaluation episodes at the end of training\. Since environments differ in reward scales, we report the normalized regret to the average score of BO’s initial points in each environment’s dataset\. We report additional empirical results in Appendix[C](https://arxiv.org/html/2607.26680#A3)\.

### 5\.1Can ERAHBO find reliable configurations?

![Refer to caption](https://arxiv.org/html/2607.26680v1/x2.png)Figure 2:Mean\-variance regret ranks aggregated by domain with lines and shaded area showing the mean and standard error, respectively\. ERAHBO performs best overall\. We observe different optimal values ofkkin RAHBO across domains\.We optimize the hyperparameters of PPO, DQN and SAC to see if ERAHBO can outperform RAHBO through its adaptive sampling mechanism\. Figure[2](https://arxiv.org/html/2607.26680#S5.F2)shows that both RAHBO and ERAHBO outrank the GP\-UCB baseline, but that the best value for RAHBO’skkvaries across environments\. On Brax for example,k=20k=20outperformsk=2k=2while the opposite is true in XLand\. The environments ERAHBO does not perform well on are predominantly from XLand, which contains environments for which we see only very few good performances overall\. This makes it hard to find a good incumbent and leads to many repetitions preventing exploration\.

Overall, ERAHBO outperforms both RAHBO variants in a total of77out of1919algorithm\-environment pairs, and at least one RAHBO variation1616out of1919times\. In Table[1](https://arxiv.org/html/2607.26680#S5.T1), the Wilcoxon signed\-rank test shows a statistically significant improvement of ERAHBO over RAHBO withk=20k=20and GP\-UCB\. This means the adaptive sampling can automatically strike a balance between the different versions of RAHBO and eliminates the need for manually selectingkk\. We document all rank metrics\-related results in Appendix[C\.2](https://arxiv.org/html/2607.26680#A3.SS2), including a comparison of ERAHBO with RAHBO using different repetitionskk\.

Table 1:Mean±\\pmstandard error of algorithm rank across experiments \(lower is better\)\. Bold values are not statistically significantly worse than best\.
### 5\.2Is ERAHBO making HPO more sample efficient?

ERAHBO not only balances additional evaluations for the best performance tradeoff, but it is also more efficient in terms of evaluations than RAHBO or GP\-UCB\. In Table[2](https://arxiv.org/html/2607.26680#S5.T2), we report the evaluation number where the algorithms achieve a regret threshold measured as the percent of the initial design’s regret, and we count the tasks where all algorithms reach this threshold for easier comparability\. ERAHBO achieves sample efficiency comparable to RAHBO withk=2k=2, reaching the regret thresholds after a similar number of evaluations\. However, as discussed above, RAHBO withk=2k=2yields worse configurations after the full evaluation budget\. Compared with RAHBO withk=20k=20and GP\-UCB, ERAHBO reaches almost all the regret thresholds significantly faster\.

Table 2:Mean±\\pmstandard error number of evaluations needed to improve over regret thresholds\. We average tasks where all methods reach the threshold \(count per method in brackets\)\.![Refer to caption](https://arxiv.org/html/2607.26680v1/x3.png)Figure 3:Domain\-aggregated normalized regret over evaluation budgets\. Lines and shaded areas show the inter\-quantile mean \(IQM\) and95%95\\%bootstrapped confidence interval \(CI\), respectively\.Furthermore, Figure[3](https://arxiv.org/html/2607.26680#S5.F3)shows normalized mean regret for all domains\. Compared to GP\-UCB, both ERAHBO and RAHBO can have better anytime performance\. Therefore, they are better suited to low\-budget HPO, as is often necessary in RL\. As in the overall ranks, we observekkbeing an essential HP for RAHBO\. With a lowerkk, RAHBO is very efficient for small budgets, but cannot effectively utilize larger optimization budgets\. Withk=20k=20, on the other hand, RAHBO becomes inefficient with small budgets\. ERAHBO can adapt to different budgets without HPO for its own HPs, making it a more flexible method\. We note that the pattern depends on the risk\-sensitivity parameterα\\alpha, since large values can prevent BO from exploring high\-mean performance configurations\. More detailed results are available in Appendix[C\.3](https://arxiv.org/html/2607.26680#A3.SS3)and[C\.4](https://arxiv.org/html/2607.26680#A3.SS4)\.

### 5\.3Does the adaptive sampling focus on well\-performing configurations?

Beyond being more efficient than RAHBO, we want to verify that ERAHBO actually prioritizes promising configurations and spends very few evaluations on poorly performing ones\. Figure[4](https://arxiv.org/html/2607.26680#S5.F4)shows the distribution of repetitions across all evaluations\. These results indicate that ERAHBO allocates more budget to better configurations\. Additionally, we note that schedulingβ\\betain the incumbent lower bound in \([10](https://arxiv.org/html/2607.26680#S4.E10)\) further improves the performance of ERAHBO \(see Appendix[C\.5](https://arxiv.org/html/2607.26680#A3.SS5)\)\.

![Refer to caption](https://arxiv.org/html/2607.26680v1/x4.png)Figure 4:Repetition numbers in dataset experiments\.Left: Compared with RAHBO using fixed sampling repetition, ERAHBO rejects the majority of configurations without spending the full budget\.Right: ERAHBO invests more repetition in promising configurations with higher MV scores, demonstrating adaptivity through the confidence\-based resampling behavior\.

## 6Conclusion

We identify variability between repeated runs as a key difficulty factor for HPO in RL and propose to use risk\-aware optimization to find an ideal variability\-performance tradeoff\. To do so efficiently for computationally expensive RL algorithms, we introduce ERAHBO, an adaptive sampling mechanism that automatically adds more samples only in regions of the search space that show high uncertainty\. We provide sublinear regret guarantees and demonstrate empirically that ERAHBO improves upon its baselines in terms of overall performance and efficiency\. Furthermore, the ERAHBO successfully identifies which configurations to prioritize and which to discard early\.

We show that ERAHBO can improve the practical efficiency of risk\-aware hyperparameter optimization by adaptively allocating samples to configurations where uncertainty matters most\. However, our approach optimizes a mean\-variance objective, which is only one notion of risk: the risk parameterα\\alphais scale\-sensitive and does not directly target tail events or failure probabilities\. Moreover, our regret guarantee is a conservative worst\-case bound over all sample\-count scheduleskt∈\[kmin,kmax\]k\_\{t\}\\in\[k\_\{\\min\},k\_\{\\max\}\]rather than a tight characterization of the specific adaptive rule\. Finally, our empirical results rely on offline datasets of learning outcomes; while this enables broad and reproducible comparisons, it is not identical to fully online HPO with fresh training runs\.

While we demonstrate the benefits of risk\-aware HPO and ERAHBO’s adaptive budget allocation for RL algorithms, our empirical evaluation shows that not all environments benefit equally, as we see in the XLand environments\. The dataset we release with this paper will facilitate further research into the factors that influence risk in different RL settings\. This will help the community and us to further develop adaptive risk\-aware HPO methods for the wide range of RL task settings\. We see ERAHBO’s sampling strategy as a first step in this direction\.

## Appendix ARegret bound for ERAHBO

We follow the setup ofmakarova2021risk\. Throughout, letkt:=k​\(xt\)∈\[kmin,kmax\]k\_\{t\}:=k\(x\_\{t\}\)\\in\[k\_\{\\min\},k\_\{\\max\}\]withkmin≥2k\_\{\\min\}\\geq 2, so that the unbiased sample variance is well\-defined\. We assume normalized kernels,κ​\(x,x\)≤1\\kappa\(x,x\)\\leq 1andκvar​\(x,x\)≤1\\kappa^\{\\mathrm\{var\}\}\(x,x\)\\leq 1for allx∈𝒳x\\in\\mathcal\{X\}\. We consider the BO observation model \(Eq\. \([3](https://arxiv.org/html/2607.26680#S2.E3)\)\) with heteroscedastic noise, and denote byμt−1f​\(x∣Σ\)\\mu^\{f\}\_\{t\-1\}\(x\\mid\\Sigma\)andσt−1f​\(x∣Σ\)\\sigma^\{f\}\_\{t\-1\}\(x\\mid\\Sigma\)the GP posterior mean and standard deviation of the mean model with noise matrixΣ\\Sigma\.

###### Lemma 1\(Lemma 7 inkirschner2018information\)\.

Letf∈ℋκf\\in\\mathcal\{H\}\_\{\\kappa\}, and letμt​\(⋅\)\\mu\_\{t\}\(\\cdot\)andσt2​\(⋅\)\\sigma\_\{t\}^\{2\}\(\\cdot\)be the GP posterior mean and varianceλ\>0\\lambda\>0\. Assume that the observations\(xt,yt\)t≥1\(x\_\{t\},y\_\{t\}\)\_\{t\\geq 1\}satisfy Eq\. \([3](https://arxiv.org/html/2607.26680#S2.E3)\)\. Then for allt≥1t\\geq 1andx∈𝒳x\\in\\mathcal\{X\}, with probability at least1−δ1\-\\delta,

\|μt−1​\(x\)−f​\(x\)\|≤\(2​ln⁡\(det\(λ​Σt\+Kt\)1/2δ​det\(λ​Σt\)1/2\)\+λ​‖f‖κ\)⏟:=βt​σt−1​\(x\)\.\\displaystyle\|\\mu\_\{t\-1\}\(x\)\-f\(x\)\|\\leq\\underbrace\{\\left\(\\sqrt\{2\\ln\\\!\\left\(\\frac\{\{\\det\(\\lambda\\Sigma\_\{t\}\+K\_\{t\}\)\}^\{1/2\}\}\{\\delta\\,\\det\(\\lambda\\Sigma\_\{t\}\)^\{1/2\}\}\\right\)\}\+\\sqrt\{\\lambda\}\\\|f\\\|\_\{\\kappa\}\\right\)\}\_\{:=\\beta\_\{t\}\}\\,\\sigma\_\{t\-1\}\(x\)\.\(14\)

In each BO roundtt, ERAHBO collectsktk\_\{t\}independent samples atxtx\_\{t\}, denoted\{yt\(i\)\}i=1kt\\\{y\_\{t\}^\{\(i\)\}\\\}\_\{i=1\}^\{k\_\{t\}\}, and formsm^​\(xt\):=kt−1​∑i=1ktyt\(i\)\\hat\{m\}\(x\_\{t\}\):=k\_\{t\}^\{\-1\}\\sum\_\{i=1\}^\{k\_\{t\}\}y\_\{t\}^\{\(i\)\}\. Using Lemma[1](https://arxiv.org/html/2607.26680#Thmlemma1)for the mean GP posterior, define

UCBtf​\(x\)\\displaystyle\\mathrm\{UCB\}^\{f\}\_\{t\}\(x\):=μt−1f​\(x∣Σ^t−1\)\+βtf​σt−1f​\(x∣Σ^t−1\),\\displaystyle:=\\mu^\{f\}\_\{t\-1\}\(x\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\)\+\\beta\_\{t\}^\{f\}\\,\\sigma^\{f\}\_\{t\-1\}\(x\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\),\(15\)LCBtf​\(x\)\\displaystyle\\mathrm\{LCB\}^\{f\}\_\{t\}\(x\):=μt−1f​\(x∣Σ^t−1\)−βtf​σt−1f​\(x∣Σ^t−1\)\.\\displaystyle:=\\mu^\{f\}\_\{t\-1\}\(x\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\)\-\\beta\_\{t\}^\{f\}\\,\\sigma^\{f\}\_\{t\-1\}\(x\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\)\.\(16\)
We make the same smoothness assumption on the variance proxy as inmakarova2021risk\.

###### Assumption 1\(Assumption 1 inmakarova2021risk\)\.

The variance\-proxyρ2​\(x\)\\rho^\{2\}\(x\)belongs to an RKHS induced by some kernelκvar\\kappa^\{\\text\{var\}\}, i\.e\.,ρ2∈ℋκvar\\rho^\{2\}\\in\\mathcal\{H\}\_\{\\kappa^\{\\text\{var\}\}\}, and its RKHS norm is bounded‖ρ2‖κvar≤Bvar\\\|\\rho^\{2\}\\\|\_\{\\kappa^\{\\text\{var\}\}\}\\leq B\_\{\\text\{var\}\}for some finiteBvar\>0B\_\{\\text\{var\}\}\>0\. Moreover, the noiseξ​\(x\)\\xi\(x\)in Eq\. \([3](https://arxiv.org/html/2607.26680#S2.E3)\) is strictlyρ​\(x\)\\rho\(x\)\-sub\-Gaussian, i\.e\.,Var​\[ξ​\(x\)\]=ρ2​\(x\)\\text\{Var\}\[\\xi\(x\)\]=\\rho^\{2\}\(x\)for everyx∈𝒳x\\in\\mathcal\{X\}\.

###### Assumption 2\(Analogue of Assumption 2 inmakarova2021risk\)\.

Letℱt−1\\mathcal\{F\}\_\{t\-1\}denote the BO history before roundtt\. The noiseη​\(xt,kt\)\\eta\(x\_\{t\},k\_\{t\}\)ins^2​\(xt\)=ρ2​\(xt\)\+η​\(xt,kt\)\\hat\{s\}^\{2\}\(x\_\{t\}\)=\\rho^\{2\}\(x\_\{t\}\)\+\\eta\(x\_\{t\},k\_\{t\}\)is conditionallyρη​\(xt,kt\)\\rho\_\{\\eta\}\(x\_\{t\},k\_\{t\}\)\-sub\-Gaussian givenℱt−1\\mathcal\{F\}\_\{t\-1\},xtx\_\{t\}, andktk\_\{t\}, with knownρη2​\(xt,kt\)\\rho\_\{\\eta\}^\{2\}\(x\_\{t\},k\_\{t\}\)\. The realizations\{η​\(xt,kt\)\}t≥1\\\{\\eta\(x\_\{t\},k\_\{t\}\)\\\}\_\{t\\geq 1\}are conditionally independent acrossttgiven the corresponding histories and selected pairs\(xt,kt\)\(x\_\{t\},k\_\{t\}\)\.

In the variable\-sample setting, the variance\-observation proxy may depend on both the query point and the replication count, i\.e\.,ρη2​\(xt,kt\)\\rho\_\{\\eta\}^\{2\}\(x\_\{t\},k\_\{t\}\)\. The regret analysis only requires a uniform bound on these proxies\. Thus, it suffices to assume that there existsℛ2\\mathcal\{R\}^\{2\}such that

ℛ2≥supx∈𝒳,k∈\[kmin,kmax\]ρη2​\(x,k\),ℛ2=2​ρ¯4kmin−1​is valid under strict sub\-Gaussianity\.\\mathcal\{R\}^\{2\}\\geq\\sup\_\{x\\in\\mathcal\{X\},\\;k\\in\[k\_\{\\min\},k\_\{\\max\}\]\}\\rho\_\{\\eta\}^\{2\}\(x,k\),\\qquad\\mathcal\{R\}^\{2\}=\\frac\{2\\bar\{\\rho\}^\{4\}\}\{k\_\{\\min\}\-1\}\\ \\text\{is valid under strict sub\-Gaussianity\}\.
Letμt−1var\\mu^\{\\mathrm\{var\}\}\_\{t\-1\}andσt−1var\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}denote the variance\-GP posterior mean and standard deviation built withΣt−1var:=diag​\(ρη2​\(x1,k1\),…,ρη2​\(xt−1,kt−1\)\)\\Sigma^\{\\mathrm\{var\}\}\_\{t\-1\}:=\\mathrm\{diag\}\(\\rho\_\{\\eta\}^\{2\}\(x\_\{1\},k\_\{1\}\),\\ldots,\\rho\_\{\\eta\}^\{2\}\(x\_\{t\-1\},k\_\{t\-1\}\)\)\. Using Lemma[1](https://arxiv.org/html/2607.26680#Thmlemma1)for the variance GP posterior, define

UCBtvar​\(x\)\\displaystyle\\mathrm\{UCB\}^\{\\mathrm\{var\}\}\_\{t\}\(x\):=μt−1var​\(x\)\+βtvar​σt−1var​\(x\),\\displaystyle:=\\mu^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\)\+\\beta\_\{t\}^\{\\mathrm\{var\}\}\\,\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\),\(17\)LCBtvar​\(x\)\\displaystyle\\mathrm\{LCB\}^\{\\mathrm\{var\}\}\_\{t\}\(x\):=μt−1var​\(x\)−βtvar​σt−1var​\(x\)\.\\displaystyle:=\\mu^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\)\-\\beta\_\{t\}^\{\\mathrm\{var\}\}\\,\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\)\.\(18\)
Followingmakarova2021risk, we construct

Σ^t−1:=diags<t​\(min⁡\{UCBt−1var​\(xs\),ρ¯2\}ks\)\.\\displaystyle\\widehat\{\\Sigma\}\_\{t\-1\}:=\\mathrm\{diag\}\_\{s<t\}\\\!\\left\(\\frac\{\\min\\\{\\mathrm\{UCB\}^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\_\{s\}\),\\overline\{\\rho\}^\{2\}\\\}\}\{k\_\{s\}\}\\right\)\.\(19\)On the simultaneous variance\-confidence event,ρ2​\(xs\)≤UCBt−1var​\(xs\)\\rho^\{2\}\(x\_\{s\}\)\\leq\\mathrm\{UCB\}^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\_\{s\}\)for alls≤t−1s\\leq t\-1, and by assumptionρ2​\(xs\)≤ρ¯2\\rho^\{2\}\(x\_\{s\}\)\\leq\\overline\{\\rho\}^\{2\}\. Hence the construction above is used as a conservative noise matrix for the sample\-mean observations\. Equivalently, throughout the proof we condition on the event that

ρ2​\(xs\)ks≤min⁡\{UCBt−1var​\(xs\),ρ¯2\}ks,s<t,\\frac\{\\rho^\{2\}\(x\_\{s\}\)\}\{k\_\{s\}\}\\leq\\frac\{\\min\\\{\\mathrm\{UCB\}^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\_\{s\}\),\\overline\{\\rho\}^\{2\}\\\}\}\{k\_\{s\}\},\\qquad s<t,so Lemma[1](https://arxiv.org/html/2607.26680#Thmlemma1)applies to the mean GP with noise matrixΣ^t−1\\widehat\{\\Sigma\}\_\{t\-1\}\.

For convenience, defineNT:=∑t=1TktN\_\{T\}:=\\sum\_\{t=1\}^\{T\}k\_\{t\}andβ¯Tℓ:=max1≤s≤T⁡βsℓ\\bar\{\\beta\}\_\{T\}^\{\\ell\}:=\\max\_\{1\\leq s\\leq T\}\\beta\_\{s\}^\{\\ell\},ℓ∈\{f,var\}\\ell\\in\\\{f,\\mathrm\{var\}\\\}\.

We use the sequence\-based information gain terms

γ¯T\\displaystyle\\overline\{\\gamma\}\_\{T\}:=maxx1,…,xT∈𝒳k1,…,kT∈\[kmin,kmax\]​∑t=1T12​ln⁡\(1\+\(σt−1f\)2​\(xt∣Dt−1\)ρ¯2/kt\),\\displaystyle:=\\max\_\{\\begin\{subarray\}\{c\}x\_\{1\},\\ldots,x\_\{T\}\\in\\mathcal\{X\}\\\\ k\_\{1\},\\ldots,k\_\{T\}\\in\[k\_\{\\min\},k\_\{\\max\}\]\\end\{subarray\}\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{2\}\\ln\\\!\\left\(1\+\\frac\{\\bigl\(\\sigma^\{f\}\_\{t\-1\}\\bigr\)^\{2\}\(x\_\{t\}\\mid D\_\{t\-1\}\)\}\{\\overline\{\\rho\}^\{2\}/k\_\{t\}\}\\right\),\(20\)ΓT\\displaystyle\\Gamma\_\{T\}:=maxx1,…,xT∈𝒳k1,…,kT∈\[kmin,kmax\]​∑t=1T12​ln⁡\(1\+\(σt−1var\)2​\(xt\)ρη,t2\)\.\\displaystyle:=\\max\_\{\\begin\{subarray\}\{c\}x\_\{1\},\\ldots,x\_\{T\}\\in\\mathcal\{X\}\\\\ k\_\{1\},\\ldots,k\_\{T\}\\in\[k\_\{\\min\},k\_\{\\max\}\]\\end\{subarray\}\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{2\}\\ln\\\!\\left\(1\+\\frac\{\\bigl\(\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\\bigr\)^\{2\}\(x\_\{t\}\)\}\{\\rho\_\{\\eta,t\}^\{2\}\}\\right\)\.\(21\)HereDt−1:=diag​\(ρ¯2/k1,…,ρ¯2/kt−1\)D\_\{t\-1\}:=\\mathrm\{diag\}\(\\overline\{\\rho\}^\{2\}/k\_\{1\},\\ldots,\\overline\{\\rho\}^\{2\}/k\_\{t\-1\}\)\.

We now adapt the regret analysis ofmakarova2021riskto variable sample counts\.

###### Theorem 1\.

Consider anyf∈ℋκf\\in\\mathcal\{H\}\_\{\\kappa\}with‖f‖κ≤Bf\\\|f\\\|\_\{\\kappa\}\\leq B\_\{f\}, and the BO observation model in Eq\. \([3](https://arxiv.org/html/2607.26680#S2.E3)\) with an unknown variance proxyρ2​\(x\)\\rho^\{2\}\(x\)that satisfies Assumptions[1](https://arxiv.org/html/2607.26680#Thmassumption1)and[2](https://arxiv.org/html/2607.26680#Thmassumption2)\. Let\{xt\}t=1T\\\{x\_\{t\}\\\}\_\{t=1\}^\{T\}denote the sequence of query points selected by ERAHBO overTTBO rounds, where in roundttthe algorithm collectskt∈\[kmin,kmax\]k\_\{t\}\\in\[k\_\{\\min\},k\_\{\\max\}\]samples atxtx\_\{t\}\. We assume that the aggregated observations used to update the mean and variance GPs satisfy the observation models stated above; in particular, this holds whenktk\_\{t\}is fixed before observing the samples in roundtt\. Let\{βtf\}t=1T\\\{\\beta\_\{t\}^\{f\}\\\}\_\{t=1\}^\{T\}and\{βtvar\}t=1T\\\{\\beta\_\{t\}^\{\\mathrm\{var\}\}\\\}\_\{t=1\}^\{T\}be defined according to Lemma[1](https://arxiv.org/html/2607.26680#Thmlemma1)\(withλ=1\\lambda=1\)\. Setρ​\(⋅\)∈\[ρ¯,ρ¯\]\\rho\(\\cdot\)\\in\[\\underline\{\\rho\},\\overline\{\\rho\}\]and letℛ2\\mathcal\{R\}^\{2\}be any uniform bound on the variance\-GP observation proxies\. Then, with probability at least1−2​δ1\-2\\delta, for allT≥1T\\geq 1,

RT≤2​β¯Tf​kmax​2​T​γ¯Tln⁡\(1\+kmax/ρ¯2\)\+2​α​β¯Tvar​kmax​2​T​ΓTln⁡\(1\+ℛ−2\),\\displaystyle R\_\{T\}\\;\\leq\\;2\\,\\bar\{\\beta\}^\{f\}\_\{T\}\\,k\_\{\\max\}\\,\\sqrt\{\\frac\{2T\\,\\overline\{\\gamma\}\_\{T\}\}\{\\ln\\\!\\bigl\(1\+k\_\{\\max\}/\\overline\{\\rho\}^\{2\}\\bigr\)\}\}\\;\+\\;2\\,\\alpha\\,\\bar\{\\beta\}\_\{T\}^\{\\mathrm\{var\}\}\\,k\_\{\\max\}\\,\\sqrt\{\\frac\{2T\\,\\Gamma\_\{T\}\}\{\\ln\\\!\\bigl\(1\+\\mathcal\{R\}^\{\-2\}\\bigr\)\}\},\(22\)whereβ¯Tf:=max1≤s≤T⁡βsf\\bar\{\\beta\}\_\{T\}^\{f\}:=\\max\_\{1\\leq s\\leq T\}\\beta\_\{s\}^\{f\},β¯Tvar:=max1≤s≤T⁡βsvar\\bar\{\\beta\}\_\{T\}^\{\\mathrm\{var\}\}:=\\max\_\{1\\leq s\\leq T\}\\beta\_\{s\}^\{\\mathrm\{var\}\}, andγ¯T\\overline\{\\gamma\}\_\{T\}andΓT\\Gamma\_\{T\}are defined in \([20](https://arxiv.org/html/2607.26680#A1.E20)\)–\([21](https://arxiv.org/html/2607.26680#A1.E21)\)\.

###### Proof\.

The proof follows the same steps as Appendix A\.4 inmakarova2021risk, with the modifications needed for variable sample counts\.

Step 1 \(Confidence bounds forMV\\mathrm\{MV\}\)\.By the same argument as inmakarova2021risk, with probability at least1−2​δ1\-2\\delta,

LCBtMV​\(x\)≤MV​\(x\)≤UCBtMV​\(x\),∀x∈𝒳,t≥1,\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\)\\leq\\mathrm\{MV\}\(x\)\\leq\\mathrm\{UCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\),\\qquad\\forall x\\in\\mathcal\{X\},\\ t\\geq 1,where

UCBtMV​\(x\)\\displaystyle\\mathrm\{UCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\)=UCBtf​\(x\)−α​LCBtvar​\(x\),\\displaystyle=\\mathrm\{UCB\}\_\{t\}^\{f\}\(x\)\-\\alpha\\,\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{var\}\}\(x\),\(23\)LCBtMV​\(x\)\\displaystyle\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\)=LCBtf​\(x\)−α​UCBtvar​\(x\)\.\\displaystyle=\\mathrm\{LCB\}\_\{t\}^\{f\}\(x\)\-\\alpha\\,\\mathrm\{UCB\}\_\{t\}^\{\\mathrm\{var\}\}\(x\)\.\(24\)
Step 2 \(Instantaneous and cumulative regret\)\.Letrt:=MV​\(x∗\)−MV​\(xt\)r\_\{t\}:=\\mathrm\{MV\}\(x^\{\*\}\)\-\\mathrm\{MV\}\(x\_\{t\}\)\. As inmakarova2021risk,

rt\\displaystyle r\_\{t\}≤UCBtMV​\(xt\)−LCBtMV​\(xt\)\\displaystyle\\leq\\mathrm\{UCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\_\{t\}\)\-\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\_\{t\}\)=2​βtf​σt−1f​\(xt∣Σ^t−1\)\+2​α​βtvar​σt−1var​\(xt\)\.\\displaystyle=2\\beta\_\{t\}^\{f\}\\,\\sigma^\{f\}\_\{t\-1\}\(x\_\{t\}\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\)\+2\\alpha\\beta\_\{t\}^\{\\mathrm\{var\}\}\\,\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\_\{t\}\)\.\(25\)Hence

RT\\displaystyle R\_\{T\}=∑t=1Tkt​rt\\displaystyle=\\sum\_\{t=1\}^\{T\}k\_\{t\}r\_\{t\}≤2​β¯Tf​∑t=1Tkt​σt−1f​\(xt∣Σ^t−1\)\+2​α​β¯Tvar​∑t=1Tkt​σt−1var​\(xt\)\.\\displaystyle\\leq 2\\bar\{\\beta\}\_\{T\}^\{f\}\\sum\_\{t=1\}^\{T\}k\_\{t\}\\,\\sigma^\{f\}\_\{t\-1\}\(x\_\{t\}\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\)\+2\\alpha\\bar\{\\beta\}\_\{T\}^\{\\mathrm\{var\}\}\\sum\_\{t=1\}^\{T\}k\_\{t\}\\,\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\_\{t\}\)\.\(26\)
Step 3 \(Bounding the mean\-model term\)\.Letvt:=ρ¯2/ktv\_\{t\}:=\\overline\{\\rho\}^\{2\}/k\_\{t\}andut:=\(σt−1f\)2​\(xt∣Dt−1\)/vtu\_\{t\}:=\\bigl\(\\sigma^\{f\}\_\{t\-1\}\\bigr\)^\{2\}\(x\_\{t\}\\mid D\_\{t\-1\}\)/v\_\{t\}\. Since

min⁡\{UCBt−1var​\(xs\),ρ¯2\}ks≤ρ¯2ks=vs∀s<t,\\frac\{\\min\\\{\\mathrm\{UCB\}^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\_\{s\}\),\\overline\{\\rho\}^\{2\}\\\}\}\{k\_\{s\}\}\\leq\\frac\{\\overline\{\\rho\}^\{2\}\}\{k\_\{s\}\}=v\_\{s\}\\qquad\\forall s<t,we haveΣ^t−1⪯Dt−1\\widehat\{\\Sigma\}\_\{t\-1\}\\preceq D\_\{t\-1\}, and thereforeσt−1f​\(xt∣Σ^t−1\)≤σt−1f​\(xt∣Dt−1\)\\sigma^\{f\}\_\{t\-1\}\(x\_\{t\}\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\)\\leq\\sigma^\{f\}\_\{t\-1\}\(x\_\{t\}\\mid D\_\{t\-1\}\)\. By Cauchy–Schwarz,

∑t=1Tkt​σt−1f​\(xt∣Σ^t−1\)\\displaystyle\\sum\_\{t=1\}^\{T\}k\_\{t\}\\,\\sigma^\{f\}\_\{t\-1\}\(x\_\{t\}\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\)≤∑t=1Tkt​σt−1f​\(xt∣Dt−1\)\\displaystyle\\leq\\sum\_\{t=1\}^\{T\}k\_\{t\}\\,\\sigma^\{f\}\_\{t\-1\}\(x\_\{t\}\\mid D\_\{t\-1\}\)=∑t=1Tkt​vt​ut=ρ¯​∑t=1Tkt​ut\\displaystyle=\\sum\_\{t=1\}^\{T\}k\_\{t\}\\sqrt\{v\_\{t\}\}\\sqrt\{u\_\{t\}\}=\\overline\{\\rho\}\\sum\_\{t=1\}^\{T\}\\sqrt\{k\_\{t\}\}\\sqrt\{u\_\{t\}\}≤ρ¯​NT​∑t=1Tut\.\\displaystyle\\leq\\overline\{\\rho\}\\sqrt\{N\_\{T\}\}\\sqrt\{\\sum\_\{t=1\}^\{T\}u\_\{t\}\}\.\(27\)Moreover, sinceλ=1\\lambda=1andκ​\(x,x\)≤1\\kappa\(x,x\)\\leq 1,0≤ut≤kt/ρ¯2≤kmax/ρ¯20\\leq u\_\{t\}\\leq k\_\{t\}/\\overline\{\\rho\}^\{2\}\\leq k\_\{\\max\}/\\overline\{\\rho\}^\{2\}\. Thus,

ut≤kmax/ρ¯2ln⁡\(1\+kmax/ρ¯2\)​ln⁡\(1\+ut\),u\_\{t\}\\leq\\frac\{k\_\{\\max\}/\\overline\{\\rho\}^\{2\}\}\{\\ln\\\!\\bigl\(1\+k\_\{\\max\}/\\overline\{\\rho\}^\{2\}\\bigr\)\}\\ln\(1\+u\_\{t\}\),and summing overttgives

∑t=1Tut\\displaystyle\\sum\_\{t=1\}^\{T\}u\_\{t\}≤2​kmax/ρ¯2ln⁡\(1\+kmax/ρ¯2\)​∑t=1T12​ln⁡\(1\+ut\)\\displaystyle\\leq\\frac\{2k\_\{\\max\}/\\overline\{\\rho\}^\{2\}\}\{\\ln\\\!\\bigl\(1\+k\_\{\\max\}/\\overline\{\\rho\}^\{2\}\\bigr\)\}\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{2\}\\ln\(1\+u\_\{t\}\)≤2​kmax​γ¯T/ρ¯2ln⁡\(1\+kmax/ρ¯2\)\.\\displaystyle\\leq\\frac\{2k\_\{\\max\}\\,\\overline\{\\gamma\}\_\{T\}/\\overline\{\\rho\}^\{2\}\}\{\\ln\\\!\\bigl\(1\+k\_\{\\max\}/\\overline\{\\rho\}^\{2\}\\bigr\)\}\.\(28\)Substituting into \([27](https://arxiv.org/html/2607.26680#A1.E27)\), we obtain

∑t=1Tkt​σt−1f​\(xt∣Σ^t−1\)≤2​kmax​NT​γ¯Tln⁡\(1\+kmax/ρ¯2\)\.\\displaystyle\\sum\_\{t=1\}^\{T\}k\_\{t\}\\,\\sigma^\{f\}\_\{t\-1\}\(x\_\{t\}\\mid\\widehat\{\\Sigma\}\_\{t\-1\}\)\\leq\\sqrt\{\\frac\{2k\_\{\\max\}N\_\{T\}\\,\\overline\{\\gamma\}\_\{T\}\}\{\\ln\\\!\\bigl\(1\+k\_\{\\max\}/\\overline\{\\rho\}^\{2\}\\bigr\)\}\}\.\(29\)
Step 4 \(Bounding the variance\-model term\)\.Definewt:=\(σt−1var\)2​\(xt\)/ρη,t2w\_\{t\}:=\\bigl\(\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\\bigr\)^\{2\}\(x\_\{t\}\)/\\rho\_\{\\eta,t\}^\{2\}\. By Cauchy–Schwarz,

∑t=1Tkt​σt−1var​\(xt\)\\displaystyle\\sum\_\{t=1\}^\{T\}k\_\{t\}\\,\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\_\{t\}\)≤∑t=1Tkt​∑t=1Tkt​\(σt−1var\)2​\(xt\)\\displaystyle\\leq\\sqrt\{\\sum\_\{t=1\}^\{T\}k\_\{t\}\}\\,\\sqrt\{\\sum\_\{t=1\}^\{T\}k\_\{t\}\\bigl\(\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\\bigr\)^\{2\}\(x\_\{t\}\)\}≤kmax​NT​∑t=1T\(σt−1var\)2​\(xt\)\.\\displaystyle\\leq\\sqrt\{k\_\{\\max\}N\_\{T\}\}\\,\\sqrt\{\\sum\_\{t=1\}^\{T\}\\bigl\(\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\\bigr\)^\{2\}\(x\_\{t\}\)\}\.\(30\)Sinceλ=1\\lambda=1andκvar​\(x,x\)≤1\\kappa^\{\\mathrm\{var\}\}\(x,x\)\\leq 1,0≤wt≤ρη,t−20\\leq w\_\{t\}\\leq\\rho\_\{\\eta,t\}^\{\-2\}\. Hence

ρη,t2​wt≤1ln⁡\(1\+ρη,t−2\)​ln⁡\(1\+wt\)≤1ln⁡\(1\+ℛ−2\)​ln⁡\(1\+wt\),\\rho\_\{\\eta,t\}^\{2\}w\_\{t\}\\leq\\frac\{1\}\{\\ln\\\!\\bigl\(1\+\\rho\_\{\\eta,t\}^\{\-2\}\\bigr\)\}\\ln\(1\+w\_\{t\}\)\\leq\\frac\{1\}\{\\ln\\\!\\bigl\(1\+\\mathcal\{R\}^\{\-2\}\\bigr\)\}\\ln\(1\+w\_\{t\}\),where the second inequality usesρη,t2≤ℛ2\\rho\_\{\\eta,t\}^\{2\}\\leq\\mathcal\{R\}^\{2\}\. Summing overttyields

∑t=1T\(σt−1var\)2​\(xt\)\\displaystyle\\sum\_\{t=1\}^\{T\}\\bigl\(\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\\bigr\)^\{2\}\(x\_\{t\}\)=∑t=1Tρη,t2​wt\\displaystyle=\\sum\_\{t=1\}^\{T\}\\rho\_\{\\eta,t\}^\{2\}w\_\{t\}≤1ln⁡\(1\+ℛ−2\)​∑t=1Tln⁡\(1\+wt\)\\displaystyle\\leq\\frac\{1\}\{\\ln\\\!\\bigl\(1\+\\mathcal\{R\}^\{\-2\}\\bigr\)\}\\sum\_\{t=1\}^\{T\}\\ln\(1\+w\_\{t\}\)=2​ΓTln⁡\(1\+ℛ−2\)\.\\displaystyle=\\frac\{2\\Gamma\_\{T\}\}\{\\ln\\\!\\bigl\(1\+\\mathcal\{R\}^\{\-2\}\\bigr\)\}\.\(31\)Substituting into \([30](https://arxiv.org/html/2607.26680#A1.E30)\), we obtain

∑t=1Tkt​σt−1var​\(xt\)≤2​kmax​NT​ΓTln⁡\(1\+ℛ−2\)\.\\displaystyle\\sum\_\{t=1\}^\{T\}k\_\{t\}\\,\\sigma^\{\\mathrm\{var\}\}\_\{t\-1\}\(x\_\{t\}\)\\leq\\sqrt\{\\frac\{2k\_\{\\max\}N\_\{T\}\\,\\Gamma\_\{T\}\}\{\\ln\\\!\\bigl\(1\+\\mathcal\{R\}^\{\-2\}\\bigr\)\}\}\.\(32\)
Step 5 \(Combine bounds\)\.Substituting \([29](https://arxiv.org/html/2607.26680#A1.E29)\) and \([32](https://arxiv.org/html/2607.26680#A1.E32)\) into \([A](https://arxiv.org/html/2607.26680#A1.Ex5)\) yields \([22](https://arxiv.org/html/2607.26680#A1.E22)\) withNT≤T​kmaxN\_\{T\}\\leq Tk\_\{\\max\}\. ∎

##### Remark on adaptive resampling\.

The bound is stated for bounded sample countskt∈\[kmin,kmax\]k\_\{t\}\\in\[k\_\{\\min\},k\_\{\\max\}\]under the aggregate observation model used by RAHBO\. ERAHBO’s practical stopping rule choosesktk\_\{t\}by repeatedly checking the MV\-UCB at the current point\. Since the confidence bounds are uniform over points and rounds, and since the inner loop contains only finitely many checksk∈\[kmin,kmax\]k\\in\[k\_\{\\min\},k\_\{\\max\}\], this provides a valid high\-confidence stopping certificate whenever the intermediate GP updates satisfy the stated concentration assumptions, after applying a union or anytime bound over the inner\-loop checks if needed\. A fully optional\-stopping analysis of the stopped sample mean and sample variance is beyond the scope of this work; the theorem should therefore be read as showing that bounded variable replication itself does not degrade the RAHBO regret rate, while our stopping rule is the practical mechanism used to choose such bounded replications\.

#### Acknowledgments

Mingxuan Che acknowledges funding by the European Union \(ERC, “ixAutoML”, grant no\.101041029\)\. Theresa Eimer and Marius Lindauer acknowledge funding by the German Research Foundation \(DFG\) under LI 2801/7\-1 and LI 2801/10\-1\. Alexander von Rohr is funded by the Deutsche Forschungsgemeinschaft \(DFG\) under project 468806714 of the Emmy Noether Programme\. Alexander von Rohr also gratefully acknowledges funding from the European Union \(ERC, ConSequentIAL, 101165883\)\. Views and opinions expressed are however those of the author\(s\) only and do not necessarily reflect those of the European Union or the European Research Council\. Neither the European Union nor the granting authority can be held responsible for them\.

## References

Supplementary Materials

*The following content was not necessarily subject to peer review\.*

## Appendix BFinite\-sample certificates

This section provides a local certificate for ERAHBO’s stopping rule in the case where the currently queried configuration can be shown to be suboptimal relative to the incumbent lower bound\. Concretely, we derive a sufficient condition under which, after collecting enough samples at the current configurationxtx\_\{t\}, its optimistic mean\-variance estimate drops below the incumbent lower bound with the current confidence bounds, so that additional sampling atxtx\_\{t\}is unnecessary\.

Fix a BO roundttand define

Bt:=maxx∈𝒟t−1⁡LCBtMV​\(x\),B\_\{t\}:=\\max\_\{x\\in\\mathcal\{D\}\_\{t\-1\}\}\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\),computed once at the start of roundttand kept fixed during the inner sampling loop atxtx\_\{t\}\. Fork≥2k\\geq 2, letμt,kMV​\(xt\)\\mu^\{\\mathrm\{MV\}\}\_\{t,k\}\(x\_\{t\}\),σt,kf​\(xt\)\\sigma^\{f\}\_\{t,k\}\(x\_\{t\}\), andσt,kvar​\(xt\)\\sigma^\{\\mathrm\{var\}\}\_\{t,k\}\(x\_\{t\}\)denote the corresponding posterior quantities after incorporating the firstkksamples collected atxtx\_\{t\}, and define

mt​\(k\):=Bt−μt,kMV​\(xt\)\.m\_\{t\}\(k\):=B\_\{t\}\-\\mu^\{\\mathrm\{MV\}\}\_\{t,k\}\(x\_\{t\}\)\.Also define

UCBt,kMV​\(xt\):=μt,kMV​\(xt\)\+βtf​σt,kf​\(xt\)\+α​βtvar​σt,kvar​\(xt\)\.\\mathrm\{UCB\}\_\{t,k\}^\{\\mathrm\{MV\}\}\(x\_\{t\}\):=\\mu^\{\\mathrm\{MV\}\}\_\{t,k\}\(x\_\{t\}\)\+\\beta\_\{t\}^\{f\}\\sigma^\{f\}\_\{t,k\}\(x\_\{t\}\)\+\\alpha\\beta\_\{t\}^\{\\mathrm\{var\}\}\\sigma^\{\\mathrm\{var\}\}\_\{t,k\}\(x\_\{t\}\)\.
###### Lemma 2\(Finite\-sample certificate of suboptimality\)\.

Assumemt​\(k\)\>0m\_\{t\}\(k\)\>0and

σt,kf​\(xt\)≤ρ​\(xt\)k,σt,kvar​\(xt\)≤cvark,\\sigma^\{f\}\_\{t,k\}\(x\_\{t\}\)\\leq\\frac\{\\rho\(x\_\{t\}\)\}\{\\sqrt\{k\}\},\\qquad\\sigma^\{\\mathrm\{var\}\}\_\{t,k\}\(x\_\{t\}\)\\leq\\frac\{c\_\{\\mathrm\{var\}\}\}\{\\sqrt\{k\}\},for some constantsρ​\(xt\)\>0\\rho\(x\_\{t\}\)\>0andcvar\>0c\_\{\\mathrm\{var\}\}\>0\. If

k≥\(βtf​ρ​\(xt\)\+α​βtvar​cvar\)2mt​\(k\)2,k\\geq\\frac\{\\bigl\(\\beta\_\{t\}^\{f\}\\rho\(x\_\{t\}\)\+\\alpha\\beta\_\{t\}^\{\\mathrm\{var\}\}c\_\{\\mathrm\{var\}\}\\bigr\)^\{2\}\}\{m\_\{t\}\(k\)^\{2\}\},\(33\)then

UCBt,kMV​\(xt\)≤Bt\.\\mathrm\{UCB\}\_\{t,k\}^\{\\mathrm\{MV\}\}\(x\_\{t\}\)\\leq B\_\{t\}\.

###### Proof\.

By definition ofUCBt,kMV​\(xt\)\\mathrm\{UCB\}\_\{t,k\}^\{\\mathrm\{MV\}\}\(x\_\{t\}\), it suffices that

βtf​σt,kf​\(xt\)\+α​βtvar​σt,kvar​\(xt\)≤mt​\(k\)\.\\beta\_\{t\}^\{f\}\\sigma^\{f\}\_\{t,k\}\(x\_\{t\}\)\+\\alpha\\beta\_\{t\}^\{\\mathrm\{var\}\}\\sigma^\{\\mathrm\{var\}\}\_\{t,k\}\(x\_\{t\}\)\\leq m\_\{t\}\(k\)\.Using the assumed bounds onσt,kf​\(xt\)\\sigma^\{f\}\_\{t,k\}\(x\_\{t\}\)andσt,kvar​\(xt\)\\sigma^\{\\mathrm\{var\}\}\_\{t,k\}\(x\_\{t\}\), this is implied by

βtf​ρ​\(xt\)\+α​βtvar​cvark≤mt​\(k\),\\frac\{\\beta\_\{t\}^\{f\}\\rho\(x\_\{t\}\)\+\\alpha\\beta\_\{t\}^\{\\mathrm\{var\}\}c\_\{\\mathrm\{var\}\}\}\{\\sqrt\{k\}\}\\leq m\_\{t\}\(k\),which is equivalent to \([33](https://arxiv.org/html/2607.26680#A2.E33)\)\. ∎

Takeaway\.If the current posterior meanμt,kMV​\(xt\)\\mu^\{\\mathrm\{MV\}\}\_\{t,k\}\(x\_\{t\}\)lies below the incumbent lower boundBtB\_\{t\}by a marginmt​\(k\)\>0m\_\{t\}\(k\)\>0, then the stopping rule is triggered once the confidence radius becomes smaller than this margin\. In particular, the sufficient sample size in \([33](https://arxiv.org/html/2607.26680#A2.E33)\) scales as1/mt​\(k\)21/m\_\{t\}\(k\)^\{2\}: candidates that are closer to the incumbent require substantially more samples to certify suboptimality\. The threshold also increases with the uncertainty multipliersβtf\\beta\_\{t\}^\{f\}andβtvar\\beta\_\{t\}^\{\\mathrm\{var\}\}, with the local noise levelρ2​\(xt\)\\rho^\{2\}\(x\_\{t\}\), and with the variance\-model constantcvarc\_\{\\mathrm\{var\}\}, formalizing that ERAHBO allocates more samples only when uncertainty could plausibly change the mean\-variance decision\.

## Appendix CAdditional empirical results

This section contains additional empirical results for ERAHBO and the full experiment details for the results presented in Section[5](https://arxiv.org/html/2607.26680#S5)\.

### C\.1Algorithm\-environment combination

Table[3](https://arxiv.org/html/2607.26680#A3.T3)shows the RL algorithms and environments used in the experiment, and each pair of them corresponds to a dataset for risk\-aware BO tasks\. By ‘task’, we refer to a dataset for the algorithm\-environment pair\. The dataset is generated using ARLbench\(becktepe2024arlbench\), including all available RL tasks at the time of publication\. Each dataset contains 512 configurations generated by a Sobol sequence, and each configuration includes policy returns across 50 random seeds\.

Some datasets contain configurations that returnnan, a common issue in RL benchmarks\. In our experiments, we filter out thesenanconfigurations, since failure handling is beyond the scope of this work and is left for future work\. In detail, there are 18 infeasible configurations fromppo\_cc\_pendulumdataset, 48 fromppo\_cc\_continuous\_mountain\_car, and 182 fromppo\_brax\_halfcheetah\. In addition, we exclude the datasetdqn\_xland\_doorkeybecause for this task, all configurations sampled by the Sobol sequence yield zero performance\. Both datasets, before and after feasibility filtering, are available online at[https://github\.com/LUH\-AI/Efficient\-Risk\-Averse\-BO](https://github.com/LUH-AI/Efficient-Risk-Averse-BO)\.

Table 3:RL algorithms and environments from ARLBench used in the experiment by domain
### C\.2Ranking statistics

Tables[1](https://arxiv.org/html/2607.26680#S5.T1)and[4](https://arxiv.org/html/2607.26680#A3.T4)show the aggregated mean and median rank for final simple and cumulative regret of the mean\-variance objective\. We see similar trends in performance over time: RAHBO and ERAHBO outperform GP\-UCB, with RAHBO withk=2k=2ranking similarly to ERAHBO but with a larger inter\-quantile range\.

Table 4:Median algorithm rank\[25th percentile,75th percentile\]\[\\text\{25th percentile\},\\text\{75th percentile\}\]aggregated across experiments; lower is better\.Figures[5](https://arxiv.org/html/2607.26680#A3.F5)shows the mean ranks over time per environment, aggregated across RL algorithms\. As in the main paper, we see clear differences across domains, especially in XLand, but ERAHBO ranks best overall\.

Figure[6](https://arxiv.org/html/2607.26680#A3.F6)shows the rank distribution\. In this experiment, the rank distributions across algorithms are similar; however, the fraction colormap reveals that the RAHBOk=2k=2rank distribution is bimodal, with a concentration at the best and worst ranks\.

In addition to the rank result with RAHBO repetitionsk=2k=2andk=20k=20shown in Figure[2](https://arxiv.org/html/2607.26680#S5.F2), we run RAHBO withk∈\{5,8,11,14,17\}k\\in\\\{5,8,11,14,17\\\}and present the domain\-aggregated rank over time in Figures[7](https://arxiv.org/html/2607.26680#A3.F7)\. After around 750 evaluations, ERAHBO outperforms all the RAHBO repetition variants\.

![Refer to caption](https://arxiv.org/html/2607.26680v1/x5.png)Figure 5:Mean algorithm rank aggregated by RL environments\. The line and shaded area show the mean and1×1\\timesstandard error, respectively\.![Refer to caption](https://arxiv.org/html/2607.26680v1/x6.png)Figure 6:Rank distribution over time\. Rows and columns correspond to the aggregation domain and method, respectively, as compared in the experiment \(e\.g\., Figure[2](https://arxiv.org/html/2607.26680#S5.F2)\)\. The solid line and the colormap show the rank mode and the fraction of rank appearances\.![Refer to caption](https://arxiv.org/html/2607.26680v1/x7.png)Figure 7:Mean algorithm rank aggregated by domain with RAHBOk∈\{2,5,8,11,14,17,20\}k\\in\\\{2,5,8,11,14,17,20\\\}\. The line and shaded area show the mean and1×1\\timesstandard error, respectively\.
### C\.3Aggregated regret over time

Figure[9](https://arxiv.org/html/2607.26680#A3.F9)\-[12](https://arxiv.org/html/2607.26680#A3.F12)show the normalized mean\-variance regret at different evaluation budgetsttfor domains CC, Brax, and XLand\. Figures[8](https://arxiv.org/html/2607.26680#A3.F8)shows the mean regret over time per environment and algorithm\. Overall, the tasks are quite different: for some, we see large improvements over the initial design \(e\.g\., on acrobot\), whereas in others, not much can be gained \(e\.g\., on mountain car\)\. While the curves look slightly different for different algorithms, the overall trend seems to be environment\-dependent\.

![Refer to caption](https://arxiv.org/html/2607.26680v1/x8.png)Figure 8:Algorithm normalized regret for individual RL task\. The line and shaded area show the IQM and95%95\\%bootstrapped CI, respectively\. The colored marker indicates the point at which the algorithm’s normalized regret exceeds the threshold \(% of initial\-design regret\)\.
### C\.4Sample efficiency

![Refer to caption](https://arxiv.org/html/2607.26680v1/x9.png)Figure 9:Normalized mean\-variance regret at different evaluation budgettt\. Mean regret is normalized by the initial design’s mean regret\.![Refer to caption](https://arxiv.org/html/2607.26680v1/x10.png)Figure 10:Normalized mean\-variance regret at different evaluation budgetttin domain Brax\. Mean regret is normalized by the initial design’s mean regret\.![Refer to caption](https://arxiv.org/html/2607.26680v1/x11.png)Figure 11:Normalized mean\-variance regret at different evaluation budgetttin domain CC\. Mean regret is normalized by the initial design’s mean regret\.![Refer to caption](https://arxiv.org/html/2607.26680v1/x12.png)Figure 12:Normalized mean\-variance regret at different evaluation budgetttin domain Xland\. Mean regret is normalized by the initial design’s mean regret\.Tables[5](https://arxiv.org/html/2607.26680#A3.T5)shows how quickly ERAHBO, RAHBO and GP\-UCB improve over the initial design\. We clearly see that ERAHBO can be more efficient than RAHBO in most cases due to discarding poor configurations early on\.

Table 5:First evaluation steps where the IQM of normalized MV regret drops below threshold \(% of initial\-design regret\)\. "—" means not reached\.ERAHBORAHBO \(K=20\)RAHBO \(K=2\)GP\-UCBCombo75%75\\%50%50\\%25%25\\%75%75\\%50%50\\%25%25\\%75%75\\%50%50\\%25%25\\%75%75\\%50%50\\%25%25\\%dqn/cc\_acrobot212165651511512121818122122177252575752121101101241241dqn/cc\_cartpole4343135135—6161121121—25925911851185—421421781781—dqn/cc\_mountain\_car446161—21216161—663663——11——dqn/xland\_empty\_random——————727727—————dqn/xland\_four\_rooms9797130130217217121121241241321321191929293333121121201201301301ppo/brax\_fast484822322338938981812012015815817575121121889889818124124110811081ppo/brax\_halfcheetah23238181—4141261261—33121121—4141——ppo/cc\_acrobot48486363929281811411411811812121373765656161101101141141ppo/cc\_cartpole212163638787212181811611612525575712912921218181161161ppo/cc\_continuous\_mountain\_car434315115127027081811611615615611111151533336161101101121121ppo/cc\_mountain\_car898898——581581————————ppo/cc\_pendulum21214343210210212114114138138125256565—2121——ppo/xland\_door\_key12381238—————13132323454576176112411241—ppo/xland\_empty\_random4141145145403403616110110128128199191961618181141141201201ppo/xland\_four\_rooms6969123123165165101101141141221221232327273737101101141141221221sac/brax\_fast21212525120120212141413213213737111111201201212114114110011001sac/brax\_halfcheetah2323272742742721216161101101———41418181301301sac/cc\_continuous\_mountain\_car6363838312512581811011011811811515191929298181141141181181sac/cc\_pendulum49498585111111121121181181321321171725257575121121201201301301

### C\.5Scheduleβstop\\beta\_\{\\text\{stop\}\}

It can be observed, e\.g\., in Figure[2](https://arxiv.org/html/2607.26680#S5.F2), that RAHBO \(k=2\) ranks best for small budgets, indicating that exploring with minimal repetition can be efficient at this stage\. Inspired by this, we propose to increase the LCB of the incumbent\. Recall \([10](https://arxiv.org/html/2607.26680#S4.E10)\) as

Bt:=maxx∈𝒟t−1⁡LCBtMV​\(x\)\.B\_\{t\}:=\\max\_\{x\\in\\mathcal\{D\}\_\{t\-1\}\}\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\)\.\(34\)We set the confidence parameterβ\\betain theLCBtMV​\(x\)\\mathrm\{LCB\}\_\{t\}^\{\\mathrm\{MV\}\}\(x\)asβstop,t\\beta\_\{\\text\{stop\},t\}and increase it with an exponential schedule

βstop,t=eγ​τ−1eγ−1\\beta\_\{\\text\{stop\},t\}=\\frac\{e^\{\\gamma\\tau\}\-1\}\{e^\{\\gamma\}\-1\}\(35\)or a sigmoid schedule

βstop,t=σs​\(τ\)−σs​\(0\)σs​\(1\)−σs​\(0\)\\beta\_\{\\text\{stop\},t\}=\\frac\{\\sigma\_\{s\}\(\\tau\)\-\\sigma\_\{s\}\(0\)\}\{\\sigma\_\{s\}\(1\)\-\\sigma\_\{s\}\(0\)\}\(36\)whereτ=t/T\\tau=t/Tis the normalized progress, withttbeing the current evaluation andTTbeing the total evaluation budget,σs​\(τ\)=1/\(1\+es​\(τ−0\.5\)\)\\sigma\_\{s\}\(\\tau\)=1/\(1\+e^\{s\(\\tau\-0\.5\)\}\)is a sigmoid function,γ\\gammaandssare hyperparameter of the schedule\. We choose different schedule hyperparameters and illustrate them in Figure[13](https://arxiv.org/html/2607.26680#A3.F13)\. Moreover, we apply the sameβstop,t\\beta\_\{\\text\{stop\},t\}to the UCB in \([12](https://arxiv.org/html/2607.26680#S4.E12)\)\. We note that it is independent of the confidence parameterβ\\betain the acquisition function\.

Figure[14](https://arxiv.org/html/2607.26680#A3.F14)shows the domain\-aggregated mean rank over time for ERAHBO with different schedules\. We see that most schedules can outperform RAHBOk=2k=2after 200\-500 evaluations, while some consistently outperform ERAHBO throughout the budget\. Notably, on XLand, an exponential schedule withγ=50\\gamma=50can drastically improve ERAHOBO, as it not only outperforms a constant schedule but also ranks comparably close to RAHBOk=2k=2\. Even though the schedule introduces one additional hyperparameter, we see the performance is at least comparable with ERAHBO with a constantβstop\\beta\_\{\\text\{stop\}\}as long as the initialβstop,t\\beta\_\{\\text\{stop\},t\}value of the schedule is small enough\.

A small initialβstop\\beta\_\{\\text\{stop\}\}benefits ERAHBO from a more optimistic triggering of the confidence\-based resampling rule \([12](https://arxiv.org/html/2607.26680#S4.E12)\) early on; therefore, ERAHBO with such a schedule will start with investing fewer repetitions for rejection, however, still resamples thoroughly if the configuration is promising enough\. As theβstop\\beta\_\{\\text\{stop\}\}increases with the schedule, promising configurations are exploited with more repetitions\.

![Refer to caption](https://arxiv.org/html/2607.26680v1/x13.png)Figure 13:Theβstop\\beta\_\{\\text\{stop\}\}schedule used in the ablation study\. The horizontal axis is the evaluation progressttnormalized by the total evaluation budgetTT, and the vertical axis is the instantaneous valueβstop,t\\beta\_\{\\text\{stop\},t\}, normalized by the maximumβstop\\beta\_\{\\text\{stop\}\}, at normalized progresst/Tt/T\.![Refer to caption](https://arxiv.org/html/2607.26680v1/x14.png)Figure 14:Domain aggregated mean rank over evaluation\. The line and shaded area show the mean and1×1\\timesstandard error, respectively\. Schedules with steep rises can outperform constant schedules\.