Learning Neural Contextual Bandits through Perturbed Rewards
Authors: Yiling Jia
Weitong ZHANG
Dongruo Zhou
Quanquan Gu
Hongning Wang
Venue: ICLR 2022 Poster (2022)
Keywords: contextual bandit
neural bandit

Abstract: Thanks to the power of representation learning, neural contextual bandit algorithms demonstrate remarkable performance improvement against their classical counterparts. But because their exploration has to be performed in the entire neural network parameter space to obtain nearly optimal regret, the resulting computational cost is prohibitively high.  
We propose to perturb the rewards when updating the neural network to eliminate the need of explicit exploration and the corresponding computational overhead. We prove that a $\tilde{O}(\tilde{d}\sqrt{T})$ regret upper bound is still achievable under standard regularity conditions, where $T$ is the number of rounds of interactions and $\tilde{d}$ is the effective dimension of a neural tangent kernel matrix. 
Extensive comparisons with several benchmark contextual bandit algorithms, including two recent neural contextual bandit models, demonstrate the effectiveness and computational efficiency of our proposed neural bandit algorithm.

Published as a conference paper at ICLR 2022
LEARNING NEURAL THROUGH PERTURBED REWARDS
CONTEXTUAL
BANDITS
Yiling Jia', Weitong Zhang', Dongruo Zhou', Quanquan Gu², Hongning Wang' 'Department of Computer Science, University of Virginia
*Department of Computer Science, University of California, Los Angeles. yj9xsévirginia edu, wt zhang @ucnanguulla...mmm edu, drzhoulcs ucla. qguêcs www.ucllaccc.o hw5x@virginia. edu
ABSTRACT
Thanks to the power of representation learning, neural contextual bandit algo- rithms demonstrate remarkable performance improvement against their classical counterparts. But because their exploration has to be performed in the entire neu- ral network parameter space obtain nearly optimal regret, the resulting com- putational cost is prohibitively high. We perturb the rewards when updating the neural network to eliminate the need of explicit exploration and the correspond-
ing computational overhead. We prove that a (dvTT) regret upper bound is still achievable under standard regularity conditions, where T is the number of rounds of interactions and d is the effective dimension of a neural tangent kernel matrix. Extensive comparisons with several benchmark contextual bandit algorithms, in- cluding two recent neural contextual bandit models, demonstrate the effectiveness and computational efficiency of our proposed neural bandit algorithm.
INTRODUCTION
Contextual bandit a well-formulated abstraction of many important real-world problems, includ- ing content recommendation (Li et al., 2010, Wu et al. 2016). online advertising (Schwartz et al., 2017 Nuara Nuara et al.) 2018), and mobile health (Lei al. 2017 Tewari & Murphy, 2017). In such problems, an agent iteratively interacts with an environment to maximize its accumulated rewards over time. Its essence sequential decision-making under uncertainty. Because the reward from the environment for a chosen action (also referred to an arm in literature) under each context is stochastic, a no-regret learning algorithm needs to explore the problem space for improved reward estimation, i.c., learning the mapping from
and its contex to the expected reward.
Linear contextual bandit algorithms (Abbasi- Yadkori et al. 2011 Li et al. 2010), which assume the reward mapping is linear function of the context vector, dominate the community's 'ss attention in the study of contextual bandits. Though theoretically sound and practically effective, their lin- ear reward mapping assumption is incompetent between the context vector and reward. This motivated the extended studies in parametric bandits, such as generalized linear bandits (Filippi et al. 2010: Faury et al. 2020) and kernelized bandits (Chowdhury & Gopalan| 2017: Krause & Ong 2011). Recently. to unleash the power of repre- sentation learning, deep neural networks (DNN) have also been introduced to learn the underlying reward mapping directly. In (Zahavy & Mannor 2019; Riquelme et al., 2018: Xu et al. 2020). deep neural network is applied to provide a feature mapping, and exploration performed at the last layer. NeuralUCB (Zhou et al., 2020) and NeuralTS (ZHANG et al.) 2020) explore the entire neural network parameter space to obtain nearly optimal regret using the neural tangent kernel tech- nique (Jacot et al. 2018). These neural contextual bandit algorithms significantly boosted empirical performance compared to their classical counterparts.
capture possible complex non-linear relations
Nevertheless, major practical concern of existing neural contextual bandit algorithms is their added computational cost when performing exploration. Take the recently developed Neural UCB and Neu- raITS for example. Their construction of the high-probabillty confidence set for model exploration
When ambiguity is invoked, we refer the feature vector for arm and its context context vector.

---

Published as a conference paper at ICLR 2022
depends the dimensionality of the network parameters and the learned context vectors' represen- tations, which is often very large for DNNs. For instance, a performing neural bandit solution often has the number of parameters in the order of 100 thousands (if not less). It is prohibitively expen- sive to compute inverse of the induced covariance matrix on such a huge number of parameters, as required by their construction of confidence set. As result, approximations, e-g., only using the diagonal of the covariance matrix (Zhou et al., 2020; ZHANG et al., 2020), are employed to make such algorithms operational in practice. But there is no thcoretical guarantee for such diagonal ap- proximations, which directly leads to the gap between the theoretical and empirical performance of the neural bandit algorithms.
In this work, to alleviate the computational overhead caused by the expensive exploration, we pro- pose to eliminate explicit model exploration by learning a neural bandit model with perturhed re- wards. At each round of model update, we inject pseudo noise generated from a zero-mean Gaussian distribution to the observed reward history. With the induced randomization, sufficient exploration is achieved when simply pulling the arm with the highest estimated reward. This brings in consider- able advantage over existing neural bandit algorithms: no additional computational cost is needed to obtain no regret. We rigorously prove that with a high probability the algorithm obtains a ((dTT) regret, where d is the effective dimension of neural tangent kernel matrix and T' is the number of rounds of interactions. This result recovers existing regret bounds for the linear setting where the effective dimension equals to the input feature dimension. Besides, extensive empirical evalua- tions demonstrate the strong advantage in efficiency and effectiveness of our solution against a rich set of state-of-the-ar contextual bandit solutions over both synthetic and real-world datasets.
2 RELATED WORK
Most recently, attempts have been made to incorporate DNNs with contextual bandit algorithms. Several existing work study neural-linear bandits (Riquelme et al. where exploration is performed on the last layer of the DNN. Under the neural tangent kernel
2018 Zahavy & Mannor 2019),
(NTK) framework (Jacot et al. 2018), NeuralUCB (Zhou et al. 2020) constructs confidence sets
with DNN-based random feature mappings to perform upper confidence bound based exploration. NeuralTS (ZHANG et al. 2020) samples from the posterior distribution constructed with a simi- lar technique. However, the exploration is performed in the induced random feature space, the added computational overhead is prohibitively high, which makes such solutions impractical. The authors suggested diagonal approximations of the resulting covariance matrix, which however leave the promised theoretical guarantees of those algorithms up in the air.
Reward perturbation based exploration has been studied in number of classical bandit models (Kveton et al. [219a] 2020; 2019b). In context-free k-armed bandit setting, Kveton et al.) (009b) proposed estimate each arm's 's reward over perturbed history and select the with the highest estimated reward at each round. Such an arm selection strategy is proved to be optimistic with a sufficiently high probability. Later this strategy has been extended to linear and generalized linear bandits (Kveton et al., 2019a 2020). In (Kveton et al. 2020), the authors suggested its application to neural network models; but only some simple empirical evaluations were provided, without any theoretical justifications. Our work for the first time provides a rigorous regret analysis of neural exploration: a sublinear regret bound is still achiev-
contextual bandits with the perturbation-bant able in terms of the number of interactions between the agent and environment.
NEURAL BANDIT LEARNING WITH PERTURBED REWARDS
We study the problem of contextual bandit with finite K arms, where each arm is associated with a
d-dimensional context vector: x; Rd for í E [K]. At each round t [T), the agent needs to select
one of the arms, denoted as at and receives its reward J, which is generated as ra,, = h(x.,) +
me. In particular, h(x) represents the unknown underlying reward mapping function satisfying 0 S
h(x) < 1 for any x, and is an Sauu-Gaassiinn random variable that satisfies E(exp(um)) S
exp f R2 for all p 2 0. The goal is to minimize pseudo regret over I rounds:
RT = E Σ
(ra- - rexoe)
(3.1)
t=]
2

---

