Combinatorial Bandit Bayesian Optimization for Tensor Outputs Jingru Huang, Haijie Xu, Jie Guo, Manrui Jiang, Chen Zhang Abstract Bayesian optimization (BO) has been widely used to optimize expensive and black-box functions across various domains. However, existing BO methods have not addressed tensor-output functions. To fill this gap, we propose a novel tensor-output BO framework. Specifically, we first introduce a tensor-output Gaussian process (TOGP) with two classes of tensor-output kernels as a surrogate model of the tensor-output function, which can effectively capture the structural dependencies within the tensor. Based on it, we develop an upper confidence bound (UCB) acquisition function to select query points. Furthermore, we introduce a more practical and challenging problem setting, termed combinatorial bandit Bayesian optimization (CBBO), where only a subset of the tensor outputs can be selected to contribute to the objective. To tackle this, we propose a tensor-output CBBO method, which extends TOGP to handle partially observed tensor outputs, and accordingly design a novel combinatorial multi-arm bandit-UCB2 (CMAB-UCB2) criterion to sequentially select both the query points and the output subset. We establish theoretical regret bounds for both methods, guaranteeing sublinear regret. Extensive experiments on synthetic and real-world datasets demonstrate the superiority of our methods. 1 Introduction Bayesian optimization (BO) is a widely used strategy for optimizing expensive, black-box objective functions ( 18 ; 44 ) . Its effectiveness has led to successful applications in various domains such as hyperparameter tuning, experimental design, and robotics ( 37 ; 35 ; 45 ) . Most existing BO methods focus on scalar outputs ( 8 ; 47 ) , while recent studies have extended BO to handle multi-output settings ( 11 ; 41 ; 28 ; 38 ) . However, to the best of our knowledge, no prior work has addressed BO with tensor-valued outputs, where the system response is a multi-mode tensor. In contrast, tensor-valued data have been extensively explored in other areas, including tensor decomposition ( 1 ) , tensor regression ( 27 ) , and tensor completion ( 39 ) , among others. In current multi-output BO (MOBO) methods, a surrogate model, typically a multi-output Gaussian process (GP) or a collection of independent scalar-output GPs, is constructed from observed data, and an acquisition function is then optimized to sequentially select query points by balancing exploration and exploitation. A straightforward way to handle tensor-valued outputs is to vectorize the tensor and apply existing MOBO methods. However, vectorization ignores the intrinsic structural correlations of tensor data, especially mode-wise dependencies that are critical in many applications. As a result, MOBO methods may become less effective when optimizing the acquisition function to identify the global optimum. As such, it is important to develop GP surrogates that model tensor structure directly. Existing tensor-output GP models typically adopt fully separable covariance structures, in which the joint covariance factorizes as a Kronecker product of covariance matrices across the input and each output mode ( 25 ; 51 ; 5 ) . While computationally attractive, separability implies that correlations across tensor modes do not vary with the input, an assumption that is often violated in complex systems such as spatiotemporal processes ( 23 ) . This mismatch can lead to poor predictive accuracy, numerical instability in posterior inference, and ultimately degraded BO performance. Therefore, in this paper, we first aim to construct a more flexible and scalable GP model that can capture input-dependent correlations within tensor outputs. Then, we aim to design an acquisition function and a sequential querying policy tailored for tensor-output BO. Furthermore, we consider a more complex and practical setting in which only a subset of tensor entries contributes to the objective. This naturally transforms the problem into a combinatorial multi-armed bandit (CMAB) setting. Specifically, each tensor element is treated as an base arm, and at each round, select a subset of arms, referred to as a super-arm. The objective value associated with the chosen super-arm is then observed, which we interpret as the reward. We term this novel problem as combinatorial bandit Bayesian optimization (CBBO). The goal of tensor-output CBBO is to jointly identify an optimal input in the search space and the corresponding best super-arm over tensor outputs. Recent work has combined BO with multi-armed bandits (MAB), often termed bandit Bayesian optimization (BBO), to handle mixed input spaces with both continuous and categorical variables ( 29 ; 32 ; 24 ) . In these settings, categorical variables can be viewed as indexing discrete modes, and choosing one category per variable amounts to selecting a single arm along each mode, which is a special case of CBBO. However, existing BBO methods do not be directly extend to our CBBO setting for two reasons. First, they typically model the effects of categorical choices using independent GPs, and thus cannot capture the rich structural correlations inherent in tensor outputs. Second, their selection strategies effectively decompose the decision into multiple independent bandit problems (one per categorical variable), whereas CBBO requires joint selection of multiple, potentially correlated arms within a super-arm. Thus, these methods are not well suited for our tensor-output CBBO framework. To address the aforementioned challenges, we propose a tensor-output Bayesian optimization framework, termed TOBO, together with its extension to the CBBO setting, termed TOCBBO. Our main contributions are summarized as follows: • We propose a tensor-output Gaussian process (TOGP) with two classes of tensor-output kernels. The proposed kernels explicitly incorporate tensor structure by extending the linear model of coregionalization from vector-valued to tensor-valued outputs, thereby capturing dependencies both across tensor modes and over the input domain. • Using the TOGP model as the surrogate, we develop a TOBO framework based on the upper confidence bound (UCB) acquisition. We establish a sublinear regret bound for TOBO, which provides the first Bayesian regret analysis tailored to tensor-valued outputs. • We formulate a novel problem setting, referred to as CBBO. To address this problem, we design the TOCBBO framework by introducing a CMAB-UCB2 acquisition function, which couples UCB-based input selection with CMAB-UCB-based super-arm selection. We further establish a sublinear regret bound for TOCBBO. • We demonstrate the efficiency of our methods on synthetic experiments and case studies. Notably, compared with existing TOGP methods ( 5 ; 25 ; 51 ) , our model provides a more general kernel-construction framework. Specifically, existing tensor-output kernels can be interpreted as special cases induced by particular low-rank tensor decompositions, whereas our LMC-based formulation allows a broad class of tensor constraints to be encoded through the coregionalization structure. Compared with standard BO methods ( 40 ; 4 ; 11 ) , our work is the first to establish a BO framework for tensor outputs and further extend it to the proposed CBBO setting. Moreover, our contributions lie in deriving regret bounds for both TOBO and TOCBBO based on concentration inequalities specialized to the proposed TOGP under a Bayesian framework. 2 Related works High-order Gaussian processes (HOGPs): Most existing studies for modeling HOGPs adopt separable kernel structures. In particular, 5 proposes a tensor-variate GP with separable covariance across tensor modes, 25 develops a scalable multi-task GP for tensor outputs by factorizing the cross-covariance kernel into mode-wise and input components, and 51 introduces a scalable high-order GP framework based on Kronecker-structured kernels. Although these formulations simplify computation, they typically imply that correlations across tensor modes do not vary with the input, which limits their ability to capture input-dependent dependencies. Recent work has also developed non-separable kernels for multi-output GPs (MOGPs), including convolution-based kernels ( 19 ) , linear model of coregionalization (LMC) kernels ( 26 ; 7 ) , and linear damped harmonic oscillator-based kernels ( 23 ) . A closely related viewpoint is multi-task GPs, where each task corresponds to one output component ( 48 ; 11 ; 28 ) . However, these methods are primarily designed for vector-valued outputs and therefore cannot fully exploit the intrinsic multi-mode structure of tensor data, see Section 1 . Multi-output Bayesian optimization (MOBO): MOBO typically refers to either multi-task BO or multi-objective BO ( 18 ; 44 ) . A desirable property of BO algorithms is no-regret, namely achieving cumulative regret R(T)=o(T) after T rounds ( 40 ; 11 ) . Recent work has developed various MOBO methods with theoretically grounded acquisition functions. For multi-task BO, 11 ; 13 ; 34 employ UCB-type acquisition rules and establish \mathcal{O}(\sqrt{T}) regret. For multi-objective BO, 4 ; 50 study max-value entropy search and obtain \mathcal{O}(\sqrt{T}) regret, while 15 proposes a trust-region-based criterion with \mathcal{O}(\sqrt{T\log T}) regret. In parallel, a large body of MOBO methods emphasizes empirical performance without regret guarantees, including improvement-based criteria ( 42 ; 14 ; 16 ) , entropy-based search ( 22 ; 21 ; 41 ) , and information-gain-based methods ( 11 ) . Although effective for multi-output problems, these methods typically do not exploit the intrinsic multi-mode correlations of tensor outputs and are therefore less suitable for our TOBO setting. Moreover, hypervolume-based and entropy-search-based multi-objective BO methods become computationally prohibitive as the number of objectives grows, which makes them impractical for tensor-output optimization. Bandit Bayesian optimization (BBO): BBO combines BO with multi-armed bandit (MAB) algorithms to tackle optimization in mixed input spaces containing both continuous and categorical variables. 29 ; 24 study a setting with one continuous and one categorical variable, coupling BO with Thompson sampling for the categorical choice and establishing \mathcal{O}(\sqrt{T^{\alpha+1}}\log T) regret. 32 extends this idea to multiple categorical variables, named CoCaBO, by employing EXP3 ( 3 ) to select categories and achieving \mathcal{O}(\sqrt{T}\log T) regret. Such settings can be viewed as special cases of CBBO, yet they do not directly extend to our problem due to the tensor-output structure and the need to jointly select multiple correlated arms. Table 1 summarizes a comprehensive comparison between our method and existing literature. Table 1: Comparison of related works and our proposed method GP Type Literature Tensor structure Separable (Independent modes) Non-separable (Cross-mode correlations) BO (Regret) BBO (Regret) CBBO (Regret) HOGP 5 25 51 \surd \surd \times \times \times \times MOGP 19 26 23 \times \times \surd \times \times \times MTBO 13 34 \times \surd \times \surd ( \mathcal{O}(\sqrt{T}) ) \times \times MTBO 11 \times \surd \surd \surd ( \mathcal{O}(\sqrt{T}) ) \times \times MOBO 4 50 \times \times \times \surd ( \mathcal{O}(\sqrt{T}) ) \times \times MOBO 15 \times \times \times \surd ( \mathcal{O}(\sqrt{T}\log T) ) \times \times BBO 29 24 \times \surd \times \surd ( \mathcal{O}(\sqrt{T^{\alpha+1}}\log T) ) \surd ( \mathcal{O}(\sqrt{T^{\alpha+1}}\log T) ) \times BBO 32 \times \surd \times \surd ( \mathcal{O}(\sqrt{T}\log T) ) \surd ( \mathcal{O}(\sqrt{T}\log T) ) \times TOBO+TOCBBO Our proposed method \surd \surd \surd \surd ( \mathcal{O}(\sqrt{T}\log T) ) \surd ( \mathcal{O}(\sqrt{T}\log T) ) \surd ( \mathcal{O}(\sqrt{T}\log T) ) 3 Tensor-output Bayesian optimization In this section, we propose a novel tensor-output Bayesian optimization (TOBO) framework for optimizing expensive black-box systems with tensor-valued responses. Let \mathbf{f}:\mathcal{X}\to\mathcal{Y} denote the objective function, where the input \bm{x}=(x_{1},\ldots,x_{d}) lies in a compact and convex domain \mathcal{X}\subset\mathbb{R}^{d} , and the output \mathbf{f}(\bm{x})\in\mathcal{Y}\subset\mathbb{R}^{t_{1}\times\ldots\times t_{m}} is an m -mode tensor. Denote f_{i_{1},\ldots,i_{m}}(\bm{x}) as the (i_{1},\ldots,i_{m}) -th entry of the tensor, where i_{l}=1,\ldots,t_{l} for l=1,\ldots,m , and let T=\prod_{l=1}^{m}t_{l} be the total number of elements. To optimize tensor-output systems, an intuitive way is to map the tensor-valued objective into a scalar function. To this end, we introduce a bounded linear operator L_{f}\in\mathcal{L}(\mathcal{Y},\mathbb{R}) , where \mathcal{L}(\mathcal{Y},\mathbb{R}) denotes the set of bounded linear operators from \mathcal{Y} to \mathbb{R} . The optimization problem is thus \displaystyle{\bm{x}}^{\star}=\arg\max_{\bm{x}\in\mathcal{X}}L_{f}\mathbf{f}(\bm{x}). (1) To solve this problem, the proposed TOBO aims to sequentially select inputs \bm{x}_{i} and observe the corresponding tensor outputs, \displaystyle\mathbf{y}_{i}=\mathbf{f}\left(\bm{x}_{i}\right)+\bm{\varepsilon}_{i},\qquad\forall i=1,2,\ldots (2) where \bm{\varepsilon}_{i}\in\mathbb{R}^{t_{1}\times\cdots\times t_{m}} denotes i.i.d. measurement noise with \mathrm{vec}(\bm{\varepsilon}_{i})\sim\mathcal{N}(0,\tau^{2}\mathbf{I}_{T}) , and \mathrm{vec}:\mathcal{Y}\to\mathbb{R}^{T} is the vectorization operator. Based on the collected data, we fit a tensor-output Gaussian process (TOGP) surrogate for \mathbf{f} using two classes of tensor-output kernels, as detailed in Subsection 3.1 . Then, we develop a UCB-based acquisition strategy to efficiently identify the maximizer \bm{x}^{\star} , as presented in Subsection 3.2 . 3.1 Tensor-output Gaussian process Define the prior of \mathbf{f}:\mathcal{X}\to\mathcal{Y} as a tensor-output Gaussian process (TOGP): \displaystyle\mathrm{vec}\left(\mathbf{f}(\bm{x})\right)\sim\mathcal{TOGP}\left(\bm{\mu},\sigma^{2}\mathbf{K}(\bm{x},\bm{x}^{\prime})\right),\qquad\forall\bm{x},\bm{x}^{\prime}\in\mathcal{X}, (3) where \bm{\mu}\in\mathbb{R}^{T} is the prior mean, \sigma^{2}>0 is a variance hyperparameter, and \mathbf{K}(\bm{x},\bm{x}^{\prime})\in\mathbb{R}^{T\times T} is a symmetric and positive semi-definite kernel function. The classes of \mathbf{K}(\bm{x},\bm{x}^{\prime}) are discussed later. Given n observations \mathbf{X}_{n}=(\bm{x}_{1},\ldots,\bm{x}_{n})^{\top} and \bm{Y}_{n}=\left(vec(\mathbf{y}_{1})^{\top},\ldots,vec(\mathbf{y}_{n})^{\top}\right)^{\top} , the posterior distribution of \mathrm{vec}(\mathbf{f}(\bm{x})) at a new input \bm{x}\in\mathcal{X} is Gaussian in \mathbb{R}^{T} with mean and covariance \displaystyle\hat{\bm{\mu}}_{n}(\bm{x})=\bm{\mu}+\mathbf{K}_{n}^{\top}(\bm{x})\left(\mathbf{K}_{n}+\eta\mathbf{I}_{nT}\right)^{-1}\left(\bm{Y}_{n}-\bm{1}_{n}\otimes\bm{\mu}\right), (4) \displaystyle\hat{\mathbf{K}}_{n}(\bm{x},\bm{x})=\sigma^{2}\left[\mathbf{K}(\bm{x},\bm{x})-\mathbf{K}_{n}^{\top}(\bm{x})\left(\mathbf{K}_{n}+\eta\mathbf{I}_{nT}\right)^{-1}\mathbf{K}_{n}(\bm{x})\right], (5) where \mathbf{K}_{n}(\bm{x})\in\mathbb{R}^{nT\times T} is the block column matrix whose i -th block is \mathbf{K}(\bm{x}_{i},\bm{x}) , \mathbf{K}_{n}\in\mathbb{R}^{nT\times nT} is the block matrix with (i,j) -block \mathbf{K}(\bm{x}_{i},\bm{x}_{j}) , \bm{1}_{n} is the n -vector of ones, and \eta=\tau^{2}/\sigma^{2} . To specify the tensor-output kernel in TOGP, we introduce two classes of kernels. The first class consists of non-separable tensor-output kernels constructed via a tensor extension of the linear model of coregionalization (LMC) ( 19 ; 26 ) . Let \mathrm{vec}\!\left(\mathbf{f}(\bm{x})\right)=\sum_{\ell=1}^{m}\sum_{j=1}^{r_{\ell}}\bm{a}_{\ell}\,u_{\ell j}(\bm{x}) , where \bm{a}_{\ell j}\in\mathbb{R}^{T} are loading vectors and \{u_{\ell j}\} are independent scalar GPs with zero mean and covariance functions \mathrm{Cov}(u_{\ell j}(\bm{x}),u_{\ell j}(\bm{x}^{\prime}))=k_{\ell j}(\bm{x},\bm{x}^{\prime}) . We parameterize the loading vectors by tensor cores, namely \bm{a}_{\ell j}=\mathrm{vec}(\mathbf{A}_{\ell j}) with \mathbf{A}_{\ell j}\in\mathbb{R}^{t_{1}\times\cdots\times t_{m}} . Then \mathbf{f}(\bm{x}) has zero mean and covariance \mathrm{Cov}\left(\mathrm{vec}(\mathbf{f}(\bm{x})),\mathrm{vec}(\mathbf{f}(\bm{x}^{\prime}))\right)=\sum_{\ell=1}^{m}\sum_{j=1}^{r_{\ell}}\mathrm{vec}(\mathbf{A}_{\ell})\,\mathrm{vec}(\mathbf{A}_{\ell})^{\top}\,k_{\ell j}(\bm{x},\bm{x}^{\prime}) . This yields a non-separable covariance structure since the cross-entry correlations are governed by a mixture of base kernels \{k_{\ell j}\} and therefore can vary with the input. The non-separable tensor-output kernel is defined as Definition 1 . Define the non-separable tensor-output kernel \mathbf{K}(\bm{x},\bm{x}^{\prime}) for any \bm{x},\bm{x}^{\prime}\in\mathcal{X} : \displaystyle\mathbf{K}(\bm{x},\bm{x}^{\prime})=\sum_{l=1}^{m}\sum_{j=1}^{t_{l}}\mathrm{vec}\big(\mathbf{A}_{l}\big)\mathrm{vec}\big(\mathbf{A}_{l}\big)^{\top}k_{lj}(\bm{x},\bm{x}^{\prime}), (6) where \mathbf{A}_{l}\in\mathbb{R}^{t_{1}\times\cdots\times t_{m}} are core tensors and k_{lj}(\bm{x},\bm{x}^{\prime}) are base kernels on \mathcal{X} (e.g., Matérn). Furthermore, if all w_{i_{1},\ldots,i_{m}}(\bm{z}) share the same covariance k(\bm{z},\bm{z}^{\prime}) for i_{l}\in[t_{l}],\,l=1,\ldots,m , and the convolution degenerates to g_{i_{1},\ldots,i_{m}}(\bm{z})=A_{i_{1},\ldots,i_{m}}\delta(\bm{z}-\bm{x}) , then the induced tensor-output kernel reduces to a separable structure in which the correlations across tensor modes are independent of the input. Definition 2 . For any \bm{x},\bm{x}^{\prime}\in\mathcal{X} , define the separable tensor-output kernel \displaystyle\mathbf{K}(\bm{x},\bm{x}^{\prime})=\mathrm{vec}\big(\mathbf{A}\big)\mathrm{vec}\big(\mathbf{A}\big)^{\top}k(\bm{x},\bm{x}^{\prime}). (7) where \mathbf{A}\in\mathbb{R}^{t_{1}\times\cdots\times t_{m}} is a core tensor, and k(\cdot,\cdot) is a base kernel on \mathcal{X} . Note that \mathbf{K}(\bm{x},\bm{x}^{\prime}) is designed to capture both input correlations and dependencies among tensor entries. For the non-separable kernel in ( 6 ), each base kernel k_{lj}(\bm{x},\bm{x}^{\prime}) models correlations in the input space, while the matrix \operatorname{vec}(\mathbf{A}_{l})\operatorname{vec}(\mathbf{A}_{l})^{\top} encodes the dependency structure across tensor entries. For the separable kernel in ( 7 ), k(\bm{x},\bm{x}^{\prime}) captures input correlations and \mathrm{vec}(\mathbf{A})\mathrm{vec}(\mathbf{A})^{\top} specifies the dependency structure within the tensor output. Proposition 1 . The kernels in Definitions 1 and 2 are symmetric and positive semidefinite on \mathcal{X} , i.e., (1) \forall\bm{x},\bm{x}^{\prime}\in\mathcal{X} , \mathbf{K}(\bm{x},\bm{x}^{\prime})=\mathbf{K}(\bm{x}^{\prime},\bm{x})^{\top} ; (2) \forall n\in\mathbb{N} , any \bm{x}_{1},\ldots,\bm{x}_{n}\in\mathcal{X} , and any \mathbf{y}_{1},\ldots,\mathbf{y}_{n}\in\mathcal{Y} , \sum_{i,j=1}^{n}vec(\mathbf{y}_{i})^{\top}\mathbf{K}(\bm{x}_{i},\bm{x}_{j})vec(\mathbf{y}_{j})\geq 0 . Its proof is given in Appendix E . Proposition 1 ensures that both classes of tensor-output kernels define valid covariance functions for TOGP, and hence the induced TOGP prior is well defined. Remark 1 . The core tensors \{\mathbf{A}_{l}\}_{l=1}^{m} in ( 6 ) and \mathbf{A} in ( 7 ) contain mT and T free parameters, respectively. To reduce the parameter complexity, low-rank decomposition-based structures can be imposed on these cores, such as CANDECOMP/PARAFAC (CP) decomposition ( 20 ) or tensor-train (TT) decomposition ( 30 ) . Details are shown in Appendix B . Denote the hyperparameters by \bm{\Theta}=\left\{\bm{\theta},\mathbf{a},\sigma^{2},\tau^{2}\right\} . For the non-separable kernel in ( 6 ), \bm{\theta}=\{\theta_{l,j}\}_{l,j=1}^{m,t_{l}} are the parameters of the base kernel \{k_{l,j}(\cdot,\cdot)\} , and \bm{a}=\{a_{lij}\}_{l,i,j}^{m,m,t_{l}} are the entries of \{\mathbf{A}_{l}\}_{l=1}^{m} . For the kernel in ( 7 ), \bm{\theta}=\{\theta_{1},\ldots,\theta_{d}\} is the parameters of k(\cdot,\cdot) , and \bm{a}=\{a_{ij}\}_{i,j}^{m,t_{l}} are the entries of \mathbf{A} . We estimate \bm{\Theta} by maximum likelihood. The detailed estimation, algorithm, and complexity analysis are provided in Appendix C . Remark 2 . The ranks of the core tensors \{\mathbf{A}_{\ell}\}_{\ell=1}^{m} are selected via cross-validation. Let \mathbf{R}_{c}=\{\bm{r}_{1},\dots,\bm{r}_{c}\} be the set of candidate ranks, we fit the TOGP model and evaluate its predictive performance on a held-out validation set using the mean absolute error (MAE) criterion. We select \bm{r}^{\star}=\arg\min_{\bm{r}\in\mathbf{R}_{c}}\text{MAE}(\bm{r}) , where \text{MAE}(\bm{r})=\frac{1}{n_{\text{test}}}\sum_{i=1}^{n_{\text{test}}}\left\|\frac{\mathbf{f}_{i}-\hat{\mathbf{f}}_{i}(\bm{r})}{\mathbf{f}_{i}}\right\| . The data-driven choice balances model flexibility and complexity, mitigating overfitting while preserving expressive capacity. Remark 3 . To improve scalability for large nT , we adopt a Nyström low-rank approximation of the block covariance matrix \mathbf{K}_{n}\in\mathbb{R}^{nT\times nT} . Specifically, it selects n_{\ell}\ll nT landmark columns to construct a rank- n_{\ell} approximation \mathbf{K}_{n}\approx\tilde{\mathbf{U}}\tilde{\mathbf{\Lambda}}\tilde{\mathbf{U}}^{\top} , which can be viewed as approximating the leading spectral components of \mathbf{K}_{n} . We choose the effective rank via cumulative explained variance, i.e., l=\min\limits_{l_{0}}\left\{l_{0}\in\{1,\ldots,nT\}:\sum_{i=1}^{l_{0}}\lambda_{i}/\sum_{i=1}^{nT}\lambda_{i}\geq c\right\} , where \{\lambda_{i}\} denote the eigenvalues of \mathbf{K}_{n} in non-increasing order. Then, evaluating (\mathbf{K}_{n}+\eta\mathbf{I}_{nT})^{-1} can be reduced to \mathcal{O}(nT\,n_{\ell}^{2}+n_{\ell}^{3}) ( 46 ) . Thus, the overall training complexity is reduced to \mathcal{O}\left((nT\,n_{\ell}^{2}+n_{\ell}^{3}+n^{2}T^{2}m_{h})\log n\right) . 3.2 Upper Confidence Bound Acquisition Strategy Building on TOGP as a surrogate for \mathbf{f} , we develop a UCB-based acquisition strategy. At round n+1 , given past observations \mathbf{X}_{n} and \bm{Y}_{n} , we update the hyperparameters \bm{\Theta}_{n} and the posterior mean ( 4 ) and covariance ( 5 ). The UCB acquisition function for the scalarization-based objective in ( 1 ) is defined as \displaystyle\alpha_{UCB}(\bm{x}\mid\mathcal{D}_{n})=L_{f}\hat{\bm{\mu}}_{n}(\bm{x})+\beta_{n}\big\|\hat{\mathbf{K}}_{n}(\bm{x},\bm{x})\big\|^{1/2}, (8) where \beta_{n}>0 balances exploration and exploitation. This criterion encourages exploration in directions with greater predictive uncertainty under the tensor-output setting. The next query is then selected by maximizing ( 8 ): \displaystyle\bm{x}_{n+1}=\arg\max_{\bm{x}\in\mathcal{X}}\alpha_{UCB}(\bm{x}\mid\mathcal{D}_{n}). (9) The complete TOBO algorithm and its complexity analysis are given in Appendix D . We now study theoretical properties of TOBO under the following conditions. We first define two commonly used notions of regret. Definition 3 . At each round n , the TOBO method selects a queried input \bm{x}_{n}\in\mathcal{X} . The instantaneous regret is defined as r_{n}=L_{f}\mathbf{f}(\bm{x}^{\star})-L_{f}\mathbf{f}(\bm{x}_{n}) , and the cumulative regret up to round N is defined as R_{N}=\sum_{n=1}^{N}\left[L_{f}\mathbf{f}(\bm{x}^{\star})-L_{f}\mathbf{f}(\bm{x}_{n})\right] . The regret quantifies the gap from not knowing the objective in advance. A good strategy can achieve a sub-linear cumulative regret so that the average regret per round converges to zero as N\to\infty . Definition 4 . At round n , TOBO selects an input \bm{x}_{n}\in\mathcal{X} . The instantaneous regret is r_{n}=L_{f}\mathbf{f}(\bm{x}^{\star})-L_{f}\mathbf{f}(\bm{x}_{n}) , and the cumulative regret up to round N is R_{N}=\sum_{n=1}^{N}\left[L_{f}\mathbf{f}(\bm{x}^{\star})-L_{f}\mathbf{f}(\bm{x}_{n})\right] . The regret quantifies the gap due to not knowing the objective in advance. A good strategy achieves sublinear cumulative regret so that the average regret R_{N}/N converges to zero as N\to\infty . Assumption 1 . The unknown function \mathbf{f} is a TOGP prior with kernel \mathbf{K} as defined in ( 6 )–( 7 ). Assumption 2 . The scalarized objective \bm{x}\mapsto L_{f}\!\big(\mathbf{f}(\bm{x})\big) is L -Lipschitz on \mathcal{X} , i.e., for any \bm{x},\bm{x}^{\prime}\in\mathcal{X} , |L_{f}(\mathbf{f}(\bm{x}_{i}))-L_{f}(\mathbf{f}(\bm{x}_{j})|\leq L\|\mathbf{f}(\bm{x}_{i})-\mathbf{f}(\bm{x}_{j})\| holds. Assumption 1 specifies the Bayesian setting under which \mathbf{f} follows a TOGP prior. Assumption 2 ensures that the scalarized objective is stable under small perturbations of the input. Lemma 1 . Let \partial vec(\mathbf{f})/\partial x_{j}\in\mathbb{R}^{T} be the gradient of vec(\mathbf{f}) with respect to the j -th coordinate of \bm{x}\in\mathcal{X} . Then, \partial vec(\mathbf{f})/\partial x_{j} is a GP with covariance \mathbf{K}^{\nabla}(x_{j},x_{j}^{\prime}) . Under Assumptions 1 , given data \mathbf{X}_{n} and \bm{Y}_{n} with n\geq 1 , there exist constants a,b>0 such that for any L^{\prime}>0 , \displaystyle\Pr\left(\sup_{\bm{x}\in\mathcal{X}}\|\partial vec(\mathbf{f})/\partial x_{j}\|>L^{\prime}+C_{\nabla}\right)\leq a\exp(-L^{\prime 2}/b^{2}),\quad j=1,\cdots,d. (10) where C_{\nabla}=\sup_{\bm{x}\in\mathcal{X}}\sqrt{\mathrm{tr}(\hat{\mathbf{K}}_{n}^{\nabla}(x_{j},x_{j}))} . Its proof is given in Appendix F . Lemma 1 shows that the derivative of the vectorized TOGP remains Gaussian and holds high-probability confidence bounds. Theorem 1 . Under Assumptions 1 – 2 , define C_{n}=\sup_{\bm{x}\in\mathcal{X}}\mathrm{tr}(\hat{\mathbf{K}}_{n}(\bm{x},\bm{x}))/\lambda_{\max}^{(n)}(\bm{x}) , where \lambda_{\max}^{(n)}(\bm{x}) is the largest eigenvalue of \hat{\mathbf{K}}_{n}(\bm{x},\bm{x}) . Suppose \mathcal{X}\subseteq[0,r]^{d} . Then, for any \delta\in(0,1) , TOBO with \beta_{n}=\sqrt{C_{n}}+2d\log(rdn^{2}\big(b\sqrt{\log(da/\delta)}+C_{\nabla}\big)/\delta) holds that, \Pr\left(R_{N}\leq L\left(\sqrt{C_{1}N\gamma_{N}(\mathbf{K},\eta)}\,\beta_{N}+\tfrac{\pi^{2}}{6}\right)\right)\geq 1-\delta , where C_{1}>0 is a constant and \gamma_{N}(\mathbf{K},\eta):=\max_{\mathcal{X}_{N}\subset\mathcal{X}}\frac{1}{2}\log\det\left(\mathbf{I}_{NT}+\eta^{-1}\mathbf{K}_{N}\right) denotes the maximum information gain. Its proof is given in Appendix G . Theorem 1 implies that TOBO achieves sublinear cumulative regret with high probability. Proposition 2 . If \mathbf{K}(\bm{x},\bm{x}^{\prime}) is the separable kernel in Definition 2 , then the maximum information gain satisfies \gamma_{n}(\mathbf{K},\eta)=\mathcal{O}\left(T\log(n)^{d+1}\right) when k(\bm{x},\bm{x}^{\prime}) is a Gaussian kernel, and \gamma_{n}(\mathbf{K},\eta)=\mathcal{O}(Tn^{d(d+1)/(2\nu+d(d+1))}\log(n)) when k(\bm{x},\bm{x}^{\prime}) is a Matérn kernel with \nu>1 . Details are provided in Appendix H . 4 Tensor-output combinatorial bandit Bayesian optimization We now consider a more challenging setting in which only k0 , TOCBBO with \tilde{\beta}_{n}=\sqrt{\tilde{C}_{n}}+2d\log(\frac{rdn^{2}(b\sqrt{\log(da/\delta)}+\tilde{C}_{\nabla})}{l}{\delta}) and \tilde{\rho}_{n}=\sqrt{2\log\left(\frac{NT\pi_{n}}{\delta}\right)} holds that, \Pr\left(R_{N}\leq H\left(\sqrt{C_{3}N\gamma_{N}(\tilde{\mathbf{K}},\eta)}\tilde{\beta}_{N}+\frac{\pi^{2}}{6}+\sqrt{C_{4}TN\tilde{\gamma}_{N}\big(\tilde{\mathbf{K}},\eta)}\tilde{\rho}_{N}\right)\right)\geq 1-\delta , where C_{3},C_{4}>0 are constants, \pi_{n}>0 is a sequence such that \sum_{n=1}^{\infty}1/\pi_{n}=1 , \gamma_{n}(\tilde{\mathbf{K}},\eta)=\max_{\mathbf{X}_{N}\subset\mathcal{X}}\frac{1}{2}\log\det\left(\mathbf{I}_{kN}+\eta^{-1}\mathbf{E}_{N}\mathbf{K}_{N}\mathbf{E}^{\top}_{N}\right) , and \tilde{\gamma}_{N}(\tilde{\mathbf{K}},\eta)=\max_{\bm{\Lambda}_{N}\subset\Lambda}\frac{1}{2}\log\det\left(\mathbf{I}_{kN}+\eta^{-1}\mathbf{E}_{N}\mathbf{K}_{N}\mathbf{E}^{\top}_{N}\right) is the maximum information gain for super-arms. The proof is provided in Appendix I . Theorem 2 implies that TOCBBO achieves a sublinear regret upper bound with high probability. Proposition 3 . Suppose the kernel \mathbf{K}(\bm{x},\bm{x}^{\prime}) follows the separable structure specified in Definition 2 . The maximum information gain \gamma_{n}(\tilde{\mathbf{K}},\eta) and \tilde{\gamma}_{n}(\tilde{\mathbf{K}},\eta) are \mathcal{O}\left(T(\log n)^{d+1}\right) and \mathcal{O}\left(Tn^{\frac{d(d+1)}{2\nu+d(d+1)}}\log n\right) for the Gaussian kernel and the Matérn kernel ( \nu>1 ), respectively, where d denotes the input dimension. Details are provided in Appendix J . 5 Experiments We evaluate TOBO and TOCBBO on both synthetic and real-case data, and compare them with baselines where the tensor output is vectorized and MOGPs are used as surrogate models. Specifically, we consider three GPs in the literature: (1) sMTGP: the scalable multi-task GP 25 ; (2) MLGP: the multi-linear GP 48 ; and (3) MVGP: the multi-variate GP 9 . For each GP, we examine two sequential BO sampling strategies: UCB-based BO and random sampling. In addition, we replace the UCB acquisition in TOBO and TOCBBO with random sampling to construct an ablation baseline, denoted as TOGP-RS. Details of all baseline settings are provided in Appendix K . 5.1 Synthetic experiments We generate synthetic functions of the form \mathbf{f}(\bm{x})=\mathbf{B}\otimes_{1}\mathbf{U}_{1}\otimes_{2}\ldots\otimes_{m-1}\mathbf{U}_{m-1}\otimes_{m}\mathbf{g}(\bm{x}) , where each element of \mathbf{B}\in\mathbb{R}^{P_{1}\times\ldots P_{m}} is independently sampled from U(0,1) , the ij -th element of \mathbf{U}_{l}\in\mathbb{R}^{P_{l}\times T_{l}} is defined as li\cos(ijl/2)+\sin(li) , and \mathbf{g}(\bm{x})=\left(\sin(5\bm{x}),\cos(\bm{x})\right)\in\mathbb{R}^{P_{m}\times T_{m}} . Here P_{m}=d and \bm{x}\in[0,1]^{d} . We consider three parameter settings: \mathbf{f}(\bm{x}) : (1) m=3 , (T_{1},T_{2},T_{3})=(2,4,2) , (P_{1},P_{2},P_{3})=(3,3,3) ; (2) m=2 , (T_{1},T_{2})=(3,2) , (P_{1},P_{2})=(3,2) ; and (3) m=3 , (T_{1},T_{2},T_{3})=(4,5,2) , (P_{1},P_{2},P_{3})=(3,3,3) . Observations are collected as \mathbf{y}_{i}=\mathbf{f}(\bm{x}_{i})+\bm{\varepsilon}_{i} , where \bm{\varepsilon}_{i}\overset{\text{i.i.d.}}{\sim}N(0,0.1^{2}\mathbf{I}) . For CBBO tasks, we set k=T/6 . We generate n_{\text{train}}=10d training samples and n_{\text{test}}=5d testing samples via a Latin hypercube design ( 33 ) . The training set is used for hyperparameter estimation, and predictive performance is evaluated on the test set in terms of NLL, MAE, and \|\text{Cov}\| , with details provided in Appendix K . To balance modeling flexibility and computational cost, we use the separable tensor-output kernel in ( 7 ) for Settings (1) and (2), and the non-separable tensor-output kernel in ( 6 ) for Setting (3). The results are summarized in Table 2 . Table 2: The prediction performance of GPs in the three synthetic settings. Setting (1) Setting (2) Setting (3) NLL MAE \|\text{Cov}\| NLL MAE \|\text{Cov}\| NLL MAE \|\text{Cov}\| TOGP 503.0 0.1571 2.02 -18.1 0.1052 0.04 -3923.1 0.1372 2.82 sMTGP 749.4 0.1684 1.44 -5.0 0.1566 0.06 -3743.0 0.1501 22.01 MLGP 707937.1 0.9428 67.00 7066.9 0.8789 5.12 -55800.7 1.1670 0.06 MVGP 11152.2 0.6746 22.20 46.54 0.1784 0.10 -2583.1 1.0000 142.72 As shown, our proposed method achieves the lowest NLL and MAE, indicating that the TOGP model provides the highest prediction accuracy. Among the three baselines, MLGP performs the worst because its fitted covariance matrix becomes singular under our experimental configuration. sMTGP outperforms MVGP because it considers modeling each mode of the tensor output, and MVGP ignores the tensor structure by vectorizing it. Table 3 summarizes the optimization performance of different methods for the BO and CBBO tasks. We set N=10d and evaluate each method using \text{MSE}_{x} , \text{MAE}_{y} , and Acc, as defined in Appendix K . Table 3: The optimization performance of different methods in the three synthetic settings. Setting (1) Setting (2) Setting (3) \text{MSE}_{x} \text{MAE}_{y} Acc \text{MSE}_{x} \text{MAE}_{y} Acc \text{MSE}_{x} \text{MAE}_{y} Acc BO TOBO 0.0000 0.0008 - 0.0003 0.0350 - 0.0001 0.0050 - sMTGP-UCB 0.0001 0.0031 - 0.0003 0.0361 - 0.0048 0.0590 - MLGP-UCB 0.0433 0.3793 - 0.0512 0.9295 - 0.0342 0.6263 - MVGP-UCB 0.0015 0.0523 - 0.0044 0.0550 - 0.0342 0.6263 - TOGP-RS 0.0893 0.3145 - 0.0026 0.0351 - 0.0106 0.1526 - sMTGP-RS 0.0251 0.3242 - 0.0206 0.3684 - 0.0084 0.1223 - MLGP-RS 0.0433 0.3793 - 0.0435 0.7976 - 0.0075 0.0934 - MVGP-RS 0.0148 0.2036 - 0.0157 0.2697 - 0.0084 0.1223 - CBBO TOCBBO 0.0023 0.0172 1.00 0.0000 0.0000 1.00 0.0021 0.0145 1.00 sMTGP-UCB 0.1832 0.5614 0.67 0.0000 0.0000 1.00 0.0075 0.2171 0.86 MLGP-UCB 0.0667 0.6527 0.33 0.1826 0.0779 1.00 0.2070 0.7105 0.43 MVGP-UCB 0.0032 0.0285 1.00 0.0725 0.0312 1.00 0.0151 0.1988 0.71 TOGP-RS 0.0438 0.5319 0.67 0.0908 0.0395 1.00 0.0512 0.8793 0.43 sMTGP-RS 0.3151 0.5882 0.67 0.1826 0.0779 1.00 0.0117 0.9453 0.29 MLGP-RS 0.1053 0.6909 0.33 0.1826 0.0779 1.00 0.0117 0.9453 0.29 MVGP-RS 0.1313 0.5975 0.33 0.1489 0.0654 0.00 0.0512 0.8793 0.43 For each surrogate, the UCB-based strategy consistently outperforms random sampling. This is intuitive due to UCB’s better theoretical guarantees. Across all GPs, TOBO and TOCBBO achieve the smallest \mathrm{MSE}_{x} and \mathrm{MAE}_{y} , indicating that the selected pairs yield objective values closest to the true optimum. Among the baseline methods, sMTGP-UCB delivers the second-best performance, followed by MVGP-UCB, while MLGP-UCB performs the worst. This result is consistent with their modeling abilities shown in Table 2 . Finally, we provide each round’s logarithmic instantaneous regret for different methods for BO and CBBO in Figure 1 . Figure 1: Each round’s logarithmic instantaneous regret of different methods in the Setting (1) (L), (2) (M), and (3) (R) for BO (Top row) and CBBO (Bottom row). We can observe that TOBO and TOCBBO consistently achieve the lowest instantaneous regret across all three settings, highlighting their superiority. Additional synthetic results are provided in Appendix M . 5.2 Case studies We further apply apply TOBO and TOCBBO to four real-world datasets: (1) CHEM ( 35 ) : input \bm{x}\in\mathbb{R}^{2} and output \mathbf{y}\in\mathbb{R}^{4\times 3\times 3} ; (2) MAT ( 43 ) : input \bm{x}\in\mathbb{R}^{4} and output \mathbf{y}\in\mathbb{R}^{5\times 4\times 4} ; (3) PRINT ( 49 ) : input \bm{x}\in\mathbb{R}^{5} and output \mathbf{y}\in\mathbb{R}^{3\times 4\times 3} ; (4) REEN : input \bm{x}\in\mathbb{R}^{6} and output \mathbf{y}\in\mathbb{R}^{10\times 2} . Detailed description of these datasets is provided in Appendix K . Since the REEN dataset provides fully observed tensor outputs, we first evaluate surrogate modeling performance by randomly selecting 30 samples for training and 5 samples for testing. Table 4 reports the predictive performance of the four GP surrogates on the test set. TOGP achieves the best accuracy in terms of NLL and MAE. Figure 2 further compares optimization performance on both BO (left) and CBBO (right), where TOBO and TOCBBO consistently perform the best, demonstrating their effectiveness on real-world black-box systems. Table 4: The prediction performance of GPs in the REEN dataset. TOGP sMTGP MLGP MVGP NLL 15.6664 33.3198 88.2722 48.7167 MAE 0.0883 0.0993 0.0929 0.1054 \|\text{Cov}\| 0.4918 0.3555 0.4318 0.3711 Figure 2: Each round’s optimal objective value in REEN for BO (L) and CBBO (R). The remaining three datasets contain only partially observed tensor outputs, we only evaluate optimization performance under the CBBO setting. Figure 2 shows that TOCBBO can identify the optimal input consistently using fewer rounds than the baselines, further demonstrating its superior effectiveness. Figure 3: Each round’s optimal objective value in CHEM (L), MAT (M), and PRINT (R). 6 Conclusion and discussion In this work, we develop two BO methods for tensor-output systems. TOBO employs two classes of kernel-based TOGP as a surrogate model and selects query points via a UCB acquisition function. TOCBBO extends TOGP to the partially observed tensor outputs and adopts a CMAB-UCB2 criterion to sequentially select both the query input and the super-arm. We establish theoretical regret bounds for both methods and demonstrate their effectiveness on extensive synthetic and real-world experiments. Future work could consider integrating the proposed tensor-output kernels with sparse techniques, such as sparse GPs ( 36 ) and scalable LMC ( 7 ) , to improve the computational efficiency of TOGP. It would be valuable to explore alternative acquisition functions within this framework. For example, one may combine the TOGP model with improvement-based criteria such as EI or PI ( 18 ) , and further extend them to the TOCBBO setting. Moreover, acquisition functions based on improvement ( 42 ) or information-theoretic criteria ( 41 ) are also be considered in our framework, provided that the computational challenges for tensor outputs can be addressed. Finally, it is worth exploring more meaningful tensor structures for our proposed framework, such as a spatiotemporal system. Appendix A Use of LLMs Large Language Models (LLMs) were used to aid in the writing and polishing of the manuscript. Specifically, we used an LLM to assist in refining the language, improving readability, and ensuring clarity in various sections of the paper. The model helped with tasks such as sentence rephrasing, grammar checking, and enhancing the overall flow of the text. It is important to note that the LLM was not involved in the ideation, research methodology, or experimental design. All research concepts, ideas, and analyses were developed and conducted by the authors. The contributions of the LLM were solely focused on improving the linguistic quality of the paper, with no involvement in the scientific content or data analysis. The authors take full responsibility for the content of the manuscript, including any text generated or polished by the LLM. We have ensured that the LLM-generated text adheres to ethical guidelines and does not contribute to plagiarism or scientific misconduct. Appendix B The details of the tensor decomposition in Remark 1 As discussed in Remark 1 , directly estimating the entries of the core tensors \{\mathbf{A}_{l}\}_{l=1}^{m} or \mathbf{A} requires mT parameters for the non-separable tensor-output kernel and T parameters for the separable tensor-output kernel, which becomes intractable for large-scale or high-order tensors. To reduce the parameter complexity, we impose low-rank tensor structures and adopt different decompositions depending on the tensor order. Low-order tensors ( m\leq 3 ): When the tensor order is small, we employ the CP decomposition: \displaystyle\mathbf{A}_{l}=\sum_{r=1}^{R_{l}}\bm{a}_{lr1}\circ\bm{a}_{lr2}\circ\cdots\circ\bm{a}_{lrm}\quad\text{for the non-separable kernel}, (17) \displaystyle\mathbf{A}=\sum_{r=1}^{R}\bm{a}_{r1}\circ\bm{a}_{r2}\circ\cdots\circ\bm{a}_{rm}\quad\text{for the separable kernel}, (18) where \bm{a}_{lri},\bm{a}_{ri}\in\mathbb{R}^{t_{l}} for r=1,\ldots,R and i=1,\ldots,m for r=1,\ldots,R and i=1,\ldots,m . The number of free parameters becomes \sum_{l=1}^{m}\sum_{i=1}^{m}R_{l}t_{i} for the non-separable kernel and R\sum_{i=1}^{m}t_{i} for the separable kernel, which scales linearly with each mode size t_{i} . Thus, CP provides a compact representation when m\leq 3 . However, CP can be ill-posed for higher-order tensors because the set of tensors with bounded CP rank is not closed, and a best low-rank approximation may fail to exist ( 17 ) . Moreover, the factor matrices can easily become ill-conditioned as m increases, leading to numerical instability ( 10 ) . High-order tensors ( m>3 ): When the tensor order is large, we employ the TT decomposition: \displaystyle\mathbf{A}_{l}=\mathbf{G}_{l1}(t_{1})\mathbf{G}_{l2}(t_{2})\cdots\mathbf{G}_{lm}(t_{m})\quad\text{for the non-separable kernel}, (19) \displaystyle\mathbf{A}=\mathbf{G}_{1}(t_{1})\mathbf{G}_{2}(t_{2})\cdots\mathbf{G}_{m}(t_{m})\quad\text{for the separable kernel}, (20) where each \mathbf{G}_{lj}(t_{j}) is a r_{l,j-1}\times t_{j}\times r_{l,j} three-mode tensor and the TT-ranks satisfy r_{l,0}=r_{l,m}=1 for l=1,\ldots,m . Similarly, \mathbf{G}_{j}(t_{j}) is a r_{j-1}\times t_{j}\times r_{j} three-mode tensor that satisfies r_{0}=r_{m}=1 . The total number of free parameters is \sum_{l=1}^{m}\sum_{j=1}^{m}r_{l,j-1}t_{j}r_{l,j} for the non-separable tensor-output kernel in ( 6 ) and \sum_{j=1}^{m}r_{j-1}t_{j}r_{j} for the separable tensor-output kernel in ( 7 ). It scales linearly with the tensor order m , instead of exponentially as in the full tensor. This makes TT decomposition highly suitable for high-order tensors ( m>3 ), as it balances modeling flexibility with computational scalability and avoids the instability of CP. In summary, we use CP for low-order cores and TT for high-order cores, ensuring both efficiency and numerical robustness across different tensor settings. Appendix C The estimation of hyperparameters for the TOGP and PTOGP In this appendix, we provide the details of hyperparameter estimation for both TOGP and PTOGP. Without loss of generality, we assume a zero prior mean \bm{\mu}=0 in ( 3 ) and ( 12 ). C.1 Parameter estimation for training TOGP Given the training data \mathbf{X}_{n}=(\bm{x}_{1},\ldots,\bm{x}_{n}) and \bm{Y}_{n}=\left(vec(\mathbf{y}_{1})^{\top},\ldots,vec(\mathbf{y}_{n})^{\top}\right)^{\top} , the log marginal likelihood of TOGP is given by: \displaystyle\log L(\bm{\Theta})=-\frac{1}{2}\log|\mathbf{\Sigma}_{n}|-\frac{1}{2}\bm{Y}_{n}^{\top}\mathbf{\Sigma}_{n}^{-1}\bm{Y}_{n}, (21) where \mathbf{\Sigma}_{n}=\sigma^{2}\mathbf{K}_{n}+\tau^{2}\mathbf{I}_{nT} . Then, ( 21 ) can be optimized by applying gradient-based optimization methods, such as L-BFGS algorithm. The gradients of the log-likelihood function in ( 21 ) with respect to the hyperparameters \tau^{2} , \sigma^{2} , \bm{\theta} , and \mathbf{a} is given by \displaystyle\frac{\partial\log L}{\partial\tau^{2}} \displaystyle=\frac{1}{2}\mathrm{tr}\left(\bm{\Sigma}_{n}^{-1}\mathbf{K}_{n}\right)-\frac{1}{2}\bm{Y}_{n}^{\top}\bm{\Sigma}_{n}^{-1}\mathbf{K}_{n}\bm{\Sigma}_{n}^{-1}\bm{Y}_{n}, (22) \displaystyle\frac{\partial\log L}{\partial\sigma^{2}} \displaystyle=\frac{1}{2}\mathrm{tr}\left(\bm{\Sigma}_{n}^{-1}\right)-\frac{1}{2}\bm{Y}_{n}^{\top}\bm{\Sigma}_{n}^{-1}\bm{\Sigma}_{n}^{-1}\bm{Y}_{n}, (23) \displaystyle\frac{\partial\log L}{\partial\theta_{lij}} \displaystyle=\frac{\tau^{2}}{2}\mathrm{tr}\left(\bm{\Sigma}_{n}^{-1}\frac{\partial\mathbf{K}_{n}}{\partial\theta_{lij}}\right)-\frac{\tau^{2}}{2}\bm{Y}_{n}^{\top}\bm{\Sigma}_{n}^{-1}\frac{\partial\mathbf{K}_{n}}{\partial\theta_{lij}}\bm{\Sigma}_{n}^{-1}\bm{Y}_{n}, (24) \displaystyle\frac{\partial\log L}{\partial a_{lij}} \displaystyle=\frac{1}{2}\mathrm{tr}\left(\bm{\Sigma}_{n}^{-1}\tau^{2}\frac{\partial\mathbf{K}_{n}}{\partial a_{lij}}\right)-\frac{\tau^{2}}{2}\bm{Y}_{n}^{\top}\bm{\Sigma}_{n}^{-1}\frac{\partial\mathbf{K}_{n}}{\partial a_{lij}}\bm{\Sigma}_{n}^{-1}\bm{Y}_{n}, (25) where \theta_{lij} represents the scale parameters of k_{lj} , the kernel function associated with the l -th mode. The matrices \frac{\partial\mathbf{K}_{n}}{\partial\theta_{lij}} and \frac{\partial\mathbf{K}_{n}}{\partial a_{lij}} are the partial derivatives of the kernel matrix with respect to the corresponding kernel parameters. The detailed algorithm for training TOGP is given as follows: Algorithm 1 Parameter estimation for training TOGP 1: Training data \mathbf{X}_{n} and \bm{Y}_{n} , initial hyperparameters \bm{\Theta}_{0}=\{\sigma^{2}_{0},\tau^{2}_{0},\bm{\theta}_{0},\mathbf{a}_{0}\} ; 2: \sigma^{2}\leftarrow\sigma^{2}_{0} , \tau^{2}\leftarrow\tau^{2}_{0} , \bm{\theta}\leftarrow\bm{\theta}_{0} \mathbf{a}\leftarrow\mathbf{a}_{0} ; 3: while \tau^{2} , \sigma^{2} , \bm{\theta} , \bm{\omega} not converge do 4: Update \tau^{2} based on ( 22 ); 5: Update \sigma^{2} based on ( 23 ); 6: Update \bm{\theta} based on ( 24 ); 7: Update \mathbf{a} based on ( 25 ). 8: end while Remark 4 . For the non-separable tensor-output kernel in Definition 1 , the total number of hyperparameters to be estimated in TOGP is m_{h}=2+T+\sum_{l=1}^{m}\sum_{i=1}^{m}R_{l}t_{i} when m\leq 3 and m_{h}=2+T+\sum_{l=1}^{m}\sum_{j=1}^{m}r_{l,j-1}t_{j}r_{l,j} when m>3 . For the separable tensor-output kernel in Definition 2 , the total number of hyperparameters to be estimated in TOGP is m_{h}=2+T+R\sum_{i=1}^{m}t_{i} when m\leq 3 and m_{h}=2+T+\sum_{j=1}^{m}r_{j-1}t_{j}r_{j} when m>3 . The computational complexity of computing the gradient of \log L(\bm{\Theta}) with respect to all m_{h} parameters is \mathcal{O}(n^{3}T^{3}+n^{2}T^{2}m_{h}) . When using the L-BFGS algorithm to optimize the likelihood function results, the number of iterations typically scales as \mathcal{O}\left(\log(n)\right) ( 6 ) . Therefore, the overall computational complexity for training the TOGP takes \mathcal{O}\left(n^{3}T^{3}\log(n)+n^{2}T^{2}m_{h}\log(n)\right) computational complexity. C.2 Parameter estimation for training PTOGP Given the partially observed training data \mathbf{X}_{n}=(\bm{x}_{1},\ldots,\bm{x}_{n}) , \bm{\Lambda}_{n}=(\bm{\lambda}_{1},\ldots,\bm{\lambda}_{n})^{\top} , and \tilde{\bm{Y}}_{n}=(\tilde{\bm{y}}_{1},\ldots,\tilde{\bm{y}}_{n})^{\top} , the log marginal likelihood of PTOGP is given by: \displaystyle\log\tilde{L}(\bm{\Theta})=-\frac{1}{2}\log|\tilde{\mathbf{\Sigma}}_{n}|-\frac{1}{2}\mathrm{vec}(\tilde{\bm{Y}}_{n})^{\top}\tilde{\mathbf{\Sigma}}_{n}^{-1}\mathrm{vec}(\tilde{\bm{Y}}_{n}), (26) where \tilde{\mathbf{\Sigma}}_{n}=\sigma^{2}\mathbf{E}_{n}\mathbf{K}_{n}\mathbf{E}_{n}^{\top}+\tau^{2}\mathbf{I}_{nk} . Then, ( 26 ) can also be optimized by applying gradient-based optimization methods. The gradients of the log-likelihood function in ( 26 ) with respect to the hyperparameters \sigma^{2} , \tau^{2} , \bm{\theta} , and \mathbf{a} is given by \displaystyle\frac{\partial\tilde{L}}{\partial\tau^{2}} \displaystyle=\frac{1}{2}\mathrm{tr}\left(\tilde{\mathbf{\Sigma}}_{n}^{-1}\mathbf{E}_{n}\mathbf{K}_{n}\mathbf{E}_{n}^{\top}\right)-\frac{1}{2}\tilde{\bm{Y}_{n}}^{\top}\tilde{\mathbf{\Sigma}}_{n}^{-1}\mathbf{E}_{n}\mathbf{K}_{n}\mathbf{E}_{n}^{\top}\tilde{\mathbf{\Sigma}}_{n}^{-1}\tilde{\bm{Y}_{n}}, (27) \displaystyle\frac{\partial\tilde{L}}{\partial\sigma^{2}} \displaystyle=\frac{1}{2}\mathrm{tr}\left(\tilde{\bm{\Sigma}}_{n}^{-1}\right)-\frac{1}{2}\tilde{\bm{Y}_{n}}^{\top}\tilde{\mathbf{\Sigma}}_{n}^{-1}\tilde{\mathbf{\Sigma}}_{n}^{-1}\tilde{\bm{Y}_{n}}, (28) \displaystyle\frac{\partial\tilde{L}}{\partial\theta_{lij}} \displaystyle=\frac{\tau^{2}}{2}\mathrm{tr}\left(\tilde{\bm{\Sigma}}_{n}^{-1}\mathbf{E}_{n}\frac{\partial\mathbf{K}_{n}}{\partial\theta_{lij}}\mathbf{E}_{n}^{\top}\right)-\frac{\tau^{2}}{2}\tilde{\bm{Y}_{n}}^{\top}\tilde{\bm{\Sigma}}_{n}^{-1}\mathbf{E}_{n}\frac{\partial\mathbf{K}_{n}}{\partial\theta_{lij}}\mathbf{E}_{n}^{\top}\tilde{\bm{\Sigma}}_{n}^{-1}\tilde{\bm{Y}_{n}}, (29) \displaystyle\frac{\partial\tilde{L}}{\partial a_{lij}} \displaystyle=\frac{\tau^{2}}{2}\mathrm{tr}\left(\tilde{\bm{\Sigma}}_{n}^{-1}\mathbf{E}_{n}\frac{\partial\mathbf{K}_{n}}{\partial a_{lij}}\mathbf{E}_{n}^{\top}\right)-\frac{\tau^{2}}{2}\tilde{\bm{Y}_{n}}^{\top}\tilde{\bm{\Sigma}}_{n}^{-1}\mathbf{E}_{n}\frac{\partial\mathbf{K}_{n}}{\partial a_{lij}}\mathbf{E}_{n}^{\top}\tilde{\bm{\Sigma}}_{n}^{-1}\tilde{\bm{Y}_{n}}, (30) The detailed algorithm for training PTOGP is given as follows: Algorithm 2 Parameter estimation for training PTOGP 1: Training data \mathbf{X}_{n} , \bm{\Lambda}_{n} and \tilde{\bm{Y}}_{n} , initial hyperparameters \bm{\Theta}_{0}=\{\sigma^{2}_{0},\tau^{2}_{0},\bm{\theta}_{0},\mathbf{a}_{0}\} ; 2: \sigma^{2}\leftarrow\sigma^{2}_{0} , \tau^{2}\leftarrow\tau^{2}_{0} , \bm{\theta}\leftarrow\bm{\theta}_{0} \mathbf{a}\leftarrow\mathbf{a}_{0} ; 3: while \sigma^{2} , \tau^{2} , \bm{\theta} , \mathbf{a} not converge do 4: Update \tau^{2} based on ( 27 ); 5: Update \sigma^{2} based on ( 28 ); 6: Update \bm{\theta} based on ( 29 ); 7: Update \mathbf{a} based on ( 30 ). 8: end while Remark 5 . For the non-separable tensor-output kernel in Definition 1 , the total number of hyperparameters to be estimated in PTOGP is m_{h}=2+T+\sum_{l=1}^{m}\sum_{i=1}^{m}R_{l}t_{i} when m\leq 3 and m_{h}=2+T+\sum_{l=1}^{m}\sum_{j=1}^{m}r_{l,j-1}t_{j}r_{l,j} when m>3 . For the separable tensor-output kernel in Definition 2 , the total number of hyperparameters to be estimated in PTOGP is m_{h}=2+T+R\sum_{i=1}^{m}t_{i} when m\leq 3 and m_{h}=2+T+\sum_{j=1}^{m}r_{j-1}t_{j}r_{j} when m>3 . The computational complexity of computing the gradient of \tilde{L}(\bm{\Theta}) with respect to all m_{h} parameters is \mathcal{O}(k^{3}T^{3}+n^{2}kTm_{h}) . When using the L-BFGS algorithm to optimize the likelihood function results, the number of iterations typically scales as \mathcal{O}\left(\log(n)\right) 6 . Therefore, the overall computational complexity for training the PTOGP takes \mathcal{O}\left(n^{3}k^{3}\log(n)+n^{2}kTm_{h}\log(n)\right) computational complexity. Appendix D The proposed algorithms and computational complexity analysis D.1 UCB-based TOBO algorithm The detailed procedure of the proposed TOBO method is given in Algorithm 3 . Algorithm 3 UCB-based TOBO 1: Total rounds N , initial dataset \mathcal{D}_{0}=\varnothing , initial hyperparameters \bm{\Theta}_{0} ; 2: for round n=1,\ldots,N do 3: Update the posterior mean ( 4 ) and covariance ( 5 ) of \mathbf{f} given \bm{\Theta}_{n-1} ; 4: Select the next input \bm{x}_{n}\leftarrow\arg\max_{\bm{x}\in\mathcal{X}}\alpha_{UCB}(\bm{x}\mid\mathcal{D}_{n-1}) ; 5: Evaluate the black-box system and observe output \mathbf{y}_{n} ; 6: Update dataset \mathcal{D}_{n}\leftarrow\mathcal{D}_{n-1}\cup\{\bm{x}_{n},\mathbf{y}_{n}\} ; 7: Update hyperparameters \bm{\Theta}_{n} by maximizing ( 21 ) with L-BFGS; 8: end for 9: Identify i^{\star}=\arg\max_{i\in[N]}L_{f}\mathbf{f}(\bm{x}_{i}) ; 10: Output: Optimal input \bm{x}_{i^{\star}} and corresponding output \mathbf{y}_{i^{\star}} . Remark 6 . When using the TOBO method to select \bm{x}^{\star} , the computational complexity of updating TOGP is \mathcal{O}\left((n-1)^{3}T^{3}\right) at round n . Then, the computational complexity of querying the next point is \mathcal{O}\left((n-1)^{2}T^{2}\log(n)\right) by using the L-BFGS method. After updating the design dataset, the computational complexity of updating the hyperparameters \bm{\Theta} is \mathcal{O}\left(n^{3}T^{3}\log(n)+n^{2}T^{2}m_{h}\log(n)\right) . Thus, the computational complexity of TOBO at round n is \mathcal{O}\left(n^{3}T^{3}\log(n)+n^{2}T^{2}m_{h}\log(n)\right) . Suppose that there are N points needed to query, the total computational complexity of Algorithm 3 is \mathcal{O}\left(\sum_{n=1}^{N}\left[n^{3}T^{3}\log(n)+n^{2}T^{2}m_{h}\log(n)\right]\right) . D.2 CMAB-UCB2-based TOCBBO algorithm The detailed algorithm of TOCBBO is provided in Algorithm 4 . Algorithm 4 CMAB-UCB2-based TOCBBO 1: Total rounds N , initial dataset \tilde{\mathcal{D}}_{0}=\varnothing , initial hyperparameters \bm{\Theta}_{0} ; 2: for round n=1,\ldots,N do 3: Update the posterior mean ( 13 ) and covariance ( 14 ); 4: Select the next input \bm{x}_{n} using ( 15 ); 5: Select the super-arm \bm{\lambda}_{n} using ( 16 ); 6: Evaluate \mathbf{f} under (\bm{x}_{n},\bm{\lambda}_{n}) and observe \tilde{\bm{y}}_{n} ; 7: Update dataset \tilde{\mathcal{D}}_{n}\leftarrow\tilde{\mathcal{D}}_{n-1}\cup\{(\bm{x}_{n},\bm{\lambda}_{n}),\tilde{\bm{y}}_{n}\} ; 8: Update hyperparameters \bm{\Theta}_{n} by maximizing \log\tilde{L}(\bm{\Theta}) with L-BFGS; 9: Update incumbent solution \{\bm{x}_{n}^{\star},\bm{\lambda}_{n}^{\star}\}=\arg\max_{i=1,\ldots,n}H_{f}\tilde{\bm{f}}(\bm{x}_{i},\bm{\lambda}_{i}) ; 10: end for 11: Identify i^{\star}=\arg\max_{i\in[N]}H_{f}\tilde{\bm{f}}(\bm{x}_{i},\bm{\lambda}_{i}) ; 12: Output: Optimal input \bm{x}_{i^{\star}} , optimal super-arm \bm{\lambda}_{i^{\star}} , and output \tilde{\bm{y}}_{i^{\star}} . Remark 7 . When using the proposed TOCBBO method to jointly select \bm{x}^{\star} and \bm{\lambda}^{\star} , the computational complexity of updating the PTOGP at round n is \mathcal{O}\left((n-1)^{3}k^{3}\right) . Then, based on the proposed CMAB-UCB2 criterion, the computational complexity of querying the next input by using L-BFGS method is \mathcal{O}\left((n-1)^{2}k^{2}\right) and selecting the next super-arm by using greedy Top- k method is \mathcal{O}(kT^{3}) , respectively. After updating the current design dataset, the computational complexity of updating hyperparameters \bm{\Theta} is \mathcal{O}(n^{3}k^{3}\log(n)+n^{2}kTm_{h}\log(n)) . Therefore, at round n , the computational complexity of TOCBBO method is \mathcal{O}(n^{3}k^{3}\log(n)+n^{2}kTm_{h}\log(n)+kT^{3}) . Assuming a total of N rounds, the overall computational complexity of Algorithm 4 is \mathcal{O}\left(\sum_{n=1}^{N}\left[n^{3}k^{3}\log(n)+n^{2}kTm_{h}\log(n)+kT^{3}\right]\right) . Appendix E The proof of Proposition 1 Proof. We prove symmetry and positive semi-definite for the two kernel classes in Definitions 1 – 2 . Non-separable kernel (Definition 1 ): Denote \bm{a}_{\ell}:=\mathrm{vec}(\mathbf{A}_{\ell})\in\mathbb{R}^{T} (resp. \bm{a}:=\mathrm{vec}(\mathbf{A})\in\mathbb{R}^{T} ). The tensor-output kernel is \displaystyle\mathbf{K}(\bm{x},\bm{x}^{\prime})=\sum_{\ell=1}^{m}\sum_{j=1}^{t_{\ell}}\,\bm{a}_{\ell}\bm{a}_{\ell}^{\top}\,k_{\ell j}(\bm{x},\bm{x}^{\prime})\;,\qquad\bm{x},\bm{x}^{\prime}\in\mathcal{X}, (31) where each k_{\ell j} is a scalar positive semi-definite kernel. For any \bm{x},\bm{x}^{\prime}\in\mathcal{X} , we have \displaystyle\mathbf{K}(\bm{x},\bm{x}^{\prime})^{\top} \displaystyle=\sum_{\ell,j}\big(\bm{a}_{\ell}\bm{a}_{\ell}^{\top}\big)^{\top}\,k_{\ell j}(\bm{x},\bm{x}^{\prime})=\sum_{\ell,j}\bm{a}_{\ell}\bm{a}_{\ell}^{\top}\,k_{\ell j}(\bm{x},\bm{x}^{\prime}) \displaystyle=\sum_{\ell,j}\bm{a}_{\ell}\bm{a}_{\ell}^{\top}\,k_{\ell j}(\bm{x}^{\prime},\bm{x})=\mathbf{K}(\bm{x}^{\prime},\bm{x}), This shows that the full tensor-output kernel \mathbf{K} is symmetric. Let \{\bm{x}_{i}\}_{i=1}^{n}\subset\mathcal{X} and \{\bm{y}_{i}\}_{i=1}^{n}\subset\mathbb{R}^{T} be arbitrary. Then, we have \displaystyle\sum_{i,j=1}^{n}\bm{y}_{i}^{\top}\mathbf{K}(\bm{x}_{i},\bm{x}_{j})\bm{y}_{j} \displaystyle=\sum_{\ell,j}\sum_{i,j}\bm{y}_{i}^{\top}\big(\bm{a}_{\ell}\bm{a}_{\ell}^{\top}\big)\bm{y}_{j}\,k_{\ell j}(\bm{x}_{i},\bm{x}_{j}) \displaystyle=\sum_{\ell,j}\sum_{i,j}s_{\ell j,i}\,k_{\ell j}(\bm{x}_{i},\bm{x}_{j})\,s_{\ell j,j}, (32) where s_{\ell j,i}:=\bm{a}_{\ell}^{\top}\bm{y}_{i}\in\mathbb{R} . For each fixed (\ell,j) , the matrix \big[k_{\ell j}(\bm{x}_{i},\bm{x}_{j})\big]_{i,j=1}^{n} is positive semi-definite, so \sum_{i,j}s_{\ell j,i}\,k_{\ell j}(\bm{x}_{i},\bm{x}_{j})\,s_{\ell j,j}\geq 0 . Summing over (\ell,j) preserves nonnegativity, hence the Gram matrix induced by \mathbf{K} is positive semi-definite. Separable kernel (Definition 2 ): The kernel is \displaystyle\mathbf{K}(\bm{x},\bm{x}^{\prime})=\bm{a}\,\bm{a}^{\top}\,k(\bm{x},\bm{x}^{\prime})\;,\qquad\bm{x},\bm{x}^{\prime}\in\mathcal{X}, (33) where k is a scalar positive semi-definite kernel. Since \big(\bm{a}\bm{a}^{\top}\big)^{\top}=\bm{a}\bm{a}^{\top} and k(\bm{x},\bm{x}^{\prime})=k(\bm{x}^{\prime},\bm{x}) , we have \mathbf{K}(\bm{x},\bm{x}^{\prime})^{\top}=\mathbf{K}(\bm{x}^{\prime},\bm{x}) . For arbitrary \{\bm{x}_{i}\}_{i=1}^{n} and \{\bm{y}_{i}\}_{i=1}^{n} , \sum_{i,j=1}^{n}\bm{y}_{i}^{\top}\mathbf{K}(\bm{x}_{i},\bm{x}_{j})\bm{y}_{j}=\sum_{i,j}\big(\bm{a}^{\top}\bm{y}_{i}\big)\,k(\bm{x}_{i},\bm{x}_{j})\,\big(\bm{a}^{\top}\bm{y}_{j}\big)\geq 0 , because the Gram matrix \big[k(\bm{x}_{i},\bm{x}_{j})\big] is positive semi-definite. Therefore, both kernel classes are symmetric and generate positive semi-definite Gram matrices for any finite set of inputs, i.e., they are valid tensor-output kernels on \mathcal{X} . ∎ Appendix F The proof of Lemma 1 Proof. First, for a tensor-output system \mathrm{vec}(\mathbf{f}(\bm{x})) following a TOGP defined in ( 3 ), denote the derivative field of \mathrm{vec}(\mathbf{f}(\bm{x})) to the j -coordinate element of \bm{x} as \bm{g}_{j}(\bm{x})\;:=\partial\mathrm{vec}(\mathbf{f}(\bm{x}))/\partial x_{j} , where \mathrm{vec}\big(\mathbf{f}(\bm{x})\big)\in\mathbb{R}^{T} and j\in\{1,\ldots,d\} . According to the derivative property of GP ( 33 ) , we have that \bm{g}_{j}(\bm{x})\in\mathbb{R}^{\top} is a multivariate-output GP with mean \hat{\bm{\mu}}^{\nabla}_{n}(x_{j})\;:=\;\frac{\partial}{\partial x_{j}}\,{\bm{\mu}}_{n}(\bm{x}) and covariance \hat{\mathbf{K}}^{\nabla}_{n}(x_{j},x^{\prime}_{j})\;:=\;\mathrm{Cov}\!\left(\mathbf{g}_{j}(\bm{x}),\mathbf{g}_{j}(\bm{x}^{\prime})\right)=\frac{\partial^{2}}{\partial x_{j}\,\partial x^{\prime}_{j}}\sigma^{2}\mathbf{K}(\bm{x},\bm{x}^{\prime}) . At round n+1 , the observed data is denoted as \mathbf{X}_{n} and \bm{Y}_{n} , then we have the posterior distribution of \bm{g}_{j}(\bm{x}) is a T -dimensional Gaussian with mean and covariance \displaystyle\hat{\bm{\mu}}^{\nabla}_{n}(x_{j})=\frac{\partial\hat{\bm{\mu}}_{n}(\bm{x})}{\partial x_{j}};\quad\hat{\mathbf{K}}^{\nabla}_{n}(x_{j},x^{\prime}_{j})=\frac{\partial^{2}\hat{\mathbf{K}}_{n}(\bm{x},\bm{x})}{\partial x_{j}\,\partial x^{\prime}_{j}}. (34) It is easy to verify that \hat{\mathbf{K}}^{\nabla}_{n}(x_{j},x^{\prime}_{j}) is positive semi-definite for every \bm{x} . For any fixed \bm{x}\in\mathcal{X} , given \mathbf{X}_{n} and \bm{Y}_{n} , the random vector \displaystyle\mathbf{g}_{j}(\bm{x})-\hat{\bm{\mu}}^{\nabla}_{n}(x_{j})\sim\mathcal{N}\!\big(\mathbf{0},\hat{\mathbf{K}}^{\nabla}_{n}(\bm{x},\bm{x};j)\big). (35) Applying the Gaussian Lipschitz concentration (Proposition 2.5.2 and Theorem 5.2.2 in 31 ) to the norm \|\cdot\|_{2} yields, for all t>0 , \displaystyle\Pr\!\left(\left\|\mathbf{g}_{j}(\bm{x})-\hat{\bm{\mu}}^{\nabla}_{n}(x_{j})\right\|\;\geq\;\sqrt{\mathrm{tr}\!\big(\hat{\mathbf{K}}^{\nabla}_{n}(x_{j},x_{j})\big)}\;+\;t\right)\;\leq\;\exp\!\left(-\frac{t^{2}}{2\,\lambda_{\max}^{(n)}(x_{j})}\right), (36) where \lambda_{\max}^{(n)}(\bm{x};j) is the largest eigenvalue of \hat{\mathbf{K}}^{\nabla}_{n}(\bm{x},\bm{x};j) . Let \mathcal{D}_{M}=\{\bm{x}_{1},\ldots,\bm{x}_{M}\}\subset\mathcal{X} be any finite discretization. Using ( 36 ) with t(\bm{x})=\sqrt{2\,\lambda_{\max}^{(n)}(x_{j})\,\log(M/\delta)} , and applying the union bound, we obtain with probability at least 1-\delta , \displaystyle\left\|\mathbf{g}_{j}(\bm{x})-\hat{\bm{\mu}}^{\nabla}_{n}(x_{j})\right\|\;\leq\;\sqrt{\mathrm{tr}\!\big(\hat{\mathbf{K}}^{\nabla}_{n}(x_{j},x_{j})\big)}\;+\;\sqrt{2\,\lambda_{\max}^{(n)}(x_{j})\,\log(M/\delta)},\qquad\forall\,\bm{x}\in\mathcal{D}_{M}. (37) Let C_{\nabla}\;:=\;\sup_{\bm{x}\in\mathcal{X}}\sqrt{\mathrm{tr}\!\big(\hat{\mathbf{K}}^{\nabla}_{n}(x_{j},x_{j})\big)} and \Lambda_{\nabla}:=\sup_{\bm{x}\in\mathcal{X}}\lambda^{(n)}_{max}(x_{j}) , then ( 37 ) implies that, with probability at least 1-\delta , \displaystyle\left\|\mathbf{g}_{j}(\bm{x})\right\|\;\leq\;\left\|\hat{\bm{\mu}}^{\nabla}_{n}(x_{j})\right\|\;+\;C_{\nabla}\;+\;\sqrt{2\,\Lambda_{\nabla}\,\log(M/\delta)},\qquad\forall\,\bm{x}\in\mathcal{D}_{M}. (38) Assume the kernel is sufficiently smooth so that \mathbf{g}_{j}(\cdot) has almost surely Lipschitz sample paths. Then there exist absolute constants a,b>0 (depending on the Lipschitz modulus and a covering-number bound of \mathcal{X} ) such that for any L^{\prime}>0 , \displaystyle\Pr\!\left(\sup_{\bm{x}\in\mathcal{X}}\left\|\mathbf{g}_{j}(\bm{x})\right\|\;>\;L^{\prime}+C_{\nabla}\right)\;\leq\;a\,\exp\!\left(-\frac{(L^{\prime})^{2}}{b^{2}}\right). (39) This follows by combining the net bound ( 38 ) with a standard chaining argument to pass from a finite net to the full domain; the Gaussian tail is preserved with a possible adjustment of absolute constants into a,b . ∎ Appendix G The proof of Theorem 1 Proof. The proof consists of two main parts. We first establish a concentration inequality for \mathrm{vec}(\mathbf{f}(\bm{x})) for any \bm{x}\in\mathcal{X} , and then use this result to derive an upper bound for the regret. Part 1. Concentration inequality. We begin by proving a concentration inequality for \mathrm{vec}(\mathbf{f}(\bm{x})) evaluation on a discrete set of points in the domain \mathcal{X} . We then extend the result to neighborhoods of these discrete points, and ultimately to the entire space \mathcal{X} . We first prove a basic concentration inequality for a general T -dimensional Gaussian distribution, i.e., \bm{Z}\sim\mathcal{N}(\bm{\mu},\mathbf{K}) . If we define \bm{U}=\bm{Z}-\bm{\mu} and set another T -dimensional standard Gaussian distribution \bm{V}\sim\mathcal{N}(0,\mathbf{I}_{T}) , we can obtain \displaystyle\bm{U}\overset{d}{=}\mathbf{K}^{1/2}\bm{V},\quad\|\bm{U}\|=\|\mathbf{K}^{1/2}\bm{V}\|. Define the function f(\bm{U})\triangleq\|\mathbf{K}^{1/2}\bm{V}\| . For any \bm{U},\bm{U}^{\prime} , we have \displaystyle|f(\bm{U})-f(\bm{U}^{\prime})|\leq\|\mathbf{K}^{1/2}(\bm{U}-\bm{U}^{\prime})\|\leq\|\mathbf{K}^{1/2}\|_{op}\,\|\bm{U}-\bm{U}^{\prime}\|=\sqrt{\lambda_{\max}(\mathbf{K})}\,\|\bm{U}-\bm{U}^{\prime}\|, where \lambda_{\max}(\mathbf{K}) is the maximum eigenvalue of \mathbf{K} . Therefore f is a Lipschitz function with constant L=\sqrt{\lambda_{\max}(\mathbf{K})} . According to Proposition 2.5.2 and Theorem 5.2.2 in 31 , we have the following concentration inequality for a Lipschitz function of a standard Gaussian distribution: \displaystyle\Pr\big(f(\bm{U})\geq\mathbb{E}[f(\bm{U})]+t\big)\leq\exp\Big(-\frac{t^{2}}{2L^{2}}\Big). Substituting f and L , we obtain \displaystyle\Pr\big(\|\bm{Z}-\bm{\mu}\|\geq\mathbb{E}[\|\bm{Z}-\bm{\mu}\|]+t\big)\leq\exp\Big(-\frac{t^{2}}{2\lambda_{\max}(\mathbf{K})}\Big). Since \displaystyle\mathbb{E}[\|\bm{Z}-\bm{\mu}\|]\leq\sqrt{\mathbb{E}[\|\bm{Z}-\bm{\mu}\|^{2}]}=\sqrt{\mathrm{tr}(\mathbf{K})}, we get the final result for a general Gaussian distribution: \displaystyle\Pr\!\left(\|\bm{Z}-\bm{\mu}\|\geq\sqrt{\mathrm{tr}(\mathbf{K})}+t\right)\leq\exp\!\Big(-\tfrac{t^{2}}{2\lambda_{\max}(\mathbf{K})}\Big). (40) Define the discrete set \mathcal{D}_{M}=\{\bm{x}_{1},\dots,\bm{x}_{M}\}\subset\mathcal{X} . According to the above concentration inequality, we have \displaystyle\Pr\!\left(\|\mathrm{vec}(\mathbf{f}(\bm{x}))-\hat{\bm{\mu}}_{n}(\bm{x})\|>\sqrt{\mathrm{tr}(\hat{\mathbf{K}}_{n}(\bm{x},\bm{x}))}+z\right)\leq\exp\!\Big(-\tfrac{z^{2}}{2\lambda^{(n)}_{\max}(\bm{x})}\Big),\quad\forall\bm{x}\in\mathcal{D}_{M}, where \lambda^{(n)}_{\max}(\bm{x}) is the maximum eigenvalue of \hat{\mathbf{K}}_{n}(\bm{x},\bm{x}) . By setting z=\sqrt{2\lambda^{(n)}_{\max}(\bm{x})\log\frac{M}{\delta}} , we obtain \displaystyle\Pr\!\left(\|\mathrm{vec}(\mathbf{f}(\bm{x}))-\hat{\bm{\mu}}_{n}(\bm{x})\|\leq\beta_{n}\sqrt{\lambda^{(n)}_{\max}(\bm{x})}\right)\geq 1-\delta,\quad\forall\bm{x}\in\mathcal{D}_{M}, (41) where \beta_{n}=\sqrt{\sup_{\bm{x}\in\mathcal{X}}\frac{\mathrm{tr}(\hat{\mathbf{K}}_{n}(\bm{x},\bm{x}))}{\lambda^{(n)}_{\max}(\bm{x})}}+\sqrt{2\log\frac{M}{\delta}}=\sqrt{C_{n}}+\sqrt{2\log\frac{M}{\delta}} . From Lemma 1 , we obtain that \|\mathrm{vec}(\mathbf{f}(\bm{x}))-\mathrm{vec}(\mathbf{f}(\bm{x}^{\prime}))\|\leq(L^{\prime}+C^{\nabla})\|\bm{x}-\bm{x}^{\prime}\|_{1} holds with probability at least 1-a\exp(-L^{\prime 2}/b^{2}) for all \bm{x},\bm{x}^{\prime}\in\mathcal{X} . Then, at round n , we set the size of \mathcal{D}_{M(n)} as (\tau_{n})^{d} , i.e., M(n)=(\tau_{n})^{d} . For \bm{x}\in\mathcal{D}_{M(n)} , we have \|\bm{x}-[\bm{x}]_{n}\|_{1}\leq\tfrac{rd}{\tau_{n}} , where [\bm{x}]_{n} is the closest point in \mathcal{D}_{M(n)} to \bm{x} . Using the above aligns, if we set L^{\prime}=b\sqrt{\log\frac{da}{\delta}} , we obtain \displaystyle\|\mathrm{vec}(\mathbf{f}(\bm{x}))-\mathrm{vec}(\mathbf{f}([\bm{x}]_{n}))\|\leq\Big(b\sqrt{\log\tfrac{da}{\delta}}+C^{\nabla}\Big)\|\bm{x}-[\bm{x}]_{n}\|_{1}\leq\Big(b\sqrt{\log\tfrac{da}{\delta}}+C^{\nabla}\Big)\frac{rd}{\tau_{n}}, with probability at least 1-\delta for all \bm{x}\in\mathcal{X} . Choosing \tau_{n}=rdn^{2}(b\sqrt{\log\frac{da}{\delta}}+C^{\nabla}) , we have \displaystyle\Pr\!\Big(\|\mathrm{vec}(\mathbf{f}(\bm{x}))-\mathrm{vec}(\mathbf{f}([\bm{x}]_{M}))\|\leq\tfrac{1}{n^{2}}\Big)\geq 1-\delta,\quad\forall\bm{x}\in\mathcal{X}. Combining the above results, we obtain \displaystyle\Pr\!\Big(\|\mathrm{vec}(\mathbf{f}(\bm{x}^{\star}))-\hat{\bm{\mu}}([\bm{x}^{\star}]_{n})\|\leq\beta_{n}\sqrt{\lambda_{\max}^{(n)}([\bm{x}^{\star}]_{n})}+\tfrac{1}{n^{2}}\Big)\geq 1-\delta, where [\bm{x}^{\star}]_{n} is the closest point in \mathcal{D}_{M(n)} to \bm{x}^{\star} , and \beta_{n}=\sqrt{C_{n}}+2d\log\!\Big(\tfrac{rdn^{2}(b\sqrt{\log(da/\delta)}+C^{\nabla})}{\delta}\Big) . Part 2. Regret bound. According to the Lipschitz property of h , we have \displaystyle r_{n}=h(\bm{x}^{\star})-h(\bm{x}_{n})\leq L\|\mathrm{vec}(\mathbf{f}(\bm{x}^{\star}))-\mathrm{vec}(\mathbf{f}(\bm{x}_{n}))\|, (42) where L>0 is the Lipschitz constant. Since \displaystyle\hat{\bm{\mu}}_{n-1}(\bm{x}_{n})+\beta_{n}\sqrt{\lambda_{\max}^{(n-1)}(\bm{x}_{n})}\geq\hat{\bm{\mu}}_{n-1}([\bm{x}^{\star}]_{n})+\beta_{n}\sqrt{\lambda_{\max}^{(n-1)}([\bm{x}^{\star}]_{n})}\geq\mathrm{vec}(\mathbf{f}(\bm{x}^{\star}))-\tfrac{1}{n^{2}}, we have \displaystyle r_{n}\leq L\Big(2\beta_{n}\sqrt{\lambda_{\max}^{(n-1)}(\bm{x}_{n})}+\tfrac{1}{n^{2}}\Big). (43) We first consider the first term: \displaystyle 4\beta_{n}^{2}\lambda_{\max}^{(n-1)}(\bm{x}_{n}) \displaystyle\leq 4\beta_{N}^{2}\eta\big(\eta^{-1}\lambda_{\max}^{(n-1)}(\bm{x}_{n})\big)\leq 4\beta_{N}^{2}\eta C_{2}\log\big(1+\eta^{-1}\lambda_{\max}^{(n-1)}(\bm{x}_{n})\big) \displaystyle\leq 4\beta_{N}^{2}\eta C_{2}\log\!\big|\mathbf{I}_{T}+\eta^{-1}\hat{\mathbf{K}}_{n-1}(\bm{x}_{n},\bm{x}_{n})\big|, where C_{2} is a constant. Define C_{1}=4\eta C_{2} . Then \displaystyle\sum_{n=1}^{N}4\beta_{n}^{2}\lambda_{\max}^{(n-1)}(\bm{x}_{n})\leq C_{1}N\beta_{N}^{2}\sum^{N}_{n=1}\log\!\big|\mathbf{I}_{T}+\eta^{-1}\hat{\mathbf{K}}_{n-1}(\bm{x}_{n},\bm{x}_{n})\big|\leq C_{1}N\beta_{N}^{2}\gamma_{N}(\mathbf{K},\eta), where the last inequality holds by the definition of \gamma_{N}(\mathbf{K},\eta) . Since \sum_{n=1}^{N}\tfrac{1}{n^{2}}\leq\tfrac{\pi^{2}}{6} , we have the final result: \displaystyle\sum_{n=1}^{N}r_{n}\leq L\Big(\sqrt{C_{1}N\gamma_{N}(\mathbf{K},\eta)}\,\beta_{N}+\tfrac{\pi^{2}}{6}\Big). (44) ∎ Appendix H The proof of Proposition 2 Proof. We start from the definition of the (maximum) information gain: \displaystyle\gamma_{n}(\mathbf{K},\eta)=\max_{\mathbf{X}_{n}}\;\frac{1}{2}\log\det\!\big(\mathbf{I}_{nT}+\eta^{-1}\sigma^{2}\,\mathbf{K}_{n}\big),\quad\mathbf{K}_{n}:=\big[\mathbf{K}(\bm{x}_{i},\bm{x}_{j})\big]_{i,j=1}^{n}\in\mathbb{R}^{nT\times nT}. (45) Under the separable kernel in Definition 2 , we have \displaystyle\mathbf{K}(\bm{x},\bm{x}^{\prime})=\big(\mathrm{vec}(\mathbf{A})\mathrm{vec}(\mathbf{A})^{\top}\big)\,k(\bm{x},\bm{x}^{\prime})=:\mathbf{B}\,k(\bm{x},\bm{x}^{\prime}), (46) where \mathbf{B}:=\mathrm{vec}(\mathbf{A})\mathrm{vec}(\mathbf{A})^{\top}\in\mathbb{R}^{T\times T} . Then, the Gram matrix factorizes as a Kronecker product \displaystyle\mathbf{K}_{n}=\mathbf{K}_{x}\otimes\mathbf{B},\qquad\mathbf{K}_{x}=[k(\bm{x}_{i},\bm{x}_{j})]_{i,j=1}^{n}\in\mathbb{R}^{n\times n}. (47) Let \{\alpha_{i}\}_{i=1}^{n} be the eigenvalues of \mathbf{K}_{x} and \{\beta_{j}\}_{j=1}^{T} be the eigenvalues of \mathbf{B} . By the spectral property of the Kronecker product, the eigenvalues of \mathbf{K}_{x}\otimes\mathbf{B} are \{\alpha_{i}\beta_{j}:i=1,\ldots,n,\;j=1,\ldots,T\} . Therefore, we have \displaystyle\log\det\!\big(\mathbf{I}_{nT}+\eta^{-1}\sigma^{2}(\mathbf{K}_{x}\otimes\mathbf{B})\big)=\sum_{i=1}^{n}\sum_{j=1}^{T}\log\!\big(1+c\,\alpha_{i}\,\beta_{j}\big),\qquad c:=\eta^{-1}\sigma^{2}. (48) For each fixed i , the function u\mapsto\log(1+c\,\alpha_{i}\,u) is non-decreasing for u\geq 0 , hence \displaystyle\sum_{j=1}^{T}\log\!\big(1+c\,\alpha_{i}\,\beta_{j}\big)=\sum_{j:\,\alpha_{j}>0}\log\!\big(1+c\,\alpha_{i}\,\beta_{j}\big)\;\leq\;T\cdot\log\!\big(1+c\,\alpha_{i}\,\beta_{\max}\big), (49) where \beta_{\max}:=\max_{j}\beta_{j} . Summing over i=1,\ldots,n and multiplying by 1/2 gives \displaystyle\gamma_{n}(\mathbf{K},\eta)\;\leq\;\frac{T}{2}\sum_{i=1}^{n}\log\!\big(1+c\,\beta_{\max}\,\lambda_{i}\big)\;=\;T\cdot\gamma_{n}\!\big(k^{\sharp},\eta\big), (50) where k^{\sharp}:=\beta_{\max}\,k is simply a rescaled version of k . Since rescaling by a positive constant does not change the asymptotic order of the information gain, we obtain the general comparison bound \displaystyle\gamma_{n}(\mathbf{K},\eta)\;\leq\;T\cdot\gamma_{n}(k,\eta). In our specific setting, the tightest bound is \gamma_{n}(\mathbf{K},\eta)=\mathcal{O}(T\gamma_{n}(k,\eta)) . Finally, we substitute known results for the scalar kernel k : (i) If k is the Gaussian (squared exponential) kernel in d dimensions, then \gamma_{n}(k,\eta)=\mathcal{O}\!\big((\log n)^{d+1}\big) , which gives \gamma_{n}(\mathbf{K},\eta)=\mathcal{O}\!\big(T(\log n)^{d+1}\big) . (ii) If k is a Matérn kernel with smoothness parameter \nu>1 , then \gamma_{n}(k,\eta)=\mathcal{O}\!\Big(n^{\frac{d(d+1)}{2\nu+d(d+1)}}\log n\Big) , which gives \gamma_{n}(\mathbf{K},\eta)=\mathcal{O}\!\Big(T\,n^{\frac{d(d+1)}{2\nu+d(d+1)}}\log n\Big) . ∎ Appendix I The proof of Theorem 2 Denote \tilde{h}(\bm{x},\bm{\lambda})=H_{f}\tilde{\bm{f}}(\bm{x},\bm{\lambda}) , then we have \displaystyle\tilde{h}(\bm{x}^{\star},\bm{\lambda}^{\star})-\tilde{h}(\bm{x}_{n},\bm{\lambda}_{n}) \displaystyle=\left[\tilde{h}(\bm{x}^{\star},\bm{\lambda}^{\star})-\tilde{h}(\bm{x}_{n},\bm{\lambda}^{\star})\right]+\left[\tilde{h}(\bm{x}_{n},\bm{\lambda}^{\star})-\tilde{h}(\bm{x}_{n},\bm{\lambda}_{n})\right] \displaystyle=r_{1n}+r_{2n}. For the first item, according to the Cauchy-Schwarz inequality, we have \displaystyle H_{f}\tilde{\bm{f}}(\bm{x},\bm{\lambda})-H_{f}\tilde{\bm{\mu}}_{n}(\bm{x},\bm{\lambda})\leq H\|\tilde{\bm{f}}(\bm{x},\bm{\lambda})-\tilde{\bm{\mu}}_{n}(\bm{x},\bm{\lambda})\|. (51) Similar to the proof of Theorem 1 , we provide the following lemma. Lemma 2 . Under Assumption 1 – 3 , suppose the noise vectors \big\{vec(\bm{\varepsilon}_{i})\big\}_{i\geq 1} are independently and identically distributed in N(0,\sigma^{2}\mathbf{I}_{k}) . Then, for any \delta\in(0,1] , with probability at least 1-\delta , \|\tilde{\bm{f}}(\bm{x},\bm{\lambda})-\tilde{\bm{\mu}}_{n}(\bm{x},\bm{\lambda})\|_{2}\leq\tilde{\beta}_{n}\|\tilde{\mathbf{K}}_{n}(\bm{x},\bm{x};\bm{\lambda},\bm{\lambda})\|^{1/2} holds uniformly over all \bm{x}\in\mathcal{X} and \bm{\lambda}\in\Lambda and i\geq 1 , where \beta_{n}=\sqrt{\tilde{C}_{n}}+2d\log(\frac{rdn^{2}(b\sqrt{\log(da/\delta)}+\tilde{C}_{\nabla})}{l}{\delta}) , \tilde{C}_{n}=\sup_{\bm{x}\in\mathcal{X}}\frac{tr(\tilde{\mathbf{K}}_{n}(\bm{x},\bm{x};\bm{\lambda}^{\star}_{n},\bm{\lambda}^{\star}_{n})))}{\lambda^{(n)}_{max}(\bm{x},\bm{\lambda}^{\star}_{n})} , and \tilde{C}_{\nabla}=\sup_{\bm{x}\in\mathcal{X}}\sqrt{\mathrm{tr}(\tilde{\mathbf{K}}_{n}^{\nabla}(x_{j},x_{j}))} . From Lemma 2 and ( 51 ), we have \displaystyle H_{f}\tilde{\bm{f}}(\bm{x},\bm{\lambda})-H_{f}\tilde{\bm{\mu}}_{n}(\bm{x},\bm{\lambda})\leq H\|\tilde{\bm{f}}(\bm{x},\bm{\lambda})-\tilde{\bm{\mu}}_{n}(\bm{x},\bm{\lambda})\|\leq H\tilde{\beta}_{n}\|\tilde{\mathbf{K}}_{n}(\bm{x},\bm{x};\bm{\lambda},\bm{\lambda})\|^{1/2}. Then, we have \displaystyle r_{1n} \displaystyle=\tilde{h}(\bm{x}^{\star},\bm{\lambda}^{\star})-\tilde{h}(\bm{x}_{n},\bm{\lambda}^{\star}) \displaystyle\leq H_{f}(\tilde{\bm{\mu}}_{n}(\bm{x}^{\star},\bm{\lambda}^{\star}))+H\tilde{\beta}_{n}\|\tilde{\mathbf{K}}_{n-1}(\bm{x}^{\star},\bm{x}^{\star})\|^{1/2}-H_{f}(\tilde{\bm{f}}(\bm{x}_{n},\bm{\lambda}^{\star})) \displaystyle\leq 2H\tilde{\beta}_{n-1}\|\tilde{\mathbf{K}}_{n-1}(\bm{x}_{n},\bm{x}_{n};\bm{\lambda}^{\star},\bm{\lambda}^{\star})\|^{1/2}. Similar to Theorem 1 , we obtain \displaystyle R_{1N} \displaystyle:=\sum_{n=1}^{N}r_{1n}\leqslant 2H\tilde{\beta}_{n-1}\|\tilde{\mathbf{K}}_{n-1}(\bm{x}_{n},\bm{x}_{n};\bm{\lambda}^{\star},\bm{\lambda}^{\star})\|^{1/2} \displaystyle\leq H\left(\sqrt{C_{3}N\gamma_{N}(\tilde{\mathbf{K}},\eta)}\,\tilde{\beta}_{N}+\tfrac{\pi^{2}}{6}\right), where C_{3}>0 is a constant. For the second item, followed in 2 , we have \displaystyle R_{2N}\leq H\sqrt{C_{4}TN\tilde{\gamma}_{n}(\tilde{\mathbf{K}},\eta)}\tilde{\rho}_{N}, where C_{4}>0 is a constant. Then we have the cumulative regret over N rounds is bounded by \displaystyle r_{n} \displaystyle\leq r_{1n}+r_{2n} \displaystyle\leq H\left(\sqrt{C_{3}\gamma_{N}(\tilde{\mathbf{K}},\eta)N}\,\tilde{\beta}_{N}+\tfrac{\pi^{2}}{6}+\sqrt{C_{4}TN\tilde{\gamma}_{N}\big(\tilde{\mathbf{K}},\eta)}\tilde{\rho}_{N}\right). Appendix J The proof of Proposition 3 Proof. Based on the definition of the (maximum) information gain, we have \displaystyle\gamma_{n}(\tilde{\mathbf{K}},\eta)=\max_{\mathbf{X}_{n}}\;\frac{1}{2}\log\det\!\big(\mathbf{I}_{m}+c\,\tilde{\mathbf{K}}_{n}\big),\qquad c:=\eta^{-1}\sigma^{2}, (52) where the Gram matrix takes the form \tilde{\mathbf{K}}_{n}=\mathbf{E}\mathbf{K}_{n}\mathbf{E}^{\top} and \mathbf{K}_{n}=\mathbf{B}\otimes\mathbf{K}_{x} , with \mathbf{K}_{x}=[k(\bm{x}_{i},\bm{x}_{j})]_{i,j=1}^{n}\in\mathbb{R}^{n\times n} , \mathbf{B}=\mathrm{vec}(\mathbf{A})\mathrm{vec}(\mathbf{A})^{\top}\in\mathbb{R}^{T\times T} . By Sylvester’s identity, we have \displaystyle\det\big(\mathbf{I}_{nk}+c\,\mathbf{E}_{n}\mathbf{K}_{n}\mathbf{E}_{n}^{\top}\big)=\det\big(\mathbf{I}_{nT}+c\,\mathbf{K}_{n}^{1/2}\mathbf{E}_{n}^{\top}\mathbf{E}_{n}\mathbf{K}_{n}^{1/2}\big). (53) Since \mathbf{E}_{n} selects rows, 0\preceq E_{n}^{\top}E_{n}\preceq\mathbf{I}_{nT} , hence \displaystyle\log\det\!\big(\mathbf{I}_{nk}+c\,\mathbf{E}_{n}\mathbf{K}_{n}\mathbf{E}_{n}^{\top}\big) \displaystyle=\log\det\!\big(\mathbf{I}_{nT}+c\,\mathbf{K}_{n}^{1/2}\mathbf{E}_{n}^{\top}\mathbf{E}_{n}\mathbf{K}_{n}^{1/2}\big) \displaystyle\leq\log\det\!\big(\mathbf{I}_{nT}+c\,\mathbf{K}_{n}\big). (54) Then, followed in Proposition 1 , we have \displaystyle\gamma_{n}(\tilde{\mathbf{K}}_{n},\eta)=\mathcal{O}\big(T(\log n)^{d+1}\big)\ \text{for the Gaussian kernel}, (55) \displaystyle\gamma_{n}(\tilde{\mathbf{K}}_{n},\eta)=\mathcal{O}\!\Big(Tn^{\frac{d(d+1)}{2\nu+d(d+1)}}\log n\Big)\ \text{for the Mat\'{e}rn kernel}. (56) From ( 54 ), we also obtain that \displaystyle\tilde{\gamma}_{n}(\tilde{\mathbf{K}}_{n},\eta)=\mathcal{O}\big(T(\log n)^{d+1}\big)\ \text{for the Gaussian kernel}, (57) \displaystyle\tilde{\gamma}_{n}(\tilde{\mathbf{K}}_{n},\eta)=\mathcal{O}\!\Big(Tn^{\frac{d(d+1)}{2\nu+d(d+1)}}\log n\Big)\ \text{for the Mat\'{e}rn kernel}. (58) ∎ Appendix K Detailed settings of the experiments K.1 Detailed settings of synthetic experiments The setting of simulations are as follows: • Compute resources: All experiments were run on a Windows 10 Pro (Build 19045) desktop with an Intel Core i9-7900X CPU (3.10 GHz) and 32 GB RAM. • Kernel setting: We use the Matérn kernel function with the smoothing parameter \nu=5/2 as the input kernel for different GPs. • Data setting: For the GP prediction, we generate n_{train}=10d training samples for estimating hyperparameters and n_{test}=5d testing samples for predicting. In the BO and CBBO framework, we generate n_{0}=5d initial design points based on Latin Hypercube Sampling (LHS), and N=10d sequential design points. • Criteria: To compare the GPs prediction performance of different methods, we use the following criteria: (1) Negative Log-Likelihood (NLL): It measures how well a probabilistic model fits the observed data. For given data \mathbf{X}_{n} and \bm{Y}_{n} , the NLL is defined as \text{NLL}=\frac{1}{2}\log(\tau^{2}\mathbf{K}_{n}+\sigma^{2}\mathbf{I}_{nT})+\frac{1}{2}\bm{Y}_{n}^{\top}(\tau^{2}\mathbf{K}_{n}+\sigma^{2}\mathbf{I}_{nT})^{-1}\bm{Y}_{n} . (2) Mean Absolute Error (MAE): \text{MAE}=\frac{1}{n_{test}}\sum_{i=1}^{n_{test}}\|\frac{\mathbf{y}_{i}-\hat{\mathbf{y}}_{i}}{\mathbf{y}_{i}}\| . (3) Covariance Operator Norm ( \|Cov\| ): \|\hat{\mathbf{K}}_{n}\|=\sup_{\|\bm{v}\|=1}\|\hat{\mathbf{K}}_{n}\| . For the BO framework, we use the the mean squared error of inputs ( \text{MSE}_{x} ) and the mean absolute error of outputs \text{MAE}_{y} to compare the optimization performance of different methods. Here \text{MSE}_{x}=\|\bm{x}^{\star}-\bm{x}^{\star}_{N}\|^{2} , and \text{MAE}_{y}=\|\frac{\mathbf{f}^{\star}-\mathbf{f}^{\star}_{N}}{\mathbf{f}^{\star}}\| over N rounds. For the CBBO framework, we add the Acc criterion to compare the match between the optimal super arm and the super arm chosen over N rounds, that is, Acc=\mathbb{I}_{\bm{\lambda}^{\star}=\bm{\lambda}_{N}}/k , where \mathbb{I} is a indictor function. K.2 Detailed settings of case studies The detailed datasets of case studies are as follows: Chemistry reaction (CHEM): Reaction optimization is fundamental to synthetic chemistry, from improving yields in industrial processes to selecting reaction conditions for drug candidate synthesis. According to 35 , we aim to evaluate the reaction parameters ( x_{1} : concentration, x_{2} : temperature) to improve the experimental yields ( \mathbf{y}:4\times 3\times 3 ) of palladium-catalysed direct arylation reaction under varying bases (Mode 1), ligands (Mode 2), and solvents (Mode 3). PS/PAN material (MAT): Electrospun polystyrene/polyacrylonitrile (PS/PAN) materials are commonly used as potential oil sorbents for marine oil spill remediation. From 43 , we aim to optimize the fabrication parameters of PS/PAN materials, including spinneret speed ( x_{1} ), collector distance ( x_{2} ), applied voltage ( x_{3} ), and fiber diameter ( x_{4} ), to improve their oil absorption capacity ( \mathbf{y}:5\times 4\times 4 ) under varying PS content (Mode 1), mass fraction (Mode 2), and SiO 2 content (Mode 3). 3D printing (PRINT): Material extrusion-based three-dimensional printed products have been widely used in aerospace, automotive, and other fields. Following 49 , we focus on selecting appropriate process parameters ( x_{1} : layer thickness, x_{2} : platform temperature, x_{3} : nozzle temperature, x_{4} : infill density, and x_{5} : printing speed) to reduce variations in part quality ( \mathbf{y}:3\times 4\times 3 ) caused by different printer nozzles (Mode 1) and printing geometries (Mode 2). The quality (Mode 3) is evaluated in terms of compression deformation, compressive strength, and the printing cost. Renewable energy (REEN): Climate change affects the availability and reliability of renewable energy sources such as wind, solar, and hydropower. We employ the operational energy dataset from the Copernicus Climate Change Service ( https://cds.climate.copernicus.eu/datasets/sis-energy-derived-reanalysis?tab=overview ) to explore the climate conditions that are most beneficial to renewable energy generation in various European nations. The climate-related variables, used as input features, include air temperature ( x_{1} ), precipitation ( x_{2} ), surface incoming solar radiation ( x_{3} ), wind speed at 10 meters ( x_{4} ) and 100 meters ( x_{5} ), and mean sea level pressure ( x_{6} ). The energy-related indicators ( \mathbf{y}:10\times 2) collected from ten European countries (Mode 1), used as outputs, include the capacity factor ratio of solar photovoltaic power generation and wind power generation onshore (Mode 2). Appendix L The comparison of computational complexity for baselines To provide a clearer comparison, we summarize the computational complexity of GP training, BO, and CBBO for the baseline methods sMTGP, MLGP, and MVGP, together with our proposed method, in the table below. Table 5: The computational complexity of different methods for GP training, BO, and CBBO. Task Method Computational complexity GP Training TOGP \mathcal{O}\big((n^{3}T^{3}+n^{2}T^{2}m_{h})\log n\big) sMTGP \mathcal{O}\big((n^{3}+\sum_{l=1}^{m}t_{l}^{3}+n^{2}m_{h}+\sum_{l=1}^{m}t_{l}^{2}m_{hl})\log n\big) MLGP \mathcal{O}\big((n^{3}+\sum_{l=1}^{m}t_{l}^{3}+n^{2}m_{h}+\sum_{l=1}^{m}t_{l}^{2}m_{hl})\log n\big) MVGP \mathcal{O}\big((n^{3}+T^{3}+n^{2}m_{h1}+T^{2}m_{h2})\log n\big) BO (Round n ) TOGP \mathcal{O}\big((n^{3}T^{3}+n^{2}T^{2}m_{h})\log n\big) sMTGP \mathcal{O}\big((n^{3}+\sum_{l=1}^{m}t_{l}^{3}+n^{2}m_{h}+\sum_{l=1}^{m}t_{l}^{2}m_{hl})\log n\big) MLGP \mathcal{O}\big((n^{3}+\sum_{l=1}^{m}t_{l}^{3}+n^{2}m_{h}+\sum_{l=1}^{m}t_{l}^{2}m_{hl})\log n\big) MVGP \mathcal{O}\big((n^{3}+T^{3}+n^{2}m_{h1}+T^{2}m_{h2})\log n\big) CBBO (Round n ) TOGP \mathcal{O}\big((n^{3}k^{3}+n^{2}kTm_{h})\log n+kT^{3}\big) sMTGP \mathcal{O}\big((n^{3}+k^{3}+n^{2}m_{h}+k\sum_{l=1}^{m}t_{l}m_{hl})\log n+k\sum_{l=1}^{m}t_{l}^{3}\big) MLGP \mathcal{O}\big((n^{3}+k^{3}+n^{2}m_{h}+k\sum_{l=1}^{m}t_{l}m_{hl})\log n+k\sum_{l=1}^{m}t_{l}^{3}\big) MVGP \mathcal{O}\big((n^{3}+T^{3}+n^{2}m_{h1}+kTm_{h2})\log n+kT^{3}\big) Here m_{h} , m_{h1} , m_{h2} , and m_{hl} for l=1,\cdots,m denote the numbers of hyperparameters for the corresponding methods. Furthermore, we report the empirical computational time for GP training across all methods under the three experimental settings. The results are summarized below. Table 6: The runtime (s) of different methods for GP training in the three synthetic settings. TOGP sMTGP MLGP MVGP Setting (1) 266.04 27.26 30.57 6.50 Setting (2) 69.85 16.08 21.99 1.31 Setting (3) 900.13 851.34 891.73 769.50 We further report the empirical running time of BO and CBBO under all baseline methods. The results are summarized in the table below. Table 7: The runtime (s) of different methods for BO and CBBO in the three synthetic settings. Setting (1) Setting (2) Setting (3) Method/Task BO CBBO BO CBBO BO CBBO TOBO/TOCBBO 6968.25 8017.08 1588.53 2348.16 6035.61 11699.09 sMTGP-UCB 1516.31 953.82 117.78 179.11 5291.26 9436.90 MLGP-UCB 1545.41 981.86 133.93 185.49 5452.90 9696.60 MVGP-UCB 340.44 437.29 14.86 20.76 3006.97 3199.47 TOGP-RS 6176.84 7990.44 1573.36 2338.97 5786.02 11501.01 sMTGP-RS 1503.24 939.27 106.93 164.95 5273.84 9421.08 MLGP-RS 1530.32 971.25 109.14 180.70 5252.32 9431.96 MVGP-RS 334.79 386.86 7.70 6.70 2997.75 3116.23 Finally, we provide the prediction and optimization performance of TOGP based on the Nystrm̈ low-rank approximation (SVD-TOGP) in Remark 3 under the three synthetic settings. The results are summarized below. Table 8: Summary of TOGP and SVD-TOGP performance for GP training, BO and CBBO in the three synthetic settings. Setting (1) Setting (2) Setting (3) Task Criterion SVD-TOGP TOGP SVD-TOGP TOGP SVD-TOGP TOGP GP Training NLL 557.09 503.00 -18.39 -18.10 -3778.74 -3923.10 MAE 0.1756 0.1571 0.1099 0.1052 0.1436 0.1372 \|Cov\| 3.9627 2.0200 0.6261 0.0400 0.0881 2.8200 Time (s) 21.80 266.04 10.83 69.85 436.17 900.13 BO \text{MSE}_{x} 0.0001 0.0000 0.0003 0.0003 0.0002 0.0001 \text{MAE}_{y} 0.0041 0.0008 0.0356 0.0350 0.0051 0.0050 Ins Regret 0.0040 0.0001 0.0002 0.0002 0.0402 0.0302 Time (s) 831.02 6968.25 162.78 1588.53 3604.66 6035.61 CBBO \text{MSE}_{x} 0.0024 0.0023 0.0000 0.0000 0.0035 0.0021 \text{MAE}_{y} 0.0180 0.0172 0.0000 0.0000 0.0246 0.0145 Acc 1 1 1 1 1 1 Ins Regret 1.0944 0.9807 0.0000 0.0000 1.8571 1.4406 Time (s) 655.83 8017.08 134.22 2348.16 4446.12 11699.09 Appendix M Additional results of Synthetic Experiments Table 9: The additional optimization performance of different methods in three synthetic settings. Setting (1) Setting (2) Setting (3) k \text{MSE}_{x} \text{MAE}_{y} Acc \text{MSE}_{x} \text{MAE}_{y} Acc \text{MSE}_{x} \text{MAE}_{y} Acc T/3 TOCBBO 0.0054 0.0509 1.00 0.0001 0.0036 1.00 0.0021 0.0312 1.00 SMTGP-UCB 0.0057 0.0942 1.00 0.0548 0.3336 1.00 0.0340 0.8616 0.71 MLGP-UCB 0.0677 0.9775 0.33 0.0434 0.6961 0.50 0.3549 0.8205 0.29 MVGP-UCB 0.0325 0.7530 0.33 0.0019 0.0191 1.00 0.0405 0.3647 0.71 TOGP-RS 0.0208 1.3279 0.83 0.0206 0.4347 0.50 0.0709 1.5521 0.57 SMTGP-RS 0.0203 1.2625 0.50 0.1201 0.4443 0.50 0.0254 1.0703 0.50 MLGP-RS 0.0619 1.0296 0.67 0.1191 0.5081 1.00 0.1816 1.1735 0.64 MVGP-RS 0.0634 0.9733 0.67 0.0469 0.4444 0.50 0.0574 1.3837 0.43 2T/3 TOCBBO 0.0006 0.0125 1.00 0.0010 0.0076 1.00 0.0103 0.1163 0.96 SMTGP-UCB 0.0066 0.0585 1.00 0.0012 0.0177 1.00 0.0122 1.9890 0.89 MLGP-UCB 0.0323 3.6747 0.82 0.2229 1.4532 0.75 0.0423 4.0294 0.81 MVGP-UCB 0.0047 0.4765 1.00 0.0022 0.0309 1.00 0.0324 1.4985 0.93 TOGP-RS 0.0128 4.6512 0.82 0.0202 1.1872 1.00 0.0218 10.4919 0.70 SMTGP-RS 0.0128 4.6512 0.82 0.2229 1.4532 0.75 0.0110 6.0795 0.70 MLGP-RS 0.0323 3.6747 0.82 0.2229 1.4532 0.75 0.0423 4.0294 0.81 MVGP-RS 0.0128 4.6512 0.82 0.0439 0.8309 1.00 0.0423 4.0294 0.81 Figure 4: Each round’s logarithmic instantaneous regret of different methods in the Setting (1) (Left), (2) (Middle), and (3) (Right) when k=T/3 (Top row) and k=2T/3 (Bottom row). Table 10: Summary across CHEM, MAT, and PRINT datasets with 10 repetitions. Method CHEM MAT PRINT TOBO 100 (0.00) 150.07 (0.00) -25.03 (0.00) sMTGP-UCB 99.91 (0.10) 147.97 (2.24) -25.03 (0.00) MLGP-UCB 99.29 (0.75) 147.90 (2.32) -25.13 (0.11) MVGP-UCB 96.32 (4.89) 147.20 (3.44) -25.27 (0.32) TOGP-RS 93.84 (1.56) 147.83 (2.32) -25.27 (0.23) sMTGP-RS 96.63 (3.74) 146.22 (4.30) -25.03 (0.13) MLGP-RS 99.41 (0.76) 148.28 (1.64) -25.27 (0.23) MVGP-RS 96.32 (3.72) 147.20 (2.80) -25.27 (0.33) In the BO setting, we additionally include a single-objective GP-UCB baseline, which directly assumes that L_{f}\mathbf{f} follows a GP and uses the UCB acquisition function to select query points sequentially. The optimization results under the three settings in our numerical experiments are summarized below. Table 11: The results of Single GP-UCB in three synthetic settings. Criterion Single GP-UCB TOBO Setting (1) \text{MSE}_{x} 0.0004 0.0000 Ins Regret 0.0459 0.0001 Time 457.34 6968.25 Setting (2) \text{MSE}_{x} 0.4761 0.0003 Ins Regret 0.2093 0.0002 Time 187.30 1588.53 Setting (3) \text{MSE}_{x} 0.0084 0.0001 Ins Regret 0.1964 0.0302 Time 415.61 6035.61 We include an independent GP-UCB baseline (Ind GP-UCB), which assumes that each tensor element follows its own GP model and applies the proposed CMAB-UCB2 acquisition function to sequentially select both query points and super-arms. The optimization results under the three synthetic settings are summarized below. Table 12: The results of the Ind GP-UCB in three synthetic settings. Criterion Ind GP-UCB TOBO Setting (1) MSE x 0.2121 0.0023 MAE y 0.6739 0.0172 Acc 0.67 1 Ins Regret 36.301 0.9807 Time (s) 328.56 8017.08 Setting (2) MSE x 0.0731 0.0000 MAE y 0.0486 0.0000 Acc 1 1 Ins Regret 0.1561 0.0000 Time (s) 110.77 2348.16 Setting (3) MAE y 0.0139 0.0021 Acc 0.86 1 Ins Regret 54.2714 1.4406 Time (s) 3296.72 11699.09 For non-separable multi-output GPs ( 19 ) , we additionally provide the results under the three synthetic settings below. Table 13: The results of the non-separable MOGP in three synthetic settings. Task Criterion Setting (1) Setting (2) Setting (3) GP NLL 507.19 -39.33 -3094.10 MAE 0.1923 0.1493 0.1591 \|\mathrm{Cov}\| 6.7398 0.5618 20.5800 Time (s) 453.11 151.31 1397.68 BO MSE x 0.0014 0.0005 0.0244 MAE y 0.0536 0.0503 0.6277 Ins Regret 1.0284 0.0030 6.6283 Time (s) 9109.08 2101.45 7881.31 CBBO MSE x 0.0073 0.0683 0.0091 MAE y 0.0643 0.0390 0.1257 Acc 1 1 0.86 Ins Regret 1.7389 0.1551 51.4646 Time (s) 10462.18 3107.82 14175.50 As shown, TOBO achieves consistently better optimization accuracy than Single GP-UCB, Ind GP-UCB, and non-separable MOGP-UCB across all settings. Although the runtime of TOBO is higher, we further introduce an efficient variant named SVD-TOBO, which employs a low-rank eigen-decomposition to approximate the TOGP covariance in Remark 3 and significantly reduces runtime. To evaluate the sensitivity of our method with respect to different choices of L_{f} and H_{f} , we consider three types of operators defined as follows ( 12 ) . • Sum operator (used in the main manuscript): L_{f}\mathbf{f}(\bm{x})=\sum f_{i_{1},\ldots,i_{m}}(\bm{x}) , H_{f}\tilde{\mathbf{f}}(\bm{x},\bm{\lambda})=\sum\tilde{f}_{i_{1},\ldots,i_{m}}(\bm{x},\bm{\lambda}) . • Weighted sum operator: L_{f}\mathbf{f}(\bm{x})=\sum w_{i_{1},\ldots,i_{m}}f_{i_{1},\ldots,i_{m}}(\bm{x}) , H_{f}\tilde{\mathbf{f}}(\bm{x},\bm{\lambda})=\sum w_{i_{1},\ldots,i_{m}}\tilde{f}_{i_{1},\ldots,i_{m}}(\bm{x},\bm{\lambda}) , where w_{i_{1},\ldots,i_{m}}\sim U(0,1) . • Exponential weighted operator: L_{f}\mathbf{f}(\bm{x})=\sum e^{pw_{i_{1},\ldots,i_{m}}-1}e^{pf_{i_{1},\ldots,i_{m}}(\bm{x})} , H_{f}\tilde{\mathbf{f}}(\bm{x},\bm{\lambda})=\sum e^{pw_{i_{1},\ldots,i_{m}}-1}e^{p\tilde{f}_{i_{1},\ldots,i_{m}}(\bm{x},\bm{\lambda})} , where p=2 and w_{i_{1},\ldots,i_{m}}\sim U(0,1) . The results under Setting (1) in our numerical experiments are summarized below. Table 14: The results of different operators in three synthetic settings. Criterion Sum operator Weighted sum operator Exponential weighted operator BO MSE x 0.0000 0.0000 0.0000 MAE y 0.0008 0.0083 0.0072 Ins Regret 0.0001 0.0044 0.0533 CBBO MSE x 0.0023 0.0037 0.0025 MAE y 0.0172 0.0329 0.0548 Acc 1 1 1 Ins Regret 0.1964 0.0107 0.4972 It can be seen that our method is robust across different choices of L_{f} and H_{f} , and both TOBO and TOCBBO consistently achieve strong optimization performance. Appendix N Real-world Application: Semiconductor manufacturing process A motivating example arises from semiconductor manufacturing, where each wafer consists of numerous dies (chips) arranged in a two-dimensional grid. During the Chip Probing (CP) phase, a critical stage for functional quality control, each die is evaluated based on multiple quality variables such as voltage, current, leakage, and power consumption. These variables are spatially correlated across neighboring dies due to physical effects such as process variation and mechanical stress, forming a naturally structured tensor output. To ensure high yield and reliability, manufacturers aim to adjust process control parameters (inputs) so that all quality variables across the wafer remain within target specifications. This leads to an optimization problem where the output is a three-mode tensor: the first two modes index the die positions on the wafer, and the third mode captures multiple quality variables. Such a scenario cannot be effectively modeled by scalar- or vector-output BO approaches, as they would lose essential structural information. In practice, each wafer may contain hundreds of dies. However, resource and time constraints often make it infeasible to measure all quality variables across all die positions on every wafer. Manufacturers instead selectively measure a subset of output entries, such as centrally located dies, those more prone to failure, or historically most informative regions. Similarly, only a subset of quality variables may be measured if certain tests are time-consuming or costly. This results in a partially observed tensor, where only part of the full output is available at each iteration. We incorporate this example into the revised paper and conduct a corresponding case study. The input is \bm{x}=(x_{1},x_{2},x_{3}) representing process parameters, and the output \mathbf{f}(\bm{x})\in\mathbb{R}^{5\times 5\times 3} denotes die-wise quality variables on the wafer. A black-box semiconductor simulator is employed as the true system. We generate 5 observations as the initial design and then sequentially select 20 queried points based on different BO methods. Tables 15 and 16 compare the performance of TOBO and TOCBBO against several baselines. Our methods significantly outperform the alternatives in terms of input accuracy (MAE x ), regret, and final objective value, demonstrating their superiority. TOBO sMTGP-UCB MLGP-UCB MVGP-UCB MAE x 0.0651 (0.0016) 0.1997 (0.0020) 0.1579 (0.0059) 0.2669 (0.0046) Regret 0.1702 (0.0007) 0.2400 (0.0014) 0.1956 (0.0088) 0.3818 (0.0029) Objective 0.8298 (0.0009) 0.7600 (0.0031) 0.8044 (0.0079) 0.6182 (0.0033) Table 15: Performance comparison of TOBO with baseline methods in terms of MAE x , regret, and objective (mean and standard deviation). TOCBBO sMTGP-UCB MLGP-UCB MVGP-UCB MAE x 0.1453 (0.0466) 0.4313 (0.0592) 0.5702 (0.0747) 0.6758 (0.0844) Regret 0.1431 (0.0388) 0.2483 (0.0522) 0.4338 (0.0918) 0.3461 (0.0709) Objective 0.6085 (0.0436) 0.5290 (0.0500) 0.4282 (0.1147) 0.4794 (0.0912) Table 16: Performance comparison of TOCBBO with baseline methods in terms of MAE x , regret, and objective (mean and standard deviation). These results show that the proposed methods can effectively optimize under partially observed tensor data, highlighting their practical relevance for semiconductor manufacturing.