Bayesian Analysis of Combinatorial Gaussian Process Bandits
Authors: Jack Sandberg
Niklas Åkerblom
Morteza Haghir Chehreghani
Venue: ICLR 2025 Poster (2025)
Keywords: Multi-armed bandits
Combinatorial bandits
Contextual bandits
Gaussian processes
Energy-efficient navigation
Primary area: reinforcement learning
TL;DR: We present novel Bayesian regret bounds for GP-UCB, GP-BayesUCB and GP-TS for the combinatorial volatile Gaussian process semi-bandit problem and study the application of online energy-efficient navigation.

Abstract: We consider the combinatorial volatile Gaussian process (GP) semi-bandit problem. Each round, an agent is provided a set of available base arms and must select a subset of them to maximize the long-term cumulative reward. We study the Bayesian setting and provide novel Bayesian cumulative regret bounds for three GP-based algorithms: GP-UCB, GP-BayesUCB and GP-TS. Our bounds extend previous results for GP-UCB and GP-TS to the \emph{infinite}, \emph{volatile} and \emph{combinatorial} setting, and to the best of our knowledge, we provide the first regret bound for GP-BayesUCB. Volatile arms encompass other widely considered bandit problems such as contextual bandits.
Furthermore, we employ our framework to address the challenging real-world problem of online energy-efficient navigation, where we demonstrate its effectiveness compared to the alternatives.

Published as a conference paper at ICLR 2025
BAYESIAN ANALYSIS OF COMBINATORIAL GAUSSIAN PROCESS BANDITS
Jack Sandberg', Niklas Åkerblom' & Morteza Haghir Chehreghani'
Depaatment of Computer Science and Engineering, Chalmers University of Technology University of Gothenburg Volvo Car Corporation
{jack. sandberg, morteza. chehreghami hecaleeehslll.s..cc.mcomm ni niklas, akerblom@vol com
ABSTRACT
We consider the combinatorial volatile Gaussian process (GP) semi-bandit problem. Each round, an agent is provided set of available base arms and must select subset of them maximize the long-term cumulative reward. We study the Bayesian setting and provide novel Bayesian cumulative regret bounds for three GP-based algorithms: GP-UCB, GP- BC-BayesUCB and GP-TS. Our bounds extend previous results for GP-UCB and GP-TS to the infinite, volaile and combinatorial setting, and to the best of our knowledge, we provide the first regret bound for UC-BayesUUCB. Volatile arms encompass other widely considered bandit problems such as contextual bandits. Furthermore, we employ our framework to address the challenging real-world problem of online energy-efficien navigation, where demonstrate its effectiveness compared to the alternatives.
INTRODUCTION
The multi-armed bandit (MAB) problem is a classical problem in which an agent repeatedly has to choose between a number of available actions to perform (commonly called arms) and receives rewards depending regret over a certain time horizon, either finite or infinite, where regret is defined as the expected difference in reward between the agent's 's selected arm and the best arm (Robbins) 1985). The MAB problem has applications in healthcare, advertising, telecommunication and more Bouneffouf et al. 2020).
the selected action. The goal of the agent is minimize its expected cumulative
The combinatorial MAB Gaa et al. 2012 Cesa- Bitaa-iincchi & Lugosi 2012 Chen et al. 2013) considers problem where the agent must select subset of the available base arms, a super arm, in every round. The large number of super arms necessitates efficient exploration and may require solving difficult optimization problems.
The arms and enviromments in bandit applications often have some side-information (or context) that correlated with the reward, e.g., the titles or user specifications in a news recommendation problem. In the contextual MAB (Li et al., 2010; Krause & Ong] 2011 Agarwal et al., 2014 Zhou 2016). before selecting an arm, the agent provided a context vector (for the entire environment or each individual arm) that may (randomly) vary over time. By utilizing the information in the context the agent can learn the expected rewards more efficiently.
When the set of arms or contexts is continuous (infinite), it is necessary to impose smoothness assumptions on the expected reward since the agent can only explore finite number of arms. A common assumption is that the expected reward is a sample from Gaussian process (GP) over the arm or context set. For a sufficiently smooth GP, this ensures that arms which lie close in the arm space have similar expected rewards. Integrating GPs into bandits can yield higher sample efficiency and improved learning.
In Table I provide an overview and comparison of similar work in GP MABs. The seminal paper Srinivas et al, (2012) first introduced the GP-UCB algorithm, which combines upper confidence bounds (UCB) with GPs for MABs with finite or infinite arm sets. Srinivas et al. provided frequentist

---

Published as a conference paper at ICLR 2025
Table Comparison of similar work in GP MABs where T' the horizon, K the maximum super
arm size, and "rr (?rk) ) is the maximum information gain from T (T)) base arms. Note that Takeno
al. (2023 2024) obtain a regret bound of (vTTT) for IRGP-UCB, GP-TS and PIMS in the finite setting.
Ours
Nika, 2022
Takeno, 2023; 2024
Kandasumy, 2018)
Russo, 2014
Srinivas, 2012
Infinite/Tinise Volatile/Static Commiinatorial
Infinite Volatiee
Infinite Volatile
Infinite
Infinite
Finite Volatile
Static X Bayesian
Static
Static
X
Aayysiin/Freguentie
Rayesian
Frequentist
Bayesian
Bayesian
Frequentist
GP-UCB
GP-TS
GP-BUCB
Regret
KV RVT To log
Tww T
VT log
log'
VT log'
VT log
regret bounds for GP-UCB on a MAB problem with compact (infinite) arm space. Later work by Russo & Roy| 2014) provided Bayesian regret bounds for GP-UCB and GP-TS, a similar algorithm based on Thompson sampling [Thompson 1933), in the finite-arm setting with volatile arms. Volatile arms (often called time-varying or sleeping arms) means that not all arms are available to the agent in every round. This is general formulation that encompasses other MAB extensions such as the contextual MAB.
For the infinite arm setting, Russo & Roy only hinted that the proof follows by discretization arguments. Using discretization, the recent work by Takeno et al. (2023 2024) derives Bayesian regret bounds for GP-UCB and GP-TS in the infinite arm setting but without volatile arms.
The combinatorial and contextual MAB with changing arm sets (C3-MAB) incorporates both extensions and has received much interest recently (Qin al., 2014,, Chen et al., 2018 Nika et al.) 2020: 2022 Elahi et al.] (023), with applications in online advertisement, epidemic control and base station assignment (Nuara et al. 2018 Lin & Bouneffouf] 2022, Shi et al.) (023). Recent work by Nika et al. (2022) considered the C3-MAB with base rewards sampled from GP. Nika ct al. 2022) provided high probability regret bounds for combinatorial variant of GP-UCB with an approximation oracle.
In this work, we present novel Bayesian regret bounds for both GP-UCB and GP-TS in the combina- torial volatile Gaussian process cemi-bandit problem that extend previous regret bounds for GP-UCB and GP-TS to the infinite, volatile and combinatorial setting. As discussed above, our results hold for the contextual setting is special case of the volatile setting. Additionally, we present Bayesian regret bound for a third bandit algorithm called GP-BayesUCB (GP-BUCB) which is based on the BAyesUCB algorithm of Kaufmann al. (2012). Whilst GP-BUCB was introduced by Nuara et al.) (2018) for a combinatorial bandit problem, to the best of our knowledge there are no regret bounds GP-BUCB even in the non-combinatorial setting. We demonstrate that the parametrization of GP-BUCB is more flexible than GP-UCB and is less prone to over-exploration whilst retaining theoretical guarantees.
Furthermore, we demonstrate the applicability of combinatorial and contextual GP bandits to large scale problems with experiments on an online energy-efficien, navigation problem for electric vehicles on real-world road networks. With the increasing emergence of electric vehicles, addressing this problem is crucial to mitigating the so-called range anxiety. Akerblom et al. (2023) introduced a combinatorial MAB framework using Bayesian inference to learn the energy consumption on each road segment. In this paper, we extend the framework of Akerblom et al. to a contextual setting and apply it to real-world road networks. The experimental results demonstrate that the contextual GP model achieves lower regret than the Bayesian inference model.
Our contributions can be summarized as follows.
We extend previous Bayesian regret bounds for GP-UCB and GP-TS to the infinite, volatile (previous results only held for finite volatile arms) and combinatorial setting.
To the best of our knowledge, we establish the first regret bound for UC-BBaysUUBB
We develop a combinatorial and contextual bandit framework for the important real-world application of online energy-efficient navigation.
2

---

Published as a conference paper at ICLR 2025
Algorithm Framework for combinatorial volatile semi-bandit problem
Require: Prior agent parameters Op. base arm set A, super arm set S, horizon T.
1: for < I,..., do
2: A,, S f- ObserveAvailableeArss44444
3:
U, f GerBasseArllnddcoss 0;-1)
4:
SeleccOpiiallSuerrAm(,,, Ut)
5:
r, < ObserveRewards (a:)
6: 0, UpdateParameters(ce rt, 0t-1)
2 SETUP AND ALGORIHTS
In this section, we formulate our bandit problem, introduce Gaussian process bandit algorithms, and define the information gain, a quantity that is essential for GP bandits.
2.1 PROBLEM FORMULATION
We begin by formulating the combinatorial volatile Gaussian process semi-bandit problem. Let A Rd denote the set of base arms in d-dimensional space and S = {aaa A} 24 denote the set of feasible super arms. Note that |A4 can either be finite or infinite, and 2 denotes the power of A. The expected reward for the base arms f'a) GP(p(a), k(aa, a²)) ) assumed to be sample from a Gaussian process with mean function ulaa) A - R and covariance function A [].
k(a, a()
At time f, possibly random and finite subset of base arms A, C A is available to the agent. In a combinatorial setting, the agent must select feasible subset of base arms, a super arm, a, E Sy where S, C 2 is the set of feasible and available super arms. To facilitate feasible combinatorial problem, the super arms have a maximum size K (Ja) S K Va Sz). The agent observes the rewards of the selected base arms (semi-bandit feedback) the base arm reward Tı,a = f(a) + εz,a is a sum of the expected reward and i.i.d. Gaussian noise with zero mean and variance 2². Motivated by the online energy- energy-efficient navigation problem in Section 4.1 the total reward is assumed to be additive, and the agent also observes this reward at time Rs Enen, Tt,a- The total number time steps, the horizon, is denoted by T'. Let Hf, denote the a; Fr Ar, S.) of past observations and the currently history (Ai,S1, Si, .......; :t, St-
{rr,ala E a where
available arms at time t.
In this work, we are interested minimizing the Bayesian cumulative regret which, with a horizon of T, is defined
BR BR(T) (T)
E
Σ f(a;) f(a.)) TE[T]
where T (1...., ...,..., aj arg max f(a) and f(a) = s(a). As discussed by Russo & Roy 2014), allowing stochastic arm sets permits us to consider broader sets of bandit problems, an example of particular interest to us will be contextual models. Even though A, is finite, note that the infinite case [A] is of great importance since it it is necessary for the context be a continuous random variable.
Algorithm provides a framework for the introduced bandit problem. In the framework, the agent parameters θ, are defined for a general agent and are not specified here. Similarly, U, denotes the set of base arm indices which could be upper confidence bounds posterior sample, depending the algorithm used.
2.2 BAYESIAN FRA MEWORK FOR COMBINATORIAL GAUSSIAN PROCESS BANDITS
Gaussian process (a) ~ (P(u(a), k(a, d')) is a collection of random variables such that for any subset (a1, {a....., aND C. A the vector f [f(a))...., (((1)) has multivariate Gaussian distribution.
'The restriction (Ael < prevents issues with limit points since the agent can only select the same base This limitation not necessary in non-combinatorial setting.
3

---

Published as a conference paper at ICLR 2025
We take Bayesian view of the combinatorial problem and consider (P k) as prior over the base arm rewards. GPs are very useful for defining and solving bandit problems, due to their probabilistic nature and the flexibility they provide through the design of suitable kernels.
Let N1-1 = E |a|| denote the total number of base arms selected up to time t - 1 and let 01,...., ,,,...., denote the arms selected before time 1. Additionally, let y E RR- denote the corresponding observed base arm rewards and μ = [u(ar) (a((:)::.,,,(,....)) p[aaN_.]] denote the corresponding prior expected base arm mean rewards. Then, for any E A, the posterior GP distribution is given by:
(r-i(a) p(a) + k(a) (K + 52 (y 14)
(2)
k=1(a, k(a, a k(a) T (K+ + 22) -(('),
(3)
where K (k(a,, a;)
i,j=1 M-11
N
is the covariance matrix of the previously selected arms and k(a)
= [R(a, a1)..... ,(a,,,,,,)) aN is the covariance between and the previously selected arms. Let Te-1 (a) and (a) denote the posterior standard deviation and variance respectively.
In 2012 Srinivas et al.] introduced the GP-UCB algorithm, which selects the next arm based on upper confidence bound. In combinatorial setting, the GP-UCB algorithm selects the super arm a, = arg aax Ut(a) where (z(a) = (a) + - Pt-1(a) = Eoga Pt-1 (a), (a) = Lnca (a) and Be a confidence parameter, typically of or- der Ollogt), t). Kaufmann al. (2012) introduced Bayes-UCB, which selects the with the largest (1 -quantile, where the quantile parameter т)t was of order O (1/1). Adapted to the combinatorial Gaussian process setting, we suggest the following selection rule for Bayes-UCB: a, arg maxaes, Eaca Q (1117t.4 (1- nt.NV (H--1(a), o2 ) where (p, A) denotes the p-quamtile of the distribution A. We refer to this adapted version as GP-BUCB. Note that for X = -N,,, the p- quantile is given by (p,,N(u, o²)) = ptooooo2000 erl (2p- 1) where erf erf-r(()))) (.) is the inverse of the er- ror function. Thus, GP- BUCB can be seen as a variant of GP-UCB where 3r = 2 (erf- (1 -2m)) GP-TS (Russo & Roy 2014 Chowdhury & Gopalan 2017) selects the next arm randomly by using posterior sampling. If fe(a) GP(Pt-
a sample from the posterior distribution. then, in the combinatorial setting, GP-TS selects the super arm a = arg max fc(a), where fa(a) Eaca f((a).
2.3 INFORMATION GAIN
The regret bounds of most GP bandit algorithms depend on parameter called the maximal infor- mation gain "T (Srinivas et al. 2012 Vakili et al., 2021). The maximal information gain (MIG) describes how the uncertainty of diminishes the best set of sampling points A, |a| < T grows in size T. The MIG is defined using the mutual information between the observations Ya at locations and expected reward function
TT
sup aCA.
T(ya: f),
(y (yylf)) and (.) denotes the entropy. Both the true value of yr and most upper bounds depend on the kernel function & defining the GP from which f is sampled from. Srinivas et al. (2012) initially introduced bounds 7r for common kernels, such as the Matérn and
where / (yyai f)
RBF kernels. For the RBF kernel, Srinivas et al. showed that ?r = O (log"1((T)) (T)). Later, Vakili ct al. 2021) presented a general method of bounding "T that utilizes the eigendecay of the kernel K. Using this method, Vakili et al. obtained improved bounds on the Matérn kernel with smoothness
24 parameter v: O Tauta 20 (T)). To apply these bounds, we require that A is compact.
3 REGRET ANALYSIS
Whilst the work of Chen et al. (2013) can be seen as a standard combinatorial framework, we adopt the framework of (Russo& & Roy 2014) since it is better suited for Bayesian bandits with volatile and
4

---

Published as a conference paper at ICLR 2025
infinite arms. Russo & Roy (2014) first provided Bayesian regret bound for GP-UCB in volatile (but non-combinatorial setting with a finite arm set. Recently, Takeno et al. (2023) presented explicit proof for the Bayesian regret of GP-UCB with compact and static arm set. In this section, present novel Bayesian regret bounds for both GP-UCB and GP-TS in a combinatorial and volatile setting (including the contextual setting). Additionally, to the best of our knowledge, we present the first Bayesian regret bound for GP-BayesUCCB Similar to previous work, we first consider the finite arm case, | < 00, and then consider the infinite case, |A|] oc, by extending the finite arm results via a discretization.
3.1 FINITE CASE
We start by highlighting our technical contributions for GP-BUCB Following the proof framework and E[Ur(a;) f(a)) For GP-BUCB, establishing an upper bound for the second term requires us to work around the non-elementary function erf" (u). Using Thm. 2 of Chang et al. 2011). we find that erf (uu) >
of Russo & Roy (2014), we seek to bound two terms: [[f( Uz(a;]]
V-w-1 log( w) for w > 1 and 0 < 0 < /2e/TV/ tighter for larger values of the parameter (Chang et al. 2011), thus we set to its maximum value whilst w is kept as a tunable parameter. Recall that the quantile parameter 7/2 determines how quickly the confidence bound grows and the order & > 0 (s.t. T = O( {)) is another tunable parameter. As shown in the lemma below, these parameters influence the bound we get.
1/w, see Lemma A.13 The bound
Lemma 3.1. Let Cs (VTw/ V 2e(w - 1)
1/W
then GP-BUCB with confidence parameter
3. (erf-(() 2n1)) and ni
1/2" 21A1-
E 0, w >
w
TI
ff//w < 1,
B[S(a]) - U.(a,)) S Cu EE(T]
logT
if 1,
ift/w >
Kaufmann et al. (2012) studied (non-GP and non-combinatorial) Bayes- UCB for Bernuulli bandit with 5 = whilst our analysis permit any & > 0. Lemma 3.1 shows that the ratio E/w determines the bound for the right term is sublinear, logarithmic or constant w.r.t 7 for GP-BUCB. The equivalent bounds for GP-UCB and GP-TS are both constant if B, 2 log (IA]t2) / see Lemma A.2 thus we assume E/w
to simplify the regret bounds.
Srinivas et al. (2012) showed, a non-combinatorial setting, that the sum of posterior variances can be bounded by the information gain between the sampled points and the expected reward function f. Lemma in Nika et al. (2022) (adopted to our setting in Lemma A.11) generalizes this result to combinatorial setting. The result depends on the maximum eigenvalue of all possible posterior covariance matrices of size at most K, which we denote as Ax.
Then, we present the main theorems for GP-UCB, GP-BUCB and GP-TS in the finite case, Appendix A. for the proofs.
Theorem 3.2 (Finite regret bounds). Lei CK == 2(Xxx +s²). When A is finite, the Bayesian regret of
(i) GP-UCB with 8, = =2log(1A|1 /2x) is bounded as BR(T) S _² &VCKTKBTTKK
(i) GP-BUCB with 3r = 2 (erlf 22)))² for vi
/25" "A & w > 1 is bounded as
(R( & VCRTKBITTK + Cs. & &-w where C. = (Viw// v /26lw - 1)) 1/4
(ii) GP-TS is bounded as BR(T) S oJ + +2VCRTKBBTT where 3r 2 log (1A|11/ /TT2T.
For all three algorithms (if E/w > 1 for GP-BUCB), we find that BR(T) O1 T T STYTK) where YrK is the MIG from TK base arms. Using the bounds of ?7 from Section 2.3 we get that the regret is sublinear in T for both the RBF and Matérn kernels. The closest work, by Nika et al. 2022 obtains a frequentist regret bound of the same order. Nika et al. 2022) noted that X = O(K) which gives linear dependence K in the worst case
(7han 2005). For linear kernel, the setting of
5

---

Published as a conference paper at ICLR 2025
Wen al. 2015) is similar to our setting and they obtain O(K /log K) and O(K) dependencies on K whereas our dependency is OKK vlog For combinatorial semi- bandits with linear reward functions (but independent arms), Merlis & Mannor (2020) obtain a 9 V K/ log K) lower bound which would suggest gap of vK log K for the linear kernel. When K = 1, our results match the non-combinatorial results for GP-UCB. However, the improved random GP-UCB (IRGP-UCB) and GP-TS of Takeno et al. (2023 2024 has a Bayesian regret of (vTTTr in the finite case, suggesting that a vBr = O /log 7) improvement is possible. To our knowledge, there are no known lower bounds for the Bayesian regret of GP-bandit algorithms in general. However, for the SE-kernel the non- con-Bayeiian regret satisfies Q2( (Tlog T)d/2) (Scarlett ( 20 Cai & Scarlett (2021)). Taken at face value, this would imply that our bounds are tight up to logarithmic factors of T.
3.2 INFINITE CASE
The infinite case, |A| oo, is an important generalization since many decision problems have continuum of actions to select from. Based on our framing of contextual MABs as a subset of volatile MAB, an infinite This setting is often analytically more difficult and requires the following additional assumptions:
permits contexts with support infinite domains such continuous time.
Assumption 3.3 (Regularity assumptions). Assume A C [0, CiJ is a compact and convex set for some C₁ O. Furthermore, assume that μ and k are both L-Lipschitz on A and A A, respectively, for some L >> 0. In addition, for f ~ GP( k) assume that there exists constants C2, C3 > 0 such that:
0ʃ dali)
|
12 (-03)
sup aEA
C2
(5)
for j E d} and 1 > where al5) denotes the j-th element of a.
Whilst the high probability bound on the derivatives of the sample paths is a common assumption in the literature (Srinivas et al. 2012 Kandasamy et al. 2018 Takeno et al. 2023), we additionally require that both μ and are Lipschitz but this is not particularly restrictive, see Remark A.6
Following Srinivas al. (2012), proofs for the compact case tend to use discretization Dj A where each dimension is divided into T; points such that [Del = गf. Let [a]p, denote the nearest A. Due the assumption of
point in D, for a E A and similarly let (a]p, = [ a E a} for volatile arms, we require the following finer discretization (as compared to Takeno et al. 2023): :
Assumption 3.4 (Discretization size). Let Tr denote the number of discretization points per dimension and assume that
Ts 2 21 KLdCi( + +)
(6a)
T// 2 K2
(6b)
Tf/B, 2 81 1- 132
(6c)
2 K2C, Vlg( (22)) + /
(6d)
where the constants C1, C2, C3 and L are given by Assumption 3.3 whilst the constants d, K and are defined by the bandil problem (Section 2.7)
We note that Eq. (c)) is equivalent to the discretization size used by Takeno et al. (2033) with an extra factor of K to account for the combinatorial setting whilst we introduce Eqs. (6a) to (6c) to bound Ur([a] [[a]p,)
(a). A key step to establish the regret bound of GP-UCB by Takeno et al. (2023) is to use the fact (for that setting) that a, maximizes the upper confidence bound (a) and thus Uz ((aj),)) - Ug (a:) S O. Since we consider a setting with volatile arms, [aj]o, is not necessarily a feasible super arm and our technical contribution in the infinite setting is analysis of the discretization error of (a((p),,) - U,(a).
Lemma 3.5. (a) = p-1 (a) / Vio..11 (a)), Assumption 3.3 and Tr and B, satisfy Eqs. 6a)
to (6c) in Assumption 3.4 then for any sequence of super arms a E S. 2
72
Σ [
(U.((())))))) - -Ur(a.)
6

---

Published as a conference paper at ICLR 2025
To bound the difference in posterior mean, P4-1 - 1 Cholesky decompose K
<²1= LL' and note that (y -4) has chi distribution with at most TK degrees of freedom. The difference in posterior standard deviation, ((a),))) 0z (a), is bounded by using that k is Lipschitz, Assumption 3.4 and other smaller steps.
Next, we present our regret bounds for GP-UCB, GP-BUCB and GP-TS in the infinite setting:
Theorem 3.6 (Infinite regret bounds). If Asssupttion 3.3 holds and satisfies Assumption 3.4 then the Bayesian regret of
(i) GP-UCB with 3r - log /2TT/ is bounded as BR(T) S o VCKTKBBTT
(ii) GP-BUCB with Be 2 2er 2n)))² for t = (2T)w/2/ (2TQ > > is bounded BR(T)
I
x²
3 + VCRTKKTTTK + Cw E-w where Cu
(VTw/ feel://eewww)) 1/4
(iii) GP-TS is bounded as BR(T) S 2n +2
3
The proof's are presented in Appendix into multiple terms which are either bounded by the finite case or by using results such as Lemma 3.5 Because of the stochastic arm selection, the regret for GP-TS must be decomposed into more terms compared to GP-UCB, which increases the constants in the bound. As in the finite case, we get that BR(Z) = O(yy X3 TK STYTK) for all three algorithms which matches the non-combinatorial result of Takeno al. (023 for K
Similar Takeno al, (023). the regret decomposed
EXPERIMENTS
In this section, consider the important real-world application of online energy-efficient navigation for electric vehicles and formulate it as a combinatorial and contextual bandit problem. Previous work by Akerblom al. (2023) introduced framework based Bayesian inference address the online navigation problem when no contextual information is available. Bayesian combinatorial bandits allow us to combine imperfect initial estimates with exploration find efficient routes. In this work, we extend the framework to incorporate contextual information, enabling us to make use of correlations for even faster learning.
4.1 BANDIT FORMULATION OF ONLINE ENERGY EFFICIENT NAVIGATION PROBLEM
The online energy- navigation problem Consider directed graph G(V, E) where the vertices denote intersections of road segments and the edges e = (u1, U2) E E denote the road segment from intersection i1 intersection U2- Additionally, let L(g) G(E, C2) denote the directed line graph of G where the set of connections C, S. {(e1, e2),,e))e1110 = (u. v) E E, C2 = (v, w) E E} determine which turns legal in the road network time t. Assume that we are given a start vertex 4 E V and a goal vertex un E V. Let P, denote the set of simple feasible paths from to un at time t. A path p (u1, u.,..., un is legal if all the connections are legal, and p simple if every vertex is visited at most once. At each time step t, we observe the set of available paths Pe and context vector 2t,e E Idd for each edge E The context Zt,e can include static features, such as the length of the road segment, and time-narying features, such as the congestion level. Based on the available connections and the context vector, we select a path Pt E P. and observe the energy consumption associated with each edge in the path (negated reward): R, Eeep, Tr.e. The goal of online energy energy-efficient navigation is to minimize the total energy consumed over a horizon T. Note that the base arm set A, corresponds to all edge-context tuples at.e) and that the base arm space defined as A E x X' where X' C [0, C d a compact and convex set for some C1 > 0. The super arm set S, corresponds to sequences of edge-context tuples that form paths in Pr-
Shortest paths with rectified Gaussians Using regenerative braking, the energy consumption of an electric vehicle can be negative along individual road segments which presents challenges when we wish to find the most inergy-efficient path. The most common shortest path algorithm, Dijkstra's 's algorithm (Dijkstra 1959). does not permit negative edge weights. Whilst alternative shortest path
7

---

Published as a conference paper at ICLR 2025
algorithms, such as Bellman-For (Shimbel, 1954: Bellman 1958 Ford 1956), allow negative edge weights, they are significantly slower and do not return a path the graph has a reachable negative cycle. To avoid the complexity associated with negative weights, we use the rectified normal distribution to get non-negative energy consumption estimates Uze as input for Dijkstra's 's algorithm. Upper confidence bound methods output op- timistic estimates Pe E IR whereas Thomp- son sampling outputs posterior estimates He E I by sampling from the posterior Mi 1,-,))) To ensure non-negative weights, the edge weight Ut, is set to B[ze] where z. is distributed as the rectified Gaus- sian ( _,,- A random variable Y= max(0, X) is said to have rectified
Algorithm 2 Compute Rectified Indices
procedure GETBASEARMINDICESSS 0,-1
1: for each edge A₁ do
2:
Me t M1-1e VBIoi-1.
> UCB
2:
Be + W
> BUCB
Gaussian distribution (R,(,, if X o²), In Algorithm 2 we show how to integrate UCB, BUCB and Thompson sam- pling with rectification within the framework of Algorithm | The notation 14-1,e and of- refer respectively to the posterior mean and variance of the expected energy consumption for edge whilst S- refers to the variance of the noise. Since the number of edges |ε] may be large, each edge is sampled independently in TS, as by NNuaa et (2018). Note that Algorithm@deccupp the probabilistic regression model and Thompson sampling. In the next sections, we describe two probabilistic regression models for energy-efficient navigation.
2:
t Sample from N N 1,, of-1,)
D TS
3: U t Bize] where ze (Mes S.
4: return U,
GP regression for energy-efficient navigation To our knowledge, this study is the first com- binatorial Gaussian process bandit solution for online energy-efficient navigation. The energy consumption depends on both the structure of the graph and the provided context. We use the graph Matérn kernel ka E x E + R from Borovitskiy et al. (202T) to encode the structure of the line graph L into the GP and an ordi- nary 5/2 5/2-Matérn kernel ky : X' x X + IR to encode the dependence kernels are combined KG-f+s = kg ky + kyy where the two feature kernels ky and Ky use separate sets of lengthscale and outputscale pa- rameters. The cubic cost of exact GPs prohibits their application to large datasets. The sparse variational Gaussian processes (SVGP) (Titsias) 2009 Hensman et al., 2013) approximate the posterior distribution using set of inducing points Z, ...,..., 3M} where z; E A and M is sig- nificantly smaller than the number of datapoints. By defining a prior distribution q(u,) = (m S,) for the inducing variables u, an approximate GP posterior can be obtained such that the complexity to perform N predictions is O(M2N), i.e. linear w.r.t. N. The variational paramaters (m,, S,) are optimized by minimizing the evidence lower bound (ELBO) by performing stochastic (natural) gradient descent steps using batch size B. Since the inducing points z; lie in a mixed discrete and continuous space (A = & x X for X' C [0, C,J²), we heuristically set 2; equal to the edge-context tuple of the i-th most visited edge at the start of the SVGP optimization. Then, the continuous dimen- sions of 24 are optimized together with (m,,S) St) using natural gradient descent (NGD) (Salimbeni et al. 2018). The procedure is described in Algorithm Further details of the kernels and parameter values are provided in Appendices B. and B.3
Algorithm 3 SVGP Optimization Procedure
procedure UPDATEPARAMETERS(Ia rt, 0.-1)
1: Add ar; re history.
2: Set inducing points Z, to top M most visited edges.
3: for i f1...., G} do
4: ā. <- Subsample batch of size from history.
the context. The two
5: Compute batch ELBO.
6: Optimize variational parameters with NGD.
7:
Compute μt: oe, Sr using the optimized GP.
8: return μa, ot, Sa and the optimized variational parameters.
Bayesian inference for energy-efficient navigation Ákerblom et al. (023) introduced a framework for energy- mefgy-efficient navigation using Bayesian inference to learn the distribution of the energy consumption in each road segment. The key assumption is that the energy consumption of an electric vehicle driving along a road segment is stochastic and follows Gaussian distribution with unknown
8

---

Published as a conference paper at ICLR 2025
mean and known variance. Additionally, it is assumed that the energy consumption along different edges independent. Using a Gaussian prior, the posterior distribution for edge e is computed using standard conjugate update rules.
Real-world road networks In our experi-
ments we use the road networks of Luxembourg and Monaco (Codeca et al., [2017] Codeca &
Härri 2018 based on data by OpenStreetMap
contributors 2017 Elevation data (Administra- tion la navigation aérienne 2018) added to the network using QGIS and the netconvert tool from SUMO. In Fig. the two road networks visualized along with two evaluation routes (A and B) per network. The evaluation routes span multiple regions of the network, allowing for many alternative paths. The context for each road segment consists of three fixed scalar prop- erties: the length, the speed limit and the incline. Each property standardized have unit-variance computed by a deterministic model that assumes that the vehicle drives along an edge E &, with length le and inclination Ogg at constant speed Ue. The expended energy is then
Figure 1: Road networks of Luxembourg (left) and
Monaco (right) with evaluation routes A and B highlighted in blue and red.
The prior expected energy consumption is
theeedeed
Ed (mgle san( mgC,le cos(a.) + O.5C, (2) /3600 (8)
The deterministic energy consumption Ee in Eq. given in Watt-hours and depends on the m, rolling resistance C,, front surface
following vehicle-specific parameters: drag coefficient Ca and powertrain efficiency 17. The gravitational acceleration g and air density
A, air
also determine Edat The parameter values are specified in Table 2 in Appendix B.3 Let E
EeEE Eeet and o Te En E denote the mean and variance of the deterministic
energy consumption. The expected energy consumption is sampled from GP kG.f+f) where the outputscale kG-f+s (i.e. the variance of) is set to 0.25 The noise variance <² is set to for all edges and the kernel lengthscales are set to See Appendix for further details.
0.1 0. det
4.2 RESULTS
Here, demonstrate experimental studies in different settings. We begin by comparing GP algorithms to Bayesian inference methods, then we compare the parametrizations of GP-UCB and GP-BUCB. Finally, study the impact of the kernel lengthscale. Visualizations of the exploration are provided in Appendix C.2
Investigation of different bandit algorithms our first experiment, we compare the three algorithms GP-UCB, GP-BUCB and GP-TS. We use the Bayesian inference (BI) method of Akerblom et al. 2023) with UCB, BUCB and TS as baselines. For UCB and BUCB (GP and BI), we use the 3 parametrization given by Theorem 3.2 with
1, E 1. The six methods each on the four routes in the Luxembourg and Monaco networks with a horizon of T' 500. The cumulative regret is shown in Fig. 2 The results show that the TS-based methods have significantly lower regret than both UCB and BUCB. Similarly, the GP-based methods generally have lower regret than their BI-based counterparts. Thereby, GP-TS yields the best results in terms of minimizing cumulative regret. Finally, we observe that GP-BUCB has lower regret than GP-UCB. In the next experiment, we investigate how the parametrization of these two algoritms affects the results.
evaluated 5 times
BUCB parametrization As discussed in Section 2.2 GP-UCB and GP-BUCB differ mainly in
their parametrization of the confidence parameter 3.. The confidence parameter determines the balance between exploration and exploitation. It is known that theoretical results tend to provide 3e values that overexplore (Russo & Roy 2014). Using the parameters of B, for GP-BUCB (w and {), tune GP-BUCB towards more exploitation whilst retaining theoretical guarantees. We compare two theoretically valid choices of parametrizations for BP-BUBB (w = 1, E = 1 and g 0.5) against two parametrizations of GC-UCB where the first is theoretically valid and the

---

Published as a conference paper at ICLR 2025
Cum.. regret (kWh]
10
Lux. A
75
Lux. B
75
Mon. A
Mon. B
50
20
25
25
0
200
200
400
200
GP-UCB
BI-UCB
GP-BUCB
BI-BUCB
GP-TS
BI-TS
Figure 2: Cumulative regret for UCB, BUCB and TS using GP and Bayesian inference (BI) methods.
The lines and regions correspond to the mean and +1 standard error.
40
Lux. A
50
Lux. B
Cumulotive regret [kWh]
A 5160
20
25
20
0-
40
Mon.
Mon.
40
[A
3474
25
20
20
0
200
GP-UCB: 1. -- GP-UCB: 0.5
GP-BUCB: =,
GP-BUCB: 1,6 0.5
Figure 3: Cumulative regret of GP-UCB and GP-BUCB (left and middle column) for different parametrizations of Be (right column).
second has scaled 3t by 0.5. The four parametrizations are evaluated 5 times each on the four routes in the Luxembourg and Monaco networks with horizon of T = 500. The cumulative regret and the 3 values are shown Fig. The theoretically valid 3, values for GP-BUCB are smaller than for GP-UCB. By lowering & from to 0.5, the quantile parameter goes from (t )) to O(t-0.5) and using w 1 the theoretial cumulative regret remains ((VT) The experimental results indicate that the parametrization with lower 3r generally has lower cumulative regret. Using GP-BUCB, we gain more control of 3r without sacrificing the theoretical guarantees.
Impact of lengthscale Finally. we investigate varying the kernel lengthscale to ensure our results are consistent and stable. large lengthscale increases the correlation between edges, which should lower the regret of the GP-methods. Whilst lower lengthscale decreases the correlation which should increase the regret of the GP-methods. We evaluate GP-BUCB and GP-TS against BI-BUCB and BI-TS with the kernel lengthscale varying between 0.1 and 2.0. Each combination of lengthscale and bandit-method cumulative regret / = 500 for the different lengthscales is shown in Figs. and in Appendix C.I For GP-based methods, increasing the lengthscale increases the cumulative regret overall but for Bl-based methods, there is no discernale pattern.
evaluated times on four routes with a horizon T 500. The final
CONCLUSION
We presented novel Bayesian regret bounds for the combinatorial volatile Gaussian process semi- bandit for three GP-based bandit algorithms: GP-UCB, GP-BayesUCB and GP-TS. Additionally, we experimentally evaluated our contextual combinatorial GP method on the online energy-efficient navigation problem on real-world networks.
Technically, one must & 0.5 5 and w > + 5 for some 8 0. However, we could choose 8 to be small enough such that GP-BUCB would select the exact routes in all experiments.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The work of Jack Sandberg and Morteza Haghir Chehreghani was partially supported by the Wal- lenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. The work Niklas Akerblom was partially funded by the Strategic Vehicle Research and Innovation Programme (FFI) of Sweden, through the project EENE (reference number: 2018-01937). The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725. Map data from Openstreetmap and available from www www.ppeseeeeepp.org/oooooooeoooe
REFERENCES
Administration de la navigation aérienne. Digital Terrain Model (high DEM resolution). 2018.
URL https://data. ptt.:::://..a..u.lic....c...
tirital-terrain-motte -en-a--------------------------- rew.mn-rrslliiiiooooooom
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits. In Proceedings of the 31 International Conference Machine Learning, pp. 1638-1646. PMLR, June 2014.
Niklas Åkerblom, Yuxin Chen, and Morteza Haghir Chehreghani. Online learning of energy con- sumption for navigation of electric vehicles. Artificial Intelligence. 317:103879, April 2023.
Richard Bellman. On routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958.
Viacheslav Borovitskiy, Iskander Azangulov, Alexander Terenin, Peter Mostowsky, Mare Deisenroth, and Nicolas Durrande. Matérn Gaussian Processes on Graphs. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. April 2021.
PMLR,
Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey on Applications of Multi-Armed and Contextual Bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), 2020. doi: 10.1 LLL109//EEC48600222001111111
Xu Cai and Jonathan Scarlett. On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization. In Proceedings of the 38th International Conference Machine Learning, pp. 1216-1226. PMLR, July 2021.
Nicolò Desa-Bianchhi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 4045):24 September 2012.
Scok-Ho Chang, Pamela C. Cosman, and Laurence B. Milstein. Chernoff-Type Bounds for the Gaussian Error Function. IEEE Transactions on Communications, 59(1 (0:11))9992244 2011.
Lixing Chen, Jie Xu, and Zhuo Lu. Contextual Combinatorial Multi-armed Bandits with Volatile Arms and Submodular Reward. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial Multi-Armed Bandit: General Framework and Applications. In Proceedings of the 30th International Conference on Machine Learning, pp- 151-159, PMLR, February 2013. ISSN: 1938-7228.
Sayak Ray Chowdhury and Aditya Gopalan. On Kernelized Multi-armed Bandits. In Proceedings of the 34th International Conference Machine Learning, pp. 844 853. PMLR, July 2017.
Lara Codeca and Jérôme Härri. Monaco SUMO Traffic (MoST) Scenario: A 3D Mobility Scenario for Cooperative ITS. In SUMO 2018. SUMO User Conference, Simulating Autonomous and Intermodal Transport Systems, May 14-16, 2018, Berlin, Germany, Berlin, GERMANY, May 2018.
11

---

Published as a conference paper at ICLR 2025
Lara Codeca, Raphael Frank, Sebastien Faye, and Thomas Engel. Luxembourg SUMO Traffic (LuST)
Scenario: Traffic Demand Evaluation. IEEE Intelligent Transportation Systems Magazine, 9(2): 52 52-63, 2017.
E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, 1: 269-271, 1959.
Sepehr Elahi, Baran Atalar, Sevda Öugüt, and Cem Tekin. Contextual Combinatorial Multi-output GP Bandits with Group Constraints. Transactions Machine Learning Research, January 2023.
L. R. Ford. Network Flow Theory. Technical report, RAND Corporation, January 1956.
Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial Network Optimization With Unknown Variables: Multi-Armed Bandits With Linear Rewards and Individual Observations. JEEE/ACM Transactions on Networking, 2065):166-14788 October 2012.
Jacob R Gardner, Geoff Pleiss, David Bindel, Kilian Q Weinberger, and Andrew Gordon Wilson. GPyTorrc: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration, In Advances in Neural Information Processing Systems, 2018.
Subhashis Ghosal and Anindya Roy. Posterior consistency of Gaussian process prior for nonparamet- ric binary regression. The Annals of Statistics, 34(5), October 2006.
James Hensman, Nicolò Fusi, and Neil D. Lawrence. Gaussian Processes for Big Data. In Proceedings of the Tienty-Ninth Conference on Uncertainty in Artificial Intelligence, UAI'13, pp. 282-290,, Arlington, Virginia, USA, 2013, AUAI Press.
Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabas Poczos. Parallelised Bayesian Optimisation via Thompson Sampling. In Proceedings of the Twenty- Frenty-First International Conference Artificial Intelligence and Statistics, pp. 133 142. PMLR, March 2018.
Emilie Kaufmann, Olivier Cappe, and Aurelien Garivier. On Bayesian Upper Confidence Bounds for Bandit Problems. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, pp. 592-600. PMLR, March 2012.
Andreas Krause and Cheng Ong. Contextual Gaussian Process Bandit Optimization. In Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670. Association for Computing Machinery, April 2010.
caatexttal-badiit approach to
Baihan Lin and Djallel Bouneffouf. Optimal Epidemic Control as a Contextual Combinatorial Bandit with Budget. In 2022 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), pp. 1-8, July 2022.
Pablo Alvarez Lopez, Michael Behrisch, Laura Bieker-Waa Jakob Erdmann, Yun-Pang Flötteröd, Robert Hilbrich, Leonhard Lücken, Johannes Rummel, Peter Wagner, and Evamarie Wiessner. Microscopic Traffic Simulation using SUMO. In 2018 21 International Conference on Intelligent Transportation Systems (ITSC), pp. 2552, November 2018
Nadav Merlis and Shie Mannor. Tight Lower Bounds for Combinatorial Multi-Armed Bandits. In Proceedings of Thirty Third Conference on Learning Theory, pp. 2830 2850.2287.22 PMLR, 2020. URL
htttp:://xxoceddnng: mlr www..ppeess/ee wwwp:///meerrree htmll..maa.mllllm.....mmmmmmmm1.
Andi Nika, Sepehr Elahi, and Cem Tekin. Contextual Combinatorial Volatile Multi-armed Bandit with Adaptive Discretization. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pp. 1486-1490 PMLR, June 2020.
Andi Nika, Sepehr Elahi, and Cem Tekin. Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes, October 2022. arXiv:21 10.002288.
Alessandro Nuara, Francesco Trovò, Nicola Gatti, and Marcello Restelli. A Combinatorial Bandit Algorithm for the Online Joint Bid/Budget Optimization of Pay-per- per-Click Advertising Campaigns. Proceedings of the AAAI Conference Artificial Intelligence, 32(1), April 2018.
12

---

Published as a conference paper at ICLR 2025
OpenStreetMap contributors. Planet dump retrieved from https://planet.osm.org openstreetmay org 2017.
https:/ WwW
K. B. Petersen and M. S. Pedersen. The Matrix Cookbook, November 2012. URL http://www/
compute.dtu. dk pubdo pubs//ubss// /aaiis/3224 32744 full. html
QGIS Development Team. QGIS Geographic Information System. QGIS Association, 2023. URL
Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual Combinatorial Bandit and its Application on Diversified Online Recommendation. In Proceedings of the 2014 SIAM International Conference on Data Mining (SDM), Proceedings, pp. 461-469 Society for Industrial and Applied Mathematics, April 2014.
Herbert Robbins. Some aspects of the sequential design of experiments. Herbert Robbins Selected Papers, pp. 177, 1985.
Daniel Russo and Benjamin Van Roy. Learning to Optimize via Posterior Sampling. Mathematics of Operations Research, 39(4):1221-1243, 2014.
Hugh Salimbeni, Stefanos Eleftheriadis, and James Hensman. Natural Gradients in Practice: Non- Conjugate Variational Inference in Gaussian Process Models. In Amos Storkey and Fernando Perez- Cruz (eds.), Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 689-697. PMLR. April 2018.
Jonathan Scarlett. Tight Regret Bounds for Bayesian Optimization in One Dimension. In Proceedings of the 35th International Conference on Machine Learning, pp. 4500-4508. PMLR, July 2018.
Fang Shi, Weiwei Lin, Lisheng Fan, Xiazhi Lai, and Xiumin Wang. Efficient Client Selection Based on Contextual Combinatorial Multi-Arm Bandits. IEEE Transactions on Wireless Communications, 22(8):5265-522) 5277, August 2023.
Alfonso Shimbel. Structure in communication nets. Proceedings of the Symposium Information Networks, pp. 119-203, 1954.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Information-Theoree Regret Bounds for Gaussian Process Optimization in the Bandit Setting. IEEE Transactions Information Theory, 58(5):3250-33 -3650,,3,,,-00 May 2012.
Michael L. Stein. Interpolation of Spatial Data. Springer Series NY, 1999.
in Statistics. Springer, New York,
Shion Takeno. Yu Inatsu, and Masayuki Karasuyama. Randomized Gaussian Process Upper Con- fidence Bound with Tighter Bayesian Regret Bounds In Proceedings of the 40th International Conference on Machine Learning, pp. 33490-33511 PMLR, July 2023.
Shion Takeno, Yu Inatsu, Masayuki Karasuyama, and Ichiro Takeuchi. Posterior Sampling Sampling-Based Based Bayesian Optimization with Tighter Bayesian Regret Bounds. Proceedings of the 41st Interna- tional Conference on Machine Learning. PMLR, 2024.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-29)) December 1933.
Michalis Titsias. Variational Learning of Inducing Variables in Sparse Gaussian Processes. In Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, pp. 567-574. PMLR, April 2009.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On Information Gain and Regret Bounds in Gaussian Process Bandits. In Proceedings The 24th International Conference on Artificial Intelligence and Statistics, pp. 22-90. PMLR, March 2021.
Zheng Wen, Branislav Kveton, and Azin Ashkan. Efficient Learning in Large-Scake Scale Combinatorial Aani-Bandits. In Proceedings of the 32nd International Conference on Machine Learning, pp. 1113-1122. PMLR, June 2015.
13

---

Published as a conference paper at ICLR 2025
Xingzhi Zhan. Extremal Eigenvalues of Real Symmetric Matrices with Entries in an Interval. SIAM Journal on Matrix Analysis and Applications, 27 860, 2005. ISSN 0895-4798. doi: 10.1
Li Zhou, A Survey on Contextual Multi-armed Bandits, February 2016. arXiv: 100.003366.
14

---

Published as a conference paper at ICLR 2025
A PROOFS
A.1 FINITE CASE
In this section, we state and prove the regret bounds in the finite case for the three bandit algorithms GP-UCB, GP-BUCB and GP-TS. To begin, we establish lemmas that demonstrate the general procedure for the proofs and later we combine the lemmas to get the desired regret bounds.
In the following lemma, the Bayesian regret is separated into two terms.
Lemma A.1. For GP-TS or any GP-UCB method the following upper bound on the Bayesian regret holds (with equality for GP-TS):
(R(T) -
Σ :E[T]
B[f(a)) U,(a,) + E(U,(a,) - f(ar))
(9)
Proof. The proof follows the procedure of Prop. 1 by Russo & Roy (2014) for GP-TS and Thm. B.1. by Takeno et al. (2023) for GP-UCB. For GP-TS,
BR(T)
Σ (E[T]
E [f(a,) - f(ar)]
(10)
Σ tE[T]
Eu, E. [f(at) - U.(aat + Uz(aa) - f(a:)) H.]l
(aj)H, d a H:)
(11)
Σ
B[S(a,) Ut(a;)] +
Σ
[a(U((a)) - [(a)))
(12)
KE[T]
(E[7]
Similarly, for any GP-UCB method,
BR(T) = Σ
E [f(at) - f(ai))
(13)
:E(T]
Σ E [f((at) U.(aa) + U.(at) U,(a:) + U,(a)) - s(a:)
(14)
:E(T)
<
Σ
E (ʃ(a)) U.(a,) + U,(a)) - s(a))
(15)
(E(T]
where the final step uses that U,(a?) U.(a:) < 0 since arg max U.(a).
Whilst Lemma A. applies to all the considered bandit algorithms, the terms in the decomposition requires knowing the specific bandit algorithm. Bounding the left term requires knowledge of the confidence parameter 3. Therefore we present lemma that applies GP-UCB and GP-TS, and another lemma that applies to GP-BUCB.
Lemma A.2. If |A| < 0o, then
Σ E[f(a;) - (,(a))) < 6 LE|T
(16)
holds for GP-UCB and GP-TS with 3 = 2og (1A112/ /2T)
15

---

Published as a conference paper at ICLR 2025
Proof. The proof closely follows the proof of Thm. B.1 by Takeno et al. 2023 Let R1
EiE( [[f( Ua(a]), then
R1
Ed,
Be [f(aī) HH,
(17)
1E[2]
Σ
EH,
E, Σ f(a) U.(a) H4
(18)
1E[2]
.Ea;
EH E,
Σ (f(a) Uc(a))+
He
xx)
(19)
[E[]]
oEar
Σ RH
Σ Ee
(f(a) U,(a))+
(a) A)
(20)
(E[T]
LEE
Note that f(a) (L(a))
- As Russo & Roy (2014), by using that
X NWH, 0²) for μ 0, then [[{++ S
V2*
exp
2
we get the following for Rı:
(1-1(a)
-3e
R1
EH,
Σ E,
exp
Hi
(21)
V
2
[E(T]
LAEAA
|AI
-Be
exp
(a) - k(a, a) 1
(22)
2
1
B = 21og([AA|t? /V22
(23)
t
EE(T)
π²
T²
(24)
2
1/w
Lemma 3.1. Let Co /V
Veew//2e(uu (2((w-1) -2="
.hhn for GP-BUCB with confidence parameter
8, (orf-1 (1 2n:)) and ai 2/ {> > 1,
w TI-5
ift/w < 1, ift/w 1, E/ >
Σ -(((a))-Uc(a?)) - EE(T]
s C..
lolog
Proof. Following the proof of Lemma A.2
we get that
AA
B
Σ E [(((a))
U,(af))
exp
(25)
V2T
EE(T]
EE[T]
Note that, according to Lemma A.13 orf (u)
- (1 - u)/1) for w > 1 and D /2e/TVW T/w. We the largest value of & permitted by Lemma A.13 since yields the
16

---

Published as a conference paper at ICLR 2025
tightest bound. Then,
M
Bt 2
exp
exp
(erf~((1
(1 - 2//1)/
(26)
2T
2T
(E
EE [T)
|A
1 - (1 2111)
exp
w
log
(Lemma A.13
(27)
2T
0
(E(T]
2TT
(28)
2
EE(T]
E EE|T]
0 -
(Def. of me)
(29)
TT
Σ
(Def. of v)
(30)
/2eww - 1)
(E(T]
The behaviour of Eiemm tー critically depends on the ratio g/w. First, E/w < 1, then
T {' t f dt
Σ 5 <
T1
(31)
5
00
4E|2]
Second, E/w 1, then
Σt's1 [
T
E'dt = + logT.
(32)
[E|T]
Finally, if E/w > then
5+ /
t- à 1+
E
(33)
:E(T]
Before bound the right term in Lemma A.1 introduce lemma for the confidence radius that applies to all the bandit algorithms considered.
Lemma A.3.
Σ E LE|T
Σ LEER
(i
222 KTTTKB
(34)
for GP-TS or any GP-UCB method with increasing confidence parameter Br.
17

---

Published as a conference paper at ICLR 2025
Proof.
Σ
(
(35)
aaa
E
Σ
(36)
[E|T] aEar
< E
Σ
B1
Σ
Σ
inequality)
(37)
rE[2] aEat
LE[2] aea:
< E
TTK
|a
K, max Br ST) 1E(7]
(38)
[ aEa.
VTKBTE
Σ (a) NE[T] aca.
(39)
$ VTKBTB
V 12(2x + 52)
(Lemma A.12
(40)
V 2(Ax + +3)TKBTTTK.
(41)
Next, we show how the right term in Lemma A.I can be rewritten in terms of the confidence radius for any GP-UCB method.
Lemma A.4.
Σ
((U((a)) f(ai)]
Σ
(42)
EE(T)
(E(T)
for any GP-UCB method with confidence parameter 3r.
Proof. Note that given the history Hi, a == arg max Ua(a) is deterministic. Thus,
(as) f(a:))
Σ
EH. E. (U((ar)
(43)
EE(T]
1E(T]
Σ
EH,
E. (at) v VB f(at) He]]
(44)
tE(T]
Σ 1E[2)
EH, Ee (a))(as)) VB1or-1(ay)) - Hi
(45)
Σ EE|T]
E
(46)
For the final lemma in the finite case, we bound the right term in Lemma A.I for Thompson sampling using the previous results. Lemma A.5.
=²
Σ ((U((a)) - f(a)) 2 CxTKBrrTK +
(47)
(E[T]
holds for GP-TS with 3r 2 log (1A11//v /TT)
18

---

Published as a conference paper at ICLR 2025
Proof. By adding and subtracting the lower bound L(as), obtain
Σ
E (aa)
f(a:))
Σ
E (U)(ar)
f(ar) L(ar) L(a+)]
(48)
1E|T
Σ tE|T
I (Ue(at))
I(ax)] +
Σ
E [L((a)) f(a))]
(49)
<E[T]
2
E (
E (a{))) - f(a))
(50)
EE[T]
EE[T]
By Lemma A.3
(1) S 2(
krrKKBrTT The bound (2) x² is obtained using the same
steps as Lemma A.2 due to the symmetry of L(as) - f(a)) and f(a)) - U(s)..
Finally, we present and prove the regret bounds for GP-UCB, GP-BUCB and GP-TS using the established lemmas.
Theorem 3.2 (Finite regret bounds). Lei CK == 2(xx +s When A finite, the Bayesian regret of
(i) GP-UCB with Br = 2lgg( /v2///22x))) is bounded as BR(T) S 6 + V
(ii) GP-BUCB with 3, (erf (1 2n)) for At
E w 1 is bounded as I 2[
BR(T) S VCRTKBrTTK Cw E-w where C. (VTw/ /eeww- - 1)) 1/w
(iii) GP-TS is bounded as BR(T) < d2 3 + 22CxTKKBrTT where Br = 2 log (1A|(2/ /V12/
Proof. The regret bound for GP-UCB is obtained as follows:
(R( &
Σ
[[f(a]] - (a(a]] +
Σ
E [U,)(a,) - f(a)))
(Lemma A.I
(51)
tE|T]
tE|T]
2
<
+ ((ao)
(Lemmas and
A.4
(52)
6
LE[T]
2
$
+ 2(xx + <2)TKBTTKK
(Lemma A.3
(53)
6
(ii) The regret of GP-BUCB can be decomposed as follows:
BR(T) <
Σ
E (a) - f(a:)] + Σ
E[f(a?) - (aa))
(Lemma A.
(54)
(e[T]
(E[T]
<
E Vioo (a.))
(Lemma A.4
(55)
EE[T]
1/w
VTW
TI-
ifE/w 1,
w-
(Lemma 3
(56)
2ee(w - 1)
if > 1.
From Lemma A.3
Evem E [VBioci(au)] & /2(2x + +²2 (2)TKBryzz and we obtain the desired
result.
(iii) The regret of GP-TS is obtained as follows:
BR(T) = Σ E [f U+(a;)] + Σ
E(U TE[T]
(Lemma A.1
(57)
(E[T]
2
2
+ 2 TKBTTK
(Lemmas A.2 and A.5
(58)
6
6
19

---

Published as a conference paper at ICLR 2025
A.2 INFINITE CASE
Similar to the finite case, we establish lemmas that hold for all bandit algorithms and finally state and prove the regret bounds.
Before stating the first lemma, we restate the assumptions for convenience:
Assumption 3.3 (Regularity assumptions). Assume A C [0, Ci)s is a compact and convex set for some C1 O. Furthermore, assume that μ and l are both L-Lipschitz on A and A A, respectively, for some L > O. In addition, for f ~ GP(,, k) assume that there exists constants C2, C3 > 0 such that:
0ʃ
>1)$Co C2exp (-c3)
12
sup aEA
OaLi)
(5)
for j (1.....d) d) and 1 >> O where a denotes the j-th element of a.
Remark A.6. By Thm. of & 2006)) the high probability bound holds if μ continuously differentiable and is 4 times differentiable, which would also imply the Lipschitzness of i and As discussed by Srinivas et al. (2012), this holds for the Matérn kernel if 2 by result of Stein (999) and holds trivially for the squared exponential kernel. Thus, the Lipschitz assumption of and le is not particularly restrictive.
Assumption 3.4 (Discretization size). Let Ti denote the number of discretization points per dimension and assume that
To 2 26 2 (1+tkkss))
(6a)
T/B 8t LdC,,
(6b)
T//3. 2 81 K L2
(6c)
b2 C3( log((22) 7T/2)
(6d)
where the constants C₁ Cz Cg and are given by Assumption 3.3 whilst the constants d, K and defined by the bandit problem (Section 2.7
Remark A.7. For the theorems to be relevant, the assumptions imposed Tę must be satisfiable for
some If 3: = 2 log T2
then Assumption 3.4 is satisfied by
2
(1
1-t
((1GH (d+log log Vēn
12
Ti max
(1168) (d (d+ log 22
2
2-1/0
(59)
PKdCCC's ( (Vlog(C2d)
v
This can be shown by noting that log S Th and 1 s T/ and then deriving that Br 7. [2"(44ooptt2//221
2
Similarly, if B: = 2 (erf-1 - (1 (1-220 22)))))) and mh
2 2 w > 1, then Assumption 3.4 is satisfied by (1
((BG*)LLCC) (dw +
+log log
1
1-170
22/2T
Tt = max
(1655X91-AC9553) (dw + log
2 172
(60)
22
(KdCiCa (Vlo((2dd) + vT
This is shown similarly as before but using Lemma A.14 to upper bound erl (1 - 2TJe) in Br-
Next, we present a lemma that bounds the discretization error of the expected reward of optimal super
20

---

Published as a conference paper at ICLR 2025
Lemma A.8. Let Dr C A be finite discretization with each dimension equalty divided into 12 KKdC (Vlos(Cad) + vT/2) such that (Dal = T6. Then,
B[s(at) [(aa)o))) x² E
Σ
(61)
Proof.
[[f(a;) - f(aatoo))]
= Σ
Σ f(a) f(alp.)
(62)
*E (T]
aEa;
$ K
E
sup f(a) - f((alo.)
(|a S K)
(63)
AE(T)
LaEA
Lemma H.2 of
1
K
Takeno et al. (2023)
(64)
Kt²
with U4 Ktt"
x
8
x²
(65)
6
In the following lemma, we bound the discretization error of the posterior mean and standard deviation in terms of the regularity parameters, the discretization size and number of arms selected.
Lemma A.9. Let lt-1 and 0-11 denote the posterior mean and standard deviation GP k) after sampling Ni-1 base arms. If a E A, then
(t-1((alp.) - -4--1(a) s
dC1
+ L
dC1
NN-15
-N-I5-VVI--1 - 1)
VI
(66)
Tt.
and
/ + N. 12
dCi,
dC
(e-1((app)-o---1 (a)) S /
5
(67)
for L Lipischitz i and where L is the Cholesky decomposition of +2 and Ly- with N degrees of freedom.
x²
Proof. Consider first the difference in posterior mean:
[--(((ap.)) (a)
(68)
=,((alo,) - p(a) + (k((a)p.) - k(a)) (K (K+ (y -) 44)
(69)
< sup ||a [4],,1l || + (k(la)o,) k(a)) (K + w)/l
(n L-Lisschit))z) (70)
aeA
L dC1,
+ ((((((())))) - k(a)) k(a)) T (K (K + 21= (y - -1)l1/
(71)
Ti
where the last step uses that sup ||a - [a] p. ||1 v dC1
Next, we will appropriately split the norm into a product norms and bound the individual factors.
Let K + 2 LL denote the Cholesky decomposition. Note that y (0, K + +s2I). Then, (y (1) ~ (O, 'LL" 'LL (L-1) = (O I) and thus [ (y - :4) has a chi distribution
with N; degrees of freedom.
21

---

Published as a conference paper at ICLR 2025
Let cig(A) denote the set of cigenvalues of the square matrix A. The matrix norm of the inverted Cholesky decomposition L can be bounded as:
Eq. (538) of Petersen
L 1/2 V max eig (LI-I)
(72)
Pedersen 2012
v max eig (K +21))-1)
(73)
1
max
(74)
eig (K 52T)
1
1
max eig (K) 5
S
$ 5
(K p.s.d.,. 0)
(75)
Similarly, we also get that
IK + 22 -1 112 S5
(76)
The kernel difference can be bounded as follows:
(.) k(a)ll2=
(k((lp,)at) k(a, x:))
(77)
N
dC1
dC1
Σ
L
L
N
(78)
Tt
Tt
where we use the fact that i is T--Lipschitz. Applying Cauchy-Schwarz and the obtained bounds, we find that
dC1 T2
dC1
- ((-
& L
+
N -
| - -H)ll2-
(y-1
(79)
The posterior standard deviation is bounded similarly:
1--1(lala)--a--. - s (looo) - -a]
(80)
Continuing,
- (a)
(81)
M(lolo, (a]p,) - k(a, a) (k(lalo,) - k(a)) (K (K+ +2)) (k((a)o,) - (<<)))((((abb)))
k(a))
(82)
S [ala),,,allo.) k(a, a)) + (k(lalp.) - k(a)) (K + (2)) (k((ap)) -
-k((al))) k(a))
(83)
s dCi,
+ [[(((olo.) k<a)) 12 +21))
(84)
Tt
< L dC', Tt
+ (1 dC1
VN
(Eqs. 766) and 78
(85)
Combining the above, the final bound is:
dCi Ti
(L dC2 ) Ts
)² 5-2.
d.-1((alo)) - 00)1(a) $/1
+ N
(86)
Using Lemma A.9 we are ready construct constant bound for the expected discretization error of the posterior mean:
Lemma A.10. If Assumptiin 3.3 holds and Tt satisfies Eq. (6a) in Assumption 3.4 then for any sequence of super arms a S, t 1, the posterior mean p (a) satisfies
n²
Σ tE T
R ((aooo)))) - (ac) S
(87)
12
22

---

Published as a conference paper at ICLR 2025
Proof. Note that the assumption 7 is equivalent to KL dC1 (1 bound the discretization error of the posterior mean as follows:
1. S 2(2-
Then, we
7.
E
Σ Laca,
Mt- ((al()) 14-1(a)
(88)
EE|T]
E
K sup aeA
( - [a-1
(|ayl S K)
(89)
NE(T]
Σ (E[2]
E
K sup aEA
L
dC1
1+ Vt+K V || (y 10)1
Lemma
A.9
and
(90)
N < LK
Tt
Σ 1E|T"
E
KL dCi
(1+ [ V |L- -y -1l13
L (L U.' y. indepen-) dent of
(91)
T1
= Σ
KI.
dC1
1 \ -1)13
(92)
Tt
tE|T]
KL dC1
D--Vis--VEElII - -101131
Concave Jensen's 's) iinequllit
(93)
Tt
1E/2
[y 11 X with at most (t - 1)K d.o.f.
dC1
Σ
KL (1 (1+ (Ks (1+
(94)
Tt.
1E|T
1
(Assumption on Tt)
(95)
21
(E(T]
?
<
(96)
12"
1=1
See the proof of Lemma A.9 for the motivation that ||_-'(y -1)113 x2.
Similar to Lemma A.10 we establish a constant bound for the discretization error of the posterior standard deviation:
holds; Tr and Be satisfy Eqs. (6b) and (6c) in Assumption 3.4 then, for any sequence of super arms a, S, t 2 1, the posterior standard deviation 1t-1 (a) satisfies
Lemma A.11. If Assumption 3.3
2²
Σ (E[T]]
v Be (o.- (a.)) s 12
(97)
Proof. Note that Eqs.
6bb and (6c) are equivalent
B, dC1 <
1
&CP
1
and
3,tk3
3
2
<
(98)
814
7/
2
814
23

---

Published as a conference paper at ICLR 2025
Then,
E
((o o0
(99)
1E|T
Σ
E
VBs
- -
(100)
te[2]
dCi
C2C
E
+ IKT?
(Lemma A.9
(101)
TI
(E[T]
Laca
dC1
d'C
Σ
K
Be
+ +tKL2
5
(|al S K)
(102)
[E|7]
dCi
&CT
Σ
B,K2
BBBK3
5-2
(103)
Tt
-t
EE|T]
+
(Eq. 98
(104)
811
8/4
(E[T]
8
x²
(105)
21
12"
12
[E[2]
Lemma 3.5. (a) = 1 -Bor.1 Assumption holds and Tę and Br satisfy Eqs. 66a)
(6c) in Assumption 3.4
then for any sequence of super arms a, E St t. 2 1:
[(Ur(la)oo.) - Us(a.)) S Σ 1E
π²
6
Proof. Follows by combining Lemmas A.10 and A.11
Finally, we are ready to prove the regret bounds for the infinite case:
Theorem 3.6 (Infinite regret bounds). Asssumpttin 3.3 holds and satisfies Assumption 3.4 then the Bayesian regret of
(i) GP-UCB with 8, = 2 20 /2T) is bounded as BR(T) S x² + VCCTKBBTT KBTTK.
(i) GP-BUCB with Be = 2 (erl (1 - -2n)))² for m = (2T))//2 (2T bounded as BR(T)
> w > = where Cw =
<
x² + VCXTKBrTIK + Cs &-w
3
/2el 1)) l/W
(ii) GP-TS is bounded as BR(T) < 2x +2VCRTKBBTTK
3
Proof. (i) Similar to Takeno et al. 2023); ) Srinivas et al. 2012), we use a fixed discretization D, C A
for t 1. Let De C A be finite set with De 7 and each dimension equally divided into т
points with T, satisfying Assumption 3.3 Let (a D. denote the nearest point in D, for a E A and similarly let [a]p, {[a] p. la E a) for A.
24

---

Published as a conference paper at ICLR 2025
As Takeno et al. 2023
we decompose the Bayesian regret into several parts:
BR
Σ
E [(at) f((at),)) + f((a)),,)
U:((a))o.)
(106)
1E[T]
(2)
+ Ut((aa]o.) - Ut(a;) + Ut(a;)))))))))))()){() - Ut(a))
(107)
(3)
(4)
+ Uz(as) - f(aa))
(108)
(6)
Term (1) can be bounded using Lemma
A.8
Enery (at) - f(aajl,)) S E Terms (2) and (5)
can be bounded using the finite case with Br 2 log( D 12 ///v/T Then, by Lemmas A.2 to A.4
- - U. + (,,)) - f(a,) - n² + v 2( +T)TKBTTT -
Σ tE[T]
(109)
Takeno et al. 2023) consider the term U U,(aa p.) (a and argue that it is non-positive since
a, arg max (a). Unlike Takeno et al. we not assume that all arms are available at time and thus [a:] l. St does not necessarily hold. By further decomposing this term into (3) and (4).
(ar) O. Then, term (3) can be bounded using Lemma 3.5 ExE(T] ((U,(()))p)) - U, (at) ) S 2/66.
same argument can applied to term (4): U, (a;)
Finally, by combining the bounds for all terms we that
2
(R( S 2 + VCRTKBTTTK.
(110)
(ii) The proof for GP-BUCB is shown by following the steps of GP-UCB and using the finite case for Bayes-GP-UCB (Theorem 3.2 (ii)).
(iii) As in the proof for GP-UCB, assume that we have discretization D, and decompose the Bayesian regret into 4 terms:
BR(T)=
Σ EE[T]
E f(at) f((aā).)) + f((aī]o.) U,(lailo.)
(111)
(1)
(2)
+ U(([lo)))) U.(ay) Uz(a)) f(ar)
(112)
(3)
(4)
As in the proof for GP-UCB, (1) is dealt with using Lemma handled as in the finite case (Theorem 3.2
A.8 and term (2) and (4) are
(iii)):
n²
n² +2 + CRTK3TTTK
Σ EE|T]
[(
(113)
3
To bound term (3), we start by utilizing that at H, d thus:
a. H, and U.((-Io.) H, is deterministic and
Σ B[(3)=
Σ
Em,
E2 [U,(())))) (H.))
(114)
AE[T]
TE(T]
Σ
EH, E. (U(((a))))) - H.l
(115)
π²
(Lemma 3.5)
(116)
Put together, we have that
2T² +2 222CCTKBBrT
BR
(117)
25

---

Published as a conference paper at ICLR 2025
A.3 ADDITIONAL LEMMAS
Lemma A.12. For any sequence of superarms a aT,
T E Loi- S 2((x + MTrK.
(118)
where XK is the largest eigenvalue of all possible posterior covariance matrices of size at most K.
Proof. This proof follows the proof of Lemma 3 of (Nika et al. 2022). Let K, = |ay] denote the number of base arms selected at time Similarly, let Nr LiE(T] Kr denote the number of base arms selected up to time T. Note that the information gain can be decomposed into two entropy terms: [Frp] f) = H (F(T)) H (rm))f).
Since rurlff (fug sk H (Iwnlffrr) 1/2 log [2 INrl- The first term can be analyzed by using the chain rule of entropy on the superarms:
H(rp))) H(rr + H ((rp-1))
(119)
T
Σ H(rllTp-1))
(120)
Then, r1|r[t-1] ~ [H E,-1 + Ix.) where p4-1 = (4e1(c))aEm, is the posterior mean vector and E,-1 = (ki-1 (a, a' d'))aa''a xa, is the posterior covariance matrix for superarm a, after observing (a), P() ri),..., ... 1a rr-1). ). Let de, denote the smallest kth eigenvalue of E,-1. Then,
H(rl///-1))
log [2te(E111 +s²
(121)
1
log [2TTes
25-22 + IK.)
(122)
2
log 2 I
+ 2
log -2 + Ik.
(123)
2
Let de, denote the smallest kth eigenvalue of Σ, Let M = (E,-ilii E [7], Vaj,................. a, E S)
be the set of all possible posterior covariance matrices and let Ai = supsEM max eig Σ) be the
largest eigenvalue of all eigenvalues of the matrices in M. Recall that |A + /n I (Ax + 1) for any real and symmetric matrix Rax= with eigenvalues An.... Then,
1 log
- Ik.l
(124)
Kg
II Ae. Nex
log
(125)
2
Kr
log (s -2x, + 1)
(126)
2 k=1
(log( + +1. 1)
(127)
2 Xx, +
1=1
2
K2
2
Xe.
(128)
2(s -Xx + 1)
2x
km
2 (a).
Tr(A)
Σ
(129)
2X +
a6a,
AEcig(A)
Put together, we get that Σr o7 (a.) < 2(x +<2)((TTT)) f). Since the maximum information
Or is increasing w.r.t. T and lad| < K, get that Σ of (ar) 2(x" + 5
n
26

---

Published as a conference paper at ICLR 2025
Lemma A.13. The inverse ervor function is lower bounded by
-
crf (u) 2
-
log
(130)
for u E [0,1), w and
yu-1 w
Proof. According to Theorem 2 of Chang al. 2011 erfc(u) 2 0 exp((www)) for 1 and
0 < 0 V
2e vw-1 Since erf(u) 1 crfc((u)) it follows that erf(()) 1-10 exp( exp(-wu?) h(u).
In general, if [(x) < g(x:) then (x) 2 g (x)) Thus, eu) 2 (w)
log ((1 u)/0).
Lemma A.14. The inverse error function is upper bounded by
11 0
erf (u) S
- log
(131)
for u E 1), 0 2 1 and 0 < w S
Proof. The same arguments in Lemma A.13 but using Theorem 1 of Chang al. (201))
B ADDITIONAL EXPERIMENTAL DETAILS
B. KERNEL DETAILS
Here, provide further details the graph kernel used in the experiments. The original graph Matérn GP of Borovitskiy et al. (202I) defines GP on the vertices weighted and undirected graph. We extend the graph Matérn GP from (Borvviskii al. (202T) the edges of directed graph by considering the incidence graph Laplacian of the line graph L(G).
Let We E [|x| denote the weight matrix of L(g) (E, where E the set of edges and is to E/le, where is the average
the set of all connections the network. The weight W Weeeee length of all edges and be is the length of edge e1. We replace the ordinary graph Laplacian used by Borovitskiy al. 202T) with the incidence Laplacian:
A BB
(132)
where the incidence matrix B E X has entries
WC,eres Wc,en.
if C1 if C22 otherwise
Be,
Ye E, (21, E C.
(133)
Let A, U, denote the eigendecomposition of A,, then the graph Matérn GP of the edges is given by
f N~N L~N(O,U)
0,U,
22G I A1) -V R2
U7
(134)
Recall that ky Rd x Rdd + R denotes feature kernel which measures the similarity between the contexts of the edges. The feature kernel an ordinary Matérn kernel with fixed 5/2 but tunable outputscale oy and lengthscales ł, E Rd for each dimension:
2 ky xe)) == = (VZeD)* Ko (V2VD).
(135)
27

---

Published as a conference paper at ICLR 2025
Table 2: Vehicle and environmental parameters for the energy model.
Variable
Value
Unit
Mass m
1830
kg
Rolling resistance coefficient C+
0.01
Front surface area A
2.6
m²
Air drag coefficient Ca
0.35
Power train efficiency 17*
0.98
Recuperation efficiency
0.96
Gravitational acceleration g
9.82
m/s²
Air density
1.2
kg/m²
where z, denotes the feature vector of edge e and the feature distance D between edge e and e' is given by
D V(r. TTe)T diag(e,)
(136)
The kernels, the SVGP model and Algorithm 3 was implemented using GPyTorch (Gardner et al. 2018
B.2 ROAD NETWORK
The set of available paths was restricted edges within the largest strongly connected component. This mainly removed road segments in inaccessible areas and does not affect the navigational challenge. The route Luxembourg A starts in edge -31 121110 1 and ends in edge -- -232 64 6 1. The route Luxembourg B starts in edge 43446655 and ends in edge 4094 6#0. Similarly, the route Monaco starts edge -35558 and ends in edge -32888 # whilst Monaco starts in edge -321 # and ends in edges -232 4 4044 #0. For simplicity, the start and end points are edges since the shortest path was computed using the line graph L(g).
B.3 DETAILED PARAMETER VALUES
In this section, further specify the vehicle, environmental and algorithmic parameters used. We use the default parameters for electric vehicles provided by SUMO (opezz et al. 2018). see Table 2
The graph kernel is initialized with parameters ve 2, KG 1 and OG set according to the prior. The natural gradient descent learning rate is set to 0.1 whilst the Adam learning rate is set to 0.01. The GP model number inducing points is set to 1000.
batch size B of 2500 and gradient step per optimization procedure. The
C ADDITIONAL EXPERIMENTAL RESULTS
C.1 IMPACT OF LENGTHSCALE
In this section, provide the full results for the lengthscale experiments in Section The cumulative regret over time is visualized in Fig. and the final cumulative regret as function on the lengthscale is visualized in Fig.
C.2 VISUALIZATION OF EXPLORATION
In this section, provide visualization of the routes selected by the algorithms. See Figs. 6 9 for visualization on Lux. A, Lux B. Mon. A and Mon. B, respectively. According to the results, the TS variants able find sophisticated paths with significantly less exploration compared BUCB and UCB. This observation implies the sample efficiency of TS methods.
28

---

Published as a conference paper at ICLR 2025
Lux. A
Cum. regret [eWh]]
CUBBUBB
40
BI-BUCB
GP- 18
BI-TS
2
20
0
0
200
100
200
400
200
100
200
400
Lux. B
GP-BUCB
50
BI-BUCB
GP-TS
BI-TS
50
2
5
0
200
400
200
400
200
200
400
Mon. A
GP-BUCB
BI-BUCB
GP-TS
BI-TS
50
50
25
25
20
0
0
200
400
200
400
200
400
200
400
Mon. B
EP.BUCB
40
BI-BUCB
GP-TS
BI-TS
40
20
01
0
0
0
200
400
200
400
200
400
200
400
2.00
1.00
8
0.50
0.25
0.10
Figure 4: Cumulative regret of GP-BUCB, BI-BUCB, GP-TS and BI-TS for varying prior lengthscale
values
29

---

Published as a conference paper at ICLR 2025
Lux. A
BUCB
TS
Cum. regret [kWh]
40
10
5
20
Lux.
Cum. regret [kWh]
75
10
50
25
Mon. A
Cum. regret [Wh]
60
40
50
20
40
2
Mon. B
Cum. regret WWh
50
20
40
10
30
GP-BUCB I
BI-BUBB -
GP-TS
BI-TS
Figure 5: Cumulative regret at 500 for varying prior lengthscale values. Errorbars correspond to +1 standard error.
30

---

Published as a conference paper at ICLR 2025
500
500
400
400
300
300
200
200
100
100
(a) BI-TS
(b) GP-TS
500
500
400
400
300
300
200
200
100
100
(c) BI-UCB
(d) GP-UCB
500
500
400
400
300
300
200
200
100
100
(e) BI-BUCB
(1) GP-BUCB
Figure 6: Exploration of Luxembourg A.
31

---

Published as a conference paper at ICLR 2025
500
500
400
400
300
300
200
200
100
100
(a) BI-TS
(b) GP-TS
500
500
400
400
300
300
200
200
100
100
(c) BI-UCB
(d) GP-UCB
500
500
400
400
300
300
200
200
100
100
(e) BI-BUCB
(I) GP-BUCB
Figure 7: Exploration of Luxembourg B.
32

---

Published as a conference paper at ICLR 2025
500
500
400
400
300
300
200
200
100
100
(a) BI-TS
(b) GP-TS
500
500
400
400
300
300
200
200
100
100
(c) BI-UCB
(d) GP-UCB
500
500
400
400
300
300
200
200
100
100
(e) BI-BUCB
(1) GP-BUCB
Figure 8: Exploration of Monaco A.
33

---

Published as a conference paper at ICLR 2025
500
500
400
400
300
300
200
200
100
100
(a) BI-TS
(b) GP-TS
500
500
400
400
300
300
200
200
100
100
(c) BI-UCB
(d) GP-UCB
500
500
400
400
300
300
200
200
100
100
(e) BI-BUCB
(1) GP-BUCB
Figure 9: Exploration of Monaco B.
34


Reviews:
[{"review_id": "nkjnwwAI9g", "reviewer": "Reviewer_mCBV", "summary": "The authors derive Bayesian regret bounds for various algorithms applied to combinatorial volatile GP semi-bandit problems. Specifically, the authors derive regret bounds for 3 algorithms: GP-UCB, GP-BayesUCB, and GP-Thompson Sampling. In comparison to previous works, this is the first regret bound for GP-Bayes UCB, and in addition, extend the existing regret bounds for GP-UCB and GP-TS to infinite, volatile and combinatorial setting (which is also includes the popular contextual bandit setting).\n\nThe authors apply these algorithms to the problem of online energy-efficient navigation to demonstrate the performance of the various algorithms.", "questions": "Please respond to my above concerns.\n\nIn addition, I would request the authors to add theorems / propositions after Theorems 3.2 and 3.6, without any \\gamma_t and \\beta_t terms. Or more generally, with as few variables as possible.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main strengths of the paper is the theory. I do believe the GP semi-bandit problems considered in this paper are important, and having regret bounds for the algorithms discussed in this paper is also useful. \n\nSpecifically, it is nice to see sub-linear regret bound for all three algorithms.\n\nFurthermore, I also believe that the general techniques developed here may be useful to derive regret bounds for other bandit settings.", "weaknesses": "1. I think the paper lacks some clarity, and the exposition can improve significantly. For example, it requires recalling previous literature to properly understand the set-up in Section 2.1: Is A a finite set? 2^A is the set of a all subsets of A? What happens when A is infinite as in Section 3.2? \n2. Though the dependency on T is sub-linear, I am not sure how to view the dependency on K. Especially in the infinite case. Are there any lower bounds for these settings? It is hard to view how good or bad the bounds are with lack of comparisons.\n3. Building on top of 2 above, I am curious to know if this is the best dependency on T you can get. I am used to seeing \\sqrt{T} regret bounds for bandit algorithms -- is this not achievable in such settings?\n4. I thought that the experimental section was too artificial. If the motivation is to solve the problem in best possible way, there are probably better ways of solving the problem (for example using RL), than naively applying the semi-bandit learning algorithms. If the point is to show the performance of various algorithms, a simple example would suffice. In my opinion, the addition of these experiments does not add any additional value to the paper, and does not change the fact that the papers main (only) contributions are the theoretical bounds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yAvuhJRQMA", "reviewer": "Reviewer_2DSA", "summary": "This paper investigates the combinatorial volatile Gaussian process (GP) semi-bandit problem and provides the first Bayesian regret bounds for the GP-BayesUCB algorithm. In addition to this novel contribution, the authors extend their theoretical analysis to include Bayesian cumulative regret bounds for the GP-UCB and GP-TS algorithms, effectively addressing a notable research gap as highlighted in Table 1. To demonstrate the practical relevance of their framework, the authors apply their methods to a real-world problem: online energy-efficient navigation.", "questions": "1.\tConnection Between Theory and Empirical Results:\nThe online energy-efficient navigation application is a compelling demonstration of the framework’s practical utility. However, it would be helpful to clarify how the empirical results relate to the theoretical findings. Specifically, can the empirical results be used to verify or illustrate key observations from the theoretical analysis? If this connection is not direct, could you design controlled simulated experiments that more explicitly validate the theoretical regret bounds or insights?\n2.\tExtended Comparison in Table 1:\nIncluding the regret rates alongside the regret bounds in Table 1 would greatly enhance its utility. This addition would allow readers to quickly compare the performance of different algorithms in terms of their theoretical guarantees. An extended table with this information would provide a clearer overview of the contributions and situate the work more firmly within the existing literature.\n3.\tDiscussion of Theoretical Challenges:\nAs mentioned in the weaknesses, a dedicated section or paragraph discussing the theoretical challenges faced in deriving the regret bounds for GP-BayesUCB, GP-UCB, and GP-TS would add significant value. This discussion could cover aspects such as handling the volatility in combinatorial settings, managing the complexities introduced by semi-bandit feedback, or other technical hurdles specific to these algorithms.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tClear and Structured Presentation:\nThe paper is well-written, with clear explanations and illustrations of the research gaps. The novelty of this work is effectively communicated, making it accessible even to readers who may not be deeply familiar with the field.\n2.\tSolid Theoretical Contributions:\nThe authors provide rigorous theoretical analysis and establish new Bayesian regret bounds for multiple algorithms, including GP-BayesUCB, GP-UCB, and GP-TS. The paper addresses a significant gap in the literature by formalizing regret bounds for these settings. Full proofs are provided in the appendices, showcasing the depth of their analysis (though the correctness of these proofs was not verified).\n3.\tPractical Application:\nThe real-world application of their framework to online energy-efficient navigation is both relevant and interesting. It demonstrates the practical utility of their theoretical advancements and highlights the potential for real-world impact.", "weaknesses": "1.\tLack of Discussion on Theoretical Challenges:\nWhile the paper provides new theoretical results, it does not clearly articulate the specific challenges encountered in deriving these results for GP-BayesUCB, GP-UCB, and GP-TS. A discussion on the theoretical hurdles and how they were addressed would provide valuable insight into the novelty and difficulty of these contributions.\n2.\tReproducibility Concerns:\nNo code is provided for the experiments. This absence raises concerns about the reproducibility of the empirical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M3be81hOwM", "reviewer": "Reviewer_WnA6", "summary": "The paper claims to present a novel Bayesian regret bounds for GP-UCB and GP-TS in combinatorial, volatile and infinite arms setting. Further they present the experimental results for a real world application of online energy efficient navigation.", "questions": "See the weakness section", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The paper provides the bounds for the Bayesian regret for GP-BUCB, GP-UCB and GP-TS.", "weaknesses": "1. Though the work claims to present the bounds for volatile case but the proof for the bounds do not seem to consider it. As an example what would happen when the best arm is not present among the observed arms?\n2. Not significant contribution, the paper mainly builds on the works of Russo & Roy 2014, Srinivas et al 2012 and Takeno et al 2023, where in to compute the Bayesian regret one only needs to compute the expectation over the high probability regret bounds given by the above works.\n3. Lemma 3.1 the results are considered for different regimes of horizons for different cases of the ratio, why not choose the limits as 1 to T for the 3rd case, wouldn't that be a tighter bound?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VH01lBGBMT", "reviewer": "Reviewer_8zLg", "summary": "The paper studies Gaussian process bandits in the contextual volatile semi-bandit setting. The contribution of the paper is mainly theoretical as it provides novel Bayesian regret bounds for previously designed algorithms. In addition, there is an interesting application of their framework in online energy efficient navigation. This experimental application builds on top of the previously designed experiment of the same application in bandit papers.", "questions": "Does the type of directed graph affect the applicability of the framework? For instance, how does the graph [being cyclic or acyclic] affect the performance of the framework? \n\nI did not notice any discussion in the paper about possible extensions and future directions and further impacts of their research, not even in the supplamentary section. Why? Can you please clarify?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is building on top of other previously published frameworks, however, it is not a straightforward extension of the previous works. \n\nThe experiments (application of their framework) in online energy-efficient navigation problem seem to have added some novelties and value to the paper. \n\nThe paper is written in an excellent way. The explanations for the most important parts of the algorithms are clear. Also the similarities and differences (novelties) of their framework in comparison to the state-of-the-art is clarified properly.", "weaknesses": "No synthetic data experiment. Not even in the supplementary material. In my opinion, synthetic data experiments can significantly add to the development of intuitions about the framework. Also since you have much more control over the creation of the data, it can reveal interesting properties of the framework [in comparison with state-of-the-art]. \n\nAlso, I could not find an experiment with the horizon more than 500 rounds. I am curious about the performance of the frameworks as the horizon goes well beyond T=500. I believe that proper comparison of bandit frameworks [most of the times] comes with running the experiments for long horizons. \n\nI did not notice any discussion in the paper about possible extensions and future directions and further impacts of their research.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)