Empirical analysis of representation learning and exploration in neural kernel bandits
Authors: Michal Lisicki
Arash Afkanpour
Graham W. Taylor
Venue: Submitted to ICLR 2023 (2023)
Keywords: neural bandits
contextual bandits
gaussian process
neural tangent kernel
neural kernel

Abstract: Neural bandits have been shown to provide an efficient solution to practical sequential decision tasks that have nonlinear reward functions. The main contributor to that success is approximate Bayesian inference, which enables neural network (NN) training with uncertainty estimates. However, Bayesian NNs often suffer from a prohibitive computational overhead or operate on a subset of parameters. Alternatively, certain classes of infinite neural networks were shown to directly correspond to Gausian processes (GP) with neural kernels (NK). NK-GPs provide accurate uncertainty estimates and can be trained faster than most Bayesian NNs. We propose to guide common bandit policies with NK distributions and show that NK bandits achieve state-of-the-art performance on nonlinear structured data. Moreover, we propose a framework for measuring independently the ability of a bandit algorithm to learn representations and explore, and use it to analyze the impact of NK distributions w.r.t. those two aspects. We consider policies based on a GP and a Student's t-process (TP). Furthermore, we study practical considerations, such as training frequency and model partitioning. We believe our work will help better understand the impact of utilizing NKs in applied settings.

