1 Introduction↩︎

The kernelized bandit (KB) problem, also known as the Gaussian process (GP) bandit, is an effective sequential decision-making framework for nonlinear reward functions. Its applications are extensive, e.g., robotics [1], recommendation systems [2], and hyperparameter tuning [3]. In prior research on KB, most existing works focus on the stochastic setting in which the learner makes decisions from noisy observations of a common fixed reward function over rounds. A key desideratum in the application of KB is to develop algorithms that bypasses the restrictive assumptions in a stochastic setting, which are often invalid in practice. For example, in recommendation systems, the presence of a malicious user may critically degrade the performance of the stochastic KB algorithm [4]. Decision-making in the stock market may also encounter adversarial behavior from other market participants. To overcome the limitations of the stochastic setting, several existing works [5], [6] have studied the adversarial KB problem, aiming to design algorithms under minimal smoothness assumptions encoded via the kernel.

This paper addresses a significant open problem in adversarial KB: the construction of a nearly-optimal algorithm. Specifically, to our knowledge, existing algorithms fail to attain even a no-regret guarantee for the commonly used \(\nu\)-Matérn kernels. Our algorithm and theoretical findings substantially enhance the existing theoretical guarantees in adversarial KB.

1.0.0.1 Contributions.

Our contributions are described below.

• In Sec. 3, we propose kernelized Exp3, which is the kernelized extension of the exponential-weight algorithm for exploration and exploitation (Exp3). We provide an \(\widetilde{O}(\sqrt{T \gamma_T})\) regret upper bound for kernelized Exp3, where \(T\) and \(\gamma_T\) represent the total number of rounds and the maximum information gain (MIG), respectively (the definition is in Sec. 2)¹. In addition, this is the first guarantee for adversarial KB under an adaptive adversary.

• In Sec. 4, we propose RLS-kernelized Exp3, which is a variant of kernelized Exp3 that alleviates the heavy computational burden of the original kernelized Exp3. Specifically, by utilizing the existing ridge-leverage-score (RLS)-based Nyström method [7], the per-round computational complexity of RLS-kernelized Exp3 becomes \(\widetilde{O}(|\mathcal{X}| \gamma_T^2 + \gamma_T^3)\), while that of the original kernelized Exp3 is \(O(|\mathcal{X}|^3)\). Here, \(|\mathcal{X}|\) denotes the cardinality of the input domain \(\mathcal{X}\subset \mathbb{R}^d\)². Furthermore, RLS-kernelized Exp3 also achieves an \(\widetilde{O}(\sqrt{T\gamma_T})\) regret.

• Finally, in Sec. 5, we show the algorithm-independent lower bounds for the adversarial KB problem with SE or \(\nu\)-Matérn kernels. Our lower bounds guarantee that the proposed algorithms are optimal up to polylogarithmic factors for SE and \(\nu\)-Matérn kernels with \(\nu > 1\).

Tab. 1 summarizes the existing algorithm and our results.

1.1 Related works↩︎

The KB algorithms in the stochastic setting have been widely studied, including e.g., GP-upper confidence bound (GP-UCB) [8], GP-Thompson sampling (GP-TS) [9], and theoretically more advanced non-adaptive sampling-based algorithms [10]–[13]. In addition to the standard stochastic KB settings, several variants are also studied, e.g., the contextual model [13], [14], the multi-objective setting [15], [16], the parallel setting [17], the noise-free setting [18]–[21], and the Bayesian setting [22]–[27]. In addition to these settings, some existing studies have examined more robust or general variants of the standard stochastic KB model, which are orthogonal to the adversarial KB model in this paper. For example, robust objective settings [28]–[32], adversarial corruptions of rewards [4], [33], [34], adversarial contextual information [35], [36], and non-stationary rewards [37]–[40] have been considered.

Regarding the adversarial KB problem, to our knowledge, [5] is the first work to tackle it. However, their analysis is only valid under the quite restrictive rank \(1\) assumption; specifically, the reward function \(f_t\) at each round \(t\) must have the form \(f_t(\cdot) = k(\boldsymbol{z}_t, \cdot)\). In addition, their lower bounds (Theorem 43 in [5]) only apply to an unrealistic infinite-dimensional linear kernel and do not imply lower bounds for an adversarial KB model with practically used SE or Matérn kernels.³ [6] proposed the algorithm, which broke the limitation of [5], called APG-Exp3. The core idea of [6] is to reduce the adversarial KB problem to an approximated (misspecified) linear bandit (LB) problem. However, due to the non-negligible effect of the linear approximation, the current analysis of APG-Exp3 fails to provide even a no-regret guarantee under the commonly-used \(\nu\)-Matérn kernel with \(d \geq \nu\) (see Tab. 1). Another related work for adversarial KB is [42], which studies the \(K\)-armed adversarial contextual KB problem and remains distinct from our setting. Their model considers independent \(K\) reward functions on the RKHS defined over the context space (with \(K \ll T\)). In contrast, [5], [6] and our analysis assume that the reward function is an element of RKHS defined on entire decision space \(\mathcal{X}\), whose cardinality may be \(|\mathcal{X}| \gg T\) or infinite.

From a technical perspective, our algorithm construction and several parts of our analysis leverage the existing results in the adversarial LB and stochastic KB. Firstly, from the high-level view, our algorithm construction is interpreted as an extension of the existing Exp3-based algorithms for adversarial LB [43]–[45]. The differences from the existing Exp3 are the one-sample estimator of the reward function and the exploration distribution, which are redesigned by adapting the existing theoretical tools in the stochastic KB problem [10], [46]–[48]. Secondly, in our analysis of the regret upper bound, the existing information gain-based arguments by [8] play a central role in quantifying the regret. To our knowledge, our paper is the first to bridge the adversarial KB theory with the information-gain-based arguments commonly used in stochastic KB analysis. Thirdly, regarding the RLS-kernelized Exp3 proposed in Sec. 4, we construct our algorithm by combining our kernelized Exp3 with the existing RLS-based Nyström approximation [7]. Furthermore, several parts of our regret analysis are motivated by the techniques in [49], which studies the stochastic KB algorithm with Nyström approximation. Finally, regarding the lower bound, our analysis reduces the adversarial KB lower bound to that of the stochastic KB analyzed in [50], [51]. Specifically, our hard problem instance in the proof of the lower bound is interpreted as the kernelized extension of the parameter noise model in LB (see Chap. 29 in [44]), which is used to study the lower bound for adversarial LB [52].

1.1.0.1 Concurrent work.

The concurrent work by [41] studies the nearly-identical algorithm as our kernelized Exp3 in Sec. 3. Indeed, our kernelized Exp3 becomes identical to theirs by replacing our MVR-based exploration distribution with a G-optimal design-based one (defined in Appendix 16). Furthermore, their regret analysis and ours are almost identical. The summary of the minor differences between ours and their algorithm can be found in Appendix B of [41]. We would like to note that our proposal of the computationally efficient nearly-optimal algorithm (RLS-kernelized Exp3 in Sec. 4) and the lower bounds for SE and Matérn kernels (in Sec. 5) do not overlap with the contents in [41].

2 Preliminaries↩︎

2.0.0.1 Problem setting.

We study the KB problem in an adversarial environment. Let \(\mathcal{X}\subset [0, 1]^d\) be the input domain of the problem. At each round \(t\), the learner sequentially draws a query point \(\boldsymbol{x}_t \in \mathcal{X}\) based on the history up to round \(t-1\); subsequently, the bandit feedback of the reward \(f_t(\boldsymbol{x}_t)\) is revealed, where \(f_t: \mathcal{X}\rightarrow \mathbb{R}\) is the reward function drawn by the environment. This paper assumes the environment to be adaptive. Namely, the environment can draw \(f_t\) based on the learner’s past history \(\mathcal{H}_{t-1} \mathrel{\vcenter{:}}= \{\boldsymbol{x}_1, f_1(\boldsymbol{x}_1), \ldots, \boldsymbol{x}_{t-1}, f_{t-1}(\boldsymbol{x}_{t-1})\}\), while (\(f_t\), \(\boldsymbol{x}_t\)) must be conditionally independent given \(\mathcal{H}_{t-1}\). Under this setup, the learner’s goal is to minimize the following expected (pseudo) regret \(\bar{R}_T\): \[\bar{R}_T = \sup_{\boldsymbol{x}\in \mathcal{X}} \mathbb{E}\left[R_T(\boldsymbol{x})\right],~\mathrm{where}~R_T(\boldsymbol{x}) = \sum_{t \in [T]} f_t(\boldsymbol{x}) - \sum_{t \in [T]} f_t(\boldsymbol{x}_t)~\mathrm{and}~[T] = \{1, \ldots, T\}.\] In this paper, we adopt the following standard assumption of KB, which demands that the reward functions lie in a known RKHS.

As examples of the kernel, the following SE and \(\nu\)-Matérn kernels are commonly studied: \[\begin{align} k_{\mathrm{SE}}(\boldsymbol{x}, \boldsymbol{x}') = \exp\left(\frac{\|\boldsymbol{x}- \boldsymbol{x}'\|_2^2}{2\ell^2}\right),~k_{\mathrm{Mat}}(\boldsymbol{x}, \boldsymbol{x}') = \frac{2^{1-\nu}}{\Gamma(\nu)} \left(\frac{\sqrt{2\nu} \|\boldsymbol{x}- \boldsymbol{x}'\|_2}{\ell}\right)^{\nu} K_{\nu}\left(\frac{\sqrt{2\nu} \|\boldsymbol{x}- \boldsymbol{x}'\|_2}{\ell}\right), \end{align}\] where \(\ell > 0\) and \(\nu > 0\) are the lengthscale and smoothness parameters, respectively. Furthermore, \(\Gamma(\nu)\) and \(K_{\nu}(\cdot)\) denote the Gamma function and the modified Bessel function of the second kind, respectively.

2.0.0.2 Gaussian process (GP) model.

In a stochastic setting of KB, the GP model [54] is a commonly used tool for guiding the learner. In the adversarial setting, although GP is not directly used in our algorithm construction, it plays an important role in quantifying regret via GP’s information gain in the analysis. Let us consider a function \(f\) that follows a mean-zero GP prior \(f \sim \mathcal{GP}(0, k)\) characterized by a covariance kernel \(k\). Then, for some training inputs \(\mathbf{X}= (\boldsymbol{x}^{(1)}, \ldots, \boldsymbol{x}^{(t)})\) and outputs \(\boldsymbol{y} = (y^{(1)}, \ldots, y^{(t)})^{\top}\), the GP model assumes that outputs are generated as \(y^{(i)} = f(\boldsymbol{x}^{(i)}) + \epsilon^{(i)}\), where \(\epsilon^{(i)} \sim \mathcal{N}(0, \lambda)\) is the Gaussian noise with variance \(\lambda > 0\), and is independent across \(i \in [t]\). Under the aforementioned modeling assumptions, the posterior distribution of \(f\) given \((\mathbf{X}, \boldsymbol{y})\) also follows GP [54]. Specifically, its posterior variance \(\sigma^2(\boldsymbol{x}; \mathbf{X}, \lambda)\) of \(f(\boldsymbol{x})\) is often used to upper-bound the regret of the KB problem: \[\begin{align} \label{eq:posterior95var} \sigma^2(\boldsymbol{x}; \mathbf{X}, \lambda) = k(\boldsymbol{x}, \boldsymbol{x}) - \boldsymbol{k}(\boldsymbol{x}, \mathbf{X})^{\top} \left(\mathbf{K}(\mathbf{X}, \mathbf{X}) + \lambda \boldsymbol{I}_t\right)^{-1} \boldsymbol{k}(\boldsymbol{x}, \mathbf{X}), \end{align}\tag{1}\] where \(\boldsymbol{k}(\boldsymbol{x}, \mathbf{X}) \mathrel{\vcenter{:}}= [k(\boldsymbol{x}, \boldsymbol{x}^{(i)})]_{i \in [t]} \in \mathbb{R}^t\), \(\mathbf{K}(\mathbf{X}, \mathbf{X}) \mathrel{\vcenter{:}}= [k(\boldsymbol{x}^{(i)}, \boldsymbol{x}^{(j)})]_{i, j \in [t]} \in \mathbb{R}^{t \times t}\), and \(\boldsymbol{I}_t\) are kernel vector, kernel matrix, and \(t\times t\)-identity matrix, respectively.

2.0.0.3 Maximum information gain (MIG).

The MIG of a GP is a widely-used complexity parameter for the stochastic KB problem [8]. Given some inputs \(\mathbf{X}= [\boldsymbol{x}^{(i)}]_{i \in [t]}\), let \(I(\boldsymbol{f}(\mathbf{X}); \boldsymbol{y}) \mathrel{\vcenter{:}}= \frac{1}{2} \log \det(\boldsymbol{I}_t + \lambda^{-1} K(\mathbf{X}, \mathbf{X}))\) be the mutual information between random vectors \(\boldsymbol{f}(\mathbf{X}) = (f(\boldsymbol{x}^{(1)}), \ldots, f(\boldsymbol{x}^{(t)}))^{\top} \sim \mathcal{N}(\boldsymbol{0}, K(\mathbf{X}, \mathbf{X}))\) and \(\boldsymbol{y} \mathrel{\vcenter{:}}= \boldsymbol{f}(\mathbf{X}) + \boldsymbol{\epsilon}\), where \(\boldsymbol{\epsilon} \sim \mathcal{N}(\boldsymbol{0}, \boldsymbol{I}_t)\). Namely, \(I(\boldsymbol{f}(\mathbf{X}); \boldsymbol{y})\) represents the mutual information between underlying function values and outputs under the Bayesian assumption of GP. Then, the MIG \(\gamma_t(\lambda, \mathcal{X})\) is defined as the maximum amount of \(I(\boldsymbol{f}(\mathbf{X}); \boldsymbol{y})\) over all possible selections of \(t\) inputs \(\mathbf{X}\in \mathcal{X}^t\): \(\gamma_t(\lambda, \mathcal{X}) \mathrel{\vcenter{:}}= \sup_{\mathbf{X}\in \mathcal{X}^t} I(\boldsymbol{f}(\mathbf{X}); \boldsymbol{y})\). For simplicity, we use the notation \(\gamma_t\) by omitting the dependence on \(\lambda\) and \(\mathcal{X}\). For commonly used kernels, the growth rates of MIG are known. For example, for the SE kernel, \(\gamma_t = O((\log t)^{d+1}/(\log \log t)^d)\) holds [55]. Regarding \(\nu\)-Matérn kernels, it is known that \(\gamma_t = \widetilde{O}(t^{\frac{\nu+d}{2\nu+d}})\) [22], [53]. Here, one of the well-known useful results for regret analysis of stochastic KB is the relation between MIG and the posterior variance of GP. Specifically, it is known that the cumulative posterior variance at the observed points is bounded from above by the MIG [8]: \[\label{eq:sigma95295cum95ub} \sum_{i \in [t]} \sigma^2 (\boldsymbol{x}^{(i)}; \mathbf{X}^{(i-1)}, \lambda) \leq \frac{2 \gamma_t}{\log (1 + \lambda^{-1})},\tag{2}\] where we define \(\mathbf{X}^{(i-1)}\) as \(\mathbf{X}^{(i-1)} = (\boldsymbol{x}^{(1)}, \ldots, \boldsymbol{x}^{(i-1)})\) for any \(i\). Even in the adversarial KB setting, the above inequality plays a central role in upper-bounding the regret, as highlighted in Sec. 3.

2.0.0.4 Feature representation of kernel and GP.

In our algorithm construction and analysis, we leverage the feature representation of kernels. In general, it is known that a positive definite kernel \(k: \mathcal{X}\times \mathcal{X}\rightarrow \mathbb{R}\) cannot always be represented by a finite-dimensional feature map for a continuous input domain \(\mathcal{X}\); however, for a finite input domain \(\mathcal{X}\), we can always construct an \(|\mathcal{X}|\)-dimensional feature map \(\psi: \mathbb{R}^d \rightarrow \mathbb{R}^{|\mathcal{X}|}\), which satisfies \(k(\boldsymbol{x}, \boldsymbol{x}') = \psi(\boldsymbol{x})^{\top}\psi(\boldsymbol{x}')\) for all \(\boldsymbol{x}, \boldsymbol{x}' \in \mathcal{X}\). For example, for kernel matrix \(\mathbf{K}(\mathcal{X}, \mathcal{X}) \mathrel{\vcenter{:}}= [k(\boldsymbol{x}, \boldsymbol{x}')]_{\boldsymbol{x}, \boldsymbol{x}' \in \mathcal{X}}\), the Cholesky decomposition \(\mathbf{K}(\mathcal{X}, \mathcal{X}) \mathrel{\vcenter{:}}= \boldsymbol{L} \boldsymbol{L}^{\top}\) induces the feature map by defining \(\psi(\boldsymbol{x}^{(i)})\) as the \(i\)-th row vector of \(\boldsymbol{L} \in \mathbb{R}^{|\mathcal{X}| \times |\mathcal{X}|}\).

3 Exponential-weight algorithm for adversarial kernelized bandits↩︎

The pseudocode for our first algorithm, kernelized Exp3, is presented in Alg. 1. While Alg. 1 assumes that \(\mathcal{X}\) is a finite set, the extension to a continuous input domain is obtained by discretizing \(\mathcal{X}\), as discussed later in this section. At a high-level viewpoint, Alg. 1 is constructed based on the Exp3 algorithm for adversarial LB [43], [45], using a kernel feature map. The primary differences lie in (i) the choice of the estimator for \(f_t(\cdot)\) (Lines 7–8) and the choice of the exploration distribution (Line 2).

3.0.0.1 Estimator.

To use the Exp3 algorithm, at each round \(t\), we require an estimator \(\widehat{f}_t(\cdot)\) of the reward function. The standard Exp3 algorithm in the adversarial LB adopts an unbiased estimator based on inverse propensity score (IPS); however, the IPS estimator suffers from high variance as the feature map dimension increases, making it unsuitable for a kernelized setting. To address this issue, we adopt the following regularized version of the IPS estimator, whose effectiveness has been demonstrated in the stochastic KB literature [10], [47], [56]: \[\label{eq:reg95ips} \widehat{f}_t(\boldsymbol{x}) = \psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t) f_t(\boldsymbol{x}_t),~\text{where}~~G_t(\lambda) = \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}.\tag{3}\] Here, \(P_t(\cdot)\) is the sampling distribution of the learner at round \(t\), and \(\lambda > 0\) is the regularization parameter. Note that, when \(\lambda = 0\), \(\widehat{f}_t(\cdot)\) reduces to the standard IPS estimator used in LB [44]. Due to the regularization, the estimator \(\widehat{f}_t(\boldsymbol{x})\) is not unbiased when \(\lambda > 0\). To prevent the exploration behavior from being undermined by the bias of the estimator, we use the optimistic estimator \(u_t(\cdot) \mathrel{\vcenter{:}}= \widehat{f}_t(\cdot) + \beta \|\psi(\cdot)\|_{G_t(\lambda)^{-1}}\) (Line 8) in the exponential-weight procedures by adding the optimistic term \(\beta \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}\), where \(\|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}} \mathrel{\vcenter{:}}= \sqrt{\psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x})}\). Note that the addition of such a term is the common algorithm construction strategy in the adversarial LB [43], [45].

