Online Adaptive Kernel Mixing for Gaussian Process Decision Making

# Online Adaptive Kernel Mixing for Gaussian Process Decision Making
Source: [https://arxiv.org/html/2609.19891](https://arxiv.org/html/2609.19891)
Mani Tej SriramAffiliation:International Institute of Information Technology, HyderabadGautam DasarathyAffiliation:Arizona State UniversityTejas BodasAffiliation:International Institute of Information Technology, Hyderabad

###### Abstract

Gaussian Processes \(GPs\) are widely used as surrogates for black\-box functions in sequential decision\-making problems such as Bayesian optimization \(BO\), level set estimation \(LSE\), and Bayesian active learning \(BAL\)\. GP performance critically depends on kernels, and standard kernels can lead to suboptimal decisions under misspecification\. To address this, we introduceHACK GPs\(Hedge Adaptive Cumulative Kernels\), a method that views kernel selection as an online learning with expert advice problem\. HACK treats each candidate kernel as a GP “expert” and updates a distribution over experts online using AdaHedge, based on a loss received as a proxy for their ability to fit the function and align with the task objective\. We provide two variants of HACK: \(i\) Mixture of Gaussians \(MoG\) and \(ii\) categorical sampling\. We establish general guarantees showing that, under a loss\-gap condition, the weight concentrates on the best kernel and the resulting acquisition function is close to that of the best expert\. Empirically, we observe robust performance across BO, LSE, and BAL compared to standard kernels such as Squared Exponential and Matérn\-5/2, as well as simple ensemble baselines\.

###### Keywords:

Gaussian Processes, Online Learning, Bayesian Optimization, Active Learning, Level Set Estimation\.

## 1Introduction

Many experimental setups in science, engineering and machine learning require the optimization and modeling of noisy, expensive\-to\-evaluate, black\-box functions\. Gaussian processes \(GPs\) have proven to be an effective choice for these tasks due to their sample efficiency and ability to model uncertainties\[[1](https://arxiv.org/html/2609.19891#bib.bib1)\]\.

Several of these tasks are sequential in nature: at each roundtt, a surrogate model proposes an inputxtx\_\{t\}, observes a noisy evaluationyty\_\{t\}of the black\-box functionff, and updates its posterior before the next decision\. This template underlies Bayesian Optimization \(BO\), which seeks the maximizerx∗=argmaxx∈𝒳f​\(x\)x^\{\*\}=\\argmax\_\{x\\in\\mathcal\{X\}\}f\(x\)under a limited budget; Level Set Estimation \(LSE\), which aims to recover a superlevel setSh:=\{x∈𝒳:f⁡\(x\)≥h\}S\_\{h\}:=\\\{x\\in\\mathcal\{X\}:f\(x\)\\geq h\\\}; and Bayesian Active Learning \(BAL\), where one queries to maximally reduce uncertainty about a target quantity\. GPs are well suited to these settings because of their ability to convert the posterior model’s uncertainty estimates into sampling strategies called acquisition functions\. It is essential to ensure the quality of the GP in order to have reliable performance in these tasks\.

GP performance is governed by the choice of the kernel, which encodes assumptions such as smoothness, stationarity, and the length scales across which such phenomena occur in the underlying function\.Kernel misspecification, where these assumptions are misaligned with the underlying function, can lead to poorly calibrated uncertainty estimates and compounding errors in sequential decision\-making\. Despite this, standard kernels such as squared exponential and Matérn\-5/2 are often used in practice, even when they may be ill\-suited for the task at hand\[[2](https://arxiv.org/html/2609.19891#bib.bib2),[3](https://arxiv.org/html/2609.19891#bib.bib3)\]\.

To address this issue, we proposeHACK GPs\(HedgeAdaptiveCumulativeKernels\), a simple alternative that views kernel selection through the lens of online learning with expert advice\. We treat each candidate kernel as a GP “expert”, maintain a distribution of weights over experts, and update the distribution online using AdaHedge\[[4](https://arxiv.org/html/2609.19891#bib.bib4)\], a parameter\-free variant of Hedge\[[5](https://arxiv.org/html/2609.19891#bib.bib5)\]with a time\-varying learning rate\. Experts are scored with per\-round*probabilistic*losses derived from their predictive performance, such as negative log\-likelihood, optionally augmented with task\-dependent proxies, allowing the weighting \(and therefore the acquisition strategy\) to adapt over time\.

We instantiate two use modes: \(i\) a*mixture\-of\-Gaussians*\(MoG\) predictive distribution formed by weighting each expert’s posterior, and \(ii\)*categorical sampling*of a single kernel\. Both yield a plug\-and\-play procedure that progressively down\-weights poorly aligned kernels, while boosting suitable ones, and incur only a modest computational overhead when the user\-specified kernel candidate set is small\. To place our approach in context, we next review existing methods for addressing kernel misspecification and model uncertainty in GP\-based sequential decision making\.

Most approaches that use GPs as surrogates make use of standard kernels not necessarily designed for the function at hand, such as the squared exponential or Matérn\-5/2 kernels\[[2](https://arxiv.org/html/2609.19891#bib.bib2)\]\. While the use of a general\-purpose kernel is convenient, it can lead to suboptimal performance during tasks where the kernel does not align well with the nature of the function it is fitting\[[6](https://arxiv.org/html/2609.19891#bib.bib6)\], referred to as*kernel misspecification*\. It is also known that with overly general kernel choices, tasks like BO may converge slowly on complex functions in moderate to high dimensions\[[3](https://arxiv.org/html/2609.19891#bib.bib3)\]\. Early attempts to address kernel misspecification include compositional kernel structure search for GP regression\[[7](https://arxiv.org/html/2609.19891#bib.bib7)\], where a grammar is used to generate new kernel compositions that may fit the data better\. Parallel work has focused on flexible kernel families, such as spectral mixture kernels, which are able to approximate a broad class of stationary covariances\[[8](https://arxiv.org/html/2609.19891#bib.bib8)\]\. However, these methods often require significant data before their selection criteria can separate candidates effectively\. A modern variant addresses this by leveraging the generalizability of LLMs to suggest and combine kernels, achieving an effective, expressive family without the need for a large number of samples\[[9](https://arxiv.org/html/2609.19891#bib.bib9)\]\.

Ensemble methods offer an alternative approach by maintaining multiple GP models and combining their predictions or decisions, rather than committing to a single kernel throughout the sequential process\. Roman et al\.\[[6](https://arxiv.org/html/2609.19891#bib.bib6)\]investigated multiple heuristics for GP ensembling\. Formalizing this, Lu et al\.\[[10](https://arxiv.org/html/2609.19891#bib.bib10)\]applied Bayesian Model Averaging \(BMA\) over kernels, while Ravishankar et al\.\[[11](https://arxiv.org/html/2609.19891#bib.bib11)\]extended the ensemble approach to both kernels and acquisition functions\. Sandberg et al\.\[[12](https://arxiv.org/html/2609.19891#bib.bib12)\]apply BMA to general GP priors, while concurrently employing an elimination strategy, first introduced by Ziomek et al\.\[[13](https://arxiv.org/html/2609.19891#bib.bib13)\]\. Early GP\-based LSE methods use confidence\-bound heuristics, with Bryan et al\.\[[14](https://arxiv.org/html/2609.19891#bib.bib14)\]introducing the straddle algorithm, which samples points around the threshold with high variance\. Gotovos\[[15](https://arxiv.org/html/2609.19891#bib.bib15)\]formalized this, utilizing GP\-UCB\-style bounds\[[16](https://arxiv.org/html/2609.19891#bib.bib16)\]to provide convergence guarantees\. Alternatively, Ravishankar et al\.\[[17](https://arxiv.org/html/2609.19891#bib.bib17)\]formulated the problem via EI, targeting points that reduce the gap to the threshold\. However, these methods rely on the GP being well\-specified for the black\-box function\. To address potential mismatches, Zanette et al\.\[[18](https://arxiv.org/html/2609.19891#bib.bib18)\]proposed an acquisition function robust to model misspecification, RMILE\.

GP\-based BAL for regression typically uses uncertainty\-driven acquisition strategies, with predictive entropy being a standard choice\[[19](https://arxiv.org/html/2609.19891#bib.bib19),[20](https://arxiv.org/html/2609.19891#bib.bib20)\]\. An alternative choice is Bayesian Active Learning by Disagreement \(BALD\) introduced by Houlsby et al\.\[[21](https://arxiv.org/html/2609.19891#bib.bib21)\], which proposes maximizing the expected decrease in predictive entropy\. In an attempt to address hyperparameter misspecification in BAL, Riis et al\.\[[22](https://arxiv.org/html/2609.19891#bib.bib22)\]propose using a fully Bayesian treatment of the GP hyperparameters, providing other acquisition function variants that use the fully Bayesian nature of the GP\. Polyzos et al\.\[[23](https://arxiv.org/html/2609.19891#bib.bib23)\]formulated an adaptive ensemble GP method using BMA to handle kernel misspecification, utilizing a weighted mixture of acquisition functions\.

Taken together, existing approaches address model misspecification through the use of more expressive kernel families, or through model averaging or selection, or through the use of task\-specific robust acquisition strategies\. HACK complements these directions by treating kernel adaptation itself as an online expert\-advice problem, allowing the relative importance of candidate kernels to evolve during sequential decision making according to their performance and alignment with the task\. The main contributions of this work are as follows\.

### Contributions:

- 1\.We introduceHACK GPs, a framework for online adaptive kernel weighting in Gaussian process–based sequential decision making, formulated as an expert\-advice problem over a finite set of candidate kernels\.
- 2\.We develop two practical instantiations: \(i\) HACK\-MoG, which combines expert posterior predictive distributions into a mixture\-of\-Gaussians predictive distribution, and \(ii\) HACK\-Cat, which samples a single kernel per round, both of which integrate seamlessly with standard acquisition\-driven methods\.
- 3\.We establish theoretical guarantees showing that, under a loss\-gap condition, the expert weights concentrate on the best kernel in hindsight and that this concentration translates to closeness of the acquisition function\.
- 4\.We empirically demonstrate across BO, LSE, and BAL benchmarks that adaptive kernel weighting improves robustness to kernel misspecification compared to standard single\-kernel and simple ensemble methods\.

## 2Background

### 2\.1Gaussian Processes

A Gaussian Process \(GP\) is a stochastic process such that any finite collection of its random variables has a multivariate Gaussian distribution\. GPs are often used as surrogate models to approximate the black\-box functionffin BO, LSE and BAL\. GPs are parametrized by a mean functionμ\\muand a covariance function given by a kernelk⁡\(⋅,⋅\)k\(\\cdot,\\cdot\)\. We model the black\-box functionffwith the GP priorf⁡\(x\)∼𝒢​𝒫​\(μ⁡\(x\),k⁡\(x,x′\)\)\.f\(x\)\\sim\\mathcal\{GP\}\\\!\\left\(\\mu\(x\),\\,k\(x,x^\{\\prime\}\)\\right\)\.The mean functionμ⁡\(x\)\\mu\(x\)provides the mean at pointxx, while the kernelk⁡\(x,x′\)k\(x,x^\{\\prime\}\)determines the covariance between function values at two inputsxxandx′x^\{\\prime\}\. We fit the GP on noisy observationsyi=f⁡\(xi\)\+ϵiy\_\{i\}=f\(x\_\{i\}\)\+\\epsilon\_\{i\}withϵi∼𝒩⁡\(0,σn2\)\\epsilon\_\{i\}\\sim\\mathcal\{N\}\(0,\\sigma\_\{n\}^\{2\}\)\. Let𝒟t=\{\(xi,yi\)∣i=1,2,…,t\}\\mathcal\{D\}\_\{t\}=\\\{\(x\_\{i\},y\_\{i\}\)\\mid i=1,2,\\dots,t\\\},X=\[x1,…,xt\]⊤X=\[x\_\{1\},\\dots,x\_\{t\}\]^\{\\top\}, and𝐲=\[y1,…,yt\]⊤\\mathbf\{y\}=\[y\_\{1\},\\dots,y\_\{t\}\]^\{\\top\}\. Define the kernel matrixK∈ℝt×tK\\in\\mathbb\{R\}^\{t\\times t\}byKi​j=k⁡\(xi,xj\)K\_\{ij\}=k\(x\_\{i\},x\_\{j\}\), and the cross\-covariance vectorsk⁡\(x,X\)=\[k⁡\(x,x1\),…,k⁡\(x,xt\)\]k\(x,X\)=\[k\(x,x\_\{1\}\),\\dots,k\(x,x\_\{t\}\)\]andk⁡\(X,x\)=k​\(x,X\)⊤k\(X,x\)=k\(x,X\)^\{\\top\}\. LetYt\+1=f⁡\(xt\+1\)\+ϵt\+1Y\_\{t\+1\}=f\(x\_\{t\+1\}\)\+\\epsilon\_\{t\+1\}denote the noisy observation at a test pointxt\+1x\_\{t\+1\}\. After conditioning the GP on𝒟t\\mathcal\{D\}\_\{t\}, the posterior distributions of the function value and the noisy observation are

f⁡\(xt\+1\)\|𝒟t,xt\+1\\displaystyle f\(x\_\{t\+1\}\)\\mid\\mathcal\{D\}\_\{t\},x\_\{t\+1\}∼𝒩⁡\(μf\|𝒟t​\(xt\+1\),σf\|𝒟t2​\(xt\+1\)\),\\displaystyle\\sim\\mathcal\{N\}\\\!\\left\(\\mu\_\{f\\mid\\mathcal\{D\}\_\{t\}\}\(x\_\{t\+1\}\),\\,\\sigma\_\{f\\mid\\mathcal\{D\}\_\{t\}\}^\{2\}\(x\_\{t\+1\}\)\\right\),Yt\+1\|𝒟t,xt\+1\\displaystyle Y\_\{t\+1\}\\mid\\mathcal\{D\}\_\{t\},x\_\{t\+1\}∼𝒩⁡\(μf\|𝒟t​\(xt\+1\),σf\|𝒟t2​\(xt\+1\)\+σn2\),\\displaystyle\\sim\\mathcal\{N\}\\\!\\left\(\\mu\_\{f\\mid\\mathcal\{D\}\_\{t\}\}\(x\_\{t\+1\}\),\\,\\sigma\_\{f\\mid\\mathcal\{D\}\_\{t\}\}^\{2\}\(x\_\{t\+1\}\)\+\\sigma\_\{n\}^\{2\}\\right\),μf\|𝒟t​\(x\)\\displaystyle\\mu\_\{f\\mid\\mathcal\{D\}\_\{t\}\}\(x\)=μ⁡\(x\)\+k⁡\(x,X\)​\(K\+σn2​I\)−1​\(𝐲−μ⁡\(X\)\),\\displaystyle=\\mu\(x\)\+k\(x,X\)\\bigl\(K\+\\sigma\_\{n\}^\{2\}I\\bigr\)^\{\-1\}\\bigl\(\\mathbf\{y\}\-\\mu\(X\)\\bigr\),σf\|𝒟t2​\(x\)\\displaystyle\\sigma\_\{f\\mid\\mathcal\{D\}\_\{t\}\}^\{2\}\(x\)=k⁡\(x,x\)−k⁡\(x,X\)​\(K\+σn2​I\)−1​k​\(X,x\)\.\\displaystyle=k\(x,x\)\-k\(x,X\)\\bigl\(K\+\\sigma\_\{n\}^\{2\}I\\bigr\)^\{\-1\}k\(X,x\)\.Refer to\[[1](https://arxiv.org/html/2609.19891#bib.bib1)\]for more details\. The kernel encodes assumptions about the nature of the function that is being fit \(e\.g\., smoothness, stationarity\)\. When the kernel is ill\-suited for the underlying function, it can lead to subpar performance on tasks that use GPs, a phenomenon referred to as kernel misspecification\.

Figure[1](https://arxiv.org/html/2609.19891#S2.F1)illustrates the effect of kernel misspecification on Gaussian Process regression using the 1D Ackley function\. We fit GPs with a Squared Exponential \(SE\) kernel and a Periodic \(PER\) kernel to the same set of 15 uniformly sampled observations\. While the SE kernel captures the smooth global structure of the function, it fails to model the underlying periodic components present in Ackley, leading to oversmoothing\. In contrast, the Periodic kernel imposes strong periodic inductive bias, which results in spurious oscillations and poor extrapolation outside the observed regions\. This example highlights how inappropriate kernel choices can significantly distort posterior mean and uncertainty estimates, motivating adaptive kernel selection\. In this work, we consider collections of GP models corresponding to different kernels, each inducing its own posterior and acquisition function\.

### 2\.2Bayesian Optimization

Bayesian optimization \(BO\) is a sequential method for optimizing expensive\-to\-evaluate black\-box functionsf:𝒳→ℝf:\\mathcal\{X\}\\to\\mathbb\{R\}, with the goal of findingx∗∈arg⁡maxx∈𝒳⁡f⁡\(x\)x^\{\\ast\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}f\(x\)\. An acquisition functionαt\\alpha\_\{t\}uses the posterior GP conditioned on𝒟t\\mathcal\{D\}\_\{t\}to select the next point to evaluate, viaxt\+1∈arg⁡maxx∈𝒳​αt​\(x\)x\_\{t\+1\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t\}\(x\)\. A popular acquisition function is Expected Improvement \(EI\)\[[24](https://arxiv.org/html/2609.19891#bib.bib24)\], given byEI⁡\(x\)=𝔼⁡\[max⁡\(f⁡\(x\)−y\+,0\)\]\\mathrm\{EI\}\(x\)=\\mathbb\{E\}\[\\max\(f\(x\)\-y^\{\+\},0\)\], wherey\+y^\{\+\}is the best observed output till the current iteration and the expectation is over the distribution provided by the GP posterior atxx\. Other common acquisition functions include UCB and KG\[[16](https://arxiv.org/html/2609.19891#bib.bib16),[25](https://arxiv.org/html/2609.19891#bib.bib25)\]\.

Figure 1:GP Fit on Ackley 1D function for 15 sample data points\.
### 2\.3Level Set Estimation

Level set estimation \(LSE\) aims to identify the super\-level setSh:=\{x∈𝒳:f⁡\(x\)≥h\}S\_\{h\}:=\\\{x\\in\\mathcal\{X\}:f\(x\)\\geq h\\\}of an expensive black\-box function using a limited number of queries\. We focus on the setting where𝒳\\mathcal\{X\}is a fixed, finite set, following Gotovos\[[15](https://arxiv.org/html/2609.19891#bib.bib15)\], andhhis provided as an explicit threshold\. Similar to BO, LSE proceeds sequentially by selecting the next evaluation point via an acquisition function,xt\+1∈arg⁡maxx∈𝒳​αt​\(x\)x\_\{t\+1\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t\}\(x\)\. EI\-LSE\[[17](https://arxiv.org/html/2609.19891#bib.bib17)\]is an acquisition function based on EI for LSE and is given byEI\-LSE​\(x\)=𝔼⁡\[max⁡\(g∗−\|f⁡\(x\)−h\|,0\)\],\\text\{EI\-LSE\}\(x\)=\\mathbb\{E\}\[\\max\(g^\{\*\}\-\|f\(x\)\-h\|,0\)\],whereg∗=min1≤i≤t⁡\|f⁡\(xi\)−h\|g^\{\*\}=\\min\_\{1\\leq i\\leq t\}\|f\(x\_\{i\}\)\-h\|\. Additionally, an exploration termβ​σ2​\(x\)\\beta\\sigma^\{2\}\(x\)is often added, whereβ\\betais a hyperparameter\. Other acquisition functions include straddle\[[14](https://arxiv.org/html/2609.19891#bib.bib14)\]and its generalization\[[15](https://arxiv.org/html/2609.19891#bib.bib15)\], TruVaR\[[26](https://arxiv.org/html/2609.19891#bib.bib26)\]and RMILE\[[18](https://arxiv.org/html/2609.19891#bib.bib18)\]\.

### 2\.4Bayesian Active Learning for Regression

Bayesian active learning \(BAL\) involves querying labels for unlabelled data such that each query maximally reduces the uncertainty about the target functionff\[[20](https://arxiv.org/html/2609.19891#bib.bib20)\]\. We focus on BAL for regression tasks, operating on a finite unlabelled dataset𝒳\\mathcal\{X\}, for which we seek to obtain continuous labels\. Similar to BO and LSE, BAL selects points viaxt\+1∈arg⁡maxx∈𝒳​αt​\(x\)x\_\{t\+1\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t\}\(x\)\. The most common acquisition functions are predictive entropy\[[19](https://arxiv.org/html/2609.19891#bib.bib19)\], which is a monotonic function of the posterior variance for a Gaussian, so maximizing it is equivalent to usingαt​\(x\)=σt2​\(x\)\\alpha\_\{t\}\(x\)=\\sigma\_\{t\}^\{2\}\(x\), and Bayesian Active Learning by Disagreement \(BALD\), which maximizes the expected decrease in predictive entropy\[[21](https://arxiv.org/html/2609.19891#bib.bib21)\]\.

### 2\.5AdaHedge Algorithm

We use AdaHedge\[[4](https://arxiv.org/html/2609.19891#bib.bib4)\], a parameter\-free variant of Hedge\[[5](https://arxiv.org/html/2609.19891#bib.bib5)\]for prediction with expert advice\. At each roundtt, the learner maintains a distributionw\(t\)w^\{\(t\)\}overMMexperts and then observes a loss vectorℓ\(t\)∈\[0,1\]M\\ell^\{\(t\)\}\\in\[0,1\]^\{M\}\. Define the learner’s*expected \(linear\) loss*at roundttash\(t\):=∑m=1Mwm\(t\)​ℓm\(t\)\.h^\{\(t\)\}\\;:=\\;\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\ell\_\{m\}^\{\(t\)\}\.Given a learning rateη\(t\)\\eta^\{\(t\)\}, the corresponding*mix loss*is defined as:

m\(t\):=−1η\(t\)​log⁡\(∑m=1Mwm\(t\)​exp⁡\(−η\(t\)​ℓm\(t\)\)\)\.m^\{\(t\)\}\\;:=\\;\-\\frac\{1\}\{\\eta^\{\(t\)\}\}\\log\\left\(\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\exp\\\!\\big\(\-\\eta^\{\(t\)\}\\ell\_\{m\}^\{\(t\)\}\\big\)\\right\)\.Furthermore, the*per\-round mixability gap*is then defined asδ\(t\):=h\(t\)−m\(t\)≥0\\delta^\{\(t\)\}\\;:=\\;h^\{\(t\)\}\-m^\{\(t\)\}\\;\\geq\\;0and the*cumulative mixability gap*is defined asΔm​i​x\(t\):=∑s=1tδ\(s\)\\Delta\_\{mix\}^\{\(t\)\}:=\\sum\_\{s=1\}^\{t\}\\delta^\{\(s\)\}withΔm​i​x\(0\)=0\\Delta\_\{mix\}^\{\(0\)\}=0\. LettingLm\(t−1\)=∑s=1t−1ℓm\(s\)L\_\{m\}^\{\(t\-1\)\}=\\sum\_\{s=1\}^\{t\-1\}\\ell\_\{m\}^\{\(s\)\}, AdaHedge chooses a data\-dependent learning rate

η\(t\+1\)=ln⁡M/Δm​i​x\(t\),\\eta^\{\(t\+1\)\}\\;=\\;\\ln M/\\Delta\_\{mix\}^\{\(t\)\},\(1\)\(with the conventionη\(1\)=∞\\eta^\{\(1\)\}=\\inftywhenΔ\(0\)=0\\Delta^\{\(0\)\}=0, i\.e\. Follow\-the\-Leader initially\), and sets

wm\(t\+1\)=wm\(1\)​exp⁡\(−η\(t\+1\)​Lm\(t\)\)∑i=1Mwi\(1\)​exp⁡\(−η\(t\+1\)​Li\(t\)\)\.w\_\{m\}^\{\(t\+1\)\}=\\frac\{w\_\{m\}^\{\(1\)\}\\exp\\\!\\big\(\-\\eta^\{\(t\+1\)\}L\_\{m\}^\{\(t\)\}\\big\)\}\{\\sum\_\{i=1\}^\{M\}w\_\{i\}^\{\(1\)\}\\exp\\big\(\-\\eta^\{\(t\+1\)\}L\_\{i\}^\{\(t\)\}\\big\)\}\.After observingℓ\(t\)\\ell^\{\(t\)\}, it updatesΔm​i​x\(t\)=Δm​i​x\(t−1\)\+δ\(t\)\\Delta\_\{mix\}^\{\(t\)\}=\\Delta\_\{mix\}^\{\(t\-1\)\}\+\\delta^\{\(t\)\}using the definition above\. AdaHedge retains the worst\-caseO⁡\(T​log⁡M\)O\(\\sqrt\{T\\log M\}\)regret guarantee while adapting to easier sequences via this self\-tuned learning rate\. Refer to\[[4](https://arxiv.org/html/2609.19891#bib.bib4)\]for more details\.

## 3Methodology

Given a finite set of kernels, our goal is to adaptively emphasize kernels that are most useful for a sequential GP decision task\. We cast this as online learning with expert advice: each kernel defines a GP expert, and we update a distribution over experts based on their per\-round predictive performance and task\-relevant progress\.

Formally, we consider a sequential decision process over roundst=1,…,Tt=1,\\dots,T\. At roundtt, the learner selects a queryxt∈𝒳x\_\{t\}\\in\\mathcal\{X\}, observesyt=f⁡\(xt\)\+ϵty\_\{t\}=f\(x\_\{t\}\)\+\\epsilon\_\{t\}, and appends\(xt,yt\)\(x\_\{t\},y\_\{t\}\)to the dataset𝒟t−1\\mathcal\{D\}\_\{t\-1\}\. The goal is to choose the sequence\{xt\}t=1T\\\{x\_\{t\}\\\}\_\{t=1\}^\{T\}so as to optimize a task\-specific objective \(e\.g\., BO, LSE, or BAL\), which is operationalized through a task\-specific acquisition function\.

Given a set ofMMkernels𝒦=\{k1,…,kM\}\\mathcal\{K\}=\\\{k\_\{1\},\\ldots,k\_\{M\}\\\}, we associate each kernelkmk\_\{m\}with GP expertmm\. At the start of roundtt, expertmmis conditioned on𝒟t−1\\mathcal\{D\}\_\{t\-1\}, inducing the posterior predictive distributionpt,m\(⋅∣x\)∼𝒩\(μt,m\(x\),σt,m2\(x\)\)p\_\{t,m\}\(\\cdot\\mid x\)\\sim\\mathcal\{N\}\\\!\\left\(\\mu\_\{t,m\}\(x\),\\sigma\_\{t,m\}^\{2\}\(x\)\\right\), whereμt,m​\(x\)\\mu\_\{t,m\}\(x\)andσt,m2​\(x\)\\sigma\_\{t,m\}^\{2\}\(x\)denote the posterior predictive mean and variance of expertmmatxx, respectively, with observation noise included when applicable\. LetYt,mY\_\{t,m\}denote the random variable associated with expertmm, so thatYt,m∣x∼pt,m\(⋅∣x\)Y\_\{t,m\}\\mid x\\sim p\_\{t,m\}\(\\cdot\\mid x\)\. Hereafter,mmindexes both the expert and its associated kernel, and dependence on𝒟t−1\\mathcal\{D\}\_\{t\-1\}is suppressed since it is implicit in the round indextt\. We maintain a vector of expert weightsw\(t\)w^\{\(t\)\}with initializationwm\(1\)=1/Mw\_\{m\}^\{\(1\)\}=1/Mand∑m=1Mwm\(t\)=1\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}=1\. Different experts can prefer different query locations at the same roundttdue to differing inductive biases encoded by their kernels\. Our algorithm uses the current weight distribution either to combine expert posteriors into a single acquisition function or to sample a single expert, then uses the observed\(xt,yt\)\(x\_\{t\},y\_\{t\}\)to assign per\-expert losses and updatew\(t\)w^\{\(t\)\}via AdaHedge\. Task\-specific acquisition constructions and loss definitions are given in Sections 5–7\. A brief outline of the proposed algorithm is as follows:

1. 1\.Select a pointxtx\_\{t\}\(Algorithms[1](https://arxiv.org/html/2609.19891#alg1)or[2](https://arxiv.org/html/2609.19891#alg2)\) and observeyty\_\{t\}from the black\-boxff\.
2. 2\.Compute each expert’s lossℓm\(t\)\\ell\_\{m\}^\{\(t\)\}using its posterior predictive distribution at the queried pair\(xt,yt\)\(x\_\{t\},y\_\{t\}\)\.
3. 3\.Update the expert weights via AdaHedge and refit each GP on𝒟t=𝒟t−1∪\{\(xt,yt\)\}\\mathcal\{D\}\_\{t\}=\\mathcal\{D\}\_\{t\-1\}\\cup\\\{\(x\_\{t\},y\_\{t\}\)\\\}\.

### 3\.1AdaHedge for Kernel Mixing

After querying data pointxtx\_\{t\}at iterationtt, each kernel/expertmmincurs alossdenoted byℓm\(t\)\\ell\_\{m\}^\{\(t\)\}\. We assume thatℓm\(t\)∈\[0,1\]\\ell\_\{m\}^\{\(t\)\}\\in\[0,1\]; smaller values ofℓ\\ellare preferred\.Lm\(t\)=∑i=1tℓm\(i\)L\_\{m\}^\{\(t\)\}=\\sum\_\{i=1\}^\{t\}\\ell\_\{m\}^\{\(i\)\}denotes the cumulative loss of expertmmat iterationtt\. The weights for each expertm=1,…,Mm=1,\\dots,Mare updated with an exponential \(multiplicative\-weights\) rule using the AdaHedge*learning\-rate rule*\[[4](https://arxiv.org/html/2609.19891#bib.bib4)\]and are given by

wm\(t\+1\)=wm\(1\)​exp⁡\(−η\(t\+1\)​Lm\(t\)\)∑i=1Mwi\(1\)​exp⁡\(−η\(t\+1\)​Li\(t\)\)\.w\_\{m\}^\{\(t\+1\)\}=\\frac\{w\_\{m\}^\{\(1\)\}\\exp\\\!\\big\(\-\\eta^\{\(t\+1\)\}L\_\{m\}^\{\(t\)\}\\big\)\}\{\\sum\_\{i=1\}^\{M\}w\_\{i\}^\{\(1\)\}\\exp\\big\(\-\\eta^\{\(t\+1\)\}L\_\{i\}^\{\(t\)\}\\big\)\}\.Kernels that repeatedly incur smaller losses accumulate exponentially larger weight over time, while kernels with larger losses are down\-weighted\. AdaHedge provides a conservative online weighting rule whose effective learning rate adapts to the observed separability of the experts\. When losses strongly distinguish kernels, the learning rate permits rapid concentration\. When losses are similar or noisy, the update remains less aggressive, which is desirable because premature kernel commitment can degrade early round performance\.

We consider two types of loss functions\. The first is negative log likelihood \(NLL\) that is designed towards better fitting of the black\-box function\. The second type of loss function is task specific, and its discussion is deferred to later\. Note that NLL measures the “surprise” of a model at seeing the observation\(xt,yt\)\(x\_\{t\},y\_\{t\}\)and is equivalent to maximizing the likelihood of the data given the model\. For likelihood\-based losses, we define the raw lossℓ~m\(t\):=−log⁡pt,m​\(yt∣xt\)\\tilde\{\\ell\}\_\{m\}^\{\(t\)\}:=\-\\log p\_\{t,m\}\(y\_\{t\}\\mid x\_\{t\}\)\. To ensure bounded losses as required by AdaHedge, we apply an affine normalization and clipping:

ℓm\(t\):=min⁡\(1,\(ℓ~m\(t\)−minj⁡ℓ~j\(t\)\)/C\),\\ell\_\{m\}^\{\(t\)\}:=\\min\(1,\\;\(\\tilde\{\\ell\}\_\{m\}^\{\(t\)\}\-\\min\_\{j\}\\tilde\{\\ell\}\_\{j\}^\{\(t\)\}\)/C\),\(2\)whereC\>0C\>0is a fixed scaling constant and is a hyperparameter\. This transformation preserves relative loss differences while ensuringℓm\(t\)∈\[0,1\]\\ell\_\{m\}^\{\(t\)\}\\in\[0,1\]\. AdaHedge is invariant to additive shifts of the losses\. We additionally note that the scaling and clipping are intended to ensure weight stability and avoid abrupt changes observed empirically without this transformation\.

### 3\.2Query Selection

We propose two different methods of using the expert weight distribution to decide the next query point:*mixture of Gaussians \(MoG\)*and*categorical sampling*\.

#### 3\.2\.1Mixture of Gaussians \(MoG\)

At the start of roundtt, each expertmmprovides a posterior predictive distributionpt,m\(⋅∣x\)p\_\{t,m\}\(\\cdot\\mid x\)\. To combine experts at the predictive level, we introduce a kernel index variableMt∼Cat⁡\(w\(t\)\)M\_\{t\}\\sim\\mathrm\{Cat\}\(w^\{\(t\)\}\)\. Conditional onMt=mM\_\{t\}=m, the distribution of the observation ispt,m\(⋅∣x\)∼𝒩\(μt,m\(x\),σt,m2\(x\)\)\.p\_\{t,m\}\(\\cdot\\mid x\)\\sim\\mathcal\{N\}\\\!\\big\(\\mu\_\{t,m\}\(x\),\\,\\sigma^\{2\}\_\{t,m\}\(x\)\\big\)\.Marginalizing overMtM\_\{t\}yields the MoG predictive distribution:

pt,MoG​\(y∣x\)=∑m=1Mwm\(t\)​pt,m​\(y∣x\)\.p\_\{t,\\mathrm\{MoG\}\}\(y\\mid x\)\\;=\\;\\sum\_\{m=1\}^\{M\}w^\{\(t\)\}\_\{m\}\\,p\_\{t,m\}\(y\\mid x\)\.We then construct the acquisitionαt,MoG​\(x\)\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\)using the MoG predictive distributionpt,MoG\(⋅\|x\)p\_\{t,\\mathrm\{MoG\}\}\(\\cdot\|x\), and select the next query asxt∈arg⁡maxx∈𝒳​αt,MoG​\(x\)x\_\{t\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\)\.

Algorithm 1Query Selection via MoG1:Input:search space

𝒳\\mathcal\{X\}; task

Γ\\Gamma; GP posteriors

\{\(μt,m​\(⋅\),σt,m2​\(⋅\)\)\}m=1M\\\{\(\\mu\_\{t,m\}\(\\cdot\),\\sigma\_\{t,m\}^\{2\}\(\\cdot\)\)\\\}\_\{m=1\}^\{M\}; weights

\{wm\(t\)\}m=1M\\\{w\_\{m\}^\{\(t\)\}\\\}\_\{m=1\}^\{M\}\.

2:Output:query point

xt∈𝒳x\_\{t\}\\in\\mathcal\{X\}\.

3:MoG predictive distribution:for each

x∈𝒳x\\in\\mathcal\{X\},

pt,MoG​\(y∣x\)←∑m=1Mwm\(t\)​pt,m​\(y∣x\)\.p\_\{t,\\mathrm\{MoG\}\}\(y\\mid x\)\\;\\leftarrow\\;\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,p\_\{t,m\}\(y\\mid x\)\.
4:Acquisition:define

αt,MoG​\(x\)\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\)from

pt,MoG\(⋅∣x\)p\_\{t,\\mathrm\{MoG\}\}\(\\cdot\\mid x\)according to task

Γ\\Gamma\.

5:Point selection:

xt←arg⁡maxx∈𝒳​αt,MoG​\(x\)x\_\{t\}\\leftarrow\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\)\.

6:return

xtx\_\{t\}\.

#### 3\.2\.2Categorical Sampling

As an alternative to MoG, we can sample a single expert according to the current AdaHedge weights and obtainxtx\_\{t\}using that expert’s posterior predictive distribution only\. We draw an expert indexmtm\_\{t\}fromMtM\_\{t\}and then use the sampled expert’s GP posterior predictive distributionpt,mt\(⋅∣x\)p\_\{t,m\_\{t\}\}\(\\cdot\\mid x\)and its acquisition functionαt,mt​\(x\)\\alpha\_\{t,m\_\{t\}\}\(x\)\. We select the next query point byxt∈arg⁡maxx∈𝒳​αt,mt​\(x\)\.x\_\{t\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,m\_\{t\}\}\(x\)\.

Algorithm 2Query Selection via Categorical Sampling1:Input:search space

𝒳\\mathcal\{X\}; task

Γ\\Gamma; GP posteriors

\{\(μt,m​\(⋅\),σt,m2​\(⋅\)\)\}m=1M\\\{\(\\mu\_\{t,m\}\(\\cdot\),\\sigma\_\{t,m\}^\{2\}\(\\cdot\)\)\\\}\_\{m=1\}^\{M\}; weights

\{wm\(t\)\}m=1M\\\{w\_\{m\}^\{\(t\)\}\\\}\_\{m=1\}^\{M\}\.

2:Output:query point

xt∈𝒳x\_\{t\}\\in\\mathcal\{X\}\.

3:For each

m=1,…,Mm=1,\\dots,M, define acquisition

αt,m​\(x\)\\alpha\_\{t,m\}\(x\)from

pt,m\(⋅∣x\)p\_\{t,m\}\(\\cdot\\mid x\)according to task

Γ\\Gamma\.

4:Sample kernel index

mtm\_\{t\}from

MtM\_\{t\}\.

5:Set

xt←arg⁡maxx∈𝒳​αt,mt​\(x\)x\_\{t\}\\leftarrow\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,m\_\{t\}\}\(x\)\.

6:return

xtx\_\{t\}\.

Algorithm 3HACK Algorithm \(task\-agnostic\)1:Input:search space

𝒳\\mathcal\{X\}; kernels

𝒦=\{k1,…,kM\}\\mathcal\{K\}=\\\{k\_\{1\},\\dots,k\_\{M\}\\\}; task

Γ\\Gamma; point\-selection routineSelectQuery\(Alg\.[1](https://arxiv.org/html/2609.19891#alg1)or[2](https://arxiv.org/html/2609.19891#alg2)\); task loss

ℓΓ\\ell\_\{\\Gamma\}; iterations

TT\.

2:Output:task\-specific estimate

θ^T\\hat\{\\theta\}\_\{T\}\.

3:Initialize data

𝒟0\\mathcal\{D\}\_\{0\}; fit GP posteriors

\{𝒢​𝒫m\(0\)\}m=1M\\\{\\mathcal\{GP\}^\{\(0\)\}\_\{m\}\\\}\_\{m=1\}^\{M\}on

𝒟0\\mathcal\{D\}\_\{0\}\.

4:Initialize weights

wm\(1\)←1/Mw\_\{m\}^\{\(1\)\}\\leftarrow 1/Mand cumulative losses

Lm\(0\)←0L\_\{m\}^\{\(0\)\}\\leftarrow 0for all

m=1,…,Mm=1,\\dots,M\.

5:for

t=1t=1to

TTdo

6:Point selection:

xt←SelectQuery​\(𝒳,\{𝒢​𝒫m\(t−1\)\}m=1M,𝒘\(t\),Γ\)x\_\{t\}\\leftarrow\\textsc\{SelectQuery\}\(\\mathcal\{X\},\\\{\\mathcal\{GP\}\_\{m\}^\{\(t\-1\)\}\\\}\_\{m=1\}^\{M\},\\bm\{w\}^\{\(t\)\},\\Gamma\)\.

7:Query:observe

yt=f⁡\(xt\)\+ϵty\_\{t\}=f\(x\_\{t\}\)\+\\epsilon\_\{t\}\.

8:Loss computation:for each

m=1,…,Mm=1,\\dots,M,

ℓm\(t\)←ℓΓ​\(𝒢​𝒫m\(t−1\),xt,yt,𝒟t−1\),\\ell\_\{m\}^\{\(t\)\}\\leftarrow\\ell\_\{\\Gamma\}\(\\mathcal\{GP\}\_\{m\}^\{\(t\-1\)\},x\_\{t\},y\_\{t\},\\mathcal\{D\}\_\{t\-1\}\),Lm\(t\)←Lm\(t−1\)\+ℓm\(t\)\.L\_\{m\}^\{\(t\)\}\\leftarrow L\_\{m\}^\{\(t\-1\)\}\+\\ell\_\{m\}^\{\(t\)\}\.
9:Learning\-rate update:update

η\(t\+1\)\\eta^\{\(t\+1\)\}according to the AdaHedge rule described in Equation[1](https://arxiv.org/html/2609.19891#S2.E1)\.

10:Weight update:for all

m=1,…,Mm=1,\\dots,M,

wm\(t\+1\)←wm\(1\)​exp⁡\(−η\(t\+1\)​Lm\(t\)\)∑i=1Mwi\(1\)​exp⁡\(−η\(t\+1\)​Li\(t\)\)\.w\_\{m\}^\{\(t\+1\)\}\\leftarrow\\frac\{w\_\{m\}^\{\(1\)\}\\exp\\\!\\big\(\-\\eta^\{\(t\+1\)\}L\_\{m\}^\{\(t\)\}\\big\)\}\{\\sum\_\{i=1\}^\{M\}w\_\{i\}^\{\(1\)\}\\exp\\big\(\-\\eta^\{\(t\+1\)\}L\_\{i\}^\{\(t\)\}\\big\)\}\.
11:Update

𝒟t←𝒟t−1∪\{\(xt,yt\)\}\\mathcal\{D\}\_\{t\}\\leftarrow\\mathcal\{D\}\_\{t\-1\}\\cup\\\{\(x\_\{t\},y\_\{t\}\)\\\}and update each

𝒢​𝒫m\(t−1\)\\mathcal\{GP\}^\{\(t\-1\)\}\_\{m\}using

𝒟t\\mathcal\{D\}\_\{t\}to obtain posterior

𝒢​𝒫m\(t\)\\mathcal\{GP\}^\{\(t\)\}\_\{m\}\.

12:endfor

13:return

θ^T←DecideΓ​\(𝒟T,\{𝒢​𝒫m\(T\)\}m=1M,𝒘\(T\+1\)\)\\hat\{\\theta\}\_\{T\}\\leftarrow\\textsc\{Decide\}\_\{\\Gamma\}\(\\mathcal\{D\}\_\{T\},\\\{\\mathcal\{GP\}^\{\(T\)\}\_\{m\}\\\}\_\{m=1\}^\{M\},\\bm\{w\}^\{\(T\+1\)\}\)\.

A generic task\-agnostic version of our algorithm is presented in Algorithm[3](https://arxiv.org/html/2609.19891#alg3)\. We hereafter refer to the use of Algorithm[3](https://arxiv.org/html/2609.19891#alg3)with MoG \(Algorithm[1](https://arxiv.org/html/2609.19891#alg1)\) as HACK\-MoG and with categorical selection \(Algorithm[2](https://arxiv.org/html/2609.19891#alg2)\) as HACK\-Cat\. The task\-specific estimatesθ^T\\hat\{\\theta\}\_\{T\}returned from the last step of Algorithm[3](https://arxiv.org/html/2609.19891#alg3)DecideΓ\\textsc\{Decide\}\_\{\\Gamma\}are:

1. 1\.BO:θ^T=x^∈argmax\(xi,yi\)∈𝒟Tyi\\hat\{\\theta\}\_\{T\}=\\hat\{x\}\\in\\argmax\_\{\(x\_\{i\},y\_\{i\}\)\\in\\mathcal\{D\}\_\{T\}\}y\_\{i\};
2. 2\.LSE:θ^T=\{x∈𝒳:∑m=1Mwm\(T\+1\)​μm,T​\(x\)≥h\}\\hat\{\\theta\}\_\{T\}=\\\{x\\in\\mathcal\{X\}:\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(T\+1\)\}\\mu\_\{m,T\}\(x\)\\geq h\\\};
3. 3\.BAL :θ^T=𝒟T\\hat\{\\theta\}\_\{T\}=\\mathcal\{D\}\_\{T\}\.

The learning rateη\(t\+1\)\\eta^\{\(t\+1\)\}is updated at each iteration according to the AdaHedge rule given in Equation[1](https://arxiv.org/html/2609.19891#S2.E1), after computing the round\-ttlosses and before updating the expert weights\. The GP experts are then updated using the augmented dataset𝒟t\\mathcal\{D\}\_\{t\}\. Additionally, AdaHedge can also be replaced by standard Hedge\[[5](https://arxiv.org/html/2609.19891#bib.bib5)\], results of which can be found in[C\.2](https://arxiv.org/html/2609.19891#A3.SS2)\.

### 3\.3Computational Complexity

Table[1](https://arxiv.org/html/2609.19891#S3.T1)provides a breakdown of the computational complexity of both HACK\-MoG and HACK\-Cat in comparison with a standard single kernel GP decision making process\. Acquisition function optimization is performed using multi\-start L\-BFGS and therefore requires multiple acquisition function evaluations\. The complexities reported in Table[1](https://arxiv.org/html/2609.19891#S3.T1)correspond to the cost of a single such evaluation\. For HACK\-Cat, each acquisition function evaluation requires the posterior of only the sampled expert, whereas for HACK\-MoG it requires the posterior from all experts\. In addition, both HACK variants evaluate allMMexpert posteriors at the queried point to compute their losses\.

We note that the primary increase in computational overhead in HACK comes from the need to refit all theMMkernels present in the family versus updating only 1 kernel for a standard GP\. HACK\-MoG incurs an additional factor ofMMduring acquisition evaluation because its mixture acquisition depends on all expert posteriors\. Thus, for a fixed number of candidate kernels, the additional cost of HACK scales linearly with the size of the kernel family\. In applications where black\-box evaluations dominate computational cost andMMis small, this overhead may remain modest\. We also provide an empirical wall\-clock comparison with simple baselines in[C\.4](https://arxiv.org/html/2609.19891#A3.SS4)\.

Table 1:Per\-iteration computational complexity\.nndenotes the number of observations andMMthe number of candidate kernels\. Refer to Section[3\.3](https://arxiv.org/html/2609.19891#S3.SS3)for more details\.

## 4Theoretical Analysis

We now provide some general theoretical results that are used for all three tasks considered in this paper\. These results are intentionally stated for abstract, task\-agnostic functions and generic expert losses\. Later we will specialize these to each task\. Proofs and technical details may be found in[A\.1](https://arxiv.org/html/2609.19891#A1.SS1)\.

###### Lemma 4\.1\.

For the MoG predictive distributionpt,MoG​\(y∣x\)=∑m=1Mwm\(t\)​pt,m​\(y∣x\)p\_\{t,\\mathrm\{MoG\}\}\(y\\mid x\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,p\_\{t,m\}\(y\\mid x\), the mean and variance areμ¯t​\(x\)=∑m=1Mwm\(t\)​μt,m​\(x\)\\bar\{\\mu\}\_\{t\}\(x\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\mu\_\{t,m\}\(x\),

σ¯t2​\(x\)=∑m=1Mwm\(t\)​σt,m2​\(x\)⏟within\-kernel\+∑m=1Mwm\(t\)​\(μt,m​\(x\)−μ¯t​\(x\)\)2⏟between\-kernel \(disagreement\)\.\\bar\{\\sigma\}^\{2\}\_\{t\}\(x\)=\\underbrace\{\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\sigma^\{2\}\_\{t,m\}\(x\)\}\_\{\\text\{within\-kernel\}\}\+\\underbrace\{\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\big\(\\mu\_\{t,m\}\(x\)\-\\bar\{\\mu\}\_\{t\}\(x\)\\big\)^\{2\}\}\_\{\\text\{between\-kernel \(disagreement\)\}\}\.

###### Proof\.

LetYt∣x∼pt,MoG\(⋅∣x\)Y\_\{t\}\\mid x\\sim p\_\{t,\\mathrm\{MoG\}\}\(\\cdot\\mid x\)\. The mean follows directly from the law of total expectation:

𝔼⁡\[Yt∣x\]=𝔼Mt​\[μt,m​\(x\)\]=∑m=1Mwm\(t\)​μt,m​\(x\)\.\\mathbb\{E\}\[Y\_\{t\}\\mid x\]=\\mathbb\{E\}\_\{M\_\{t\}\}\[\\mu\_\{t,m\}\(x\)\]=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\mu\_\{t,m\}\(x\)\.Using the law of total variance, we have

Var⁡\(Yt∣x\)\\displaystyle\\mathrm\{Var\}\(Y\_\{t\}\\mid x\)=𝔼Mt\[Var\(Yt∣\(Mt=m\),x\)\]\+VarMt\(𝔼\[Yt∣\(Mt=m\),x\]\)\\displaystyle=\\mathbb\{E\}\_\{M\_\{t\}\}\\\!\\Big\[\\mathrm\{Var\}\\\!\\big\(Y\_\{t\}\\mid\(M\_\{t\}=m\),x\\big\)\\Big\]\+\\mathrm\{Var\}\_\{M\_\{t\}\}\\\!\\Big\(\\mathbb\{E\}\\\!\\big\[Y\_\{t\}\\mid\(M\_\{t\}=m\),x\\big\]\\Big\)=𝔼Mt​\[σt,m2​\(x\)\]\+VarMt​\(μt,m​\(x\)\)\\displaystyle=\\mathbb\{E\}\_\{M\_\{t\}\}\\\!\\big\[\\sigma^\{2\}\_\{t,m\}\(x\)\\big\]\+\\mathrm\{Var\}\_\{M\_\{t\}\}\\\!\\big\(\\mu\_\{t,m\}\(x\)\\big\)=∑m=1Mwm\(t\)​σt,m2​\(x\)\+∑m=1Mwm\(t\)​\(μt,m​\(x\)−∑j=1Mwj\(t\)​μt,j​\(x\)\)2\.\\displaystyle=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\sigma^\{2\}\_\{t,m\}\(x\)\+\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\Big\(\\mu\_\{t,m\}\(x\)\-\\sum\_\{j=1\}^\{M\}w\_\{j\}^\{\(t\)\}\\,\\mu\_\{t,j\}\(x\)\\Big\)^\{2\}\.Defining the mixture meanμ¯t​\(x\):=∑m=1Mwm\(t\)​μt,m​\(x\)\\bar\{\\mu\}\_\{t\}\(x\):=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\mu\_\{t,m\}\(x\), the above can be written as

Var⁡\(Yt∣x,𝒟t−1\)=∑m=1Mwm\(t\)​σt,m2​\(x\)\+∑m=1Mwm\(t\)​\(μt,m​\(x\)−μ¯t​\(x\)\)2\.∎\\mathrm\{Var\}\(Y\_\{t\}\\mid x,\\mathcal\{D\}\_\{t\-1\}\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\sigma^\{2\}\_\{t,m\}\(x\)\+\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\big\(\\mu\_\{t,m\}\(x\)\-\\bar\{\\mu\}\_\{t\}\(x\)\\big\)^\{2\}\.\\qed

We denote the between\-kernel disagreement term byαt,disag​\(x\):=∑m=1Mwm\(t\)​\(μt,m​\(x\)−μ¯t​\(x\)\)2\.\\alpha\_\{t,\\mathrm\{disag\}\}\(x\):=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\left\(\\mu\_\{t,m\}\(x\)\-\\bar\{\\mu\}\_\{t\}\(x\)\\right\)^\{2\}\.The equality in Lemma[4\.1](https://arxiv.org/html/2609.19891#S4.Thmtheorem1)is a standard mixture identity\. The first term is the average of the per\-expert posterior variances\. The second term captures disagreement among experts and thus quantifies how much mixture uncertainty is driven by between\-expert differences in predictive means\.

The following two lemmas, Lemma[4\.2](https://arxiv.org/html/2609.19891#S4.Thmtheorem2)and Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)provide lower bounds for the number of iterationsTTfor AdaHedge to concentrate on the best expert under the assumption of a loss gap\. Here,m∗m^\{\*\}denotes the best\-performing kernel under the chosen HACK loss\. Proofs for both the AdaHedge and Hedge variant can be found in[A\.1](https://arxiv.org/html/2609.19891#A1.SS1)\.[C\.3](https://arxiv.org/html/2609.19891#A3.SS3)also provides empirical support for our loss gap assumption\.

###### Lemma 4\.2\.

Assume the per\-round loss difference between the best expertm∗m^\{\*\}and every other expertm≠m∗m\\neq m^\{\*\}is bounded from below,ℓm\(t\)−ℓm∗\(t\)≥Δ\>0\\ell\_\{m\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}\\geq\\Delta\>0\. DefineaM:=1\+23​ln⁡Ma\_\{M\}:=1\+\\frac\{2\}\{3\}\\ln M\. Thenwm∗\(T\)≥1−εw\_\{m^\{\*\}\}^\{\(T\)\}\\geq 1\-\\varepsilonfor

T≥1\+max⁡\{4​aM2ln⁡M,1Δ2​ln⁡M​ln2⁡\(\(M−1\)​\(1−ε\)ε\)\}\.T\\geq 1\+\\max\\left\\\{\\frac\{4a\_\{M\}^\{2\}\}\{\\ln M\},\\frac\{1\}\{\\Delta^\{2\}\\ln M\}\\ln^\{2\}\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\\right\\\}\.

Lemma[4\.2](https://arxiv.org/html/2609.19891#S4.Thmtheorem2)is a reasonably straightforward consequence of the analysis of AdaHedge under a uniform deterministic gap\. The bound makes explicit the dependence on the number of expertsMM, the gapΔ\\Delta, and the desired confidence level1−ε1\-\\varepsilon\.

###### Lemma 4\.3\.

Let\(ℱt\)t≥0\(\\mathcal\{F\}\_\{t\}\)\_\{t\\geq 0\}be a filtration such that the loss vectorℓ\(t\)∈\[0,1\]M\\ell^\{\(t\)\}\\in\[0,1\]^\{M\}isℱt\\mathcal\{F\}\_\{t\}\-measurable\. Fix an expertm∗∈\{1,…,M\}m^\{\*\}\\in\\\{1,\\ldots,M\\\}\. Suppose there existsΔ\>0\\Delta\>0such that, for everym≠m∗m\\neq m^\{\*\}and everyt=1,…,T−1t=1,\\ldots,T\-1,𝔼⁡\[ℓm\(t\)−ℓm∗\(t\)\|ℱt−1\]≥Δ\\mathbb\{E\}\[\\ell\_\{m\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}\|\\mathcal\{F\}\_\{t\-1\}\]\\geq\\Delta\. DefineaM:=1\+23​ln⁡Ma\_\{M\}:=1\+\\frac\{2\}\{3\}\\ln M\. Thenwm∗\(T\)≥1−εw\_\{m^\{\*\}\}^\{\(T\)\}\\geq 1\-\\varepsilonwith probability1−δ01\-\\delta\_\{0\}for

T≥1\+max\{4​aM2ln⁡M,4Δ2​ln⁡Mln2\(\(M−1\)​\(1−ε\)ε\),32Δ2ln\(M−1δ0\)\}\.\\begin\{split\}T\\geq 1\+\\max\\Bigg\\\{&\\frac\{4a\_\{M\}^\{2\}\}\{\\ln M\},\\;\\frac\{4\}\{\\Delta^\{2\}\\ln M\}\\ln^\{2\}\\\!\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\),\\frac\{32\}\{\\Delta^\{2\}\}\\ln\\\!\\left\(\\frac\{M\-1\}\{\\delta\_\{0\}\}\\right\)\\Bigg\\\}\.\\end\{split\}

Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)relaxes the deterministic gap to an expected gap conditioned on the history\. The result again follows from AdaHedge martingale\-style arguments and standard concentration bound arguments; details are in[A\.1](https://arxiv.org/html/2609.19891#A1.SS1)\.

The next theorem formalizes the intuitive statement that if the MoG acquisition function is uniformly close to the best expert’s acquisition function, then the point selected by maximizing the MoG acquisition achieves nearly the same acquisition value under the best expert\.

###### Proposition 4\.4\.

For an iterationttand expertm∗m^\{\*\}, suppose there existsδ≥0\\delta\\geq 0such thatsupx∈𝒳\|αt,M​o​G​\(x\)−αt,m∗​\(x\)\|≤δ\.\\sup\_\{x\\in\\mathcal\{X\}\}\\big\|\\alpha\_\{t,MoG\}\(x\)\-\\alpha\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\delta\.Letxt∈arg⁡maxx∈𝒳​αt,M​o​G​\(x\)​and​xt∗∈arg⁡maxx∈𝒳​αt,m∗​\(x\)\.x\_\{t\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,MoG\}\(x\)\\ \\text\{and\}\\ x\_\{t\}^\{\*\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,m^\{\*\}\}\(x\)\.Thenαt,m∗​\(xt\)≥αt,m∗​\(xt∗\)−2​δ\.\\alpha\_\{t,m^\{\*\}\}\(x\_\{t\}\)\\geq\\alpha\_\{t,m^\{\*\}\}\(x\_\{t\}^\{\*\}\)\-~2\\delta\.

###### Proof\.

By our hypothesis,supx∈𝒳\|αt,MoG​\(x\)−αt,m∗​\(x\)\|≤δ,\\sup\_\{x\\in\\mathcal\{X\}\}\\big\|\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\alpha\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\delta,so for everyx∈𝒳x\\in\\mathcal\{X\},

αt,m∗​\(x\)≥αt,MoG​\(x\)−δandαt,MoG​\(x\)≥αt,m∗​\(x\)−δ\.\\alpha\_\{t,m^\{\*\}\}\(x\)\\geq\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\delta\\quad\\text\{and\}\\quad\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\)\\geq\\alpha\_\{t,m^\{\*\}\}\(x\)\-\\delta\.Sincext∈arg⁡maxx∈𝒳​αt,MoG​\(x\)x\_\{t\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\), we haveαt,MoG​\(xt\)≥αt,MoG​\(xt∗\)\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\_\{t\}\)\\geq\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\_\{t\}^\{\*\}\)\. Therefore,

αt,m∗​\(xt\)≥αt,MoG​\(xt\)−δ≥αt,MoG​\(xt∗\)−δ≥αt,m∗​\(xt∗\)−2​δ,\\alpha\_\{t,m^\{\*\}\}\(x\_\{t\}\)\\geq\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\_\{t\}\)\-\\delta\\geq\\alpha\_\{t,\\mathrm\{MoG\}\}\(x\_\{t\}^\{\*\}\)\-\\delta\\geq\\alpha\_\{t,m^\{\*\}\}\(x\_\{t\}^\{\*\}\)\-2\\delta,which proves the claim\. ∎

Proposition[4\.4](https://arxiv.org/html/2609.19891#S4.Thmtheorem4)is a simple stability\-of\-argmax statement\. It requires a uniform approximation guarantee of the MoG acquisition function by the best expert’s acquisition function over all𝒳\\mathcal\{X\}\.

The results above identify a generic mechanism: when the expert losses induce a persistent gapΔ\\Delta, the AdaHedge algorithm concentrates the weights on the best expert, and the mixture\-of\-Gaussians predictive distribution and its associated acquisition function become uniformly close to those of that expert\. What remains is to specify, for each task, loss functions that reliably reflect task\-relevant progress and to verify that the corresponding acquisition functions satisfy the regularity conditions required by the generic results\. In the following sections, we instantiate this framework for BO, LSE, and BAL, showing how appropriate task\-specific losses and acquisition constructions allow the generic concentration and stability arguments to translate into concrete, task\-relevant consequences\.

## 5Bayesian Optimization

We first specialize the generic expert\-advice framework and theoretical results to Bayesian Optimization \(BO\)\. We define a task\-specific loss that rewards predictive improvement, describe the resulting acquisition construction under the MoG predictive distribution, and show how expert weight concentration translates into uniform closeness of the BO acquisition function\.

### 5\.1Loss and Acquisition function

In BO, a natural notion of per\-round task progress is whether the newly queried point improves upon the best observed value so far\. This motivates losses that reward accurate prediction of improvement events, rather than purely predictive fit\. To capture this, we propose a Brier score based loss\[[27](https://arxiv.org/html/2609.19891#bib.bib27)\]where the binary event indicates whether the new observation improves upon the existing maximum\. Expertmmgives a posterior predictive distribution for the next observationYt,m\|xt∼𝒩⁡\(μt,m​\(xt\),σt,m2​\(xt\)\)Y\_\{t,m\}\\mid x\_\{t\}\\sim\\mathcal\{N\}\(\\mu\_\{t,m\}\(x\_\{t\}\),\\sigma^\{2\}\_\{t,m\}\(x\_\{t\}\)\)\. Define the predicted improvement probability

πt,mbo​\(xt\):=ℙ⁡\(Yt,m≥yt−1∗∣xt\)=Φ⁡\(\(μt,m​\(xt\)−yt−1∗\)/σt,m​\(xt\)\),\\pi^\{\\textsc\{bo\}\}\_\{t,m\}\(x\_\{t\}\):=\\mathbb\{P\}\(Y\_\{t,m\}\\geq y^\{\*\}\_\{t\-1\}\\mid x\_\{t\}\)=\\Phi\\\!\\big\(\(\\mu\_\{t,m\}\(x\_\{t\}\)\-y^\{\*\}\_\{t\-1\}\)/\\sigma\_\{t,m\}\(x\_\{t\}\)\\big\),whereΦ\\Phiis the standard normal CDF\. We then define the Brier loss as

ℓm,brier\(t\):=\(𝟏\{yt≥yt−1∗\}−πt,mbo\(xt\)\)2\.\\ell^\{\(t\)\}\_\{m,\\textsc\{brier\}\}:=\\Big\(\\mathbf\{1\}\\\{y\_\{t\}\\geq y^\{\*\}\_\{t\-1\}\\\}\-\\pi^\{\\textsc\{bo\}\}\_\{t,m\}\(x\_\{t\}\)\\Big\)^\{2\}\.The Brier score is a proper scoring rule for probabilistic binary events and is naturally bounded in\[0,1\]\[0,1\], making it well suited for expert\-advice algorithms\. To combine the model fit loss \(NLL, Equation[2](https://arxiv.org/html/2609.19891#S3.E2)\) and task loss, we use a convex combination of the two and considerℓm\(t\)=α​ℓm,brier\(t\)\+\(1−α\)​ℓm,nll\(t\)\.\\ell^\{\(t\)\}\_\{m\}=\\alpha\\,\\ell^\{\(t\)\}\_\{m,\\textsc\{brier\}\}\+\(1\-\\alpha\)\\,\\ell^\{\(t\)\}\_\{m,\\textsc\{nll\}\}\.The NLL term encourages overall predictive calibration, while the task loss focuses the weighting on task\-relevant predictive behavior\. We find that combining the two stabilizes learning in early rounds, when task\-specific signals alone may be noisy\. Empirically, we find thatα=0\.5\\alpha=0\.5provides a good tradeoff\. Results with other loss functions are in[C\.1](https://arxiv.org/html/2609.19891#A3.SS1)\. In all our BO experiments, we use the EI acquisition function\. Due to linearity of expectation, the EI of the MoG predictive distribution is:

EIt,MoG​\(x\)=∑m=1Mwm\(t\)​EIt,m​\(x\)\.\\mathrm\{EI\}\_\{t,\\mathrm\{MoG\}\}\(x\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\mathrm\{EI\}\_\{t,m\}\(x\)\.This linearity allows EI to be computed exactly under the MoG predictive distribution without approximation, preserving the semantics of EI while enabling adaptive kernel weighting\.

### 5\.2Theoretical Analysis

We now show how the generic concentration and stability results from Section[4](https://arxiv.org/html/2609.19891#S4)translate into acquisition\-level guarantees for BO when EI is used as the acquisition function\. The key property is the linearity of EI under the MoG predictive distribution\. The following lemma shows that expert weight concentration directly implies uniform closeness of the EI acquisition\.

###### Lemma 5\.1\.

For each roundtt, assume∃BEI<∞\\exists B\_\{\\mathrm\{EI\}\}<\\inftysuch thatE​It,m​\(x\)≤BEIEI\_\{t,m\}\(x\)\\leq B\_\{\\mathrm\{EI\}\}for every expertmmand everyx∈𝒳x\\in\\mathcal\{X\}\. Ifwm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\varepsilon, then

supx∈𝒳\|EIt,MoG​\(x\)−EIt,m∗​\(x\)\|≤ε​BEI\.\\sup\_\{x\\in\\mathcal\{X\}\}\|\\mathrm\{EI\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\|\\leq\\varepsilon B\_\{\\mathrm\{EI\}\}\.

###### Proof\.

By the MoG construction,EIt,MoG​\(x\)=∑m=1Mwm\(t\)​EIt,m​\(x\)\.\\mathrm\{EI\}\_\{t,\\mathrm\{MoG\}\}\(x\)=\\sum\_\{m=1\}^\{M\}w^\{\(t\)\}\_\{m\}\\,\\mathrm\{EI\}\_\{t,m\}\(x\)\.Hence, for any fixedx∈𝒳x\\in\\mathcal\{X\},

EIt,MoG​\(x\)−EIt,m∗​\(x\)\\displaystyle\\mathrm\{EI\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)=∑m=1Mwm\(t\)​EIt,m​\(x\)−EIt,m∗​\(x\)\\displaystyle=\\sum\_\{m=1\}^\{M\}w^\{\(t\)\}\_\{m\}\\,\\mathrm\{EI\}\_\{t,m\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)=∑m≠m∗wm\(t\)​\(EIt,m​\(x\)−EIt,m∗​\(x\)\)\.\\displaystyle=\\sum\_\{m\\neq m^\{\*\}\}w^\{\(t\)\}\_\{m\}\\Big\(\\mathrm\{EI\}\_\{t,m\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\\Big\)\.Taking absolute values and applying the triangle inequality gives us

\|EIt,MoG​\(x\)−EIt,m∗​\(x\)\|≤∑m≠m∗wm\(t\)​\|EIt,m​\(x\)−EIt,m∗​\(x\)\|\.\\big\|\\mathrm\{EI\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\sum\_\{m\\neq m^\{\*\}\}w^\{\(t\)\}\_\{m\}\\,\\big\|\\mathrm\{EI\}\_\{t,m\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\\big\|\.Since0≤EIt,m​\(x\)≤BEI0\\leq\\mathrm\{EI\}\_\{t,m\}\(x\)\\leq B\_\{\\mathrm\{EI\}\}for allmm, we have\|EIt,m​\(x\)−EIt,m∗​\(x\)\|≤BEI\\big\|\\mathrm\{EI\}\_\{t,m\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq B\_\{\\mathrm\{EI\}\}, and therefore

\|EIt,MoG​\(x\)−EIt,m∗​\(x\)\|≤∑m≠m∗wm\(t\)​BEI=\(1−wm∗\(t\)\)​BEI≤ε​BEI\.\\big\|\\mathrm\{EI\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\sum\_\{m\\neq m^\{\*\}\}w^\{\(t\)\}\_\{m\}\\,B\_\{\\mathrm\{EI\}\}=\(1\-w^\{\(t\)\}\_\{m^\{\*\}\}\)B\_\{\\mathrm\{EI\}\}\\leq\\varepsilon\\,B\_\{\\mathrm\{EI\}\}\.supx\|EIt,M​o​G​\(x\)−EIt,m∗​\(x\)\|≤ε​BEI\.∎\\sup\_\{x\}\|\\mathrm\{EI\}\_\{t,MoG\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\|\\leq\\varepsilon B\_\{\\mathrm\{EI\}\}\.\\qed

This boundedness holds under standard GP regularity conditions \(compact𝒳\\mathcal\{X\}, continuous bounded kernels, and a positive noise variance ensuring well\-defined posterior mean/variance\), sinceEIt,m​\(x\)\\mathrm\{EI\}\_\{t,m\}\(x\)is continuous on𝒳\\mathcal\{X\}and hence attains a finite maximum\. We next recall the results characterizing EI regret that will serve as the basis for subsequent results\. We begin by restating in our notation, a key result from Nguyen et al\.\[[28](https://arxiv.org/html/2609.19891#bib.bib28), Theorem 4\]that requires the following assumptions\.

###### Assumption A1\.

1. \(i\)ffbelongs to the RKHSℋk\\mathcal\{H\}\_\{k\}associated with the GP kernel, with bounded RKHS norm‖f‖k<∞\\\|f\\\|\_\{k\}<\\infty\.
2. \(ii\)The kernel is normalized, withk⁡\(x,x\)=1k\(x,x\)=1for allx∈𝒳x\\in\\mathcal\{X\}\.
3. \(iii\)The GP confidence event stated below holds true with probability at least1−δNg1\-\\delta\_\{\\mathrm\{Ng\}\} \|μt−1​\(x\)−f⁡\(x\)\|≤βt​σt−1​\(x\),∀t,∀x∈𝒳\.\|\\mu\_\{t\-1\}\(x\)\-f\(x\)\|\\leq\\sqrt\{\\beta\_\{t\}\}\\,\\sigma\_\{t\-1\}\(x\),\\qquad\\forall\\,t,\\ \\forall\\,x\\in\\mathcal\{X\}\.
4. \(iv\)The EI stopping condition holds on the rounds under consideration: the EI value at the selected point remains at leastκ\>0\\kappa\>0\.

###### Theorem 5\.2\(Consequence of Nguyen et al\.\[[28](https://arxiv.org/html/2609.19891#bib.bib28)\]\)\.

Fix a kernelkm∗k\_\{m^\{\*\}\}satisfying Assumption[A1](https://arxiv.org/html/2609.19891#Thmngassumption1)\. Suppose EI is run with the best\-observed incumbentytmaxy\_\{t\}^\{\\max\}\. LetγTm∗\\gamma\_\{T\}^\{m^\{\*\}\}denote the maximum information gain of expertm∗m^\{\*\}, letσn2\\sigma\_\{n\}^\{2\}be the observation\-noise variance, and define

βTm∗::=2​‖f‖km∗2\+300​γTm∗​log3⁡\(TδNg\)andCκ=log⁡\(12​π​κ2\)\.\\beta\_\{T\}^\{m^\{\*\}\}::=2\\\|f\\\|\_\{k\_\{m^\{\*\}\}\}^\{2\}\+300\\gamma\_\{T\}^\{m^\{\*\}\}\\log^\{3\}\\\!\\left\(\\frac\{T\}\{\\delta\_\{\\mathrm\{Ng\}\}\}\\right\)\\quad\\text\{and\}\\quad C\_\{\\kappa\}=\\log\\\!\\left\(\\frac\{1\}\{2\\pi\\kappa^\{2\}\}\\right\)\.Then, with probability at least1−δNg1\-\\delta\_\{\\mathrm\{Ng\}\}, the cumulative regret of EI using expertm∗m^\{\*\}satisfies

RT≤2​T​γTm∗log⁡\(1\+σn−2\)​\[3​\(βTm∗\+1\+Cκ\)\+βTm∗\]=O⁡\(T​βTm∗​γTm∗\)\.R\_\{T\}\\leq\\sqrt\{\\frac\{2T\\gamma\_\{T\}^\{m^\{\*\}\}\}\{\\log\(1\+\\sigma\_\{n\}^\{\-2\}\)\}\}\\left\[\\sqrt\{3\(\\beta\_\{T\}^\{m^\{\*\}\}\+1\+C\_\{\\kappa\}\)\}\+\\sqrt\{\\beta\_\{T\}^\{m^\{\*\}\}\}\\right\]=O\\\!\\left\(\\sqrt\{T\\beta\_\{T\}^\{m^\{\*\}\}\\gamma\_\{T\}^\{m^\{\*\}\}\}\\right\)\.

Theorem[5\.2](https://arxiv.org/html/2609.19891#S5.Thmtheorem2)is conditional on Assumption[A1](https://arxiv.org/html/2609.19891#Thmngassumption1)holding for the expertm∗m^\{\*\}on the query sequence considered\. For HACK\-MoG, the selected point is not necessarily the exact maximizer of the EI acquisition ofm∗m^\{\*\}\. However, once the weight onm∗m^\{\*\}is large, Lemma[5\.1](https://arxiv.org/html/2609.19891#S5.Thmtheorem1)shows that the MoG EI acquisition is uniformly close to the EI acquisition ofm∗m^\{\*\}, and Proposition[4\.4](https://arxiv.org/html/2609.19891#S4.Thmtheorem4)converts this acquisition\-level closeness into an additive regret slack\. The following theorem formalizes this transfer, showing how concentration of the HACK weights converts the fixed\-expert EI regret guarantee into a regret bound for HACK\-MoG\.

###### Theorem 5\.3\.

Fix a horizonTTand a burn\-in timeT0<TT\_\{0\}<T\. LetIT:=\{T0\+1,…,T\}I\_\{T\}:=\\\{T\_\{0\}\+1,\\dots,T\\\}andnT:=T−T0n\_\{T\}:=T\-T\_\{0\}\. Fix an expertm∗m^\{\*\}using EI satisfying Assumption[A1](https://arxiv.org/html/2609.19891#Thmngassumption1)\. LetxtHx\_\{t\}^\{H\}denote the HACK\-MoG query at roundttand definertH:=f⁡\(x∗\)−f⁡\(xtH\)r\_\{t\}^\{H\}:=f\(x^\{\*\}\)\-f\(x\_\{t\}^\{H\}\)andsTH:=f⁡\(x∗\)−max1≤t≤T⁡f⁡\(xtH\)\.s\_\{T\}^\{H\}:=f\(x^\{\*\}\)\-\\max\_\{1\\leq t\\leq T\}f\(x\_\{t\}^\{H\}\)\.Assume that the eventℰconc:=\{wm∗\(t\)≥1−ϵtfor everyt∈IT\}\\mathcal\{E\}\_\{\\mathrm\{conc\}\}:=\\\{w\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\epsilon\_\{t\}\\text\{ for every \}t\\in I\_\{T\}\\\}holds with probability at least1−δconc1\-\\delta\_\{\\mathrm\{conc\}\}, and that there existsBEI<∞B\_\{\\mathrm\{EI\}\}<\\inftysuch thatEIt,m​\(x\)≤BEI\\mathrm\{EI\}\_\{t,m\}\(x\)\\leq B\_\{\\mathrm\{EI\}\}for allt∈ITt\\in I\_\{T\},m∈\{1,…,M\}m\\in\\\{1,\\dots,M\\\}, andx∈𝒳x\\in\\mathcal\{X\}\. Then, with probability at least1−δNg−δconc1\-\\delta\_\{\\mathrm\{Ng\}\}\-\\delta\_\{\\mathrm\{conc\}\},

∑t=T0\+1TrtH≤ℛT,T0Ng​\(m∗\)\+2​∑t=T0\+1Tϵt​BEIandsTH≤ℛT,T0Ng​\(m∗\)nT\+2nT​∑t=T0\+1Tϵt​BEI,\\sum\_\{t=T\_\{0\}\+1\}^\{T\}r\_\{t\}^\{H\}\\leq\\mathcal\{R\}\_\{T,T\_\{0\}\}^\{\\mathrm\{Ng\}\}\(m^\{\*\}\)\+2\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}B\_\{\\mathrm\{EI\}\}\\quad\\text\{and\}\\quad s\_\{T\}^\{H\}\\leq\\frac\{\\mathcal\{R\}\_\{T,T\_\{0\}\}^\{\\mathrm\{Ng\}\}\(m^\{\*\}\)\}\{n\_\{T\}\}\+\\frac\{2\}\{n\_\{T\}\}\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}B\_\{\\mathrm\{EI\}\},whereℛT,T0Ng​\(m∗\)\\mathcal\{R\}\_\{T,T\_\{0\}\}^\{\\mathrm\{Ng\}\}\(m^\{\*\}\)denotes the Nguyen et al\. cumulative regret term applied to expertm∗m^\{\*\}over the post\-burn\-in horizonnTn\_\{T\}, and is given by

ℛT,T0Ng​\(m∗\):=2​nT​γTm∗log⁡\(1\+σn−2\)​\[3​\(βTm∗\+1\+Cκ\)\+βTm∗\]\.\\mathcal\{R\}\_\{T,T\_\{0\}\}^\{\\mathrm\{Ng\}\}\(m^\{\*\}\):=\\sqrt\{\\frac\{2n\_\{T\}\\gamma\_\{T\}^\{m^\{\*\}\}\}\{\\log\(1\+\\sigma\_\{n\}^\{\-2\}\)\}\}\\left\[\\sqrt\{3\(\\beta\_\{T\}^\{m^\{\*\}\}\+1\+C\_\{\\kappa\}\)\}\+\\sqrt\{\\beta\_\{T\}^\{m^\{\*\}\}\}\\right\]\.

###### Proof\.

We work on the eventℰconc\\mathcal\{E\}\_\{\\mathrm\{conc\}\}and on the GP confidence event from assumption[A1](https://arxiv.org/html/2609.19891#Thmngassumption1); by a union bound, their intersection has probability at least1−δconc−δNg1\-\\delta\_\{\\mathrm\{conc\}\}\-\\delta\_\{\\mathrm\{Ng\}\}\. We analyze only the post\-burn\-in intervalIT=\{T0\+1,…,T\}I\_\{T\}=\\\{T\_\{0\}\+1,\\dots,T\\\}\. This is sufficient for simple regret because

sTH=f⁡\(x∗\)−max1≤t≤T⁡f⁡\(xtH\)≤f⁡\(x∗\)−maxt∈IT⁡f⁡\(xtH\)\.s\_\{T\}^\{H\}=f\(x^\{\*\}\)\-\\max\_\{1\\leq t\\leq T\}f\(x\_\{t\}^\{H\}\)\\leq f\(x^\{\*\}\)\-\\max\_\{t\\in I\_\{T\}\}f\(x\_\{t\}^\{H\}\)\.Thus, ignoring the firstT0T\_\{0\}rounds can only make the upper bound more conservative\. Fixt∈ITt\\in I\_\{T\}\. Sincewm∗\(t\)≥1−ϵtw\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\epsilon\_\{t\}, Lemma[5\.1](https://arxiv.org/html/2609.19891#S5.Thmtheorem1)impliessupx∈𝒳\|EIt,MoG​\(x\)−EIt,m∗​\(x\)\|≤ϵt​BEI\.\\sup\_\{x\\in\\mathcal\{X\}\}\\left\|\\mathrm\{EI\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\\right\|\\leq\\epsilon\_\{t\}B\_\{\\mathrm\{EI\}\}\.SincextH∈arg⁡maxx∈𝒳​EIt,MoG​\(x\)x\_\{t\}^\{H\}\\in\\arg\\max\_\{x\\in\\mathcal\{X\}\}\\mathrm\{EI\}\_\{t,\\mathrm\{MoG\}\}\(x\), Proposition[4\.4](https://arxiv.org/html/2609.19891#S4.Thmtheorem4)givesEIt,m∗​\(xtH\)≥maxx∈𝒳⁡EIt,m∗​\(x\)−2​ϵt​BEI\.\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\_\{t\}^\{H\}\)\\geq\\max\_\{x\\in\\mathcal\{X\}\}\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\)\-2\\epsilon\_\{t\}B\_\{\\mathrm\{EI\}\}\.Therefore, in particular,

EIt,m∗​\(x∗\)≤EIt,m∗​\(xtH\)\+2​ϵt​BEI\.\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x^\{\*\}\)\\leq\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\_\{t\}^\{H\}\)\+2\\epsilon\_\{t\}B\_\{\\mathrm\{EI\}\}\.\(3\)
On the GP confidence event in Assumption[A1](https://arxiv.org/html/2609.19891#Thmngassumption1), Nguyen et al\.\[[28](https://arxiv.org/html/2609.19891#bib.bib28), Lemma 6\]implies

It​\(x∗\)≤EIt,m∗​\(x∗\)\+βtm∗​σt−1,m∗​\(x∗\)\.I\_\{t\}\(x^\{\*\}\)\\leq\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x^\{\*\}\)\+\\sqrt\{\\beta\_\{t\}^\{m^\{\*\}\}\}\\sigma\_\{t\-1,m^\{\*\}\}\(x^\{\*\}\)\.Substituting Equation[3](https://arxiv.org/html/2609.19891#S5.E3)into the previous confidence bound yields

It​\(x∗\)≤EIt,m∗​\(xtH\)\+βtm∗​σt−1,m∗​\(x∗\)\+2​ϵt​BEI\.I\_\{t\}\(x^\{\*\}\)\\leq\\mathrm\{EI\}\_\{t,m^\{\*\}\}\(x\_\{t\}^\{H\}\)\+\\sqrt\{\\beta\_\{t\}^\{m^\{\*\}\}\}\\sigma\_\{t\-1,m^\{\*\}\}\(x^\{\*\}\)\+2\\epsilon\_\{t\}B\_\{\\mathrm\{EI\}\}\.Applying the remainder of the EI regret argument of Nguyen et al\.\[[28](https://arxiv.org/html/2609.19891#bib.bib28), Theorem 4\]on the post\-burn\-in roundsITI\_\{T\}, using the stopping condition in Assumption[A1](https://arxiv.org/html/2609.19891#Thmngassumption1), yields

∑t=T0\+1TrtH≤ℛT,T0Ng​\(m∗\)\+2​BEI​∑t=T0\+1Tϵt\.\\sum\_\{t=T\_\{0\}\+1\}^\{T\}r\_\{t\}^\{H\}\\leq\\mathcal\{R\}\_\{T,T\_\{0\}\}^\{\\mathrm\{Ng\}\}\(m^\{\*\}\)\+2B\_\{\\mathrm\{EI\}\}\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}\.Finally,

sTH≤f⁡\(x∗\)−maxt∈IT⁡f⁡\(xtH\)=mint∈IT⁡rtH≤1nT​∑t=T0\+1TrtH\.s\_\{T\}^\{H\}\\leq f\(x^\{\*\}\)\-\\max\_\{t\\in I\_\{T\}\}f\(x\_\{t\}^\{H\}\)=\\min\_\{t\\in I\_\{T\}\}r\_\{t\}^\{H\}\\leq\\frac\{1\}\{n\_\{T\}\}\\sum\_\{t=T\_\{0\}\+1\}^\{T\}r\_\{t\}^\{H\}\.Substituting the cumulative\-regret bound gives

sTH≤ℛT,T0Ng​\(m∗\)nT\+2​BEInT​∑t=T0\+1Tϵt\.∎s\_\{T\}^\{H\}\\leq\\frac\{\\mathcal\{R\}\_\{T,T\_\{0\}\}^\{\\mathrm\{Ng\}\}\(m^\{\*\}\)\}\{n\_\{T\}\}\+\\frac\{2B\_\{\\mathrm\{EI\}\}\}\{n\_\{T\}\}\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}\.\\qed

Theorem[5\.3](https://arxiv.org/html/2609.19891#S5.Thmtheorem3)cleanly transfers the regret statement of Nguyen et al\.\[[28](https://arxiv.org/html/2609.19891#bib.bib28)\]with the inclusion of an additional error term\. The second term is the cost of not usingm∗m^\{\*\}directly quantified using Lemma[5\.1](https://arxiv.org/html/2609.19891#S5.Thmtheorem1)and Proposition[4\.4](https://arxiv.org/html/2609.19891#S4.Thmtheorem4)\. Thus, the adaptive mixture inherits the fixed\-expert EI guarantee whenever the cumulative residual mass∑t\>T0ϵt\\sum\_\{t\>T\_\{0\}\}\\epsilon\_\{t\}is small\. We now evaluate the order of this residual term under the AdaHedge dynamics and the loss gap assumptions from Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)\. It shows that, once the burn\-in is large enough for the gap to be detected with high probability, the post\-burn\-in excess simple\-regret term decays asO⁡\(1/nT\)O\(1/n\_\{T\}\)\.

###### Corollary 5\.4\.

Assume the conditional loss\-gap condition of Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)holds form∗m^\{\*\}with gapΔ\>0\\Delta\>0\. Fix a horizonTT, letδ0=δconc/nT\\delta\_\{0\}=\\delta\_\{\\mathrm\{conc\}\}/n\_\{T\}, and define

ϵt=M−1M−1\+exp⁡\(Δ2​\(t−1\)​ln⁡M\),\\epsilon\_\{t\}=\\frac\{M\-1\}\{M\-1\+\\exp\\\!\\left\(\\frac\{\\Delta\}\{2\}\\sqrt\{\(t\-1\)\\ln M\}\\right\)\},fort∈ITt\\in I\_\{T\}and letT0T\_\{0\}satisfy

T0≥max⁡\{4​aM2ln⁡M,32Δ2​ln⁡\(M−1δ0\)\}\.T\_\{0\}\\geq\\max\\left\\\{\\frac\{4a\_\{M\}^\{2\}\}\{\\ln M\},\\;\\frac\{32\}\{\\Delta^\{2\}\}\\ln\\\!\\left\(\\frac\{M\-1\}\{\\delta\_\{0\}\}\\right\)\\right\\\}\.Then, for this fixed horizon, withc=Δ2​ln⁡Mc=\\tfrac\{\\Delta\}\{2\}\\sqrt\{\\ln M\}, the summation ofϵt\\epsilon\_\{t\}post\-burn\-in is bounded by

∑t=T0\+1Tϵt≤\(M−1\)​\[1\+2c2​\(1\+c​T0\)\]​e−c​T0\.\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}\\;\\leq\\;\(M\-1\)\\\!\\left\[1\+\\frac\{2\}\{c^\{2\}\}\\\!\\left\(1\+c\\sqrt\{T\_\{0\}\}\\right\)\\right\]e^\{\-c\\sqrt\{T\_\{0\}\}\}\.Consequently, in Theorem[5\.3](https://arxiv.org/html/2609.19891#S5.Thmtheorem3)the additional simple\-regret term satisfies

2​BEInT​∑t=T0\+1Tϵt=O⁡\(1nT\)\.\\frac\{2B\_\{\\mathrm\{EI\}\}\}\{n\_\{T\}\}\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}=O\\\!\\left\(\\frac\{1\}\{n\_\{T\}\}\\right\)\.

Corollary[5\.4](https://arxiv.org/html/2609.19891#S5.Thmtheorem4)shows that, under a persistent loss gap, the HACK\-specific error term in Theorem[5\.3](https://arxiv.org/html/2609.19891#S5.Thmtheorem3)contributes onlyO⁡\(1/nT\)O\(1/n\_\{T\}\)to the post\-burn\-in simple regret\. Therefore,

sTH≤ℛT,T0Ng​\(m∗\)nT\+O⁡\(1nT\)\.s\_\{T\}^\{H\}\\leq\\frac\{\\mathcal\{R\}\_\{T,T\_\{0\}\}^\{\\mathrm\{Ng\}\}\(m^\{\*\}\)\}\{n\_\{T\}\}\+O\\\!\\left\(\\frac\{1\}\{n\_\{T\}\}\\right\)\.Thus, once the weights concentrate on a clearly favored expert, the dominant term is the EI regret term inherited from Nguyen et al\.\[[28](https://arxiv.org/html/2609.19891#bib.bib28)\], averaged over the post\-burn\-in horizon\. The size of this inherited term is governed by the maximum information gainγTm∗\\gamma\_\{T\}^\{m^\{\*\}\}\. For the squared exponential kernel indddimensions, Nguyen et al\.\[[28](https://arxiv.org/html/2609.19891#bib.bib28)\]useγT=O⁡\(\(log⁡T\)d\+1\)\\gamma\_\{T\}=O\(\(\\log T\)^\{d\+1\}\)and obtain the cumulative regret orderRT=O⁡\(T​\(log⁡T\)d\+4\)\.R\_\{T\}=O\\\!\\left\(\\sqrt\{T\(\\log T\)^\{d\+4\}\}\\right\)\.Consequently, when them∗m^\{\*\}kernel is SE, the corresponding post\-burn\-in contribution in Theorem[5\.3](https://arxiv.org/html/2609.19891#S5.Thmtheorem3)is

ℛT,T0Ng​\(m∗\)nT=O⁡\(\(log⁡nT\)d\+4nT\),\\frac\{\\mathcal\{R\}\_\{T,T\_\{0\}\}^\{\\mathrm\{Ng\}\}\(m^\{\*\}\)\}\{n\_\{T\}\}=O\\\!\\left\(\\sqrt\{\\frac\{\(\\log n\_\{T\}\)^\{d\+4\}\}\{n\_\{T\}\}\}\\right\),replacingTTby the post\-burn\-in horizonnTn\_\{T\}\.

Overall, the BO guarantee is most informative in the separated\-expert regime: one kernel has a persistent loss advantage, AdaHedge concentrates on it, and the remaining HACK\-specific term vanishes asO⁡\(1/nT\)O\(1/n\_\{T\}\)\.

### 5\.3Experiments

We evaluate on \(i\) synthetic functions from the Virtual Library of Simulation Experiments\[[29](https://arxiv.org/html/2609.19891#bib.bib29)\]and \(ii\) the 3D RobotPushing simulator benchmark\[[30](https://arxiv.org/html/2609.19891#bib.bib30)\]\. Log simple regret,ln⁡\(f⁡\(x∗\)−maxt≤T⁡yt\)\\ln\\\!\\big\(f\(x^\{\*\}\)\-\\max\_\{t\\leq T\}y\_\{t\}\\big\), is used as the performance metric, capturing how close the current observations are to the function’s global maxima\. Across all tasks, we run BO forT=100T=100iterations with EI, initializing with 5 random points, and report final log simple regret averaged over 20 seeds\. All ensemble/compositional methods use the same kernel set

𝒦=\{SE,Matern\-​5/2,Matern\-​3/2,RQ,LIN,PER\}\\mathcal\{K\}=\\\{\\textsc\{SE\},\\textsc\{Matern\-\}5/2,\\textsc\{Matern\-\}3/2,\\textsc\{RQ\},\\textsc\{LIN\},\\textsc\{PER\}\\\}and we compare against common choices for fixed\-kernel GP\-BO \(SE, Matérn\-5/25/2\), adaptive kernel\-selection heuristics\[[6](https://arxiv.org/html/2609.19891#bib.bib6)\], EGP\[[10](https://arxiv.org/html/2609.19891#bib.bib10)\], and CAKE\[[9](https://arxiv.org/html/2609.19891#bib.bib9)\]\.HACK\-MoGperforms best overall, achieving the lowest average rank and most wins on the synthetic suite and the best performance on RobotPushing \(details in[B\.1\.2](https://arxiv.org/html/2609.19891#A2.SS1.SSS2)\); see Table[2](https://arxiv.org/html/2609.19891#S5.T2)and Figure[2](https://arxiv.org/html/2609.19891#S5.F2)\. Note that the wider confidence intervals in the higher\-dimensional BO problems are expected, since the larger search spaces permit greater variation in the optimization trajectories across runs\. We reiterate that the intended goal of HACK is not to provide a guaranteed improvement in performance but rather to prevent the undesirable case of using a misspecified kernel for BO, or any other sequential decision\-making task\.

Figure 2:Log regret for the two synthetic \(Branin\-2D and Hartmann\-6D\) and the robot pushing task described in Section[5\.3](https://arxiv.org/html/2609.19891#S5.SS3)\. The lines and shaded regions represent the mean log regret and corresponding 95% confidence interval for each method across 20 seeds\.HACK\-MoGis competitive across the three displayed tasks and achieves the best overall average rank in Table[2](https://arxiv.org/html/2609.19891#S5.T2)\.#### Unknown smoothness and adaptive weighting

We next isolate a common source of kernel misspecification: uncertainty about the smoothness of the objective\. For this diagnostic, we run BO on Bukin\-2D using the smoothness\-ordered dictionary

𝒦smooth=\{Matern\-​1/2,Matern\-​3/2,Matern\-​5/2,SE\}\.\\mathcal\{K\}\_\{\\mathrm\{smooth\}\}=\\\{\\textsc\{Matern\-\}1/2,\\textsc\{Matern\-\}3/2,\\textsc\{Matern\-\}5/2,\\textsc\{SE\}\\\}\.This removes other kernel families from the comparison and focuses on whether HACK can adapt among rough and smooth priors during the BO run\.

Figure[3](https://arxiv.org/html/2609.19891#S5.F3)shows that Matérn\-1/21/2is the strongest fixed kernel among this dictionary on Bukin\-2D, a function that has sharp peaks\. Starting from uniform weights,HACK\-MoGrapidly places most of its mass on Matérn\-1/21/2, and its regret curve follows the same trend as the best fixed kernel after the early iterations\. This example illustrates an intended use case of HACK: when the candidate kernels encode different plausible smoothness assumptions, the online loss can shift the acquisition toward the kernel that is more useful for the observed BO trajectory\.

Figure 3:Unknown\-smoothness diagnostic on Bukin\-2D\. Left: log simple regret for fixed smoothness\-ordered kernels andHACK\-MoG\. The lines and shaded regions represent the mean log regret and corresponding 95% confidence interval for each kernel/method across 20 seeds\. Right: HACK kernel weights over BO iterations\. The lines and shaded regions represent the mean AdaHedge weight and corresponding 95% confidence interval for each kernel across 20 seeds\. In this diagnostic, Matérn\-1/21/2performs best among the fixed kernels, and HACK rapidly shifts most of its mass to that kernel\.
#### Similarly Performing Kernels

When the candidate kernels induce similar BO behavior, aggressive concentration on a single expert is neither expected nor necessarily desirable\. We illustrate this regime on the Beale\-2D benchmark using a restricted kernel dictionary containing only the squared exponential and Matérn\-5/2 kernels\. In contrast to the unknown\-smoothness diagnostic in Figure[3](https://arxiv.org/html/2609.19891#S5.F3), these two kernels achieve comparable simple\-regret trajectories on this task\. HACK\-MoG correspondingly does not exhibit a sharp collapse of the weight distribution onto one kernel\. Instead, the AdaHedge weights remain distributed across the two experts, reflecting the absence of a persistent loss gap large enough to justify decisive kernel selection\.

This behavior is important for interpreting HACK as an adaptive kernel\-mixing method rather than a hard model\-selection procedure\. When one kernel is clearly better, as in the Bukin smoothness experiment, the weights rapidly concentrate on that kernel\. When the experts are nearly tied, as in Figure[4](https://arxiv.org/html/2609.19891#S5.F4), HACK preserves a mixture and obtains performance comparable to the fixed kernels\. This is consistent with the theory in Section 5\.2: the concentration and regret\-transfer guarantees are strongest under a separated loss\-gap condition, while near\-tied experts naturally lead to slower concentration and a smaller practical distinction between selecting and mixing kernels\.

Figure 4:Similarly performing kernels on Beale\-2D\. Left: log simple regret for HACK\-MoG compared with fixed SE and Matérn\-5/2 kernels over 100 BO iterations\. The lines and shaded regions represent the mean log regret and corresponding 95% confidence interval for each method across 20 seeds\. The two fixed kernels perform similarly, and HACK\-MoG tracks their regret behavior without a large penalty\. Right: HACK\-MoG kernel weights over time\. The lines and shaded regions represent the mean AdaHedge weight and corresponding 95% confidence interval for each kernel across 20 seeds\. Unlike the sharp concentration observed in the Bukin smoothness diagnostic, the weights remain shared between SE and Matérn\-5/2, indicating that AdaHedge does not force premature selection when the experts have comparable task performance\.Table 2:Final log simple regret afterT=100T=100BO iterations \(Lower is better\) with EI averaged over 20 seeds\. Mean values are shown with standard deviation in parentheses\. Best performing method is inbold, second best isunderlined\.

## 6Level Set Estimation

We next specialize the expert\-advice framework to Level Set Estimation \(LSE\)\. In this setting, the objective is to identify the superlevel set of the unknown function relative to a fixed threshold, which naturally induces binary outcomes at queried points\. We define task\-specific losses that reward accurate threshold classification and analyze how expert weight concentration affects the resulting LSE acquisition function\.

### 6\.1Loss and Acquisition function

For the expert loss, LSE naturally induces a binary label at the queried point:zt:=𝟏\{yt≥h\}z\_\{t\}:=\\mathbf\{1\}\\\{y\_\{t\}\\geq h\\\}\. Define the predicted above\-threshold probability

πt,mlse​\(xt\):=ℙ⁡\(Yt,m≥h∣xt\)=Φ⁡\(\(μt,m​\(xt\)−h\)/σt,m​\(xt\)\)\.\\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\_\{t\}\):=\\mathbb\{P\}\(Y\_\{t,m\}\\geq h\\mid x\_\{t\}\)=\\Phi\\\!\\big\(\(\\mu\_\{t,m\}\(x\_\{t\}\)\-h\)/\\sigma\_\{t,m\}\(x\_\{t\}\)\\big\)\.We then use the Brier scoreℓm,brier\(t\)=\(zt−πt,mlse​\(xt\)\)2,\\ell^\{\(t\)\}\_\{m,\\textsc\{brier\}\}=\\Big\(z\_\{t\}\-\\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\_\{t\}\)\\Big\)^\{2\},a proper scoring rule for probabilistic binary predictions, naturally bounded in\[0,1\]\[0,1\]\. As in BO, we combine the task\-specific loss with NLL \(Equation[2](https://arxiv.org/html/2609.19891#S3.E2)\) to balance threshold classification accuracy with overall predictive calibration:ℓm\(t\)=α​ℓm,brier\(t\)\+\(1−α\)​ℓm,nll\(t\)\.\\ell^\{\(t\)\}\_\{m\}=\\alpha\\,\\ell^\{\(t\)\}\_\{m,\\textsc\{brier\}\}\+\(1\-\\alpha\)\\,\\ell^\{\(t\)\}\_\{m,\\textsc\{nll\}\}\.We use EI\-LSE\[[17](https://arxiv.org/html/2609.19891#bib.bib17)\]as the primary acquisition function for LSE\. For the MoG predictive distribution, EI\-LSE retains the same linearity\-of\-expectation advantage as EI:EI​\-​LSEt,MoG​\(x\)=∑m=1Mwm\(t\)​EI​\-​LSEt,m​\(x\)\+β​σ¯t2​\(x\),\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,\\textsc\{MoG\}\}\(x\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\\;\+\\;\\beta\\,\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\),whereσ¯t2​\(x\)\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\)is the MoG predictive variance andβ≥0\\beta\\geq 0promotes exploration\. The variance\-based term is included to encourage exploration near the decision boundary\.

### 6\.2Theoretical Analysis

The following result specializes the generic acquisition stability argument to EI\-LSE, accounting for the additional variance\-based exploration term\. Proofs can be found in[A\.3](https://arxiv.org/html/2609.19891#A1.SS3)\.

###### Assumption A2\.

Assumeκ2:=max⁡supx∈𝒳m⁡km​\(x,x\)<∞\\kappa^\{2\}:=\\max\_\{m\}\\sup\_\{x\\in\\mathcal\{X\}\}k\_\{m\}\(x,x\)<\\infty\.

This implies thatσt,m2​\(x\)≤km​\(x,x\)≤κ2\\sigma^\{2\}\_\{t,m\}\(x\)\\leq k\_\{m\}\(x,x\)\\leq\\kappa^\{2\}for allt∈\{1,…,T\}t\\in\\\{1,\\dots,T\\\},m∈\{1,…,M\}m\\in\\\{1,\\dots,M\\\}, andx∈𝒳x\\in\\mathcal\{X\}\.

###### Lemma 6\.1\.

Under Assumption[A2](https://arxiv.org/html/2609.19891#Thmngassumption2), supposeEI​\-​LSEt,m​\(x\)≤BLSE\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\\leq B\_\{\\mathrm\{LSE\}\}for allm∈\{1,…,M\}m\\in\\\{1,\\dots,M\\\}andx∈𝒳x\\in\\mathcal\{X\}\. Ifwm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\varepsilon, then

supx\|EI​\-​LSEt,MoG​\(x\)−EI​\-​LSEt,m∗​\(x\)\|≤ε​BLSE\+β⁡\(ε​κ2\+supxαt,disag​\(x\)\)\.\\sup\_\{x\}\\big\|\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\varepsilon B\_\{\\mathrm\{LSE\}\}\+\\beta\\Big\(\\varepsilon\\kappa^\{2\}\+\\sup\_\{x\}\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\Big\)\.

The bound consists of two terms\. The first reflects expert weight concentration, as in the BO setting\. The second one arises from the additional variance\-based exploration component in EI\-LSE and captures residual disagreement between experts\. As weights concentrate and predictive means align, this term becomes small\. Beyond acquisition\-level stability, weight concentration also has a direct structural implication for the inferred level set\. Intuitively, once the mixture\-of\-Gaussians behaves similarly to the best expert, the superlevel sets they induce can differ only near the decision boundary, where posterior uncertainty is inherently high\. The following corollary makes this intuition precise by localizing the discrepancy between the MoG and best\-expert level sets to a narrow boundary region\.

###### Corollary 6\.2\.

Forτ∈\(0,1\)\\tau\\in\(0,1\), define the setSt,m​\(τ\):=\{x:πt,mlse​\(x\)≥τ\}S\_\{t,m\}\(\\tau\):=\\\{x:\\ \\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\)\\geq\\tau\\\}and defineSt,MoG​\(τ\)S\_\{t,\\mathrm\{MoG\}\}\(\\tau\)similarly\. Ifwm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\varepsilon, then the symmetric difference of the two sets satisfiesSt,MoG​\(τ\)​△​St,m∗​\(τ\)⊆\{x∈𝒳:\|πt,m∗lse​\(x\)−τ\|≤ε\}\.S\_\{t,\\mathrm\{MoG\}\}\(\\tau\)\\triangle S\_\{t,m^\{\*\}\}\(\\tau\)\\subseteq\\left\\\{x\\in\\mathcal\{X\}:\\left\|\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\-\\tau\\right\|\\leq\\varepsilon\\right\\\}\.

### 6\.3Experiments

Our evaluations consist of two synthetic test functions, Himmelblau and GaussianModulatedSinusoid \(GMS\) \(Details in[B](https://arxiv.org/html/2609.19891#A2)\), and the motorcycle dataset from\[[31](https://arxiv.org/html/2609.19891#bib.bib31)\]\. The synthetic functions are evaluated on a50×5050\\times 50grid uniformly and motorcycle is evaluated on 133 uniform points from their bounds\. We use the mean of the posterior model to classify all the points in the grid as above/below the threshold\. For HACK,μ¯t\\bar\{\\mu\}\_\{t\}is used as the mean\. EI\-LSE is run forT=50T=50iterations and results are averaged over 30 seeds\. Because LSE can be framed as predicting whether a function value exceeds a given threshold, the F1\-score serves as a natural evaluation metric\. We compare against 4 baselines: \(i\) EI\-LSE with SE and Matérn\-5/2, \(ii\) RMILE\[[18](https://arxiv.org/html/2609.19891#bib.bib18)\]with SE and Matérn\-5/2, \(iii\) Equally weighted MoG, \(iv\) Random Uniform selection\. All ensemble methods use the same set of kernels𝒦=\{SE,Matern\-​5/2,Matern\-​3/2,RQ,LIN,PER\}\\mathcal\{K\}=\\\{\\textsc\{SE\},\\textsc\{Matern\-\}5/2,\\textsc\{Matern\-\}3/2,\\textsc\{RQ\},\\textsc\{LIN\},\\textsc\{PER\}\\\}\.

Uniform Random and Equal Weights exhibit significantly lower performance in the Himmelblau task, even compared to standard single kernels likeSEandMatern\-5/2\. While most methods reach comparable F1 scores by iteration 50, HACK and RMILE effectively address model misspecification, particularly within the SE kernel on the GMS function\. On the Motorcycle dataset, RMILE performs slightly worse than HACK, where SE kernel misspecification is again observed\. Overall, we note that HACK is able to match the performance of standard kernels while remaining robust to kernel misspecification\. RMILE provides a strong baseline as a non\-kernel\-based robust LSE method, yet HACK performs comparably or better across tasks\. We note that the per\-iteration runtime of RMILE isO⁡\(\|𝒳\|2\)O\(\|\\mathcal\{X\}\|^\{2\}\)\[[18](https://arxiv.org/html/2609.19891#bib.bib18)\], compared toO⁡\(\|𝒳\|\)O\(\|\\mathcal\{X\}\|\)for standard acquisition functions such as EI\-LSE used by HACK\.

Figure 5:F1\-scores for the 2 synthetic \(Himmelblau and GMS\) and 1 real\-world data task \(Motorcycle\) described in[6\.3](https://arxiv.org/html/2609.19891#S6.SS3)\. The lines and shaded regions represent the mean F1 score and corresponding 95% confidence interval for each method across 30 seeds\. We see that HACK achieves similar to better performance compared to SE and Matern 5/2\. We note the apparent misspecification of SE in the GMS and to a lesser extent in Motorcycle\. Equal Weights and Uniform Random show the necessity of AdaHedge in rebalancing the weights of the kernels effectively\.

## 7Bayesian Active Learning

We finally specialize the framework to Bayesian Active Learning \(BAL\), where the goal is to sequentially select informative observations so as to improve the predictive model of the unknown function\. In contrast to BO, which focuses on locating an optimum, or LSE, which focuses on identifying a thresholded region, BAL aims to reduce predictive uncertainty over the input space\. Unlike BO and LSE, it does not naturally provide a binary task\-progress event analogous to improvement or threshold crossing\. The acquisition itself is uncertainty reduction, so we use predictive variance directly and score experts primarily through predictive calibration\. In this setting, the MoG variance decomposition is especially interpretable because the acquisition separates within\-expert uncertainty from between\-kernel disagreement\.

### 7\.1Loss and Acquisition Function

In BAL for regression, a common acquisition strategy is to query points with high posterior uncertainty\. Accordingly, we use predictive variance as the acquisition function in our experiments\. For the MoG predictive distribution, this acquisition reduces exactly to the mixture varianceσ¯t2​\(x\)\\bar\{\\sigma\}^\{2\}\_\{t\}\(x\), which decomposes into within\-expert variance and between\-expert disagreement as in Lemma[4\.1](https://arxiv.org/html/2609.19891#S4.Thmtheorem1)\. For expert weighting, we use the normalized NLL loss \(Equation[2](https://arxiv.org/html/2609.19891#S3.E2)\)\. Unlike BO and LSE, BAL does not naturally provide a binary task\-specific event for defining a Brier\-style loss\.

### 7\.2Theoretical Analysis

We now show that expert weight concentration implies uniform closeness of the BAL acquisition function under the MoG predictive distribution\. Proofs can be found in[A\.4](https://arxiv.org/html/2609.19891#A1.SS4)\.

###### Lemma 7\.1\.

Assume Assumption[A2](https://arxiv.org/html/2609.19891#Thmngassumption2)\. Ifwm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\{\(t\)\}\}\\geq 1\-\\varepsilon, then

supx∈𝒳\|σt,MoG2​\(x\)−σt,m∗2​\(x\)\|≤ε​κ2\+supx∈𝒳αt,disag​\(x\)\.\\sup\_\{x\\in\\mathcal\{X\}\}\\big\|\\sigma^\{2\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\varepsilon\\kappa^\{2\}\+\\sup\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\.

Lemma[7\.1](https://arxiv.org/html/2609.19891#S7.Thmtheorem1)shows that once the expert weights concentrate, the predictive variance under the MoG closely tracks that of the best expert, up to residual disagreement across experts\. In particular, when expert predictions align, BAL queries selected using the MoG acquisition behave similarly to those selected using the best kernel\. In Bayesian Active Learning, the variance\-based acquisition admits a particularly transparent decomposition under the MoG predictive distribution\. Expert weight concentration suppresses disagreement\-driven uncertainty, causing the MoG acquisition to approximate that of the best expert while retaining robustness to kernel misspecification in earlier rounds\.

Figure 6:RMSE and NLPD for the 3 BAL synthetic test functions\. The lines and shaded regions represent the mean RMSE \(Top\) and NLPD \(Bottom\) score and corresponding 95% confidence interval for each method across 30 seeds\.
### 7\.3Experiments

We evaluate on three synthetic functions \(Branin\-2D, Gramacy\-2D, and Hartmann\-6D\) with the same settings as\[[22](https://arxiv.org/html/2609.19891#bib.bib22)\]\. Predictive performance is evaluated using Root Mean Squared Error \(RMSE\) and Negative Log Predictive Density \(NLPD\)\. RMSE measures the accuracy of the posterior predictive mean, while NLPD evaluates the probability assigned by the predictive distribution to the observed values and therefore also reflects the quality of its uncertainty estimates\. Lower values are better for both metrics\. Reporting both is useful in BAL because accurate mean predictions alone do not guarantee well\-calibrated uncertainty, which directly influences where the model chooses to query next\.

We run BAL forT=100T=100iterations and results are averaged over 30 seeds\. All ensemble methods use the same set of kernels𝒦=\{SE,Matern\-​5/2,Matern\-​3/2,RQ,LIN,PER\}\\mathcal\{K\}=\\\{\\textsc\{SE\},\\textsc\{Matern\-\}5/2,\\textsc\{Matern\-\}3/2,\\textsc\{RQ\},\\textsc\{LIN\},\\textsc\{PER\}\\\}\. We compare against: \(i\) fixed kernels SE and Matérn\-5/25/2; \(ii\) Uniform Random; \(iii\) Equally weighted MoG; and \(iv\) EGP with Variance of GP Mixtures from\[[23](https://arxiv.org/html/2609.19891#bib.bib23)\]\. HACK performs better than EGP on Gramacy\-2D and Hartmann\-6D, while remaining competitive on Branin\-2D\. Overall, the results support the robustness of adaptive kernel weighting across problems with varying best kernels, rather than a consistent large improvement on every benchmark\.

## 8Conclusion

We provide a framework, HACK, an online mechanism for adapting over a finite set of GP kernels during sequential decision\-making\. Rather than committing to a single kernel before data collection, it uses task\-aware losses to reweight candidate GP experts as iterations pass\. The method is most beneficial when kernel misspecification would otherwise cause poor BO, LSE, or BAL decisions, and it reduces to conservative model averaging when several kernels are similarly useful\. Its guarantees and empirical behavior are therefore best understood through the size of the loss gap between candidate kernels: large gaps lead to concentration and best\-expert\-like behavior, while small gaps lead to shared weights without necessarily harming task performance\.

## Acknowledgments

This work was supported by the ANRF MATRICS project grant number MTR/2023/000042 and the AlphaGrep Quantitative Research lab at IIIT\-H\. Most of this work was done while GD was on \(sabbatical\) leave from ASU, visiting IIIT\-H\.

## References

- \[1\]C\. E\. Rasmussen, C\. K\. I\. Williams, Gaussian Processes for Machine Learning, MIT Press, Cambridge, MA, USA, 2006\.
- \[2\]J\. Snoek, H\. Larochelle, R\. P\. Adams, Practical bayesian optimization of machine learning algorithms, in: F\. Pereira, C\. Burges, L\. Bottou, K\. Weinberger \(Eds\.\), Advances in Neural Information Processing Systems, Vol\. 25, Curran Associates, Inc\., 2012\.
- \[3\]J\. Gardner, C\. Guo, K\. Weinberger, R\. Garnett, R\. Grosse, Discovering and Exploiting Additive Structure for Bayesian Optimization, in: A\. Singh, J\. Zhu \(Eds\.\), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Vol\. 54 of Proceedings of Machine Learning Research, PMLR, 2017, pp\. 1311–1319\.
- \[4\]S\. De Rooij, T\. Van Erven, P\. D\. Grünwald, W\. M\. Koolen, Follow the leader if you can, hedge if you must, J\. Mach\. Learn\. Res\. 15 \(1\) \(2014\) 1281–1316\.
- \[5\]Y\. Freund, R\. E\. Schapire, A decision\-theoretic generalization of on\-line learning and an application to boosting, Journal of Computer and System Sciences 55 \(1\) \(1997\) 119–139\.[doi:10\.1006/jcss\.1997\.1504](https://doi.org/10.1006/jcss.1997.1504)\.
- \[6\]I\. Roman, R\. Santana, A\. Mendiburu, J\. Lozano, An experimental study in adaptive kernel selection for bayesian optimization, IEEE Access PP \(2019\) 1–1\.[doi:10\.1109/ACCESS\.2019\.2960498](https://doi.org/10.1109/ACCESS.2019.2960498)\.
- \[7\]D\. Duvenaud, J\. Lloyd, R\. Grosse, J\. Tenenbaum, G\. Zoubin, Structure discovery in nonparametric regression through compositional kernel search, in: S\. Dasgupta, D\. McAllester \(Eds\.\), Proceedings of the 30th International Conference on Machine Learning, Vol\. 28 of Proceedings of Machine Learning Research, PMLR, Atlanta, Georgia, USA, 2013, pp\. 1166–1174\.
- \[8\]A\. Wilson, R\. Adams, Gaussian process kernels for pattern discovery and extrapolation, in: S\. Dasgupta, D\. McAllester \(Eds\.\), Proceedings of the 30th International Conference on Machine Learning, Vol\. 28 of Proceedings of Machine Learning Research, PMLR, Atlanta, Georgia, USA, 2013, pp\. 1067–1075\.
- \[9\]R\. C\. Suwandi, F\. Yin, J\. Wang, R\. Li, T\.\-H\. Chang, S\. Theodoridis, Adaptive kernel design for bayesian optimization is a piece of cake with llms, in: The Thirty\-ninth Annual Conference on Neural Information Processing Systems, 2025\.
- \[10\]Q\. Lu, K\. D\. Polyzos, B\. Li, G\. B\. Giannakis, Surrogate modeling for bayesian optimization beyond a single gaussian process, IEEE Transactions on Pattern Analysis and Machine Intelligence 45 \(9\) \(2023\) 11283–11296\.[doi:10\.1109/TPAMI\.2023\.3264741](https://doi.org/10.1109/TPAMI.2023.3264741)\.
- \[11\]A\. Ravishankar, F\. Llorente, Y\. Song, P\. Djuric, Ensemble mashups: A simple recipe for better bayesian optimization, in: NeurIPS 2024 Workshop on Bayesian Decision\-making and Uncertainty, 2024\.
- \[12\]J\. Sandberg, M\. H\. Chehreghani, Adaptive prior selection in gaussian process bandits with thompson sampling \(2026\)\.
- \[13\]J\. Ziomek, M\. Adachi, M\. A\. Osborne, Time\-varying gaussian process bandits with unknown prior, in: Y\. Li, S\. Mandt, S\. Agrawal, E\. Khan \(Eds\.\), Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, Vol\. 258 of Proceedings of Machine Learning Research, PMLR, 2025, pp\. 4294–4302\.
- \[14\]B\. Bryan, R\. C\. Nichol, C\. R\. Genovese, J\. Schneider, C\. J\. Miller, L\. Wasserman, Active learning for identifying function threshold boundaries, Advances in neural information processing systems 18 \(2005\)\.
- \[15\]A\. Gotovos, Active learning for level set estimation, Master’s thesis, Eidgenössische Technische Hochschule Zürich, Department of Computer Science, \(2013\)\.
- \[16\]N\. Srinivas, A\. Krause, S\. M\. Kakade, M\. W\. Seeger, Information\-theoretic regret bounds for gaussian process optimization in the bandit setting, IEEE Transactions on Information Theory 58 \(5\) \(2012\) 3250–3265\.[doi:10\.1109/tit\.2011\.2182033](https://doi.org/10.1109/tit.2011.2182033)\.
- \[17\]A\. Ravishankar, F\. Llorente, P\. M\. Djurić, Improvement\-based acquisition functions for level set estimation, in: 2025 33rd European Signal Processing Conference \(EUSIPCO\), 2025, pp\. 1852–1856\.[doi:10\.23919/EUSIPCO63237\.2025\.11226629](https://doi.org/10.23919/EUSIPCO63237.2025.11226629)\.
- \[18\]A\. Zanette, J\. Zhang, M\. J\. Kochenderfer, Robust super\-level set estimation using gaussian processes, in: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, 2018, pp\. 276–291\.
- \[19\]D\. J\. MacKay, Information\-based objective functions for active data selection, Neural computation 4 \(4\) \(1992\) 590–604\.
- \[20\]B\. Settles, Active learning literature survey \(2009\)\.
- \[21\]N\. Houlsby, F\. Huszár, Z\. Ghahramani, M\. Lengyel, Bayesian active learning for classification and preference learning, arXiv preprint arXiv:1112\.5745 \(2011\)\.
- \[22\]C\. Riis, F\. Antunes, F\. Hüttel, C\. Lima Azevedo, F\. Pereira, Bayesian active learning with fully bayesian gaussian processes, Advances in Neural Information Processing Systems 35 \(2022\) 12141–12153\.
- \[23\]K\. D\. Polyzos, Q\. Lu, G\. B\. Giannakis, Weighted ensembles for adaptive active learning, IEEE Transactions on Signal Processing 72 \(2024\) 4178–4190\.[doi:10\.1109/TSP\.2024\.3450270](https://doi.org/10.1109/TSP.2024.3450270)\.
- \[24\]D\. Jones, M\. Schonlau, W\. Welch, Efficient global optimization of expensive black\-box functions, Journal of Global Optimization 13 \(1998\) 455–492\.[doi:10\.1023/A:1008306431147](https://doi.org/10.1023/A:1008306431147)\.
- \[25\]P\. Frazier, W\. Powell, S\. Dayanik, The knowledge\-gradient policy for correlated normal beliefs, INFORMS journal on Computing 21 \(4\) \(2009\) 599–613\.
- \[26\]I\. Bogunovic, J\. Scarlett, A\. Krause, V\. Cevher, Truncated variance reduction: A unified approach to bayesian optimization and level\-set estimation, in: D\. Lee, M\. Sugiyama, U\. Luxburg, I\. Guyon, R\. Garnett \(Eds\.\), Advances in Neural Information Processing Systems, Vol\. 29, Curran Associates, Inc\., 2016\.
- \[27\]G\. W\. Brier, Verification of forecasts expressed in terms of probability, Monthly Weather Review 78 \(1\) \(1950\) 1 – 3\.[doi:10\.1175/1520\-0493\(1950\)078<0001:VOFEIT\>2\.0\.CO;2](https://doi.org/10.1175/1520-0493(1950)078%3C0001:VOFEIT%3E2.0.CO;2)\.
- \[28\]V\. Nguyen, S\. Gupta, S\. Rana, C\. Li, S\. Venkatesh, Regret for expected improvement over the best\-observed value and stopping condition, in: M\.\-L\. Zhang, Y\.\-K\. Noh \(Eds\.\), Proceedings of the Ninth Asian Conference on Machine Learning, Vol\. 77 of Proceedings of Machine Learning Research, PMLR, Yonsei University, Seoul, Republic of Korea, 2017, pp\. 279–294\.
- \[29\]S\. Surjanovic, D\. Bingham, Virtual library of simulation experiments: Test functions and datasets, Retrieved November 14, 2025, from[http://www\.sfu\.ca/~ssurjano](http://www.sfu.ca/~ssurjano)\.
- \[30\]L\. Yang, J\. Lyu, W\. Lyu, Z\. Chen, Efficient robust bayesian optimization for arbitrary uncertain inputs, in: Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Curran Associates Inc\., Red Hook, NY, USA, 2023\.
- \[31\]B\. W\. Silverman, Some aspects of the spline smoothing approach to non\-parametric regression curve fitting, Journal of the Royal Statistical Society: Series B \(Methodological\) 47 \(1\) \(1985\) 1–21\.
- \[32\]Z\. Wang, S\. Jegelka, Max\-value entropy search for efficient bayesian optimization, in: International conference on machine learning, PMLR, 2017, pp\. 3627–3635\.

## Appendix AProofs

### A\.1

We first provide proofs of the weight\-concentration results with AdaHedge and Standard Hedge used as the online learning algorithms\.

##### Lemma[4\.2](https://arxiv.org/html/2609.19891#S4.Thmtheorem2)

Assume the per\-round loss difference between the best kernelm∗m^\{\*\}and any other kernel is bounded from below,ℓm\(t\)−ℓm∗\(t\)≥Δ\>0\\ell\_\{m\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}\\geq\\Delta\>0\. Thenwm∗\(T\)≥1−εw\_\{m^\{\*\}\}^\{\(T\)\}\\geq 1\-\\varepsilonunder either of the following conditions:

1. 1\.withη\(T\)\\eta^\{\(T\)\}given by Equation[1](https://arxiv.org/html/2609.19891#S2.E1)\(AdaHedge\), T≥1\+max⁡\{4​aM2ln⁡M,1Δ2​ln⁡M​ln2⁡\(\(M−1\)​\(1−ε\)ε\)\},T\\geq 1\+\\max\\left\\\{\\frac\{4a\_\{M\}^\{2\}\}\{\\ln M\},\\frac\{1\}\{\\Delta^\{2\}\\ln M\}\\ln^\{2\}\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\\right\\\},whereaM=1\+23​ln⁡Ma\_\{M\}=1\+\\frac\{2\}\{3\}\\ln M\.
2. 2\.with a constantη\(T\)=η\\eta^\{\(T\)\}=\\eta\(Hedge\), T≥1\+1η​Δ​ln⁡\(\(M−1\)​\(1−ε\)ε\)\.T\\geq 1\+\\frac\{1\}\{\\eta\\Delta\}\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\.

###### Proof\.

For both update rules,

wm∗\(T\)\\displaystyle w\_\{m^\{\*\}\}^\{\(T\)\}=exp⁡\(−η\(T\)​Lm∗\(T−1\)\)∑i=1Mexp⁡\(−η\(T\)​Li\(T−1\)\)\\displaystyle=\\frac\{\\exp\\left\(\-\\eta^\{\(T\)\}L\_\{m^\{\*\}\}^\{\(T\-1\)\}\\right\)\}\{\\sum\_\{i=1\}^\{M\}\\exp\\left\(\-\\eta^\{\(T\)\}L\_\{i\}^\{\(T\-1\)\}\\right\)\}=11\+∑i=1,i≠m∗Mexp⁡\(−η\(T\)​\(Li\(T−1\)−Lm∗\(T−1\)\)\)\\displaystyle=\\frac\{1\}\{1\+\\sum\_\{i=1,i\\neq\{m^\{\*\}\}\}^\{M\}\\exp\\left\(\-\\eta^\{\(T\)\}\(L\_\{i\}^\{\(T\-1\)\}\-L\_\{m^\{\*\}\}^\{\(T\-1\)\}\)\\right\)\}≥11\+\(M−1\)​exp⁡\(−η\(T\)​\(T−1\)​Δ\)\.\\displaystyle\\geq\\frac\{1\}\{1\+\(M\-1\)\\exp\\left\(\-\\eta^\{\(T\)\}\(T\-1\)\\Delta\\right\)\}\.
We will havewm∗\(T\)≥1−εw\_\{m^\{\*\}\}^\{\(T\)\}\\geq 1\-\\varepsilonif

11\+\(M−1\)​exp⁡\(−η\(T\)​\(T−1\)​Δ\)\\displaystyle\\frac\{1\}\{1\+\(M\-1\)\\exp\\left\(\-\\eta^\{\(T\)\}\(T\-1\)\\Delta\\right\)\}≥1−ε\\displaystyle\\geq 1\-\\varepsilonη\(T\)​\(T−1\)​Δ\\displaystyle\\eta^\{\(T\)\}\(T\-1\)\\Delta≥ln⁡\(\(M−1\)​\(1−ε\)ε\)\.\\displaystyle\\geq\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\.\(4\)
Case 1: AdaHedge\.

From De Rooij et al\.\[[4](https://arxiv.org/html/2609.19891#bib.bib4), Lemma 5\],

\(Δm​i​x\(T−1\)\)2≤VT−1​ln⁡M\+\(1\+23​ln⁡M\)​Δm​i​x\(T−1\)\.\(\\Delta\_\{mix\}^\{\(T\-1\)\}\)^\{2\}\\leq V\_\{T\-1\}\\ln M\+\\left\(1\+\\frac\{2\}\{3\}\\ln M\\right\)\\Delta\_\{mix\}^\{\(T\-1\)\}\.From De Rooij et al\.\[[4](https://arxiv.org/html/2609.19891#bib.bib4), Lemma 4\],vt≤1/4v\_\{t\}\\leq 1/4, thusVT−1≤T−14V\_\{T\-1\}\\leq\\frac\{T\-1\}\{4\}\. Usingx2≤a\+b​x⟹x≤a\+bx^\{2\}\\leq a\+bx\\implies x\\leq\\sqrt\{a\}\+b,

Δm​i​x\(T−1\)≤12​\(T−1\)​ln⁡M\+1\+23​ln⁡M\.\\Delta\_\{mix\}^\{\(T\-1\)\}\\leq\\frac\{1\}\{2\}\\sqrt\{\(T\-1\)\\ln M\}\+1\+\\frac\{2\}\{3\}\\ln M\.
η\(T\)=ln⁡MΔm​i​x\(T−1\)≥2​ln⁡M\(T−1\)​ln⁡M\+2​\(1\+23​ln⁡M\)\.\\eta^\{\(T\)\}=\\frac\{\\ln M\}\{\\Delta\_\{mix\}^\{\(T\-1\)\}\}\\geq\\frac\{2\\ln M\}\{\\sqrt\{\(T\-1\)\\ln M\}\+2\(1\+\\frac\{2\}\{3\}\\ln M\)\}\.
LetaM:=1\+23​ln⁡Ma\_\{M\}:=1\+\\frac\{2\}\{3\}\\ln M\. If\(T−1\)​ln⁡M≥2​aM\\sqrt\{\(T\-1\)\\ln M\}\\geq 2a\_\{M\}, then

T≥1\+4​aM2ln⁡MT\\geq 1\+\\frac\{4a\_\{M\}^\{2\}\}\{\\ln M\}and

η\(T\)≥ln⁡MT−1\.\\eta^\{\(T\)\}\\geq\\sqrt\{\\frac\{\\ln M\}\{T\-1\}\}\.Substituting this into \([4](https://arxiv.org/html/2609.19891#A1.E4)\) gives

T≥1\+1Δ2​ln⁡M​ln2⁡\(\(M−1\)​\(1−ε\)ε\)\.T\\geq 1\+\\frac\{1\}\{\\Delta^\{2\}\\ln M\}\\ln^\{2\}\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\.
Hence the stated AdaHedge condition is sufficient\.

Case 2: Hedge\.

For Hedge,η\(T\)=η\\eta^\{\(T\)\}=\\etais fixed\. Substituting this into \([4](https://arxiv.org/html/2609.19891#A1.E4)\) gives

T≥1\+1η​Δ​ln⁡\(\(M−1\)​\(1−ε\)ε\)\.T\\geq 1\+\\frac\{1\}\{\\eta\\Delta\}\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\.
Hence the stated Hedge condition is sufficient\. ∎

##### Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)

Letℱt\\mathcal\{F\}\_\{t\}be the filtration generated by all randomness and observations up to roundtt\. Assume the per\-round loss difference between the best kernelm∗m^\{\*\}and any other kernel is bounded from below in expectation,

𝔼⁡\[ℓm\(t\)−ℓm∗\(t\)∣ℱt−1\]≥Δ,∀m≠m∗,t∈\{1,…,T−1\}\.\\mathbb\{E\}\\left\[\\ell\_\{m\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\geq\\Delta,\\qquad\\forall m\\neq m^\{\*\},\\;t\\in\\\{1,\\dots,T\-1\\\}\.Thenwm∗\(T\)≥1−εw\_\{m^\{\*\}\}^\{\(T\)\}\\geq 1\-\\varepsilonwith probability at least1−δ1\-\\deltaunder either of the following conditions:

1. 1\.withη\(T\)\\eta^\{\(T\)\}given by Equation[1](https://arxiv.org/html/2609.19891#S2.E1)\(AdaHedge\), T≥1\+max⁡\{4​aM2ln⁡M,4Δ2​ln⁡M​ln2⁡\(\(M−1\)​\(1−ε\)ε\),32Δ2​ln⁡\(M−1δ\)\},T\\geq 1\+\\max\\left\\\{\\frac\{4a\_\{M\}^\{2\}\}\{\\ln M\},\\frac\{4\}\{\\Delta^\{2\}\\ln M\}\\ln^\{2\}\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\),\\frac\{32\}\{\\Delta^\{2\}\}\\ln\\left\(\\frac\{M\-1\}\{\\delta\}\\right\)\\right\\\},whereaM=1\+23​ln⁡Ma\_\{M\}=1\+\\frac\{2\}\{3\}\\ln M\.
2. 2\.with a constantη\(T\)=η\\eta^\{\(T\)\}=\\eta\(Hedge\), T≥1\+max⁡\{2η​Δ​ln⁡\(\(M−1\)​\(1−ε\)ε\),32Δ2​ln⁡\(M−1δ\)\}\.T\\geq 1\+\\max\\left\\\{\\frac\{2\}\{\\eta\\Delta\}\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\),\\frac\{32\}\{\\Delta^\{2\}\}\\ln\\left\(\\frac\{M\-1\}\{\\delta\}\\right\)\\right\\\}\.

###### Proof\.

Let

Xi\(t\):=\(ℓi\(t\)−ℓm∗\(t\)\)−𝔼⁡\[ℓi\(t\)−ℓm∗\(t\)∣ℱt−1\]\.X\_\{i\}^\{\(t\)\}:=\(\\ell\_\{i\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}\)\-\\mathbb\{E\}\\left\[\\ell\_\{i\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\.Then\{Xi\(t\)\}\\\{X\_\{i\}^\{\(t\)\}\\\}is a martingale difference sequence\. Using Azuma–Hoeffding and noting that\(ℓi\(t\)−ℓj\(t\)\)∈\[−1,1\]\(\\ell\_\{i\}^\{\(t\)\}\-\\ell\_\{j\}^\{\(t\)\}\)\\in\[\-1,1\], which implies\|Xi\(t\)\|≤2\|X\_\{i\}^\{\(t\)\}\|\\leq 2, we have

ℙ⁡\(∑t=1T−1Xi\(t\)≤−a\)≤exp⁡\(−a28​\(T−1\)\)\.\\mathbb\{P\}\\left\(\\sum\_\{t=1\}^\{T\-1\}X\_\{i\}^\{\(t\)\}\\leq\-a\\right\)\\leq\\exp\\left\(\-\\frac\{a^\{2\}\}\{8\(T\-1\)\}\\right\)\.
Using𝔼⁡\[ℓi\(t\)−ℓm∗\(t\)∣ℱt−1\]≥Δ,\\mathbb\{E\}\\left\[\\ell\_\{i\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\geq\\Delta,we obtain

ℙ⁡\(Li\(T−1\)−Lm∗\(T−1\)≤−a\+\(T−1\)​Δ\)\\displaystyle\\mathbb\{P\}\\left\(L\_\{i\}^\{\(T\-1\)\}\-L\_\{m^\{\*\}\}^\{\(T\-1\)\}\\leq\-a\+\(T\-1\)\\Delta\\right\)≤ℙ⁡\(Li\(T−1\)−Lm∗\(T−1\)≤−a\+∑t=1T−1𝔼⁡\[ℓi\(t\)−ℓm∗\(t\)∣ℱt−1\]\)\\displaystyle\\leq\\mathbb\{P\}\\Bigg\(L\_\{i\}^\{\(T\-1\)\}\-L\_\{m^\{\*\}\}^\{\(T\-1\)\}\\leq\-a\+\\sum\_\{t=1\}^\{T\-1\}\\mathbb\{E\}\\left\[\\ell\_\{i\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}\\mid\\mathcal\{F\}\_\{t\-1\}\\right\]\\Bigg\)≤exp⁡\(−a28​\(T−1\)\)\.\\displaystyle\\leq\\exp\\left\(\-\\frac\{a^\{2\}\}\{8\(T\-1\)\}\\right\)\.Settinga=2​2​\(T−1\)​ln⁡\(M−1δ\)a=2\\sqrt\{2\(T\-1\)\\ln\\left\(\\frac\{M\-1\}\{\\delta\}\\right\)\}gives

ℙ⁡\(Li\(T−1\)−Lm∗\(T−1\)≤\(T−1\)​Δ−2​2​\(T−1\)​ln⁡\(M−1δ\)\)≤δM−1\.\\mathbb\{P\}\\left\(L\_\{i\}^\{\(T\-1\)\}\-L\_\{m^\{\*\}\}^\{\(T\-1\)\}\\leq\(T\-1\)\\Delta\-2\\sqrt\{2\(T\-1\)\\ln\\left\(\\frac\{M\-1\}\{\\delta\}\\right\)\}\\right\)\\leq\\frac\{\\delta\}\{M\-1\}\.Using a union bound over alli≠m∗i\\neq m^\{\*\}, with probability at least1−δ1\-\\delta,

Li\(T−1\)−Lm∗\(T−1\)≥\(T−1\)​Δ−2​2​\(T−1\)​ln⁡\(M−1δ\)L\_\{i\}^\{\(T\-1\)\}\-L\_\{m^\{\*\}\}^\{\(T\-1\)\}\\geq\(T\-1\)\\Delta\-2\\sqrt\{2\(T\-1\)\\ln\\left\(\\frac\{M\-1\}\{\\delta\}\\right\)\}for everyi≠m∗i\\neq m^\{\*\}\. IfT≥1\+32Δ2​ln⁡\(M−1δ\),T\\geq 1\+\\frac\{32\}\{\\Delta^\{2\}\}\\ln\\left\(\\frac\{M\-1\}\{\\delta\}\\right\),then

Li\(T−1\)−Lm∗\(T−1\)≥12​\(T−1\)​ΔL\_\{i\}^\{\(T\-1\)\}\-L\_\{m^\{\*\}\}^\{\(T\-1\)\}\\geq\\frac\{1\}\{2\}\(T\-1\)\\Deltafor everyi≠m∗i\\neq m^\{\*\}\. Therefore,

wm∗\(T\)\\displaystyle w\_\{m^\{\*\}\}^\{\(T\)\}=11\+∑i=1,i≠m∗Mexp⁡\(−η\(T\)​\(Li\(T−1\)−Lm∗\(T−1\)\)\)\\displaystyle=\\frac\{1\}\{1\+\\sum\_\{i=1,i\\neq m^\{\*\}\}^\{M\}\\exp\\left\(\-\\eta^\{\(T\)\}\(L\_\{i\}^\{\(T\-1\)\}\-L\_\{m^\{\*\}\}^\{\(T\-1\)\}\)\\right\)\}≥11\+\(M−1\)​exp⁡\(−η\(T\)​\(T−1\)​Δ2\)\.\\displaystyle\\geq\\frac\{1\}\{1\+\(M\-1\)\\exp\\left\(\-\\eta^\{\(T\)\}\\frac\{\(T\-1\)\\Delta\}\{2\}\\right\)\}\.We will havewm∗\(T\)≥1−εw\_\{m^\{\*\}\}^\{\(T\)\}\\geq 1\-\\varepsilonif

11\+\(M−1\)​exp⁡\(−η\(T\)​\(T−1\)​Δ2\)\\displaystyle\\frac\{1\}\{1\+\(M\-1\)\\exp\\left\(\-\\eta^\{\(T\)\}\\frac\{\(T\-1\)\\Delta\}\{2\}\\right\)\}≥1−ε,\\displaystyle\\geq 1\-\\varepsilon,η\(T\)​\(T−1\)​Δ2\\displaystyle\\eta^\{\(T\)\}\\frac\{\(T\-1\)\\Delta\}\{2\}≥ln⁡\(\(M−1\)​\(1−ε\)ε\)\.\\displaystyle\\geq\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\.\(5\)
Case 1: AdaHedge\.

As shown in the proof of Lemma[4\.2](https://arxiv.org/html/2609.19891#S4.Thmtheorem2), ifT≥1\+4​aM2ln⁡M,T\\geq 1\+\\frac\{4a\_\{M\}^\{2\}\}\{\\ln M\},then

η\(T\)≥ln⁡MT−1\.\\eta^\{\(T\)\}\\geq\\sqrt\{\\frac\{\\ln M\}\{T\-1\}\}\.Substituting this into Inequality[5](https://arxiv.org/html/2609.19891#A1.E5), we require

Δ2​\(T−1\)​ln⁡M≥ln⁡\(\(M−1\)​\(1−ε\)ε\),\\frac\{\\Delta\}\{2\}\\sqrt\{\(T\-1\)\\ln M\}\\geq\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\),which gives

T≥1\+4Δ2​ln⁡M​ln2⁡\(\(M−1\)​\(1−ε\)ε\)\.T\\geq 1\+\\frac\{4\}\{\\Delta^\{2\}\\ln M\}\\ln^\{2\}\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\.Together with

T≥1\+32Δ2​ln⁡\(M−1δ\),T\\geq 1\+\\frac\{32\}\{\\Delta^\{2\}\}\\ln\\left\(\\frac\{M\-1\}\{\\delta\}\\right\),the AdaHedge condition follows\.

Case 2: Hedge\.

For Hedge,η\(T\)=η\\eta^\{\(T\)\}=\\eta\. Therefore, Inequality[5](https://arxiv.org/html/2609.19891#A1.E5)becomes

η​\(T−1\)​Δ2≥ln⁡\(\(M−1\)​\(1−ε\)ε\),\\eta\\frac\{\(T\-1\)\\Delta\}\{2\}\\geq\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\),which gives

T≥1\+2η​Δ​ln⁡\(\(M−1\)​\(1−ε\)ε\)\.T\\geq 1\+\\frac\{2\}\{\\eta\\Delta\}\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\varepsilon\)\}\{\\varepsilon\}\\right\)\.Together with

T≥1\+32Δ2​ln⁡\(M−1δ\),T\\geq 1\+\\frac\{32\}\{\\Delta^\{2\}\}\\ln\\left\(\\frac\{M\-1\}\{\\delta\}\\right\),the Hedge condition follows\. ∎

### A\.2

##### Corollary[5\.4](https://arxiv.org/html/2609.19891#S5.Thmtheorem4)

Assume the conditional loss\-gap condition of Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)holds form∗m^\{\*\}with gapΔ\>0\\Delta\>0\. Fix a horizonTT, letδ0=δconc/nT\\delta\_\{0\}=\\delta\_\{\\mathrm\{conc\}\}/n\_\{T\}, and define

ϵt=M−1M−1\+exp⁡\(Δ2​\(t−1\)​ln⁡M\),\\epsilon\_\{t\}=\\frac\{M\-1\}\{M\-1\+\\exp\\\!\\left\(\\frac\{\\Delta\}\{2\}\\sqrt\{\(t\-1\)\\ln M\}\\right\)\},fort∈ITt\\in I\_\{T\}and letT0T\_\{0\}satisfy

T0≥max⁡\{4​aM2ln⁡M,32Δ2​ln⁡\(M−1δ0\)\}\.T\_\{0\}\\geq\\max\\left\\\{\\frac\{4a\_\{M\}^\{2\}\}\{\\ln M\},\\;\\frac\{32\}\{\\Delta^\{2\}\}\\ln\\\!\\left\(\\frac\{M\-1\}\{\\delta\_\{0\}\}\\right\)\\right\\\}\.Then, for this fixed horizon, withc=Δ2​ln⁡Mc=\\tfrac\{\\Delta\}\{2\}\\sqrt\{\\ln M\}, the summation ofϵt\\epsilon\_\{t\}post\-burn\-in is bounded by

∑t=T0\+1Tϵt≤\(M−1\)​\[1\+2c2​\(1\+c​T0\)\]​e−c​T0\.\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}\\;\\leq\\;\(M\-1\)\\\!\\left\[1\+\\frac\{2\}\{c^\{2\}\}\\\!\\left\(1\+c\\sqrt\{T\_\{0\}\}\\right\)\\right\]e^\{\-c\\sqrt\{T\_\{0\}\}\}\.Consequently, in Theorem[5\.3](https://arxiv.org/html/2609.19891#S5.Thmtheorem3)the additional simple\-regret term satisfies

2​BEInT​∑t=T0\+1Tϵt=O⁡\(1nT\)\.\\frac\{2B\_\{\\mathrm\{EI\}\}\}\{n\_\{T\}\}\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}=O\\\!\\left\(\\frac\{1\}\{n\_\{T\}\}\\right\)\.
###### Proof\.

Fixt∈ITt\\in I\_\{T\}and apply Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)with terminal timett, confidence levelδ0\\delta\_\{0\}, and error levelϵt\\epsilon\_\{t\}\. Sincet−1≥T0t\-1\\geq T\_\{0\}, the first and third terms in the maximum of Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)are bounded byt−1t\-1by assumption\. For the second term, the definition ofϵt\\epsilon\_\{t\}gives

ln⁡\(\(M−1\)​\(1−ϵt\)ϵt\)=Δ2​\(t−1\)​ln⁡M\.\\ln\\left\(\\frac\{\(M\-1\)\(1\-\\epsilon\_\{t\}\)\}\{\\epsilon\_\{t\}\}\\right\)=\\frac\{\\Delta\}\{2\}\\sqrt\{\(t\-1\)\\ln M\}\.Hence

4Δ2​ln⁡M​ln2⁡\(\(M−1\)​\(1−ϵt\)ϵt\)=t−1\.\\frac\{4\}\{\\Delta^\{2\}\\ln M\}\\ln^\{2\}\\left\(\\frac\{\(M\-1\)\(1\-\\epsilon\_\{t\}\)\}\{\\epsilon\_\{t\}\}\\right\)=t\-1\.Thus Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)yieldsℙ⁡\(wm∗\(t\)≥1−ϵt\)≥1−δ0\.\\mathbb\{P\}\\left\(w\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\epsilon\_\{t\}\\right\)\\geq 1\-\\delta\_\{0\}\.Taking a union bound overt∈ITt\\in I\_\{T\}gives the stated simultaneous event\. Finally,

ϵt=M−1M−1\+ec​t−1≤\(M−1\)​e−c​t−1,\\epsilon\_\{t\}=\\frac\{M\-1\}\{M\-1\+e^\{c\\sqrt\{t\-1\}\}\}\\leq\(M\-1\)e^\{\-c\\sqrt\{t\-1\}\},so

∑t=T0\+1Tϵt≤\(M−1\)​∑s=T0T−1e−c​s≤\(M−1\)​\(e−c​T0\+∫T0∞e−c​x​𝑑x\)\.\\sum\_\{t=T\_\{0\}\+1\}^\{T\}\\epsilon\_\{t\}\\leq\(M\-1\)\\sum\_\{s=T\_\{0\}\}^\{T\-1\}e^\{\-c\\sqrt\{s\}\}\\leq\(M\-1\)\\left\(e^\{\-c\\sqrt\{T\_\{0\}\}\}\+\\int\_\{T\_\{0\}\}^\{\\infty\}e^\{\-c\\sqrt\{x\}\}\\,dx\\right\)\.The change of variablesu=xu=\\sqrt\{x\}gives

∫T0∞e−c​x​𝑑x=2​∫T0∞u​e−c​u​𝑑u=2c2​\(1\+c​T0\)​e−c​T0,\\int\_\{T\_\{0\}\}^\{\\infty\}e^\{\-c\\sqrt\{x\}\}\\,dx=2\\int\_\{\\sqrt\{T\_\{0\}\}\}^\{\\infty\}ue^\{\-cu\}\\,du=\\frac\{2\}\{c^\{2\}\}\(1\+c\\sqrt\{T\_\{0\}\}\)e^\{\-c\\sqrt\{T\_\{0\}\}\},which proves the summation bound\. ∎

### A\.3

##### Lemma[6\.1](https://arxiv.org/html/2609.19891#S6.Thmtheorem1)

Under Assumption[A2](https://arxiv.org/html/2609.19891#Thmngassumption2), supposeEI​\-​LSEt,m​\(x\)≤BLSE\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\\leq B\_\{\\mathrm\{LSE\}\}for allm∈\{1,…,M\}m\\in\\\{1,\\dots,M\\\}andx∈𝒳x\\in\\mathcal\{X\}\. Ifwm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\varepsilon, then

supx\|EI​\-​LSEt,MoG​\(x\)−EI​\-​LSEt,m∗​\(x\)\|≤ε​BLSE\+β⁡\(ε​κ2\+supxαt,disag​\(x\)\)\.\\sup\_\{x\}\\big\|\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\varepsilon B\_\{\\mathrm\{LSE\}\}\+\\beta\\Big\(\\varepsilon\\kappa^\{2\}\+\\sup\_\{x\}\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\Big\)\.
###### Proof\.

By the MoG construction \(linearity of expectation for the EI–LSE term\),

EI​\-​LSEt,MoG​\(x\)=∑m=1Mwm\(t\)​EI​\-​LSEt,m​\(x\)\+β​σ¯t2​\(x\),\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,\\mathrm\{MoG\}\}\(x\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\\;\+\\;\\beta\\,\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\),whereσ¯t2​\(x\)\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\)is the MoG posterior predictive variance\. Letm∗∈\{1,…,M\}m^\{\*\}\\in\\\{1,\\dots,M\\\}satisfywm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\varepsilon\. Fix anyx∈𝒳x\\in\\mathcal\{X\},

EI​\-​LSEt,MoG​\(x\)−EI​\-​LSEt,m∗​\(x\)\\displaystyle\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)=∑m=1Mwm\(t\)​EI​\-​LSEt,m​\(x\)−EI​\-​LSEt,m∗​\(x\)\+β​σ¯t2​\(x\)\\displaystyle=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\;\+\\;\\beta\\,\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\)=∑m≠m∗wm\(t\)​\(EI​\-​LSEt,m​\(x\)−EI​\-​LSEt,m∗​\(x\)\)\+β​σ¯t2​\(x\)\.\\displaystyle=\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\(t\)\}\\Big\(\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\Big\)\\;\+\\;\\beta\\,\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\)\.Taking absolute values and applying the triangle inequality yields

\|EI​\-​LSEt,MoG​\(x\)−EI​\-​LSEt,m∗​\(x\)\|\\displaystyle\\big\|\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\big\|≤∑m≠m∗wm\(t\)​\|EI​\-​LSEt,m​\(x\)−EI​\-​LSEt,m∗​\(x\)\|\+β​σ¯t2​\(x\)\.\\displaystyle\\leq\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\(t\)\}\\,\\big\|\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\;\+\\;\\beta\\,\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\)\.Since0≤EI​\-​LSEt,m​\(x\)≤BLSE0\\leq\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\\leq B\_\{\\mathrm\{LSE\}\}for allmmandxx,\|EI​\-​LSEt,m​\(x\)−EI​\-​LSEt,m∗​\(x\)\|≤BLSE,\\big\|\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq B\_\{\\mathrm\{LSE\}\},and therefore

∑m≠m∗wm\(t\)​\|EI​\-​LSEt,m​\(x\)−EI​\-​LSEt,m∗​\(x\)\|≤∑m≠m∗wm\(t\)​BLSE=\(1−wm∗\(t\)\)​BLSE≤ε​BLSE\.\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\(t\)\}\\,\\big\|\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\(t\)\}\\,B\_\{\\mathrm\{LSE\}\}=\(1\-w\_\{m^\{\*\}\}^\{\(t\)\}\)B\_\{\\mathrm\{LSE\}\}\\leq\\varepsilon B\_\{\\mathrm\{LSE\}\}\.Next, use the MoG posterior predictive variance decomposition

σ¯t2​\(x\)=∑m=1Mwm\(t\)​σt,m2​\(x\)\+αt,disag​\(x\),\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\sigma\_\{t,m\}^\{2\}\(x\)\\;\+\\;\\alpha\_\{t,\\mathrm\{disag\}\}\(x\),Hence,

σ¯t2​\(x\)=∑m≠m∗wm\(t\)​σt,m2​\(x\)\+wm∗\(t\)​σt,m∗2​\(x\)\+αt,disag​\(x\)≤\(1−wm∗\(t\)\)​κ2\+σt,m∗2​\(x\)\+αt,disag​\(x\),\\bar\{\\sigma\}\_\{t\}^\{2\}\(x\)=\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\(t\)\}\\,\\sigma\_\{t,m\}^\{2\}\(x\)\\;\+\\;w\_\{m^\{\*\}\}^\{\(t\)\}\\sigma\_\{t,m^\{\*\}\}^\{2\}\(x\)\\;\+\\;\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\leq\(1\-w\_\{m^\{\*\}\}^\{\(t\)\}\)\\kappa^\{2\}\\;\+\\;\\sigma\_\{t,m^\{\*\}\}^\{2\}\(x\)\\;\+\\;\\alpha\_\{t,\\mathrm\{disag\}\}\(x\),where the inequality uses Assumption[A2](https://arxiv.org/html/2609.19891#Thmngassumption2):σt,m2​\(x\)≤κ2\\sigma\_\{t,m\}^\{2\}\(x\)\\leq\\kappa^\{2\}for allm,xm,x\. Combining the two bounds gives, for everyxx,

\|EI​\-​LSEt,MoG​\(x\)−EI​\-​LSEt,m∗​\(x\)\|≤ε​BLSE\+β⁡\(ε​κ2\+αt,disag​\(x\)\)\.\\big\|\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\varepsilon B\_\{\\mathrm\{LSE\}\}\\;\+\\;\\beta\\Big\(\\varepsilon\\kappa^\{2\}\+\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\Big\)\.Takingsupx∈𝒳\\sup\_\{x\\in\\mathcal\{X\}\}finishes the proof:

supx∈𝒳\|EI​\-​LSEt,MoG​\(x\)−EI​\-​LSEt,m∗​\(x\)\|≤ε​BLSE\+β⁡\(ε​κ2\+supx∈𝒳αt,disag​\(x\)\)\.∎\\sup\_\{x\\in\\mathcal\{X\}\}\\big\|\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\mathrm\{EI\\text\{\-\}LSE\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\varepsilon B\_\{\\mathrm\{LSE\}\}\\;\+\\;\\beta\\Big\(\\varepsilon\\kappa^\{2\}\+\\sup\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\Big\)\.\\qed

##### Corollary[6\.2](https://arxiv.org/html/2609.19891#S6.Thmtheorem2)

Forτ∈\(0,1\)\\tau\\in\(0,1\), define the setSt,m​\(τ\):=\{x:πt,mlse​\(x\)≥τ\}S\_\{t,m\}\(\\tau\):=\\\{x:\\ \\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\)\\geq\\tau\\\}and defineSt,MoG​\(τ\)S\_\{t,\\mathrm\{MoG\}\}\(\\tau\)similarly\. Ifwm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\varepsilon, then the symmetric difference of the two sets satisfies

St,MoG​\(τ\)​△​St,m∗​\(τ\)⊆\{x∈𝒳:\|πt,m∗lse​\(x\)−τ\|≤ε\}\.S\_\{t,\\mathrm\{MoG\}\}\(\\tau\)\\triangle S\_\{t,m^\{\*\}\}\(\\tau\)\\subseteq\\left\\\{x\\in\\mathcal\{X\}:\\left\|\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\-\\tau\\right\|\\leq\\varepsilon\\right\\\}\.
###### Proof\.

Under the MoG predictive distribution, the law of total probability gives, for everyx∈𝒳x\\in\\mathcal\{X\},

πt,MoGlse​\(x\):=ℙMoG​\(Yt≥h∣x,Dt−1\)=∑m=1Mwm\(t\)​πt,mlse​\(x\)\.\\pi^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(x\):=\\mathbb\{P\}\_\{\\mathrm\{MoG\}\}\(Y\_\{t\}\\geq h\\mid x,D\_\{t\-1\}\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\)\.Fixm∗m^\{\*\}such thatwm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\(t\)\}\\geq 1\-\\varepsilon, and fix anyx∈𝒳x\\in\\mathcal\{X\}\. Then

πt,MoGlse​\(x\)−πt,m∗lse​\(x\)\\displaystyle\\pi^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)=∑m=1Mwm\(t\)​πt,mlse​\(x\)−πt,m∗lse​\(x\)\\displaystyle=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\(t\)\}\\,\\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\)\-\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)=∑m≠m∗wm\(t\)​\(πt,mlse​\(x\)−πt,m∗lse​\(x\)\)\.\\displaystyle=\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\(t\)\}\\Big\(\\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\)\-\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\\Big\)\.Taking absolute values and applying the triangle inequality yields

\|πt,MoGlse​\(x\)−πt,m∗lse​\(x\)\|≤∑m≠m∗wm\(t\)​\|πt,mlse​\(x\)−πt,m∗lse​\(x\)\|\.\\Big\|\\pi^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\\Big\|\\leq\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\(t\)\}\\,\\Big\|\\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\)\-\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\\Big\|\.Since eachπt,mlse​\(x\)∈\[0,1\]\\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\)\\in\[0,1\], we have\|πt,mlse​\(x\)−πt,m∗lse​\(x\)\|≤1\\big\|\\pi^\{\\textsc\{lse\}\}\_\{t,m\}\(x\)\-\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq 1, hence

\|πt,MoGlse​\(x\)−πt,m∗lse​\(x\)\|≤∑m≠m∗wm\(t\)=1−wm∗\(t\)≤ε\.\\Big\|\\pi^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\\Big\|\\leq\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\(t\)\}=1\-w\_\{m^\{\*\}\}^\{\(t\)\}\\leq\\varepsilon\.Letx∈St,MoG​\(τ\)∖St,m∗​\(τ\)x\\in S\_\{t,\\mathrm\{MoG\}\}\(\\tau\)\\setminus S\_\{t,m^\{\*\}\}\(\\tau\)\. Thenπt,MoGlse​\(x\)≥τ\\pi^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(x\)\\geq\\tauandπt,m∗lse​\(x\)<τ\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)<\\tau, so

τ≤πt,MoGlse​\(x\)≤πt,m∗lse​\(x\)\+ε⇒πt,m∗lse​\(x\)≥τ−ε⇒\|πt,m∗lse​\(x\)−τ\|≤ε\.\\tau\\leq\\pi^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(x\)\\leq\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\+\\varepsilon\\quad\\Rightarrow\\quad\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\\geq\\tau\-\\varepsilon\\quad\\Rightarrow\\quad\\big\|\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\-\\tau\\big\|\\leq\\varepsilon\.Similarly, ifx∈St,m∗​\(τ\)∖St,MoG​\(τ\)x\\in S\_\{t,m^\{\*\}\}\(\\tau\)\\setminus S\_\{t,\\mathrm\{MoG\}\}\(\\tau\), thenπt,m∗lse​\(x\)≥τ\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\\geq\\tauandπt,MoGlse​\(x\)<τ\\pi^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(x\)<\\tau, so

πt,m∗lse​\(x\)≤πt,MoGlse​\(x\)\+ε<τ\+ε⇒\|πt,m∗lse​\(x\)−τ\|≤ε\.\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\\leq\\pi^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(x\)\+\\varepsilon<\\tau\+\\varepsilon\\quad\\Rightarrow\\quad\\big\|\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\-\\tau\\big\|\\leq\\varepsilon\.Combining the two cases,

St,MoGlse​\(τ\)​△​St,m∗lse​\(τ\)⊆\{x∈𝒳:\|πt,m∗lse​\(x\)−τ\|≤ε\},S^\{\\textsc\{lse\}\}\_\{t,\\mathrm\{MoG\}\}\(\\tau\)\\,\\triangle\\,S^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(\\tau\)\\subseteq\\left\\\{x\\in\\mathcal\{X\}:\\big\|\\pi^\{\\textsc\{lse\}\}\_\{t,m^\{\*\}\}\(x\)\-\\tau\\big\|\\leq\\varepsilon\\right\\\},which is the claimed inclusion\. ∎

### A\.4

##### Lemma[7\.1](https://arxiv.org/html/2609.19891#S7.Thmtheorem1)

Assume Assumption[A2](https://arxiv.org/html/2609.19891#Thmngassumption2)\. Ifwm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\{\(t\)\}\}\\geq 1\-\\varepsilon, then

supx∈𝒳\|σt,MoG2​\(x\)−σt,m∗2​\(x\)\|≤ε​κ2\+supx∈𝒳αt,disag​\(x\)\.\\sup\_\{x\\in\\mathcal\{X\}\}\\big\|\\sigma^\{2\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\varepsilon\\kappa^\{2\}\+\\sup\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\.
###### Proof\.

Letm∗∈\{1,…,M\}m^\{\*\}\\in\\\{1,\\dots,M\\\}satisfywm∗\(t\)≥1−εw\_\{m^\{\*\}\}^\{\{\(t\)\}\}\\geq 1\-\\varepsilon\. By the MoG posterior variance decomposition \(Lemma[4\.1](https://arxiv.org/html/2609.19891#S4.Thmtheorem1)\),

σt,MoG2​\(x\)=∑m=1Mwm\(t\)​σt,m2​\(x\)\+αt,disag​\(x\),\\sigma^\{2\}\_\{t,\\mathrm\{MoG\}\}\(x\)=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\{\(t\)\}\}\\,\\sigma^\{2\}\_\{t,m\}\(x\)\\;\+\\;\\alpha\_\{t,\\mathrm\{disag\}\}\(x\),whereαt,disag​\(x\)≥0\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\geq 0for allxx\. Fix anyx∈𝒳x\\in\\mathcal\{X\}\. Then

σt,MoG2​\(x\)−σt,m∗2​\(x\)\\displaystyle\\sigma^\{2\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)=∑m=1Mwm\(t\)​σt,m2​\(x\)−σt,m∗2​\(x\)\+αt,disag​\(x\)\\displaystyle=\\sum\_\{m=1\}^\{M\}w\_\{m\}^\{\{\(t\)\}\}\\,\\sigma^\{2\}\_\{t,m\}\(x\)\-\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)\\;\+\\;\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)=∑m≠m∗wm\(t\)​σt,m2​\(x\)−\(1−wm∗\(t\)\)​σt,m∗2​\(x\)\+αt,disag​\(x\)\.\\displaystyle=\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\{\(t\)\}\}\\,\\sigma^\{2\}\_\{t,m\}\(x\)\-\\big\(1\-w\_\{m^\{\*\}\}^\{\{\(t\)\}\}\\big\)\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)\\;\+\\;\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\.By Assumption[A2](https://arxiv.org/html/2609.19891#Thmngassumption2),σt,m2​\(x\)≤κ2\\sigma^\{2\}\_\{t,m\}\(x\)\\leq\\kappa^\{2\}for allm,xm,x, so

0≤∑m≠m∗wm\(t\)​σt,m2​\(x\)≤\(1−wm∗\(t\)\)​κ2,0≤\(1−wm∗\(t\)\)​σt,m∗2​\(x\)≤\(1−wm∗\(t\)\)​κ2\.0\\leq\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\{\(t\)\}\}\\,\\sigma^\{2\}\_\{t,m\}\(x\)\\leq\(1\-w\_\{m^\{\*\}\}^\{\{\(t\)\}\}\)\\kappa^\{2\},\\qquad 0\\leq\(1\-w\_\{m^\{\*\}\}^\{\{\(t\)\}\}\)\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)\\leq\(1\-w\_\{m^\{\*\}\}^\{\{\(t\)\}\}\)\\kappa^\{2\}\.Hence the term

A⁡\(x\):=∑m≠m∗wm\(t\)​σt,m2​\(x\)−\(1−wm∗\(t\)\)​σt,m∗2​\(x\)A\(x\):=\\sum\_\{m\\neq m^\{\*\}\}w\_\{m\}^\{\{\(t\)\}\}\\,\\sigma^\{2\}\_\{t,m\}\(x\)\-\\big\(1\-w\_\{m^\{\*\}\}^\{\{\(t\)\}\}\\big\)\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)satisfies\|A⁡\(x\)\|≤\(1−wm∗\(t\)\)​κ2\|A\(x\)\|\\leq\(1\-w\_\{m^\{\*\}\}^\{\{\(t\)\}\}\)\\kappa^\{2\}\. Usingαt,disag​\(x\)≥0\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\geq 0,

\|σt,MoG2​\(x\)−σt,m∗2​\(x\)\|=\|A⁡\(x\)\+αt,disag​\(x\)\|≤\|A⁡\(x\)\|\+αt,disag​\(x\)≤\(1−wm∗\(t\)\)​κ2\+αt,disag​\(x\)≤ε​κ2\+αt,disag​\(x\)\.\\big\|\\sigma^\{2\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)\\big\|=\\big\|A\(x\)\+\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\big\|\\leq\|A\(x\)\|\+\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\leq\(1\-w\_\{m^\{\*\}\}^\{\{\(t\)\}\}\)\\kappa^\{2\}\+\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\\leq\\varepsilon\\kappa^\{2\}\+\\alpha\_\{t,\\mathrm\{disag\}\}\(x\)\.Takingsupx∈𝒳\\sup\_\{x\\in\\mathcal\{X\}\}yields

supx∈𝒳\|σt,MoG2​\(x\)−σt,m∗2​\(x\)\|≤ε​κ2\+supx∈𝒳αt,disag​\(x\),\\sup\_\{x\\in\\mathcal\{X\}\}\\big\|\\sigma^\{2\}\_\{t,\\mathrm\{MoG\}\}\(x\)\-\\sigma^\{2\}\_\{t,m^\{\*\}\}\(x\)\\big\|\\leq\\varepsilon\\kappa^\{2\}\+\\sup\_\{x\\in\\mathcal\{X\}\}\\alpha\_\{t,\\mathrm\{disag\}\}\(x\),as claimed\. ∎

## Appendix BExperimental Details

We use a set of Automatic Relevance Determination \(ARD\) kernels as the candidate kernel dictionary for our adaptive method\. Here are the kernels we used:

- 1\.Squared Exponential \(SE\): k\(x,x′\)=σ2exp\(−12∑i=1d\(xi−xi′\)2ℓi2\)k\(x,x^\{\\prime\}\)=\\sigma^\{2\}\\exp\\\!\\left\(\-\\frac\{1\}\{2\}\\sum\_\{i=1\}^\{d\}\\frac\{\(x\_\{i\}\-x\_\{i\}^\{\\prime\}\)^\{2\}\}\{\\ell\_\{i\}^\{2\}\}\\right\)Infinitely smooth kernel modeling very smooth functions with dimension\-specific lengthscales\.
- 2\.Matérn 5/2 \(M5\): k⁡\(x,x′\)=\\displaystyle k\(x,x^\{\\prime\}\)=\{\}σ2​\(1\+5​r\+53​r2\)​exp⁡\(−5​r\),\\displaystyle\\sigma^\{2\}\\left\(1\+\\sqrt\{5\}r\+\\frac\{5\}\{3\}r^\{2\}\\right\)\\exp\(\-\\sqrt\{5\}r\),r=∑i=1d\(xi−xi′\)2ℓi2\\displaystyle r=\\sqrt\{\\sum\_\{i=1\}^\{d\}\\frac\{\(x\_\{i\}\-x\_\{i\}^\{\\prime\}\)^\{2\}\}\{\\ell\_\{i\}^\{2\}\}\}Models moderately smooth functions with twice mean\-square differentiability\.
- 3\.Matérn 3/2 \(M3\): k⁡\(x,x′\)=\\displaystyle k\(x,x^\{\\prime\}\)=\{\}σ2​\(1\+3​r\)​exp⁡\(−3​r\),\\displaystyle\\sigma^\{2\}\\left\(1\+\\sqrt\{3\}r\\right\)\\exp\(\-\\sqrt\{3\}r\),r=∑i=1d\(xi−xi′\)2ℓi2\\displaystyle r=\\sqrt\{\\sum\_\{i=1\}^\{d\}\\frac\{\(x\_\{i\}\-x\_\{i\}^\{\\prime\}\)^\{2\}\}\{\\ell\_\{i\}^\{2\}\}\}Models rougher functions with once mean\-square differentiability\.
- 4\.Rational Quadratic \(RQ\): k⁡\(x,x′\)=σ2​\(1\+12​α​∑i=1d\(xi−xi′\)2ℓi2\)−αk\(x,x^\{\\prime\}\)=\\sigma^\{2\}\\left\(1\+\\frac\{1\}\{2\\alpha\}\\sum\_\{i=1\}^\{d\}\\frac\{\(x\_\{i\}\-x\_\{i\}^\{\\prime\}\)^\{2\}\}\{\\ell\_\{i\}^\{2\}\}\\right\)^\{\-\\alpha\}Equivalent to a scale mixture of SE kernels with dimension\-wise lengthscales\.
- 5\.Periodic \(PER\): k\(x,x′\)=σ2exp\(−2∑i=1dsin2⁡\(π​\|xi−xi′\|/pi\)ℓi2\)k\(x,x^\{\\prime\}\)=\\sigma^\{2\}\\exp\\\!\\left\(\-2\\sum\_\{i=1\}^\{d\}\\frac\{\\sin^\{2\}\\\!\\big\(\\pi\|x\_\{i\}\-x\_\{i\}^\{\\prime\}\|/p\_\{i\}\\big\)\}\{\\ell\_\{i\}^\{2\}\}\\right\)Models strictly periodic functions with possibly different periodspip\_\{i\}per dimension\.
- 6\.Linear \(LIN\): k⁡\(x,x′\)=σ2​∑i=1d\(xi−ci\)​\(xi′−ci\)k\(x,x^\{\\prime\}\)=\\sigma^\{2\}\\sum\_\{i=1\}^\{d\}\(x\_\{i\}\-c\_\{i\}\)\(x\_\{i\}^\{\\prime\}\-c\_\{i\}\)Models linear trends with dimension\-specific offsets\.

The training data\(X,y\)\(X,y\)are preprocessed by scaling the inputsXXto the unit hypercube\[0,1\]\[0,1\]and standardizing the outputsyyto have zero mean and unit variance\. At each iteration, the hyperparameters of the GP kernel are re\-optimized\. For all experiments, we fit aSingleTaskGPmodel frombotorch\.models\. Most synthetic test functions are taken directly frombotorch\.test\_functionsorbotorch\.test\_functions\.synthetic\. For test functions not available in BoTorch, we implement custom classes inheriting fromSyntheticTestFunctionto ensure consistent behavior and interfaces\.

Before being used by the algorithm, the negative log\-likelihood \(NLL\) losses are further transformed to ensure numerical stability and comparability across kernels\. Specifically, the losses are first shifted by subtracting the minimum NLL value across candidates, making the smallest loss equal to zero\. The shifted losses are then scaled by a constant factorC=10C=10and clipped to the interval\[0,1\]\[0,1\]\. This normalization prevents excessive clamping and also manages to ensure the losses lie in\[0,1\]\[0,1\]for Hedge regret guarantees\.

### B\.1Bayesian Optimization

Log simple regret for each test mentioned below is averaged over 20 seeds and 100 iterations per seed\.

#### B\.1\.1Synthetic Test functions

Table 3:Details of the test functions used in the experiments for Bayesian Optimization\.
#### B\.1\.2Robot Pushing Task

We evaluate on the 3D robot pushing benchmark implemented in a 2D Box2D physics simulator, originally used for Bayesian optimization in robot pre\-image learning\[[32](https://arxiv.org/html/2609.19891#bib.bib32)\]and later adapted as a robust multi\-target benchmark\[[30](https://arxiv.org/html/2609.19891#bib.bib30)\]\. The environment contains a single object \(a puck/“ball”\) initialized at the origino=\(0,0\)o=\(0,0\)and a planar end\-effector initialized atr=\(rx,ry\)r=\(r\_\{x\},r\_\{y\}\)\. An action is parameterized byx=\(rx,ry,tr\)∈\[−5,5\]×\[−5,5\]×\[0,30\],x=\(r\_\{x\},r\_\{y\},t\_\{r\}\)\\in\[\-5,5\]\\times\[\-5,5\]\\times\[0,30\],wheretrt\_\{r\}is the push duration\.

##### Action execution

To keep the action space 3\-dimensional, we do not optimize over a push angle\. Instead, the end\-effector is always commanded to move directly toward the object, i\.e\., along the deterministic directionu⁡\(x\)∝\(o−r\),u\(x\)\\propto\(o\-r\),equivalently fixing the push angle to face the object \(as in prior work\)\. The simulator is stepped forN=round⁡\(10​tr\)N=\\mathrm\{round\}\(10\\,t\_\{r\}\)steps and we record the final object positionl⁡\(x\)∈ℝ2l\(x\)\\in\\mathbb\{R\}^\{2\}\.

##### Objective

Following the robust robot pushing setup of\[[30](https://arxiv.org/html/2609.19891#bib.bib30)\], we define four target locationsg1=\(−3,−3\),g2=\(−3,3\),g3=\(4\.3,4\.3\),g4=\(5\.1,3\.0\),g\_\{1\}=\(\-3,\-3\),\\;g\_\{2\}=\(\-3,3\),\\;g\_\{3\}=\(4\.3,4\.3\),\\;g\_\{4\}=\(5\.1,3\.0\),and measure the terminal loss as a minimum over targets with mixed squared/linear distances:

ℓ⁡\(x\)=min⁡\(‖l⁡\(x\)−g1‖22,‖l⁡\(x\)−g2‖2,‖l⁡\(x\)−g3‖2,‖l⁡\(x\)−g4‖2\)\.\\ell\(x\)\\;=\\;\\min\\big\(\\\|l\(x\)\-g\_\{1\}\\\|\_\{2\}^\{2\},\\;\\\|l\(x\)\-g\_\{2\}\\\|\_\{2\},\\;\\\|l\(x\)\-g\_\{3\}\\\|\_\{2\},\\;\\\|l\(x\)\-g\_\{4\}\\\|\_\{2\}\\big\)\.\(6\)We maximize the rewardf⁡\(x\)=−ℓ⁡\(x\)f\(x\)=\-\\ell\(x\), so that the optimum value is00\.

##### Bayesian optimization protocol

We run Bayesian optimization forT=100T=100iterations using Expected Improvement \(EI\)\. Performance is reported as the \(log\) simple regret, averaged over 20 random seeds\. Sincef⁡\(x\)≤0f\(x\)\\leq 0, the final simple regret can be written asrT=0−maxt≤T⁡f⁡\(xt\)=mint≤T⁡ℓ⁡\(xt\)\.r\_\{T\}=0\-\\max\_\{t\\leq T\}f\(x\_\{t\}\)=\\min\_\{t\\leq T\}\\ell\(x\_\{t\}\)\.We use the same baselines and kernel families as in Section[5\.3](https://arxiv.org/html/2609.19891#S5.SS3)\.

#### B\.1\.3Baseline Details

1. 1\.Uniform Random:A heuristic from\[[6](https://arxiv.org/html/2609.19891#bib.bib6)\]that selects a kernel uniformly at random from the candidate set\.
2. 2\.Best Util:A heuristic from\[[6](https://arxiv.org/html/2609.19891#bib.bib6)\]that selects, at iterationtt, the kernel with the largest maximum acquisition value\.
3. 3\.Equal Weights:A uniform ensemble of GPs\. It is equivalent to HACK with the MoG predictive distribution and a constant zero loss at every round\.
4. 4\.EGP:The primary method of\[[10](https://arxiv.org/html/2609.19891#bib.bib10)\]\. It corresponds to HACK with categorical sampling, Hedge withη=1\\eta=1in place of AdaHedge, and unbounded NLL as the loss function\.
5. 5\.CAKE:We use the CAKE implementation provided in the authors’ public GitHub repository\[[9](https://arxiv.org/html/2609.19891#bib.bib9)\]\. We follow their experimental settings \(nc=5n\_\{c\}=5,pm=0\.7p\_\{m\}=0\.7, andnp=10n\_\{p\}=10\) and usegemini\-2\.0\-flash, which Appendix C of\[[9](https://arxiv.org/html/2609.19891#bib.bib9)\]reports to achieve performance similar togpt\-4o\-mini\.

### B\.2Level Set Estimation

#### B\.2\.1Synthetic Test functions

The synthetic test functions used for Level Set Estimation are defined as follows\.

##### Shifted Negative Himmelblau\[[18](https://arxiv.org/html/2609.19891#bib.bib18)\]

Letx=\(x1,x2\)∈\[−5,5\]2x=\(x\_\{1\},x\_\{2\}\)\\in\[\-5,5\]^\{2\}\. The function is defined as

fHim​\(x\)=−\[\(x12\+x2−11\)2\+\(x1\+x22−7\)2\]\+100,f\_\{\\text\{Him\}\}\(x\)=\-\\Big\[\(x\_\{1\}^\{2\}\+x\_\{2\}\-11\)^\{2\}\+\(x\_\{1\}\+x\_\{2\}^\{2\}\-7\)^\{2\}\\Big\]\+100,\(7\)

##### Gaussian Modulated Sinusoid

Letx=\(x1,x2\)∈\[0,1\]2x=\(x\_\{1\},x\_\{2\}\)\\in\[0,1\]^\{2\}\. The function is defined as

fGMS​\(x\)=\\displaystyle f\_\{\\text\{GMS\}\}\(x\)=\{\}sin⁡\(2​π​x1\)\+sin⁡\(2​π​x2\)\\displaystyle\\sin\(2\\pi x\_\{1\}\)\+\\sin\(2\\pi x\_\{2\}\)\(8\)\+0\.7​exp⁡\(−∥x−c∥22​s2\)​sin⁡\(20​π​x1\)​cos⁡\(20​π​x2\),\\displaystyle\}\{\\displaystyle\+0\.7\\exp\\\!\\left\(\-\\frac\{\\lVert x\-c\\rVert^\{2\}\}\{2s^\{2\}\}\\right\)\\sin\(20\\pi x\_\{1\}\)\\cos\(20\\pi x\_\{2\}\),wherec=\(0\.7,0\.35\)c=\(0\.7,0\.35\)ands=0\.10s=0\.10\.

Table 4:Synthetic datasets used for Level Set Estimation

#### B\.2\.2Visualizations:

![Refer to caption](https://arxiv.org/html/2609.19891v1/figures/Gemini_Generated_Image_GMS.png)\(a\)Gaussian Modulated Sinusoid
![Refer to caption](https://arxiv.org/html/2609.19891v1/figures/Gemini_Generated_Image_Himmelblau.png)\(b\)Himmelblau

Figure 7:Synthetic benchmark functions used in our experiments\.
#### B\.2\.3Real\-world dataset

We use the Motorcycle dataset used in\[[31](https://arxiv.org/html/2609.19891#bib.bib31)\]\. This dataset gives a series of measurements of head acceleration in a simulated motorcycle accident, used to test crash helmets\.

Table 5:Motorcycle datasetEach data point in this dataset corresponds to the instantaneous accelerationa⁡\(t\)a\(t\)of the motorcycle helmet measured at a specific timettduring the crash event\.

### B\.3Bayesian Active Learning for Regression

Table 6:Details of the test functions \(simulators\) used in the experiments for Bayesian Active Learning\.

## Appendix CAblation Study

### C\.1Choice of Loss Function

Table 7:Final log simple regret afterT=100T=100BO iterations \(Lower is better\)\. Mean values are shown with standard deviation in parentheses\. Best performing method is inbold, second best isunderlined\.Table[7](https://arxiv.org/html/2609.19891#A3.T7)reports the final log simple regret afterT=100T=100BO iterations across synthetic benchmark functions\. We compare Zero, NLL, Brier, and their convex combination

Combo​\(α\)=α​ℓBrier\+\(1−α\)​ℓNLL,\\text\{Combo\}\(\\alpha\)=\\alpha\\,\\ell\_\{\\text\{Brier\}\}\+\(1\-\\alpha\)\\,\\ell\_\{\\text\{NLL\}\},whereα→0\\alpha\\to 0recovers NLL andα→1\\alpha\\to 1recovers Brier\. Asα\\alphavaries, the combined loss smoothly interpolates between the two losses\. Empirically,MixAcq withα=0\.5\\alpha=0\.5achieves the lowest average rank, indicating the best overall performance\.

### C\.2Hedge vs AdaHedge

Figure 8:Comparison of AdaHedge and Hedge within HACK\-MoG on the Branin\-2D benchmark\. Left: log simple regret over BO iterations\. Right: entropy of the kernel\-weight distribution, with lower entropy indicating greater concentration of weight on a smaller number of experts\. Lines show the mean across runs and shaded regions show the corresponding 95% confidence intervals\. AdaHedge concentrates its weights more rapidly while achieving comparable or faster regret reduction\.The figure compares AdaHedge and Hedge as online learning algorithms on the Branin 2D benchmark using HACK\-MoG with the same loss described in Section 5, showing their evolution in terms of log regret and entropy over iterations\. We note similar performance in terms of regret with AdaHedge being faster to reach the same regret value\. In the entropy plot, AdaHedge’s entropy drops more rapidly, reflecting faster concentration of weights on the better\-performing kernels, whereas Hedge maintains higher entropy for longer before gradually converging\. This demonstrates the advantage of AdaHedge over Hedge in sample efficient settings where the budget is constrained\.

### C\.3Empirical Evidence for Loss Gap

This ablation study empirically evaluates the loss gap assumptions underlying Lemmas[4\.2](https://arxiv.org/html/2609.19891#S4.Thmtheorem2)and[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3), which require a strictly positive loss difference between the best\-performing kernelm∗m^\{\*\}and competing kernels, either per iteration or in expectation\. Figure[9](https://arxiv.org/html/2609.19891#A3.F9)shows the empirical loss differenceℓm\(t\)−ℓm∗\(t\)\\ell\_\{m\}^\{\(t\)\}\-\\ell\_\{m^\{\*\}\}^\{\(t\)\}and its running average for the Bukin benchmark, where the Matérn1/21/2kernel emerges as the best kernel, under the combined NLL–Brier loss\.

Figure 9:Empirical loss gap for the Bukin 2D benchmark\. The left plot reports the per\-iteration loss difference, estimated using a Monte Carlo method, as defined in Lemma[4\.2](https://arxiv.org/html/2609.19891#S4.Thmtheorem2)under its stated assumptions, and the right panel reports the expected loss difference, as defined in Lemma[4\.3](https://arxiv.org/html/2609.19891#S4.Thmtheorem3)under its corresponding assumptions, between the best\-performing kernel \(Matérn 1/2\) and each competing kernel\. Results are shown for the combined NLL and Brier loss functionℓm\(t\)\\ell^\{\(t\)\}\_\{m\}\(Section[5\.1](https://arxiv.org/html/2609.19891#S5.SS1)\)\.
### C\.4Runtime Comparison

Table 8:Average computational time \(↓\\downarrow\) in seconds per iteration for different methods in Bayesian Optimization\.Table[8](https://arxiv.org/html/2609.19891#A3.T8)shows the time taken by the baselines defined in Table[2](https://arxiv.org/html/2609.19891#S5.T2), per\-iteration time averaged over 200 iterations\.