Contextual Gaussian Process Bandits with Neural Networks
Authors: Haoting Zhang
Jinghai He
Rhonda Righter
Zuo-Jun Shen
Zeyu Zheng
Venue: NeurIPS 2023 poster (2023)
Keywords: contextual bandit
Gaussian process
neural network
TL;DR: We propose a surrogate model for solving contextual bandit problems, which integrates neural networks with Gaussian processes.

Abstract: Contextual decision-making problems have witnessed extensive applications in various fields such as online content recommendation, personalized healthcare, and autonomous vehicles, where a core practical challenge is to select a suitable surrogate model for capturing unknown complicated reward functions. It is often the case that both high approximation accuracy and explicit uncertainty quantification are desired. In this work, we propose a neural network-accompanied Gaussian process (NN-AGP) model, which leverages neural networks to approximate the unknown and potentially complicated reward function regarding the contextual variable, and maintains a Gaussian process surrogate model with respect to the decision variable. Our model is shown to outperform existing approaches by offering better approximation accuracy thanks to the use of neural networks and possessing explicit uncertainty quantification from the Gaussian process. We also analyze the maximum information gain of the NN-AGP model and prove regret bounds for the corresponding algorithms. Moreover, we conduct experiments on both synthetic and practical problems, illustrating the effectiveness of our approach.

Contextual Gaussian Process Bandits with Neural Networks
Haoting Zhang Jinghai He Rhonda Righter Zuo-Jun Max Shen Zeyu Zheng
Department of Industrial Engineering & Operations Research
University of California, Berkeley
Berkeley, CA 94720
haoting_ zhang, jinghai w max.hen, sxaaxshee,zyhhhnn@@bekeeee.e. edu
Abstract
Contextual decision-making problems have witnessed extensive applications in various fields such as online content recommendation, personalized healthcare, and autonomous vehicles, where core practical challenge to select suitable surro- gate model for capturing unknown complicated reward functions. is often the case that both high approximation accuracy and explicit uncertainty quantification are desired. In this work, we propose a neural detwork-accoppaniee Gaussian process (NN-AGP) model, which leverages neural networks approximate the unknown and potentially complicated reward function regarding the contextual variable, and maintains a Gaussian process metamodel with respect the decision variable. Our model is shown to outperform existing approaches by offering better approximation accuracy thanks to the of neural networks and possessing ex- plicit uncertainty quantification from the Gaussian process. We also analyze the maximum information gain of the NN-AGP model and prove regret bounds for the corresponding algorithms. Moreover, we conduct experiments on both synthetic and practical problems, illustrating the effectiveness of our approach.
Introduction
Various applications, including online content recommendation (1) healthcare 37 15 36]. and autonomous vehicles [7], demand the sequential selection of a decision variable, conditional on the observed contextual variable representing the state of the environment in each round. These
applications can generally be framed as contextual bandit problems [5] 59 63 2] especially when the reward function associated with each pair of decision and contextual variables unknown. When both the decision and contextual variables are drawn from continuous sets, a significant challenge selecting an appropriate surrogate model approximate the reward function, considering both approximation accuracy and uncertainty quantification. A common approach to alleviate this issue to employ Gaussian process (GP) model the reward function 61 46). yielding the GP bandit method [80 81] Indeed, GP has proven to be an effective surrogate model to address the exploration-exploitattie exploitation trade-off in estimating the unknown function while optimizing over it; see 51]. On the other hand, most of the existing GP bandit literature does not take the exogenous contextual variable into consideration, despite its critical role in capturing effects beyond the decision variable that influence the reward - effects that are integral to many of the applications previously mentioned [50] 62). When the contextual variable included in GP bandit problems, previous work largely adopts GP to jointly model the reward function with both contextual and decision variables, employing a composite kernel that is either the sum or product of two separate
[88 (75] 90 43
kernels; see [57]
While GP-based bandit methods have proven effective in various applications they may fall short in scenarios where the reward function exhibits intricate dependence on complex
86 6]
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