3.0.0.2 Exploration distribution.

As with Exp3 for adversarial LB, we adopt an exploration distribution \(\pi(\boldsymbol{x})\) to prevent the estimator \(\widehat{f}_t(\cdot)\) from becoming unstable due to the extremely small sampling probabilities. As we will see later in Lemma 1, the variance (the second moment) of the estimator \(\widehat{f}_t(\cdot)\) is dominated by the posterior variance of a GP, whose inputs are sampled from the distribution \(P_t\). Based on this fact, we propose using the empirical distribution of the input sequence generated by maximum variance reduction (MVR) [48] (see, Alg. 2 in Appendix 9), which greedily minimizes the maximum posterior variance of the GP.

3.0.0.3 Regret upper bound.

We provide the following regret upper bound for kernelized Exp3.

The full proof is provided in Appendix 11. The desired regret upper bound is obtained by tuning the learning rate \(\eta\) depending on \(T\) and \(|\mathcal{X}|\), as formally stated in the following Corollary 1.

3.0.0.4 Proof overview of Theorem 1.

The basic proof strategy follows from that of Exp3. Compared with existing analyses in adversarial LB, the primary technical challenge is how to address the high dimensionality of the feature map \(\psi(\boldsymbol{x})\). Specifically, by following the standard Exp3 analysis, we can observe that the quadratic form \(\|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}^2\) is the central quantity for governing the analysis. For example, the second moment \(\sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \widehat{f}_t^2(\boldsymbol{x})\) and the supremum of the estimator, which are crucial quantities for Exp3 analysis [44], are dominated by this quadratic form. Without regularization \(\lambda = 0\), in general, the worst-case value of this quantity depends on the dimensionality of the feature map, i.e., \(\|\psi(\boldsymbol{x})\|_{G_t(0)^{-1}}^2 = \Theta(|\mathcal{X}|)\). However, under the regularization, we can observe a simple yet useful connection among the quadratic form, the posterior variance of the GP, and the MIG. We introduce the following lemma, which is used in the various parts of our analysis to handle the quadratic form \(\|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}^2\) via MIG.

Lemma 1 is derived by combining the direct consequence of matrix Jensen’s inequality with information gain inequality in Eq. 2 from [8]. We give the full proof in Appendix 10. Our proof for Theorem 1 is obtained by carefully combining Lemma 1 with the existing Exp3 analysis and the existing MVR analysis, in e.g., [46], [48].

3.0.0.5 Extension to a continuous domain.

The extension to a continuous domain⁵ can be directly obtained by relying on the discretization argument used in the stochastic KB literature [9], [11]. The only additional requirement is the following uniform Lipschitz condition of RKHS.

The above Lipschitz condition is relatively mild. For example, SE and Matérn kernels with \(\nu > 1\) satisfy this condition with \(L(B) = CB\) for some constant \(C > 0\)⁶ [57]. By Assumption 2, we can ignore the regret incurred from a sufficiently fine discretization. Specifically, we use a discretized input set \(\widetilde{\mathcal{X}} \subset \mathcal{X}\subset [0, 1]^d\) as a \(\Theta(1/\sqrt{T})\)-net of \(\mathcal{X}\) with respect to \(\|\cdot\|_{2}\), as with [11]⁷. Then, the existence of \(\widetilde{\mathcal{X}}\) with \(|\widetilde{\mathcal{X}}| = O(T^{\frac{d}{2}})\) is guaranteed (e.g., Corollary 4.2.13 in [58]), and the regret incurred from the cumulative discretization error is at most \(O(\sqrt{T})\), which does not affect the growth rate of regret. Thus, we obtain the following corollary of Theorem 1.

Corollary 2 shows that kernelized Exp3 achieves an \(\widetilde{O}(\sqrt{T \gamma_T})\) regret, which is identical to the nearly-optimal regret obtained in the stochastic KB literature [11]–[13]. By substituting the explicit upper bounds of the MIG, we can also obtain kernel-specific regret results. For the SE and \(\nu\)-Matérn kernels, \(\gamma_T = O((\log T)^{d+1}(\log \log T)^{-d})\) [55] and \(\gamma_T = \widetilde{O}(T^{\frac{d}{2\nu+d}})\) [22], [53], respectively. Thus, for SE and \(\nu\)-Matérn kernels, we have \(\bar{R}_T = O(\sqrt{T (\log T)^{d+2}(\log \log T)^{-d}})\) and \(\bar{R}_T = \widetilde{O}(T^{\frac{\nu+d}{2\nu+d}})\), respectively. In addition, for the linear kernel, we have \(\bar{R}_T = O(\sqrt{T} \log(T))\) since \(\gamma_T = O(\log T)\) [8]. This result matches the regret of Exp3 in the adversarial LB up to a logarithmic factor [43]–[45].

3.0.0.6 Computational cost.

The primary drawback of kernelized Exp3 is its prohibitive computational cost, stemming from the manipulation of the \(|\mathcal{X}|\)-dimensional feature map. To obtain the MVR sequence used in the exploration distribution, we require \(O(|\mathcal{X}| \sum_{t=1}^{\lceil T\alpha \rceil} t^2) = O(|\mathcal{X}| (T\gamma_T)^{3/2})\) computation via one-rank update of the matrix inverse. Regarding the per-round computational cost, we need to calculate the inverse of the \(|\mathcal{X}| \times |\mathcal{X}|\) matrix \(G_t(\lambda)\), which requires \(O(|\mathcal{X}|^3)\) computation⁸. Since the KB problem mainly focuses on the regime where \(|\mathcal{X}|\) is extremely large (e.g., as in Corollary 2, we must consider the case \(|\mathcal{X}| = \Theta(T^{d/2})\) for a continuous domain), \(O(|\mathcal{X}|^3)\) computation per round is computationally infeasible. We tackle this efficiency issue in the next section.

4 Exponential-weight algorithm with RLS-based Nyström approximation↩︎