Under review as a conference paper at ICLR 2023
EMPIRICAL ANALYSIS OF REPRESENTATION LEARNING AND EXPLORATION IN NEURAL KERNEL BANDITS
Anonymous authors Paper under double-bling review
ABSTRACT
Neural bandits have been shown to provide efficient solution practical se- quential decision tasks that have nonlinear reward functions. The main contributor that success is approximate Bayesian inference, which enables neural network (NN) training with uncertainty estimates. However, Bayesian NNs often suffer from a prohibitive computational overhead or operate on subset of parameters. Alternatively, certain classes of infinite neural networks were shown to directly correspond to Gausian processes (GP) with neural kernels (NK). NK-GPs provide accurate uncertainty estimates and can be trained faster than most Bayesian NNs. We propose to guide common bandit policies with NK distributions and show that NK bandits achieve state-of-the-at performance nonlinear structured data. Moreover, we propose a framework for measuring independently the ability of a bandit algorithm to learn representations and explore, and use it analyze the impact of NK distributions w.r.t. those two aspects. We consider policies based a GP and a Student's t-process (TP). Furthermore, we study practical consid- erations, such as training frequency and model partitioning. We believe our work will help better understand the impact of utilizing NKs in applied settings.
INTRODUCTION
Contextual bandit algorithms, like upper confidence bound (UCB) Auur et al., 2002) or Thomp- son sampling (TS) (Thompson) [933). typically utilize Bayesian inference facilitate both repre- sentation learning and uncertainty estimation. Neural networks (NN) are increasingly applied to model non-linear relations between contexts and rewards (Allesiardo al. 2014, Collier & Llorens] 2018). Due to lack of one-size- mie-szze-iit-all solution to model uncertainty with neural networks, various NN models result trade-offs in the bandits framework. [Riquelme et al. (2018) compared a com- prehensive set of modern Bayesian approximation methods in their benchmark, and observed that state-of-the-art Bayesian NNs require training times prohibitive for practical bandit applications. Classic approaches,
the other hand, lack complexity to accurately guide nonlinear policy. Fur- ther, the authors showed that the neural- method provides the best practical performance and strikes the right balance between computational efficiency and Bayesian parameter estimation.
Bandit policies balance exploration and exploitation with two terms: (1) a mean reward estimate and (2) uncertainty term (Lattimore & Szepesvári 2020). From Bayesian perspective those two terms represent the first two moments of a posterior predictive distribution, e.g. a Gaussian process (GP). Research neural kernels (NK) has recently established a correspondence between deep net- works and Gaussian processes (GP) (Lee et al., 2018). The resulting model can be trained more efficiently than most Bayesian NNs. In this work we focus on the conditions in which NK-GPs pro- vide competitive advantage over other NN approaches in bandit settings. Even though NKs have been shown lack the full representational power of the corresponding NNs, they outperform finite fully-connected networks in small data regimes (Arora et al.) (019b), and combined with GPs, suc- cessfully solve simple reinforcement learning tasks (Goumiri et al. 2020). NK-GPs provide a fully probabilistic treatment of infinite NNs, and therefore result in more accurate predictive distributions than those used in most of the state-of-ther art neural bandit models. We hypothesized that NKs would outperform NNs for datasets possessing certain characteristics, like data complexity, the need for exploration, or reward type. The full list of considered characteristics can be found in Tab. 2 We an empirical assessment of NK bandits using the contextual bandit benchmark proposed by

---

Under review as a conference paper at ICLR 2023
Riquelme et al. (2018). The obtained results show that NKs provide the biggest advantage in bandit problems derived from balanced classification tasks, with high non-linear feature entanglement.
Measuring empirical performance of bandits may require a more detailed analysis than rendered in standard frameworks, in which the task dimensions are usually entangled. Practitioners choosing the key components of bandits (e.g. forms of predictive distributions, policies, or hyperparameters) looking for the best performance on a single metric, may be missing a more nuanced view along the key dimensions of representation learning and exploration. Moreover, interactions between policy and predictive distribution may differ depending on particular view. In order to provide a detailed performance assessment we need to test these two aspects separately. For most real-worid datasets, this is not feasible as we do not have access to the data generating distribution. In order to gain insight into the capability to explore, Riquelme et al. (2018) created the "wheel dataset", which lets us measure performance under sparse reward conditions. We propose to expand the wheel dataset by parameter that controls the representational complexity of the task, and use it to perform an ablation study set of NK predictive distributions (He et al. 2020: Lee et al. 20200 with stochastic policies. We remark that our approach provides a general framework for evaluating sequential decision algorithms.
Our contributions can be summarized as follows:
We utilize recent results on equivalence between NKs and deep neural networks derive practical bandit algorithms.
We show that NK bandits achieve state-of-the-art performance on complex structured data.
We propose an empirical framework that decouples evaluation of representation learning and exploration in sequential decision processes.
Within this framework:
We evaluate the most common NK predictive distributions and bandit policies and assess their impact on the key aspects of bandits - exploration and exploitation.
We analyze the efficacy of Student's t-process (TP), as proposed by Shah al. (201)); Tracey & Wolpert (2018), in improving exploration in NK bandits.
We make our work fully reproducible by providing the implementation of our algorithm and the experimental benchmark. The explanation of the mathematical notation can be found in Sec. A
2 BACKGROUND
In this section we provide necessary background on NK bandits from the perspective of Bayesian inference. Our approach focuses heavily on the posterior predictive derivation and the Bayesian interpretation of predictive distributions obtained ensembles of withh deep neural networks. We build on material related to neural bandits, NKs, and the posterior predictive. We also point out the unique way in which the methods are combined and utilized in our approach.
2.1 CONTEXTUAL BANDIT POLICIES
Contextual multi-armed bandits are probabilistic models that at each round E [T] of a sequential decision process receive set of & arms and global context Xt. The role of policy an action E [k] and observe the associated reward Yt.o. We name the triplet (Xe, at, Ut,e,) an observation at time Observations are stored in a dataset, which can be joint (D) or separate for each arm (D.)) The objective is to minimize the cumulative regret Rr = E. D t= max, Yt,a
to select
E Vt,a.] or, alternatively, to maximize the cumulative reward ΣT Vt,ar.
Thompson sampling (TS) is a policy that operates on the Baycsian principle. The reward esti- mates for each arm are computed in terms of posterior predictive distribution p(y. D,.. 0) p(y- 0)p( 0 D. d0. Linear, kernel, and neural TS (Agrawal & Goyal, 2013, Chowdhury & Gopalan 2017 Riquelme al. 2018) are all contextual variants TS, which commonly model
"Code link temporarily hidden for blind review.
2

---

Under review as a conference paper at ICLR 2023
Predictive GP
1
NNGP
Xa.x(Xxx+*X) +yl xxx
Ka.e, - x
Deep Ensembles Randomized Prior
Ka,,, +0x xxxxxxxxxxxxxxxxx xx xx. -20 x xxx
O x +-l
Ka.a, xxxx(Oxx 71) 1xxx(xxx + 7I) 10xx.
-2xx 71) 1xx.
NTKGP
Ox.x x + '1)
Ox... xx,x Ox.
Table NK predictive distributions. Table reproduced from He ct al. 2020
the rewards in terms of GP feature regression 40 + where + (() and e ~ (O oy)- Assuming the prior for each parameter to be 0 (0, σe), the analytical solution the model i ($p 4 + 4p by y. where 7 is regularizer, and covariance matrix Σxx = $ tb Together
and Σxx parametrize the marginal predictive distribution used to obtain reward estimates Pa.t-
If the number of parameters p is larger than the number of samples it is advantageous apply the kernel trick to reduce the amount of computation, that is to use the identity (Ø o + +1) -
p- p"($5" + to convert the p x covariance matrix Σxx = (x)" ((X) into a smaller n x kernel matrix Kxx = K(X, X) = ((X) This results in a posterior predictive distribution:
p(y. D) N (K x (Kxx + ++ (Kx.. - xxxxx(xxx + 'Kxx))
This distribution was originally applied to bandits by Srinivas et al. (2010); Valko et al. (2013)
contextual bandit can be either joint or disjoint. A joint model (e.g. Chu et al. (001)) uses single kernel and makes predictions based on action-specific contexts, while disjoint model uses separate kernel per action, which is more suited for a global context scenario.
While TS offers explicit Bayesian interpretation, other stochastic policies, like upper confidence bound (UCB) (Auer et al.] 2002), can take advantage the same inference process, and use the moments of the predictive distribution to compute the reward estimates.
Neural bandits. Neural bandits are a special case of nonlinear contextual bandits, in which the function f fxx) is represented by neural network. The neural gurralygreeyy (e.g. Allesiardo et al. (2014)) approach uses predictions of a NN directly to choose the next action. It is considered a naive ap- proach, tantamount exploitation in feature space. Neural-linear (Riquelme al. 2018) utilizes probabilistic regression with 6(z) representing its penultimate layer features. Nabati et al. (2021) proposed limited memory version of neural-linear (LiM2), which uses likelihood matching to propagate information about the predictive parameters. This approach is in contrast to storing the data and re-training the network each iteration in order to prevent catastrophic forgetting.
2.2 NEURAL KERNEL DISTRIBUTIONS
We define neural kernel (NK) to be any compositional kernel (Cho & Saul 2009 Daniely et al. 2017) that mimics a state or behavior a neural network. We consider two recently proposed kernels: the neural network Gaussian process kemee (NNGP) (Lee et al. 2018), ,, K. and the neural tangent kernel (NTK) (Jacot et al.) 2020). O Both were shown to model the behavior of an infinitely wide network, and allow for training by means of Bayesian inference. He al. (2020) distinguished several NK predictive distributions, corresponding to common approaches in Bayesian deep learning (Tab. I..
The NNGP kernel models the network's 's output covariance at random initialization. It can be com- posed recursively, such that the kernel of each subsequent layer KC() denotes the expected covariance between the outputs of the current layer, for inputs sampled from GP induced by a kernel of the previous layer ((-1)) The output the last layer K. (L) induces a prior GP the Bayesian regression model and the NNGP posterior predictive can be obtained by inference (Tab. [].
Jacot et al. 2020) showed that the dynamics gradient descent optimization, when exam- ined from functional perspective,
be captured by another kernel, NTK, with general form V (xf Vo fXX",, and with the corresponding feature space covariance Z = (of(X) (x.( referred to the neural tangent feature matrix (NTF). In practice compute NTK recursively
3

---

Under review as a conference paper at ICLR 2023
1-1o
65
Noisy wheel dataset. The coordinates represent input features, and the colors represent classes. E regulates the complexity of the problem linearly w.r.t. the common baselines (Sec. B.3)
Figure 1:
- - (KC
L+1 I ic ) with dot denoting a gradient. For networks with ReLU activa- tions both NNGP and NTK become variants of the arc-cosine kernel (Cho & Saul (009).
In the infinite width limit the parameters change so little during the training (0(1/ LL),), where is the number of parameters) that the network can approximated with first order Taylor expansion about the initial parameters (Lee et al., 2020). That approximation is referred to as "linearized network". By putting a Gaussian prior of N (0; KC) on the functional form of the neural network, the linearized NTK model results in GP predictive distribution with moments outlined in Tab D- Deep Ensembles. This formulation given by Lee et al. (2020) (eq 16), who point out, however, that it does not admit the interpretation of Bayesian posterior, yet still be used predictive distribution. When a regularization term added to the GP, He et al. (2020) showed that this approach also corresponds to networks with randomized priors (Osband al.) 2018) (Tab. D. He et al. (220)) further attempted to remedy the lack of admittance as a posterior by adding the missing variance of the parameters of all layers except the last one, to the linearized network formulation, which resulted in the NTKGP distribution (Tab. Db.
3 METHODS
Our extensions designed to provide insights to the behavior of the NK bandits along the axes of Bayesian inference and exploration-exploitaiie expand the wheel dataset and provide grounds for analysis of differences among the posterior predictive distributions. We then discuss details of the main algorithm, with the emphasis on implementation considerations and the choice of posterior predictive. We close by discussing the conjugate prior approach to the posterior derivation.
trade-off. We begin this section with a proposal to way that lets decouple representation learning from exploration,
3.1 WHEEL DATASET AND EXTENSION
In the "wheel"" dataset the data organized in 2-D Euclidean space, such that Vr |||||| < 1. and classes are separated by inner circles that let us smoothly regulate the class proportions (e.g. & Abu-Mostafa (2006)). RRiquelme et al.] (2018) introduced bandit variant of the wheel dataset, which can be seen in the far left subplot of Fig. I The parameter 5 controls the proportion of the inner circle to the peripheral classes, which are given the highest rewards. By increasing we ask the algorithm to explore more in order to find the high reward classes. Our reward distribution follows directly from Riquelme et al. (2118) and is detailed in Sec. B.I
We propose extend the wheel dataset by an orthogonal parameter that regulates the representation learning difficulty. The "difficulty" established terms data complexity, following a body of work measuring the complexity of machine learning problems (Li & Abu-Mostafal 2006 Lorena et al. 2019). In order to generate the data, we morph the original wheel dataset such that predictably decays the performance of a specfied algorithm. In particular, propagate the wheel dataset through fully-connected MLP, initialized with random weights, w ~ NO, Van ). where
d()) is the number of input dimensions to a particular layer, and a scalar. In the experiments we use ReLU activation functions and L 5 fully-connected layers. The newly introduced "noise parameter" e causes the dataset to be warped nonlinearly and injects a moderate level of noise around samples. The effect of increasing create tasks of varying exploration and representation learning difficulty. More details on how the morphing influences complexity can be found in Sec. B.3 and in Fig.
be seen from left to right in Fig. [T] By varying d and e
4

---

Under review as a conference paper at ICLR 2023
3.2 NEURAL KERNEL BANDITS
Algorithm Neural kernel bandit with randomized prior posterior predictive distribution (disjoint)
Require: Number of arms k, number of rounds T, kernel regularization parameter 7, exploration parameter 77, NNGP kernel function K(:,-), neural langent kernel function ( initial
number of steps i, policy π
1: Play each arm sequentially for steps to accumulate data X R Na E R' Va for round 2. T do
2:
3: Observe context X
4: for arm a 1, ...... k do
5: Ko, f (X,, X.)
6:
Da. t -(( X.) +
7:
// Calculate predictive distribution moments
8:
Pa,t < xx, o
9:
0a. t- Kxxxx + xxx, Ka, 0 0x,x. -2 O xxx if IT is UCB then
10:
11:
Pa,t < Ma, 71/2 aatt
else i is TS then
13:
Pa,t ~ NHo 2o
14:
end if
15:
end for
16:
Choose arg max, Pa,t and obtain reward y/:
17:
Update (X., with (Xt, Vr
18:
end for
Our algorithm (Alg. is built using similar structure to classic kernel and GP bandits (Chowhhury & Gopalan 2017 Srinivas et al. [2100] Valko et al.) 2013). We compute GP moments Pa. and oa,t according Tab. by modilying the definitions of lines and As an example, in Alg. [ [we the randomized prior approach. We provide both UCB and TS variants of our algorithm. In each round an is chosen based on the highest estimate of the reward Pa.t- We use the disjoint approach as our primary model, which means that the data (Xa.ya) and kernels (NNGP K., and NTK ...,) are collected and computed separately for each arm a. The disjoint strategy preserves memory, while ensuring that better performing arms, chosen more frequently, have larger associated datasets and thus more certainty over time. This approach very much in line with classic optimism in face of uncertainty (OFU) methods. A common alternative is the joint model, which, in the case of GP, uses a single kernel and produces separate posteriors, albeit with a common uncertainty estimate, for each arm at prediction time. Using NKs in this manner for multi-class problems is common in the NNGP/NTK literature (e.g. Arora et al. (2019b); Novak et al. (2019)). However, the approach is not feasible in the bandit setting it assumes access rewards associated with all the arms. A common solution (e.g. Zhou et al. (0200) to use zero-padding to create a separate context vector for each X, [0.... 0, Xorig: O....,0 0). In the feature space this has an effect of splitting the model's parameters arm yielding separate uncertainty estimates.
3.3 STUDENT'S T-PROCESS
While our GP predictive distributions represent the posterior predictives with the fixed observation noise oy. we also analyze the behavior of the algorithm in conjunction with the joint prior. Linear and neural-linear models were shown by Nabati et al. (2021) and Riquelme et al. (2018) to benefit from applying a joint conjugate prior to both parameters of the likelihood, resulting in a Normal- inverse-Gamma distribution p(0, az)) p(0 ()))) When o, is not fixed, it continues to evolve with the data, which results in more accurate uncertainty estimates over time. The joint prior infer- sampled
ence be performed either by (1) two-stage sampling process, where parameters individually, and then used in the regression model, or (2) by a full predictive distribution derivation. We use the first approach in linear and neural-linear bandits. When using kernels, the parameters
5

---

Under review as a conference paper at ICLR 2023
NKTS (ours) NKB lours)
LinearTS LinearUCB
MultitaskGP NeuralLinearTS
NeuraLLineerTs NeuralGreedy
NeuralTS NeuralUCB
1.2
Norm. Cumulativv Roward
1.0
0.6
0.4
0.2
adult
census
covertype
fnanccil
jester
mushroom
stallog
Figure 2: Final normalized cumulative rewards (y-axis) of NK bandits compared against all other methods after 5,000 steps rollout on the respective UCI datasets (x-axis). Each bar shows the mean and standard deviation over 10 rollouts.
cannot be sampled, and require a full derivation, which results in a Student's 's t-process (TP):
p(y. D) -T Xx. (KKxxxxxx>
V + y xx - RR,, v v+n);
1 -
V + 12
(2)
v- 2 -Kxx.. Kx. xxxxxxxxxx - - K
The TP is related to the GP by having the same mean, but scaled covariance, by factor of レ- is known as "degrees of freedom", and controls the kurtosis. The lower v values result in heavier tails, and thus lead to more aggressive exploration. TP approaches GP as - oc, and can therefore be interpreted
generalization of the GP (Traeyy & Wolpert 2018). Correspondence to GP allows us to use the same NK-based distribution parameters in an unchanged form. To introduce make use of regularizer 7, although
finer control over performance, have the same interpretation as in the GP. The key advantage of TP over GP is that its variance depends both input and output data, rather than just inputs. The output variance introduced through the y" (Kxx - - y term, which represents the data complexity. This term will drift from the more the outputs deviate from the GP modelling assumption (Traeyy & Wolpert 2018).
note that does not
4 EXPERIMENTS
While NK bandits were proposed in the past, the work presented by Zhou et al. (2020): Zhang et al. (220)) focuses mainly on theoretical analysis and offers only limited empirical evaluation of an approach that can be considered a feature space variant of NTKGP. We conduct experiments to show that NKs provide a competitive approach bandit settings. We begin by evaluating our method on Bayesian bandit benchmark (Riquelme et al., 2018) and show that it achieves on-par better performance than state-of-the-art baselines on most the tested UCI datasets. We conclude that method should be considered by the community as one of the standard approaches for bandits with nonlinear reward models. Next, we utilize the noisy wheel dataset to assess the impact utilizing NK predictive distributions to accurately trade off exploration and exploitation. While no approach can adapt to all settings, we observe that NTKGP provides a significant improvement in sparse environments requiring large exploration. In addition the main results, assess the ability of the noisy wheel dataset to model complexity, and measure the implications of practical implementation considerations training frequency and model partitioning (Sec. B.4 Sec. B.3 and Sec. B.5
4.1 NK BANDITS OUTPERFORM NEURAL-LINEAR AND NTF BANDITS ON COMPLEX DATA
We tested the performance of NK bandits set of UCI datasets Dua & Graft 2019) used in the Bayesian bandit benchmark (Riquelme et al. 2018). We compared our method against the state-of- the-art neural-linear (Riquelme et al.) 2018 8) and neural-linear LiM2 (Nabati al. 2021 bandits, following their experimental setup. We report the mean and standard deviation of the cumulative re- ward over 10 runs. We included important baselines: linear TS / UCB and multitask GP, due their notable performance on simpler datasets. According to common practice in the field (Riquelme) al. 2018 Nabati al. 2021), we did not tune the hyperparameters of any algorithm. Unlike

---

Under review as a conference paper at ICLR 2023
in supervised learning, bandit benchmarks typically do not provide separate test set. Instead, pre-set the hyperparameters to values established by Riquelme et al. (2018). whenever applicable.
Due to differences in the NN architecture between Riquelme et al. (2018) and Nabati et al. (202I) in Tab. 3 we report the results for both settings. We used the neural -tangenss library (Novak et al,
2019) to obtain the NTK, NNGP kernel, and the mean and covariance of the predictive distributions. We computed the NKs based on a two-layer fully-connected architecture with ReLU activations and
regularizer 7 0.2. We chose the randomized prior GP (He et al., 2020 Lee al., 2020 Osband et al., 2018) as our preliminary experiments showed it to perform best on the majority of the selected UCI datasets (not shown in the paper). In light of the findings presented in Sec. 4.2 and the assess- ment by Riquelme et al. (2018) we suspect that deep ensemble and randomized prior distributions are more suitable for datasets like UCI, that require fewer exploration steps. We tested both UCB and TS policies with the exploration parameter 1) set to 0.1. As established by |Nabati et al. (202T), normalized cumulative rewards are computed w.r.t naive uniform sampling and the best algorithm for each dataset: www.:ccu__eeaaaaa = cum.reway reWunito
The results (Fig. 2) show that NK bandits constitute a competitive approach, achieving state-of-the art results on most datasets. The improvement is most apparent datasets with high non-linear entanglement and large number of features (> 50). Interestingly, we attain the highest performance boost on the covertype dataset, which is typically considered the hardest. We attribute the increase to accurate exploitation, achieved by application of NTK to nonlinear structured data problems (Arora et al. 2019b), and exploration, achieved through the appropriate choice of the predictive distribution. For linear datasets, linear methods tend to outperform non-linear ones, including ours. The same trend was noted by Riquelme et al. (2018) w.r.t. previous methods.
We recognize that scalability is current limitation of our method. Computing NTK requires large computational resources. In Sec. B we show two avenues for scaling up. with relatively low impact on performance. Disjoint arm treatment (Sec. B.5)) provides an opportunity for distributed comput- ing, while lowering the training frequency (Sec. [B.4) allows for considerable computational gain with minimal performance drop. We also note that current research directions provide promising avenues for significant scaling of our approach in the near future (Zandieh et al. 2021).
4.2 DECOUPLING REPRESENTATION LEARNING FROM UNCERTAINTY ESTIMATION
Decoupling representation learning from uncertainty estimation allows us to study each factor sep- arately and understand their impact on the overall performance of bandits. In the following ex- periment we utilize the noisy wheel dataset to measure the performance of 'SS and UCB policies combined with NK-induced TPs and GPs (Tab. [.. w.r.t. the varying factors of complexity e and the need to explore 5. We compared all methods by measuring their peripheral accuracy, i.c. the percentage of correctly chosen actions on the periphery of the wheel: pacc =E, [a; # aa]][aa, = E, * a²). We evaluated each algorithm a grid of (s. 8) pairs, where e's were spaced linearly, due to their linear impact on performance (see Sec. B.3), and 5's were spaced following pair. Each method was run for 5,000 steps and the results were averaged over 10 runs. Due to the large number of runs, we updated the model every 20 steps to speed up the computation (see Sec. B.4). All exper- iments were performed using a disjoint model with exploration parameter r) = 0.1. The distribution were regularized with 7 0.2. TP was initialized with v 12. The results are presented in Fig. 3
Riquelme et al. (011).. The grid was computed separately for each idistribution.poliyyy
While there is no single method that achieves the highest score in all circumstances, in average the NTKGP distribution provides the best performance w.r.f. the exploration-exploitaae predictive distributions and policies exhibit good performance close to the original wheel problem with 6 0.5 (Fig. 3 top left corner of each grid). and gradually worsen as problems become more complicated on both axes. The algorithms eventually fail when 8 = 0.99. We argue that a good bandit method should be able to adapt and sustain its performance longer as the problem becomes more complex and requires more exploration. In Fig. we can see that NTKGP clearly dominates on harder problems, especially in combination with Thompson sampling. This is indicated by almost uniformly higher scores (3rd column, 1st and 2nd row) and can be further verified by observing the histograms (rhs). The result is in contrast with our finding that the randomized prior distribution performed best on the UCI datasets. We believe that the difference is due to the reduced need to ex- plore in the UCI tasks (Riquelme et al. 2018). (top histograms) and Fig. further confirm that intuition by showing little distinction in performance when the need for exploration is small (low e).
trade-off. All
7

---

Under review as a conference paper at ICLR 2023
0.8
6.81
0.6
3.51
9.
petomane
6.6
2.4
15-1P
15:07
UCS
0.4
0.4
3.4
brsembli
0.2
12.2
2.2
2.2
MKGP
0.0
0.5
0.7
0.0
095
5:00
0.0
0.5
0.7
3.3
2.95
0.0
0.0
0.5
0.7
0.9
0.03
0.50
0.0
05
0.7
0.9
0.25 0.92
Fond froo
Ensemble
TS PNNG
TSTP-NTTKP
TSTP Rand Frier
.0.22 0.83
9:38 030 6.6
00089 0:32
2:40 002
2
0.58
0.4
2.28
22500
0.34
0.31
92
6.00
6.61
000
0.87
0.00
044
9.30
0.61
0.74
9.79 0.72
0:44
930 6.02
0.81 0:82
047
2:59
908
0.88
0.75
0:3
0.4
2.31
0.78 0.25
0.5
0.24 000
812
0.63 0:00
0.00
0.71 0:43
0.47
2:34
5.0
0:00
6.7
033
5.09
5.64
0.42
0:33
0.03
0.59 0.59 0.28
034 0.03
065 0:52
0.55
2.30
002
0.02
0.65
0:32
0.22
2.55
0:66
0.58
0.38
9:25 0.0
077 05
05 077
955
055
0.7
05
05 035
0.0
11g performance
TS-GP-Deep Ensemble
TS-GPANGP
TS-GP-NKGPP
TS-GP-Rand Prior
0.86 0.04 D: 024 5.00
0.89 0:81
06g 5:37 016
0.94 0.46 0.78 86
5:25
3.64 0:28
65a 0:45 0.55
0.02 0.01
0:50
0.00
0.09 0:02
2:30
912
0.00
0.70
2.33
2.01
0:25
0.0
0.73 0.60 0.36
017 2.00
0.73 0.24
0.42
2:33
3.0
0 0.78
0:52
0.43
2.26
0.72 0.63
0 0.27
0.4
2.0
0.0
0:22
0.02
0:
043
2:25
002
0.3
3.12
0.21
0:50 9:37
6.91
0:5 62
3:38
0.00
0
6.09
029
3.54
0.14
0.5 0.7 09 055 6:59
0.5 0.7
0.7 9.35
099
0.5 0.7 0.9 0.5 9:39
05 0.7
0.9 0.35 059
0.0
0.2
0.4
0.6
UCB
Ensemble
UCB NGP
UCB-NTKGP
UCB-Rand
032
5:0
.0:97 0.77 0:49 0.0 6.00
0.884 0.77
0.49 3.36
0.0
2-0.9
0.82
0:45
0.22
3.04
0.04
0.74
0.35
0.32
0.79 0.72
4:49 036 0:02
0.78 0:72
053
3:30
00c
0:02
0.73
0:45
0:3
3.00
5.63
0.1
1035351
0.61 0.5
3:23
016 p.
0.71 0:61
0:65
3:76
000
0.00 0.60
0:35
023
0.23
5.67 0.67
0.16
0:17
0.0
2.5
0.57
0.47
3.24
5.08
0:02
0:8
2.22
504
0.59
0.3
2.02
0.32
0:35
0.02
0,7
0.9
085
0.00
0.5
0.7
05
3.55
0.60
6.5
0.7
055
3.50
0.5
6.7
0.
0.45
0.0
0.2
0.6
0
peformance
Figure 3: Exploration and exploitation of NK predictive distribution (columns) in combination with bandit policies (rows). Grid cells represent peripheral accuracies. Histograms represent mean results (by method) over columns or rows respectively.
NTKGP was shown to provide more accurate out-of-distributin (OOD) and occasionally worse in- distribution predictions (He et al.] 2020). In bandits, the improved OOD performance crucial, due to its effect on initial exploration. After the uncertainty converges, it plays a significantly lesser role in overall performance. NTKGP was also shown by He et al. (2020) to make more "conservative" decisions on samples it is uncertain about. In the ensemble settings, studied He et al. (2020), this means that the algorithm utilizes uncertainty as its measure of confidence, and tends to take more confident, less extreme actions. In bandits we the larger uncertainty to produce an opposite effect, and decide to sample the uncertain regions more frequently, which facilitates exploration.
NNGP often performs better than deep ensembles and randomized prior distributions, but worse than NTKGP. It is interesting to see that a method based purely on the NNGP kernel outperforms more sophisticated distributions that combine both kernels. While deep ensemble and randomized prior approaches are well founded in representing NNs after training (Lee et al. 2018). NNGP distribution operates on randomly initialized network. However, NNGP and NTKGP are fully Bayesian approaches, while deep ensemble and randomized priors are not. The results suggest that the Bayesian interpretation may be advantageous in uncertainty estimation.
The deep ensemble distribution performs much worse than other methods, while not being the sim- plest to compute. This shows a large impact of the regularizer on the overall performance. In- terestingly, also the disparity in performance between deep ensemble and all other methods grows significantly as the data complexity increases. This disparity is less noticeable when changing the exploration parameter delta (compare with Fig. 5).
Fig. 3 shows that UCB has less variance in performance between the distributions. We attribute the lower variance to the fewer number of exploration steps that UCB performs over the rollout. Fewer exploration steps mean less reliance on uncertainty estimation, and thus smaller distinction between the tested predictive distributions. While we tried a limited sensitivity analysis for setting the 7 parameter to bring TS and UCB to similar performance, the results were inconclusive. We set 1 0.1 for both methods and leave more extensive assessment for future work.
8

---

Under review as a conference paper at ICLR 2023
5 RELATED WORK
The work of (Chu et al. 2011
Li et al. 2010) on linear UCB and (Agrawal & Goyal 2013) on linear TS motivated an abundance of research on regression bandits. GP-UCB (Srimivas et al. 2010) and
GP-TS (Chowdhury & Gopalan 2017) are special cases of kernel bandits (Valko et al. 2013). in which the ridge regularizer is set to Gaussian noise to form a GP. In practical applications, bandits are traditionally combined with well-known kernels, like linear, RBF or Matérn (Rasmussen &
Williams 2006). More recently a new family of neural kernels (NK) has emerged, which directly approximates the behavior of deep neural networks (NN) (Cho Saul| 2009 Danielyy et al. 2017). The neural network Gaussian process (NNGP) kernel is derived from forward pass of a NN, and corresponds to a NN with randomly initialized weights (Lee et al. 2018). The finding of a direct GP corrssonneenee was later followed by establishing a similar relation for linearized NNs and the neural tangent kernel (NTK), where NTK represents a network's 's dynamics during gradient descent
training (Arora et al. 2019a He et al. 2020, Jacot et al.. 2020 Lee al. 2020). A review of all recent NK-GP models, with connections to other existing uncertainty models, like deep ensembles and randomized priors (Osband et al.) 2018), can be found in (He al. 2020).
NeuralUCB (hou et al. 2020) and NeuralTS (Zhagg et al. 2020) are two related neural bandit poli- cies that can be considered feature space variants of NK bandits. They have an NTKGP posterior (He et al. 2020), whose moments are defined by a standard NN estimate and the neural tangent features (NTF) covariance (Sec. 2.2)) These algorithms were shown achieve a regret bound comparable to kernel bandits with the effective dimension induced by a corresponding NTTK (Zhou et al. 2020 Zhang et al.] 2020). Yet, they were shown to underperform in practical applications (Zhou et al, 2020 Zhang et al. 2020 Nabati et al., 2021), which was linked to overparametrization and poor covariance approximation Xu et al. 2020). Our work directly addresses these limitations.
The extended Kalman filter (EKF) provides another fully Bayesian treatment of all model param- eters that was also applied to neural bandits -Duran-Martin et al., 202T). The EKF approach was shown to be particularly suitable to online learning, it operates constant memory. In practice, however, the approach relies on dimensionality reduction to approximate parameters of a linearized network. The NK approach (NTK and NNGP), on the other hand, applies the law of large numbers and central limit theorem to construct an exact predictive distribution recursively from an infinite network, which is also linearized, but the method does not rely on further approximation. In this work we are interested in the NK approach, with the goal of testing the performance of neural bandits in the presence of exact uncertainty estimates.
CONCLUSIONS
In this paper evaluated NK bandits popular benchmark, comprising real-world (UCI) and synthetic (wheel) datasets. We proposed to guide the bandit policy by Student's or Gaussian pro- cesses corresponding common classes of infinite neural networks. We showed that our model outperforms the state-of-the-art methods on the majority of tasks. We also note that it performs best when the number of features is small, or when the reward highly non-linear. In addition, we ex- panded the wheel dataset (Riquelme et al.) 2018) to measure both the ability to explore and to learn complex representations. We used our proposed framework to evaluate the impact of NK predictive distributions on the two key aspects of bandits, exploration and exploitation, and showed that while there is no single distribution applicable to all scenarios, NTKGP combination with Thompson sampling is most robust to changes in the complexity and the need for exploration.
We consider several directions for further research. First, the limitation of our method is its scalabil- ity. While we offered several options with large performance to computation time ratios, we believe our approach can greatly benefit from kernel approximation methods, like Zandich et al. (202I). We then plan to investigate further the difference between TP and GP in handling the exploration and exploitation trade-off under varied conditions. Finally, our empirical framework could be used to analyze other fully Bayesian neural bandits, e.g. Duran- Martin et al. (2021). It would be also interesting to compare the exploration and representation learning trade-offs for other methods from (Riquelme et al. 2018). especially neural-linear that was said to benefit from decoupling.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff'.. In International Conference on Machine Learning, pp. 127-135. PMLR, 2013.
Robin Allesiardo, Raphael Feraud, and Djallel Bouneffouf. A Neural Networks Committee for the Contextual Bandit Problem. arXiv: 44098199 [cs]. September 2014. URL http://arxiv.
erg/abs/1405 91 arXiv: 1409.8191.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan L., Ruslan Salakhutdinov, and Ruosong Wang. On Exact Computation with an Infinitely Wide Neural Net. 1XXiv:990.11995 [cs, stat), November 2019a. /tt/ttt::/ /ttp//aaiivv.... org/ abs /1904/944000 11955
arXiv: 1904.11955.
Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks. arXiv:/9100 19.00006633 [cs, star), October 2019b. btRl:ttp::// wttp///aavvvv//a////e//eeeeaawvv http://wwwwvv....aa./eo/oe/
1910. 01663
arXiv: 1910.01663.
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2):235-256, May 2002. ISSN 1573-0565. doi: 10.1023/A: 1013689704352.
Youngmin Cho and Lawrence Saul. Kernel Methods for Deep Learning. In Ad-
vances in Neural Information Processing Systems. volume 22. Curran Asso-
ciates, Inc., 2009. URL https://papers: nips. /cc//aaper/200/haat)
Sayak Ray Chowdhury and Aditya Gopalan. On Kernelized Multi-armed Bandits. arXiv:1704.00444 [cs], May 2017. URL 1704.00445.
00445 arXiv:
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214. JMLR Workshop and Conference Proceedings, 2011.
Mark Collier and Hector Urdiales Llorens. (0f1::/800.0900 [cs, stat), July 2018. URL http:://anxxx..rrg/////111111
Deep Contextual Multi-armed Bandits.
arXiv: 1807.09809.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity. arXiv:1602.055: 058997 [cs, stat], May 2017. URL http: org/ http/////1...../ C5897
arXiv: 1602.05897.
Dheeru Dua and Casey Graff. UCT Machine Learning Repository, 2019. CtRlhttp://archhi ics. uci. www.ccccoee.. eduuml
Gerardo Duran-Martin, Aleyna Kara, and Kevin Murphy. Efficient Online Bayesian Inference for Neural Bandits. 1:Xiv:2/12.00/1 [es], November 2021. URI.
2112.00195
arXiv: 2112.00195
Imène R. Goumiri, Benjamin W. Priest, and Michael D. Schneider. Reinforcement Learning via Gaussian Processes with Neural Network Dual Kernels. arXiv:2004.055 0059999 [cs, eess, stat], April 2020.
a200//4/a.//00...////// 2000 C5198] arXiv: 2004.05198
Bobby He, Balaji Lakshminarayanan, and Yee Whye Teh. Bayesian Deep Ensembles via the Neural Tangent Kernel. arXiv:2007.00 2004000600.0844 [cs, stat], October 2020. URL http::p::///xxi.orr///b// 2007. 64
arXiv: 2007.05864.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks, arXiv:1806.07577 [cs, math, stat], February 2020. URL
07572
arXiv: 1806.07572.
Tor Lattimore and Csaba Szepesvári. Bandit algorithmss. Cambridge University Press, 2020. URL https://tor- att inotimmree. com/ /oww//www/// oads/book)
10

---

Under review as a conference paper at ICLR 2023
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep Neural Networks as Gaussian Processes. arXiv:1711.0011 [cs, stat),
March 2018. URL/ttp::/azxxi http://aaxxx..rraa///////// wwtp://./.aaaaatt........oo.b
00165 arXiv: 1711.00165.
Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. Journal of Statistical Mechanics: Theory and Experiment 2020(12): 124002, December 2020. ISSN 1742-5468. doi: 10. (01108//7422544//bbe22222 URL http:
(larxiv.or//a abs/ 902. 06720 arXiv: 1902.06720.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A Contextual-Bandit Approach to Personalized News Article Recommendation. Proceedings of the 19th international conference on World wide web wwW '10, pp. 661, 2010. doi: 10. (0.1145/177269011722))
URL htltt:::
//arxiv. www.iv..rg/aas///e
0146
arXiv: 1003.0146.
Ling Li and Yaser Abu-Mostafa. Data complexity in machine learning. 2006. Publisher: Califor- nia Institute of Technology.
Ana C. Lorena, Luis P. Garcia, Jens Lehmann, Marcilio C. P. Souto, and Tin Kam Ho. How Complex Is Your Classification Problem? A Survey on Measuring Classification Complexity. ACM Computing Surveys, 52(5):107:1-107:::5 September 2019. ISSN 0360-0300. doi: 10.1145/ 3347711. URL https: /oi /ttp://o...../1111111111.11111..
Ofir Nabati, Tom Zahavy, and Shie Mannor. Online Limited Memory Neural-Linear Bandits with Likelihood Matching. 0rXiv:2102.03793 [cs], June 2021.
/bs/
2102. 03799
arXiv: 2102.03799.
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. arXiv preprint wwXXiv:112.028820 2019.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. arXiv preprint arXiv: 2018.
C. Rasmussen and C. Williams. Gaussian processes for machine learning. The MIT Press, 2006. ISBN 1-262-18253-2 FRt::tRRR///tt//C/t URLLsttp:///aassaapproeee org. qpm1/
Carlos Riquelme, George Tucker, and Jasper Snock. Deep Bayesian Bandits Showdown: An Em pirical Comparison Bayesian Deep Networks for Thompson Sampling. 1802.09 [cs, stat), February 2018. URL/attp://arxiit wwg./iiii.rrr.ooooooo..o abs /00./ 09127, arXiv: 1802.09127.
Amar Shah, Andrew G. Wilson, and Zoubin Ghahramani. Bayesian optimization using Student-t Processes. In NIPS Workshop on Bayesian Optimization, 2013.
Niranjan Srinivas, Andreas Krause. Sham M. Kakade, and Matthias Seeger. Gaussian Process Op- timization in the Bandit Setting: No Regret and Experimental Design. arXiv:0912.3995 [cs], June 2010. doi: 10.1109/9T.21111111 1.122223... URL Otl.httpp//aarra....////////222. arXiv: 0912.3995.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285 294, 1933. Publisher: ISTOR.
Brendan D. Tracey and David H. Wolpert. Upgrading from Gaussian Processes to Student's-T Processes. 2018 AIAA Det-Determiiistic Approaches Conference, January 2018. doi: 10.2514/ 6.2018-1659, URL URL/ht:p::/arxxvoorr/////a
06147 arXiv: 1801.00 .61147
Michal Valko, Nathaniel Korda, Remi Munos, Ilias Flaounas, and Nelo Cristianini. Finite- Time Analysis of Kernelised Contextual Bandits. arXiv:1309 6869 [es, stat), September 2013. URL arXiv: 1309.6869.
http:/ // /awxivivvvvv. v. www./ar.////.oo.ooo.oo...o.....r 309, 6869.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural Contextual Bandits with Deep Representation and Shallow Exploration. arXiv:2012.0178: [cs, stat], December 2020. URL http:///wwwwv..og//////0/01022//
arXiv: 2012.01780.

---

Under review as a conference paper at ICLR 2023
Amir Zandieh, Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, and Jinwoo Shin. Scaling neural tangent kernels via sketching and random features. Advances in Neural Information Pro- cessing Systems, 34:1062-1073, 2021.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural Thompson Sampling. arXiv:2010.00827 [cs, stat), October 2020. URL http:t////xt...oortt wtt.://ggabb///......o arXiv: 2010.00827.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural Contextual Bandits with UCB-based Ex- ploration. arXiv: 11///911000 1et.1941104422 .0444046222 [cs, stat], July http:::://axxiv.or//////
04462 arXiv: 1911.04462.
A MATHEMATICAL NOTATION
We denote the training data by (X. E (X, and the test points by (x., y.). The input data composed of (x); where i E [r]], when we talk about predetermined set. Alternatively the data points can be indexed by time
[T] in the context of bandits, where the data is collected sequentially. When a subset of data associated with a specific action we put it in a subscript, i.c (Xa. ya). Parameter vectors are denoted by 0 and the reward estimation models by The dimensionality of both the feature vector and the parameter vector denoted by p. i.. I2 and <(x) Rº. In the linear case (xx) x, also x R" We denote a generic kernel matrix by K and the associated kernel function by -(:-), such that Kxy = yx. We use x, for a general test input in the context of Bayesian inference, or x when the input is given a specific time L. We denote test predictions by or yt- When we talk about the potential rewards from all actions, e.g. in the context of regret, we add subscript denoting the action, i.e. Vt,,, for the reward associated with the chosen action ag. and Vt.o a for rewards associated with action a.
X + V
B EXPERIMENTAL SETUP
B. DATASETS
Table provides an summary of the key properties associated with each of the UCI datasets we considered. While RRiquelme et al.] (2018) Nabati et al. (2021) used the same datasets, there are subtle differences in the way that they were implemented. Most notably, Nabati et al. (202I) use the "adult" dataset to classify income bracket, while Riquelme et al. 2018 use it to classify occupation. In case any discrepancies we followed Nabati et al. (2021)* set up for UCI datasets. In the (noisy) wheel dataset used the same reward distribution parameters proposed by Riquelme et al. (2018). The reward for guessing the inner circle class (i.e. where ||=|| S 6) is Tsmall
N 0.05). The reward for the correct peripheral class (sample classified correctly) is Tbig (50; 0.01), while perripheral ~ N(1 (105)..)).
B.2 UCI EXPERIMENTATION TIME ANALYSIS
We complement our results by reporting the average (over 10 runs) times per round that our algo- rithms took w.r.t. the neural-linear approach (Tab. 4. As the times grow with increasing number of collected data points, we report the shortest, median, and the longest average round. Both TS and UCB variants of our method tend to be about 5 times slower than the LiM2 approach, taking around 2 seconds for the longest round. The total times can be further reduced for some applications by performing less frequent updates, described in Sec. [.. However, additional study would need to be conducted to check for a similar effect in neural-linear approaches.
B.3 COMPLEXITY ASSESSMENT OF THE NOISY WHEEL DATASET
SVM performance is one of the standard metrics for empirical assessment of the complexity of problem (Li & Abu-Mostafal 2006 Lorena et al. 2019) In Fig. 6 we measured performance of
For adult and census datasets the categorical features are subsequently encoded with one hot vectors, resulting in 80 features for adult and 370 features for census. The numbers vary due to subsampling.
12

---

Under review as a conference paper at ICLR 2023
0.03
0.06
0.09
0.09
0.05
0.10
1.0
0.03
0.04
0.09
0.10
0.03
0.08
155
0.04
0.03
0.10
0.10
0.04
2.0
0.04
0.06
0.09
0.09
0.04
0.06
0.08
0.5
0.7
0.9
0.95
0.99
Figure 4: Standard deviations across tested methods (Fig. reveal regions greatest differences in performance, which can be used to rank methods.
Deep Ensemble
NNGP
NTKGP
Rand Prior
TS-GP
TS-TP
UCB
% peripheral actions
0.6
0.5
0.5
0.4
0.4
0.3
2
3
2
3
1
2
E
E
TS-GP
TS-TP
UCB
% peripheral actions
0.75
0.75
0.75
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.6
0.8
1.0
0.6
0.8
1.0
0.6
0.8
1.0
5
Figure 5: Percentage of correct peripheral actions, averaged across policies and a missing dimension (Ó in top row, and e in bottom row) for the experiment presented in Fig. 3 The aggregates provide clearer view of the average rank of each NK distribution.
nk svm_rbf
1.0
Peripheral Accuracy
0.9
wmm_poly
0.7
0.6
0.5
0.4
0.5
1.0
1.5
2.0
2.5
3.0
Figure 6: Baseline peripheral accuracy drops linearly we increase the level of noise e in the noisy wheel dataset. The result further supports as a sufficient proxy for problem's complexity.
13

---

Under review as a conference paper at ICLR 2023
3 baseline supervised approaches: NK ridge regression, SVM with RBF kernel, and SVM with polynomial kernel. Each method was run 10 times. The results show that the noise parameter increases the difficulty of the problem linearly in the chosen range from the performance perspective when no additional hyperparameter tuning is done.
B.4 TRAINING FREQUENCY
Frequent updates of complex models in bandit settings put high demand on compute resources. We measure the sensitivity of our method to the number of actions taken between subsequent model updates. We ran our NK bandit for numbers of actions specified the recent literature (Nabati al,)
2021 Riquelme et al. 2018): {1, 20, 100, 400), and report their respective cumulative rewards on the UCT datasets after 5,000 steps. Fig. 7 shows a smooth degradation in performance as the number of actions increases, which is expected. We note, however, that the degradation is relatively small and preserves competitive performance on all tested datasets. As large numbers of actions help to significant amounts of computational resources, provides a strong argument for applicability to real world scenarios. It also positions our method as good candidate for a limited memory approach, which we leave for future work. For some datasets, we observe significant spike in performance at actions before retraining, The result suggests an additional role the training frequency plays in the exploration-exploittion trade-off. also show the results of the best performing models, other than our method, as reported in Fig. We observe that for some datasets of higher complexity (e.g. covertype). our method's rank w.r.t. other algorithms is not affected, even with large numbers of actions before retraining, which additionally confirms its robustness.
believe that the sustained performance
Fig.
B.5 JOINT MODEL
compared the performance of joint and dis- joint models and noticed a considerable improvement in the last epoch performance for linear and stochastic datasets (financial and mushroom), slight improvement for datasets of medium complex- ity, and large deterioration for some of the most difficult datasets - covertype and jester. When examined from resource usage perspective, however, the joint model underperforms considerably. This result is significant, as most neural bandits use joint (NeuralUCB, NeuralTSS) or partially joint (neural-linear) model. overall number of kernel entries, while in the case of parameter space models observe the oppo- site effect. We can only create disjoint model at the expense of introducing additional (k - 1) number of parameters, which puts burden resources. Our result highlights this difference. and can help practitioners assess the impact of choosing joint or disjoint models when using NK bandits.
Following the zero-padding approach (Sec. 3.2
important to note that in functional space disjoint model reduces the
14

---

Under review as a conference paper at ICLR 2023
Table 2: Summary of the UCI datasets used in the experiments.
Dutaset
Description
Distinguishing factor(s)
Reward
Context
Adult
prodict income based per- sonal information
binary classification
13
50k
binary
categorical
iinteger
Census
predict occupation based on personal information
multivariate classification; large num-
67
250k
binary
categorical
ber of features
/ integer
Covertype
type forest coverage in var- lous areas
multivariate classification; requires
hinary
categorical
nonlinear models (Riquelme et nl. 2018
integer
Financial
stock prices from NYSE
Tinear problem; easy over-explore
4k
continuous
continuous
NASDAQ
joke recommender system
inputs and ourputs same domain imbalanced stochastic rewards; captures aspects classification regression
continuous continuous
continuous cutegorical
Mushroom
poisonous vs, safe mush-
117
10k
rooms
Statlog
space shuttle flight indicators
multivariate clossification; ploration; one arm optimal 80% of time: requires nonlinear models [Riquelme al. 2018
45k
binary
integer
Table 3: Neural-linear methods compared over two significant hyperparameter settings.
adult
census
covertype
financial
jester
mushroom
statlog
NK-T8 0.2
4119
3152
3402
4407
16779
1234
4052
4720
NK-TS 2- =
4113
3186 29
3441 36
4162 : 276
16856
1212
2016 = 3677
4820 1:32
NenralLineaarTS L= 50
3970 36
2557 5:54
2698
4358 363
12552 1875
11111 + 336
4771 13
NeuralLinearTS
100
3927
NeuraLLinca/T-LLM22 =1mmmm 50
4044 1
2726 36
2745 = 141
4485 : 360
14333 1339
10962 : 1070
4816
NeuraL.ineurT--LMM 2m 100
3993
39
2304 217
2748 85
4357 366
12325
1005
10915 1 631
4872
Table 4: Times per epoch [sec] (min median max) rounded to 2 significant figures.
consus
covertype
jester
mushroom
statlin
NIK-TS
0.0/0.8 2:25
0.0/0.07/ 193
0./00.64/.44 2.47
0.070.02/ 1.79
0.9/0.451 / 1.62
0.8/0.82 /2006
0.8/0.85/2 2.42
NTK-ICC
0.0/0/// 1.85
0.0/0.07 2.04
0D/00.1/ 00/00/1/200
0.000.2 2.04
0.0/044/1 10044/11 1.15
0.0/8.82
4.81
n.D/0.85/ 2.81
JoimNTK-TS
(.67:09//2 /5.68
00/28:55
0./0.97 01099/220 2.43
0.00033 /2.11
0./0992
01192/21 2.87
0.68 0.34 2.47
0.D/ / 44.13
JUC
0.67:091
0.0/.0//49
00/0.97/3.56
00/083/2.27 2.22
0.0/039/2.35
0.67/ /244
0.0/0.81/ /
IncarT
0./000/12
0./008/1.3
0D/0.0/1.24
00/00/0096
0./00//1.2
0.02/0.0/0.33
0.06/0.1/0.36
0.36
203//0.9/000 0.33
0.02/
0.033/003..3
/0.00
adult
cowertyyp
financial
jester
m.shmom
stetlog
Cum. revard 110")
20
37
7.5
2.8
20 300
450
20 300
403
25 300
200
20 260
400
20 320
400
20 105
400
20 320
400
Figure 7: Performance w.r.t. (1, 20, 100, 400} actions before retraining.
NKTT
JointNK-TS
NK-UCB
JOB
0:00
2:45
1:50
0.00
1:50
3:00
0.00
1:20
0.02
0:30
2:50
0.00
0-40
2:10
0.00
0.40 [16mmn))
1:1
0:30
3:40
2:30
[hrmm)
(brmm))
[hrmm)]
[hemm))
1ime (16mmk))
1ime
(10mms)
Figure& 8: Cumulative rewards w.r.t. running times of a joint and a disjoint variant of our method.
15


Reviews:
[{"review_id": "z-hTmAOyw7", "reviewer": "Reviewer_tHKv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper the authors propose an empirical analysis of neural kernel bandits, proposed as a UCB based alternative to Bayesian neural networks. Bayesian NNs have a high computational requirement as often an ensemble must be maintained in order to bootstrap a sample from the posterior, as in the case of Thompson sampling. The paper studies a version of kernel UCB where the kernel is realized by a linearized neural network in the limit where the width of the network goes to $\\infty$. The experiments compare against other neural network based bandit algorithms and show that there is a benefit for using NK bandits in terms of generalization ability and computational requirements. th authors also propose a practical setting where the ability of the algorithm to learn representations is studied and show a benefit for using NK bandits here.", "summary_of_the_review": "- I believe that the studied algorithm is not super significant and misses the point of neural network function approximation.\n- I believe that there are scaling issues with the algorithm that cannot be easily resolved in spite of some proposed approaches. I think it requires a larger scale empirical study to assess whether these algorithms actually are statistically and computationally efficient.\n\nGiven these two facts, I propose a reject/weak-reject rating for the paper.", "strength_and_weaknesses": "The paper consider NK bandits, or as studied in [1], termed as NeuralUCB_0 type algorithms.\nIn the highly cited paper [1], it is shown that when the neural network representation is allowed to change while training, and the changing representation is used to compute uncertainty estimates, the algorithm outperforms the fixed kernel representation based algorithms. This is in contrast to the results presented in this paper, which show the opposite phenomenon.\n\nAs the scale of the problem grows, the authors themselves remark in the paper that the complexity of computing the neural kernel is significant. However, the proposed solutions in the paper to remedy this issue are not satisfactory in my opinion.\n\nI also generally find it uncomfortable that the authors study an algorithm which does not use the ability of a neural network to learn a good representation for a problem, and rather use a fixed representation that an infinitely wide network would realize. While there are theorems showing equivalence in a highly overparameterized limit, this is not the typical limit in which practical multi-layer neural network architectures operate. As such the studied algorithm is inherently linear, and so I do not expect it to outperform nonlinear bandit algorithms as the problem scale grows.\n\n\n[1]: https://arxiv.org/pdf/1911.04462.pdf", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jwbuniJ85Dc", "reviewer": "Reviewer_r846", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper performs an empirical study of neural kernel bandit algorithms, to investigate the efficacy of these algorithms from different aspects such as representation learning and exploration ability. To achieve this, the paper has proposed a novel benchmark for contextual bandits which allows separately evaluating the efficacy of an algorithm in terms of representation learning and exploration.", "summary_of_the_review": "I think the paper provides some important empirical insights regarding neural kernel bandits. I have an important concern which is the first one listed under \"Weaknesses\" above, which is regarding some discrepancies with the observations from recent works on neural bandits which explicitly use NNs for reward prediction. If this concern is addressed well, I'll be happy to increase my evaluation.", "strength_and_weaknesses": "Strengths:\n- The empirical insights drawn from the empirical evaluations of this paper are interesting and can be of interest for the neural bandit community and the bandit community in general.\n- The proposed benchmark with the additional ability to evaluate the ability of an algorithm to learn representation is also interesting and can be potentially useful for the broader community.\n\nWeaknesses:\n- My biggest concern is regarding the comparison with the recent works on neural contextual bandits which explicitly train a neural network to predict the reward, including NeuralUCB and NeuralTS. **Firstly**, Figure 2 shows that NeuralUCB and NeuralTS are consistently outperformed by LinearUCB and LinearTS. This is surprising to me, because in the previous papers on NeuralUCB (Zhou et al., 2020) and NeuralTS (Zhang et al., 2020), they have both also performed experiments using the UCI datasets and had shown that both NeuralUCB and NeuralTS consistently outperform linear bandit algorithms. What's the reason for this discrepancy between your observations and theirs? **Secondly**, it is mentioned in the Introduction that \"...NKs have been shown to lack the full representational power of the corresponding NNs...\". The same statement has also been made by a few other papers such as NeuralUCB. As a result of this, the use of a neural network to predict the reward (i.e., using an NN as the term $\\mu_{a,t}$ on line 8 of Algorithm 1) is important for achieving good performances in neural bandits. Therefore, it is surprising that NeuralUCB and NeuralTS, which indeed use NNs for reward prediction, are significantly outperformed by the proposed algorithm which does not use NNs for reward prediction. Furthermore, in fact, the NeuralUCB paper also proposed another algorithm NeuralUCB0 which does not use NNs for reward prediction but instead simply treats NTK as a kernel in kernelized bandits. In this sense, NeuralUCB0 is similar to the proposed algorithm when NTKGP is used. But in their paper, they have shown that this NeuralUCB0 is consistently outperformed by NeuralUCB, which they have attributed to the fact that NeuralUCB0 does not use NNs for reward prediction.       \nThese two concerns here have broader implications, regarding whether it's useful/necessary to explicitly use an NN to predict the reward.\n- The technical contribution of the paper may be limited, since the proposed algorithm is a straightforward combination of existing methods.\n- Section 3.2: If I understand correctly, for the disjoint model, when estimating the posterior distribution for the reward of an arm, you only use the previous observations collected for this arm? So the observations from all other arms are not used? Isn't this a waste of data? Please clarify whether I misunderstood.\n- It's unclear to me which step of Algorithm 1 requires training a neural network?\n- (minor) Section 2, first paragraph, third line: \"inite-width\" should be \"infinite-width\".\n- (minor) Section 2.1, second last paragraph, first line: UCB is in fact not a \"stochastic\" policy.\n\nOther comments:\n- A concurrent work (paper [a] below) has also empirically evaluated neural kernel bandit algorithms in other real-world problems of autoML and reinforcement learning, and hence should be referenced.       \n[a] Sample-Then-Optimize batch neural Thompson sampling, NeurIPS 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "f6N-90YSZl", "reviewer": "Reviewer_st6H", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Established in deep learning literature that Neural Network (NN) is related to Neural Kernels (NK), especially between the optimization dynamic of infinitely wide NN has shown to be mostly captured by the NTK at initialization. Motivated by the correspondence, this paper proposed to guide bandit policy with NK-GP (or NK-TP to take account for varying noise level in feedback), which gives both reward predictions and uncertainty estimations at the same time. Their main algorithm and its variants are referred to as NK bandits.  \n\nEmpirically, this work shows NK bandits outperform other baselines on most of the tested UCI datasets.\n\nAs another claimed contribution, this paper designed a framework to empirically measure one bandit algorithm’s ability to learn representation and that to do exploration separately. \n\n", "summary_of_the_review": "This work makes contribution by empirically comparing different bandit policies on nonlinear data and proposing a novel way to indepedently measure representation learn and exploration as well. But it is limited by not providing substantially improved method from existing work for the purpose of solving nonlinear bandits and not much insights on NK bandits that generally apply to applications were drawn from the experimental results.\n", "strength_and_weaknesses": "**Strengths**:\n1. It gives a comprehensive side by side comparison between different bandit policies on nonlinear structure data: methods include NK bandits (multiple variants),  neural-linear (LiM2) bandits, neural bandits, linear TS / UCB and multitask GP.\n2. Proposes a way to measure one algorithm’s ability to learn representation and the ability to do exploration, by regulating the bandit environment with the tuple $(\\epsilon, \\delta)$, whose two components are controlling the learning complexity and the exploration urgency respectively.\n \n**Weaknesses**:\n1. Algorithmic novelty: it feels to me that the NK bandit policies proposed in this work are not substantially different from existing NK bandits, especially the $NeuralUCB_0$ by [Zhou et al.](http://arxiv.org/abs/1911.04462) in Appendix E, except for using separate kernels for different actions. There is some discussion in section 3.1 addressing this difference, but not sure if the separate kernel is a substantially improved design for general non-linear bandits or only fits for classification-converted bandits.\n2. Results interpretation: While the paper gives a thorough description of experiment results, the interpretation is less inconclusive. Also, the wheel dataset designed to separate representation learning and exploration is somehow simple in structure due to the low-dimensionality in context ( which I assume to be $2$ if directly following the setup in [Riquelme et al.](http://arxiv.org/abs/1802.09127)). So it’s questionable whether the results give insights of NK bandits that generally apply to applications.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JRxbMZiwMn", "reviewer": "Reviewer_uxKz", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents am empirical comparison between the performance of various neural kernels used in GPs for contextual bandit optimisation.  Comparisons are done using a modified wheel dataset, and the use of the student t-process to improve exploration in NK bandits is explored.", "summary_of_the_review": "The paper is well written, but as this boils down to a comparison of kernels in GPs I feel that there is insufficient novelty here to warrant acceptance.", "strength_and_weaknesses": "The background is interesting and the various NN kernel do have some potential for use in GP models for sequential model-based optimisation and bandits.\n\nMy main difficulty with this paper however is that, in the end, it appears to come down to a simple experimental comparison of various kernels, some of which happen to derive from various models or analysis of neural networks.  I am not convinced that this suffices to have a significant impact.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject