Bayesian Analysis of Combinatorial Gaussian Process Bandits

## Abstract

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 infinite , volatile and 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.

## 1 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 on the selected action.
The goal of the agent is to minimize its expected cumulative regret over a certain time horizon, either finite or infinite, where regret is defined as the expected difference in reward between the agent’s selected arm and the best arm (Robbins, ). The MAB problem has applications in healthcare, advertising, telecommunications and more (Bouneffouf et al., ).

The combinatorial MAB (Gai et al., ; Cesa-Bianchi & Lugosi, ; Chen et al., ) considers a problem where the agent must select a 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 environments in bandit applications often have some side-information (or context) that is correlated with the reward, e.g., the titles or user specifications in a news recommendation problem.
In the contextual MAB (Li et al., ; Krause & Ong, ; Agarwal et al., ; Zhou, ), before selecting an arm, the agent is 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 a finite number of arms.
A common assumption is that the expected reward is a sample from a 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.

**Table 1: Comparison of similar work in GP MABs.**
|  | Ours | () | () | () | () | () |
| --- | --- | --- | --- | --- | --- | --- |
| Infinite/Finite | Infinite | Infinite | Infinite | Infinite | Finite | Infinite |
| Volatile/Static | Volatile | Volatile | Static | Static | Volatile | Static |
| Combinatorial | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ |
| Bayesian/Frequentist | Bayesian | Frequentist | Bayesian | Bayesian | Bayesian | Frequentist |
| GP-UCB | ✓ | ✓ | ✓ | ✗ | ✓ | ✓ |
| GP-TS | ✓ | ✗ | ✓ | ✓ | ✓ | ✗ |
| GP-BUCB | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ |

In Table 1, we provide an overview and comparison of similar work in GP MABs.
The seminal paper of Srinivas et al. () first introduced the GP-UCB algorithm, which combines upper confidence bounds (UCB) with GPs for MABs with finite or infinite arm sets. provided frequentist regret bounds for GP-UCB on a MAB problem with a compact (infinite) arm space. Later work by Russo & Roy () provided Bayesian regret bounds for GP-UCB and GP-TS, a similar algorithm based on Thompson sampling (Thompson, ), 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 a general formulation that encompasses other MAB extensions such as the contextual MAB.

For the infinite arm setting, only hinted that the proof follows by discretization arguments.
Using discretization, the recent work by Takeno et al. (, ) 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 et al., ; Chen et al., ; Nika et al., , ; Elahi et al., ), with applications in online advertisement, epidemic control and base station assignment (Nuara et al., ; Lin & Bouneffouf, ; Shi et al., ).
Recent work by Nika et al. () considered the C3-MAB with base arm rewards sampled from a GP. Nika et al. () provided high probability regret bounds for a 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 combinatorial volatile Gaussian process semi-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 as it is a special case of the volatile setting.
Additionally, we present a Bayesian regret bound for a third bandit algorithm called GP-BayesUCB (GP-BUCB) which is based on the BayesUCB algorithm of Kaufmann et al. (). Whilst GP-BUCB was introduced by Nuara et al. () for a combinatorial bandit problem, to the best of our knowledge there are no regret bounds for 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-efficient 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*.
Åkerblom et al. () 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 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 GP-BayesUCB.
- •
We develop a combinatorial and contextual bandit framework for the important real-world application of online energy-efficient navigation.

## 2 Setup and Algorithms

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 $\mathcal{A}\subset\mathbb{R}^{d}$ denote the set of base arms in a $d$-dimensional space and $\mathcal{S}=\{\mathbf{a}|\mathbf{a}\subset\mathcal{A}\}\subset 2^{\mathcal{A}}$ denote the set of feasible super arms. The expected reward for the base arms $f(a)\sim\mathcal{GP}(\mu(a),k(a,a^{\prime}))$ is assumed to be a sample from a Gaussian process with mean function $\mu(a):\mathcal{A}\xrightarrow{}\mathbb{R}$ and covariance function $k(a,a^{\prime}):\mathcal{A}\times\mathcal{A}\xrightarrow{}[-1,1]$.

At time $t$, a possibly random and finite subset of base arms $\mathcal{A}_{t}\subseteq\mathcal{A}$ is available to the agent. In a combinatorial setting, the agent must select a feasible subset of base arms, a super arm, $\mathbf{a}_{t}\in\mathcal{S}_{t}$ where $\mathcal{S}_{t}\subset 2^{\mathcal{A}_{t}}$ is the set of feasible and available super arms. To facilitate a feasible combinatorial problem, the number of feasible super arms is finite in each round and the super arms have a maximum size $K$ ($|\mathbf{a}|\leq K$ $\forall\mathbf{a}\in\mathcal{S}_{t}$). The agent observes the rewards of the selected base arms (semi-bandit feedback) $\mathbf{r}_{t}=\{r_{t,a}|a\in\mathbf{a}_{t}\}$ where the base arm reward $r_{t,a}=f(a)+\epsilon_{t,a}$ is a sum of the expected reward and i.i.d. Gaussian noise with zero mean and variance $\varsigma^{2}$. Motivated by the online 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 $t$: $R_{t}=\sum_{a\in\mathbf{a}_{t}}r_{t,a}$. The total number of time steps, the horizon, is denoted by $T$. Let $H_{t}$ denote the history $(\mathcal{A}_{1},\mathcal{S}_{1},\mathbf{a}_{1},\mathbf{r}_{1},\ldots,\mathcal
{A}_{t-1},\mathcal{S}_{t-1},\mathbf{a}_{t-1},\mathbf{r}_{t-1},\mathcal{A}_{t},
\mathcal{S}_{t})$ of past observations and the currently available arms at time $t$.

In this work, we are interested in minimizing the Bayesian cumulative regret which, with a horizon of $T$, is defined as

$$ $\text{BR}(T)=\mathbb{E}\Big{[}\sum_{t\in[T]}f(\mathbf{a}_{t}^{*})-f(\mathbf{a} _{t})\Big{]},$ (1) $$

where $[T]:=\{1,...,T\}$, $\mathbf{a}_{t}^{*}=\operatorname*{arg\,max}_{\mathbf{a}\in\mathcal{S}_{t}}f(
\mathbf{a})$ and $f(\mathbf{a})=\sum_{a\in\mathbf{a}}f(a)$. As discussed by Russo & Roy (), allowing stochastic arm sets permits us to consider broader sets of bandit problems, an example of particular interest to us will be contextual models.

Algorithm 1 provides a framework for the introduced bandit problem. In the framework, the agent parameters $\bm{\theta}_{t}$ are defined for a general agent and are not specified here. Similarly, $\mathbf{U}_{t}$ denotes the set of base arm indices which could be upper confidence bounds or a posterior sample, depending on the algorithm used.

Figure: Algorithm 1 Framework for combinatorial volatile semi-bandit problem

### 2.2 Bayesian framework for combinatorial Gaussian process bandits

A Gaussian process $f(a)\sim\mathcal{GP}(\mu(a),k(a,a^{\prime}))$ is a collection of random variables such that for any subset $\{a_{1},\ldots,a_{N}\}\subset\mathcal{A}$ the vector $\mathbf{f}=[f(a_{1}),\ldots,f(a_{N})]$ has a multivariate Gaussian distribution.
We take a Bayesian view of the combinatorial problem and consider $\mathcal{GP}(\mu,k)$ as a 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 $N_{t-1}=\sum_{\tau=[t-1]}|\mathbf{a}_{\tau}|$ denote the total number of base arms selected up to time $t-1$ and let $a_{1},\ldots,a_{N_{t-1}}$ denote the arms selected before time $t$. Additionally, let $\mathbf{y}\in\mathbb{R}^{N_{t-1}}$ denote the corresponding observed base arm rewards and $\bm{\mu}=[\mu(a_{1}),\ldots,\mu(a_{N_{t-1}})]^{\top}$ denote the corresponding prior expected base arm mean rewards. Then, for any $a\in\mathcal{A}$, the posterior GP distribution is given by:

$$ $\displaystyle\mu_{t-1}(a)$ $\displaystyle=\mu(a)+\mathbf{k}(a)^{\top}\left(\mathbf{K}+\varsigma^{2}I\right )^{-1}(\mathbf{y}-\bm{\mu})^{\top}$ (2) $\displaystyle k_{t-1}(a,a^{\prime})$ $\displaystyle=k(a,a^{\prime})-\mathbf{k}(a)^{\top}\left(\mathbf{K}+\varsigma^{ 2}I\right)^{-1}\mathbf{k}(a^{\prime}),$ (3) $$

where $\mathbf{K}=\big{(}k(a_{i},a_{j})\big{)}_{i,j=1}^{N_{t-1}}$ is the covariance matrix of the previously selected arms and $\mathbf{k}(a)=\left[k(a,a_{1}),\ldots,k(a,a_{N_{t-1}})\right]^{\top}$ is the covariance between $a$ and the previously selected arms. Let $\sigma_{t-1}(a)$ and $\sigma_{t-1}^{2}(a)$ denote the posterior standard deviation and variance respectively.

In , introduced the GP-UCB algorithm, which selects the next arm based on an upper confidence bound. In our combinatorial setting, the GP-UCB algorithm selects the super arm
$\mathbf{a}_{t}=\operatorname*{arg\,max}_{\mathbf{a}\in\mathcal{S}_{t}}U_{t}(
\mathbf{a})$
where $U_{t}(\mathbf{a})=\mu_{t-1}(\mathbf{a})+\sqrt{\beta_{t}}\sigma_{t-1}(\mathbf{a})$, $\mu_{t-1}(\mathbf{a})=\sum_{a\in\mathbf{a}}\mu_{t-1}(a)$, $\sigma_{t-1}(\mathbf{a})=\sum_{a\in\mathbf{a}}\sigma_{t-1}(a)$ and $\beta_{t}$ is a confidence parameter, typically of order $\mathcal{O}(\log t)$.
Kaufmann et al. () introduced Bayes-UCB, which selects the arm with the largest $(1-\eta_{t})$-quantile, where the quantile parameter $\eta_{t}$ was of order $\mathcal{O}\left(1/t\right)$. Adapted to the combinatorial Gaussian process setting, we suggest the following selection rule for Bayes-UCB:
$\mathbf{a}_{t}=\operatorname*{arg\,max}_{\mathbf{a}\in\mathcal{S}_{t}}\sum_{a
\in\mathbf{a}}Q\left(1-\eta_{t},\mathcal{N}\left(\mu_{t-1}(a),\sigma^{2}_{t-1}
(a)\right)\right),$ where $Q(p,\lambda)$ denotes the $p$-quantile of the distribution $\lambda$. We refer to this adapted version as GP-BUCB. Note that for $\lambda=\mathcal{N}(\mu,\sigma^{2})$, the $p$-quantile is given by $Q(p,\mathcal{N}(\mu,\sigma^{2}))=\mu+\sigma\sqrt{2}\operatorname{erf}^{-1}
\left(2p-1\right)$ where $\operatorname{erf}^{-1}(\cdot)$ is the inverse of the error function. Thus, GP-BUCB can be seen as a variant of GP-UCB where $\beta_{t}=2\left(\operatorname{erf}^{-1}\left(1-2\eta_{t}\right)\right)^{2}$.
GP-TS (Russo & Roy, ; Chowdhury & Gopalan, ) selects the next arm randomly by using posterior sampling. If $\hat{f}_{t}(a)\sim\mathcal{GP}(\mu_{t-1},k_{t-1})$ is a sample from the posterior distribution, then, in the combinatorial setting, GP-TS selects the super arm
$\mathbf{a}_{t}=\operatorname*{arg\,max}_{\mathbf{a}\in\mathcal{S}_{t}}\hat{f}_
{t}(\mathbf{a}),$ where $\hat{f}_{t}(\mathbf{a})=\sum_{a\in\mathbf{a}}\hat{f}_{t}(a)$.

### 2.3 Information gain

The regret bounds of most GP bandit algorithms depend on a parameter called the maximal information gain $\gamma_{T}$ (Srinivas et al., ; Vakili et al., ). The maximal information gain (MIG) describes how the uncertainty of $f$ diminishes as the best set of sampling points $\mathbf{a}\subset\mathcal{A},|\mathbf{a}|\leq T$ grows in size $T$. The MIG is defined using the mutual information between the observations $\mathbf{y}_{\mathbf{a}}$ at locations $\mathbf{a}$ and expected reward function $f$:

$$ $\gamma_{T}:=\sup_{\mathbf{a}\subset\mathcal{A},|\mathbf{a}|\leq T}I(\mathbf{y} _{\mathbf{a}};f),$ (4) $$

where $I(\mathbf{y}_{\mathbf{a}};f)=H(\mathbf{y}_{\mathbf{a}})-H(\mathbf{y}_{\mathbf{
a}}|f)$ and $H(\cdot)$ denotes the entropy. Both the true value of $\gamma_{T}$ and most upper bounds depend on the kernel function $k$ defining the GP from which $f$ is sampled from. Srinivas et al. () initially introduced bounds on $\gamma_{T}$ for common kernels, such as the Matérn and RBF kernels. For the RBF kernel, showed that $\gamma_{T}=\mathcal{O}\left(\log^{d+1}(T)\right)$. Later, () presented a general method of bounding $\gamma_{T}$ that utilizes the eigendecay of the kernel $k$. Using this method, obtained improved bounds on the Matérn kernel with smoothness parameter $\nu$: $\gamma_{T}=\mathcal{O}\left(T^{\frac{d}{2\nu+d}}\log^{\frac{2\nu}{2\nu+d}}(T)\right)$. To apply these bounds, we require that $\mathcal{A}$ is compact.

## 3 Regret Analysis

Whilst the work of Chen et al. () can be seen as a standard combinatorial framework, we adopt the framework of (Russo & Roy, ) since it is better suited for Bayesian bandits with volatile and infinite arms.
Russo & Roy () first provided a Bayesian regret bound for GP-UCB in a volatile (but non-combinatorial) setting with a finite arm set. Recently, Takeno et al. () presented explicit proof for the Bayesian regret of GP-UCB with a compact and static arm set. In this section, we 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-BayesUCB. Similar to previous work, we first consider the finite arm case, $|\mathcal{A}|<\infty$, and then consider the infinite case 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 of Russo & Roy (), we seek to bound two terms: $\mathbb{E}[f(\mathbf{a}_{t}^{*})-U_{t}(\mathbf{a}^{*}_{t})]$ and $\mathbb{E}[U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_{t})]$. For GP-BUCB, establishing an upper bound for the second term requires us to work around the non-elementary function $\operatorname{erf}^{-1}(u)$. Using Thm. 2 of Chang et al. (), we find that $\operatorname{erf}^{-1}(u)\geq\sqrt{-\omega^{-1}\log((1-u)/\vartheta)}$ for $\omega>1$ and $0<\vartheta\leq\sqrt{2e/\pi}\sqrt{\omega-1}/\omega$, see Eq. 130. The bound is tighter for larger values of the parameter $\vartheta$ (Chang et al., ), thus we set $\vartheta$ to its maximum value whilst $\omega$ is kept as a tunable parameter. Recall that the quantile parameter $\eta_{t}$ determines how quickly the confidence bound grows and the order $\xi>0$ (s.t. $\eta_{t}=\mathcal{O}(t^{-\xi})$) is another tunable parameter. As shown in the lemma below, these parameters influence the bound we get.

[]
Let $C_{\omega}=\left(\sqrt{\pi}\omega/\sqrt{2e(\omega-1)}\right)^{1/\omega}$, then for
GP-BUCB with confidence parameter $\beta_{t}=2\left(\operatorname{erf}^{-1}(1-2\eta_{t})\right)^{2}$ and $\eta_{t}=\frac{\sqrt{2\pi}^{\omega}}{2|\mathcal{A}|^{\omega}t^{\xi}}$, $\xi>0$, $\omega>1$,

$$ $\sum_{t\in[T]}\mathbb{E}[f(\mathbf{a}_{t}^{*})-U_{t}(\mathbf{a}_{t}^{*})]\leq C _{\omega}\cdot\begin{cases}\frac{\omega}{\omega-\xi}T^{1-\frac{\xi}{\omega}} \quad&\text{if }\xi/\omega<1,\\ 1+\log T\quad&\text{if }\xi/\omega=1,\\ \frac{\xi}{\xi-\omega}\quad&\text{if }\xi/\omega>1.\end{cases}$ $$

Kaufmann et al. () studied (non-GP and non-combinatorial) Bayes-UCB for a Bernoulli bandit with $\xi=1$ whilst our analysis permit any $\xi>0$. Section 3.1 shows that the ratio $\xi/\omega$ determines if the bound for the right term is sublinear, logarithmic or constant w.r.t $T$ for GP-BUCB. The equivalent bounds for GP-UCB and GP-TS are both constant if $\beta_{t}=2\log\left(|\mathcal{A}|t^{2}/\sqrt{2\pi}\right)$, see Section A.1, thus we assume $\xi/\omega>1$ to simplify the regret bounds.

Srinivas et al. () showed, in 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 3 in Nika et al. () (adopted to our setting in Eq. 118) generalizes this result to a combinatorial setting. The result depends on the maximum eigenvalue of all possible posterior covariance matrices of size at most $K$, which we denote as $\lambda^{*}_{K}$.

Then, we present the main theorems for GP-UCB, GP-BUCB and GP-TS in the finite case, see Section A.1 for the proofs.

###### Theorem 3.1 (Finite regret bounds) .

Let $C_{K}:=2(\lambda^{*}_{K}+\varsigma^{2})$. When $\mathcal{A}$ is finite, the Bayesian regret of

- (i)
GP-UCB with $\beta_{t}=2\log(|\mathcal{A}|t^{2}/\sqrt{2\pi})$ is bounded as
$\text{BR}(T)\leq\frac{\pi^{2}}{6}+\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}.$
- (ii)
GP-BUCB with $\beta_{t}=2\left(\operatorname{erf}^{-1}(1-2\eta_{t})\right)^{2}$ for $\eta_{t}=\frac{\sqrt{2\pi}^{\omega}}{2|\mathcal{A}|^{\omega}t^{\xi}}$, $\xi>\omega>1$ is bounded as
$\text{BR}(T)\leq\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}+C_{\omega}\cdot\frac{\xi}{
\xi-\omega}$
where $C_{\omega}=\left(\sqrt{\pi}\omega/\sqrt{2e(\omega-1)}\right)^{1/\omega}$.
- (iii)
GP-TS is bounded as
$\text{BR}(T)\leq\frac{\pi^{2}}{3}+2\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}$
where $\beta_{t}=2\log\left(|\mathcal{A}|t^{2}/\sqrt{2\pi}\right)$.

For all three algorithms (if $\xi/\omega>1$ for GP-BUCB), we find that $\text{BR}(T)=\mathcal{O}(\sqrt{\lambda^{*}_{K}TK\beta_{T}\gamma_{TK}})$ where $\gamma_{TK}$ is the MIG from $TK$ base arms. Using the bounds of $\gamma_{T}$ 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. (), obtains a frequentist regret bound of the same order. Nika et al. () noted that $\lambda^{*}_{K}=\mathcal{O}(K)$ which gives a linear dependence on $K$ in the worst case (Zhan, ). 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. (, ) has a Bayesian regret of $\mathcal{O}(\sqrt{T\gamma_{T}})$ in the finite case, suggesting that a $\sqrt{\beta_{T}}=\mathcal{O}(\sqrt{\log T})$ improvement is possible.

###### Theorem 3.1 (Finite regret bounds) .

### 3.2 Infinite case

The infinite case is an important generalization since many decision problems have a continuum of actions to select from. Based on our framing of contextual MABs as a subset of volatile MAB, an infinite arm set permits contexts with support on infinite domains such as continuous time. This setting is often analytically more difficult and requires the following additional assumptions:
{assumption}[Regularity assumptions]
Assume $\mathcal{A}\subset[0,C_{1}]^{d}$ is a compact and convex set for some $C_{1}>0$.
Furthermore, assume that $\mu$ and $k$ are both $L$-Lipschitz on $\mathcal{A}$ and $\mathcal{A}\times\mathcal{A}$, respectively, for some $L>0$. In addition, for $f\sim\mathcal{GP}(\mu,k)$ assume that there exists constants $C_{2},C_{3}>0$ such that:

$$ $\mathbb{P}\left(\sup_{a\in\mathcal{A}}\left|\frac{\partial f}{\partial a^{(j)} }\right|>l\right)\leq C_{2}\exp\left(-\frac{l^{2}}{C_{3}^{2}}\right),$ (5) $$

for $j\in\{1,\ldots,d\}$ and $l>0$ where $a^{(j)}$ 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., ; Kandasamy et al., ; Takeno et al., ), we additionally require that both $\mu$ and $k$ are Lipschitz but this is not particularly restrictive, see Section A.2.

Following Srinivas et al. (), proofs for the compact case tend to use a discretization $\mathcal{D}_{t}\subset\mathcal{A}$ where each dimension is divided into $\tau_{t}$ points such that $|\mathcal{D}_{t}|=\tau_{t}^{d}$. Let $[a]_{\mathcal{D}_{t}}$ denote the nearest point in $\mathcal{D}_{t}$ for $a\in\mathcal{A}$ and similarly let $[\mathbf{a}]_{\mathcal{D}_{t}}=\{[a]_{\mathcal{D}_{t}}|a\in\mathbf{a}\}$ for $\mathbf{a}\subset\mathcal{A}$. Due to the assumption of volatile arms, we require the following finer discretization (as compared to , ):
{assumption}[Discretization size]
Let $\tau_{t}$ denote the number of discretization points per dimension and assume that

$$ $\displaystyle[left={\empheqlbrace}$ $\displaystyle\tau_{t}\geq 2t^{2}KLdC_{1}(1+tK\varsigma^{-1}),$ (6a) $\displaystyle\tau_{t}/\beta_{t}\geq 8t^{4}K^{2}LdC_{1},$ (6b) $\displaystyle\tau_{t}^{2}/\beta_{t}\geq 8t^{5}K^{3}L^{2}d^{2}C_{1}^{2} \varsigma^{-2},$ (6c) $\displaystyle\tau_{t}\geq t^{2}KdC_{1}C_{3}(\sqrt{\log(C_{2}d)}+\sqrt{\pi}/2)$ (6d) $$

where the constants $C_{1},C_{2},C_{3}$ and $L$ are given by Section 3.2 whilst the constants $d,K$ and $\varsigma$ are defined by the bandit problem (Section 2.1).
We note that Eq. 6d is equivalent to the discretization size used by Takeno et al. () with an extra factor of $K$ to account for the combinatorial setting whilst we introduce Eqs. 6a, 6b and 6c to bound $U_{t}([\mathbf{a}]_{\mathcal{D}_{t}})-U_{t}(\mathbf{a})$.
A key step to establish the regret bound of GP-UCB by Takeno et al. () is to use the fact (for that setting) that $\mathbf{a}_{t}$ maximizes the upper confidence bound $U_{t}(\mathbf{a})$ and thus $U_{t}([\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})-U_{t}(\mathbf{a}_{t})\leq 0$.
Since we consider a setting with volatile arms, $[\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}}$ is not necessarily a feasible super arm and our technical contribution in the infinite setting is an analysis of the discretization error of $U_{t}([\mathbf{a}]_{\mathcal{D}_{t}})-U_{t}(\mathbf{a})$.

[]
If $U_{t}(\mathbf{a})=\mu_{t-1}(\mathbf{a})+\sqrt{\beta_{t}}\sigma_{t-1}(\mathbf{a})$, Section 3.2 holds and $\tau_{t}$ and $\beta_{t}$ satisfy Eqs. 6a, 6b and 6c in Section 3.2, then for any sequence of super arms $\mathbf{a}_{t}\in\mathcal{S}_{t}$ $t\geq 1$:

$$ $\sum_{t\in[T]}\mathbb{E}\left[U_{t}([\mathbf{a}_{t}]_{\mathcal{D}_{t}})-U_{t}( \mathbf{a}_{t})\right]\leq\frac{\pi^{2}}{6}.$ (7) $$

To bound the difference in posterior mean, $\mu_{t-1}([\mathbf{a}]_{\mathcal{D}_{t}})-\mu_{t-1}(\mathbf{a})$, we Cholesky decompose $\mathbf{K}+\varsigma^{2}I=\mathbf{L}\mathbf{L}^{\top}$ and note that $||\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu})||_{2}$ has a chi distribution with at most $TK$ degrees of freedom. The difference in posterior standard deviation, $\sigma_{t-1}([\mathbf{a}]_{\mathcal{D}_{t}})-\sigma_{t-1}(\mathbf{a})$, is bounded by using that $k$ is Lipschitz, Section 3.2 and other smaller steps.

Next, we present our regret bounds for GP-UCB, GP-BUCB and GP-TS in the infinite setting:

###### Theorem 3.2 (Infinite regret bounds) .

If Section 3.2 holds and $\tau_{t}$ satisfies Section 3.2, then the Bayesian regret of

- (i)
GP-UCB with $\beta_{t}=2\log(\tau_{t}^{d}t^{2}/\sqrt{2\pi})$ is bounded as $\text{BR}(T)\leq\frac{\pi^{2}}{2}+\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}.$
- (ii)
GP-BUCB with $\beta_{t}=2\left(\operatorname{erf}^{-1}(1-2\eta_{t})\right)^{2}$ for $\eta_{t}=(2\pi)^{\omega/2}/\left(2\tau_{t}^{d\omega}t^{\xi}\right)$, $\xi>\omega>1$ is bounded as
$\text{BR}(T)\leq\frac{\pi^{2}}{3}+\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}+C_{\omega
}\cdot\frac{\xi}{\xi-\omega}$
where $C_{\omega}=\left(\sqrt{\pi}\omega/\sqrt{2e(\omega-1)}\right)^{1/\omega}$.
- (iii)
GP-TS is bounded as $\text{BR}(T)\leq\frac{2\pi^{2}}{3}+2\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}.$

The proofs are presented in Section A.2. Similar to Takeno et al. (), the regret is decomposed into multiple terms which are either bounded by the finite case or by using results such as Section 3.2. 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 $\text{BR}(T)=\mathcal{O}(\sqrt{\lambda^{*}_{K}TK\beta_{T}\gamma_{TK}})$ for all three algorithms which matches the non-combinatorial result of Takeno et al. () for $K=1$.

###### Theorem 3.2 (Infinite regret bounds) .

## 4 Experiments

In this section, we 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 Åkerblom et al. () introduced a framework based on Bayesian inference to address the online navigation problem when no contextual information is available. Bayesian combinatorial bandits allow us to combine imperfect initial estimates with exploration to 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-efficient navigation problem

Consider a directed graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ where the vertices $\mathcal{V}$ denote intersections of road segments and the edges $e=(u_{1},u_{2})\in\mathcal{E}$ denote the road segment from intersection $u_{1}$ to intersection $u_{2}$. Additionally, let $\mathcal{L}(\mathcal{G})=\mathcal{G}(\mathcal{E},\mathcal{C}_{t})$ denote the directed line graph of $\mathcal{G}$ where the set of connections $\mathcal{C}_{t}\subseteq\left\{(e_{1},e_{2})|e_{1}=(u,v)\in\mathcal{E},e_{2}=(
v,w)\in\mathcal{E}\right\}$ determine which turns are legal in the road network at time $t$.
Assume that we are given a start vertex $u_{1}\in\mathcal{V}$ and a goal vertex $u_{n}\in\mathcal{V}$. Let $\mathcal{P}_{t}$ denote the set of simple feasible paths from $u_{1}$ to $u_{n}$ at time $t$. A path $\mathbf{p}=\langle u_{1},u_{2},\ldots,u_{n}\rangle$ is legal if all the connections are legal, and $\mathbf{p}$ is simple if every vertex is visited at most once.
At each time step $t$, we observe the set of available paths $\mathcal{P}_{t}$ and a context vector $x_{t,e}\in\mathbb{R}^{d}$ for each edge $e\in\mathcal{E}$. The context $x_{t,e}$ can include static features, such as the length of the road segment, and time-varying features, such as the congestion level. Based on the available connections and the context vector, we select a path $\mathbf{p}_{t}\in\mathcal{P}_{t}$ and observe the energy consumption associated with each edge in the path (negated reward): $R_{t}=\sum_{e\in\mathbf{p}_{t}}r_{t,e}$. The goal of online energy-efficient navigation is to minimize the total energy consumed over a horizon $T$.
Note that the base arm set $\mathcal{A}_{t}$ corresponds to all edge-context tuples $(e,x_{t,e})$ and that the base arm space is defined as $\mathcal{A}=\mathcal{E}\times\mathcal{X}$ where $\mathcal{X}\subseteq[0,C_{1}]^{d}$ is a compact and convex set for some $C_{1}>0$. The super arm set $\mathcal{S}_{t}$ corresponds to sequences of edge-context tuples that form paths in $\mathcal{P}_{t}$.

Figure: Algorithm 2 Compute Rectified Indices

#### 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 energy-efficient path. The most common shortest path algorithm, Dijkstra’s algorithm (Dijkstra, ), does not permit negative edge weights. Whilst alternative shortest path algorithms, such as Bellman-Ford (Shimbel, ; Bellman, ; Ford, ), allow negative edge weights, they are significantly slower and do not return a path if 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 $U_{t,e}$ as input for Dijkstra’s algorithm.
Upper confidence bound methods output optimistic estimates $\tilde{\mu}_{e}\in\mathbb{R}$ whereas Thompson sampling outputs posterior estimates $\tilde{\mu}_{e}\in\mathbb{R}$ by sampling from the posterior $\mathcal{N}(\mu_{t-1,e},\sigma^{2}_{t-1,e})$. To ensure non-negative weights, the edge weight $U_{t,e}$ is set to $\mathbb{E}[z_{e}]$ where $z_{e}$ is distributed as the rectified Gaussian $\mathcal{N}^{R}(\tilde{\mu}_{e},\sigma^{2}_{t-1,e})$.
A random variable $Y=\max(0,X)$ is said to have a rectified Gaussian distribution $\mathcal{N}^{R}(\mu,\sigma^{2})$ if $X\sim\mathcal{N}(\mu,\sigma^{2})$.
In Algorithm 2, we show how to integrate UCB, BUCB and Thompson sampling with rectification within the framework of Algorithm 1.
The notation $\mu_{t-1,e}$ and $\sigma^{2}_{t-1,e}$ refer respectively to the posterior mean and variance of the expected energy consumption for edge $e$ whilst $\varsigma^{2}_{t-1,e}$ refers to the variance of the noise.
Since the number of edges $|\mathcal{E}|$ may be large, each edge is sampled independently in TS, as by Nuara et al. ().
Note that Algorithm 2 decouples the probabilistic regression model and Thompson sampling. In the next sections, we describe two probabilistic regression models for energy-efficient navigation.

Figure: Algorithm 3 SVGP Optimization Procedure

#### GP regression for energy-efficient navigation

To our knowledge, this study is the first combinatorial 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 $k_{G}:\mathcal{E}\times\mathcal{E}\rightarrow\mathbb{R}$ from Borovitskiy et al. () to encode the structure of the line graph $\mathcal{L}(\mathcal{G})$ into the GP and an ordinary $5/2$-Matérn kernel $k_{f}:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ to encode the dependence on the context. The two kernels are combined $k_{G\cdot f+f}=k_{G}\cdot k_{f}+k_{f}^{\prime}$
where the two feature kernels $k_{f}$ and $k_{f}^{\prime}$ use separate sets of lengthscale and outputscale parameters.
The cubic cost of exact GPs prohibits their application to large datasets. The sparse variational Gaussian processes (SVGP) (Titsias, ; Hensman et al., ) approximate the posterior distribution using a set of inducing points $\mathbf{Z}_{t}=\{z_{1},\ldots,z_{M}\}$ where $z_{i}\in\mathcal{A}$ and $M$ is significantly smaller than the number of datapoints. By defining a prior distribution $q(\mathbf{u}_{t})=\mathcal{N}(\mathbf{m}_{t},\mathbf{S}_{t})$ for the inducing variables $\mathbf{u}_{t}$, an approximate GP posterior can be obtained such that the complexity to perform $N$ predictions is $\mathcal{O}(M^{2}N)$, i.e. linear w.r.t. $N$.
The variational paramaters $(\mathbf{m}_{t},\mathbf{S}_{t})$ are optimized by minimizing the evidence lower bound (ELBO) by performing $G$ stochastic (natural) gradient descent steps using batch size $B$.
Since the inducing points $z_{i}$ lie in a mixed discrete and continuous space ($\mathcal{A}=\mathcal{E}\times\mathcal{X}$ for $\mathcal{X}\subset[0,C_{1}]^{d}$), we heuristically set $z_{i}$ equal to the edge-context tuple of the $i$-th most visited edge at the start of the SVGP optimization. Then, the continuous dimensions of $z_{i}$ are optimized together with $(\mathbf{m}_{t},\mathbf{S}_{t})$ using natural gradient descent (NGD) (Salimbeni et al., ).
The procedure is described in Algorithm 3. Further details of the kernels and parameter values are provided in Sections B.1 and B.3.

#### Bayesian inference for energy-efficient navigation

Åkerblom et al. () introduced a framework for energy-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 a Gaussian distribution with unknown mean and known variance. Additionally, it is assumed that the energy consumption along different edges is independent. Using a Gaussian prior, the posterior distribution for edge $e$ is computed using standard conjugate update rules.

Figure: Figure 1: Road networks of Luxembourg (left) and Monaco (right) with evaluation routes A and B highlighted in blue and red
Refer to caption: x1.png

#### Real-world road networks

In our experiments we use the road networks of Luxembourg and Monaco (, ; , , based on data by , ). Elevation data (Administration de la navigation
aérienne, ) is added to the network using QGIS and the netconvert tool from SUMO. In Fig. 1, the two road networks are 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 properties: the length, the speed limit and the incline. Each property is standardized to have unit-variance. The prior expected energy consumption is computed by a deterministic model that assumes that the vehicle drives along an edge $e\in\mathcal{E}$, with length $\ell_{e}$ and inclination $\alpha_{e}$, at constant speed $v_{e}$. The expended energy is then

$$ $E^{\textrm{det}}_{e}:=\frac{mg\ell_{e}\sin(\alpha_{e})+mgC_{r}\ell_{e}\cos( \alpha_{e})+0.5C_{d}A\rho\ell_{e}v_{e}^{2}}{3600\eta}.$ (8) $$

The deterministic energy consumption $E^{\textrm{det}}_{e}$ in Eq. 8 is given in Watt-hours and depends on the following vehicle-specific parameters: mass $m$, rolling resistance $C_{r}$, front surface area $A$, air drag coefficient $C_{d}$ and powertrain efficiency $\eta$. The gravitational acceleration $g$ and air density $\rho$ also determine $E^{\textrm{det}}_{e}$. The parameter values are specified in Table 2 in Section B.3. Let $\overline{E^{\textrm{det}}}=\frac{1}{|\mathcal{E}|}\sum_{e\in\mathcal{E}}E^{
\textrm{det}}_{e}$ and $\sigma^{\textrm{det}}=\sqrt{\frac{1}{|\mathcal{E}|}\sum_{e\in\mathcal{E}}(E^{
\textrm{det}}_{e}-\overline{E^{\textrm{det}}})^{2}}$ denote the mean and standard deviation of the deterministic energy consumption. The expected energy consumption is sampled from $\mathcal{GP}(E^{\textrm{det}},k_{G\cdot f+f})$ where the outputscale of $k_{G\cdot f+f}$ (i.e. the variance $\bm{\sigma}^{2}_{0}$) is set to $0.25^{2}\sigma^{\textrm{det}}$. The noise variance $\bm{\varsigma}^{2}$ is set to $0.1^{2}\sigma^{\textrm{det}}$ for all edges and the kernel lengthscales are set to $1$. See Appendix B for further details.

### 4.2 Results

Here, we demonstrate our 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, we study the impact of the kernel lengthscale. Visualizations of the exploration are provided in Section C.2.

#### Investigation of different bandit algorithms

In our first experiment, we compare the three algorithms GP-UCB, GP-BUCB and GP-TS. We use the Bayesian inference (BI) method of Åkerblom et al. () with UCB, BUCB and TS as baselines. For UCB and BUCB (GP and BI), we use the $\beta_{t}$ parametrization given by Theorem 3.1 with $\omega=1$, $\xi=1$. The six methods are evaluated 5 times 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.

Figure: 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 $\pm 1$ standard error.
Refer to caption: x3.png

#### BUCB parametrization

As discussed in Section 2.2, GP-UCB and GP-BUCB differ mainly in their parametrization of the confidence parameter $\beta_{t}$. The confidence parameter determines the balance between exploration and exploitation. It is known that theoretical results tend to provide $\beta_{t}$ values that overexplore (Russo & Roy, ). Using the parameters of $\beta_{t}$ for GP-BUCB ($\omega$ and $\xi$), we can tune GP-BUCB towards more exploitation whilst retaining theoretical guarantees. We compare two theoretically valid choices of parametrizations for GP-BUCB ($\omega=1$, $\xi=1$ and $\omega=1,\xi=0.5$) against two parametrizations of GP-UCB where the first is theoretically valid and the second has scaled $\beta_{t}$ by $0.5$. The four parametrizations are evaluated 5 times each on the four routes in the Luxembourg and Monaco networks with a horizon of $T=500$. The cumulative regret and the $\beta_{t}$ values are shown in Fig. 3. The theoretically valid $\beta_{t}$ values for GP-BUCB are smaller than for GP-UCB. By lowering $\xi$ from 1 to 0.5, the quantile parameter $\eta_{t}$ goes from $\mathcal{O}(t^{-1})$ to $\mathcal{O}(t^{-0.5})$ and using $\omega=1$ the theoretial cumulative regret remains $\mathcal{O}(\sqrt{T})$.(^1^11Technically, one must use $\xi\leq 0.5-\delta$ and $\omega\geq 1+\delta$ for some $\delta>0$. However, we could choose $\delta$ to be small enough such that GP-BUCB would select the exact same routes in all experiments.) The experimental results indicate that the parametrization with lower $\beta_{t}$ generally has lower cumulative regret. Using GP-BUCB, we gain more control of $\beta_{t}$ without sacrificing the theoretical guarantees.

Figure: Figure 3: Cumulative regret of GP-UCB and GP-BUCB (left and middle column) for different parametrizations of $\beta_{t}$ (right column).
Refer to caption: x4.png

#### Impact of lengthscale

Finally, we investigate varying the kernel lengthscale to ensure our results are consistent and stable. A large lengthscale increases the correlation between edges, which should lower the regret of the GP-methods. Whilst a 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 is evaluated 5 times on all four routes with a horizon of $T=500$. The final cumulative regret at $t=500$ for the different lengthscales is shown in Fig. 4 for Luxembourg A. For the full results, see Figs. 5 and 6 in Section C.1. For GP-based methods, increasing the lengthscale increases the cumulative regret overall but for BI-based methods, there is no discernable pattern.

Figure: Figure 4: Cumulative regret at $t=500$ for varying prior kernel lengthscale values $\ell$ on Luxembourg A. Errorbars correspond to $\pm 1$ standard error.

## 5 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.

## Acknowledgments

This work of Jack Sandberg and Morteza Haghir Chehreghani was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. The work of Niklas Åkerblom 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.

## Appendix 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.

[]
For GP-TS or any GP-UCB method the following upper bound on the Bayesian regret holds (with equality for GP-TS):

$$ $\text{BR}(T)\leq\sum_{t\in[T]}\mathbb{E}[f(\mathbf{a}_{t}^{*})-U_{t}(\mathbf{a }^{*}_{t})]+\mathbb{E}[U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_{t})].$ (9) $$

###### Proof.

The proof follows the procedure of Prop. 1 by Russo & Roy () for GP-TS and Thm. B.1. by Takeno et al. () for GP-UCB. For GP-TS,

$$ $\displaystyle\text{BR}(T)$ $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}_{t}^{*})-f(\mathbf{a} _{t})\right]$ (10) $\displaystyle=\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[f( \mathbf{a}^{*}_{t})-U_{t}(\mathbf{a}_{t}^{*})+U_{t}(\mathbf{a}_{t})-f(\mathbf{ a}_{t})|H_{t}\right]\right]$ $\displaystyle\left(\mathbf{a}_{t}^{*}|H_{t}\overset{d}{=}\mathbf{a}_{t}|H_{t}\right)$ (11) $\displaystyle=\sum_{t\in[T]}\mathbb{E}[f(\mathbf{a}^{*}_{t})-U_{t}(\mathbf{a}_ {t}^{*})]+\sum_{t\in[T]}\mathbb{E}[U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_{t})].$ (12) $$

Similarly, for any GP-UCB method,

$$ $\displaystyle\text{BR}(T)$ $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}_{t}^{*})-f(\mathbf{a} _{t})\right]$ (13) $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}^{*}_{t})-U_{t}( \mathbf{a}_{t}^{*})+U_{t}(\mathbf{a}_{t}^{*})-U_{t}(\mathbf{a}_{t})+U_{t}( \mathbf{a}_{t})-f(\mathbf{a}_{t})\right]$ (14) $\displaystyle\leq\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}^{*}_{t})-U_{t}( \mathbf{a}_{t}^{*})+U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_{t})\right]$ (15) $$

where the final step uses that $U_{t}(\mathbf{a}_{t}^{*})-U_{t}(\mathbf{a}_{t})\leq 0$ since $\mathbf{a}_{t}=\operatorname*{arg\,max}_{\mathbf{a}\in\mathcal{S}_{t}}U_{t}(
\mathbf{a})$.
∎

Whilst Section A.1 applies to all the considered bandit algorithms, the two terms in the decomposition requires knowing the specific bandit algorithm. Bounding the left term requires knowledge of the confidence parameter $\beta_{t}$. Therefore we present a lemma that applies to GP-UCB and GP-TS, and another lemma that applies to GP-BUCB.

[]
If $|\mathcal{A}|<\infty$, then

$$ $\sum_{t\in[T]}\mathbb{E}[f(\mathbf{a}_{t}^{*})-U_{t}(\mathbf{a}_{t}^{*})]\leq \frac{\pi^{2}}{6}$ (16) $$

holds for GP-UCB and GP-TS with $\beta_{t}=2\log\left(|\mathcal{A}|t^{2}/\sqrt{2\pi}\right)$.

###### Proof.

The proof closely follows the proof of Thm. B.1 by Takeno et al. (). Let $R_{1}=\sum_{t\in[T]}\mathbb{E}[f(\mathbf{a}_{t}^{*})-U_{t}(\mathbf{a}^{*}_{t})]$, then

$$ $\displaystyle R_{1}$ $\displaystyle=\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[f( \mathbf{a}_{t}^{*})-U_{t}(\mathbf{a}_{t}^{*})|H_{t}\right]\right]$ (17) $\displaystyle=\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[\sum_{ a\in\mathbf{a}_{t}^{*}}f(a)-U_{t}(a)\Bigg{|}H_{t}\right]\right]$ (18) $\displaystyle\leq\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[ \sum_{a\in\mathbf{a}_{t}^{*}}\left(f(a)-U_{t}(a)\right)_{+}\Bigg{|}H_{t}\right ]\right]$ $\displaystyle\left((x)_{+}:=\max(0,x)\geq x\right)$ (19) $\displaystyle\leq\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\sum_{a\in\mathcal{A}} \mathbb{E}_{t}\left[\left(f(a)-U_{t}(a)\right)_{+}\Bigg{|}H_{t}\right]\right].$ $\displaystyle\left(\mathbf{a}_{t}^{*}\subseteq\mathcal{A}\right)$ (20) $$

Note that $f(a)-U_{t}(a)|H_{t}\sim\mathcal{N}(-\sqrt{\beta_{t}}\sigma_{t-1}(a),\sigma^{2}
_{t-1}(a))$. As Russo & Roy (), by using that if $X\sim\mathcal{N}(\mu,\sigma^{2})$ for $\mu\leq 0$, then $\mathbb{E}[(X)_{+}]\leq\frac{\sigma}{\sqrt{2\pi}}\exp\left(\frac{-\mu^{2}}{2
\sigma^{2}}\right)$, we get the following for $R_{1}$:

$$ $\displaystyle R_{1}$ $\displaystyle\leq\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\sum_{a\in\mathcal{A}} \mathbb{E}_{t}\left[\frac{\sigma_{t-1}(a)}{\sqrt{2\pi}}\exp\left(\frac{-\beta_ {t}}{2}\right)\Bigg{|}H_{t}\right]\right]$ (21) $\displaystyle\leq\sum_{t\in[T]}\frac{|\mathcal{A}|}{\sqrt{2\pi}}\exp\left( \frac{-\beta_{t}}{2}\right)$ $\displaystyle\left(\sigma^{2}_{t-1}(a)\leq k(a,a)\leq 1\right)$ (22) $\displaystyle\leq\sum_{t\in[T]}\frac{1}{t^{2}}$ $\displaystyle\left(\beta_{t}=2\log(|\mathcal{A}|t^{2}/\sqrt{2\pi}\right)$ (23) $\displaystyle\leq\frac{\pi^{2}}{6}.$ $\displaystyle\left(\sum_{t=1}^{\infty}\frac{1}{t^{2}}=\frac{\pi^{2}}{6}\right)$ (24) $$

∎

See 3.1

###### Proof.

Following the proof of Section A.1, we get that

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}_{t}^{*})-U_{t}(\mathbf {a}^{*}_{t})\right]\leq\sum_{t\in[T]}\frac{|\mathcal{A}|}{\sqrt{2\pi}}\exp \left(-\frac{\beta_{t}}{2}\right).$ (25) $$

Note that, according to Eq. 130, $\operatorname{erf}^{-1}(u)\geq\sqrt{-\omega^{-1}\log((1-u)/\vartheta})$ for $\omega>1$ and $\vartheta=\sqrt{2e/\pi}\sqrt{\omega-1}/\omega$. We use the largest value of $\vartheta$ permitted by Eq. 130 since it yields the tightest bound.
Then,

$$ $\displaystyle\sum_{t\in[T]}\frac{|\mathcal{A}|}{\sqrt{2\pi}}\exp\left(-\frac{ \beta_{t}}{2}\right)$ $\displaystyle=\sum_{t\in[T]}\frac{|\mathcal{A}|}{\sqrt{2\pi}}\exp\left(-\left( \operatorname{erf}^{-1}(1-2\eta_{t})\right)^{2}\right)$ (26) $\displaystyle\leq\sum_{t\in[T]}\frac{|\mathcal{A}|}{\sqrt{2\pi}}\exp\left( \omega^{-1}\log\left(\frac{1-(1-2\eta_{t})}{\vartheta}\right)\right)$ $\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:erfInvLB}}\right)$ (27) $\displaystyle=\sum_{t\in[T]}\frac{|\mathcal{A}|}{\sqrt{2\pi}}\left(\frac{2\eta _{t}}{\vartheta}\right)^{\frac{1}{\omega}}$ (28) $\displaystyle=\sum_{t\in[T]}\vartheta^{-\frac{1}{\omega}}t^{-\frac{\xi}{\omega}}$ $\displaystyle\left(\text{Def. of }\eta_{t}\right)$ (29) $\displaystyle=\left(\frac{\sqrt{\pi}\omega}{\sqrt{2e(\omega-1)}}\right)^{\frac {1}{\omega}}\sum_{t\in[T]}t^{-\frac{\xi}{\omega}}.$ $\displaystyle\left(\text{Def. of }\vartheta\right)$ (30) $$

The behaviour of $\sum_{t\in[T]}t^{-\frac{\xi}{\omega}}$ critically depends on the ratio $\xi/\omega$. First, if $\xi/\omega<1$, then

$$ $\sum_{t\in[T]}t^{-\frac{\xi}{\omega}}\leq\int_{0}^{T}t^{-\frac{\xi}{\omega}} \textrm{d}t=T^{1-\frac{\xi}{\omega}}\frac{1}{1-\frac{\xi}{\omega}}.$ (31) $$

Second, if $\xi/\omega=1$, then

$$ $\sum_{t\in[T]}t^{-1}\leq 1+\int_{1}^{T}t^{-1}dt=1+\log T.$ (32) $$

Finally, if $\xi/\omega>1$, then

$$ $\sum_{t\in[T]}t^{-\frac{\xi}{\omega}}\leq 1+\int_{1}^{\infty}t^{-\frac{\xi}{ \omega}}\textrm{d}t=1+\left[\frac{1}{1-\frac{\xi}{\omega}}t^{1-\frac{\xi}{ \omega}}\right]_{1}^{\infty}=1-\frac{1}{1-\frac{\xi}{\omega}}=\frac{\xi}{\xi- \omega}.$ (33) $$

∎

Before we bound the right term in Section A.1, we introduce a lemma for the confidence radius that applies to all the bandit algorithms considered.

[]

$$ $\sum_{t\in[T]}\mathbb{E}\left[\sum_{a\in\mathbf{a}_{t}}\sqrt{\beta_{t}}\sigma_ {t-1}(a)\right]\leq\sqrt{2(\lambda^{*}_{K}+\varsigma^{2})TK\beta_{T}\gamma_{TK}}$ (34) $$

for GP-TS or any GP-UCB method with increasing confidence parameter $\beta_{t}$.

###### Proof.

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}\left[\sum_{a\in\mathbf{a}_{t}}\sqrt{ \beta_{t}}\sigma_{t-1}(a)\right]$ (35) $\displaystyle=\mathbb{E}\left[\sum_{t\in[T]}\sum_{a\in\mathbf{a}_{t}}\sqrt{ \beta_{t}}\sigma_{t-1}(a)\right]$ (36) $\displaystyle\leq\mathbb{E}\left[\sqrt{\sum_{t\in[T]}\sum_{a\in\mathbf{a}_{t}} \beta_{t}}\sqrt{\sum_{t\in[T]}\sum_{a\in\mathbf{a}_{t}}\sigma^{2}_{t-1}(a)}\right]$ $\displaystyle\left(\text{Cauchy-Schwarz inequality}\right)$ (37) $\displaystyle\leq\mathbb{E}\left[\sqrt{TK\beta_{T}}\sqrt{\sum_{t\in[T]}\sum_{a \in\mathbf{a}_{t}}\sigma^{2}_{t-1}(a)}\right]$ $\displaystyle\left(|\mathbf{a}_{t}|\leq K,\max_{t\in[T]}\beta_{t}=\beta_{T}\right)$ (38) $\displaystyle=\sqrt{TK\beta_{T}}\mathbb{E}\left[\sqrt{\sum_{t\in[T]}\sum_{a\in \mathbf{a}_{t}}\sigma^{2}_{t-1}(a)}\right]$ (39) $\displaystyle\leq\sqrt{TK\beta_{T}}\mathbb{E}\left[\sqrt{2(\lambda^{*}_{K}+ \varsigma^{2})\gamma_{TK}}\right]$ $\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:infogain}}\right)$ (40) $\displaystyle\leq\sqrt{2(\lambda^{*}_{K}+\varsigma^{2})TK\beta_{T}\gamma_{TK}}.$ (41) $$

∎

Next, we show how the right term in Section A.1 can be rewritten in terms of the confidence radius for any GP-UCB method.

[]

$$ $\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_{t})\right]= \sum_{t\in[T]}\mathbb{E}\left[\sqrt{\beta_{t}}\sigma_{t-1}(\mathbf{a}_{t})\right]$ (42) $$

for any GP-UCB method with confidence parameter $\beta_{t}$.

###### Proof.

Note that given the history $H_{t}$, $\mathbf{a}_{t}:=\operatorname*{arg\,max}_{\mathbf{a}\in\mathcal{S}_{t}}U_{t}(
\mathbf{a})$ is deterministic. Thus,

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_ {t})\right]$ $\displaystyle=\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[U_{t}( \mathbf{a}_{t})-f(\mathbf{a}_{t})|H_{t}\right]\right]$ (43) $\displaystyle=\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[\mu_{t -1}(\mathbf{a}_{t})+\sqrt{\beta_{t}}\sigma_{t-1}(\mathbf{a}_{t})-f(\mathbf{a}_ {t})\Big{|}H_{t}\right]\right]$ (44) $\displaystyle=\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[\mu_{t -1}(\mathbf{a}_{t})+\sqrt{\beta_{t}}\sigma_{t-1}(\mathbf{a}_{t})-\mu_{t-1}( \mathbf{a}_{t})\Big{|}H_{t}\right]\right]$ (45) $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[\sqrt{\beta_{t}}\sigma_{t-1}( \mathbf{a}_{t})\right].$ (46) $$

∎

For the final lemma in the finite case, we bound the right term in Section A.1 for Thompson sampling using the previous results.

[]

$$ $\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_{t})\right] \leq 2\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}+\frac{\pi^{2}}{6}$ (47) $$

holds for GP-TS with $\beta_{t}=2\log\left(|\mathcal{A}|t^{2}/\sqrt{2\pi}\right)$.

###### Proof.

By adding and subtracting the lower bound $L(\mathbf{a}_{t})$, we obtain

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_ {t})\right]$ $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})-f(\mathbf{a} _{t})+L(\mathbf{a}_{t})-L(\mathbf{a}_{t})\right]$ (48) $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})-L(\mathbf{a} _{t})\right]+\sum_{t\in[T]}\mathbb{E}\left[L(\mathbf{a}_{t})-f(\mathbf{a}_{t})\right]$ (49) $\displaystyle=2\underbrace{\sum_{t\in[T]}\mathbb{E}\left[\sqrt{\beta_{t}} \sigma_{t-1}(\mathbf{a}_{t})\right]}_{(1)}+\underbrace{\sum_{t\in[T]}\mathbb{E }\left[L(\mathbf{a}_{t})-f(\mathbf{a}_{t})\right]}_{(2)}.$ (50) $$

By Section A.1, $(1)\leq\sqrt{2(\lambda^{*}_{K}+\varsigma^{2})TK\beta_{T}\gamma_{TK}}$. The bound $(2)\leq\frac{\pi^{2}}{6}$ is obtained using the same steps as in Section A.1 due to the symmetry of $L(\mathbf{a}_{t})-f(\mathbf{a}_{t})$ and $f(\mathbf{a}_{t})-U(\mathbf{a}_{t})$.
∎

Finally, we present and prove the regret bounds for GP-UCB, GP-BUCB and GP-TS using the established lemmas.

See 3.1

###### Proof.

- (i)
The regret bound for GP-UCB is obtained as follows:
$\displaystyle\text{BR}(T)$
$\displaystyle\leq\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}_{t}^{*})-U_{t}(
\mathbf{a}_{t}^{*})\right]+\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})
-f(\mathbf{a}_{t})\right]$
$\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:BRDecomposition}}\right)$
(51)
$\displaystyle\leq\frac{\pi^{2}}{6}+\sum_{t\in[T]}\mathbb{E}\left[\sqrt{\beta_{
t}}\sigma_{t-1}(\mathbf{a}_{t})\right]$
$\displaystyle\left(\text{\lx@cref{creftypeplural~refnum}{lem:fMinusUStarFinite
UpperBound} and~\lx@cref{refnum}{lem:UMinusfUCB}}\right)$
(52)
$\displaystyle\leq\frac{\pi^{2}}{6}+\sqrt{2(\lambda^{*}_{K}+\varsigma^{2})TK
\beta_{T}\gamma_{TK}}.$
$\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:expectedPosteriorStd}}\right)$
(53)
- (ii)
The regret of GP-BUCB can be decomposed as follows:
$\displaystyle\text{BR}(T)$
$\displaystyle\leq\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})-f(\mathbf
{a}_{t})\right]+\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}_{t}^{*})-U_{t}(
\mathbf{a}_{t}^{*})\right]$
$\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:BRDecomposition}}\right)$
(54)
$\displaystyle\leq\sum_{t\in[T]}\mathbb{E}\left[\sqrt{\beta_{t}}\sigma_{t-1}(
\mathbf{a}_{t})\right]$
$\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:UMinusfUCB}}\right)$
(55)
$\displaystyle+\left(\frac{\sqrt{\pi}\omega}{\sqrt{2e(\omega-1)}}\right)^{1/
\omega}\cdot\begin{cases}\frac{\omega}{\omega-\xi}T^{1-\frac{\xi}{\omega}}
\quad&\text{if }\xi/\omega<1,\\
\frac{\xi}{\xi-\omega}\quad&\text{if }\xi/\omega>1.\end{cases}$
$\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:fMinusUStarBayesUCB}}\right)$
(56)
From Section A.1, $\sum_{t\in[T]}\mathbb{E}\left[\sqrt{\beta_{t}}\sigma_{t-1}(\mathbf{a}_{t})
\right]\leq\sqrt{2(\lambda^{*}_{K}+\varsigma^{2})TK\beta_{T}\gamma_{TK}}$ and we obtain the desired result.
- (iii)
The regret of GP-TS is obtained as follows:
$\displaystyle\text{BR}(T)$
$\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}_{t}^{*})-U_{t}(
\mathbf{a}_{t}^{*})\right]+\sum_{t\in[T]}\mathbb{E}\left[U_{t}(\mathbf{a}_{t})
-f(\mathbf{a}_{t})\right]$
$\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:BRDecomposition}}\right)$
(57)
$\displaystyle\leq\frac{\pi^{2}}{6}+\frac{\pi^{2}}{6}+2\sqrt{C_{K}TK\beta_{T}
\gamma_{TK}}.$
$\displaystyle\left(\text{\lx@cref{creftypeplural~refnum}{lem:fMinusUStarFinite
UpperBound} and~\lx@cref{refnum}{lem:UMinusfThompson}}\right)$
(58)

∎

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

### 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:

See 3.2
{remark}
By Thm. 5 of Ghosal & Roy (), the high probability bound holds if $\mu$ is continuously differentiable and $k$ is 4 times differentiable, which would also imply the Lipschitzness of $\mu$ and $k$. As discussed by Srinivas et al. (), this holds for the Matérn kernel if $\nu\geq 2$ by a result of Stein () and holds trivially for the squared exponential kernel. Thus, the Lipschitz assumption of $\mu$ and $k$ is not particularly restrictive.
See 3.2

For the theorems to be relevant, the assumptions imposed on $\tau_{t}$ must be satisfiable for some $\tau_{t}$.
If $\beta_{t}=2\log\left(\frac{\tau_{t}^{d}t^{2}}{\sqrt{2\pi}}\right)$, then Section 3.2 is satisfied by

$$ $\tau_{t}=\max\begin{cases}2KLdC_{1}(1+tK\varsigma^{-1})t^{2},\\ \left(\left(16t^{4}K^{2}LdC_{1}\right)\left(d+\log\left(\frac{t^{2}}{\sqrt{2 \pi}}\right)\right)\right)^{\frac{1}{1-1/e}},\\ \left(\left(16t^{5}K^{3}L^{2}d^{2}C_{1}^{2}\varsigma^{-2}\right)\left(d+\log \left(\frac{t^{2}}{\sqrt{2\pi}}\right)\right)\right)^{\frac{1}{2-1/e}},\\ t^{2}KdC_{1}C_{3}\left(\sqrt{\log(C_{2}d)}+\frac{\sqrt{\pi}}{2}\right).\end{cases}$ (59) $$

This can be shown by noting that $\log\tau_{t}\leq\sqrt[e]{\tau_{t}}$ and $1\leq\sqrt[e]{\tau_{t}}$ and then deriving that $\frac{1}{\beta_{t}}\geq\frac{1}{\tau_{t}^{1/e}(d+\log(t^{2}/\sqrt{2\pi})}$.

Similarly, if $\beta_{t}=2\left(\operatorname{erf}^{-1}\left(1-2\eta_{t}\right)\right)^{2}$ and $\eta_{t}=\frac{\sqrt{2\pi}^{\omega}}{2\tau_{t}^{d\omega}t^{\xi}}$, $\omega>1$, then Section 3.2 is satisfied by

$$ $\tau_{t}=\max\begin{cases}2t^{2}KLdC_{1}(1+tK\varsigma^{-1}),\\ \left(\left(16t^{4}K^{2}LdC_{1}\right)\left(d\omega+\log\left(\frac{t^{\xi}}{2 \sqrt{2\pi}^{\omega}}\right)\right)\right)^{\frac{1}{1-1/e}},\\ \left(\left(16t^{5}K^{3}L^{2}d^{2}C_{1}^{2}\varsigma^{-2}\right)\left(d\omega+ \log\left(\frac{t^{\xi}}{2\sqrt{2\pi}^{\omega}}\right)\right)\right)^{\frac{1} {2-1/e}},\\ t^{2}KdC_{1}C_{3}\left(\sqrt{\log(C_{2}d)}+\frac{\sqrt{\pi}}{2}\right).\end{cases}$ (60) $$

This is shown similarly as before but using Eq. 131 to upper bound $\operatorname{erf}^{-1}(1-2\eta_{t})$ in $\beta_{t}$.

Next, we present a lemma that bounds the discretization error of the expected reward of optimal super arm.

[]
Let $\mathcal{D}_{t}\subset\mathcal{A}$ be a finite discretization with each dimension equally divided into $\tau_{t}=t^{2}KdC_{1}C_{3}\left(\sqrt{\log(C_{2}d)}+\sqrt{\pi}/2\right)$ such that $|\mathcal{D}_{t}|=\tau_{t}^{d}$. Then,

$$ $\sum_{t\in[T]}\mathbb{E}\left[f(\mathbf{a}_{t}^{*})-f([\mathbf{a}_{t}^{*}]_{ \mathcal{D}_{t}})\right]\leq\frac{\pi^{2}}{6}.$ (61) $$

###### Proof.

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}[f(\mathbf{a}_{t}^{*})-f([\mathbf{a}_{t}^ {*}]_{\mathcal{D}_{t}})]$ $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[\sum_{a\in\mathbf{a}^{*}_{t}}f(a)- f([a]_{\mathcal{D}_{t}})\right]$ (62) $\displaystyle\leq K\sum_{t\in[T]}\mathbb{E}\left[\sup_{a\in\mathcal{A}}f(a)-f( [a]_{\mathcal{D}_{t}})\right]$ $\displaystyle\left(|\mathbf{a}_{t}^{*}|\leq K\right)$ (63) $\displaystyle\leq K\sum_{t\in[T]}\frac{1}{Kt^{2}}$ $\displaystyle\left(\parbox{80.00012pt}{ Lemma H.2 of \cite[citet]{\@@bibref{Au thors Phrase1YearPhrase2}{takeno_randomized_2023}{\@@citephrase{(}}{ \@@citephrase{)}}} with $u_{t}=Kt^{2}$}\right)$ (64) $\displaystyle\leq\frac{\pi^{2}}{6}$ $\displaystyle\left(\sum_{t=1}^{\infty}\frac{1}{t^{2}}=\frac{\pi^{2}}{6}\right)$ (65) $$

∎

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.

[]
Let $\mu_{t-1}$ and $\sigma_{t-1}$ denote the posterior mean and standard deviation of $\mathcal{GP}(\mu,k)$ after sampling $N_{t-1}$ base arms. If $a\in\mathcal{A}$, then

$$ $\mu_{t-1}([a]_{\mathcal{D}_{t}})-\mu_{t-1}(a)\leq L\frac{dC_{1}}{\tau_{t}}+L \frac{dC_{1}}{\tau_{t}}\sqrt{N_{t-1}}\varsigma^{-1}\sqrt{\|\mathbf{L}^{-1}( \mathbf{y}-\bm{\mu})\|_{2}^{2}}$ (66) $$

and

$$ $\sigma_{t-1}([a]_{\mathcal{D}_{t}})-\sigma_{t-1}(a)\leq\sqrt{L\frac{dC_{1}}{ \tau_{t}}+N_{t-1}L^{2}\left(\frac{dC_{1}}{\tau_{t}}\right)^{2}\varsigma^{-2}}$ (67) $$

for $L-$Lipschitz $\mu$ and $k$ where $\mathbf{L}$ is the Cholesky decomposition of $\mathbf{K}+\varsigma^{2}I$ and $\|\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu})\|_{2}^{2}\sim\chi^{2}$ with $N_{t-1}$ degrees of freedom.

###### Proof.

Consider first the difference in posterior mean:

$$ $\displaystyle\mu_{t-1}([a]_{\mathcal{D}_{t}})-\mu_{t-1}(a)$ (68) $\displaystyle=\mu([a]_{\mathcal{D}_{t}})-\mu(a)+\left(\mathbf{k}([a]_{\mathcal {D}_{t}})-\mathbf{k}(a)\right)^{\top}\left(\mathbf{K}+\varsigma^{2}I\right)^{- 1}\left(\mathbf{y}-\bm{\mu}\right)$ (69) $\displaystyle\leq L\sup_{a\in\mathcal{A}}\|a-[a]_{\mathcal{D}_{t}}\|_{1}+\left \|\left(\mathbf{k}([a]_{\mathcal{D}_{t}})-\mathbf{k}(a)\right)^{\top}(\mathbf{ K}+\varsigma^{2}I)^{-1}(\mathbf{y}-\bm{\mu})\right\|_{2}$ $\displaystyle\left(\mu\text{ }L\text{-Lipschitz}\right)$ (70) $\displaystyle\leq L\frac{dC_{1}}{\tau_{t}}+\left\|\left(\mathbf{k}([a]_{ \mathcal{D}_{t}})-\mathbf{k}(a)\right)^{\top}(\mathbf{K}+\varsigma^{2}I)^{-1}( \mathbf{y}-\bm{\mu})\right\|_{2}$ (71) $$

where the last step uses that $\sup_{a\in\mathcal{A}}\|a-[a]_{\mathcal{D}_{t}}\|_{1}\leq\frac{dC_{1}}{\tau_{t}}$.

Next, we will appropriately split the norm into a product of norms and bound the individual factors. Let $\mathbf{K}+\varsigma^{2}I=\mathbf{L}\mathbf{L}^{\top}$ denote the Cholesky decomposition. Note that $\mathbf{y}-\bm{\mu}\sim\mathcal{N}(0,\mathbf{K}+\varsigma^{2}I)$. Then, $\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu})\sim\mathcal{N}(0,\mathbf{L}^{-1}\mathbf{L
}\mathbf{L}^{\top}(\mathbf{L}^{-1})^{\top})=\mathcal{N}(0,I)$ and thus $\|\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu})\|_{2}$ has a chi distribution with $N_{t-1}$ degrees of freedom.

Let $\operatorname*{eig}(A)$ denote the set of eigenvalues of the square matrix $A$. The matrix norm of the inverted Cholesky decomposition $\mathbf{L}^{-1}$ can be bounded as:

$$ $\displaystyle\|\mathbf{L}^{-1}\|_{2}$ $\displaystyle=\sqrt{\max\operatorname*{eig}\left((\mathbf{L}^{-1})^{\top} \mathbf{L}^{-1}\right)}$ $\displaystyle\left(\parbox{100.00015pt}{Eq. $(538)$ of \cite[citet]{\@@bibref{ Authors Phrase1YearPhrase2}{petersen_matrix_2012}{\@@citephrase{(}}{ \@@citephrase{)}}}}\right)$ (72) $\displaystyle=\sqrt{\max\operatorname*{eig}\left((\mathbf{K}+\varsigma^{2}I)^{ -1}\right)}$ (73) $\displaystyle=\sqrt{\max\frac{1}{\operatorname*{eig}\left(\mathbf{K}+\varsigma ^{2}I\right)}}$ (74) $\displaystyle=\sqrt{\max\frac{1}{\operatorname*{eig}\left(\mathbf{K}\right)+ \varsigma^{2}}}\leq\sqrt{\frac{1}{\varsigma^{2}}}\leq\frac{1}{\varsigma}.$ $\displaystyle\left(\mathbf{K}\text{ p.s.d.},\varsigma>0\right)$ (75) $$

Similarly, we also get that

$$ $\|(\mathbf{K}+\varsigma^{2}I)^{-1}\|_{2}\leq\varsigma^{-2}.$ (76) $$

The kernel difference can be bounded as follows:

$$ $\displaystyle\|\mathbf{k}([a]_{\mathcal{D}_{t}})-\mathbf{k}(a)\|_{2}$ $\displaystyle=\sqrt{\sum_{i=1}^{N_{t-1}}\left(k([a]_{\mathcal{D}_{t}},x_{i})-k (a,x_{i})\right)^{2}}$ (77) $\displaystyle\leq\sqrt{\sum_{i=1}^{N_{t-1}}L^{2}\left(\frac{dC_{1}}{\tau_{t}} \right)^{2}}\leq L\frac{dC_{1}}{\tau_{t}}\sqrt{N_{t-1}}$ (78) $$

where we use the fact that $k$ is $L$-Lipschitz. Applying Cauchy-Schwarz and the obtained bounds, we find that

$$ $\mu_{t-1}([a]_{\mathcal{D}_{t}})-\mu_{t-1}(a)\leq L\frac{dC_{1}}{\tau_{t}}+L \frac{dC_{1}}{\tau_{t}}\sqrt{N_{t-1}}\varsigma^{-1}\|\mathbf{L}^{-1}(\mathbf{y }-\bm{\mu})\|_{2}.$ (79) $$

The posterior standard deviation is bounded similarly:

$$ $\displaystyle\sigma_{t-1}([a]_{\mathcal{D}_{t}})-\sigma_{t-1}(a)\leq\sqrt{ \left|\sigma_{t-1}^{2}([a]_{\mathcal{D}_{t}})-\sigma_{t-1}^{2}(a)\right|}.$ (80) $$

Continuing,

$$ $\displaystyle\left|\sigma_{t-1}^{2}([a]_{\mathcal{D}_{t}})-\sigma_{t-1}^{2}(a)\right|$ (81) $\displaystyle=\Big{|}k([a]_{\mathcal{D}_{t}},[a]_{\mathcal{D}_{t}})-k(a,a)+ \left(\mathbf{k}([a]_{\mathcal{D}_{t}})-\mathbf{k}(a)\right)^{\top}\left( \mathbf{K}+\varsigma^{2}I)\right)^{-1}\left(\mathbf{k}([a]_{\mathcal{D}_{t}})- \mathbf{k}(a)\right)\Big{|}$ (82) $\displaystyle\leq\left|k([a]_{\mathcal{D}_{t}},[a]_{\mathcal{D}_{t}})-k(a,a) \right|+\left|\left(\mathbf{k}([a]_{\mathcal{D}_{t}})-\mathbf{k}(a)\right)^{ \top}\left(\mathbf{K}+\varsigma^{2}I)\right)^{-1}\left(\mathbf{k}([a]_{ \mathcal{D}_{t}})-\mathbf{k}(a)\right)\right|$ (83) $\displaystyle\leq L\frac{dC_{1}}{\tau_{t}}+\left\|\mathbf{k}([a]_{\mathcal{D}_ {t}})-\mathbf{k}(a)\right\|_{2}^{2}\left\|(\mathbf{K}+\varsigma^{2}I)^{-1} \right\|_{2}$ (84) $\displaystyle\leq L\frac{dC_{1}}{\tau_{t}}+\left(L\frac{dC_{1}}{\tau_{t}}\sqrt {N_{t-1}}\right)^{2}\varsigma^{-2}.\hskip 140.00021pt\left(\text{\lx@cref{ creftypeplural~refnum}{eq:inverseGramNorm} and~\lx@cref{refnum}{eq:kernelDiscr etizationError}}\right)$ (85) $$

Combining the above, the final bound is:

$$ $\sigma_{t-1}([a]_{\mathcal{D}_{t}})-\sigma_{t-1}(a)\leq\sqrt{L\frac{dC_{1}}{ \tau_{t}}+N_{t-1}\left(L\frac{dC_{2}}{\tau_{t}}\right)^{2}\varsigma^{-2}}.$ (86) $$

∎

Using Section A.2, we are ready to construct a constant bound for the expected discretization error of the posterior mean:
{lemma}[]
If Section 3.2 holds and $\tau_{t}$ satisfies Eq. 6a in Section 3.2, then for any sequence of super arms $\mathbf{a}_{t}\in\mathcal{S}_{t}$ $t\geq 1$, the posterior mean $\mu_{t-1}(\mathbf{a})$ satisfies

$$ $\sum_{t\in[T]}\mathbb{E}\left[\mu_{t-1}([\mathbf{a}_{t}]_{\mathcal{D}_{t}})- \mu_{t-1}(\mathbf{a}_{t})\right]\leq\frac{\pi^{2}}{12}.$ (87) $$

###### Proof.

Note that the assumption on $\tau_{t}$ is equivalent to $KL\frac{dC_{1}}{\tau_{t}}(1+tK\varsigma^{-1})\leq\frac{1}{2t^{2}}$. Then, we can bound the discretization error of the posterior mean as follows:

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}\left[\sum_{a\in\mathbf{a}_{t}}\mu_{t-1}( [a]_{\mathcal{D}_{t}})-\mu_{t-1}(a)\right]$ (88) $\displaystyle\leq\sum_{t\in[T]}\mathbb{E}\left[K\sup_{a\in\mathcal{A}}\left[ \mu_{t-1}([a]_{\mathcal{D}_{t}})-\mu_{t-1}(a)\right]\right]$ $\displaystyle\left(|\mathbf{a}_{t}|\leq K\right)$ (89) $\displaystyle\leq\sum_{t\in[T]}\mathbb{E}\left[K\sup_{a\in\mathcal{A}}L\frac{ dC_{1}}{\tau_{t}}\left(1+\sqrt{tK}\varsigma^{-1}\sqrt{\|\mathbf{L}^{-1}( \mathbf{y}-\bm{\mu})\|_{2}^{2}}\right)\right]$ $\displaystyle\left(\parbox{80.00012pt}{\lx@cref{creftype~refnum}{lem:posterior DiscretizationError} and $N_{t-1}<tK$}\right)$ (90) $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[KL\frac{dC_{1}}{\tau_{t}}\left(1+ \sqrt{tK}\varsigma^{-1}\sqrt{\|\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu})\|_{2}^{2}} \right)\right]$ $\displaystyle\left(\parbox{80.00012pt}{$\mathbf{L}^{-1},\mathbf{y},\bm{\mu}$ independent of $a$}\right)$ (91) $\displaystyle=\sum_{t\in[T]}KL\frac{dC_{1}}{\tau_{t}}\left(1+\sqrt{tK} \varsigma^{-1}\mathbb{E}\left[\sqrt{\|\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu})\|_{ 2}^{2}}\right)\right]$ (92) $\displaystyle\leq\sum_{t\in[T]}KL\frac{dC_{1}}{\tau_{t}}\left(1+\sqrt{tK} \varsigma^{-1}\sqrt{\mathbb{E}\left[\|\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu})\|_{ 2}^{2}\right]}\right)$ $\displaystyle\left(\parbox{70.0001pt}{Concave Jensen's inequality}\right)$ (93) $\displaystyle=\sum_{t\in[T]}KL\frac{dC_{1}}{\tau_{t}}\left(1+tK\varsigma^{-1}\right)$ $\displaystyle\left(\parbox{80.00012pt}{$\|\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu}) \|_{2}^{2}\sim\chi^{2}$ with at most $(t-1)K$ d.o.f.}\right)$ (94) $\displaystyle\leq\sum_{t\in[T]}\frac{1}{2t^{2}}$ $\displaystyle\left(\text{Assumption on }\tau_{t}\right)$ (95) $\displaystyle\leq\frac{\pi^{2}}{12}.$ $\displaystyle\left(\sum_{t=1}^{\infty}\frac{1}{t^{2}}=\frac{\pi^{2}}{6}\right)$ (96) $$

See the proof of Section A.2 for the motivation that $\|\mathbf{L}^{-1}(\mathbf{y}-\bm{\mu})\|_{2}^{2}\sim\chi^{2}$.
∎

Similar to Section A.2, we establish a constant bound for the discretization error of the posterior standard deviation:

[]
If Section 3.2 holds; $\tau_{t}$ and $\beta_{t}$ satisfy Eqs. 6b and 6c in Section 3.2
then, for any sequence of super arms $\mathbf{a}_{t}\in\mathcal{S}_{t}$ $t\geq 1$, the posterior standard deviation $\sigma_{t-1}(\mathbf{a})$ satisfies

$$ $\sum_{t\in[T]}\mathbb{E}\left[\sqrt{\beta_{t}}\left(\sigma_{t-1}([\mathbf{a}_{ t}]_{\mathcal{D}_{t}})-\sigma_{t-1}(\mathbf{a}_{t})\right)\right]\leq\frac{\pi ^{2}}{12}.$ (97) $$

###### Proof.

Note that Eqs. 6b and 6c are equivalent to

$$ $\beta_{t}K^{2}L\frac{dC_{1}}{\tau_{t}}\leq\frac{1}{8t^{4}}\text{ and }\beta_{t }tK^{3}L^{2}\frac{d^{2}C_{1}^{2}}{\tau_{t}^{2}}\varsigma^{-2}\leq\frac{1}{8t^{ 4}}.$ (98) $$

Then,

$$ $\displaystyle\sum_{t\in[T]}\mathbb{E}\left[\sqrt{\beta_{t}}\left(\sigma_{t-1}( [\mathbf{a}]_{\mathcal{D}_{t}})-\sigma_{t-1}(\mathbf{a})\right)\right]$ (99) $\displaystyle=\sum_{t\in[T]}\mathbb{E}\left[\sum_{a\in\mathbf{a}}\sqrt{\beta_{ t}}\left(\sigma_{t-1}([a]_{\mathcal{D}_{t}})-\sigma_{t-1}(a)\right)\right]$ (100) $\displaystyle\leq\sum_{t\in[T]}\mathbb{E}\left[\sum_{a\in\mathbf{a}}\sqrt{ \beta_{t}}\sqrt{L\frac{dC_{1}}{\tau_{t}}+tKL^{2}\frac{d^{2}C_{1}^{2}}{\tau_{t} ^{2}}\varsigma^{-2}}\right]$ $\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:posteriorDiscretization Error}}\right)$ (101) $\displaystyle\leq\sum_{t\in[T]}K\sqrt{\beta_{t}}\sqrt{L\frac{dC_{1}}{\tau_{t}} +tKL^{2}\frac{d^{2}C_{1}^{2}}{\tau_{t}^{2}}\varsigma^{-2}}$ $\displaystyle\left(|\mathbf{a}|\leq K\right)$ (102) $\displaystyle=\sum_{t\in[T]}\sqrt{\beta_{t}K^{2}L\frac{dC_{1}}{\tau_{t}}+\beta _{t}tK^{3}L^{2}\frac{d^{2}C_{1}^{2}}{\tau_{t}^{2}}\varsigma^{-2}}$ (103) $\displaystyle\leq\sum_{t\in[T]}\sqrt{\frac{1}{8t^{4}}+\frac{1}{8t^{4}}}$ $\displaystyle\left(\text{\lx@cref{creftype~refnum}{eq:stdDiscretizationTauReqs }}\right)$ (104) $\displaystyle\leq\sum_{t\in[T]}\frac{1}{2t^{2}}\leq\frac{\pi^{2}}{12}.$ $\displaystyle\left(\sum_{t=1}^{\infty}\frac{1}{t^{2}}=\frac{\pi^{2}}{6}\right)$ (105) $$

∎

See 3.2

###### Proof.

Follows by combining Sections A.2 and A.2.
∎

Finally, we are ready to prove the regret bounds for the infinite case:
See 3.2

###### Proof.

- (i)
Similar to Takeno et al. (); Srinivas et al. (), we use a fixed discretization $\mathcal{D}_{t}\subset\mathcal{A}$ for $t\geq 1$. Let $\mathcal{D}_{t}\subset\mathcal{A}$ be a finite set with $|\mathcal{D}_{t}|=\tau_{t}^{d}$ and each dimension equally divided into $\tau_{t}$ points with $\tau_{t}$ satisfying Section 3.2. Let $[a]_{\mathcal{D}_{t}}$ denote the nearest point in $\mathcal{D}_{t}$ for $a\in\mathcal{A}$ and similarly let $[\mathbf{a}]_{\mathcal{D}_{t}}=\{[a]_{\mathcal{D}_{t}}|a\in\mathbf{a}\}$ for $\mathbf{a}\subset\mathcal{A}$.
As Takeno et al. (), we decompose the Bayesian regret into several parts:
$\displaystyle\text{BR}(T)$
$\displaystyle=\sum_{t\in[T]}\mathbb{E}\big{[}\underbrace{f(\mathbf{a}_{t}^{*})
-f([\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})}_{(1)}+\underbrace{f([\mathbf{a}_{t
}^{*}]_{\mathcal{D}_{t}})-U_{t}([\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})}_{(2)}$
(106)
$\displaystyle\qquad\qquad+\underbrace{U_{t}([\mathbf{a}_{t}^{*}]_{\mathcal{D}_
{t}})-U_{t}(\mathbf{a}_{t}^{*})}_{(3)}+\underbrace{U_{t}(\mathbf{a}_{t}^{*})-U
_{t}(\mathbf{a}_{t})}_{(4)}$
(107)
$\displaystyle\qquad\qquad+\underbrace{U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_{t})}
_{(5)}\big{]}$
(108)
Term $(1)$ can be bounded using Section A.2: $\sum_{t\in[T]}\mathbb{E}[f(\mathbf{a}^{*}_{t})-f([\mathbf{a}_{t}^{*}]_{
\mathcal{D}_{t}})]\leq\frac{\pi^{2}}{6}$. Terms $(2)$ and $(5)$ can be bounded using the finite case with $\beta_{t}=2\log(|\mathcal{D}_{t}|t^{2}/\sqrt{2\pi})$. Then, by Sections A.1, A.1 and A.1
$\sum_{t\in[T]}\mathbb{E}[f([\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})-U_{t}([
\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})+U_{t}(\mathbf{a}_{t})-f(\mathbf{a}_{t})
]\leq\frac{\pi^{2}}{6}+\sqrt{2(\lambda^{*}_{K}+\varsigma^{2})TK\beta_{T}\gamma
_{TK}}.$
(109)
Takeno et al. () consider the term $U_{t}([\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})-U_{t}(\mathbf{a}_{t}^{*})$ and argue that it is non-positive since $\mathbf{a}_{t}=\operatorname*{arg\,max}_{\mathbf{a}\in\mathcal{S}_{t}}U_{t}(
\mathbf{a})$. Unlike , we do not assume that all arms are available at time $t$ and thus $[\mathbf{a}^{*}_{t}]_{\mathcal{D}_{t}}\in\mathcal{S}_{t}$ does not necessarily hold. By further decomposing this term into $(3)$ and $(4)$, the same argument can be applied to term $(4)$: $U_{t}(\mathbf{a}_{t}^{*})-U_{t}(\mathbf{a}_{t})\leq 0$. Then, term $(3)$ can be bounded using Section 3.2: $\sum_{t\in[T]}\mathbb{E}[U_{t}([\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})-U_{t}(
\mathbf{a}_{t}^{*})]\leq\pi^{2}/6.$
Finally, by combining the bounds for all terms we get that
$\text{BR}(T)\leq\frac{\pi^{2}}{2}+\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}.$
(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.1 (ii)).
- (iii)
As in the proof for GP-UCB, assume that we have a discretization $\mathcal{D}_{t}$ and decompose the Bayesian regret into 4 terms:
$\displaystyle\text{BR}(T)$
$\displaystyle=\sum_{t\in[T]}\mathbb{E}\big{[}\underbrace{f(\mathbf{a}_{t}^{*})
-f([\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})}_{(1)}+\underbrace{f([\mathbf{a}_{t
}^{*}]_{\mathcal{D}_{t}})-U_{t}([\mathbf{a}_{t}^{*}]_{\mathcal{D}_{t}})}_{(2)}$
(111)
$\displaystyle\qquad\qquad+\underbrace{U_{t}([\mathbf{a}_{t}^{*}]_{\mathcal{D}_
{t}})-U_{t}(\mathbf{a}_{t})}_{(3)}+\underbrace{U_{t}(\mathbf{a}_{t})-f(\mathbf
{a}_{t})}_{(4)}\big{]}.$
(112)
As in the proof for GP-UCB, term $(1)$ is dealt with using Section A.2 and term $(2)$ and $(4)$ are handled as in the finite case (Theorem 3.1 (iii)):
$\sum_{t\in[T]}\mathbb{E}[(1)+(2)+(3)]\leq\frac{\pi^{2}}{6}+\frac{\pi^{2}}{3}+2
\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}.$
(113)
To bound term $(3)$, we start by utilizing that $\mathbf{a}^{*}_{t}|H_{t}\overset{d}{=}\mathbf{a}_{t}|H_{t}$ and $U_{t}([\cdot]_{\mathcal{D}_{t}})|H_{t}$ is deterministic and thus:
$\displaystyle\sum_{t\in[T]}\mathbb{E}[(3)]$
$\displaystyle=\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[U_{t}(
[\mathbf{a}^{*}_{t}]_{\mathcal{D}_{t}})-U_{t}(\mathbf{a}_{t})|H_{t}\right]\right]$
(114)
$\displaystyle=\sum_{t\in[T]}\mathbb{E}_{H_{t}}\left[\mathbb{E}_{t}\left[U_{t}(
[\mathbf{a}_{t}]_{\mathcal{D}_{t}})-U_{t}(\mathbf{a}_{t})|H_{t}\right]\right]$
(115)
$\displaystyle\leq\frac{\pi^{2}}{6}$
$\displaystyle\left(\text{\lx@cref{creftype~refnum}{lem:posteriorUDiscretizatio
nError}}\right)$
(116)
Put together, we have that
$\text{BR}(T)\leq\frac{2\pi^{2}}{3}+2\sqrt{C_{K}TK\beta_{T}\gamma_{TK}}.$
(117)

∎

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

###### Proof.

### A.3 Additional lemmas

[]
For any sequence of superarms $\mathbf{a}_{1},\ldots,\mathbf{a}_{T}$,

$$ $\sum_{t=1}^{T}\sigma_{t-1}^{2}(\mathbf{a}_{t})\leq 2(\lambda^{*}_{K}+\varsigma ^{2})\gamma_{TK}.$ (118) $$

where $\lambda^{*}_{K}$ 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., ).
Let $K_{t}=|\mathbf{a}_{t}|$ denote the number of base arms selected at time $t$. Similarly, let $N_{T}=\sum_{t\in[T]}K_{t}$ denote the number of base arms selected up to time $T$. Note that the information gain can be decomposed into two entropy terms: $I(\mathbf{r}_{[T]};f)=H(\mathbf{r}_{[T]})-H(\mathbf{r}_{[T]}|f)$.

Since $\mathbf{r}_{[T]}|\mathbf{f}_{[T]}\sim\mathcal{N}(\mathbf{f}_{[T]},\varsigma^{2
}I_{K_{t}}$, $H(\mathbf{r}_{[T]}|\mathbf{f}_{[T]})=\frac{1}{2}\log|2\pi e\varsigma^{2}I_{N_{
T}}|$. The first term can be analyzed by using the chain rule of entropy on the superarms:

$$ $\displaystyle H(\mathbf{r}_{[T]})$ $\displaystyle=H(\mathbf{r}_{T}|\mathbf{r}_{[T-1]})+H(\mathbf{r}_{[T-1]})$ (119) $\displaystyle=\sum_{t=1}^{T}H(\mathbf{r}_{t}|\mathbf{r}_{[t-1]}).$ (120) $$

Then, $\mathbf{r}_{t}|\mathbf{r}_{[t-1]}\sim\mathcal{N}(\bm{\mu}_{t-1},\bm{\Sigma}_{t
-1}+\varsigma^{2}I_{K_{t}})$ where $\bm{\mu}_{t-1}=[\mu_{t-1}(a)]_{a\in\mathbf{a}_{t}}$ is the posterior mean vector and $\bm{\Sigma}_{t-1}=(k_{t-1}(a,a^{\prime}))_{a,a^{\prime}\in\mathbf{a}_{t}\times
\mathbf{a}_{t}}$ is the posterior covariance matrix for superarm $\mathbf{a}_{t}$ after observing $(\mathbf{a}_{1},\bm{r}_{1}),\ldots,(\mathbf{a}_{t-1},\bm{r}_{t-1})$. Let $\lambda_{t,k}$ denote the smallest $k$th eigenvalue of $\bm{\Sigma}_{t-1}$. Then,

$$ $\displaystyle H(\mathbf{r}_{t}|\mathbf{r}_{[t-1]})$ $\displaystyle=\frac{1}{2}\log\left|2\pi e(\bm{\Sigma}_{t-1}+\varsigma^{2}I_{K_ {t}})\right|$ (121) $\displaystyle=\frac{1}{2}\log\left|2\pi e\varsigma^{2}(\varsigma^{-2}\bm{ \Sigma}_{t-1}+I_{K_{t}})\right|$ (122) $\displaystyle=\frac{1}{2}\log\left|2\pi e\varsigma^{2}I_{K_{t}}\right|+\frac{1 }{2}\log\left|\varsigma^{-2}\bm{\Sigma}_{t-1}+I_{K_{t}}\right|.$ (123) $$

Let $\lambda_{t,k}$ denote the smallest $k$th eigenvalue of $\bm{\Sigma}_{t-1}$. Let $\mathcal{M}=\{\bm{\Sigma}_{t-1}|\forall t\in[T],\forall\mathbf{a}_{1},\ldots,
\mathbf{a}_{t}\in\mathcal{S}\}$ be the set of all possible posterior covariance matrices and let $\lambda^{*}_{K}=\sup_{\bm{\Sigma}\in\mathcal{M}}\max\operatorname*{eig}(\bm{
\Sigma})$ be the largest eigenvalue of all eigenvalues of the matrices in $\mathcal{M}$.

Recall that $|A+I_{n}|=\prod_{k\leq n}(\lambda_{k}+1)$ for any real and symmetric matrix $A\in\mathbb{R}^{n\times n}$ with eigenvalues $\lambda_{1},...,\lambda_{n}$.
Then,

$$ $\displaystyle\frac{1}{2}\log\left|\varsigma^{-2}\bm{\Sigma}_{t-1}+I_{K_{t}}\right|$ (124) $\displaystyle=\frac{1}{2}\log\left(\prod_{k=1}^{K_{t}}\left(\varsigma^{-2} \lambda_{t,k}+1\right)\right)$ (125) $\displaystyle=\frac{1}{2}\sum_{k=1}^{K_{t}}\log\left(\varsigma^{-2}\lambda_{t, k}+1\right)$ (126) $\displaystyle\geq\frac{1}{2}\sum_{k=1}^{K_{t}}\frac{\varsigma^{-2}\lambda_{t,k }}{\varsigma^{-2}\lambda_{t,k}+1}$ $\displaystyle\left(\log(x+1)\geq x/(x+1),\forall x>1\right)$ (127) $\displaystyle\geq\frac{\varsigma^{-2}}{2(\varsigma^{-2}\lambda^{*}+1)}\sum_{k= 1}^{K_{t}}\lambda_{t,k}$ (128) $\displaystyle=\frac{\varsigma^{-2}}{2(\varsigma^{-2}\lambda^{*}+1)}\sum_{a\in \mathbf{a}_{t}}\sigma^{2}_{t-1}(a).$ $\displaystyle\left(\operatorname{Tr}(A)=\sum_{\lambda\in\operatorname*{eig}(A) }\lambda\right)$ (129) $$

Put together, we get that $\sum_{t=1}^{T}\sigma_{t-1}^{2}(\mathbf{a}_{t})\leq 2(\lambda^{*}+\varsigma^{2}
)I(\mathbf{r}_{[T]};f)$. Since the maximum information $\gamma_{T}$ is increasing w.r.t. $T$ and $|\mathbf{a}_{t}|\leq K$, we get that $\sum_{t=1}^{T}\sigma_{t-1}^{2}(\mathbf{a}_{t})\leq 2(\lambda^{*}+\varsigma^{2}
)\gamma_{TK}$.
∎

[]
The inverse error function is lower bounded by

$$ $\operatorname{erf}^{-1}(u)\geq\sqrt{-\omega^{-1}\log\left(\frac{1-u}{\vartheta }\right)}$ (130) $$

for $u\in[0,1)$, $\omega>1$ and $0<\vartheta\leq\sqrt{\frac{2e}{\pi}}\frac{\sqrt{\omega-1}}{\omega}$.

###### Proof.

According to Theorem 2 of Chang et al. (), $\operatorname{erfc}(u)\geq\vartheta\exp(-\omega u^{2})$ for $\omega>1$ and $0<\vartheta\leq\sqrt{\frac{2e}{\pi}}\frac{\sqrt{\omega-1}}{\omega}$. Since $\operatorname{erf}(u)=1-\operatorname{erfc}(u)$, it follows that $\operatorname{erf}(u)\leq 1-\vartheta\exp(-\omega u^{2})=:h(u)$.

In general, if $f(x)\leq g(x)$ then $f^{-1}(x)\geq g^{-1}(x)$. Thus, $\operatorname{erf}^{-1}(u)\geq h^{-1}(u)=\sqrt{-\omega^{-1}\log\left((1-u)/
\vartheta\right)}$.
∎

[]
The inverse error function is upper bounded by

$$ $\operatorname{erf}^{-1}(u)\leq\sqrt{-\omega^{-1}\log\left(\frac{1-u}{\vartheta }\right)}$ (131) $$

for $u\in[0,1)$, $\vartheta\geq 1$ and $0<\omega\leq 1$.

###### Proof.

The same arguments as in Eq. 130 but using Theorem 1 of Chang et al. ().
∎

###### Proof.

###### Proof.

###### Proof.

## Appendix B Additional experimental details

### B.1 Kernel details

Here, we provide further details on the graph kernel used in the experiments. The original graph Matérn GP of Borovitskiy et al. () defines a GP on the vertices of a weighted and undirected graph. We extend the graph Matérn GP from Borovitskiy et al. () to the edges of a directed graph by considering the incidence graph Laplacian of the line graph $\mathcal{L}(\mathcal{G})$.

Let $\mathbf{W}_{\mathcal{L}}\in\mathbb{R}^{|\mathcal{E}|\times|\mathcal{C}|}$ denote the weight matrix of $\mathcal{L}(\mathcal{G})=(\mathcal{E},\mathcal{C})$ where $\mathcal{E}$ is the set of edges and $\mathcal{C}$ is the set of all connections in the network. The weight $W_{\mathcal{L},e_{1},e_{2}}$ is set to $\bar{\ell}/\ell_{e_{1}}$ where $\bar{\ell}$ is the average length of all edges and $\ell_{e_{1}}$ is the length of edge $e_{1}$. We replace the ordinary graph Laplacian used by Borovitskiy et al. () with the incidence Laplacian:

$$ $\mathbf{\Delta}_{I}=\mathbf{B}\mathbf{B}^{\top},$ (132) $$

where the incidence matrix $\mathbf{B}\in\mathbb{R}^{|\mathcal{E}|\times|\mathcal{C}|}$ has entries

$$ $B_{e,c}=\begin{cases}-W_{\mathcal{L},e_{1},e_{2}}\quad&\text{if }e=e_{1},\\ W_{\mathcal{L},e_{1},e_{2}}\quad&\text{if }e=e_{2},\\ 0\quad&\text{otherwise}\\ \end{cases}\quad\forall e\in\mathcal{E},c=(e_{1},e_{2})\in\mathcal{C}.$ (133) $$

Let $\mathbf{\Delta}_{I}=\mathbf{U}_{I}\mathbf{\Lambda}_{I}\mathbf{U}_{I}^{\top}$ denote the eigendecomposition of $\mathbf{\Delta}_{I}$, then the graph Matérn GP of the edges is given by

$$ $\mathbf{f}\sim\mathcal{N}\left(0,\mathbf{U}_{I}\left(\frac{2\nu_{G}}{\kappa_{G }^{2}}\mathbf{I}+\mathbf{\Lambda}_{I}\right)^{-\nu}\mathbf{U}_{I}^{\top}\right).$ (134) $$

Recall that $k_{f}:\mathbb{R}^{d}\times\mathbb{R}^{d}\xrightarrow{}\mathbb{R}$ denotes a feature kernel which measures the similarity between the contexts of the edges. The feature kernel is an ordinary Matérn kernel with fixed $\nu=5/2$ but tunable outputscale $\sigma_{f}$ and lengthscales $\bm{\ell}_{f}\in\mathbb{R}^{d}_{+}$ for each dimension:

$$ $\displaystyle k_{f}(x_{e},x_{e^{\prime}})$ $\displaystyle:=\sigma_{f}\frac{2^{1-\nu}}{\Gamma(\nu)}\left(\sqrt{2\nu}D\right )^{\nu}K_{\nu}\left(\sqrt{2\nu}D\right),$ (135) $$

where $x_{e}$ denotes the feature vector of edge $e$ and the feature distance $D$ between edge $e$ and $e^{\prime}$ is given by

$$ $D=\sqrt{(x_{e}-x_{e^{\prime}})^{\top}\operatorname{diag}(\bm{\ell}_{f})^{-2}(x _{e}-x_{e^{\prime}})}.$ (136) $$

The kernels, the SVGP model and Algorithm 3 was implemented using GPyTorch (Gardner et al., ).

### B.2 Road network

The set of available paths was restricted to 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 -31118#2 and ends in edge --32646#1. The route Luxembourg B starts in edge -30436#5 and ends in edge -30946#0. Similarly, the route Monaco A starts in edge -30558 and ends in edge -32888#0 whilst Monaco B starts in edge -32166#0 and ends in edges --32940#0. For simplicity, the start and end points are edges since the shortest path was computed using the line graph $\mathcal{L}(\mathcal{G})$.

### B.3 Detailed parameter values

In this section, we further specify the vehicle, environmental and algorithmic parameters used. We use the default parameters for electric vehicles provided by SUMO (Lopez et al., ), see Table 2.

**Table 2: Vehicle and environmental parameters for the energy model.**
| Variable | Value | Unit |
| --- | --- | --- |
| Mass $m$ | 1830 | kg |
| Rolling resistance coefficient $C_{r}$ | 0.01 |  |
| Front surface area $A$ | 2.6 | $\textrm{m}^{2}$ |
| Air drag coefficient $C_{d}$ | 0.35 |  |
| Power train efficiency $\eta^{+}$ | 0.98 |  |
| Recuperation efficiency $\eta^{-}$ | 0.96 |  |
| Gravitational acceleration $g$ | 9.82 | m/$\textrm{s}^{2}$ |
| Air density $\rho$ | 1.2 | kg/$\textrm{m}^{3}$ |

The graph kernel is initialized with parameters $\nu_{G}=2$, $\kappa_{G}=1$ and $\sigma_{G}$ 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 uses a batch size $B$ of 2500 and 1 gradient step per optimization procedure. The number of inducing points is set to $1000$.

## Appendix C Additional experimental results

### C.1 Impact of lengthscale

In this section, we provide the full results for the lengthscale experiments in Section 4.2. The cumulative regret over time is visualized in Fig. 5 and the final cumulative regret as a function on the lengthscale $\ell$ is visualized in Fig. 6.

Figure: Figure 5: Cumulative regret of GP-BUCB, BI-BUCB, GP-TS and BI-TS for varying prior lengthscale values $\ell$.
Refer to caption: x5.png

Figure: Figure 6: Cumulative regret at $t=500$ for varying prior lengthscale values. Errorbars correspond to $\pm 1$ standard error.
Refer to caption: x6.png

### C.2 Visualization of exploration

In this section, we provide visualization of the routes selected by the algorithms. See Figs. 7, 8, 9 and 10 for visualization on Lux. A, Lux B, Mon. A and Mon. B, respectively. According to the results, the TS variants are able to find sophisticated paths with significantly less exploration compared to BUCB and UCB. This observation implies the sample efficiency of TS methods.

Figure: (a) BI-TS
Refer to caption: x7.png

Figure: (a) BI-TS
Refer to caption: x13.png

Figure: (a) BI-TS
Refer to caption: x19.png

Figure: (a) BI-TS
Refer to caption: x25.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: Please respond to my above concerns.

In 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.
soundness: 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. 

Specifically, it is nice to see sub-linear regret bound for all three algorithms.

Furthermore, I also believe that the general techniques developed here may be useful to derive regret bounds for other bandit settings.
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).

The authors apply these algorithms to the problem of online energy-efficient navigation to demonstrate the performance of the various algorithms.
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? 
2. 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.
3. 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?
4. 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.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 1.	Connection Between Theory and Empirical Results:
The 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?
2.	Extended Comparison in Table 1:
Including 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.
3.	Discussion of Theoretical Challenges:
As 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.
soundness: 3
strengths: 1.	Clear and Structured Presentation:
The 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.
2.	Solid Theoretical Contributions:
The 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).
3.	Practical Application:
The 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.
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.
weaknesses: 1.	Lack of Discussion on Theoretical Challenges:
While 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.
2.	Reproducibility Concerns:
No code is provided for the experiments. This absence raises concerns about the reproducibility of the empirical results.

---

confidence: 4
contribution: 1
initial_rating: 5
presentation: 2
questions: See the weakness section
soundness: 2
strengths: The paper provides the bounds for the Bayesian regret for GP-BUCB, GP-UCB and GP-TS.
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.
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?
2. 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.
3. 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?

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 4
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? 

I 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?
soundness: 3
strengths: The paper is building on top of other previously published frameworks, however, it is not a straightforward extension of the previous works. 

The experiments (application of their framework) in online energy-efficient navigation problem seem to have added some novelties and value to the paper. 

The 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.
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.
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]. 

Also, 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. 

I did not notice any discussion in the paper about possible extensions and future directions and further impacts of their research.

Meta-review: This is a borderline paper with one reviewer being very positive and three reviewers somewhat critical. After having had a read through the reviews and discussions I believe that the criticisms are mostly about minor issues like the presentation of results. The paper presents useful results around Gaussian process semi-bandit problems and applies these techniques to a real-world problem. I believe that these contributions are valuable and worth being published.

Decision: Accept (Poster)