Published as a conference paper at ICLR 2022
Algorithm 1 Neural bandit with perturbed reward (NPR)
Input: Number of rounds T' regularization coefficient X, perturbation parameter v, network
width m, network depth L.
2: Initialization: 6g (vec(W1). (W1).... vee (e()) E R' with Gaussian distribution: for </
L 1. W,
(W, 0: O. W) with each entry of W sampled independently from (0, 4/m);
Wr - [w - w with each entry of sampled independently from ((, 2/m)..
3: for [- 1, ,,..., , do
4: if > K then
5: Pull arm o, and receive reward at, where a, argmax,e|k] fxx, 0t-1).
6: Generate [e(t (000, 2²).
7: Set O, by the output of gradient descent for solving Eq 3.2
8: else
9: Pull arm dg.
10: end if
11:
end for
where a" is the optimal arm with the maximum expected reward.
To deal with the potential non-linearity of h(x) and unleash the representation learning power
of DNNs, we adopt a fully connected neural network f(x; 0) to approximate h(x):: f(x; 0)
vm W áó
W WL-10(-- ... (W1x))) where xxx) = (eLU(()) 0 = [vec(W1), vec (V)) L)] e
Iº with p = m + md + m2 1). and depth L 2 2. Each hidden layer is assumed to have the same width (i.e., m) for convenience in later analysis; but this does not affect the conclusion of our theoretical analysis.
Existing neural bandit solutions perform explicit exploration in the entire model space (Zhou al., 2020 ZHANG et al. 2020 Zahavy & Mannor 2019) Riquelme et al. 2018) Xu et al.) (2020). which introduces prohibitive computational cost. And oftentimes the overhead so high that approxima- tion has to be employed (Zhou et al. 2020 ZHANG et al. 2020). which unfortunately breaks the theoretical promise of these algorithms. In our proposed model, eliminate such explicit model exploration in neural bandit, a randomization strategy is introduced in the neural network update. We name the resulting solution Neural bandit with Perturbed Rewards, or NPR in short. In NPR, at round 1, the neural model is learned with the ł rewards perturbed with designed perturbations:
min (()) = =E... (f(xa, 0) - (r + +²)²²² /2 + mAll0 - 001l//2 0
(3.2)
where {ni)<= ~ NO, o²) are Gaussian random variables that are independently sampled in each round t, and is hyper-paramete that controls the strength of perturbation (and thus the explo- ration) in NPR. We use an Iz-regularized square loss for model estimation, where the regularization centers the randomly initialization 6g with the trade-off parameter X.
The detailed procedure of NPR is given in Algorithm I The algorithm starts by pulling all candidate arms once. This guarantees that for any arm, NPR sufficiently optimistic compared to the true reward with respect to its approximation error (Lemmaa4.4) When all the arms have been pulled once, the algorithm pulls the arm with the highest estimated reward, a argmax, fxx; 0,-1). Once received the feedback Ta,,, the model perturbs the entire reward history so far via a freshly sampled noise sequence {1:) and updates the neural network by ( + } using gradient descent. In the regret analysis in Section 4 we prove that the variance from the added (1')xe[t) will lead to the necessary optimism for exploration (Abbasi- Yadkori et al., 2011). We adopt gradient descent for analysis convenience, while stochastic gradient descent can also be used to solve the optimization problem with similar theoretical guarantee based on recent works (Allen-
Zhu al. 2019 Zou al. 2019).
Compared with existing neural contextual bandit algorithms (Zhou et al. 2020 ZHANG et al. 2020 Zahavy & Mannor 2019 Riquelme et al. 2018 Xu et al. 2020)) NPR does not need any added com- putation for model exploration, besides the regula lar neural network update. This greatly alleviates the overhead for the computation resources (both space and time) and makes NPR sufficiently general to be applied for practical problems. More importantly, our theoretical analysis directly corresponds to its actual behavior when applied, no approximation is needed.
3

---

Published as a conference paper at ICLR 2022
4 REGRET ANALYSIS
In this section, we provide finite time regret analysis of NPR, where the time horizon T set beforehand. The theoretical analysis is built on the recent studies about the generalization of DNN models (Cao & Gul 2020 Chen Chen et al. 2020 Daniely 2017 Arora et al. 2019). which illustrate that with (stochastic) gradient descent, the learned parameters of DNN locate a particular regime with the generalization error being characterized by the best function in the corresponding neural tangent kernel (NTK) space (Jacot et al. 2018). We leave the background of NTK the appendix and focus on the key steps of our proof in this section.
The analysis starts with the following lemma for the set of context vectors {x;
Lemma 4.1. There exists positive constant C' such that for any 5 (0, 1), with probability least 1 - 8, when mn 2 CK* L log K L/0) there exists a 0 E I2, for all i [K].
Vmll0' 0oll2 S 2h H ', where H is the NTK matrix defined the context set and h (h(x1), .... h(xx)). Details of H can be found in the appendix.
(x;)) = (g( x; 0p), Oo),
(4.1)
This lemma suggests that with a satisfied neural network width m, with high probability, the under- lying reward mapping function can be approximated by linear function over g(x'; 0o), parameter- ized by 0" - Oo. where g(x"; 0o) = Vof(x: 0o) E Id the gradient of the initial neural network. We also define the covariance matrix A, round as,
A, Σ x.,, 0 (o)g(xx.,, O0) /m To)T/m + AI
(4.2)
where A > 0 is the la regularization parameter in Eq 3.22 Discussed before, there exist two kinds of noises in the training samples: the observation noise and the perturbation noise. To analyze the effect of each noise in model estimation, two auxiliary least square solutions are introduced, A, ', and A, b, with
b. E01 (rs,a,
00)/
b, = --=E- (rs,a, +/2 )xx,),, 0n)/ mm.
These two auxiliary solutions isolate the induced deviations: the first least square solution only contains the deviation caused by observation noise {n=]s=): and the second least square solution has an extra deviation caused by -
To analysis the estimation error of the neural network, we first define the following events. At round t, we have event F,,1 defined as:
1 Vi E [K], (x,,; 0o). A, A b./Vm) hxxx,))) S (lg(, 0o) 00)
According to Lemma 4.1 and the definition of b,, under event E,,,, the deviation caused by the observation noise [m, can be controlled by az. We also need event E, at round defined as
F (Vi E [K] 1f(xx,; (g(x,,, b. <(m) Bellg(x,,;; 0o)1l,
where e(m) is defined as
2/313 <(m) =C,,m 2/ -2/3 Vlogm- C2,2(1 myma)' VTL/A Vlog + VT/X),
+ 1/6
with constants -0 Event Er, considers the situation that the deviation caused by the added ]== noise [== is under control with parameter at round f, and the approximation error c(m) is carefully tracked by properly setting the neural network width m.
The following lemmas show that given the history F o o(x1, Fl, X2, 7t-1 xt), which is -lageerr generated by the previously pulled arms and the observed rewards, with proper setting, events F, and F,, happen with high probability.
4

---

Published as a conference paper at ICLR 2022
Lemma 4.2. For any t E [2], X > and ò > O, with ae = V log (de((A))((@deet())))) + VĀS, we have 1 2 1 8.
In particular, S denotes the upper bound 22h T H- which is constant the reward function h(-) belongs the RKHS space induced by the neural tangent kernel.
Lemma 4.3. There exist positive constants {Ci) such that with step size and the neural net- work satisfy that 77 = C1 Ci m 2
and m[logm] 2 L (1+ (1+V///)) given history F:-1, by choos- C3 max (7 1" (
ing 3, o o log 2 log K, we have P(F 21-
We leave the detailed proof in the appendix. According to Lemma 4.2 and Lemma 4.3 with more observations become available, the neural network based reward estimator f(x: O2) will gradually converge to the true expected reward hxx). In the meantime, the variance the added perturba- tion leads reward overestimation, which will compensate the potential underestimation caused by the observation noise and the approximation error. The following lemma describes this anti- concentration behavior of the added noise {1g (- J==1
Lemma 4.4. For any E (T), with o a,,
(AR)) a, defined in Lemma 4.2 <(m) defined in Lemma 4.3 given history Fi-1, we have P(F{,)) = (( 0.-1) ((x,,;) F(-1) E 2 (4e//)=1 -1 where Ax is the covariance matrix constructed after the initial K-round arm pulling (line to in Algorithm I by Eq (42). and Ax Ax(Ak) represents the K-th largest eigenvalue of matrix Ak.
With ar defined in Lemma 4.2 and e(m) and 3r defined in Lemma 4.3 we divide the arms into two groups. More specifically, define the set of sufficiently sampled arms in round /. as:
f4 = {Vi E [K] 2e(m) + (at + B:) Ig(x,, 00)1l S h(x(,-)) h(xx,,))
Accordingly, the set of undersampled arms is defined as f2 [K] \ Ω4. Note that by this definition, the best arm a" belongs to Ω4. In the following lemma, we show that at any time step >> K, the expected one-step regret is upper bounded in terms of the regret due to playing undersampled arm a, E 9z.
Lemma 4.5.
4.4 and c(m) defined in Lemma 4.3 with probability at least 1 å the one step regret of NPR is upper bounded,
With m, 7). a satisfying the conditions in Lemma 4.2
4.3
B(h(xx,0;) h(x,,a,) ) S ((E + 4c(m) (B. az) + 2/P((a (2)) [xx(Xx, 0u)/ (0)//mllAct VmllA Furthermore, P(a, E 22)) 2 Pa 2..2).
To bound the cumulative regret of NPR, also need the following lemma. Lemma 4.6. With d as the effective dimension the NTK matrix H, we have
Σ
min [|g(x,,,, 00)/ m
} < 2(dlog(1 + +K/A)++1
The effective dimension is first proposed in (Valko et al. 2013) analyze the kernelized contextual bandit, which roughly measures the number of directions in the kernel space where the data mostly lies. The detailed definiton of d can be found in Definition B.3 in the appendix. Finally, with proper neural network setup, we provide an m-independent regret upper bound.
Theorem 4.7. Let be the effective dimension of the NTK kernel matrix H. There exist positive constants Ci and Cr. such that for any 8 (0, 1), when network structure and the step size for model update satisfy m 2 (T,y(T, L, K, X S-1 log(1 (1))), 7 CimIL mA) and À 2 max 1, (-)), with probability least 1 5. the cumulative regret of NPR satisfies
Rr < (R (RVdToog( TK// + log 6 + VAS) 2o +2+ 7 K
(4.3)
where r = 44e/m(1 + + (4log T 2log K)/(1 (A
5

---

Published as a conference paper at ICLR 2022
Proof. By Lemma 4.2 E holds for all t [T] with probability at least 1 - 8. Therefore, with
probability at least
6, we have
Rr
B((h(xxaa;) ----hhhs ((xx,aa))1((BII))
B[(h(xe,a;) ((xx,))) (F,,)) + K
t=K+1
T <4Te(m) + P((()))) + (8, a.) + (.(E)))) - P. (E12)
2
(g( 00)/vmll A, + K.
t=1
The second inequality is due to the analysis of step regret in Lemma 4.5 According Lemma
4.3 by choosing oc,, with c / log K, (Er,)) S t- Hence, > (B. 2
/ Based on Lemma 4.4 with a ar(1 [1 (Ax)) Pt(Et,a) 2 Jev= Therefore,
+ (/())(E (E.22) I 41e/T. By chaining all the inequalities, have the cumulative regret of NPR upper bounded as,
2² + 4Tc(m) E'_ (Be oz) Pr(Er.3) (.( (g((1,, 0o)
2
Rí
AT + K
7²
RV (log@lll11((ii
+ +KK/A) +2 2 2oog vXs) v /22T log(1 + TK/A) + 2
+
3
Cc. - 2/3 logm Cr,2(1 I
5/3 + Cc,3m 11/67//3////// 1 Togm(1 + (T/A)
where r = 44c/5(1 + v (4 T + 2 log /)((1 AA (Ak))). The second inequality is due
to Lemma 4.6, and the bounds of events E,, and E,,3- By setting = c(m) + mLT)-1 and J = (1 (T/))((o((...))) +og T /T////// C,2(1 CT2(1-mmA)'T TT// < 1. Then by choosing
the satisfied m, 100 x- 2/3 1.3 Vlg m 1/ -5/3 /log mil /T/A) S
2/3. Rr can be further bounded by Rr s r [Ry dlog(1 (1 TK/A) + 2 log 5 + vx8)
V lo
(1 + TK/A) +
This completes the proof.
EXPERIMENTS
In this section, we empirically evaluate the proposed neural bandit algorithm NPR against several state-of-the-art baselines, including: linear and neural UCB (LinUCB (Abbasi- Yadkori et al. 2011)) and NeuralUCB (Zhou et al. 20200), linear and neural Thompson Sampling (LinTS (Agrawal & Goyal] 2013) and NeuralTS (ZHANG et al.) 2020)), perturbed reward for linear bandits (Lin (vetton et al. 2019a). To demonstrate the real impact of using diagonal approximation confi- also include NeuralUCB and NeuralTS with diagonal approximation as suggested in their original papers for comparisons.
dence set construction,
We evaluated all the algorithms 1) synthetic dataset via simulation, six K-class classification datasets from UCI machine learning repository (Beygelzimer et al., 2011), ) and 3) two real-world datasets extracted from the social bookmarking web service Delicious and music streaming service LastFM (Wu et al. 2016). We implemented all the algorithms in PyTorch and performed all the experiments on server equipped with Intel Xeon Gold 6230 2.10GHz CPU, 128G RAM. four NVIDIA GeForce RTX 2080Ti graphical cards.
5.1 EXPERIMENT ON SYNTHETIC DATASET
In our simulation, we first generate a size-K arm pool, in which each arm associated with d-dimensional feature vector x;. The contextual vectors are sampled uniformly at random from unit ball. We generate the rewards via the following two nonlinear functions:
hr(x) 1 ΣΣ! x). hz(x) exp(-10c )))))

---

Published as a conference paper at ICLR 2022
LinfPL
1400
2000
LinUCB
NFR
1000
Neundft
Regret
8.00
NcurOTTs (Dlggonoi)
Neuraluce
600
Neuraluch (Dlagena))
600
500
0-
Rounds
Rounds
(a) hi (x) = (x ΣΣ
TTxX x)
(b) h2(x) 10ppp100(x 0)
Time Are Sabetian
2007
Nouralcca
Dipped Time (oer)
Diver Time Dock
Nouarrts Phlggrest
Nousal ern (Nkoowee
2:49
Eacoeed
Nar UCB MORTS MEAUUC NUrAAO W/K
22
of Peel
114
Nevell Netwert Strchare
(c) Elapsed time
(d) Effect of pool size
(c) Effect of network complexity
Figure 1: Empirical results of regret and time consumption on synthetic dataset.
where each element of Σ E Rdd is randomly sampled from M( 1), and is randomly sampled from a unit ball. At each round t, only subset of arms out of the total K arms sampled without replacement and disclosed to all algorithms for selection. The ground-truth reward Ta is corrupted by Gaussian noise 1 (0, <²) before feeding back to the bandit algorithms. We fixed the feature dimension 50 and the pool size K = 100 with 20. & was set to 0.1 for both hı and h2-
Cumulative regret is used to compare the performance of different algorithms. Here the best arm is defined as the one with the highest expected reward in the presented k candidate arms. All the algorithms were executed up to 10000 rounds in simulation, and the averaged results over 10 runs are reported in Figure [(a) to [(e) For the neural bandit algorithms, we adopted 3-layer neural network with m 64 units in each hidden layer. We did grid search on the first 1000 rounds for regularization parameter À over (10 ====- (10-)440-
and step size over (10-1) 1==0- We also searched for the concentration parameter 8 so that the exploration parameter v is equivalently searched over (10-1} Nez The best set of hyper-parameter
for each algorithm are applied for the full simulation over 10000 rounds, i.c., only that trial will be continued for the rest of 9000 rounds.
In Figure I(a) and ((b) we can observe that linear bandit algorithms clearly failed to learn non- linear mapping and suffered much higher regret compared to the neural algorithms. NPR achieved similar performance NeuralUCB and NeuralTS, which shows the effectiveness of our randomized exploration strategy in neural bandit learning.
Figure ICe shows the average running time for all the neural bandit models in this experiment. With the same network structure, the time spent for model update was similar across different neural bandit models. But we can clearly observe that NeuralUCB and NeuralTS took much more time in arm selection. When choosing an arm, NeuralUCB and NeuralTS, and their corresponding versions with diagonal approximation, need to repeatedly compute: the inverse of the covariance matrix based on the pulled arms in history; and 2) the confidence set of their reward estimation on each candidate arm. The size of the covariance matrix depends on the number parameters the neural network (c.g., 7460-by-7460 in this experiment). With diagonal approximation, the computational cost significantly reduced. But, as mentioned before, there is no theoretical guarantee about the approximation's 's impact on the model's performance. Intuitively. the impact depends on how the full covariance matrix concentrates on its diagonal, e.g., whether the random feature mappings of the network the pulled arms are correlated among their dimensions. Unfortunately, this cannot be determined in advance. Figure ((a) and [(b) show that the diagonal approximation leads to a significant performance drop. This confirms concern of such an approximation. In contrast, as shown in Figure [(c] there is no extra computation overhead in NPR; in the meantime, provides comparable performance NeuralUCB and NeuralTS with full covariance matrix.

---

Published as a conference paper at ICLR 2022
210
LXTTL
LVTTS
200
MPR
NcuroltS
Reyyne
NauraltS (Blogora)
MeuralaCe
Meura UKB sponall
200
2700
1000
1535 2008
100
100
1000
10.00
(a) Adult
(b) Mushroom
(c) Shuttle
Figure 2: Comparison of NPR and the baselines on the UCI datasets.
To further investigate the efficiency advantage of NPR, reported the total running time for the neural handit algorithms under different sizes of the arm pool and different structures of the neural network under the same simulation setting. With the same neural network structure, models with different sizes of candidate arms should share the same running time for model update. Hence, Figure reports how the size of arm pool affects the time spent on arm selection. As we can find, with more candidate arms, NeuralUCB, NeuralTS,, and their corresponding diagonal approximations spent more time on arm selection, or more specifically on constructing the confidence set of the reward estimation for each arm. With fixed size arm pool, the complexity of the neural network will strongly affect the time for computing the inverse of the covariance matrix. In Figure [[e] the x-axis shows the structure for the hidden layers. The running time for NeuralUCB and NeuralTS significantly increased with enlarged neural networks. The running time NPR stayed stable, across varying sizes of arm pools and the network complexity. This shows the strong advantage of NPR in efficiency and effectiveness, especially for large-scale problems.
5.2 EXPERIMENT ON CLASSIFICATION DATASETS
Following the setting in (Zhou al. 2020), evaluated the bandit algorithms on K-elass classifi- cation problem with six public benchmark datasets, including adu tt, mushroom, and shuttle le from UCI Machine Learning Repository (Dua & Graff 2017). Due to space limit, we report the results on these three datasets in this section, and leave the other three, let better, covertype, and MagicTelescopy
in the appendix. We adopted the disjoint model (Li et al.. 2010) to build the context vectors for candidate arms: given an input instance with feature x E Ik of k--class classification problem, we constructed the context features for i candidate arms as: X1 (x, 0, ......, X2. (O...., x) E Rdxk The model receives reward I if it selects the correct class by pulling the corresponding arm, otherwise The cumulative regret measures the total mistakes made by the model over T rounds. Similar the experiment in synthetic datasets, we adopted a 3-layer neural network with m = 64 units in each hidden layer. We used the same grid search setting in experiments synthetic datasets. Figure 2 shows the averaged results across 10 runs for 10000 rounds, except for mush room which only contains 8124 14 data instances.
There are several key observations in Figure 2 First, the improvement of applying neural bandit model depends on the nonlinearity of the dataset. For example, the performance on mu mushoom and shuttle was highly boosted by the neural models, while the improvement on adule .dult was limited. Second, the impact of the diagonal approximation for NeuralUCB and NeuralTS also depends on the dataset. It did not hurt their performance too much on shuttle. while using the full covariance matrix led to much better performance on Mushroom. Overall. NPR showed consistently better or least comparable performance to the best neural bandit baselines in all six datasets. Such robust performance and high efficiency make it more advantageous in practice.
5.3 EXPERIMENT ON LASTEM & DELICIOUS
The LastEM dataset was extracted from the music streaming service website Last.fm, and the Deli- cious data set was extracted from the social bookmark sharing service website Delicious (Wu al.) 2016). In particular, the LastFM dataset contains 1,892 users and 17,632 items (artists). We treat the "listened artists" in each user positive feedback. The Delicious dataset contains 1,861 users and 69,226 items (URLs). We treat the bookmarked URLs for each user as positive feedback. Following the standard setting (Cesa-Bianche et al. 2013), pre-processed these two datasets. For the item
8

---

Published as a conference paper at ICLR 2022
Normalized Payoff
25-
Normalized Payoff
30-
25-
(Dlagona)) Ncurolice (Diagonal)
NP8 NeuralTS (Dlogonal)
15-
(Dlagoral
0-
10000
LastFM datasct
(b) Delicious dataset
Figure 3: Comparisons of normalized rewards on LastFM & Delicious datasets.
features, we used all the tags associated with each item to create its TF-IDF feature vector. Then PCA was applied to reduce the dimensionality the features. In both datasets, we used the first 25 principle components to construct the item feature vectors. On the user side, we created user fea- tures by running node2vec (Grover Leskoved 2016) on the user relation graph extracted from social network provided by the datasets. Each of the feature vector. We generated the candidate pool as follows: we fixed the size candidate arm pool to k 25 for each round; for each according to the complete observations in the dataset, and randomly picked the other 24 from those zero-payoff items. We constructed the context vectors by concatenating the user and item feature vectors, In our experiment, a 3-layer neural network with m = 128 units in each hidden layer was applied to learn the bandit model. And the same gird search was performed to find the best set of prpperpprramters. We performed the experiment with 10000 rounds. Because of the high demand of GPU memory for the matrix inverse computation, we only compared NPR to NeuralUCB and NeurallSS with the diagonal approximation.
represented with 50-dimensional
picked one item from those non-zero payoff items
We compared the cumulative reward from each algorithm in Figure Besides the neural contextual bandit algorithms, we also include the best reported model on these two datasets, hLinUCB (Wang 2016) for comparison. To improve visibility, we normalized the cumulative reward by random strategy's s cumulative reward (Wu al.) 2016), where the arm was randomly sampled from candidate pool. All the neural models showed the power to learn the potential non-linear reward mapping on these two real-world datasets. NPR showed its advantage over the baselines (especially on LastEM). As NPR has no additional requirement on the computation resource (e.g., no need for the expensive matrix operation in the baselines), also experienced much shorter running in NPR than the other two neural bandit models.
CONCLUSION
Existing neural contextual bandit algorithms sacrifice computation efficiency for effective explo- ration in the entire neural network parameter space. To eliminate the computational overhead caused by such an expensive operation, we appealed to randomization- based exploration and obtained the same level of learning outcome. No extra computational cost resources needed besides the regular neural network update. We proved that the proposed solution obtains (dVT)) regret for T rounds of interactions between the system and user. Extensive empirical results on both synthetic and real-worke datasets support our theoretical analysis, and demonstrate the strong advantage of our model in efficiency and effectiveness, which suggest the potential of deploying powerful neural bandit model online in practice.
Our empirical efficiency analysis shows that the key bottleneck of learning neural model online is at the model update step. Our current regret analysis depends on (stochastic) gradient descent over the entire training set for model update in each round, which is prohibitively expensive. We would like to investigate the possibility of more efficient model update, e.g., online stochastic gradient de- scent continual learning, and the corresponding effect model convergence and regret analysis. Currently, our analysis focuses on the K-armed setting, and it is important to extend our solution and analysis infinitely many arms in future work.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their helpful comments. YJ and HW are partially supported by the National Science Foundation under grant IIS (12-0128019 and IIS- 1553568. WZ, DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169 and 10--1904888 The views and conclusions contained in this paper are those of the authors and should not be inter- preted as representing any funding agencies.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff'.. In International Conference on Machine Learning, pp. 127-135, 2013.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On ex- act computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, 2019.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth Interna- fional Conference on Artificial Intelligence and Statistics, pp. 19 19-26, 2011.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, 2019.
Yuan Cao and Quanquan Gu. Generalization error bounds of gradient descent for learning over- parameterized deep relu networks. In the Thirty-Fourte AAAI Conference Artificial Intelli- gence, 2020.
Nicolo Cesa-Bianchi. Claudio Gentile, and Giovanni Zappella. A gang of bandits. arXiv preprint 1rXiv:1306.0811, 2013.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much peeepaarametriizaiionn is suf- ficient to learn deep relu networks? In International Conference on Learming Representations, 2020.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pp. 844 853. PMLR, 2017.
Amit Daniely. SGD learns the conjugate kernel class of the network. In Advances in Neural Infor- mation Processing Systems, pp. 2422-222222 22230, 2017.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. International Conference on Machine Learning, pp. 1675- 1685, 2019.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htth:httt///hhhii ics. aici.edu//m
Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algo- rithms for logistic bandits. In International Conference Machine Learning, pp. 3062-3060. PMLR, 2020.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, pp. 586-594, 2010.
10

---

Published as a conference paper at ICLR 2022
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855 864, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Andreas Krause and Cheng S Ong. Contextual Gaussian process bandit optimization. In Advances in neural information processing systems, pp. 2447-2455, 2011.
Branislav Kveton, Csaba Szepesvári, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. In Proceedings of the 35th Conference on Uncer- tainty in Artificial Intelligence (UAI), pp. 176, 2019a.
Branislav Kveton, Csaba Szepesvari. Sharan Vaswani, Zheng Wen, Tor Lattimore, and Mohammad Ghavamzadeh. Garbage in, reward out: Bootstrapping exploration in multi-armed bandits. In International Conference on Machine Learning, pp. 3601-3610, PMLR, 2019b.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvári, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2020.
Huitian Lei, Ambuj Tewari, and Susan A Murphy. An actor-critic contextual bandit algorithm for personalized mobile health interventions. arXiv preprint arXiv: 1r%,001706.09090, 2017.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A cattextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670. ACM, 2010.
Alessandro Nuara, Francesco Trovo, Nicola Gatti, and Marcello Restelli. A combinatorial-bande algorithm for the online joint bid/budget optimization of pay-per-click advertising campaigns. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep Bayesian bandits showdown. In Interna- tional Conference on Learning Representations, 2018.
Eric M Schwartz, Eric T Bradlow, and Peter S Fader. Customer acquisition via display advertising using multi-armed bandit experiments. Marketing Science, 3604):500-52,, 2017.
Ambuj Tewari and Susan A Murphy. From ads to interventions: Contextual bandits in mobile health. In Mobile Health, pp. 495-517. Springer, 2017.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-tine time analysis of kernelised contextual bandits. arXiv preprint arXiv:1309 3869.666.9.... 2013.
Huazheng Wang, Qingyun Wu, and Hongning Wang. Learning hidden features for contextual ban- dits. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pp. 1633-1642, 2016.
Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in collabo- rative environment, In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 529-538, 2016.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:20/2.001780, 2020.
Tom Zahavy and Shie Mannor. Deep neural linear bandits: Overcoming catastrophic forgetting through likelihood matching. arXiv preprint 1rXiv:1901.0861 2019.
Weitong ZHANG, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference on Learning Representations, 2020.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with exploration. In International Conference on Machine Learning, pp. 11492-1 1500. PMLR, 2020.

---

Published as a conference paper at ICLR 2022
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep ReLU networks. Machine Learning, 2019.
A ADDITIONAL EXPERIMENTS
A.1 EXPERIMENTS ON SYNTHETIC DATASETS
A.1.1 REWARD PREDICTION WITH MORE COMPLICATED NEURAL NETWORKS
In the main paper, to compare NPR with the existing neural bandit baselines, chose relatively can be executed with a full co-
small neural network, e.g., m = 64, so that NeuralUCB/Neuraal variance matrix. To better capture the non-linearity in reward generation, we increased the width of the neural network to m = 128, and report the results in Figure 4 All other experiment settings (e.g., underlying reward generation function) are the same as reported in the main paper. And to pro- vide more comprehensive picture, we also reported the variance of each algorithm's 's performance in this figure.
With the increased network width and limited by the GPU memory, NeuralUCB and NeuralTTS can only be executed with the diagonal matrix of the covariance matrix when computing their required "exploration bonus term". In Figure 4 we can observe 1) all neural bandit algorithms obtained the expected sublinear regret; and 2) NPR performed better than NeuralUCB and NeuralTS, because of the diagonal approximation that we have to use on these two baselines. This again strongly suggested the advantage of NPR: the approximation due to the computational complexity in NeuralUCB and NeuralTS limits their practical effectiveness, though they have the same theoretical regret bound as NPR's. 3) FALCON+ shows better performance the initial rounds, while with more iterations, its regret is higher than the neural bandit baselines' and our NPR model'. Compared to the neural bandit models, FALCON+ has much slower convergence, e.g. the slope its regret curve did not decrease as fast other models' over the course of interactions. After careful investigation, we found this is caused by its scheduled update: because less and less updates can be performed in the later rounds, FALCON+ still selected the suboptimal arms quite often. Another important observation is that FALCON+ has a very high variance in its performance: in some epochs, it could keep sampling the suboptimal arms. This is again caused by lazy update: in some epochs of some trials, its estimation could be biased by large reward noise, which will directly cost it miss the right arm in almost the entire next epoch.
LiUUCB
1400
LHUCS
LaTT
LnFRL
1200
LnFFL
2000
IPR
NeuralUCC, Dleg
1000
NeuraUUC_,DH Dhag
NeurafTS_Diag
NeurafTS__O Diug
IALCON+
800
2000
600
400
200
0
2000
4000
6000
5000
10000
2000
4000
6000
8000
10000
Rounds
Raunds
(a) le (x) = 10 2x ΣΣ x)
(b) hx(xx) exp( 100x 0)2)
Figure& 4: Comparison of NPR and the baselines on the synthetic datasstt with m 128
A.1 COMPARISONS UNDER DIFFERENT VALUES OF k
For the experiment in the main paper, each round only & = 20 arms are sampled from the K = 100 arm pool and disclosed to all the algorithms for selection.
is to test a more general setting in practice, e.g., different recommendation candidates appear across rounds. In the meantime, such setting also introduces more practical difficulties as only a subset of arms are revealed to the agent to learn from each time. In this experiment, report the results of the neural bandit models with
12

---

Published as a conference paper at ICLR 2022
TALCON+ k-100
FALCON+ k=100
FALCON+
FALCON+
1400
k-100
b-20
Diag k-100
300
NeuralTS Diag
1000
NeuraiTs_ Diag k=20
NeuralTS Ding k=
NeunatiCR Dueg k-100
NeuralUCS Drug k-100
800
NeuratiCe Dog k-20
200
NeuralUCS Diog kw
400
100
200
0
2000
4000
6000
5000
10000
2000
4000
5000
1000
10000
Rounds
Rounds
(a) to (x)
10 (x ΣΣ
10
(b) (x)
exp( 10 0)*)
Figure 5: Comparison of NPR and the baselines the synthetic dataset with different k.
different value k, e.g., the number of arms disclosed each round. We followed the setting in Section to set the network width 128.
Figure demonstrates that for both datasets, revealing all the candidate arms, c.g., = 100, will considerably reduce the regret compared only revealing subset of the arms. But in both settings, all bandit algorithms, including NPR, can obtain desired performance (i.e., sublinear regret). And again, NPR still obtained more satisfactory performance as not subject the added compu- lational complexity in NeuralUCB and NeuralTS. The FALCON+ baseline performed much better when A 20 than 100, has less chance select the suboptimal arms in each epoch, which is expected based on its polynomial dependence on the number of arms K. On the contrary, NPR only has a logarithmic dependence K, whose advantage was validated in this experiment.
A.2 EXPERIMENTS ON CLASSIFICATION DATASETS
MR
118 (7eamss
1/0
x00
2000
2000
9:00
17000
400
10:00
2008
25.
5000
1000
12.00
MagicTelescope
(b) Letter
(c) Covertype
Figure 6: Comparison of NPR and the baselines on the UCI datasets.
Table Dataset statisties
DATASET ADULT
MUSHROOM SHUTTLE MAGIC LETTER COVERTYPE
INPUT DIMENSION
2 x 15
x23 7 2 x 12 16 x 26
54 x
We present the experiment results of the classification problem on UCI datasets, SegicTelescopp letter and covertype. The experiment setting and grid search setting for parameter tuning are the same as described in Section 5 For datasets letter and ype only the results of NeuralUCB and NeuralTS with diagonal approximation are reported as the required GPU memory for the caleulation of matrix inverse, together with the neural model update, exceeds the supported memory of the NVIDIA GEFORCE RTX 2080 graphical card. Similar observations are obtained for these three datasets. Compared to the linear contextual models, the neural contextual bandit algorithms significantly improve the performance with much lower regret (mistakes on classification). NPR showed consistently better performance to the best neural bandit baselines. And due its verturbation-basse exploration strategy, extra computational resources are needed, which makes it more practical in weal-world problems, especially large-scale tasks.
13

---

Published as a conference paper at ICLR 2022
B BACKGROUND FOR THEORETICAL ANALYSIS
We denote the set of all the possible K arms by their context vectors as (x:) Our analysis is built upon the existing work in neural tangent kernel techniques.
Definition B.1 Jacot et al. (2018) Cao & Gu (2019)). Let {x.
be set of contexts. Define
Σ
H 20 (xi, X)).
B
x(+11 (j = 2E (.. (d(u)(b)),
( = -2H (o.)) lo' (u)d
Then, H (H14) + //2 is called the neural langent kernel (NTK) matrix on the context set.
/
With Definition B.1 also have the following assumption on the contexts: {x:)
Assumption B.2. H Aol; and moreover, for any 1 < i K, |x and [xa]] [xl5++d/2.
By assuming H AoI, the neural tangent kernel matrix is non-singular (Du et al. 2019 Arora et al., 2019 Cao & Gu 2.19). It be easily satisfied when
context vectors in the context set in parallel. The second assumption is just for convenience in analysis and can be easily satisfied by:
for any context vector x, ||x|2 = 1, we can construct new context x' = [x [ /T//2. verified that if 0, initialized in Algorithm [ then fx;;; 0n) 0 for any [K].
It can be
The NTK technique builds a connection between the analysis of DNN and kernel methods. With the following definition of effective dimension, we are able analyze the neural network by some complexity measures previously used for kernel methods.
K Definition B.3. The effective dimension d of the neural tangent kernel matrix on contexts { is defined as
d log det +TH/A)
log(1 TK/A)
The notion effective dimension is first introduced in Valko et al. (2013) for analyzing kernel contextual bandits, which describes the actual underlying dimension in the set of observed contexts {
And also need the following concentration bound on Gaussian distribution.
Lemma B.4. Consider normally distributed random variable X ~ (N o²) and B 2 0. The probability that is within radius of Bo from its mean can be written as,
P([X pl - Ba) exp(-82 /2).
C PROOF THEOREMS AND LEMMAS IN SECTION
C.I PROOF OF LEMMA 4.2
Proof of Lemma 4.2 By Lemma 4.1 with satisfied m, with probability at least 5, we have for
any E [K].
((x.) = (g(x;; 0n)/ /m, (m -0)),, and mml 0" - 0ull2 S 22h H < S.
Hence, based the definition of A, and b,, we know that A, is the least square solution top of the observation noise. Therefore, by Theorem in Abbasi- Yadkori et al. (2011), with probability least 1 8, for any < < T, 0* satisfies that
R2a log det(Ar) VāS. 82 (eT)
O0 0n) - A. S
(C.I)
14

---

Published as a conference paper at ICLR 2022
where R is the sub-Gaussian variable for the observation noise 1). Then we have,
( 0o), A b V - h(xx,,)l
= (x 00), A b:/ m) (g(>,, :; 0o), 0- -001
00)/ < <llvm(0* 0n) A, by A, [lg 00)/ ///l///llllla AT I on (0)l /mlla,"
with at = VIEE log det(Ar) det(AT)
VAS. This completes the proof.
C.2 PROOF OF LEMMA
The proof starts with three lemmas that bound the error terms of the function value and gradient of a neural network.
Lemma C.I (Lemma B.2, Zhou al. (0220). There exist constants 3 0 such that for any 8 > O, with J as the number of steps for gradient descent in neural network learning, if for all t [T], 77 and m satisfy
2 2/t/(mA)= 2 01m- 1/ (lll- (lg(( (1
2 2 4/(mmmm)= s C2 min { (L0g [l 3
--og--(logmm) 3/2 (m(An)22 ((ogm) 1) )
C3 + tmL)-1
ml/ 1/6 2 C. Co 2 7//
vt/A),
then with probability least 1 8, we have that 10, 1 Bolla S 2 2/tt/ (m/) and
10:-1 0g A, b./bb//mml - 1mm) J/2 (t((m)) + Cam - 2/3 1oonn//////loll///l/// /logmL 5/3 + t/))).
Lemma C.2 (Lemma B.3 Zhou et al. 2020 There exist constants {C; Fim1 such that for any > 0, satisfies
C/m" - /1 C m] 3/2
then with probability least 1 - 8, for any θ and satisfying |@ 0nll2 TT, 110 0oll2 s t and j E [K] we have
Cr 4/3 log ((x;;0) f(x;; 0) (g(x;; 0). Ø 0)
Lemma C.3 (Lemma B.4, Zhou al. 22200)) There exist constants
{Čr 13 0 such that for any
> if satisfies that
Cim 3/2 -m 3/2
(LLL/// [og(KL
ST L. "log [loggm]]/// 3/2
then with probability at least 8, for any |10 0oll2 and j E [K] we have |lg(x;;0)|] S
C% CL..
With above lemmas, we prove Lemma 4.3 as follows.
Proof of Lemma
4.3 According to Lemma with satisfied neural network and the learning rate we have |0 0ol12 < 2 2 ///m Further, by the choice of m, Lemma C.2 and C.3 hold.
Therefore, 1f(x 0.-1) i 0b), A, b,/ mmml can be first upper bounded by:
1f 0--1) ( 0o), A, b l
(x,,,,, 0,11) (xx, 0n) x ; 0o), 0. 0o) + (g((x, 0o), 0,), 0.-
On A b.b./m/) (C.2)
SC..m-1187p 2/3 1,3 Vlog m + (x,,, 0g), 0, 0, - A, mm)
where the first inequality holds due to triangle inequality. f(x,,; 0o) = by the random initial- ization of Oo. and the second inequality holds due to Lemma C.2 with the fact ||0,11 0ol1 <
21/mmx.
15

---

Published as a conference paper at ICLR 2022
Next, we bound the second term of Eq C.2
( 0o), 0 0o A, A,:b,///oo m)
(g(x 0o), 0--1 0. A, A, m (g( 0o), - A,'b,./
, 0o) 02)112 0o- b, + kg( 0o). A, bh//m A, b./ /
SC,,2 ()mA)) /TLA> + Cr,3 -//06///////////////////// 5/3 mi + T/X)
+ +(gg(x,,;00) A, b./ fr//m A, b./
(C.3)
where the first inequality holds due to the triangle inequality, the second inequality holds according with the fact
to Sauchy-Schwart inequality, and the third inequality holds due to Lemma that ||0-1 - 2 & 2/1/m and < T.
Now, we provide the upper bound of the last term in Eq C.3 Based on the definition of b, and b,, have
(g( (0) Ar
bi/ D...A,//////m A, b./bi//m) = (g( /m. A, E g(x.,a, 0o)
According to the definition of the added random noise 7/- -V(00, 2 and Lemma B.4 with 3r 2 0, we have the following inequality,
P. (g( 9o)/vm,A.
A,' Σ ==1 7 g(x : ml Bellg(x,,; mmll,,
gx 0o) m A,
<2exp
2x2g(Xx,15 00)T A, (2 1 g(x,,a,; 0n)g Xx,, 0o) /mm)A, (g 00)/m
<2exp
20
where the last inequality stands as,
A, TA," t-1
g(x,, 0u)
g(xx, g(x,, 00)gg(xx....) (0) Oo) //mm/m/A/ A 0u)/m
<g(x,, 00) A,
g(x, 0n)g(x.,, /mm + AI)A, A 0p)/m
=1g(xr,:; 0n)/ A.
Therefore, in round f, for the given arm i,
P, (gx, 00), A. - A, (.bbb//m) (x 0o)/ ml /mllaa')) 2 10l-esy exp((f3/(2o)),
Taking the union bound over K arms, we have that for any t:
Pr Vi E [K], (g(x, 0o), A, bi/ Vm A.'b.//m) s
21 K (exp(-B3/(20))
By choosing Br a / log log K, we have:
P. (Vi [K], (g 0o), A, b./Vm AT A.'b.//m) $ B 00)/V//la," 21
1
t²
This completes the proof.
C.3 PROOF OF LEMMA
The proof requires the anti-concentration bound of Gaussian distribution.
Lemma C.4. For a Gaussian random variable X NN, 02), for any 8 0.
X # 13 2
exp(-83)
4/7B
16

---

Published as a conference paper at ICLR 2022
Proof of Lemma 4.4 i [K].
Under event Er,,, according Lemma 4.2
C.2
and (C.3) we have, for all
(x 0.) h(xx,a;) - <(m))
2 0o), b// h/////m) (g(x Oo), A, b. (m) on (x),; 00)/ /m/ll,
According to the definition of A, by and b,, we have,
(g 6 00), A, ' / A Σ T g 0o) A g(x U.
which follows a Gaussian distribution with mean U = and variance Var[U:] as:
Var [r] =o²
g 0o) A
A, g(x 0u))
=0 (x 0o) A, λo
[gg( 0o)/ /m A,2
20 Va
x 00)/ / x=
g ( 0o) / - A,", where the second equality holds according to the definition of Ar. and the first inequality holds as for any positive meiineeinite matrix M Rddd
20 - YY (Ax)
x M 2 (M)x (A (M)M)) S Amax (M)
and Amii (At)
A (Ak). Therefore, based on Lemma C.4 by choosing a
a
A (Ax), the target probability could be lower bounded by,
(x 0() > h(x(,a;) c(m)) 2 P. > ar aellg(xx, 0o)/ /mll///lll,)
U
au aillg(x,, 00) h01l///llla
U²
N Pr
> 1) 2 dev
[.r
Var[U,]
Var[U.]
This completes the proof.
C.4 PROOF OF LEMMA 4.5
With the defined sufficiently sampled arms in round I, Ωr we have the set of undersampled Ω4 [K] 2z We also have the least uncertain and undersampled arm e in round defined as,
Proof of Lemma 4.5
argmin (lg(x;,ri 0o)/ vm A.
e,
jEN,
In round t, it is easy to verify that E[h(x(,;;) - h(xx,,,)) s B((h(xr,,;) - (1 + (.(
Under event E,, and E,,,, we have,
h(x(a;; - h(x(),a)
=h(x(,;;) - h(xx,,,)) + lx(xx,a)) 1((x4,a))
<A. + (Xtrer,) 0₂) - f (Xt, 0:) + 2m(m) + (B, + (lgg( 00)/ vml A, (g((x 00)/ 0m)m/ml x.
<4e(m) + (3. ar)) (2 (x 00) / A |lg(xe,o, 00) m0l//mll,,'
Next, we will bound E g (x,,,..; 0n) m A, .). It is easy to see that,
E [llg((xt,,; 0n)/ m 1-
-E [x]] 0o) ml A 1 E 24) Elllg(x,,,, (l)) 1fa e 24H
: Pip Qt).
17

---

Published as a conference paper at ICLR 2022
lim/mlaa A, I ( 0u)/vml A, (/aa Q4). Hence, It can be arranged llg(X1,e. 8 the one step regret can be bounded by the following inequality with probability at least - B(h(Xr,a;) - hxxx,a)))
<P(E222) + 4e(m) + (3, + az) (1+++)))))) 2/P((ce E ( (( 0o)/ /mll A,
For the probability Pa((a 24), we have:
(a s2,) > (3a S2 :2::((x:00) [xx,, 0.) > max (Xt,aa; ayElh
2P (xxe,a) 02) > max ayEst
((xt,a;;01). 0:))
Pr (f((,x 01) > max f(xi,a, 01), E1,2 occurs) efflt
2 (xx, 0,) > h(xx,a;) - <(m)) (2,2)
(Pr(E(,)) - Pr (E,2)
where the fourth inequality holds for 0j E S4 under event Et,1 and E,,: fxx,jji 0₂) S ((xx,)) + e(m) + (3t + 0r J 0o)/ mmll,, S h(xx.o;) E(m).
This completes the proof.
C.5 PROOF OF LEMMA 4.6
We first need the following lemma from Abbasi- Yadkori et al. (2011).
Lemma C.5 (Lemma 11. Abbasi- Yadkori al. (2011))
We have the following inequality:
det Ar
min [g((x,,,; 0
< 2
det AI
Lemma C.6 (Lemma B. Zhou al. 2020)). ) Let = [g(x*: Oo),... g(x 0o)l/ /m BXXK Let H be the NTK matrix as defined Definition B.1 For any 8 E 1),
I.0 log( T./6)
m =
then with probability at least 1 - 8, we have
G GG G
H||F S Ke.
Proof of Lemma 4.6
Denote G = [g(xt; 00)/ V g(x";; 00)/ Vml E RPxK then we have
det AT det AI
T I+ Σr g(xt,a; 0o) (x) 00) /(mm))
log
log det
S log det
T' I+ 1 Ex
K
00) /(m))
i=
log det
I+TGG /A)
log det (I+TGTG/A)
(C.4)
where the inequality holds naively, the third equality holds since for any matrix A E RpxK
have det(I + AAT T = det(I+ + A A). We can further bound Eq (C.4) as follows:
log det I IG G/A) G/A/)
log det
I I+TH/A+ T G G-H/A
< log det
I I+TH/A (I+ H)/A)
< log det
I I+ TH /
+
H|| T/X
< log det
1+TH/A /
+TVK G H
< log det
I TH/A /
+1 =1=1log(1 + +TK/A) +1,
18

---

Published as a conference paper at ICLR 2022
where the first inequality holds due to the concavity of logdet(.) the second inequality holds due to the fact that (A, B) S || [B]|,, the third inequality holds due to the facts that I + H/A > I, 2 and || I | for any A E RK*K the fourth inequality holds by Lemma C.6 with the required choice of m, the fifth inequality holds by the definition of effective dimension in Definition B.3 This completes the proof.
19


Reviews:
[{"review_id": "voDTei3xZ9-", "reviewer": "Reviewer_8GZW", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The idea of using the reward perturbation to avoid the exploration of the entire neural network is sharp. This allows their algorithm to significantly improve over NeuralUCB and NeuralTS in practice.   \n\nHowever, using the reward perturbation has been exploited in previous bandit models as in generalized linear bandits. This is also mentioned by the authors in the related works. Applying this idea to the neural bandits is straightforward. In an over-parameterization regime, the neural network behaves as the linear model. So I do not see technical challenges here because the main challenges of the neural bandits have been solved in both NeuralUCB and NeuralTS.  The used techniques of this paper is an adaptation of  NeuralUCB, NeuralTS to the situation with perturbed rewards. Indeed, Lemma 4.1 is similar to Lemma 5.1 in the NeuralUCB paper. Events $E_{t,1}$, $E_{t,2}$ are similar to the events $\\mathcal E^{\\mu}$ and $\\mathcal E^{\\sigma}$ defined in the neuralTS paper. Lemma 4.2 and Lemma 4.3 are similar to Lemma 4.3 and Lemma 4.2 in the NeuralTS paper, etc. \n\nIf the authors can show me the novelty in technical proofs compared to previous works, I will raise my score.\n \n\n ", "summary_of_the_paper": "This paper addresses the reduction of computational cost of the neural contextual bandit problem which uses the deep neural networks to model the reward function. Existing works in this field often require the exploration of the entire neural network parameter space\nand thus, the computation cost is expensive, especially when the network is large. Their main contribution is to perturb the rewards when updating the network to eliminate the need for exploration. They showed that this idea works well in experiments while still maintaining the same regret bound rate as that of previous works in the NTK regime.", "summary_of_the_review": "This is a good paper. It brings a solution that is much more practical than NeuralUCB and NeuralTS.  The experimental results are convincing. However, I think that the novelty is not enough. I am leaning forward to rejecting it.", "strength_and_weaknesses": "", "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": "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": "tk5BV8Rl3J", "reviewer": "Reviewer_NMyc", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "__Pros.__\n\n1. The algorithm is practical as the neural network training is unaffected by the exploration strategy. This is a big advantage over NeuralTS and NeuralUCB.\n\n2. The paper uses the same idea as [Kveton et al 2020] however it rigorously proves regret guarantees for the neural network function class under the NTK setting.\n\n3. The regret guarantee only scales with the effective dimension (Valko et al 2013) of the NTK.\n\n4. The experiments show some promise in real world datasets especially because of the predictably better running times than NeuralUCB.\n\n__Cons.__\n\nI have some general clarifying questions and some comments, which will hopefully improve the quality of the paper.\n\n1. My biggest concern is that the paper fails to discus and compare with the line of work in FALCON (https://arxiv.org/pdf/2003.12699.pdf). Both the papers lie in the realizable setting. FALCON also does not need to modify the training of the neural network in any way and in fact needs to train the model even less frequently based on an epoch schedule. Further I think the guarantees of FALCON will probably hold with a similar regret term; basically the generalization error from the NTK will appear in Assumption 2 and Theorem 2 in https://arxiv.org/pdf/2003.12699.pdf. I think the paper should definitely have a discussion with this. Besides the paper should also compare with this algorithm in the experiments as it is easy to implement.\n\n2. The $\\lambda$ term is missing from Equation 3.2. In algorithm 1 how is $\\nu$ set -- can the authors please point me to wherever this is defined in the paper? What setting of $\\nu$ is used in practice in the experiments? Also, in practice is the neural network trained per time-step as in the algorithm pseudocode? That would be pretty prohibitive in practice. \n\n3. (minor) In the def of $\\bar{b}_t$ in page 4 the expectation of $\\gamma_s^{t-1}$ is zero, right?  Then is this just for the sake of readability?\n\n4. The reference to definition of effective dimension is broken in page 5.\n\n5. In the synthetic experiments in Figure 1 it does seem that all algorithms kind of have a linear regret scaling. It would be great if we can add a full information algorithm (algorithm that sees reward from all arms chooses greedily). Such an oracle algorithm would show the lower bound on the achievable regret. I could find that the real experiments in Figure 2 are averaged over 10 runs, is such an averaging performed in the simulated setting. If so, then please also plot the confidence bars. \n\nAlso subsampling k arms out of a total of 100 arms each time is slightly non-standard. It would be good if the algorithms are just compared over a fixed set of 10, 20, 50 and 100 arms, that are decided in the beginning and held fixed over the rounds.\n\n6. In all experiments, as before it would be great if the following baselines (or moonshots) can be added\n-- FALCON\n-- Greedy (bandit feedback plus choosing the arms greedily)\n-- Full information (full information feedback and the arms are chosen greedily)\n", "summary_of_the_paper": "The paper studies neural contextual bandits in the realizable setting. It proposes an algorithm that trains the neural network that maps arm contexts to rewards, with perturbed rewards. The paper proves that under NTK analysis the learnt function provides an optimistic estimate of the reward of each arms and therefore sub-linear regret guarantees can be derived. Crucially the dimension term in the regret only depends on the effective dimension of the NTK. Some experiments are performed on real and synthetic datasets where the proposed algorithm performs at par with neuralTS and neuralUCB algorithms while cutting down the running time by a large factor. Thus this can indicate the practicality of the proposed algorithm.", "summary_of_the_review": "I think the pros above outweigh the cons slightly in my mind. I am happy to raise the score if the authors can answer 1 and 6 among the cons.", "strength_and_weaknesses": "", "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": "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": "N5nYNnBeARg", "reviewer": "Reviewer_ha3h", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "PROS:\n\n•\tThe paper is very nicely written. I found it very easy to follow even the more complex aspects and the introduction does a good job of motivating the work and providing a useful history of the relevant literature.\n\n•\tThe central idea of the paper is a useful and sensible combination and extension of existing techniques. It seems to work effectively, in addition to having desirable theoretical properties, and should be interesting to the ICLR community.\n\nMAJOR COMMENTS ON CONS:\n\n•\tWhat can be said in terms of order results on the computational cost of NPR versus NeuralUCB/NeuralTS? The empirical comparison is useful, but to have both would solidify the core argument for the usefulness of NPR and be quite informative.\n\n•\tThe biggest issue I can see is that the experimental results are not as informative as they could be. Firstly, they do not give a sense of the distribution of regret over different runs, and second, they do not (in the fully synthetic scenario) seem to be run for long enough to show that the algorithms have converged. All the regret plots look linear but with differing gradients in fig 1. Can you remedy this?\n\n•\tThe use of grid-search to select $\\eta$ perhaps needs some commentary as the theoretical guarantees section talks about a specific value $\\eta$ for the theoretical guarantees to hold. The diagonalised algorithms are criticised for losing theoretical guarantees, but does this optimisation of $\\eta$ not affect the theoretical guarantees of your approach?\n\nMINOR COMMENTS ON CONS\n\n•\tThe definition of $f(x,\\theta)$ may be better in an equation display as the page break in the middle of it is unfortunate.\n\n•\tMiddle of page 3: should be “When all the $K$ arms have been pulled once” not “for once”. \n\n•\tIf I were aiming to improve the commentary on the theory, I would perhaps add a paragraph to the start of Section 4 to highlight what the main challenges/novelties in the theory are – as I understand this it is the design of the noise and of the step-size in the gradient descent? This would help the reader get a clear picture of what is more/less standard going in to this section.\n\n•\tThe regret bound achieved in Theorem 4.7 is (understandably) quite complex and not directly compared to the regret of the competitor algorithms. I think there would be value in giving some commentary afterwards to highlight the dependence on the main terms such as T and K and \\tilde{d} and how this compares to NeuralUCB/TS.\n", "summary_of_the_paper": "The paper considers a version of the stochastic contextual bandit where the underlying reward function is modelled by a deep neural network. This framework is useful for a number of complex problems where simpler parametric models of the reward are insufficient. The authors propose an algorithm inspired by the perturbed reward approaches of Kveton et al (2019a,b,2020) which ensures an exploration-exploitation balance by adding additional noise to the observed rewards. This approach avoids the inversion of large covariance matrices which existing approaches (NeuralUCB and NeuralTS) necessitate, and results in a computational speed-up while maintaining near-optimal regret guarantees.", "summary_of_the_review": "I’m very positive about the idea behind this paper: to use combine perturbed rewards with neural contextual bandits and think that this work is timely and potentially very impactful. I have a few reservations about the extent to which experiments support the main claims of the paper, and as such have chosen a borderline score which I could increase if my concerns are addressed.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Lofc0aItuQg", "reviewer": "Reviewer_ZmVR", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n* Unlike the algorithms in existing literatures which are either computationally intractable or has no theoretical regret upper bound using approximate computations, NPR is computationally tractable and has nearly optimal regret upper bound.\n* Extensive experiments are conducted to compare the practical performance between the proposed algorithm and the ones in existing literatures.\n\nWeaknesses\n* NPR is technically sound but hard to be applied to practical applications due to that 1) During each time step, the algorithm has to use all of the previous rewards. When the time horizon T is large, the computation becomes expensive. 2) The model studied is a K-armed setting where during each time step, the learner are facing the *same* set of arms. For practical applications, it is more reasonable to assume the arms set faced during each time step is different.\n* The originality of the techniques used to prove the regret upper bound is limited. If I read the paper correctly, it seems the key lemma (Lemma 4.1) is from Jacot et al., 2018. It might be better if the authors could spend one paragraph to discuss the technique originality.\n* The experiment setup seems to be different from the one discussed in this paper.", "summary_of_the_paper": "This paper investigates neural contextual bandit problem. A new, computationally tractable and efficient algorithm (Neural bandit with perturbed reward, NPR) is proposed and proved to suffer a nearly optimal minimax regret upper bound.", "summary_of_the_review": "Personally, I like the idea using perturbed rewards to implicitly let the neural network to explore. However the proposed algorithm is still hard to be applied to practical applications. \n\nDetailed comments:\n\nEquation 3.2: parameter $\\lambda$ is missing?\n\nAfter Lemma 4.3: ... the the neural network ...  the extra the should be removed\n\nLemma 4.4: it might be better if the authors could define $E_{t, 3}$ in the beginning of Lemma 4.4.\n\nAfter Lemma 4.6: please resolve the cross reference error\n\nExperiment 5.1: It is confused to me that `At each round t, only a subset of k arms out of the total K arms are sampled without replacement and discosed to all algorithms for selection.` Could the authors help explain why the algorithms are restricted to pull $k < K$ arms which seems to be different from the one discussed in this paper?\n\n", "strength_and_weaknesses": "", "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": "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": {}}]

Author rebuttal:

Meta-review: This paper studies the design and analysis of contextual bandits algorithms, combining the ideas of neural network models (Zhou et al, 2020 and Zhang et al, 2020) and reward perturbations (Kveton et al, 2019, 2020); this has the computational advantage of avoiding inverting large covariance matrices, as is done in the other neural contextual bandits algorithms. Although the reviewers think that the papers need to do a better job in highlighting differences and extra challenges in the current work compared to prior works, they also acknowledge that this paper is the first that combines the above two ideas. 

The reviewers also acknowledge that the additional experiments in the rebuttal period help clear the concern the reviewers have about why all regret curves look linear. However they also pointed out, that comparison with the FALCON+ algorithm (Foster et al, 2020) may be slightly unfair, as the algorithm retrains the neural network after every new iteration. Overall, the reviewers think that the pros outweight the cons, and they lean towards acceptance.
Decision: Accept (Poster)