Our second algorithm is a computationally efficient variant of kernelized Exp3, called RLS-kernelized Exp3. Due to space limitations, the pseudocode is provided in Alg. 5 in Appendix 9. The huge computational cost in kernelized Exp3 stems from calculating the inverse of the \(|\mathcal{X}| \times |\mathcal{X}|\)-matrix \(G_t(\lambda)\). We mitigate this burden via a low-rank approximation of the feature map weighted by the distribution \(P_t\). Specifically, the resulting approximation is built on a Nyström approximation for the weighted kernel function \(\widetilde{k}_t(\boldsymbol{x}, \boldsymbol{x}') \mathrel{\vcenter{:}}= \sqrt{P_t(\boldsymbol{x}) P_t(\boldsymbol{x}')}k(\boldsymbol{x}, \boldsymbol{x}')\)⁹.

At each round \(t\), let \(\mathbf{S}_t \in \mathbb{R}^{|\mathcal{X}| \times s_t}\) be a matrix, whose only single element in each column is strictly positive, and other elements are \(0\). Here, \(s_t \in [|\mathcal{X}|]\) is determined within the algorithm as described later. Note that we can use \(\mathbf{S}_t\) to extract the \(s_t\) weighted columns of some matrix \(\boldsymbol{M} \in \mathbb{R}^{|\mathcal{X}| \times |\mathcal{X}|}\) by multiplying from the right as \(\boldsymbol{M}\mathbf{S}_t\). Thus, as with [7], we call \(\mathbf{S}_t\) a sampling matrix. We also define the weighted feature matrix \(\bar{\mathbf{\Psi}}_t = (\sqrt{P_t(\boldsymbol{x}^{(1)})} \psi(\boldsymbol{x}^{(1)}), \ldots, \sqrt{P_t(\boldsymbol{x}^{(|\mathcal{X}|)})} \psi(\boldsymbol{x}^{(|\mathcal{X}|)})) \in \mathbb{R}^{|\mathcal{X}| \times |\mathcal{X}|}\), where we arbitrarily index the elements of \(\mathcal{X}\) as \(\mathcal{X}= \{\boldsymbol{x}^{(i)}\}_{i\in[|\mathcal{X}|]}\). Note that \(G_t(\lambda) = \bar{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\) holds from the definition. Furthermore, note that \(\bar{\mathbf{\Psi}}_t\) corresponds to the feature matrix of the weighted kernel function \(\widetilde{k}_t(\boldsymbol{x}, \boldsymbol{x}')\). In our algorithm, we approximate \(G_t(\lambda)\) by projecting \(\bar{\mathbf{\Psi}}_t\) into the column span of \(\bar{\mathbf{\Psi}}_t \mathbf{S}_t\). To be more specific, let us define the orthogonal projection matrix \(\mathbf{Q}_t \mathrel{\vcenter{:}}= (\bar{\mathbf{\Psi}}_t \mathbf{S}_t) [(\bar{\mathbf{\Psi}}_t \mathbf{S}_t)^{\top} (\bar{\mathbf{\Psi}}_t \mathbf{S}_t)]^{\dagger}(\bar{\mathbf{\Psi}}_t \mathbf{S}_t)^{\top} \in \mathbb{R}^{|\mathcal{X}| \times |\mathcal{X}|}\), where \(\boldsymbol{M}^{\dagger}\) represents the pseudo-inverse of matrix \(\boldsymbol{M}\). Then, RLS-kernelized Exp3 is constructed by replacing quantities \(\widehat{f}_t\) and \(\|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}\) in kernelized Exp3 with their low-rank approximated versions: \(\widetilde{f}_t(\cdot) \mathrel{\vcenter{:}}= \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} (\mathbf{Q}_t \psi(\boldsymbol{x}_t)) f_t(\boldsymbol{x}_t)\) and \(\widetilde{\sigma}_t(\boldsymbol{x}) \mathrel{\vcenter{:}}= \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}\), respectively, where \(\widetilde{G}_t(\lambda) = (\mathbf{Q}_t \bar{\mathbf{\Psi}}_t) (\mathbf{Q}_t \bar{\mathbf{\Psi}}_t)^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\). After elementary matrix calculations, we can obtain the following identities, which can be efficiently calculated (See Lemma 7 for the detailed derivation): \[\begin{align} \tag{6} \widetilde{f}_t(\boldsymbol{x}) &= \frac{f_t(\boldsymbol{x}_t)}{\sqrt{P_t(\boldsymbol{x})P_t(\boldsymbol{x}_t)}}\phi_t(\boldsymbol{x})^{\top} \left(\sum_{\boldsymbol{x}' \in \mathcal{X}} \phi_t(\boldsymbol{x}') \phi_t(\boldsymbol{x}')^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{s_t}\right)^{-1} \phi_t(\boldsymbol{x}_t), \\ \tag{7} \widetilde{\sigma}_t^2(\boldsymbol{x}) &= \frac{T}{\lambda P_t(\boldsymbol{x})} \left(\widetilde{k}_t(\boldsymbol{x}, \boldsymbol{x}) - \phi_t(\boldsymbol{x})^{\top} \phi_t(\boldsymbol{x})\right) + \frac{1}{P_t(\boldsymbol{x})} \phi_t(\boldsymbol{x})^{\top} \left(\sum_{\boldsymbol{x}' \in \mathcal{X}} \phi_t(\boldsymbol{x}') \phi_t(\boldsymbol{x}')^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{s_t}\right)^{-1} \phi_t(\boldsymbol{x}), \end{align}\] where \(\phi_t(\boldsymbol{x}) = [(\mathbf{S}_t^{\top} \widetilde{\mathbf{K}}_t \mathbf{S}_t)^{1/2}]^{\dagger} \mathbf{S}_t^{\top} \widetilde{\boldsymbol{k}}_t(\boldsymbol{x}) \in \mathbb{R}^{s_t}\) with the weighted kernel matrix \(\widetilde{\mathbf{K}}_t \mathrel{\vcenter{:}}= [\widetilde{k}_t(\boldsymbol{x}^{(i)}, \boldsymbol{x}^{(j)})]_{i,j \in [|\mathcal{X}|]} \in \mathbb{R}^{|\mathcal{X}| \times |\mathcal{X}|}\) and the weighted kernel vector \(\widetilde{\boldsymbol{k}}_t(\boldsymbol{x}) \mathrel{\vcenter{:}}= [\widetilde{k}_t(\boldsymbol{x}, \boldsymbol{x}^{(i)})]_{i \in [|\mathcal{X}|]} \in \mathbb{R}^{|\mathcal{X}|}\). The quantity \(\phi_t(\boldsymbol{x})\) is referred to as the Nyström embedding [15], [49] associated with the weighted kernel function \(\widetilde{k}_t\). From the above expressions, we can easily confirm that the calculation of \([\widetilde{f}_t(\boldsymbol{x})]_{\boldsymbol{x}\in \mathcal{X}}\) and \([\widetilde{\sigma}_t^2(\boldsymbol{x})]_{\boldsymbol{x}\in \mathcal{X}}\) requires only \(O(|\mathcal{X}| s_t^2 + s_t^3)\)-computation (see the first paragraph in Appendix 12 for details). This drastically improves on the \(O(|\mathcal{X}|^3)\)-computational cost of the original kernelized Exp3 when \(s_t \ll |\mathcal{X}|\).

4.0.0.1 Selection of the sampling matrix.

A remaining question is how to define the sampling matrix \(\mathbf{S}_t \in \mathbb{R}^{|\mathcal{X}| \times s_t}\) such that the effect of the approximation does not severely degrade the algorithm performance, while maintaining \(s_t \ll |\mathcal{X}|\). To do so, we leverage the RLS-based Nyström approximation methods [7], [60], in which we can guarantee both the approximation accuracy of the kernel and small \(s_t\). Specifically, we adopt the recursive RLS-Nyström algorithm proposed in [7] (Alg. 3) as a subroutine to obtain \(\mathbf{S}_t\) (Line 7 in Alg. 5).

4.0.0.2 Regret and computational cost for RLS-kernelized Exp3.

By combining Lemma 1 with the existing guarantees in [7], we observe that the recursive RLS-Nyström subroutine attains sufficient approximation accuracy to ensure \(\widetilde{O}(\sqrt{T \gamma_T})\) regret with \(s_t = \widetilde{O}(\gamma_T)\) and requires only \(\widetilde{O}(|\mathcal{X}|\gamma_T^2)\)-computation with high-probability. As a result, we can obtain the following Theorem 3, which formally describes the regret and computational cost guarantees of RLS-kernelized Exp3.

The full proof is provided in Appendix 12. The above theorem confirms that RLS-kernelized Exp3 is nearly optimal while offering improved computational complexity. Compared with the regret guarantees of the original kernelized Exp3 (Corollary 1), the price of the improved computational efficiency is only a constant factor in the regret upper bound, which is hidden in the implied constant of \(\bar{R}_T = O(\sqrt{T \gamma_T \log |\mathcal{X}|})\).

4.0.0.3 Remarks on Nyström approximation.

Although we leverage the recursive RLS-Nyström algorithm in [7] as a subroutine of our algorithm, other approximation methods may be applicable as long as (i) they have the spectral guarantees of the projection matrix (Eq. 81 in the appendix), and (ii) their computational cost guarantees are quantified by effective dimension of the weighted kernel \(\widetilde{k}_t\) (see the proof of Lemma 8). However, to our knowledge, no existing method provides both strictly better computational efficiency and tighter regret bounds than those in Theorem 3.

4.0.0.4 Remarks on exploration distribution.

Note that an \(O(|\mathcal{X}|(T\gamma_T)^{3/2})\) pre-processing cost for the preparation of the exploration distribution is required even for RLS-kernelized Exp3 (see the last paragraph in Sec. 3). If this overhead is unacceptable, one can approximate the MVR-sequence itself via recursive RLS-Nyström, which alleviates \(O(|\mathcal{X}|(T\gamma_T)^{3/2})\) computation while maintaining the nearly-optimal guarantees of regret. This variant of RLS-kernelized Exp3 is given in Appendix 14. Another approach is to replace the MVR-based distribution with a simpler one, e.g., the uniform distribution. We discuss such possible choices for the exploration distribution in Appendix 16; however, based on the known theoretical tools for KB, we are not aware of any choice that strictly reduces the computational cost of MVR-based exploration distributions without imposing further restrictive assumptions on the kernel.

Finally, although this paper mainly focuses on the theoretical side, the simulation experiments for supporting our superior guarantees are provided in Appendix 17.

5 Lower bounds↩︎

The following Theorem 4 provides the lower bounds for adversarial KB under \(k = k_{\mathrm{SE}}\) or \(k = k_{\mathrm{Mat}}\).

The full proof is in Appendix 13. From Theorem 4, we confirm that kernelized Exp3 and RLS-kernelized Exp3 are optimal up to polylogarithmic factors for the SE and Matérn kernels with \(\nu > 1\). Compared with the lower bounds for the stochastic setting [51], there is an additional multiplicative logarithmic factor \((\log T)^{-1/2}\) and \((\log T)^{-\frac{\nu}{2\nu + d}}\) in the lower bounds for the SE and \(\nu\)-Matérn kernels, respectively. As clarified in the proof sketch below, these logarithmic factors arise because our proof reduces the adversarial problem to a stochastic KB lower bound under a Gaussian noise.

5.0.0.1 Proof sketch.

We consider an environment that reduces the lower bound for adversarial KB to that for stochastic KB by setting: \(f_t(\cdot) = f(\cdot) + \widetilde{\eta}_t k(\boldsymbol{0}, \cdot)\), where \(\widetilde{\eta}_t \sim \mathcal{N}(0, \sigma^2)\) for some variance \(\sigma^2 > 0\), and \(\|f\|_k \leq B/2\). Through a slight modification of the lower bounds for stochastic KB [46], [51], we can show that \(\sup_{\boldsymbol{x}\in \mathcal{X}} \mathbb{E}[\sum_{t=1}^T f_t(\boldsymbol{x}) - f_t(\boldsymbol{x}_t)] = \Omega(\underline{R}(T, \sigma^2))\), where \(\underline{R}(T, \sigma^2) = \sqrt{\sigma^{2} T(\log (T/\sigma^2))^{d/2}}\) and \(\underline{R}(T, \sigma^2) = \sigma^{\frac{2\nu}{2\nu+d}} T^{\frac{\nu+d}{2\nu+d}}\) for \(k = k_{\mathrm{SE}}\) and \(k = k_{\mathrm{Mat}}\), respectively. While this constitutes a lower bound on the expected regret, the above problem instance does not satisfy Assumption 1 since \(\|f_t\|_k \leq B\) may be violated due to the unboundedness of the Gaussian noise \(\widetilde{\eta}_t\). Therefore, the only lower bound we can rigorously obtain from the above problem instance is the looser lower bound: \(\Omega(\underline{R}(T, \sigma^2)) - \sup_{\boldsymbol{x}\in \mathcal{X}} \mathbb{E}[1l\{\exists t \in [T], \|f_t\|_k > B\}(\sum_{t=1}^T f_t(\boldsymbol{x}) - f_t(\boldsymbol{x}_t))]\), where the contribution of the event \(\{\exists t \in [T], \|f_t\|_k > B\}\) in the original lower bound is explicitly eliminated (rigorous argument is in Appendix 13). To ensure the second term remains negligible, it is sufficient to set \(\sigma^2\) as \(\sigma^2 = \Theta((\log T)^{-1})\) based on the tail properties of the Gaussian noise. Then, the lower bounds \(\Omega(\underline{R}(T, \Theta((\log T)^{-1})))\) matches Eq. 8 .

6 Discussions↩︎

In this section, we discuss both the limitations of our work and potential avenues for future research.

6.0.0.1 Algorithm without discretization.

For a continuous input domain, our algorithms require reducing the original problem to a finite input domain via discretization. Such discretization is commonly used in the stochastic KB analysis [11], [20]; however, a limitation of this approach is that the algorithm becomes computationally infeasible as the dimension \(d\) increases. This drawback motivates the development of algorithms that operate directly on continuous domains. For example, the kernelized extension of continuous exponential weight and follow-the-regularized leader in the adversarial LB setting [44] may be a promising direction for future research.

6.0.0.2 Refining lower bounds.

Our lower bound has the undesirable dependence on the logarithmic factors. As described in Sec. 5, the source of this worse dependence is that we use the lower bound for stochastic KB under the Gaussian noise model in the proof. Thus, this gap could be addressed in future research by investigating lower bounds for other noise models, such as bounded noise.

6.0.0.3 Kernelized variants for further advanced topics.

Finally, it is interesting to study the other kernelized variants of further advanced topics in the adversarial bandit literature, such as first-order bounds [61], [62], variation-bounded regret [63], [64], and best-of-both-world algorithms [65], [66]. We believe that the theoretical tools leveraged in Secs. 3 and 4 are helpful for these future directions.

7 Conclusion↩︎

We investigated a nearly-optimal algorithm for adversarial KB. We showed that the kernelized version of the Exp3 algorithm achieves nearly-optimal regret by bridging the gap between the existing information-gain-based arguments for GP and the analysis of Exp3. Furthermore, we proposed a computationally efficient algorithm that leverages RLS-based Nyström approximation. As noted in the discussions in the previous section, we believe that this research opens several avenues for future research on the adversarial KB problem.

Acknowledgment↩︎

We appreciate the helpful comments from Jonathan Scarlett and Yu-Jie Zhang on revising the paper.

8 Notation table↩︎

Tab. 2 summarizes the notations used in this paper.

9 Pseudocode↩︎

In this section, we provide the pseudocode for the algorithms that could not be included in the main text due to space limitations. Alg. 2 is the pseudocode of the MVR algorithm leveraged in the preparation of the exploration distribution \(\pi\) in our algorithm. Algs. 3 and 5 are the pseudocode of the recursive RLS-Nyström algorithm and the RLS-kernelized Exp3 algorithm described in Sec. 4, respectively. Note that Alg. 5 is identical to the original Alg. 2 in [7] except for some changes of notations. Furthermore, Alg. 6 represents the pseudocode of the variant of RLS-kernelized Exp3, which uses an approximated MVR sequence for the exploration distribution as described in the last paragraph in Sec. 4 and Appendix 14. Finally, Alg. 4 is the pseudocode of the algorithm for generating an approximated MVR sequence leveraged in Alg. 6.

10 Proof of Lemma 1↩︎

11 Proof of Theorem 1↩︎

From Lemma 2, each reward function \(f_t\) can be rewritten as \(f_t(\cdot) = \psi(\cdot)^{\top} \boldsymbol{\theta}_t\), where \(\boldsymbol{\theta}_t\) is drawn by the environment. Note that \(\boldsymbol{\theta}_t\) and \(\boldsymbol{x}_t\) are conditionally independent given \(\mathcal{H}_{t-1}\) as defined in the problem setting. Here, we first remind the following three basic facts used in various parts of our proof: (i) \(\mathbb{E}[g(\boldsymbol{x}_t) | \mathcal{H}_{t-1}] = \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) g(\boldsymbol{x})\) holds for any (measurable) fixed function \(g\), (ii) \(\mathbb{E}[g(\boldsymbol{x}_t) | \mathcal{H}_{t-1}] = \mathbb{E}[g(\boldsymbol{x}_t) | \mathcal{H}_{t-1}, \boldsymbol{\theta}_{t}]\) holds from the conditional independence of \(\boldsymbol{x}_t\) and \(\boldsymbol{\theta}_t\) given \(\mathcal{H}_{t-1}\), and (iii) \(\mathbb{E}[h(\mathcal{H}_{t-1}, \boldsymbol{\theta}_t) g(\boldsymbol{x}_t) | \mathcal{H}_{t-1}, \boldsymbol{\theta}_t] = h(\mathcal{H}_{t-1}, \boldsymbol{\theta}_t) \mathbb{E}[g(\boldsymbol{x}_t) | \mathcal{H}_{t-1}, \boldsymbol{\theta}_t]\) for any (measurable) fixed functions \(g\) and \(h\).

Next, from the tower property of conditional expectation, we have \(\mathbb{E}[\sum_{t=1}^T f_t(\boldsymbol{x}_t)] = \sum_{t=1}^T \mathbb{E}[\mathbb{E}[f_t(\boldsymbol{x}_t) \mid \mathcal{H}_{t-1}, \boldsymbol{\theta}_t]] = \sum_{t=1}^T \mathbb{E}[\sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) f_t(\boldsymbol{x})]\), where the second equality follows from \[\begin{align} \mathbb{E}[f_t(\boldsymbol{x}_t) \mid \mathcal{H}_{t-1}, \boldsymbol{\theta}_t] &= \mathbb{E}[\boldsymbol{\theta}_t^{\top} \psi(\boldsymbol{x}_t) \mid \mathcal{H}_{t-1}, \boldsymbol{\theta}_t] = \boldsymbol{\theta}_t^{\top}\mathbb{E}[\psi(\boldsymbol{x}_t) \mid \mathcal{H}_{t-1}, \boldsymbol{\theta}_t] \\ &= \boldsymbol{\theta}_t^{\top}\mathbb{E}[\psi(\boldsymbol{x}_t) \mid \mathcal{H}_{t-1}] = \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \boldsymbol{\theta}_t^{\top} \psi(\boldsymbol{x}) = \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) f_t(\boldsymbol{x}). \end{align}\] Thus, we have \[\label{eq:first95tower95property} \bar{R}_T = \sum_{t=1}^T \mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) f_t(\boldsymbol{x})\right],\tag{11}\] where \(\boldsymbol{x}^{\ast} \in \operatornamewithlimits{argmax}_{\boldsymbol{x}\in \mathcal{X}} \mathbb{E}[\sum_{t=1}^T f_t(\boldsymbol{x})]\). Note that \(\boldsymbol{x}^{\ast}\) is always well-defined since \(|\mathcal{X}| < \infty\). Furthermore, \[\begin{align} &\mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) f_t(\boldsymbol{x})\right] \\ &= \alpha \mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} \pi(\boldsymbol{x}) f_t(\boldsymbol{x})\right] + (1 - \alpha) \mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) f_t(\boldsymbol{x})\right] \\ \label{eq:first95perreg95ub} &\leq 2\alpha B + (1 - \alpha) \mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) f_t(\boldsymbol{x})\right], \end{align}\tag{12}\] where the last inequality follows from \(\|f_t\|_{\infty} \leq \|f_t\|_{k} \leq B\). Here, we further decompose the second term of the above equation by using the optimistic estimate \(u_t(\boldsymbol{x})\) as follows: \[\begin{align} &\mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) f_t(\boldsymbol{x})\right] \\ \label{eq:decomp} & = \underbrace{\mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - u_t(\boldsymbol{x}^{\ast})\right]}_{\text{(i)}} + \underbrace{\mathbb{E}\left[u_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) u_t(\boldsymbol{x})\right]}_{\text{(ii)}} + \underbrace{\mathbb{E}\left[\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(u_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right]}_{\text{(iii)}}. \end{align}\tag{13}\]

11.0.0.1 Upper bound for the first term (i) in Eq. 13 .

From the definition of \(u_t(\boldsymbol{x}^{\ast})\), we have \[f(\boldsymbol{x}^{\ast}) - u_t(\boldsymbol{x}^{\ast}) = f_t(\boldsymbol{x}^{\ast}) - \widehat{f}_t(\boldsymbol{x}^{\ast}) - \beta \|\psi(\boldsymbol{x}^{\ast})\|_{G_t(\lambda)^{-1}}.\] By noting the definition of \(\widehat{f}_t\) and \(f_t(\cdot) = \psi(\cdot)^{\top} \boldsymbol{\theta}_t\) (Lemma 2), the error term \(f_t(\boldsymbol{x}^{\ast}) - \widehat{f}_t(\boldsymbol{x}^{\ast})\) in the above equation can be rewritten as follows: \[\begin{align} f_t(\boldsymbol{x}^{\ast}) - \widehat{f}_t(\boldsymbol{x}^{\ast}) &= \psi(\boldsymbol{x}^{\ast})^{\top} \boldsymbol{\theta}_t - \psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t) f_t(\boldsymbol{x}_t) \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \boldsymbol{\theta}_t - \psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \left(\boldsymbol{I}_{|\mathcal{X}|} - G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top}\right) \boldsymbol{\theta}_t. \end{align}\] By noting that \(\boldsymbol{\theta}_t\) is conditionally independent of \(\boldsymbol{x}_t\) given \(\mathcal{H}_{t-1}\), we have \[\begin{align} \mathbb{E}[f_t(\boldsymbol{x}^{\ast}) - \widehat{f}_t(\boldsymbol{x}^{\ast}) \mid \mathcal{H}_{t-1}, \boldsymbol{\theta}_t] &= \psi(\boldsymbol{x}^{\ast})^{\top} \left(\boldsymbol{I}_{|\mathcal{X}|} - G_t(\lambda)^{-1} \mathbb{E}[ \psi(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} \mid \mathcal{H}_{t-1}, \boldsymbol{\theta}_t]\right) \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \left[G_t(\lambda)^{-1} \left(G_t(\lambda) - \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x})\psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \right)\right] \boldsymbol{\theta}_t \\ \label{eq:cond95error95i} &= \frac{\lambda}{T} \psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-1} \boldsymbol{\theta}_t, \end{align}\tag{14}\] where the last line follows from the definition of \(G_t(\lambda) \mathrel{\vcenter{:}}= \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x})\psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} + \frac{\lambda}{T}\boldsymbol{I}_{|\mathcal{X}|}\). From Schwartz’s inequality and \(\|\boldsymbol{\theta}_t\|_2 = \|f_t\|_{k} \leq B\) (Lemma 2), we have \[\begin{align} \frac{\lambda}{T} \psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-1} \boldsymbol{\theta}_t &\leq \frac{\lambda}{T} \|\psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-1}\|_2 \|\boldsymbol{\theta}_t\|_2 \\ &\leq B \frac{\lambda}{T} \sqrt{\psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-2} \psi(\boldsymbol{x}^{\ast})} \\ &\leq B \sqrt{\frac{\lambda}{T}} \sqrt{\psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}^{\ast})} \\ \label{eq:ub95schwartz} &= B \sqrt{\frac{\lambda}{T}} \|\psi(\boldsymbol{x}^{\ast})\|_{G_t(\lambda)^{-1}}, \end{align}\tag{15}\] where the last inequality follows from \(\psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-2} \psi(\boldsymbol{x}^{\ast}) \leq \frac{T}{\lambda} \psi(\boldsymbol{x}^{\ast})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}^{\ast})\), which is implied by the fact that the maximum eigenvalue of \(G_t(\lambda)^{-1}\) is bounded from above by \(T/\lambda\). From Eqs. 14 and 15 , we have \[\begin{align} \mathbb{E}[f_t(\boldsymbol{x}^{\ast}) - u_t(\boldsymbol{x}^{\ast})] &= \mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \widehat{f}_t(\boldsymbol{x}^{\ast}) - \beta \|\psi(\boldsymbol{x}^{\ast})\|_{G_t(\lambda)^{-1}}\right] \\ &= \mathbb{E}[\mathbb{E}[f_t(\boldsymbol{x}^{\ast}) - \widehat{f}_t(\boldsymbol{x}^{\ast})\mid \mathcal{H}_{t-1}, \boldsymbol{\theta}_t]] - \mathbb{E}[\beta \|\psi(\boldsymbol{x}^{\ast})\|_{G_t(\lambda)^{-1}}] \\ &\leq \mathbb{E}\left[\left(B \sqrt{\frac{\lambda}{T}} - \beta\right) \|\psi(\boldsymbol{x}^{\ast})\|_{G_t(\lambda)^{-1}}\right] \\ \label{eq:final95i} &= 0. \end{align}\tag{16}\] Thus, the first term (i) in Eq. 13 is bounded from above by \(0\).

11.0.0.2 Upper bound for the second term (ii) in Eq. 13 .

For any \(\boldsymbol{x}\in \mathcal{X}\), the definition of the exploration distribution implies the following upper bound of \(u_t(\boldsymbol{x})\) (Lemma 6): \[u_t(\boldsymbol{x}) \leq \frac{2}{\alpha} (2 B \gamma_{T} + \beta \sqrt{\gamma_T}).\] By combining the above inequality with the definition of \(\alpha\), we can observe that \(\eta u_t(\boldsymbol{x}) \leq 1\) holds for any \(\boldsymbol{x}\in \mathcal{X}\); therefore, by following the standard proof for Exp3 (Lemma 5), we obtain \[\begin{align} \label{eq:ut95put95first95ub} \sum_{t=1}^T u_t(\boldsymbol{x}^{\ast}) - \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) u_t(\boldsymbol{x}) \leq \frac{\log |\mathcal{X}|}{\eta} + \eta \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) u_t^2(\boldsymbol{x}). \end{align}\tag{17}\] Regarding the term \(\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) u_t^2(\boldsymbol{x})\), we further obtain the upper bound as follows: \[\begin{align} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) u_t^2(\boldsymbol{x}) &= \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widehat{f}_t(\boldsymbol{x}) + \beta \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}\right)^2 \\ \label{eq:ut95var95decomp} &\leq 2 \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widehat{f}_t^2(\boldsymbol{x}) + 2 \beta^2 \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}^2, \end{align}\tag{18}\] where we used \(\forall a, b \in \mathbb{R},~(a + b)^2 \leq 2a^2 + 2b^2\) in the last inequality. Here, note that the following relation: \[\begin{align} \label{eq:Ptilde95Gt95rel} (1-\alpha) \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|} \preceq \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|} \mathrel{\vcenter{:}}= G_t(\lambda). \end{align}\tag{19}\] Thus, for \(M_t(\lambda) \mathrel{\vcenter{:}}= \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} + \frac{\lambda}{\lceil T (1 - \alpha) \rceil} \boldsymbol{I}_{|\mathcal{X}|}\), we can confirm \[G_t(\lambda)^{-1} \preceq \frac{1}{1-\alpha} \left(\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} + \frac{\lambda}{T (1 - \alpha) } \boldsymbol{I}_{|\mathcal{X}|}\right)^{-1} \preceq \frac{1}{1-\alpha} M_t(\lambda)^{-1}.\] The above relation further implies \[\label{eq:tilde95p95psi} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}^2 \leq \frac{1}{1-\alpha} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{M_t(\lambda)^{-1}}^2 \leq \frac{4 \gamma_{\lceil T (1 - \alpha) \rceil}}{1-\alpha} \leq \frac{4 \gamma_{T}}{1-\alpha},\tag{20}\] where the second inequality follows from Lemma 1. Therefore, by noting the definition of \(\beta\), the second term in Eq. 18 is bounded from above as follows: \[\label{eq:ut95var95decomp95ub2} 2 \beta^2 \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}^2 \leq \frac{8 \lambda B^2 \gamma_{T}}{(1-\alpha) T}.\tag{21}\] Next, regarding the first term \(\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widehat{f}_t^2(\boldsymbol{x})\) in Eq. 18 , we have \[\begin{align} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widehat{f}_t^2(\boldsymbol{x}) &= \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left[\psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t)f_t(\boldsymbol{x}_t)\right]^2 \\ &\leq B^2 \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left[\psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t)\right]^2 \\ &= \frac{B^2}{1 - \alpha} \psi(\boldsymbol{x}_t)^{\top} G_t(\lambda)^{-1} \left[\sum_{\boldsymbol{x}\in \mathcal{X}} (1 - \alpha) \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top}\right] G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t) \\ \label{eq:ut95var95decomp95ub1} &\leq \frac{B^2}{1 - \alpha} \psi(\boldsymbol{x}_t)^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t). \end{align}\tag{22}\] Thus, by aggregating Eqs. 17 , 18 , 21 , and 22 , we have \[\begin{align} &\mathbb{E}\left[\sum_{t=1}^T u_t(\boldsymbol{x}^{\ast}) - \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) u_t(\boldsymbol{x}) \right] \\ &\leq \frac{\log |\mathcal{X}|}{\eta} + \frac{8 \eta \lambda B^2 \gamma_T}{1 - \alpha} + \frac{2\eta B^2}{1 - \alpha} \sum_{t=1}^T \mathbb{E}\left[\psi(\boldsymbol{x}_t)^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t)\right] \\ \tag{23} &= \frac{\log |\mathcal{X}|}{\eta} + \frac{8 \eta \lambda B^2 \gamma_T}{1 - \alpha} + \frac{2\eta B^2}{1-\alpha} \sum_{t=1}^T \mathbb{E}\left[ \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}^2\right] \\ \tag{24} &\leq \frac{\log |\mathcal{X}|}{\eta} + \frac{8 \eta \lambda B^2 \gamma_T}{1 - \alpha} + \frac{8\eta B^2 T \gamma_T}{1-\alpha}, \end{align}\] where Eq. 23 follows from the tower property of conditional expectation, and Eq. 24 follows from Lemma 1.

11.0.0.3 Upper bound for the third term (iii) in Eq. 13 .

By noting the definition of \(u_t\), we have \[\begin{align} \label{eq:third95iii95ub} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(u_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right) &= \beta \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}} + \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widehat{f}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right). \end{align}\tag{25}\] Regarding the first term in Eq. 25 , the applications of Jensen’s inequality for the square root \(\sqrt{x}\) and Eq. 20 imply \[\begin{align} \beta \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}} &\leq \beta \sqrt{\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}^2} \\ \label{eq:bias95ub95iii} &\leq 2B\sqrt{\frac{\lambda \gamma_T}{(1 - \alpha)T}}. \end{align}\tag{26}\] Regarding the second term in Eq. 25 , we have \[\begin{align} \widehat{f}_t(\boldsymbol{x}) - f_t(\boldsymbol{x}) &= \psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t) f_t(\boldsymbol{x}_t) - f_t(\boldsymbol{x}) \\ &= \psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} \boldsymbol{\theta}_t - \psi(\boldsymbol{x})^{\top} \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x})^{\top} \left(G_t(\lambda)^{-1} \psi(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} - \boldsymbol{I}_{|\mathcal{X}|}\right) \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x})^{\top} \left[G_t(\lambda)^{-1} \left(\psi(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} - G_t(\lambda)\right)\right] \boldsymbol{\theta}_t. \end{align}\] Thus, we have the following identities from the above equation: \[\begin{align} &\mathbb{E}\left[\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x})\left(\widehat{f}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] \\ &= \mathbb{E}\left[\mathbb{E}\left[ \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x})\left(\widehat{f}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right) ~\middle|~ \mathcal{H}_{t-1}, \boldsymbol{\theta}_t \right]\right] \\ &= \mathbb{E}\left[\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \left[G_t(\lambda)^{-1} \left(\mathbb{E}\left[\psi(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top}~\middle|~ \mathcal{H}_{t-1}, \boldsymbol{\theta}_t\right] - G_t(\lambda)\right)\right] \boldsymbol{\theta}_t\right] \\ \label{eq:exp95identity95iii} &= \frac{\lambda}{T}\mathbb{E}\left[\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \boldsymbol{\theta}_t\right]. \end{align}\tag{27}\] The upper bound of the quantity in the above expectation can be further obtained as \[\begin{align} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \boldsymbol{\theta}_t &\leq \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \sqrt{\psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-2} \psi(\boldsymbol{x})} \|\boldsymbol{\theta}_t\|_2 \\ &\leq B \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \sqrt{\psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-2} \psi(\boldsymbol{x})} \\ &\leq B \sqrt{\frac{T}{\lambda}} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \sqrt{\psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x})} \\ &\leq B \sqrt{\frac{T}{\lambda}} \sqrt{\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x})} \\ \label{eq:exp95inside95iii} &\leq 2B \sqrt{\frac{T \gamma_T}{(1 - \alpha)\lambda}}. \end{align}\tag{28}\] Thus, by aggregating Eqs. 25 , 26 , 27 , and 28 , the upper bound of the third term (iii) in Eq. 13 is obtained as follows: \[\label{eq:final95iii} \mathbb{E}\left[\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(u_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] \leq 4B\sqrt{\frac{\lambda \gamma_T}{(1-\alpha)T}}.\tag{29}\]

11.0.0.4 Aggregate all the upper bounds.

From Eqs. 11 ,  12 , 13 , 16 , 24 , and 29 , we finally obtain \[\begin{align} \bar{R}_T &\leq 2\alpha B T + \frac{(1 - \alpha) \log |\mathcal{X}|}{\eta} + 8 \eta \lambda B^2 \gamma_T + 8\eta B^2 T \gamma_T + 4B\sqrt{(1-\alpha) \lambda T \gamma_T} \\ &\leq 2\alpha B T + \frac{\log |\mathcal{X}|}{\eta} + 8 \eta (\lambda + T) B^2 \gamma_T + 4B\sqrt{\lambda T \gamma_T}. \end{align}\] 0◻

12 Proof of Theorem 3↩︎

12.0.0.1 Proof for computational complexity.

Here, for any \(t \in [T]\), we define the event \(A_t\) as follows: \[\label{eq:thm95rke395proof95eps95acc} \frac{1}{2}\left(\bar{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\right) \preceq \bar{\mathbf{\Psi}}_t \mathbf{S}_t \mathbf{S}_t^{\top} \bar{\mathbf{\Psi}}_t^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|} \preceq \frac{3}{2}\left(\bar{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\right).\tag{30}\] From Lemma 8, we can confirm that \(\mathbb{P}(A_t \mid \widetilde{\mathcal{H}}_{t-1}) \geq 1 - 1/T^3\) for any \(t \in [T]\) and \(\widetilde{\mathcal{H}}_{t-1} \mathrel{\vcenter{:}}= \{(\mathbf{S}_i, \boldsymbol{x}_i, f_i(\boldsymbol{x}_i))\}_{i \in [t-1]}\), which implies \(\mathbb{P}(A_t) \geq 1 - 1/T^3\) due to the tower property of conditional expectation. By taking the union bound, we can obtain \(\mathbb{P}\left(A\right) \geq 1 - 1/T^2\), where \(A = \bigcap_{t \in [T]} A_t\). Furthermore, Lemma 8 suggests that, with probability at least \(1-1/T^2\), the following two statements simultaneously also hold:

1. The number \(s_t\) satisfies \(s_t = O(\gamma_T \log(T\gamma_T)) = O(\gamma_T \log(T))\) for any \(t \in [T]\)¹¹.

2. The computational cost of recursive RLS-Nyström is \(O(|\mathcal{X}|\gamma_T^2 (\log(T\gamma_T))^2) = O(|\mathcal{X}|\gamma_T^2 (\log T)^2)\).

Here, we confirm the computational cost of \((\widetilde{f}_t(\boldsymbol{x}))_{\boldsymbol{x}\in \mathcal{X}}\) and \((\widetilde{\sigma}_t^2(\boldsymbol{x}))_{\boldsymbol{x}\in \mathcal{X}}\) is \(O(|\mathcal{X}|s_t^2 + s_t^3)\). Firstly, the computation of Nyström embedding \(\phi_t(\cdot)\) requires the calculation of pseudo-inverse \([(\mathbf{S}_t^{\top} \widetilde{K}_t \mathbf{S}_t)^{1/2}]^{\dagger}\), which require \(O(s_t^3)\)-computation. Once \([(\mathbf{S}_t^{\top} \widetilde{K}_t \mathbf{S}_t)^{1/2}]^{\dagger}\) is computed, the calculation of \(\phi_t(\boldsymbol{x}) \mathrel{\vcenter{:}}= [(\mathbf{S}_t^{\top} \widetilde{K}_t \mathbf{S}_t)^{1/2}]^{\dagger}\mathbf{S}_t^{\top} \widetilde{k}(\boldsymbol{x})\) can be conducted within \(O(s_t^2)\) for some given \(\boldsymbol{x}\in \mathcal{X}\). Thus, the computational cost for the preparation of \((\phi_t(\boldsymbol{x}))_{\boldsymbol{x}\in \mathcal{X}}\) is \(O(|\mathcal{X}|s_t^2 + s_t^3)\). After calculating \((\phi_t(\boldsymbol{x}))_{\boldsymbol{x}\in \mathcal{X}}\), we require \(O(|\mathcal{X}|s_t^2)\) and \(O(s_t^3)\) computations for calculating \(\sum_{\boldsymbol{x}' \in \mathcal{X}} \phi_t(\boldsymbol{x}') \phi_t(\boldsymbol{x}')^{\top}\) and \((\sum_{\boldsymbol{x}' \in \mathcal{X}} \phi_t(\boldsymbol{x}') \phi_t(\boldsymbol{x}')^{\top} + \lambda/T \boldsymbol{I}_{s_t})^{-1}\), respectively. Once we obtained the inverse \((\sum_{\boldsymbol{x}' \in \mathcal{X}} \phi_t(\boldsymbol{x}') \phi_t(\boldsymbol{x}')^{\top} + \lambda/T \boldsymbol{I}_{s_t})^{-1}\), the calculation of the quadratic form \(\phi_t(\boldsymbol{x})^{\top} (\sum_{\boldsymbol{x}' \in \mathcal{X}} \phi_t(\boldsymbol{x}') \phi_t(\boldsymbol{x}')^{\top} + \lambda/T \boldsymbol{I}_{s_t})^{-1} \phi_t(\boldsymbol{x})\) for all \(\boldsymbol{x}\in \mathcal{X}\) requires \(O(|\mathcal{X}| s_t^2)\). In summary, given the sampling matrix \(\mathbf{S}_t\), the overall computational cost for round \(t\) is \(O(|\mathcal{X}|s_t^2 + s_t^3)\). By combining this with the above two high probability statements, we can confirm that the total computational cost at each round \(t\) is \(\widetilde{O}(|\mathcal{X}|\gamma_T^2 + \gamma_T^3)\) with high probability.

12.0.0.2 Proof for regret upper bound.

We first define the following notations, while some of them are already defined in Sec. 4:

• Let \(\mathbf{S}_t \in \mathbb{R}^{|\mathcal{X}| \times s}\) be the sampling matrix at round \(t\) returned by recursive RLS-Nyström.

• Let \(\bar{\mathbf{\Psi}}_t \mathrel{\vcenter{:}}= (\bar{\psi}_t(\boldsymbol{x}^{(1)}), \ldots, \bar{\psi}_t(\boldsymbol{x}^{(|\mathcal{X}|)})) \in \mathbb{R}^{|\mathcal{X}| \times |\mathcal{X}|}\), where \(\bar{\psi}_t(\boldsymbol{x}) \mathrel{\vcenter{:}}= \sqrt{P_t(\boldsymbol{x})} \psi(\boldsymbol{x})\) be a weighted feature map.

• Let \(\mathbf{Q}_t \mathrel{\vcenter{:}}= \bar{\mathbf{\Psi}}_t \mathbf{S}_t \left[(\bar{\mathbf{\Psi}}_t \mathbf{S}_t)^{\top} (\bar{\mathbf{\Psi}}_t \mathbf{S}_t)\right]^{\dagger} (\bar{\mathbf{\Psi}}_t \mathbf{S}_t)^{\top}\) be the projection matrix into the subspace spanned by the column vectors of \(\bar{\mathbf{\Psi}}_t \mathbf{S}_t\). We also define \(\widetilde{\psi}_t(\boldsymbol{x})\) as \(\widetilde{\psi}_t(\boldsymbol{x}) = \mathbf{Q}_t \psi(\boldsymbol{x})\).

• Let \(\widetilde{G}_t(\lambda)\) be \(\widetilde{G}_t(\lambda) = \mathbf{Q}_t \bar{\mathbf{\Psi}}_t (\mathbf{Q}_t \bar{\mathbf{\Psi}}_t)^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\), which is the approximated version of \(G_t(\lambda) \mathrel{\vcenter{:}}= \bar{\mathbf{\Psi}}_t\bar{\mathbf{\Psi}}_t^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|} = \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \psi(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\).

• Let \(\widetilde{\mathbf{\Psi}}_t \mathrel{\vcenter{:}}= \mathbf{Q}_t \bar{\mathbf{\Psi}}_t\) be the projected version of \(\bar{\mathbf{\Psi}}_t\).

In the proof of this section, we define \(\widetilde{\mathcal{H}}_{t}\) as the learner’s history up to round \(t\): \(\widetilde{\mathcal{H}}_{t} = \{(\mathbf{S}_i, \boldsymbol{x}_i, f_i(\boldsymbol{x}_i))\}_{i \in [t]}\). Here, from the algorithm construction, note that \(\boldsymbol{\theta}_t\), \(\boldsymbol{x}_t\), and \(\mathbf{S}_t\) are conditionally independent given \(\widetilde{\mathcal{H}}_{t-1}\). As described in Sec. 4, note that the following identities hold (see also Lemma 7): \[\begin{align} \widetilde{f}_t(\boldsymbol{x}) &= \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\psi}_t(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} \boldsymbol{\theta}_t, \\ \widetilde{u}_t(\boldsymbol{x}) &= \widetilde{f}_t(\boldsymbol{x}) + \beta \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}. \end{align}\] To prove Theorem 3, as with the proof of Theorem 1, we decompose \(f_t(\boldsymbol{x}^{\ast}) - f(\boldsymbol{x}_t)\) as follows: \[\begin{align} \label{eq:decomp95reg95rls95exp3} \mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - f_t(\boldsymbol{x}_t)\right] \leq 2 \alpha B + (1 - \alpha) \mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) f_t(\boldsymbol{x})\right], \end{align}\tag{31}\] where \(\boldsymbol{x}^{\ast} \in \operatornamewithlimits{argmax}_{\boldsymbol{x}\in \mathcal{X}} \mathbb{E}[\sum_{t=1}^T f_t(\boldsymbol{x})]\). Now, we decompose the second term in Eq. 31 into the following three terms similarly to the proof of Theorem 1: \[\begin{align} &\mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) f_t(\boldsymbol{x})\right] \\ \label{eq:thm95rke395decomp} &= \underbrace{\mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \widetilde{u}_t(\boldsymbol{x}^{\ast})\right]}_{\text{(i)}} + \underbrace{\mathbb{E}\left[\widetilde{u}_t(\boldsymbol{x}^{\ast}) - \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{u}_t(\boldsymbol{x})\right]}_{\text{(ii)}} + \underbrace{\mathbb{E}\left[\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{u}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right]}_{\text{(iii)}}. \end{align}\tag{32}\] Below, we consider the upper bound of terms (i), (ii), and (iii).

12.0.0.3 Upper bound for the first term (i) in Eq. 32 .

By noting the definition of \(\widetilde{f}_t\) and \(f_t(\cdot) = \psi(\cdot)^{\top} \boldsymbol{\theta}_t\), the error term \(f_t(\boldsymbol{x}^{\ast}) - \widetilde{f}_t(\boldsymbol{x}^{\ast})\) in the above equation can be rewritten as follows: \[\begin{align} f_t(\boldsymbol{x}^{\ast}) - \widetilde{f}_t(\boldsymbol{x}^{\ast}) &= \psi(\boldsymbol{x}^{\ast})^{\top} \boldsymbol{\theta}_t - \psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\psi}_t(\boldsymbol{x}_t) f_t(\boldsymbol{x}_t) \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \boldsymbol{\theta}_t - \psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\psi}_t(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \left(\boldsymbol{I}_{|\mathcal{X}|} - \widetilde{G}_t(\lambda)^{-1} \widetilde{\psi}_t(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top}\right) \boldsymbol{\theta}_t. \end{align}\] Then, we have \[\begin{align} &\mathbb{E}[f_t(\boldsymbol{x}^{\ast}) - \widetilde{f}_t(\boldsymbol{x}^{\ast}) \mid \widetilde{\mathcal{H}}_{t-1}, \mathbf{S}_t, \boldsymbol{\theta}_t] \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \left(\boldsymbol{I}_{|\mathcal{X}|} - \widetilde{G}_t(\lambda)^{-1} \mathbb{E}[ \widetilde{\psi}_t(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} \mid \widetilde{\mathcal{H}}_{t-1}, \mathbf{S}_t, \boldsymbol{\theta}_t]\right) \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \left[\widetilde{G}_t(\lambda)^{-1} \left(\widetilde{G}_t(\lambda) - \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \widetilde{\psi}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \right)\right] \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \left(\widetilde{\mathbf{\Psi}}_t \widetilde{\mathbf{\Psi}}_t^{\top} - \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\right) \boldsymbol{\theta}_t \\ \label{eq:decomp95est95ftilde} &= \frac{\lambda}{T} \psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \boldsymbol{\theta}_t + \psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \left(\widetilde{\mathbf{\Psi}}_t \widetilde{\mathbf{\Psi}}_t^{\top} - \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top}\right) \boldsymbol{\theta}_t. \end{align}\tag{33}\] Regarding the first term in Eq. 33 , we have \[\begin{align} \frac{\lambda}{T} \psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \boldsymbol{\theta}_t &\leq \frac{\lambda}{T} \|\psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1}\|_2 \|\boldsymbol{\theta}_t\|_2 \\ &\leq B \frac{\lambda}{T} \sqrt{\psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-2} \psi(\boldsymbol{x}^{\ast})} \\ &\leq B \sqrt{\frac{\lambda}{T}} \sqrt{\psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \psi(\boldsymbol{x}^{\ast})} \\ &= B \sqrt{\frac{\lambda}{T}} \|\psi(\boldsymbol{x}^{\ast})\|_{\widetilde{G}_t(\lambda)^{-1}}. \end{align}\] Regarding the second term in Eq. 33 , under \((\widetilde{\mathcal{H}}_{t-1}, \boldsymbol{\theta}_t, \boldsymbol{S}_t)\) such that event \(A_t\) is true, we have \[\begin{align} &\psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \left(\widetilde{\mathbf{\Psi}}_t \widetilde{\mathbf{\Psi}}_t^{\top} - \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top}\right) \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \left(\widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} \mathbf{Q}_t^{\top} - \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top}\right) \boldsymbol{\theta}_t \\ &= \psi(\boldsymbol{x}^{\ast})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} \left(\mathbf{Q}_t - \boldsymbol{I}_{|\mathcal{X}|}\right) \boldsymbol{\theta}_t \\ &\leq \|\psi(\boldsymbol{x}^{\ast})\|_{\widetilde{G}_t(\lambda)^{-1}} \|\widetilde{G}_t(\lambda)^{-1/2} \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} \left(\mathbf{Q}_t - \boldsymbol{I}_{|\mathcal{X}|}\right) \boldsymbol{\theta}_t \|_2 \\ &\leq B \|\psi(\boldsymbol{x}^{\ast})\|_{\widetilde{G}_t(\lambda)^{-1}} \|\widetilde{G}_t(\lambda)^{-1/2} \widetilde{\mathbf{\Psi}}_t\| \|\bar{\mathbf{\Psi}}_t^{\top} \left(\mathbf{Q}_t - \boldsymbol{I}_{|\mathcal{X}|}\right) \| \\ \tag{34} &\leq B \|\psi(\boldsymbol{x}^{\ast})\|_{\widetilde{G}_t(\lambda)^{-1}} \|\bar{\mathbf{\Psi}}_t^{\top} \left(\mathbf{Q}_t - \boldsymbol{I}_{|\mathcal{X}|}\right) \| \\ \tag{35} &\leq B \sqrt{\frac{2\lambda}{T}}\|\psi(\boldsymbol{x}^{\ast})\|_{\widetilde{G}_t(\lambda)^{-1}}, \end{align}\] where Eq. 34 follows from \(\|\widetilde{G}_t(\lambda)^{-1/2} \widetilde{\mathbf{\Psi}}_t\| = \sqrt{\|\widetilde{\mathbf{\Psi}}_t^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\mathbf{\Psi}}_t\|} \leq 1\), and Eq. 35 follows from \(\|\bar{\mathbf{\Psi}}_t^{\top} \left(\mathbf{Q}_t - \boldsymbol{I}_{|\mathcal{X}|}\right)\| = \sqrt{\|\bar{\mathbf{\Psi}}_t^{\top} \left(\mathbf{Q}_t - \boldsymbol{I}_{|\mathcal{X}|}\right) \bar{\mathbf{\Psi}}_t\|} \leq \sqrt{\frac{2\lambda}{T}}\), which is implied by the fact that \(\bar{\mathbf{\Psi}}_t^{\top} \left(\boldsymbol{I}_{|\mathcal{X}|} - \mathbf{Q}_t\right) \bar{\mathbf{\Psi}}_t \preceq \frac{2\lambda}{T} \bar{\mathbf{\Psi}}_t^{\top} (\bar{\mathbf{\Psi}} \bar{\mathbf{\Psi}}_t^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|})^{-1} \bar{\mathbf{\Psi}}_t \preceq \frac{2\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\) holds from Lemma 11. Thus, we have \[\begin{align} &\mathbb{E}[f_t(\boldsymbol{x}^{\ast}) - \widetilde{u}_t(\boldsymbol{x}^{\ast})] \\ &\leq \mathbb{E}\left[1l\{A_t\} \left(f_t(\boldsymbol{x}^{\ast}) - \widetilde{u}_t(\boldsymbol{x}^{\ast})\right)\right] + \mathbb{P}\left(A_t^c\right)\left(B + \frac{BT}{\lambda} + \beta \sqrt{\frac{T}{\lambda}}\right) \\ &\leq \mathbb{E}\left[1l\{A_t\} \mathbb{E}\left[f_t(\boldsymbol{x}^{\ast}) - \widetilde{u}_t(\boldsymbol{x}^{\ast}) \mid \widetilde{\mathcal{H}}_{t-1}, \boldsymbol{\theta}_t, \mathbf{S}_t\right]\right] + \frac{1}{T^3}\left(B + \frac{BT}{\lambda} + \beta \sqrt{\frac{T}{\lambda}}\right) \\ &\leq \mathbb{E}\left[1l\{A_t\} \left(B \sqrt{\frac{\lambda}{T}} \left(\sqrt{2} + 1\right) - \beta\right) \|\psi(\boldsymbol{x}^{\ast})\|_{\widetilde{G}_t(\lambda)^{-1}}\right] + \frac{1}{T^3}\left(B + \frac{BT}{\lambda} + \beta \sqrt{\frac{T}{\lambda}}\right) \\ \label{eq:rke395final95i} &= \frac{B}{T^3}\left(\frac{T}{\lambda} + \sqrt{2} + 2\right). \end{align}\tag{36}\]

12.0.0.4 Upper bound for the second term (ii) in Eq. 32 .

For any \(\boldsymbol{x}\in \mathcal{X}\), the definition of the exploration distribution implies the following upper bound of \(\widetilde{u}_t(\boldsymbol{x})\) under event \(A\) (Lemma 9): \[\widetilde{u}_t(\boldsymbol{x}) \leq \frac{2\sqrt{3}}{\alpha} \left(2\sqrt{2} B \gamma_{T} + \beta \sqrt{\gamma_T}\right).\] By combining the above inequality with the definition of \(\alpha\), we can observe that \(\eta \widetilde{u}_t(\boldsymbol{x}) \leq 1\) holds for any \(\boldsymbol{x}\in \mathcal{X}\) under \(A\); therefore, by following the standard proof for Exp3 (Lemma 5), we obtain the following inequality under event \(A\): \[\begin{align} \label{eq:rke395ut95put95first95ub} \sum_{t=1}^T \widetilde{u}_t(\boldsymbol{x}^{\ast}) - \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{u}_t(\boldsymbol{x}) \leq \frac{\log |\mathcal{X}|}{\eta} + \eta \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{u}_t^2(\boldsymbol{x}). \end{align}\tag{37}\] Regarding the term \(\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{u}_t^2(\boldsymbol{x})\), we further obtain the upper bound as follows: \[\begin{align} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{u}_t^2(\boldsymbol{x}) &= \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{f}_t(\boldsymbol{x}) + \beta \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}\right)^2 \\ \label{eq:rke395ut95var95decomp} &\leq 2 \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{f}_t^2(\boldsymbol{x}) + 2 \beta^2 \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}^2, \end{align}\tag{38}\] As with the proof of Theorem 1 (Eqs. 19 –21 ), under event \(A\), the second term in Eq. 38 is bounded from above as follows: \[\label{eq:rke395ut95var95decomp95ub2} 2 \beta^2 \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}^2 \leq 6 \beta^2 \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}^2 \leq \frac{24 \lambda B^2 \gamma_{T}}{(1-\alpha) T},\tag{39}\] where the first inequality follows from Lemma 10 and event \(A_t\). Thus, we have \[\begin{align} &\mathbb{E}\left[1l\{A\}\left(\sum_{t=1}^T \widetilde{u}_t(\boldsymbol{x}^{\ast}) - \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{u}_t(\boldsymbol{x})\right) \right] \\ &\leq \mathbb{E}\left[1l\{A\}\left(\frac{\log |\mathcal{X}|}{\eta} + \eta \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{u}_t^2(\boldsymbol{x})\right) \right] \\ &\leq \frac{\log |\mathcal{X}|}{\eta} + \mathbb{E}\left[1l\{A\}\left( 2\eta \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{f}_t^2(\boldsymbol{x}) + 2 \eta \beta^2 \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}^2\right) \right] \\ \label{eq:rke395A95ut95Ptilde95ut} &\leq \frac{\log |\mathcal{X}|}{\eta} + \frac{24 \eta \lambda B^2 \gamma_{T}}{1-\alpha} + 2\eta \sum_{t=1}^T \mathbb{E}\left[1l\{A\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{f}_t^2(\boldsymbol{x}) \right]. \end{align}\tag{40}\] Furthermore, we have \[\begin{align} &\mathbb{E}\left[1l\{A\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{f}_t^2(\boldsymbol{x}) \right] \\ &\leq \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \widetilde{f}_t^2(\boldsymbol{x}) \right] \\ &\leq B^2 \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left[\psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\psi}_t(\boldsymbol{x}_t)\right]^2\right] \\ &= B^2 \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\psi}_t(\boldsymbol{x}_t) \widetilde{\psi}_t(\boldsymbol{x}_t)^{\top} \widetilde{G}_t(\lambda)^{-1} \psi(\boldsymbol{x})\right] \\ &= B^2 \mathbb{E}\left[\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\psi}_t(\boldsymbol{x}_t) \widetilde{\psi}_t(\boldsymbol{x}_t)^{\top} \widetilde{G}_t(\lambda)^{-1} \psi(\boldsymbol{x}) \mid \widetilde{\mathcal{H}}_{t-1}, \mathbf{S}_t\right]\right] \\ \tag{41} &= B^2 \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \mathbb{E}\left[\widetilde{\psi}_t(\boldsymbol{x}_t) \widetilde{\psi}_t(\boldsymbol{x}_t)^{\top} \mid \widetilde{\mathcal{H}}_{t-1}, \mathbf{S}_t \right] \widetilde{G}_t(\lambda)^{-1} \psi(\boldsymbol{x})\right] \\ \tag{42} &\leq B^2 \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \psi(\boldsymbol{x})\right] \\ \tag{43} &\leq 3 B^2 \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} G_t(\lambda)^{-1} \psi(\boldsymbol{x})\right] \\ \tag{44} &\leq \frac{12 B^2 \gamma_T}{1 - \alpha}, \end{align}\] where Eq. 41 follows from the fact that \(A_t\), \(\widetilde{P}_t(\cdot)\), \(\widetilde{G}_t(\lambda)\), and \(\widetilde{\psi}_t(\cdot)\) are deterministic given \(\widetilde{\mathcal{H}}_{t-1}\), \(\mathbf{S}_t\). Furthermore, Eq. 42 follows from \(\|\widetilde{G}_t(\lambda)^{-1/2} \mathbb{E}\left[\widetilde{\psi}_t(\boldsymbol{x}_t) \widetilde{\psi}_t(\boldsymbol{x}_t)^{\top} \mid \widetilde{\mathcal{H}}_{t-1}, \mathbf{S}_t \right] \widetilde{G}_t(\lambda)^{-1/2}\| \leq 1\) , which is implied by \(\mathbb{E}\left[\widetilde{\psi}_t(\boldsymbol{x}_t) \widetilde{\psi}_t(\boldsymbol{x}_t)^{\top} \mid \widetilde{\mathcal{H}}_{t-1}, \mathbf{S}_t\right] = \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \widetilde{\psi}_t(\boldsymbol{x}) \widetilde{\psi}_t(\boldsymbol{x})^{\top}\) and \(\widetilde{G}_t(\lambda) = \sum_{\boldsymbol{x}\in \mathcal{X}} P_t(\boldsymbol{x}) \widetilde{\psi}_t(\boldsymbol{x}) \widetilde{\psi}_t(\boldsymbol{x})^{\top} + \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\). In addition, Eq. 43 is implied by leveraging event \(A_t\) with Lemma 10. Hence, from Eqs. 40 and 44 , we have \[\begin{align} &\mathbb{E}\left[\sum_{t=1}^T u_t(\boldsymbol{x}^{\ast}) - \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) u_t(\boldsymbol{x}) \right] \\ &\leq \mathbb{E}\left[1l\{A^c\} \left(\sum_{t=1}^T u_t(\boldsymbol{x}^{\ast}) - \sum_{t=1}^T \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) u_t(\boldsymbol{x})\right) \right] + \frac{\log |\mathcal{X}|}{\eta} + \frac{24 \eta \lambda B^2 \gamma_{T}}{1-\alpha} + \frac{24 \eta B^2 T \gamma_T}{1 - \alpha} \\ \tag{45} &\leq 2 T\left(\frac{BT}{\lambda} + \beta \sqrt{\frac{T}{\lambda}}\right) \mathbb{P}(A^c) + \frac{\log |\mathcal{X}|}{\eta} + \frac{24 \eta \lambda B^2 \gamma_{T}}{1-\alpha} + \frac{24 \eta B^2 T \gamma_T}{1 - \alpha} \\ \tag{46} &\leq \frac{2B}{T} \left(\frac{T}{\lambda} + \sqrt{2} + 1\right) + \frac{\log |\mathcal{X}|}{\eta} + \frac{24 \eta B^2 (\lambda + T) \gamma_{T}}{1-\alpha}, \end{align}\] where Eq. 45 follows from Lemma 12, and Eq. 46 follows from \(\mathbb{P}(A^c) \leq 1/T^2\) and the definition of \(\beta\).

12.0.0.5 Upper bound for the third term (iii) in Eq. 32 .

From Lemma 12 and the inequality \(\mathbb{P}(A_t^c) \leq 1/T^3\), we have \[\begin{align} &\mathbb{E}\left[\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{u}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] \\ &= \mathbb{E}\left[1l\{A_t^c\}\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{u}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] + \mathbb{E}\left[1l\{A_t\}\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{u}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] \\ &\leq \frac{1}{T^3} \left(B + \frac{BT}{\lambda} + \beta \sqrt{\frac{T}{\lambda}}\right) + \mathbb{E}\left[1l\{A_t\}\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{u}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] \\ \label{eq:rke395iii95first95exp} &\leq \frac{B}{T^3} \left(\frac{T}{\lambda} + \sqrt{2} + 2\right) + \mathbb{E}\left[1l\{A_t\}\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{u}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right]. \end{align}\tag{47}\] Here, we can rewrite the second term as \[\begin{align} &\mathbb{E}\left[1l\{A_t\}\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{u}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] \\ \label{eq:rke395iii95At95decomp} &= \mathbb{E}\left[1l\{A_t\}\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{f}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] + \beta \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}\right]. \end{align}\tag{48}\] Then, we have \[\begin{align} &\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{f}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] \\ &= \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \left(\widetilde{G}_t(\lambda)^{-1} \widetilde{\psi}_t(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} - \boldsymbol{I}_{|\mathcal{X}|}\right) \boldsymbol{\theta}_t\right] \\ &= \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \left[\widetilde{G}_t(\lambda)^{-1} \left(\widetilde{\psi}_t(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} - \widetilde{G}_t(\lambda)\right)\right] \boldsymbol{\theta}_t\right] \\ &= \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \left[\widetilde{G}_t(\lambda)^{-1} \left( \mathbb{E}\left[\widetilde{\psi}_t(\boldsymbol{x}_t) \psi(\boldsymbol{x}_t)^{\top} \mid \widetilde{\mathcal{H}}_{t-1}, \mathbf{S}_t, \boldsymbol{\theta}_t\right] - \widetilde{G}_t(\lambda)\right)\right] \boldsymbol{\theta}_t\right] \\ &= \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \left[\widetilde{G}_t(\lambda)^{-1} \left( \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} - \widetilde{\mathbf{\Psi}}_t \widetilde{\mathbf{\Psi}}_t^{\top} - \frac{\lambda}{T} \boldsymbol{I}_{|\mathcal{X}|}\right)\right] \boldsymbol{\theta}_t\right] \\ \label{eq:rke395ftilde95f95decomp} \begin{aligned} &= \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} \left(\boldsymbol{I}_{|\mathcal{X}|} - \mathbf{Q}_t\right) \boldsymbol{\theta}_t\right] \\ &~~~~- \frac{\lambda}{T}\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \boldsymbol{\theta}_t\right]. \end{aligned} \end{align}\tag{49}\] Similar to the derivation for the upper bound of the first term (i) in Eq. 32 , we examine the upper bound of the above two terms. Regarding the first term, we have \[\begin{align} &\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} \left(\boldsymbol{I}_{|\mathcal{X}|} - \mathbf{Q}_t\right) \boldsymbol{\theta}_t\right] \\ &\leq B\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}} \left\|\widetilde{G}_t(\lambda)^{-1/2} \widetilde{\mathbf{\Psi}}_t \bar{\mathbf{\Psi}}_t^{\top} \left(\boldsymbol{I}_{|\mathcal{X}|} - \mathbf{Q}_t\right) \right\|\right] \\ \label{eq:rke395ftilde95f95first} &\leq B \sqrt{\frac{2\lambda}{T}} \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}\right]. \end{align}\tag{50}\] Regarding the second term \(-\frac{\lambda}{T}\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \boldsymbol{\theta}_t\right]\), we have \[\begin{align} -\frac{\lambda}{T}\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \boldsymbol{\theta}_t\right] &\leq \frac{\lambda}{T}\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) |\psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1} \boldsymbol{\theta}_t|\right] \\ &\leq \frac{B\lambda}{T}\mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})^{\top} \widetilde{G}_t(\lambda)^{-1}\|_2\right] \\ \label{eq:rke395ftilde95f95second} &\leq B\sqrt{\frac{\lambda}{T}} \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}\right]. \end{align}\tag{51}\] Hence, by aggregating Eqs. 47 , 48 , 49 , 50 , and 51 , we have \[\begin{align} &\mathbb{E}\left[\sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \left(\widetilde{u}_t(\boldsymbol{x}) - f_t(\boldsymbol{x})\right)\right] \\ &\leq \frac{B}{T^3} \left(\frac{T}{\lambda} + \sqrt{2} + 2\right) + 2(1 + \sqrt{2}) B \sqrt{\frac{\lambda}{T}} \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{\widetilde{G}_t(\lambda)^{-1}}\right] \\ &\leq \frac{B}{T^3} \left(\frac{T}{\lambda} + \sqrt{2} + 2\right) + 2\sqrt{3}(1 + \sqrt{2}) B \sqrt{\frac{\lambda}{T}} \mathbb{E}\left[1l\{A_t\} \sum_{\boldsymbol{x}\in \mathcal{X}} \widetilde{P}_t(\boldsymbol{x}) \|\psi(\boldsymbol{x})\|_{G_t(\lambda)^{-1}}\right] \\ \label{eq:rke395final95iii} &\leq \frac{B}{T^3} \left(\frac{T}{\lambda} + \sqrt{2} + 2\right) + 4 \sqrt{3}(1 + \sqrt{2}) B \sqrt{\frac{\lambda \gamma_T}{(1-\alpha)T}}. \end{align}\tag{52}\]

12.0.0.6 Aggregate all the upper bounds.

From Eqs. 31 ,  32 , 36 , 46 , and 52 , we finally obtain \[\begin{align} \begin{aligned} \bar{R}_T &\leq 2\alpha B T + (1-\alpha) \Biggl[\frac{B}{T^2}\left(\frac{T}{\lambda} + \sqrt{2} + 2\right) + \frac{2B}{T} \left(\frac{T}{\lambda} + \sqrt{2} + 1\right) \\ &~~~+ \frac{\log |\mathcal{X}|}{\eta} + \frac{24 \eta B^2 (\lambda + T) \gamma_{T}}{1-\alpha} + \frac{B}{T^2} \left(\frac{T}{\lambda} + \sqrt{2} + 2\right) + 4 \sqrt{3}(1 + \sqrt{2}) B \sqrt{\frac{\lambda T \gamma_T}{1-\alpha}}\Biggr] \end{aligned} \\ \begin{align} &\leq 2\alpha B T + \frac{2B}{T^2}\left(\frac{T}{\lambda} + \sqrt{2} + 2\right) + \frac{2B}{T} \left(\frac{T}{\lambda} + \sqrt{2} + 1\right) \\ &~~~+ \frac{\log |\mathcal{X}|}{\eta} + 24 \eta B^2 (\lambda + T) \gamma_{T} + 4 \sqrt{3}(1 + \sqrt{2}) B \sqrt{\lambda T \gamma_T}. \end{align} \end{align}\] In the above upper bound, the additional term \(\frac{2B}{T^2}\left(\frac{T}{\lambda} + \sqrt{2} + 2\right) + \frac{2B}{T} \left(\frac{T}{\lambda} + \sqrt{2} + 1\right)\) is \(O(1)\) and does not affect the growth rate of regret. Furthermore, the remaining term: \(2\alpha B T + 24 \eta B^2 (\lambda + T) \gamma_{T} + 4 \sqrt{3} (1 + \sqrt{2}) B \sqrt{\lambda T \gamma_T}\) is the same as the upper bound in Theorem 1 up to constant factors. Thus, we complete the proof. 0◻

13 Proof of Theorem 4↩︎

We define the noise function \(g_t\) as \(g_t(\cdot) = \frac{\eta_t B}{2 \sqrt{2 \log (2T^2)}} k(\boldsymbol{0}, \cdot)\), where \(\eta_t \sim \mathcal{N}(0, 1)\). We assume that \((\eta_t)_{t \in N_+}\) is mutually-independent. Then, we consider the following two problem instances (i.e., strategies of the environment) based on some common function \(f \in \mathcal{F}_k(B/2) \mathrel{\vcenter{:}}= \{f \in \mathcal{H}_k \mid \|f\|_k \leq B/2\}\) and \((\eta_t)_{t \in \mathbb{N}_+}\):

• Problem instance 1. The environment defines \(f_t\) as \(f_t(\cdot) = f(\cdot) + g_t(\cdot)\).

• Problem instance 2. The environment defines \(f_t\) as \(f_t(\cdot) = f(\cdot) + 1l\{|\eta_t| < \sqrt{2 \log (2T^2)} \} g_t(\cdot) + 1l\{|\eta_t| \geq \sqrt{2 \log (2T^2)} \} \text{sign}(\eta_t) \frac{B}{2} k(\boldsymbol{0}, \cdot)\).

In the above definition, the problem instance 1 does not always satisfy \(\|f_t\|_k \leq B\). On the other hand, for any realization, problem instance 2 always satisfies \(\|f_t\|_k \leq B\). Next, we derive a lower bound for problem instance 2 using problem instance 1. Here, we use the notations \(\mathbb{E}^{(1)}[\cdot]\) and \(\mathbb{P}^{(1)}(\cdot)\) as the expectation and probability under problem instance 1. Similarly, we also define \(\mathbb{E}^{(2)}[\cdot]\) and \(\mathbb{P}^{(2)}(\cdot)\). Then, for any algorithm, we have \[\begin{align} \sup_{\boldsymbol{x}\in \mathcal{X}}\mathbb{E}^{(2)}[R_T(\boldsymbol{x})] &= \sup_{\boldsymbol{x}\in \mathcal{X}}\mathbb{E}^{(2)}\left[\sum_{t=1}^T f_t(\boldsymbol{x}) - f_t(\boldsymbol{x}_t)\right] \\ \tag{53} &= \sup_{\boldsymbol{x}\in \mathcal{X}}\mathbb{E}^{(2)}\left[\sum_{t=1}^T f(\boldsymbol{x}) - f(\boldsymbol{x}_t)\right] \\ \tag{54} &\geq \sup_{\boldsymbol{x}\in \mathcal{X}}\mathbb{E}^{(2)}\left[ 1l\left\{\forall i \in [T], |\eta_i| < \sqrt{2 \log (2T^2)}\right\} \sum_{t=1}^T (f(\boldsymbol{x}) - f(\boldsymbol{x}_t))\right] \\ \tag{55} &= \sup_{\boldsymbol{x}\in \mathcal{X}}\mathbb{E}^{(1)}\left[ 1l\left\{\forall i \in [T], |\eta_i| < \sqrt{2 \log (2T^2)}\right\} \sum_{t=1}^T (f(\boldsymbol{x}) - f(\boldsymbol{x}_t))\right] \\ \tag{56} &\geq \sup_{\boldsymbol{x}\in \mathcal{X}}\mathbb{E}^{(1)}\left[\sum_{t=1}^T f(\boldsymbol{x}) - f(\boldsymbol{x}_t)\right] - BT \mathbb{P}^{(1)}\left(\exists t \in [T],~|\eta_t| \geq \sqrt{2 \log (2T^2)}\right), \end{align}\] where:

• Eq. 53 follows from the symmetry of the Gaussian distribution. Namely, \(\mathbb{E}[1l\{|\eta_t| < \sqrt{2 \log (2T^2)} \} g_t(\boldsymbol{x}) + 1l\{|\eta_t| \geq \sqrt{2 \log (2T^2)} \} \text{sign}(\eta_t) \frac{B}{2} k(\boldsymbol{0}, \boldsymbol{x})] = 0\) for any fixed \(\boldsymbol{x}\in \mathcal{X}\). Furthermore, the independence between \(\boldsymbol{x}_t\) and \(\eta_t\) also implies \(\mathbb{E}[1l\{|\eta_t| < \sqrt{2 \log (2T^2)} \} g_t(\boldsymbol{x}_t) + 1l\{|\eta_t| \geq \sqrt{2 \log (2T^2)} \} \text{sign}(\eta_t) \frac{B}{2} k(\boldsymbol{0}, \boldsymbol{x}_t)] = 0\).

• Eq. 54 follows from the fact that \(\sum_{t=1}^T f(\boldsymbol{x}^{\ast}) - f(\boldsymbol{x}_t) > 0\) always holds for the maximizer \(\boldsymbol{x}^{\ast}\) of \(f\). (Note that such \(\boldsymbol{x}^{\ast}\) always exists since \(\mathcal{X}\) is compact and the continuity of \(f\) under \(k= k_{\mathrm{SE}}\) and \(k = k_{\mathrm{Mat}}\).)

• Eq. 55 uses the fact that the expectation of \(1l\left\{\forall i \in [T], |\eta_i| < \sqrt{2 \log (2T^2)}\right\} \sum_{t=1}^T (f(\boldsymbol{x}) - f(\boldsymbol{x}_t))\) under instance \(1\) equals that under instance \(2\) from the definitions. To see this rigorously, we first assume that the learner’s algorithm is deterministic. Then, we can rewrite \(\boldsymbol{x}_t\) as the function of \(\boldsymbol{\eta}_{t-1} \mathrel{\vcenter{:}}= (\eta_1, \ldots, \eta_{t-1})\) such as \(\boldsymbol{x}_t = \boldsymbol{x}_t(\boldsymbol{\eta}_{t-1})\). Then, we can write \[\begin{align} &\mathbb{E}^{(2)}\left[1l\left\{\forall i \in [T], |\eta_i| < \sqrt{2 \log (2T^2)}\right\} \sum_{t=1}^T (f(\boldsymbol{x}) - f(\boldsymbol{x}_t))\right] \\ &= \int_{\boldsymbol{\eta}_{T-1} \in (-\sqrt{2 \log (2T^2)}, \sqrt{2 \log (2T^2)})^{T-1}} \sum_{t=1}^T \left[f(\boldsymbol{x}) - f(\boldsymbol{x}_t(\boldsymbol{\eta}_{t-1}))\right] \mathbb{P}_{\boldsymbol{\eta}_{T-1}}(\text{d}\boldsymbol{\eta}_{T-1}). \end{align}\] Note that the distribution of \(\mathbb{P}_{\boldsymbol{\eta}_{T-1}}(\cdot)\) is the same across instances 1 and 2, and \(\boldsymbol{x}_t(\boldsymbol{\eta}_{t-1})\) is also common under event \(\boldsymbol{\eta}_{T-1} \in (-\sqrt{2 \log (2T^2)}, \sqrt{2 \log (2T^2)})^{T-1}\), since the learner’s history \(\mathcal{H}_{t-1} \mathrel{\vcenter{:}}=( \boldsymbol{x}_1, f_1(\boldsymbol{x}_1), \ldots, \boldsymbol{x}_{t-1}, f_{t-1}(\boldsymbol{x}_{t-1}))\) is the common between two instances then. Thus, we can confirm \(\mathbb{E}^{(2)}\left[1l\left\{\forall i \in [T], |\eta_i| < \sqrt{2 \log (2T^2)}\right\} \sum_{t=1}^T (f(\boldsymbol{x}) - f(\boldsymbol{x}_t))\right] = \mathbb{E}^{(1)}\left[1l\left\{\forall i \in [T], |\eta_i| < \sqrt{2 \log (2T^2)}\right\} \sum_{t=1}^T (f(\boldsymbol{x}) - f(\boldsymbol{x}_t))\right]\). Finally, for a stochastic algorithm of the learner, the same argument is valid by rewriting \(\boldsymbol{x}_t\) as the function form: \(\boldsymbol{x}_t(\mathcal{H}_{t-1}, (z_i)_{i \in [t]})\), where \(z_i \sim \mathrm{Unif}(\mathcal{X})\) is used to represent additional randomness (see, e.g., Definition 1 in [67]).

• Eq. 56 follows from \(\mathbb{E}^{(1)}[1l\{\exists t \in [T],~|\eta_t| \geq \sqrt{2 \log (2T^2)}\}\sum_{t=1}^T(f(\boldsymbol{x}^{\ast}) - f(\boldsymbol{x}_t))] \leq BT \mathbb{E}^{(1)}[1l\{\exists t \in [T],~|\eta_t| \geq \sqrt{2 \log (2T^2)}\}]\), which is implied by \(\|f\|_{\infty} \leq \|f\|_k \leq B/2\).

Regarding the first term in Eq. 56 , there exists a function \(f \in \mathcal{F}_k(B/2)\) such that \(\sup_{\boldsymbol{x}\in \mathcal{X}}\mathbb{E}^{(1)}\left[\sum_{t=1}^T f(\boldsymbol{x}) - f(\boldsymbol{x}_t)\right] = \Omega(\underline{R}(T, \sigma_T^2))\), where \(\sigma_T^2 = \frac{B^2}{8 \log T}\) (see Lemma 16). Here, we defined \(\underline{R}(T, \sigma)\) as \(\underline{R}(T, \sigma^2) = \sqrt{\sigma^{2} T(\log (T/\sigma^2))^{d/2}}\) and \(\underline{R}(T, \sigma^2) = \sigma^{\frac{2\nu}{2\nu+d}} T^{\frac{\nu+d}{2\nu+d}}\) for \(k = k_{\mathrm{SE}}\) and \(k = k_{\mathrm{Mat}}\), respectively. Regarding the second term, we use the union bound with the fact \(\mathbb{P}(|\eta_t| \geq \sqrt{2 \log (2T^2)}) \leq 1/T^2\), which follows from the basic concentration inequality: \(\forall m \geq 0, \mathbb{P}(|\eta_t| \geq m) \leq 2\exp(-m^2/2)\). Then, we obtain \(BT \mathbb{P}^{(1)}\left(\exists t \in [T],~|\eta_t| \geq \sqrt{2 \log (2T^2)}\right) \leq B\). Thus, the second term is negligible compared to the first term since \(B = \Theta(1)\). Consequently, we conclude that there exists a problem instance (strategy of the environment) such that \[\sup_{\boldsymbol{x}\in \mathcal{X}}\mathbb{E}^{(2)}[R_T(\boldsymbol{x})] = \Omega(\underline{R}(T, \sigma_T^2)).\] By simplifying the constant factors in the above equation, we obtain the desired results. 0◻

14 RLS-kernelized Exp3 with approximated MVR-sequence↩︎

As described in the last paragraph of Sec. 4, by applying recursive RLS-Nyström, we can alleviate the computational cost of preparation of the MVR-based exploration distribution. Alg. 6 provides this variant of RLS-kernelized Exp3. The difference from the original RLS-kernelized Exp3 is the definition of the exploration distribution \(\widetilde{\pi}\), which is calculated by the approximated MVR algorithm in Alg. 4. With proper modification of the parameters and proof, we can obtain the following theorem, which provides the improved computational cost for the preparation of the exploration distribution, while maintaining the same per-round computational cost and regret upper bound in Theorem 3.

14.0.0.1 Computational cost.

Here, by assuming \(|\mathcal{X}| \gg T\), we study and simplify the computational cost \(\widetilde{O}\left(\sum_{t=1}^{\lceil T\alpha \rceil} (t\gamma_t^2 + \gamma_t^3 + |\mathcal{X}|\gamma_t^2)\right)\) for the preparation of the exploration distribution. Since \(\alpha = \Theta(\sqrt{\gamma_T/T})\), we have \(T\alpha = \Theta(\sqrt{T \gamma_T})\); thus, under \(|\mathcal{X}| \gg T\), we have¹² \[\widetilde{O}\left(\sum_{t=1}^{\lceil T\alpha \rceil} (t\gamma_t^2 + \gamma_t^3 + |\mathcal{X}|\gamma_t^2)\right) \leq \widetilde{O}\left(|\mathcal{X}|\sqrt{T\gamma_T} \gamma_{\lceil \sqrt{T\gamma_T} \rceil}^2\right) = o(|\mathcal{X}| (T\gamma_T)^{3/2}).\] Thus, we can confirm that the computational cost \(\widetilde{O}\left(\sum_{t=1}^{\lceil T\alpha \rceil} (t\gamma_t^2 + \gamma_t^3 + |\mathcal{X}|\gamma_t^2)\right)\) is strictly better than the \(O(|\mathcal{X}|(T \gamma_T)^{3/2})\)-computational cost in the original RLS-kernelized Exp3.

14.0.0.2 Summary of the proof.

The core lemma for the proof of Theorem 5 is Lemma 14, which guarantees that the posterior variance under the approximated MVR sequence diminishes at the same rate as that under the exact MVR sequence. See Lemma 14 and its proof for details. If we once obtain Lemma 14, Theorem 5 follows by applying the same proof as that of Theorem 3 with slight modifications. Thus, we omit the proof of Theorem 5, while we summarize the required modifications below:

• In addition to events \((A_t)\) in Eq. 30 , we consider additional event \(A_0\) such that the three events in Corollary 3 with \(\widetilde{\mathbf{S}} = \widetilde{\mathbf{S}}_{t}\), \(\mathbf{\Psi}= \mathbf{\Psi}_{t-1}^{(\mathrm{MVR})}\), and \(\widetilde{s} = \widetilde{s}_t\) hold for all round \(t \in [\lceil T\alpha\rceil]\) in the approximated MVR procedures (Line 1 in Alg. 6). Then, we also define the modified event \(\bar{A} \mathrel{\vcenter{:}}= \cap_{t \in [T]\cup \{0\}} A_t\) as the replacement of event \(A\) in the original proof. Then, note that \(\mathbb{P}(A_0) \geq 1 - 1/(2T^2)\) and \(\mathbb{P}(\cap_{t \in [T]}) \geq 1 - 1/(2T^2)\) hold due to Lemma 8, Corollary 3, and the settings of the confidence level parameters (Lines 1 and 7 in Alg. 6). Thus, the union bound implies \(\mathbb{P}(\bar{A}^c) \leq 1/T^2\), which matches the upper bound \(\mathbb{P}(A^c)\) used in the proof of the original RLS-kernelized Exp3.

• The proof for the upper bounds for terms (i) and (iii) in Eq. 32 remains unchanged from the original proof except for the replacement of the constant factor arising from the difference in \(\mathbb{P}(A_t^c)\). (In the original proof, we have \(\mathbb{P}(A_t^c) \leq 1/T^3\), while \(\mathbb{P}(A_t^c) \leq 1/(2T^3)\) under Alg. 6.)

• Regarding the upper bounds for term (ii) in Eq. 32 , we can leverage Lemma 15 under event \(\bar{A}\) instead of using Lemma 9 under event \(A\). Note that event: \(\left\{\max_{\boldsymbol{x}\in \mathcal{X}} \sigma^2\left(\boldsymbol{x}; \widetilde{\mathbf{X}}_{\lceil T\alpha \rceil}^{(\text{MVR})}, \lambda\right) \leq \frac{36 \lambda \gamma_{\lceil T\alpha \rceil}}{\lceil T\alpha \rceil}\right\}\), which is required for the application of Lemma 15, is true under event \(A_0\). Then, from Lemma 15, for guaranteeing \(\eta \widetilde{u}_t(\boldsymbol{x}) \leq 1\), we must set \(\alpha\) such that \(\frac{\eta}{\alpha} \left(36\sqrt{6} B \gamma_{T} + \beta \sqrt{108\gamma_T}\right) \leq 1\) holds. The setting of \(\alpha\) in Theorem 5 satisfies this condition; thus, we can apply the standard Exp3 analysis in Lemma 5 under event \(A\). After that, we can directly follow the original proof of the upper bound for term (ii). By aggregating the upper bounds for terms (i), (ii), and (iii), we can obtain the desired regret guarantees.

• Finally, we prove the statements regarding the computational costs. As with the original RLS-kernelized Exp3, the upper bound for the per-round computational cost (the first statement in Theorem 5) directly follows from Lemma 8. Regarding the computational cost for the preparation of the exploration distribution, under event \(A_0\), we can conclude the following two facts: (i) the computational cost of recursive RLS-Nyström is \(\widetilde{O}(t\gamma_t^2)\), and (ii) the dimension of the Nyström embedding \(\widetilde{s}_t\) is \(\widetilde{O}(\gamma_t)\), which implies the computation of Eq. [eq:nystrom95approx95mvr95expression] for all \(\boldsymbol{x}\in \mathcal{X}\) is \(\widetilde{O}(|\mathcal{X}| \gamma_t^2 + \gamma_t^3)\). Thus, the computational cost for approximated MVR procedures at round \(t\) is \(\widetilde{O}(t\gamma_t^2 + |\mathcal{X}| \gamma_t^2 + \gamma_t^3)\), which implies the desired statement.

15 Helper lemmas↩︎

15.1 Basic properties of feature map, RKHS, and GP↩︎

15.1.0.1 Overview.

The lemmas in this subsection are well-known, useful properties for handling the feature representation of the kernel [13], [15], while we provide the proof for completeness.

15.2 Helper lemmas for Kernelized Exp3↩︎

15.2.0.1 Overview.

The lemmas in this subsection are leveraged in the proof of kernelized Exp3 in Appendix 11. Lemma 5 is the adaptation of the standard Exp3 algorithm. For completeness, we provide the full proof. Lemma 6 is the upper bound for the optimistic estimator, which is used to guarantee the required condition to apply Lemma 5. In the proof of Lemma 6, we leverage the known property of posterior variance regarding the MVR sequence, which can be found in the existing stochastic KB literature [11], [46], [48].

15.3 Helper lemmas for RLS-Kernelized Exp3↩︎

15.3.0.1 Overview.

The lemmas in this subsection are leveraged in the proof of RLS-kernelized Exp3 in Appendix 12. Lemma 7 provides the identities of the approximated estimators and alternative representations based on Nyström embedding. We would like to note that, in a multi-task setting under an infinite-dimensional feature map, Lemma 8 in [15] already provides a similar result to that in Lemma 7. Lemma 8 provides the theoretical property of the computational cost and accuracy of the recursive RLS-Nyström subroutine. The proof of Lemma 8 is obtained by combining the existing effective dimension-based result by [7] with Lemma 1. Lemma 9 provides the upper bound of approximated optimistic estimator \(\widetilde{u}_t\), which serves as the counterpart of Lemma 6 for the proof of the original kernelized Exp3 algorithm. Lemmas 10 and 11 provide the spectral results. Roughly speaking, under the sufficient accuracy of the sampling matrix \(\mathbf{S}_t\), these results are useful for connecting the approximated quantities in RLS-kernelized Exp3 with non-approximated quantities in the proof. The proofs of Lemmas 10 and 11 are almost directly obtained by adapting the proof of [59] and [49], which study the kernel approximation for k-means clustering and the computationally efficient KB algorithm, respectively. Finally, Lemma 12 is used to obtain the upper bound on the regret arising from the unfavorable rare event, where the accuracy of recursive RLS-Nyström is not sufficient. The proof of Lemma 12 is obtained with elementary matrix calculations.

15.4 Helper lemmas for RLS-Kernelized Exp3 with approximated MVR sequence↩︎

15.4.0.1 Overview.

The lemmas in this subsection are leveraged in the proof of a variant of RLS-kernelized Exp3 using the approximated MVR sequence in Appendix 14. Corollary 3 and Lemma 13 provide the approximation properties related to the standard kernel functions. We omit the proof of Corollary 3 since it directly follows by noting the fact that the effective dimension of the kernel is upper bounded by MIG (see, e.g., [49]). Furthermore, Lemma 13 also directly follows by adapting the proof of Lemma 10 for the standard kernel instead of the weighted kernel; thus, we omit the proof of Lemma 13. Lemma 14 shows that the maximum of the posterior variance is also upper-bounded by MIG even under the approximated MVR sequence. This lemma serves as a replacement for the upper bound on the posterior variance in the exact MVR sequence in the proof. Finally, based on the result of Lemma 13, we can prove Lemma 15, which serves as a replacement for Lemma 9 in the proof of original RLS-kernelized Exp3.

15.5 Helper lemma for lower bounds↩︎

The above lemma is obtained with a subtle modification of the proof of Theorem 2 in [50]. Thus, we omit the full proof while providing a description of the required modification. The only part that we require modification in the proof of Theorem 2 in [50] is the upper bound of Kullback–Leibler (KL) divergence in the change of measure argument. In this section, hereafter, we use the same notations as those in [50]. When we apply the proof of [50], the maximum KL divergence term: \(\bar{D}_{f, f'}^{j}\) under the two functions \(f, f'\) and some partition \(\mathcal{R}_j \subset \mathcal{X}\) indexed with \(j\) becomes different from the original proof. Since they study the Gaussian noise model whose variance \(\sigma^2\) is homogeneous over the input domain, the term \(\bar{D}_{f, f'}^{j}\) is given as \[\bar{D}_{f, f'}^{j} = \max_{\boldsymbol{x}\in \mathcal{R}_j} \frac{(f(\boldsymbol{x}) - f(\boldsymbol{x}'))^2}{2\sigma^2}.\] See Lemma 1 and Eqs. (9) and (19) in [50]. On the other hand, the term \(\bar{D}_{f, f'}^{j}\) in our model becomes the following form due to the input dependence of the noise term \(\widetilde{\eta}_t k(\boldsymbol{0}, \cdot)\): \[\bar{D}_{f, f'}^{j} = \max_{\boldsymbol{x}\in \mathcal{R}_j} \frac{(f(\boldsymbol{x}) - f'(\boldsymbol{x}))^2}{2 \sigma^2 k^2(\boldsymbol{0}, \boldsymbol{x})}.\] The upper bound of the above term \(\bar{D}_{f, f'}^{j}\) can be further obtained as \[\bar{D}_{f, f'}^{j} \leq \max_{\boldsymbol{x}\in \mathcal{R}_j} \frac{(f(\boldsymbol{x}) - f'(\boldsymbol{x}))^2}{2 \sigma^2 k^2(\boldsymbol{0}, \boldsymbol{1})},\] where \(\boldsymbol{1} = (1, \ldots, 1) \in \mathbb{R}^{d}\). By using the above upper bound instead of the exact value of the KL divergence \(\frac{(f(\boldsymbol{x}) - f'(\boldsymbol{x}))^2}{2\sigma^2}\), we can obtain the desired lower bound by directly following the proof of [50]. Specifically, the resulting lower bound matches the lower bound in [50] with the smaller noise variance \(\sigma^2 k^2(\boldsymbol{0}, \boldsymbol{1})\). Note that \(k^2(\boldsymbol{0}, \boldsymbol{1})\) depends on only \(d\) and \(\ell\), which are \(\Theta(1)\); thus, we can recover the stochastic KB lower bound up to \((d, \ell)\)-dependent constant factors.

16 Additional discussion about exploration distribution↩︎

Our algorithm uses the empirical distribution of the MVR sequence as the exploration distribution \(\pi\). In this section, we discuss the other possible choices of \(\pi\).

16.0.0.1 Exploration distribution based on generalized G-optimal design.

The role of exploration distribution in our proof is to obtain Lemmas 6 and 9, which are required for applying Exp3 analysis by guaranteeing \(\forall \boldsymbol{x}\in \mathcal{X}, \eta u_t(\boldsymbol{x}) \leq 1\) and \(\forall \boldsymbol{x}\in \mathcal{X}, \eta \widetilde{u}_t(\boldsymbol{x}) \leq 1\) (see Lemma 5). Although we used the MVR-based empirical distribution to obtain Lemmas 6 and 9, this is not the only choice. The requirement of \(\pi(\cdot)\) for extending our proof of Lemmas 6 and 9 is that the upper bound of the following supremum of the quadratic form increases with \(O(\gamma_{\lceil T \alpha\rceil})\): \[\label{eq:necessary95cond95for95pi} \sup_{\boldsymbol{x}\in \mathcal{X}} \psi(\boldsymbol{x}) \left(\sum_{\boldsymbol{x}' \in \mathcal{X}} \pi(\boldsymbol{x}') \psi(\boldsymbol{x}') \psi(\boldsymbol{x}')^{\top} + \frac{\lambda}{T\alpha} \boldsymbol{I}_{|\mathcal{X}|}\right)^{-1} \psi(\boldsymbol{x}) = O(\gamma_{\lceil T \alpha \rceil}).\tag{102}\] See Eqs. 63 –68 in the proof of Lemma 6. From the above fact, the natural choice is to choose the following distribution \(\pi^{\ast}\) by minimizing the left-hand side of the above expression: \[\pi^{\ast} \in \operatornamewithlimits{argmin}_{P \in \mathcal{P}_{\mathcal{X}}}\sup_{\boldsymbol{x}\in \mathcal{X}} \psi(\boldsymbol{x}) \left(\sum_{\boldsymbol{x}' \in \mathcal{X}} P(\boldsymbol{x}') \psi(\boldsymbol{x}') \psi(\boldsymbol{x}')^{\top} + \frac{\lambda}{T\alpha} \boldsymbol{I}_{|\mathcal{X}|}\right)^{-1} \psi(\boldsymbol{x}),\] where \(\mathcal{P}_{\mathcal{X}} \mathrel{\vcenter{:}}= \{P: \mathcal{X}\rightarrow [0, 1] \mid \sum_{\boldsymbol{x}\in \mathcal{X}} P(\boldsymbol{x}) = 1\}\) denotes the set of the all probability mass function on \(\mathcal{X}\). This \(\pi^{\ast}\) is the generalization of G-optimal design [44] and is used in stochastic KB literature [10]. Even if we replace \(\pi\) with \(\pi^{\ast}\) in Algs. 1 and 5, we can obtain the same regret guarantees as those in Theorems 1 and 3, and Corollary 1. Then, the resulting algorithm with \(\pi^{\ast}\) can be interpreted as the kernelized extension of Exp3 with Kiefer-Wolfowitz exploration in adversarial LB (Alg. 3 in [45]). The drawback of this approach is the computational cost of \(\pi^{\ast}\). To our knowledge, even in the calculation of the near-optimal approximation of \(\pi^{\ast}\), the total computational cost is \(\Omega(|\mathcal{X}|^3)\). For example, the well-known iterative method based on the Frank-Wolfe algorithm [44] requires \(O(|\mathcal{X}| \log \log |\mathcal{X}|)\) iterations with \(O(|\mathcal{X}|^3)\) per-iteration complexity¹³. For typical KB problem setting with \(|\mathcal{X}| \gg T\), the calculation cost of \(\pi^{\ast}\) is strictly worse than \(O(|\mathcal{X}|(T\gamma_T)^{3/2})\) computational cost of MVR-based exploration distribution \(\pi\).

16.0.0.2 Uniform distribution.

Another possible choice is the uniform distribution \(\pi_{\mathrm{unif}}(\cdot) \mathrel{\vcenter{:}}= 1/|\mathcal{X}|\). If we can use \(\pi_{\mathrm{unif}}\), the computational cost for exploration distribution prior to the algorithm run is completely omitted. In this case, by applying Lemma 1 to the quadratic term in Eq. 102 , we observe that \[\sup_{\boldsymbol{x}\in \mathcal{X}} \psi(\boldsymbol{x}) \left(\sum_{\boldsymbol{x}' \in \mathcal{X}} \pi_{\mathrm{unif}}(\boldsymbol{x}') \psi(\boldsymbol{x}') \psi(\boldsymbol{x}')^{\top} + \frac{\lambda}{T\alpha} \boldsymbol{I}_{|\mathcal{X}|}\right)^{-1} \psi(\boldsymbol{x}) \leq \frac{\lceil T\alpha \rceil}{\lambda} \sup_{\boldsymbol{x}\in \mathcal{X}} \mathbb{E}_{\mathbf{X}_{\text{unif}}}[\sigma^2(\boldsymbol{x}; \mathbf{X}_{\text{unif}}, \lambda)],\] where \(\mathbf{X}_{\text{unif}} \mathrel{\vcenter{:}}= (\boldsymbol{x}_{\text{unif}}^{(1)}, \ldots, \boldsymbol{x}_{\text{unif}}^{(\lceil T \alpha \rceil)})\) with \(\boldsymbol{x}_{\text{unif}}^{(1)}, \ldots, \boldsymbol{x}_{\text{unif}}^{(\lceil T \alpha \rceil)} \sim_{\mathrm{i.i.d.}} \pi_{\mathrm{unif}}\). Thus, if \(\sup_{\boldsymbol{x}\in \mathcal{X}} \mathbb{E}_{\mathbf{X}_{\text{unif}}}[\sigma^2(\boldsymbol{x}; \mathbf{X}_{\text{unif}}, \lambda)] = O\left(\frac{\lambda \gamma_{\lceil T\alpha \rceil}}{\lceil T\alpha \rceil}\right)\), we can verify the condition 102 . The examination for the upper bound \(\sup_{\boldsymbol{x}\in \mathcal{X}} \mathbb{E}_{\mathbf{X}_{\text{unif}}}[\sigma^2(\boldsymbol{x}; \mathbf{X}_{\text{unif}}, \lambda)] = O\left(\frac{\lambda \gamma_{\lceil T\alpha \rceil}}{\lceil T\alpha \rceil}\right)\) is found in the stochastic KB literature [69]. [69] show that \(\sup_{\boldsymbol{x}\in \mathcal{X}} \sigma^2(\boldsymbol{x}; \mathbf{X}_{\text{unif}}, \lambda) = O\left(\frac{\lambda \gamma_{\lceil T\alpha \rceil}}{\lceil T\alpha \rceil}\right)\) asymptotically holds with high probability under the uniform boundedness assumption of the eigenfunction of the kernel with respect to \(\pi_{\mathrm{unif}}\). However, to our knowledge, the validity of the uniform boundedness assumption for commonly-used kernels in KB (such as SE or \(\nu\)-Matérn kernels) is unclear¹⁴. For example, see discussion in Chap. 4.4 in [70]. Thus, we believe that further careful theoretical examination is desired for the utilization of \(\pi_{\text{unif}}\).

17 Simulation experiments↩︎

We conduct simulation experiments to confirm the empirical behavior of our algorithms.

17.0.0.1 Input domain, kernel, and strategy of the environment.

We conduct the following \(4\) settings of input domain \(\mathcal{X}\):

• Setting 1. We set \(\mathcal{X}\) as \(400\) uniformly spaced grid points of \([0, 1]\).

• Setting 2. We set \(\mathcal{X}\) as \(20 \times 20\) uniformly spaced grid points of \([0, 1]^2\).

• Setting 3. We set \(\mathcal{X}\) as \(10000\) uniformly spaced grid points of \([0, 1]\).

• Setting 4. We set \(\mathcal{X}\) as \(100 \times 100\) uniformly spaced grid points of \([0, 1]^2\).

For each setting of input domain, we conduct experiments with three kernel functions: (i)SE kernel, (ii) \(\nu\)-Matérn kernel with \(\nu = 5/2\), and (iii) \(\nu\)-Matérn kernel with \(\nu = 3/2\). For each kernel, we set the lengthscale parameter \(\ell\) as \(\ell = 0.3\sqrt{d}\). To define \(f_t\) in the experiment, we consider the fully-adversarial environment. Specifically, with some pre-defined candidate set \(\mathcal{F}\subset \mathcal{F}_k(B)\) and the learner’s sampling distribution \(P_t\), we assume that the environment chooses \(f_t\) so that the learner’s conditional expected instantaneous regret becomes highest, as follows: \(f_t \in \max_{f \in \mathcal{F}} (\max_{\boldsymbol{x}\in \mathcal{X}} f(\boldsymbol{x}) - \sum_{\boldsymbol{x}' \in \mathcal{X}} P_t(\boldsymbol{x}') f(\boldsymbol{x}'))\). We define the candidate set \(\mathcal{F}\) as \(\mathcal{F}= (f^{(i)})_{i \in [1000]}\) with \(f^{(i)}(\cdot) = \min\{1, B/\|\widetilde{f}^{(i)}\|_k\} \widetilde{f}^{(i)}(\cdot)\) and \(\widetilde{f}^{(i)}(\cdot) = \sum_{m=1}^{100} c^{(m, i)} k(\boldsymbol{x}^{(m, i)}, \cdot)\), where \(\boldsymbol{x}^{(m, i)} \sim \mathrm{Uniform}(\mathcal{X})\) and \(c^{(m, i)} \sim \mathrm{Uniform}(-1, 1)\) are independent random variables. Note that we can calculate \(\|\widetilde{f}^{(i)}\|_k\) as \(\|\widetilde{f}^{(i)}\|_k = \sqrt{\sum_{m, m'}c^{(m,i)}c^{(m',i)}k(\boldsymbol{x}^{(m,i)}, \boldsymbol{x}^{(m',i)}) }\) under the definition of \(\widetilde{f}^{(i)}\). Regarding the RKHS norm upper bound \(B\), we set \(B = 2\).

17.0.0.2 Algorithms.

We compare the following algorithms:

• Random. At each round \(t\), this algorithm draws \(\boldsymbol{x}_t\) uniformly at random from \(\mathcal{X}\).

• APG-Exp3. This is the linear approximated version of Exp3 algorithm proposed in [6]. We use the G-optimal design \(\widetilde{\pi}^{\ast} \mathrel{\vcenter{:}}= \min_{P \in \mathcal{P}_{\mathcal{X}}} \max_{\boldsymbol{x}\in \mathcal{X}}\|\boldsymbol{N}(\boldsymbol{x})\|_{(\sum_{\boldsymbol{x}' \in \mathcal{X}}P(\boldsymbol{x}') \boldsymbol{N}(\boldsymbol{x}') \boldsymbol{N}(\boldsymbol{x}')^{\top})^{-1}}\) as the exploration distribution, where \(\boldsymbol{N}(\boldsymbol{x}) \in \mathbb{R}^{D_T}\) is the feature vector based on the Newton basis functions. To calculate \(\widetilde{\pi}^{\ast}\), we use the Frank-Wolfe algorithm [73]. The basis function \(\boldsymbol{N}(\boldsymbol{x})\) and \(D_T\) are determined in the P-greedy algorithm as described in [6]. We fix the admissible error \(\mathfrak{e}\) of the P-greedy algorithm as the theoretically suggested value \(\mathfrak{e} = (\log |\mathcal{X}|)/T\). Regarding the choice of the learning rate \(\eta > 0\) and mixing ratio \(\alpha \in (0, 1)\)¹⁵, we set \(\eta = c_1 / \sqrt{D_T T}\) and \(\alpha = c_2 \eta D_T\) for some constants \(c_1 > 0\) and \(c_2 > 0\). See [6] for details. Here, these settings are based on the theoretically suggested diminishing rate of \(\eta\) and \(\alpha\) for achieving \(\widetilde{O}(\sqrt{TD_T})\) regret proved in [6]. For each kernel, we fix the constants \(c_1\) and \(c_2\) based on the average performance over \(10\) different seeds under setting 1 described above, with \(T = 50\). Specifically, for each kernel, we choose the constants \(c_1\) and \(c_2\) by grid search across \(c_1, c_2 \in \{0.1, 0.5, 1.0, 5.0, 10.0\}\). The selected settings of \(c_1, c_2\) are \((c_1, c_2) = (0.5, 0.1)\), \((c_1, c_2) = (0.5, 0.1)\), and \((c_1, c_2) = (0.5, 0.1)\) for the SE, \(5/2\)-Matérn, and \(3/2\)-Matérn kernels, respectively.

• Kernelized Exp3. This is the kernelized Exp3 algorithm proposed in Sec. 3. Regarding the choice of the parameters, based on the theoretically suggested values in Theorem 1, we set \(\eta = c_3 / \sqrt{T \bar{\gamma}_T}\) and \(\alpha = c_4 \eta \bar{\gamma}_T\) with some constants \(c_3 > 0\) and \(c_4 > 0\). Here, \(\bar{\gamma}_T\) denotes a known growth rate upper bound on MIG, which is defined as \(\bar{\gamma}_T = (\log T)^{d+1}(\log \log T)^{-d}\) and \(\bar{\gamma}_T = T^{\frac{d}{2\nu+d}} (\log T)^{\frac{4\nu+d}{2\nu+d}}\) for \(k = k_{\mathrm{SE}}\) and \(k = k_{\mathrm{Mat}}\), respectively [22], [55]. For each kernel, to choose constants \(c_3\), \(c_4\), and the regularization parameter \(\lambda \geq 1\), we conduct the grid search across \(c_3, c_4 \in \{0.1, 0.5, 1.0, 5.0, 10.0\}\) and \(\lambda \in \{1.0, 5.0, 10.0\}\) as with the parameter selections of APG-Exp3. Here, we set the confidence width parameter \(\beta\) as the theoretically suggested value \(\beta \mathrel{\vcenter{:}}= B\sqrt{\lambda/T}\) in Theorem 1. Here, we omit the full experiments on kernelized Exp3 for the large-scale input domain setting (settings 3 and 4) due to its high computational cost; however, as a baseline for the computational time, we report the estimated per-round computational time for kernelized Exp3 by running the algorithm for only 1 round. The selected settings of \(c_3, c_4, \lambda\) are \((c_3, c_4, \lambda) = (5.0, 0.1, 1.0)\), \((c_3, c_4, \lambda) = (10.0, 0.1, 10.0)\), and \((c_3, c_4, \lambda) = (5.0, 0.1, 5.0)\) for the SE, \(5/2\)-Matérn, and \(3/2\)-Matérn kernels, respectively.

• RLS-Kernelized Exp3. This is the RLS-based kernelized Exp3 algorithm proposed in Sec. 3. Regarding the choice of \(\eta\), \(\alpha\), and \(\gamma\), we use the same settings as used in kernelized Exp3. We set the confidence width parameter \(\beta\) as \(\beta = B (1 + \sqrt{2})\sqrt{\lambda/T}\) as suggested in Theorem 3. Furthermore, we fix \(\delta = 0.1\).

17.0.0.3 Resource for computation.

Our experiments are conducted by AMD EPYC 7702P 64-core processor with 16 GB RAM.

17.0.0.4 Results.

We report the average regret and per-round computational time over \(10\) trials with different seeds. Tab. 3 shows the results. Firstly, we confirm that the regret of our proposed algorithms is substantially lower than that of other baseline methods. Secondly, we confirm that the computational time of our algorithms is worse than that of the baseline algorithms. However, in the large input domain \(|\mathcal{X}| = 10000\) (settings 3 and 4), the per-round cost of RLS-kernelized Exp3 is improved compared with the estimated per-round cost of the original kernelized Exp3.

In our experiments, we confirm that the computational time of RLS-kernelized Exp3 for SE kernel is worse than that of \(5/2\)-Matérn and \(3/2\)-Matérn. This phenomenon appears to contradict our theoretical guarantees, where the kernel with the small information gain leads to small computational cost of RLS-kernelized Exp3. However, as described in the algorithm setting, the regularization parameter \(\lambda = 1.0\) chosen by the grid search for SE-kernel are smaller than \(\lambda=10.0\) and \(\lambda=5.0\) for \(5/2\)-Matérn and \(3/2\)-Matérn kernels. Therefore, the computational time for SE kernel in our experiments exhibits larger computational time than those for \(5/2\)-Matérn and \(3/2\)-Matérn kernels, since the small regularization parameter \(\lambda\) leads to the large information gain \(\gamma_T\). We also found the computational cost of RLS-kernelized Exp3 exceeds that of APG-Exp3. We observe that the reason for this phenomenon is the large constant factor for \(\widetilde{O}(|\mathcal{X}|\gamma_T^2)\)-computation of the recursive Nyström algorithm provided in Lemma 8.

References↩︎

---

1. The notations \(\widetilde{O}(\cdot)\) and \(\widetilde{\Omega}(\cdot)\) ignore the polylogarithmic factors. A comprehensive notation table is in Appendix 8.↩︎

2. As described in Sec. 3, our analysis is applicable to any compact input domain via the discretization.↩︎

3. The concurrent work by [41] explicitly discuss this point. See Appendix B in [41] for details.↩︎

4. The condition \(|\mathcal{X}| = o(\exp(T \gamma_T^{-1}))\) is required to guarantee \(\eta < \overline{\eta}\), where \(\overline{\eta}\) is defined in Theorem 1. Note that, if \(|\mathcal{X}| = \Omega(\exp(T \gamma_T^{-1}))\), the upper bound \(O(\sqrt{T \gamma_T \log |\mathcal{X}|})\) becomes meaningless since \(\sqrt{T \gamma_T \log |\mathcal{X}|} = \Omega(T)\).↩︎

5. For an exponentially large finite input domain \(|\mathcal{X}| = \Omega(\exp(T))\), we can also obtain a tighter regret than that in Corollary 1 by the discretization argument.↩︎

6. This constant \(C > 0\) may depend on \(d\), \(\ell\), and \(\nu\).↩︎

7. \(\epsilon\)-net \(\widetilde{\mathcal{X}}\) of \(\mathcal{X}\) with respect to the norm \(\|\cdot\|_{2}\) is a subset of \(\mathcal{X}\) such that \(\forall \boldsymbol{x}\in \mathcal{X},~\exists \boldsymbol{z}\in \widetilde{\mathcal{X}}, \|\boldsymbol{x}- \boldsymbol{z}\|_{2} \leq \epsilon\) holds.↩︎

8. Note that the difference \(G_t(\lambda) - G_{t-1}(\lambda)\) is generally full-rank since \(P_{t}(\boldsymbol{x})\) is updated from \(P_{t-1}(\boldsymbol{x})\) for all \(\boldsymbol{x}\in \mathcal{X}\); thus, we cannot update \(G_t(\lambda)^{-1}\) efficiently by relying on standard low-rank update procedures.↩︎

9. For readers unfamiliar with the Nystöm approximation of kernels, we refer to the related KB or kernel approximation literature [7], [15], [49], [59], [60].↩︎

10. Note that Eq. 2 requires the condition \(\forall \boldsymbol{x}\in \mathcal{X}\), \(k(\boldsymbol{x}, \boldsymbol{x}) \leq 1\). See Lemma 5.4 in [8].↩︎

11. Note that \(\gamma_T = O(T)\) always holds.↩︎

12. Here, we implicitly assume \(\gamma_t = o(t)\). The condition \(\gamma_t = o(t)\) generally holds except for some pathological example of the kernel \(k\), e.g., \(k(\boldsymbol{x}, \boldsymbol{x}') \mathrel{\vcenter{:}}= 1l\{\boldsymbol{x}= \boldsymbol{x}'\}\).↩︎

13. Specifically, even if we rely on the one-rank update formula of the matrix inverse, the calculation of the maximum of the quadratic term per-iteration requires \(O(|\mathcal{X}|^2)\)-calculation of the quadratic term for all input \(\boldsymbol{x}\in \mathcal{X}\), which leads to \(O(|\mathcal{X}|^3)\) per-iteration complexity.↩︎

14. To our knowledge, the examples of the kernels for which the uniform boundedness assumption is rigorously verified are \(1/2\)-Matérn kernel with \(d = 1\) (discussed in [70]) and Hilbert-space approximation of SE and \(\nu\)-Matérn kernels [71], [72].↩︎

15. The parameter \(\alpha\) is defined as notation \(\gamma\) in [6].↩︎