contextual variables, for example, viry-ig rewards [3 31 and graph stuph-strectured contextual variables (7T) Specificallyy, it is a challenge to pre-define an appropriate composite kernel function for the joint GP. which is critical for the performance of the corresponding bandit algorithms, as documented by [21. [2]. Neural networks (NN), on the other hand, have been utilized elsewhere as surrogate models for the reward function in bandit problems [66] 54 55), thanks to their flexibility and strong approximation power. However, they bring their own set of challenges. The "black-box" nature of the neural network hinders explicit uncertainty quantification and complicates theoretical analysis of the associated algorithms. In particular, the acquisition functions guiding point selection in these algorithms necessitate approximation of uncertainty [99 [4]. Although this approximation tends to be accurate when the NN's width is large, this can also lead to overparameterization
Contribution. This paper proposes a neural network- accompanied Gaussian process (NN-AGP) model for solving contextual bandit problems, especially when the reward functions have intricate dependence on complex contextual variables. The proposed model is an inner product of neural network and multi-output GP, where the neural network captures the dependence of the reward function on the contextual variables, and the GP is employed to model the mapping from the decision variable to the reward. Our model generates a joint GP with both contextual and decision variables, which outperforms the existing GP-based bandit methods by specifying the data-driven kernel function through the lens of neural networks, thereby leading to an accurate approximation for the reward function. Moreover, compared with entirely relying on NN's, our model stands out due to the explicit GP expression with respect to the decision variable. This feature enables bandit algorithms with NN-AGP to be implemented efficiently with existing GP-based acquisition functions and provides a theoretical guarantee of the regret bounds. Our main contributions can be summarized as follows:
1. We propose NN-AGP model and its upper confidence bound (UCB) algorithm for contextual bandit problems, referred to as NN-AGP-UCB. Our algorithm offers a data- driven procedure to specify the kernel functions of the joint GP, thereby achieving superior accuracy and model flexibility. We also prove the upper bound for both the maximum information gain of the NN-AGP model and the regret of the NN-AGP-UCB algorithm.
2. We conduct the experiments to evaluate our approach for complex reward functions, in- cluding those with time-varying dependence on sequenced and graph-structured contextual variables. Experimental results demonstrate the superiority of our approach over existing approaches that entirely rely on either GP or NN.
1.1 Related work
Since the seminal work by [0), the Gaussian process (GP) bandit problem has been extensively studied, where the bandit feedback is modeled as a GP regarding the decision variable (arms to be
pulled). Some recent work includes [35] 32 13 12
II
18
65
In addition, GP bandits are also
52 231, where both problems consider optimizing black-box functions and therefore require surrogate models (GP in particular). When the number of decision variables is finite, the black-box optimization problem is also known Ranking & Selection (R&S) [44 73 70 4 87), where GP models are widely employed as well; see (20 58, 79 64]. Our NN-AGP model can also be employed in (contextual) BO or R&S, but the discussion is beyond the scope of this work.
related to Bayesian optimization (BO) problems [8 19
39
34
28
85
In this work, we specifically take the exogenous contextual variables into consideration. Previous work employs multiplicative and additive kernels to incorporate continuous context spaces into the scalar GP; see [57]. Other work considers safe contextual Bayesian optimization, employing a similar strategy to construct composite kernels; see [41 91. Another line of research explores distributionally robust BO
56 83 53], where the contextual variable distribution is selected from an ambiguity set. The methodology of representing the objective function using joint GP has also been widely used in
contextual policy search; see 722 21 40
The connection between GP and NN has been explored in 660 68), documenting that NN's 's with infinite width approach a GP model when the weight parameters are assigned with Gaussian priors. In addition, deep GP's have been proposed to enhance the model flexibility of neural networks where variational inference is employed; see [27 26 9T]. GP models in which the parameters are represented by neural networks studied in
98
97

---

2 Main procedure
We consider a problem of sequentially selecting a system's 's imput variable (decision variable) for T (not necessarily known a priori) rounds. In each round, we receive a contextual variable 0 E e C Rd from a set θ, and select a decision variable x, X I2 from a set &' of decisions. We then receive an observation
V/+ = f(x(;))))) Ec,
where fx; 0) is the reward (objective) function and ét ~ NNO, o²) denotes the noise that is independent of both the contextual variables and decision variables. We consider the scenarios when both ④ and X' are continuous and 0,'s 's are fully exogenous. That is, the selection of the decision variable in each round does not influence the future contextual variables. Although we focus on unconstrained problems in this work, our proposed model can be employed approximate the constraints in optimization problems as well; see 9 We also note that, for the description and discussion of our approach, the contextual variable is represented by vector. However, we show through experiments in Section that our approach is applicable to contextual variables with other structures.
Since fxx 0) is unknown, we will not generally be able to choose the optimal action, and will thus incur regret r; = supx'ex (x', 0.) - f (x:, 0t), indicating the difference between the optimal reward and the reward we actually receive in each round. After I' rounds, the cumulative regret is RT= = =Z= Tt- Our goal is to develop an algorithm that achieves sub-linear contextual regret, i.e., RT/T + 0 for T' + oo, which requires a statistical model of the reward function with respect to both context variables and decision variables.
We specifically consider reward function in the form
f(x: 0) = g(0) p(x),
(I)
where g0) and p(x) are both m-dimenniinal vector-valued (unknown) functions, and m E N is user-selected quantity to indicate the complexity of the function. There are two main reasons for considering this reward function. First, this formulation is a generalization of linear contextual bandits, where the reward function is the inner product of the contextual variables and the unknown parameters. Here, we assume that the inner product is taken with two vector-valued functions with respect decision variables and the contextual variable, which is similar in spirit to 24 Second, this reward function is consistent with the tensor-product approximation of a general function; (29 30 47). Therefore, further analysis model mis-specification of the reward function can be supported by existing results of tensor-product approximation.
96 42 100).
In this work, we specifically assume that (0) is a vector-valued deterministic mapping from 12d" to RT represented by neural network with given structure and some weight parameter W. In addition, p(x) is a multi-output Gaussian process (MGP) defined on X' C IR The MGP model is a generalization of the scalar-valued GP, where the output p(x) at each is m-ddimensional vector. The MGP model captures not only the dependence between two outputs but also the dependence between different entries of each output. Thus, the covariance of MGP pxx) is represented by matrix-valued covariance function, denoted by IC (x, x') and the vector of parameters involved in the MGP is denoted by + We postpone the detailed description of the NN-AGP model Section 3.1 and conclude our brief introduction of NN-AGP with an associated proposition, which follows easily from the fact that the normal distribution is preserved under linear transformations.
Proposition 1. The reward function fx; 0) is scalar-valued mean-zero Gaussian process with respect to x and O. The kernel function of this Gaussian process is
K (xx, 0) (x', 0') ( (x,x')
where K. (x,x²) is the covariance of the MGP.
Next, we provide a bandit algorithm with the NN-AGP model, during which the surrogate
model is sequentially learned from data. We name the algorithm neural network-accompunied Gaussian process upper confidence bound (NN-AGP-UCB). Suppose we are now in round I. and observe the contextual variable 0, In addition, we also have the historic data D.-1 = {(0,, x1, v1), (02, X2, V2) ...., v2....., (0,-1,00,,,,1 11-1)} in hand. Denote by yt-1 (y11 ..,.... 11-1)
3

---

the vector of observations. The selection of the next decision variable x, depends on the posterior distribution of the reward function, which fx; 0,) D.-1 ~ N (M--1 1 (x: 0.) oi (x: 0.)) Here
Pt-1 (x: 0.) (x(x0))) (RD... 02 yt-1.
-1 k(x:0)) [KDmn Tc. K(xx:))::
o² (x; 01) =0(),) Kx, x) g(,)
where K(x:0.)) denotes the covariance vector between f (x; 0τ) and {f (x,: 0,) 0,) In addition, for the 1) (L 1)-dimensional covariance matrix for historical data K PD_ the (i, entry is ((.) " (x,,,,) g(O,) as in Proposition 1 The required parameters in ②). including the weight parameters W of the neural network g the parameters + involved in the MGP p(x) and the variance o² of the noise ez. are all learned and updated with the observations through (5) which we will discuss in Section 3.1
In terms of the acquisition function (the function that decides the decision variable in the following it- eration), we employ the contextual Gaussian process-upper confidence bound (CGP-UCB) introduced in [57] That is, decide xx
arg IIIX M (x; 0r) + 3//2 00 (x; 0.)
where 1t-1 (x: 0,) and 0-1 (x: 0.) are the posterior mean and standard deviation of f (x; 0,) as calculated in (2). The optimization problem (3) can be solved efficiently by global search heuristics, as suggested [17. In addition, 3r is user-selected hyper-parameter each round, addressing the exploration-exxpooiaaion trade-off; see discussions in Section 3.2 The procedure for NN-AGP-UCD
summarized in Algorithm|] [ We note that other commonly selected acquisition functions for GP bandit problems or Bayesian optimization can be employed with NN-AGP well, including knowledge gradient 776 89 333 and Thompson sampling [25] 74) We postpone the discussion of these acquisition functions to the supplements.
Algorithm 1 NN-AGP-UCB
Input: Initial values of (W, 4, o²);
for t 1,2,.... T do
Observe the contextual variable 0,;
Choose x, arg maxxex
| (x: 0.) ( +//
0 (x: (x 0x)
Sample y1 at Xe);
Update (W.. &e of
as in 5):
end for
3 Statistical properties
3.1 Specification of NN-AGP
We describe the NN-AGP model here, which is employed as the surrogate for the reward function. Recall that the reward function with the pair of contextual and decision variables (0, x) is f(x; 0) g()) pxx), where g(0) is vector-valued neural network (with weight parameters W) from Rd to I.m and pxx) is an m-dimensional output Gaussian process defined on X' C Ied To be more specific, the outputs p (Pi, .p....... Pm.) are assumed follow multi-output Gaussian process (MGP) as
p(x) MGP (0, IC (x)x)))
Here, K. (x,x') denotes the covariance matrix of p(x) and p (x'), defined as K. (x,x') =
Kn (x,x)) Kim (x, x')
which is positive and semi-definite. The (1,1")-th entry Kir (x)x) represents the covariance (similarity) between outputs pr(x) and py (x'). The NN-AGP
Kmi (x,x') K Kmm (x,x)

---

model results in a scalar-valued Gaussian process with both the contextual and decision variables and therefore facilitates explicit acquisition functions and theoretical analysis. This GP representation arises from the linear structure between the MGP and the mapping g
To specify the covariance matrix, adopt the collaborative multi-output Gaussian process model [69] as a representative, which generalizes the commonly-used linear model of coregionalization (LMC) and the intrinsic coregionalization model (ICM); see [67]. That is, the MGP determined by the linear transformation of multiple independent scalar-valued Gaussian processes as
pr(x) Σ ug + (x).
Here, ((( is the I-th element of p(x), is the number of involved GP's, {u,(x)) and for (x)]m= are independent scalar-valued GP's, and the at,g's 's are coefficient parameters. In this way, the correlation between different entries in the MGP p(x) is captured by (x)(x))
through the "r,g's. Morever, vi (x) represents specific independent features of pı(x) itself, for I = 1, m. m. Suppose the kernel functions of the Wy (x)'ss and vy (x('s 's are ky (x, x')ss and 1 xx'''ss and all these kernel functions are less than or equal to one, as is regularly assumed
80
81 57.. Then the matrix-valued kernel function of p(x) is K. (x, x') Eg= Aghig (x, x')
km (x, x Here, Ag denotes the semi-definite matrix in which the (1, 1-thh entry is "r. .q. In some applications, the parameters involved in the kernel functions by (x, x') and ka x'), and the coefficients 01.4's are not known in advance. We denote these unknown parameters and coefficients in the MGP Φ. In addition the model (4), other types of MGP's can be employed in our methodology as well [14]. while the selection of model (4) enables the theoretical analysis of our approach.
Diag [
In terms of the mapping g0).. since we have no prior knowledge, we select the neural network the surrogate model, due to 1) its strong approximation power for intricate dependence on complex variables; 2) its flexibility of adaptation to different application scenarios (e.g. time-series or graph-structured contextual variables) and 3) the availability of fruitful methods and tools for the training procedure. Given the data D, = {() (1)
v (02, X2, 122 ..... (O,, Xx, }t)} the learning of unknown parameters in the MGP and the weight parameters in the neural network (as well the noise variance) is through maximum likelihood estimation (MLE). That is
We. 22 arg
L, (W, 0. (W.0,0?)
(5)
where the (normalized) likelihood function is L, = - In KD. + +0 -y [Ro, + I21.]
y Here, y: (W1, ./...... M/ is the vector of observations and KD, is the covariance matrix of the data D., The parameters W and & are contained this covariance matrix. That is, instead of pre-defining kernel function of the GP. the kernel function of NN-AGP is specified through learning the neural network from the data, yielding better approximation accuracy. We include a discussion of the consistency of training NN-AGP in the supplements.
3.2 Cumulative regret
Recall that the cumulative regret is defined as Rr Eim (supxex f (x, Of 0.)3. Here we provide an upper bound of Rr with NN-AGP-UCB.
Theorem 1. Suppose 8 (0, 1) and the following.
1. The decision variable I E X C r0, and X is convex and compact. The contextual variable O CECR ddd and θ is convex and compuct; g(0) is known continuous mapping of E O; p(x) is sampled from known MGP prior as in (4) and the variance of the noise of is known. That is, these parameters do not need learning and updating from data.
5

---

2. For the components of the MGP, there exist constants satisfying
{ g=1 (bol fail= [b
( {
(x)
Lg) & are (l//bb)) ( ;PP
Qvr(a) Jzy
> Li & āge -li,bb3 (6)
sup JE
sup FE
Jzz
Lg Li > 0 and =j= = 1,,,...... .., d. 9= 1=1,2,... and = 1,
3. We choose hyper-parameter in
Be log (f22*² (36)) + 2dlog [M dbr /ood/bbllgaiiiiaaaee /log(Ada//))))
where and r are the dimension and the upper bound of the decision variable, a = Eg Og + Ei dr. = Eg by + Ei=ib by M =
supage {1EE= (0.00)))...ll 9 (l9: where gi denotes the 1-th entry of g
Then the cumulative regret bounded with high probubility as
P|RT
P Rr < V log (1 Co. 6
SCT
+ π
Here = ((Eg)) ET dZ.a) +1) supace (0)( In addition, "T is the maximum information gain associated with the NN-AGP f(x 0), defined by
We postpone the discussion of the maximum information gain YT to Section 3.3 with some specific kernels employed in the MGP component of the NN-AGP model. We note that GP's with commonly- selected kernel functions, including the Matérn kernel and the radial basis function kernel, satisfy the condition (6) and further discussions can be found in Theorem in [5). A detailed proof of Theorem
D is contained in the supplements. Note that Theorem assumes that g is exactly known so does not consider the error of approximating g (0) with the neural networks. In the supplements, we include a detailed discussion of the algorithm that considers the neural network approximation error, well the corresponding regret bounds.
At the end of this section, we compare our regret bound with existing work. Specifically, NN-AGP- UCB has the same bound Ô (VT as CGP-UCB, but is superior when the contextual variable dimension is high; see details in the supplements. In terms of the algorithms which entirely rely on NN, we note that NeuralUCB 199. Neural TS [98]. and Neural LinUCB [95] all consider the scenarios when the decision variable x is selected from finite set. In comparison, we consider that is selected from a continuous set. When performed on a finite feasible set X, our NN-AGP-UCH also has a regret bound Ô (vTrr), where the maximum information gain ?r further depends on the kernel function of the GP component used in NN-AGP. When the kernel function has exponential eigendecay (see Definition NN-AGP-UCB has a regret bound of Ô (VT)). matching the regret bound of NeuralUCB, Neural TS and Neural LinUCB as well.
3.3 Maximum information gain
In this section, we discuss the information gain "T of the proposed NN-AGP model. The maximum information gain is defined
TT
sup (1 cexX
(yy: fr),
where fr is the reward function evaluated at {(0, x:) yT denotes the observations; I (yri fr) = H (yr) H (yr fr) is the mutual information between yr and fri I1(-) = E[ lo-pogp(.) is the entropy of a random element, where p is the probability density function.
For ease of notation, here we consider the scenario when Q 1 and there is no {v)(x)} } in the MGP defined (4). i.e., pr(x) = aju(x). We also impose more variability so that = A is a semi-definite positive matrix and not necessarily a rank-one matrix, analogous to [14]. We provide more general discussion of the maximum information gain the NN-AGP the supplements. We first provide proposition on the kernel function.

---

Proposition 2. When Q = and there is no {v((x)} in the MGP, the kernel function of the NN- AGP is product of two kernel functions. That is K ((x, 0), (x',0)) k(0,0" >k(x)x'))))))))) x'), where k(0, 8¹) = g (0) and X' are compact. g is continuous mapping and k (x, x') is a semi-definie kernel function. Then the kernel function K ((x, 0), (x',0))
) is finite rank kernel with respect to 0. Furthermore, suppose that both G
0')) possesses a Mercer decomposition:
K ((x,0), 0), (x', 0))
Hudzos (0) 3/ (x) Φs (0') 1/ (x).
Here, {(us d.)) and {(Aj, و are the Mercer decompositions for is (0, 0²) and k (x, x').
That is, & (0, 0²) Σ (0); (0') (x,x') ues are μ1 > #2 > ... > pm and A1 7 A2 > 0.
EE= Ay4; (x) 43 (x') where the eigenval-
With the Mercer decomposition of the NN-AGP kernel function, we provide the bound of the maximum information gain. Specifically, we consider two scenarios for the employed kernel in the MGP, analogous to [22 84
Definition 1. Consider the eigenvalues {Ag1)=1 of the kernel function l (x) ) in decreasing order.
For some Cp > O, ap > k is said to have (Cp, ap) polynomial eigendecay, if for all An example the Matérn kernel.
j N, we have X; & Cpj
For some Ce,1, C,,2, Oe > 0, k is said to have a (Ce,1, Ce.,, Oie) exponential eigendecay, if for all N, we have X3 < Ce.1 exp (xp(-Ce,2jj An example is the radial basis function kernel.
Theorem 2. Suppose that 1) K ((x, 0). (x) satisfies the conditions in Proposition 2) Vx, x' E X, [k xxxx')| ] & for some le >> 0 and 3) Vjj E N, Vx X, [15((x)1 & tb. for some vb 0. If (x,x') has a (Cp, ap) polynomial eigendecay, then
Pr & m (( NORPOCCTTTT (muPO7C
log (1+
K&T mo?
op
RkT
+1
log
1
o²
mo?
If k (x,x') has a (Ce,1, Ce,, ae) exponential eigendecay, then ac
((2g (log(T) + +Ca.)
2
ikT mo?
YT &
Ce.2
+1 log
1+
where
Ce.1mfioR
log
if a =1
oFCo.2
Can =
(2Cemmpo2
1 O
-11)
(1--))--
1
log
log Co.2
otherwise.
Or
Here, p = 1 Em Pi denotes the mean of the eigenvalues of the kernel funneifunccion ie (0,0"); K supe,0'ce (0, and @ supece (o(0)). Moreover, the maximum information gain of the NN-AGP is O (m*s:r) where 7x:T is the maximum information of k (xxxx').
more detailed discussion of the Mercer decomposition of NN-AGP contained in the supplements. as well as the proofs of Proposition 2 and Theorem 2 At the end of this section, we compare our results on maximum information gain with [57]. For the composite kernel that is product of two kernels, the upper bound is (d + d') TxeT (d d') log T. Here, 7x:2" is the maximum information gain of the kernel function with the decision variable, and d' and are the dimensions of the contextual variable and the decision variable. That is, the information gain (as well as the cumulative regret) increases as the dimension of the contextual variable increases. In comparison, the maximum information in Theorem 2 does not depend on d'. Thus, the NN-AGP model has lower cumulative regret than the classical strategy in 57 when the dimension of the contextual variable relatively high.
7

---

4 Experiments
In this section, we conduct experiments to show the practicality of our neural network eetoorr-accompaniee Gaussian process upper bound confidence (NN-AGP-UCB) approach. We apply different neural networks to different problems, including the fully-connected neural network (FCN) [77 to a synthetic reward function, the long short-term memory (LSTM) [88] neural network queuing problem with time sequence contextual variables, and the graph convolutional neural network (GCN) (78 to
a pricing problem with diffusion networks. We add a noise 6r i.ddd No, 0.01) to the ground-truth value of the reward in the first set of experiments. For the latter two sets of experiments, the reward is generated by stochastic simulation (and therefore is "black-box" with contextual/decision variables) and we postpone the description of the full dynamic to the supplements. We also provide additional experiments in the supplements, including 1) sensitivity on the structure of reward functions; 2) comparison with contextual variables possessing different dimensions; 3) regression tasks complex functions and 4) finite decision/contextuall variables with real data.
The baseline approaches includes CGP-UCB [57]. NeuralUCB [99] and NN-UCB [54] The experi- ment results provided are mean performances based on repeating the experiments 15 times. Standard deviations (represented by a shadow associated with the mean-value line) are also included. In each iteration, the exogenous contextual variable 0, is randomly selected from with equal probability. In terms of the initialization, we randomly select decision variables independently of observed contextual variables for each approach in the first 20 iterations to attain surrogates. The specific description of the employed surrogate model in each approach is postponed to the supplements.
4.1 Synthetic reward function
In this section, we consider two synthetic reward functions
Rí (x, 0) -
-Visin V|sin ( [x|) 0 exp (cos ([xx] + [))l:
R2 0) = - / ////||n((l I exp[[|<|| + (o)()
For NN-AGP-UCB, consider m 3, 3,5 study the effects of model selection on the algorithm performance. For CGP-UCB, we consider both additive kernels and multiplicative kernels. Because both NeuralUCB and NN-UCB are designed for contextual bandits with finite arms, adapt them to the problem we consider in Section 2 and postpone the details to the supplements. The experimental results of the average regret R /T are illustrated in Figure 1 and Figure 2 which provide the following insights. 1. Comparison with baseline approaches. For both reward functions, NN-AGP- UCB outperforms both the CGP-UCB and NN-based approaches. The advantage comes from 1) strong approximation power regarding O due to NN and 2) explicit inference regarding x due to GP. 2. Effects of the dimension m. Generally, when m increases, the model flexibility increases, and the regret might be smaller, although this improvement might not be significant in some scenarios. Furthermore, a relatively large m might result in overparameterization especially when there are not enough iterations. A suggested selection of m is dd/3 + d' /10] + 3 considering both the algorithm performance and training complexity of models. 3. Breaking the linear assumption. Recall that we assume the reward function is of the form of R (x; 0) g (0) p (x). However, the reward functions here break this linear assumption and yet our NN-AGP-UCB is still applicable and outperforms the baseline approaches. Moreover, additional experiments show that NN-AGP 1) is not sensitive on the structure of the reward functions; 2) has a greater advantage with higher-dimensional contextual variables and 3) achieves better approximation accuracy for complex functions, compared with a joint GP with composite kernels; see the supplements for details. In addition, when the dimension of the input increases, the uncertainty of the regret will increase well; see Figures I & 2 for comparison. We also include the recorded computational time of these bandit algorithms in the supplements.
4.2 Queuing problem with time sequence contextual variables
In this section, we show through experiments that the NN-AGP model is applicable to contextual GP bandits when the objective function depends on the sequence of the contextual variables. That is, the reward function at time t can be approximated by
ft (x: 01, .2...., 0.) g: (01, Oz..... .........)..
0.) p(x).
8

---

3.6
3.8
MN AGPI UCB (m=2)
ANLAGP-UCB (m=3)
MNJAGINUCB (mm3)
NhuAdPsLCE CB (m-5)
botth add thve barne)
3.4
CGP-UCB (whth multiplicative keme))
(wth karrel)
Nouralica
3.2
Neurafuce
Nk. LCB
NN-UCC
100
150
200
250
300
Rounds
Figure 1: Average regret of using Rg (x; 0)
Figure 2: Average regret of using (x; 0) with X' = [-1,1] and θ [-1, 1]
with = [] and θ [-1,
Here, 9t (01, 02..................... 02) is modeled by an LSTM neural network. We consider discrete-time queuing problem. In each time epoch, contextual variable is first revealed. For example, the contextual variable might includes traffic and weather conditions that affect the arrival process of the queuing system. The number of customers arriving this epoch depends the entire sequence of the revealed contextual variables up to now. The agent decides the service rate of the server and the service price for customers (decision variables). The reward function (might be negative) the expected net income (the income brought by serving customers minus the service cost and penalty for losing customers). We let X [0, 5)2 and sample 0, from multivariate normal distributions. We present the cumulative rewards in Figure 3 and oigure/J NN-AGP-
seque
with LSTM. The baseline CGP-UCB adopts both additive and multiplicative kernels with the current contextual variable. We also apply kernel functions specifically designed for time series (10) to construct the composite kernel. Experimental results indicate that 1) employing a specific time series kernel enhances the performance of CGP-UCB and 2) NN-AGP-UCB with LSTM outperforms the classical CGP-UCB approaches with different composite kernels.
3000
NNAGIP-JCS (m)
12000
NN-AGP-CC (m=33
NN ANP-UCC (m=2)
2500
CGP-UC (with addiivv kemell
(m
RN-APPUER (m-+1)
CGP UCB (with additive kemnl)
CGP-UCCS (with aive bernel)
CGP-UCE (with multiplicative kemel)
CGPUUB (with additvee time-serial kamml)
CGP-UCB (with additive time serial kemell
1500
1000
500
100
Rounds
200
Rounds
Figure 3: Cumulative rewards for queuing problem with 0, d.1.d. N (O, Ia).
Figure 4: Cumulative rewards for queuing problem with O, f.1.d. (10).
4.3 Pricing with diffusion network
In this section, we show the NN-AGP model is applicable to contextual GP bandits with graph- structured contextual variables. That is, the contextual variable is summarized by network structure
0. E.).
where 1/ denotes the set of nodes and E, denotes the set of directed/undirected edges of a network. To approximate (0) with graph-structured contextual variable, we apply the GCN model. We consider pricing problem with diffusion network, where each node represents a user who decides

---

to adopt service or not and the edge between two nodes indicates whether the choices of these two users influence each other. In each iteration, the network structure is first presented, and then the agent decides the price of the service. The reward function is the expected income for the service adoption from the users. The detailed description can be found in [66]. We X = [0. 30) and O, represents undirected graph with 5 and 10 nodes where each edge exists with probability 1/2. We present the cumulative rewards in Figure5Jand F NN-AGP-UCB with GCN. The baseline CGP-UCB adopts both additive and multiplicative kernels and in terms of the contextual variable, consider 1) vectorizing the adjacency matrix that summarizes the network structure and 2) applying kernel functions that specifically designed for graphs [49]. Experimental results indicate that NN-AGP- UCB with GCN outperforms the classical CGP-UCB approach adopting different kernels, and the advantages become greater for networks with more nodes.
NN UNBACP-UB (with GCNI
(graptumalt
CON-UCB graph.multplicative
CGP UCB
agraphaadditve
CGINUCI grapph.etdittonn
Rowords Rewores
500
CGP-UCI (vector mullipicative)
CGPUUC (vector addivee)
Accumuatiio Ruwards
CGP weettoradditive
CGP-UCB vector.mutiplicaiiee
400-
Aocmm.ittiee wom.iittiee
200-
200
100
50
110
15:0
2000
250
390
460
Figure 5: Cumulative rewards with a 5-node network diffusion problem.
Figure 6: Cumulative rewards with 10-node network diffusion problem.
Conclusion & impact
We propose neural network accompanied Gaussian process (NN-AGP) model to address contextual GP bandit problems. The advantages of our approach include 1) flexibility of employing different neural networks appropriate for applications with diverse structures of contextual information; 2) ap- proximation accuracy for the reward function and better performance on cumulative rewards/regrets: 3) tractability of a GP representation regarding the decision variable, thus supporting explicit uncer- tainty quantification and theoretical analysis. Our approach has potential application to healthcare, where doctors need develop therapy plans based on patient information achieve optimal treat- ment effects. When complex and sparse genetic information is employed, it necessitates the use of neural networks. Another potential application is for Automated Guided Vehicles (AGVs) to enhance workplace safety and reduce carbon emissions, where environmental information is provided to the AGV, and the AGV takes actions accordingly.
In terms of limitations, since NN-AGP retains a GP structure, it suffers from computational complexity with large data sets. To alleviate the computational burden, consider sparse NN-AGP for future work; see a discussion in the supplements. In addition, incorporating NN into bandit problems generally requires sufficient data approximate the unknown reward function, thereby bringing the cold-start issue to NN-AGP. To address the challenge. we also include a discussion on employing transfer learning technologies in the supplements. Other potential future work includes 1) adapting optimization problems and 2) employing NN-AGP in
NN-AGP to multi-objective/constraa federated contextual bandit problem with multiple decentralized users.
Acknowledgements
We thank the anonymous reviewers and chairs for constructive comments that helped improve this work. H. Zhang and J. He were partially supported by the Berkeley graduate fellowship. Z.J.M. Shen was partially supported by NSFC Grant 71991462. R. Righter supported by the Ron Wolff Chaired Professorship.
10

---

References
[1] N. Abe, A. W. Biermann, and P. M. Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4):263-229 -93, 2003.
[2] S. Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference machine learning, pages 127-135, PMLR, 2013.
[3] Ankenman, B. L. Nelson, and Staum. Stochastic kriging for simulation metamodeling. In 2008 Winter simulation conference, pages 362-370. IEEE, 2008.
[4] Applegate, Feldman, S. Hunter, and Pasupathy. Multi-ohjective ranking and selection: Optimal sampling laws and tractable approximations via score. Journal of Simulation, 14(1):21-4)) 2020.
[5] P. Auer. Using confidence bounds for exploitation-exploatiio trade-offs. Journal of Machine Learning Research, 3(Nov): 4229992-222222 2002.
[6] Y. Bai, H. Lam, T. Balch, and S. Vyetrenko. Efficient calibration of multi-agent simulation models from output series with bayesian optimization. In Proceedings of the Third ACM International Conference on Al in Finance, pages 437-445, 2022.
[7] R. Bajrachrya and H. Jung. Contextual bandits approach for selecting the best channel in industry 4.0 network. In 2021 International Conference on Information Networking (ICOIN), pages 13-16. IEEE, 2021.
[8] R. R. Barton, B. L.. Nelson, and W. Xie. Quantifying input uncertainty via simulation confi- dence intervals. INFORMS journal computing, 26(1):74-87, 2014.
[9] F. Berkenkamp, A. Krause, and A. Schoellig. Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics. Machine Learning, pages 1-35, 2021.
[10] Bock, M. Togninalli, E. Ghisu, T. Gumbsch, B. Rieck, and K. Borgwardt. wasserstein subsequence kernel for time series. In 2019 IEEE International Conference Data Mining (ICDM), pages 964-969. IEEE, 2019.
[11] I. Bogunovic and A. Krause. Misspecified gaussian process bandit optimization. Advances in Neural Information Processing Systems, 34:3004-301 2021.
[12] I. Bogunovic, A. Krause, and J. Scarlett. Corrupiion-tolrran gaussian process bandit optimiza- tion. International Conference on Artificial Intelligence and Statistics, pages 1071-1081. PMLR, 2020.
[13] I. Bogunovic, Scarlett, and V. Cevher. Time-varying gaussian process bandit optimization.
In Artificial Intelligence and Statistics, pages 314-323. PMLR, 2016.
[14] E. V. Bonilla, K. Chai, and C. Williams. Multi-task gaussian process prediction. Advances in neural information processing systems, 20, 2007.
[15] D. Bouneffouf, I. Rish, and C. Aggarwal. Survey applications of muulii-armet and contextual bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), pages 1-8. IEFE, 2020.
[16] J. Bowden, J. Song, Y. Chen, Y. Yue, and T. Desautels. Deep kernel bayesian optimization. Technical report, Lawrence Livermore National Lab, (LLNL), Livermore, CA (United States), 2021.
[17] E. Brochu, M. Cora, and N. De Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv:1012.2599, 2010.
[18] X. Cai and J. Scarlett. On lower bounds for standard and robust gaussian process bandit optimization. In International Conference on Machine Learning, pages 1216-1226. PMLR, 2021.
11

---

[19] S. Cakmak, R. Astudillo Marban, P. Frazier, and E. Zhou. Bayesian optimization of risk measures. Advances in Neural Information Processing Systems. 33:20130-2014: 2020.
[20] S. Cakmak, E. Zhou, and S. Gao. Contextual ranking and selection with gaussian processes. In 2021 Winter Simulation Conference (WSC), pages 1-12. IEEE, 2021.
[21] I. Char Y. Chung, W. Neiswanger, K. Kandasamy, A. O. Nelson, M. Boyer, E. Kolemen, and J. Schneider. Offline contextual bayesian optimization. Advances in Neural Information Processing Systems, 32, 2019.
[22] N. Chatterji, A. Pacchiano, and P. Bartlett. Online learning with kernel losses. In International Conference on Machine Learning, pages 971-980. PMLR, 2019.
[23] H. Chen and H. Lam. Pseudo-bayesian optimization. arXiv preprint arXiv:2310.09766 2023.
[24] V. Chernozhukov, M. Demirer, G. Lewis, and V. Syrgkanis. Semi-parametric efficient policy learning with continuous actions. Advances in Neural Information Processing Systems, 32, 2019.
[25] S. R. Chowdhury and A. Gopalan. On kemeliied multi-armed bandits. In International Conference on Machine Learning, pages 844-853. PMLR, 2017.
[26] K. Cutajar, M. Pullin, A. Damianou, N. Lawrence, and J. González. Deep gaussian processes for multi-fidelity modeling. arXiv preprint arXiv:1903.077 19000073000 2019.
[27] Damianou and N. D. Lawrence. Deep gaussian processes. Artificial intelligence and statistics, pages 207-215. PMLR, 2013.
[28] S. Daulton, S. Cakmak, M. Balandat, M. Osborne, E. Zhou, and E. Bakshy. Robust multi-objective bayesian optimization under input noise. arXiv preprint arXiv:2202.07549. 2022.
[29] L. De, B. De-Moor, and J. Vandewalle. On the best rank-1 and rank-(rl r2... m) approximation of higher-order tensors. SIAM journal on Matrix Analysis and Applications, 1244):3324-3322 2000.
[30] L. De Lathauwer, B. De Moor, and J. Vandewalle. Computation of the canonical decomposition by means of simultaneous generalized schur decomposition. SIAM journal on Matrix Analysis and Applications, 26(2):295-327, 2004.
[31] Y. Deng, X. Zhou, B. Kim, A. Tewari, A. Gupta, and N. Shroff. Weighted gaussian process bandits for non-stationary environments. In International Conference on Artificial Intelligence and Statistics, pages 6909-693 PMLR, 2022.
[32] T. Desautels, A. Krause, and J. W. Burdick. Parallelizing exploration-exxlooittinn tradeoff's in gaussian process bandit optimization. Journal of Machine Learning Research, 15:3873-3923, 2014.
[33] L. Ding, L. J. Hong, H. Shen, and X. Zhang. Knowledge gradient for selection with covariates:
Consistency and computation. Naval Research Logistics (NRL), 6963):496-577, 2022.
[34] L. Ding, R. Tuo, and Zhang. High-dimensional simulation optimization via brownian fields and sparse grids. arXiv preprint arXiv:2107.08595, 2021.
[35] J. Djolonga, A. Krause, and V. Cevher. High-dimensional gaussian process bandits. Advances in neural information processing systems, 26, 2013.
[36] J. Du, S. Gao, and C.-H. Chen. A contextual ranking and selection method for personalized medicine. Manufacturing & Service Operations Management, 2023.
[37] A. Durand, C. Achilleos, D. lacovides, K. Strati, G. D. Mitsis, and J. Pineau. Contextual bandits for adapting treatment in a mouse model of de novo carcinogenesis. Machine learning for healthcare conference, pages 67-82. PMLR, 2018.
12

---

[38] D. Eriksson, M. Pearce, J. Gardner, R. D. Turner, and M. Poloczek. Scalable global optimiza- tion via local bayesian optimization. Advances neural information processing systems, 32. 2019.
[39] D. Eriksson and M. Poloczek. Scalable constrained bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 730-738. PMLR, 2021.
[40] T. Fauvel and M. Chalk. Contextual bayesian optimization with binary outputs. arXiv preprint arXiv:2111.034477 2021.
[41] M. Fiducioso, S. Curi, B. Schumacher, M. Gwerder, and A. Krause. Safe contextual bayesian optimization for sustainable room temperature pid control tuning. arXiv preprint arXiv:1906. 12086, 2019.
[42] D. J. Foster, C. Gentile, M. Mohri, and J. Zimmert. Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33:1 1478--148889 2020.
[43] P. I. Frazier, A tutorial on bayesian optimization. arXiv preprint 1807. 0300002811. 2018.
[44] M. C. J.-Q. Hu, C.-H. Chen, and X. Xiong. Simulation allocation for determining the best design in the presence of correlated sampling. INFORMS Journal on Computing, 19(1):101-
111, 2007.
[45] S. Ghosal and A. Roy. Posterior consistency of gaussian process prior for nonparametric binary regression. The Annals of Statistics, 34(5):2413-22 2429, 2006.
[46] R. Guhaniyogi, C. Li, T. D. Savitsky, and S. Srivastava. Distributed bayesian varying coeffi- cient modeling using a gaussian process prior. The Journal of Machine Learning Research, 23(1):3642-3700, 2022.
[47] W. Hackbusch and N. Khoromskij. Tensor-product approximation to operators and functions in high dimensions. Journal of Complexity, 23(4-6):697-714, 2007.
[48] S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 978: 1780, 1997.
[49] S. Højsgaard and S. L. Lauritzen. Graphical gaussian models with edge and vertex symmetries. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 1065) 2008.
[50] L. J. Hong and G. Jiang. Offline simulation online application: A new framework of simulation- based decision making. Asia-Pucific Journal of Operational Research, (6(06):1940015 2019.
[51] L. Hong and X. Zhang. Surrogate-basee simulation optimization. Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications, pages 287-311. INFORMS, 2021.
[52] S. Hu, H. Wang, Z. Dai, B. K. H. Low, and S. H. Ng. Adjusted expected improvement for cu- mulative regret minimization in noisy bayesian optimization. arXiv preprint 1,X1v. 2022.
[53] H. Husain, V. Nguyen, and A. van den Hengel. Distributionally robust bayesian optimization with g-divergences. arXiv preprint 0AXi:22033002228 2022.
[54] P. Kassraie and A. Krause. Neural contextual bandits without regret. In International Confer- ence on Artificial Intelligence and Statistics, pages 240-278. PMLR, 2022.
[55] P. Kassraie, A. Krause, and I. Bogunovic. Graph neural network bandits. arXiv preprint 1FXi::2207.064566 2022.
[56] J. Kirschner, I. Bogunovic, S. Jegelka, and A. Krause. Distributionally robust bayesian optimization. In International Conference on Artificial Intelligence and Statistics, pages 2174-2184. PMLR, 2020.
13

---

[57] A. Krause and C. Ong. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24, 2011.
[58] P. L. Salemi, E. Song, B. L. Nelson, and J. Staum. Gaussian markov random fields for discrete optimization via simulation: Framework and algorithms. Operations Research, 67(11)250-266 2019.
[59] J. Langford and T. Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. Advances in neural information processing systems, 20 2007.
[60] J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington, and J. Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprini 17X000/711.00165, 2017.
[61] C. Li. Bayesian fixed-domas asymptotics for covariance parameters in gaussian process model. The Annals of Statistics, 50(6):3334 2022.
[62] C. Li, S. Gao, and J. Du. Convergence analysis of stochastic kriging-assisted simulation with random covariates. INFORMS Journal on Computing, 35(2):386 2023.
[63] L. Li, W. Chu, J. Langford, and R. E. Schapire. A contextual-bane approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[64] Y. Li and Gao. On the finit--tmme performance of the knowledge gradient algorithm. In International Conference on Machine Learning, pages 12741-12764, PMLR, 2022.
[65] Z. Li and Scarlett. Gaussian process bandit optimization with few batches. In International Conference on Artificial Intelligence and Statistics, pages 92-107. PMLR, 2022.
[66] Y. Lin, H. Zhang, R. Zhang, and Z.-J. M. Shen. Nonprogressive diffusion on social networks: Approximation and applications. Available at SSRN, 2022.
[67] H. Liu, J. Cai, and Y.-S. Ong. Remarks multi-output gaussian process regression. Knowledge-Bass Systems, 144:102-12) 2018.
[68] A. G. d. G. Matthews, M. Rowland, J. Hron, R. E. Turner, and Z. Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint arXiv: 11271, 2018.
[69] T. V. Nguyen, E. V. Bonilla, et al. Collaborative multi-output gaussian processes. In UAI, pages 643-652, Citeseer, 2014.
[70] E. C. Ni, D. F. Ciocan, S. G. Henderson, and S. R. Hunter. Efficient ranking and selection in parallel computing environments. Operations Research, 65(3):821-838 2017.
[71] F. Opolka, Y.-C. Zhi, P. Liò, and X. Dong. Adaptive gaussian processes on graphs via spectral graph wavelets. In International Conference on Artificial Intelligence and Statistics, pages 4818 4834. PMLR, 2022.
[72] M. Pearce and J. Branke. Continuous multi-task bayesian optimisation with correlation. European Journal of Operational Research, 270(3):1074-1085, 2018.
[73] Y. Peng, C.-H. Chen, M. C. Fu, and J.-Q. Hu. Efficient simulation resource sharing and allocation for selecting the best. IEEE Transactions on Automatic Control, 1014)100132 2012.
[74] J. Russo, B. Van Roy, A. Kazerouni, I. Oshand, Z. Wen, et al. tutorial on thompson sampling. Foundations and Trends@ in Machine Learning, 11(1):1-96, 2018.
[75] I. O. Ryzhov. On the convergence rates of expected improvement methods. Operations Research, 64(6):1515-1528, 2016.
[76] I. O. Ryzhov, W. B. Powell, and P. Frazier. The knowledge gradient algorithm for general class of online learning problems. Operations Research, 60(1):180-195 2012.
14

---

[77] T. N. Sainath, O. Vinyals, A. Senior, and H. Sak. Convolutional, long short-term memory. fully connected deep neural networks. In 2015 JEEE international conference on acoustics, speech and signal processing (ICASSP), pages 4580 IEEE, 2015.
[78] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Iransactions on neural networks, 20(1):61-80, 2008.
[79] M. Semelhago, B. L. Nelson, E. Song. and A. Wächter. Rapid discrete optimization via simulation with gaussian markov random fields. INFORMS Journal on Computing, 33(3):915- 930, 2021.
[80] N. Srinivas, A. Krause, Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning. Omnipress, 2010.
[81] N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger. coormation-theorette regret bounds for gaussian process optimization in the bandit setting. IEEE transactions on information theory, 5865):3250-3265 2012.
[82] W. T. Stephenson, S. Ghosh, T. D. Nguyen, M. Yurochkin, S. Deshpande, and T. Broderick. Measuring the robustness of gaussian processes to kernel choice. In International Conference Artificial Intelligence and Statistics, pages 3308-3331, PMLR, 2022.
[83] S. S. Tay, C. S. Foo, U. Daisuke, R. Leong, and B. K. H. Low. Efficient distributionally robust bayesian optimization with worst-case sensitivity. In International Conference Machine Learning, pages 21 21180-2111 21204. PMLR, 2022.
[84] S. Vakili, K. Khezeli, and V. Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021.
[85] S. Wang, S. H. Ng, and W. B. Haskell. A multilevel simulation optimization approach for quantile functions. INFORMS Journal on Computing, 34(1):569- -8859995555580 2022.
[86] W. Wang and X. Chen. An adaptive two-stage dual metamodeling approach for stochastic simulation experiments. IISE Transactions, 50(9):820 836, 2018.
[87] W. Wang, H. Wan, and X. Chen. Bonferroni-free and wwwfffrrenncezoon-eeeibbe sequential elimination procedures for ranking and selection. Operations Research, 2023.
[88] C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
[89] J. Wu and Frazier. The parallel knowledge gradient method for batch bayesian optimization. Advances in neural information processing systems, 29, 2016.
[90] J. Wu, M. Poloczek, A. G. Wilson, and P. Frazier. Bayesian optimization with gradients. Advances in neural information processing systems, 30, 2017.
[91] G. Wynne and V. Wild. Variational gaussian processes: A functional analysis view. In International Conference on Artificial Intelligence and Statistics, pages 4955 PMLR, 2022.
[92] W. Xie, B. I.. Nelson, and R. R. Barton. A bayesian framework for quantifying uncertainty in stochastic simulation. Operations Research, 1239)114391 2014.
[93] W. Xie, B. Wang, and Zhang. Metamodel-assisted sensitivity analysis for controlling the impact of input uncertainty. In 2019 Winter Simulation Conference (WSC), pages 3681-3692, 2019.
[94] W. Xie, Y. Yi, and H. Zheng. Global-local metamodel-assisted stochastic programming via simulation. ACM Transactions on Modeling and Computer Simulation (TOMACS), (11:113334 2020.
15

---

[95] P. Xu, Z. Wen, H. Zhao, and Q. Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.01780, 2020.
[96] and A. Zeevi. Upper counterfactual confidecce bounds: new optimism principle for contextual bandits. arXiv preprint arXiv:2007.07876, 2020.
[97] H. Zhang, J. He, R. Righter, Z.-J. M. Shen, and Z. Zheng. Machine Gaaming-assisser stochastic kriging for offline simulation online application. Working Paper.
[98] H. Zhang, J. He, D. Zhan, and Z. Zheng. Neural network-assisted simulation optimization with covariates. In 2021 Winter Simulation Conference (WSC), pages 1-12. IEEE, 2021.
[99] D. Zhou, L. Li, and Q. Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 1 11492-11502 PMLR, 2020.
[100] Y. Zhu, D. J. Foster, J. Langford, and P. Mineiro. Contextual bandits with large action spaces: Made practical. International Conference on Machine Learning, pages 27428-2744 PMLR, 2022.
16


Reviews:
[{"review_id": "aVFuIynPU9", "reviewer": "Reviewer_jVXy", "summary": "This work proposes a NN accompanied GP model. It leverages NN to approximate the unknown reward function regarding the context variable and maintains a GP with the decision variable. By introducing NN, the proposed method offers a better approximation accuracy. Theoretical implications, including maximum information gain and regret bounds, are provided for the proposed method. The effectiveness of the proposed method is also supported by empirical evaluation on both a synthetic and real-world dataset. ", "questions": "Can the authors provide corresponding justifications or empirical evidence on the potential limitations of the proposed method mentioned in the weaknesses section? \n\nI am willing to adjust my rating based on the authors' response to my question above. ", "limitations": "See weaknesses. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. A well-motivated and well-designed algorithm with solid theoretical analysis of the statistical properties of the proposed model. \n2. The proposed model is flexible enough to be used together with different types of NN models. \n3. Empirical evaluation of a diverse set of tasks is included and shows the promising effectiveness of the proposed method.", "weaknesses": "1. Potential limitations of the model: Although NN could help enable a better approximation accuracy on the reward function regarding the context variable, the training of NN models may make the model computationally prohibitive. In addition, NN typically works well with a large amount of data, which may cause a cold-start issue when the proposed model is used. \n\n2. May need to include more metrics in the empirical evaluation, such as computation cost and prediction latency. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the valuable time, questions and comments. We find them very helpful. Please find our response to the comments below.\n\n\n$\\textbf{Comment 1: }$Potential limitations of the model: Although NN could help enable a better approximation accuracy on the reward function regarding the context variable, the training of NN models may make the model computationally prohibitive. In addition, NN typically works well with a large amount of data, which may cause a cold-start issue when the proposed model is used.\n\n$\\textbf{Response:}$ We admit that incorporating NN into bandit problems generally requires sufficient data to approximate the unknown reward function. Thus, the cold-start issue is brought to, in principle, all bandit algorithms that use NN. Compared with the algorithms that fully rely on NN (e.g., NeuralUCB and NN-UCB), our NN-AGP-UCB actually suffers less from the cold-start issue, which is supported by numerical results in Section 4.1. The reason is that, in existing NN-based bandit algorithms, NN is responsible for approximating the entire reward function. In comparison, for the NN-AGP model, NN is specially used for approximating the mapping from the contextual variable to the reward function, while the approximation regarding the decision variable is supported by GP. It has been widely accepted that GP generally requires less data than NN in practical applications, and therefore NN-AGP helps to ease the cold-start issue.\n\nMoreover, to further address the cold-start issue, the transfer learning technology [1] can be incorporated as mentioned in the conclusion section. We conduct numerical experiments and present the results in $\\textbf{Figure 1}$ of the document attached in the global response. Specifically, we consider an unknown reward function $f_{T}$ and we also have access to functions $f_{s},s=1,2,\\ldots,5$ that have a similar structure with $f_T$. We first sample each $f_s$ for 50 or 100 rounds and learn an NN-AGP model with these samples. The NN component in NN-AGP helps to transfer the knowledge from $f_s$ to $f_T$. That is, during the initial rounds of NN-AGP-UCB with $f_T$, we first fix the input layer of the pretrained NN and update the remaining layers with the new data, which is a widely-used transfer learning method named freezing. \n\nExperimental results indicate that transfer learning from similar tasks helps to address the cold-start issue, and NN-AGP-UCB with/without transfer learning will converge to the similar regrets as the round increases. We also not that, to the best of our knowledge, there has not been extensive work on transfer learning with NN-based bandit algorithms. These NN-based bandit algorithms largely rely on the neural tangent kernel (NTK) to address the exploration-exploitation trade-off when selecting the decision variable. However, it remains an open question on how to transfer the knowledge between different domains with NTK. In comparison, the exploration-exploitation trade-off in NN-AGP-UCB is supported by GP, and existing transfer learning technologies with NN can be easily adapted into our algorithm. Other methodologies for addressing cold-start in learning NN in an online setting can also be employed; see [2,3]. We will add a  remark addressing this to our revised introduction.\n\n\n\n\n\n\n\n$\\textbf{Comment 2: }$May need to include more metrics in the empirical evaluation, such as computation cost and prediction latency.\n\n\n$\\textbf{Response:}$ We appreciate this comment. We record 1) the training time that constructs the surrogate model based on the historical data and 2) the execution time that selects the decision variable after the contextual variable is revealed. We record the time (seconds) for exactly one round in the 50-th, 100-th, and 300-th rounds. We take the first set of experiments in Section 4.1 as an example and present the results in $\\textbf{Table 1}$ of the document attached in the global response.\n\n\nWe notice that CGP-UCB is the most efficient in training time since it employs a pre-specified GP model which does not update during iterations. The training procedure of CGP-UCB only requires matrix operations, which can be implemented efficiently. On the other hand, all the algorithms that involve NN require learning NN from data and longer training time than CGP-UCB. In terms of the execution time, NN-AGP-UCB requires similar time as CGP-UCB, since the selection of the decision variable of NN-AGP-UCB is based on GP as well. We also note that both NN-UCB and NeuralUCB are initially designed for finite selections of decision variables. Thus, the computational cost of the execution time is largely due to searching for the optimal decision variable from the discretized feasible set. We will add this information to the supplements. In addition, we consider sparse NN-AGP to alleviate the computational burden for future work; see also a discussion in Section 9 of the supplements.\n\n\n$\\textbf{References:}$\n\n$[1]$ Weiss, K., Khoshgoftaar, T.M. and Wang, D., 2016. A survey of transfer learning. Journal of Big data, 3(1), pp.1-40.\n\n$[2]$ Wei, J., He, J., Chen, K., Zhou, Y. and Tang, Z., 2017. Collaborative filtering and deep learning based recommendation system for cold start items. Expert Systems with Applications, 69, pp.29-39.\n\n\n$[3]$ Wolfe, C.R. and Kyrillidis, A., 2022. Cold Start Streaming Learning for Deep Networks.arXiv preprint arXiv:2211.04624."}, {"review_id": "is809hnG5x", "reviewer": "Reviewer_ZHPP", "summary": "This paper proposes a reward model, called the neural network-accompanied Gaussian process (NN-AGP) for solving contextual bandit problems where the space of contexts and the space of decision variables may be continuous. This model is an inner product of a neural network and a multi-output GP. The neural network captures the dependence of the reward function on the contextual variables while the GP is to model the mapping from the decision variable to the reward.  The authors propose the NN-AGP-UCB algorithm for this problem in the form of the upper confidence bound strategy. They derive the regret for NN-AGP-UCB as well as the maximum information gain in their setting. Finally, they provide the experiments to evaluate their proposed algorithm for complex reward functions, including those with time-varying dependence on sequenced and graph-structured contextual variables. \n\n\n", "questions": "- Please see the questions in the Weaknesses section. \n- It would be interesting if the authors take into consideration the influence of the proposed NN in their regret analysis, at least in the overparametrized regime. ", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper introduces a reward model for contextual Gaussian process bandits which is more general than the previous work by Krause el al [37] by employing a neural network to capture the dependence of the reward function on the contextual variables. This allows to use different neural networks appropriate for applications with diverse structures of contextual information. This is also demonstrated in their experimental results.\n- The regret analysis and the upper bound of the maximum information gain are provided under this model.  \n- The experimental results on different structures of context information are also a strong point of this paper.\n", "weaknesses": "- As defined, the reward model is an inner product of a neural network (NN) and a multi-output GP. This reward structure seems not natural compared to the ones which are entirely either GP or NN. In addition, there are also many possible combinations of a NN and a GP to construct a reward model. Therefore, a more general model would be better. \n- In the conclusion section, the authors claimed that the advantage of their approach is the approximation accuracy for the reward function and better performance on cumulative rewards/regrets. However, this is not correct. Using a NN to model reward in overparameterized regime allows the approximation accuracy for the reward function. Moreover, they said their approach has better performance on regrets. However, it is not clear which related works they are comparing with. \n- It lacks the comparison of the regret bounds of the proposed algorithm and related algorithms like NeuralUCB, NeuralTS, and NeuralLinUCB which use entirely a NN, and algorithms which use entirely a GP to model the reward function. \n\n    ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable time, questions and comments. We find them very helpful. Please find our response to the comments below.\n\n$\\textbf{Comment 1: }$As defined, the reward model is an inner product of a neural network (NN) and a multi-output GP. This reward structure seems not natural compared to the ones which are entirely either GP or NN. In addition, there are also many possible combinations of a NN and a GP to construct a reward model. Therefore, a more general model would be better.\n\n$\\textbf{Responses:}$ We completely agree with the reviewer on the many possible combinations of NN and GP. Our particular choice of combining a neural network and a multi-output GP as an inner product is motivated by the differentiation between the decision variable and the contextual variable. By doing so, we ensure an explicit GP expression for the decision variable $\\mathbf{x}$ once the contextual variable is observed in each round. Such design not only facilitates explicit quantification of reward function approximation uncertainty, guiding decision variable selection, but also provides theoretical regret bound guarantees. While there are various ways to combine NN and GP, a more general model might compromise the explicitness of the GP expression for $\\mathbf{x}$. Our approach leverages the strong flexibility and approximation accuracy of NN while preserving statistical properties of GP, and appears to have reliable numerical performance. We plan to add a detailed remark to reflect this helpful comment.\n\n\n$\\textbf{Comment 2: }$In the conclusion section, the authors claimed that the advantage of their approach is the approximation accuracy for the reward function and better performance on cumulative rewards/regrets. However, this is not correct. Using a NN to model reward in overparameterized regime allows the approximation accuracy for the reward function. Moreover, they said their approach has better performance on regrets. However, it is not clear which related works they are comparing with.\n\n$\\textbf{Response:}$ We thank the reviewer for the comment. We would like to clarify that the advantage of approximation accuracy of NN-AGP is over the joint GP model. We also admit that using overparametrized NN to model the reward function generally leads to better approximation accuracy provided sufficient data. However, there are two challenges of the algorithms that are entirely based on NN. First, there is no explicit uncertainty quantification of NN approximation. Thus, addressing the exploration-exploitation trade-off requires further approximation, which affects the performance of bandit algorithms. Second, the overparametrized NN requires sufficient data to train, which might not be applicable in bandit problems, especially in initial rounds. Therefore, our NN-AGP-UCB algorithm achieves better performance on regrets than both the algorithms that entirely rely on GP (CGP-UCB) and the algorithms that entirely rely on NN (NeuralUCB and NN-UCB), which are also supported by experimental results. We will revise the conclusion section to provide a more clear statement and more careful descriptions.\n\n\n\n$\\textbf{Comment 3: }$It lacks the comparison of the regret bounds of the proposed algorithm and related algorithms like NeuralUCB, NeuralTS, and NeuralLinUCB which use entirely a NN, and algorithms which use entirely a GP to model the reward function.\n\n\n\n\n\n$\\textbf{Response:}$ We thank the reviewer for the comment. In terms of the algorithm which uses entirely a GP model, CGP-UCB [1], we postpone the comparison to the supplements (the end of Section 8.1 on Page 18). Specifically, NN-AGP-UCB has a same bound of $\\tilde{\\mathcal{O}}\\left(\\sqrt{T\\gamma_T}\\right)$ as CGP-UCB, but is superior when the contextual variable dimension is high. In terms of the algorithms which use entirely a NN, we note that NeuralUCB [2], Neural TS [3] and Neural LinUCB [4] all consider the scenarios when the decision variable $\\mathbf{x}$ is selected from a finite set. In comparison, we consider that $\\mathbf{x}$ is selected from a continuous set (Line 87, Page 2). When performed on a finite feasible set $\\mathcal{X}$, our NN-AGP-UCB also has a regret bound of $\\tilde{\\mathcal{O}}\\left(\\sqrt{T\\gamma_T}\\right)$, where $\\gamma_T$ further depends on the kernel function of the GP component used in NN-AGP. When the kernel function has an exponential eigendecay (see Definition 1 in Line 242, Page 6), NN-AGP-UCB has a regret bound of $\\tilde{\\mathcal{O}}\\left(\\sqrt{T}\\right)$, matching the regret bound of NeuralUCB, Neural TS and Neural LinUCB as well.\n\n\n\n\n\n$\\textbf{Comment 4: }$It would be interesting if the authors take into consideration the influence of the proposed NN in their regret analysis, at least in the overparametrized regime.\n\n$\\textbf{Response:}$ We thank the reviewer for the constructive suggestion. In Section 7 of the supplements, we provide an algorithm NN-AGP-UCB+, which accounts for the neural network approximation error and performs more conservatively than NN-AGP-UCB. We also provide the regret bound of NN-AGP-UCB+. We agree that the overparametrized regime would be an inspiring direction for future work and the neural tangent kernel (NTK) can be employed to analyze the regret. \n\n\n\n\n$\\textbf{References:}$\n\n$[1]$ Krause, A. and Ong, C., 2011. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24.\n\n$[2]$ Zhou, D., Li, L. and Gu, Q., 2020, November. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning (pp. 11492-11502). PMLR.\n\n$[3]$ ZHANG, W., Zhou, D., Li, L. and Gu, Q., 2020, October. Neural Thompson Sampling. In International Conference on Learning Representations.\n\n$[4]$ Xu, P., Wen, Z., Zhao, H. and Gu, Q., 2020. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.01780.\n\n"}, {"review_id": "BJlcHd4MBk", "reviewer": "Reviewer_ThqQ", "summary": "This work studies the contextual bandit problem with the Gaussian process. Authors tried to use neural networks to learn reward functions and introduce one algorithm NN-AGP. Then conduct empirical evaluation and theoretical analysis for it.", "questions": "(1) In Figure 2, I am wondering why there is a big jump first and then starts dropping.\n(2) How about the running time cost (portion) of GP in this algorithm?", "limitations": "Strong assumption and incremental novelty.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Recently, the bandit community paid more and more attention to the neural network approximation. It is interesting to combine it with GP in bandits. Authors use extensive experiments to demonstrate its practicability and conduct rigorous regret analysis for it.", "weaknesses": "(1) This work is an extension of [37] but very similar is very high. The key difference from [37] is changing the reward function to the inner product of $g(\\theta)$ and $p(x)$, where $g$ is the neural network function and $p$ is the Gaussian process. The optimization of $p$ and the UCB-based exploration is adapted from [37]. But I don't see very novel aspects from $g$ except that it can be replaced by different neural network functions. Therefore, I think the overall novelty of this paper is limited. \n\n(2) The required assumption of regret analysis is strong. It requires that the space of $\\theta$ is convex and compact, but it is known the parameter space of neural network is non-convex and not compact. Moreover, the analysis is based on [37] and [34,35] (the information gain part). Authors may want to discuss more about [34, 35] from analysis aspect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable time, questions and comments. We find them very helpful. Please find our response to the comments below.\n\n$\\textbf{Comment 1: }$This work is an extension of [37] but very similar is very high. The key difference from [37] is changing the reward function to the inner product of $g(\\theta)$ and $p(x)$, where $g$ is the neural network function and $p$ is the Gaussian process. The optimization of $p$ and the UCB-based exploration is adapted from [37]. But I don't see very novel aspects from $g$ except that it can be replaced by different neural network functions. Therefore, I think the overall novelty of this paper is limited.\n\n$\\textbf{Response:}$ We thank the reviewer for the comment. Please allow us to clarify more of the novelty and associated comparisonal advantage of our work compared to the literature. Our work considers the contextual Gaussian process bandit problem, which was also addressed in [1] ([37] in main text) as well. The novelty of our proposed NN-AGP model lies in the innovative integration of both GP and NN models, which partially addresses the challenge of pre-specifying an appropriate joint GP model for approximating the reward function. Based on the numerical experiments, our approach outperforms the existing GP-based bandit methods by specifying the data-driven kernel function through the lens of neural networks. In addition, by employing different structures of neural networks (e.g., graph neural network), our approach is applicable to diverse application scenarios where the contextual variable is represented in complex forms other than a vector. We hope that the above clarification may partially alleviate the potential concern. \n\n$\\textbf{Comment 2: }$The required assumption of regret analysis is strong. It requires that the space of $\\boldsymbol{\\theta}$ is convex and compact, but it is known the parameter space of neural network is non-convex and not compact. Moreover, the analysis is based on [37] and [34,35] (the information gain part). Authors may want to discuss more about [34, 35] from analysis aspect.\n\n$\\textbf{Response:}$ We agree with the reviewer's comment that the parameter space of neural network is non-convex and not compact. In fact,  we would like to clarify that parameter $\\boldsymbol{\\theta}$ in our work does not represent the neural network parameters. The parameter $\\boldsymbol{\\theta}$ denotes the contextual variable that is input to the reward function (Line 82, Page 3 in our manuscript).\n\nCompared to assumptions on the neural network parameters, the assumption of convexity and compactness on the set of contextual variables appears to be more common; see also [1]. Indeed, for NN-AGP-UCB, this assumption can be relaxed to that $\\sup_{\\boldsymbol{\\theta}\\in \\Theta} \\\\{ \\\\{  |\\sum\\_{l=1}^m \\boldsymbol{g}\\_{l}(\\boldsymbol{\\theta})a\\_{l,q}  |  \\\\}\\_{q=1}^Q , \\\\{ |  \\boldsymbol{g}\\_{l}(\\boldsymbol{\\theta})  | \\\\}^m\\_{l=1}   \\\\}$ and $\\sup_{\\boldsymbol{\\theta}\\in \\Theta}||\\boldsymbol{g}\\left(\\boldsymbol{\\theta}\\right)||_2^2$ exist.\n\n\n\n\n\nIn addition, our theoretical analysis borrows ideas from [1] and [2], and we mention it in Section 8 of the supplements, considering the length of main text. We also include a comparison of our theoretical results with those in [1] in the supplements. We will discuss more about [1,2] from analysis aspect in the revised main text. \n\n \n\n\n\n\n\n$\\textbf{Comment 3: }$In Figure 2, I am wondering why there is a big jump first and then starts dropping. (2) How about the running time cost (portion) of GP in this algorithm?\n\n$\\textbf{Response:}$ We appreciate the opportunity to clarify the appearance of a ''big jump\" in Figure 2 of the main text. In fact, the mean of average regrets of all the compared algorithms decrease as the number of rounds increases and there is no ''jump'' in the numerical results. The ''jump'' in Figure 2 is actually the overlap of the shadowed regions of the curves, which indicate the standard deviation of average regrets. In contrast with Figure 1, Figure 2 is associated with a function with higher-dimensional decision and contextual variables. Consequently, there's heightened uncertainty in the initial stages illustrated in Figure 2. We will clarify the figure in the revised manuscript. \n\n\nIn terms of the running time, we record 1) the training time that constructs the surrogate model based on the historical data and 2) the execution time that selects the decision variable after the contextual variable is revealed. We record the time (seconds) for exactly one round in the 50-th, 100-th, and 300-th rounds. We take the first set of experiments in Section 4.1 as an example and present the results in $\\textbf{Table 1}$ of the document attached in the global response.\n\n\nWe notice that CGP-UCB is the most efficient in training time since it employs a pre-specified GP model which does not update during iterations. On the other hand, all the algorithms that involve NN require learning NN from data and longer training time than CGP-UCB. In terms of the execution time, NN-AGP-UCB requires similar time as CGP-UCB, since the selection of the decision variable of NN-AGP-UCB is based on GP as well. To sum up, the training time is largely due to learning NN from the data, while the execution time is for selecting a decision variable based on the GP model. We will add this information to the supplements. In addition, we consider sparse NN-AGP to alleviate the computational burden for future work; see also a discussion in Section 9 of the supplements.\n\n\n\n$\\textbf{References:}$\n\n$[1]$ Krause, A. and Ong, C., 2011. Contextual gaussian process bandit optimization. Advances in neural information processing systems, 24.\n\n$[2]$ Srinivas, N., Krause, A., Kakade, S.M. and Seeger, M., 2009. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995.\n \n"}, {"review_id": "n4YNcv6IsG", "reviewer": "Reviewer_9ysH", "summary": "The paper proposes extension of the Gaussian Process (GP) based contextual bandits to the contextual case, where the reward function is time and context dependent. The proposed method models the context dependency via a multi-output GP and its relationship to the actions via a neural network. The inner product of the outputs of the GP and the neural network determines the reward.", "questions": "It does not look clear to me what the purpose of Section 3.3. What do we expect from studying the maximum information gain aspect?\n\nWhy is the proposed method not compared against NeuralUCB also in queuing and pricing tasks?", "limitations": "The paper does not discuss the limitations of the proposed approach.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written, its language is clear, experiments thorough, results strong, and the theoretical analysis sound.\n\nDespite the theoretical depth of the work, the paper studies two challenging and interesting use cases as bandit problems: queuing with LSTMs and pricing with graph convolutional neural nets. This gives a paper a solid standing. The graph application comes nicely together with the kernelized nature of the reward definition.\n\nThe results reported in Figures 3-6 are intriguing.", "weaknesses": "Algorithm 1 has some novel aspects such as the way mu and sigma are calculated but the methodological novelty is rather incremental.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the valuable time, questions and comments. We find them very helpful. Please find our response to the comments below.\n\n$\\textbf{Comment 1: }$Algorithm 1 has some novel aspects such as the way mu and sigma are calculated but the methodological novelty is rather incremental.\n\n$\\textbf{Response:}$ We thank the reviewer for the comment. We recognize the extensive work done on GP-based methods. However, the novelty of our proposed NN-AGP model lies in the innovative integration of both GP and NN models, which not only enhances the performance but also broadens the applicability of the bandit algorithm.\n\nIn addition, our approach uniquely retains the GP structure regarding the decision variable $\\mathbf{x}$, maintaining the key statistical properties and explicit uncertainty quantification inherent to GP. This structure ensures that bandit algorithms utilizing NN-AGP can seamlessly leverage the power of established GP-based acquisition functions designed for different settings and scenarios. As a case in point, while our main text focuses on the UCB acquisition function, we also delve into other acquisition functions in Section 6 of the supplements. In conclusion, we specifically retain the existing methodologies for GP while incorporating the NN model to enhance the bandit algorithm performance.\n\n\n\n\n\n\n\n$\\textbf{Comment 2: }$It does not look clear to me what the purpose of Section 3.3. What do we expect from studying the maximum information gain aspect?\n\n\n$\\textbf{Response:}$ We appreciate this constructive comment. In Section 3.2, we prove that the cumulative regret in terms of rewards of the bandit algorithm NN-AGP-UCB is upper-bounded by $\\tilde{\\mathcal{O}}\\left(\\sqrt{T\\gamma_T}\\right)$. Here $\\gamma_T$ is the maximum information gain of the proposed model NN-AGP, and we study it in Section 3.3 to provide the upper bound on the cumulative regret as a function of the total number of rounds $T$. \n\n\n$\\textbf{Comment 3: }$Why is the proposed method not compared against NeuralUCB also in queuing and pricing tasks?\n\n$\\textbf{Response: }$We appreciate this constructive comment. In queuing and pricing tasks, the contextual variables are complex and represented by time series and graphs. We select the long short-term memory (LSTM) model and the graph convolutional neural network (GCN) to model the mappings from these contextual variables in our NN-AGP-UCB algorithm. In contrast, NeuralUCB (as well as NN-UCB) is designed for vector-valued contextual variables and employs fully connected networks (FCN). Therefore, NeuralUCB and NN-UCB are not applicable in queuing and pricing tasks because of the complex contextual variables.\n\n\n\n\n$\\textbf{Comment 4: }$The paper does not discuss the limitations of the proposed approach. \n\n$\\textbf{Response:}$ We appreciate this constructive comment. We will definitely follow the comment and enhance the discussion in the next iteration. One of the limitations of our work is the cold-start issue during the initial rounds. That is, there are no sufficient data for learning the neural network in NN-AGP. This issue can be addressed by the transfer learning technology [1]. That is, at the beginning of NN-AGP-UCB, we can retain some layers of the neural network in NN-AGP, which are previously learned in similar tasks. This incorporation with transfer learning is also mentioned in the conclusion section. \n\nTo illustrate the transfer learning technology with NN-AGP-UCB, we conduct numerical experiments and present the results in $\\textbf{Figure 1}$ of the document attached in the global response. Specifically, we consider an unknown reward function $f_{T}$ and we also have access to functions $f_{s},s=1,2,\\ldots,5$ that have a similar structure with $f_T$. We first sample each $f_s$ for 50 or 100 rounds and learn an NN-AGP model with these samples. The NN component in NN-AGP helps to transfer the knowledge from $f_s$ to $f_T$. That is, during the initial rounds of NN-AGP-UCB with $f_T$, we first fix the input layer of the pretrained NN and update the remaining layers with the new data, which is a widely-used transfer learning method named freezing. Experimental results indicate that transfer learning from similar tasks helps to address the cold-start issue, and NN-AGP-UCB with/without transfer learning will converge to the similar regrets as the round increases.\n\n\n\n\nAnother limitation is due to the computational cost of NN-AGP. As mentioned in the conclusion section, since NN-AGP retains a GP structure, it suffers from computational complexity with large data sets. For future work, we consider sparse NN-AGP to alleviate the computational burden; see also a discussion in Section 9 of the supplements. We will include a more detailed and explicit discussion on the limitations in the revised main text. \n\n$\\textbf{References:}$\n\n$[1]$ Weiss, K., Khoshgoftaar, T.M. and Wang, D., 2016. A survey of transfer learning. Journal of Big data, 3(1), pp.1-40.\n"}]

Author rebuttal:
We would like to thank the reviewers for their review and for providing us with valuable comments to improve our work. We have treated every comment to our best efforts. In addition to the point-to-point responses to each of the reviewer, we also attach a document in this global response, containing 1) a table recording training/ execution time and 2) a figure recording the average regrets in a transfer learning setting.

We record 1) the mean of training time that constructs the surrogate model based on the historical data and 2) the mean of execution time that selects the decision variable after the contextual variable is revealed. We record the time (seconds) for exactly one round in the 50-th, 100-th, and 300-th rounds. We take the first set of experiments in Section 4.1 as an example and present the results in $\textbf{Table 1}$ in the attached document.

We also include the experimental results of transfer learning with NN-AGP-UCB in $\textbf{Figure 1}$ of the attached document. Specifically, we consider an unknown reward function $f_{T}$ and we also have access to unknown functions $f_{s},s=1,2,\ldots,5$ that have a similar structure with $f_T$. We first sample each $f_s$ for 50 or 100 rounds and learn an NN-AGP model with these samples. The NN component in NN-AGP helps to transfer the knowledge from $f_s$ to $f_T$. That is, during the initial rounds of NN-AGP-UCB with $f_T$, we first fix the input layer of the pretrained NN and update the remaining layers with the new data, which is a widely-used transfer learning method named freezing. 




Meta-review: A good paper that incorporates neural networks into bandits, hence expanding its applicability and practical use. Please incorporate the reviewers' comments and suggestions in the camera-ready version.
Decision: Accept (poster)