Neural Contextual Bandits with Deep Representation and Shallow Exploration
Authors: Pan Xu
Zheng Wen
Handong Zhao
Quanquan Gu
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Deep Learning
Multi-armed Bandits
Contextual Bandits
Computational Efficiency

Abstract: We study neural contextual bandits, a general class of contextual bandits, where each context-action pair is associated with a raw feature vector, but the specific reward generating function is unknown. We propose a novel learning algorithm that transforms the raw feature vector using the last hidden layer of a deep ReLU neural network (deep representation learning), and uses an upper confidence bound (UCB) approach to explore in the last linear layer (shallow exploration). We prove that under standard assumptions, our proposed algorithm achieves $\tilde{O}(\sqrt{T})$ finite-time regret, where $T$ is the learning time horizon. Compared with existing neural contextual bandit algorithms, our approach is computationally much more efficient since it only needs to explore in the last layer of the deep neural network.

Neural Contextual Bandits with Deep Representation and Shallow Exploration
Anonymous Author(s)
Affiliation Address email
Abstract
We study neural contextual bandits, a general class of contextual bandits, where each context-action pair is associated with raw feature vector, but the specific reward generating function unknown. We propose a novel learning algorithm that transforms the feature vector using the last hidden layer of deep ReLU neural network (deep representation learning). and uses an upper confidence bound (UCB) approach to explore in the last linear layer (shallow exploration). We prove that under standard assumptions, our proposed algorithm achieves Ö(VT) finite- time regret, where T is the learning time horizon. Compared with existing neural contextual bandit algorithms, our approach is computationally much more efficient since it only needs to explore in the last layer of the deep neural network.
3
5
Introduction
11
12 Multi-armed bandits (MAB) [9, 8, 30] are a class of online decision-making problems where an agent needs learn to maximize its expected cumulative reward while repeatedly interacting with
14 partially known environment, Based on a bandit algorithm (also called a strategy or policy), in each
15 round, the agent adaptively chooses an arm, and then observes and receives a reward associated with
16 that arm. Since only the reward of the chosen arm will be observed (bandit information feedback),
17 good bandit algorithm has deal with the exploration-explootttion dilemma: trade-off between
18 pulling the best arm based on existing knowledge/history data (exploitation) and trying the arms that have not been fully explored (exploration).
19
20 In many real-world applications, the agent will also be able to access detailed contexts associated
21 with the arms. For example, when company wants choose advertisement to present user,
22 the recommendation will be much more accurate if the company takes into consideration the contents, specifications, and other features of the advertisements in the
well as the profile of the user. 24 To encode the contextual information, contextual bandit models and algorithms have been developed,
25 and widely studied both in theory and in practice [19, 39, 34, 16, 1]. Most existing contextual bandit
26 algorithms assume that the expected reward of an arm at a context is a linear function in a known context-action feature vector, which leads to many useful algorithms such as LinUCB [16], OFUL [1], 28 etc. The representation power of the linear model can be limited in applications such as marketing, social networking, clinical studies, etc., where the rewards are usually counts or binary variables. The linear contextual bandit problem has also been extended to richer classes of parametric bandits such
27
29
30
31 as the generalized linear bandits [24, 35) and kernelised bandits [44, 15).
32 With the prevalence of deep neural networks (DNNs) and their phenomenal performances in many
33 machine learning tasks [32, 25], there has emerged line of work that employs DNNs increase the
34 representation power of contextual bandit algorithms [5, 38, 17, 49, 52, 20, 51]. The problems they
35 solve are usually referred as neural contexiual bandits. For example, Zhou et al. [52] developed
38 the NeuralUCB algorithm, which can be viewed as a natural extension of LinUCB [16, 1], where they
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

37 use the output of a deep neural network with the feature vector as input to approximate the reward.
38 Zhang et al. [51] adapted neural networks in Thompson Sampling [43. 14, 40] for both exploration and exploitation and proposed NeuralTTS. For a fixed time horizon T, it has been proved that both NeuralUCB and NeuralTS achieve O(d'T) regret bound, where d is the effective dimension of neural tangent kernel matrix which can potentially scale with O(T for K-armed bandits. This high complexity is mainly due to that the exploration is performed over the entire huge neural network parameter space, which is inefficient and even infeasible when the number of neurons is large. A more realistic and efficient way of learning neural contextual bandits may be to just explore different arms using the last layer as the exploration parameter. More specifically, Riquelme et al. [38] provided an extensive empirical study of benchmark algorithms for antextual-banditt through the lens of Thompson Sampling, which suggests decoupling representation learning and uncertainty estimation improves performance.
39
41
43
44
45
46
47
48
49
In this paper, we show that the decoupling of representation learning and the exploration can be theoretically validated. We study new neural contextual bandit algorithm, which learns mapping to transform the raw features associated with each context-action pair using a deep neural network (deep representation), and then performs an upper confidence bound (UCB)-type exploration over the linear output layer of the network (shallow exploration). We prove a sublinear regret of the proposed algorithm by exploiting the UCB exploration techniques in linear contextual bandits [1] and the analysis of deep overparameterized neural networks using neural tangent kernels [27]. Our theory confirms the empirically observed effectiveness of decoupling the deep representation learning and the UCB exploration in contextual bandits [38, 49].
51
52
53
54
55
56
57
Contributions summarize the main contributions of this paper as follows.
59
We propose a contextual bandit algorithm, Neural-LinUCB, for solving a general class of con- textual bandit problems without knowing the specific reward generating function. The proposed algorithm learns a deep representation to transform the raw feature vectors and performs U'CB-type exploration in the last layer of the neural network, which we refer to as deep representation and shallow exploration. Compared with LinUCB [34, 16] and neural bandits such as NeuralUCB [52] and NeuralTS [51], our algorithm enjoys the best of two worlds: strong expressiveness due the deep representation and computational efficiency due to the shallow exploration.
61
68
64
85
Despite the usage of a DNN the feature mapping, we prove a Ö(VT) regret for the proposed Neural-LinUCB algorithm, which matches the regret bound of linear contextual bandits [16, 1]. To the best of our knowledge, this is the first work that theoretically shows the convergence of bandits algorithms under the scheme of deep representation and shallow exploration. It is notable that a similar scheme called Neural-Linear was proposed by Riquelme al. [38] for Thompson sampling algorithms, and they empirically showed that decoupling representation learning and uncertainty estimation improves the performance. Our work confirms this observation from theoretical perspective.
67
69
70
71
72
73
74
We conduct experiments on contextual bandit problems based on real-world datasets, demon- strating a better performance and computational efficiency of Neural-LinUCB over LinUCB and NCuralUCB, which well aligns with our theory.
76
77
1.1
Additional related work
There is line of related work to ours on the recent advance in the optimization and generalization 79 analysis of deep neural networks. In particular, Jacot et al. [27] first introduced the neural tangent
78
80 kernel (NTK) to characterize the training dynamics of network outputs in the infinite width limit.
81 From the notion of NTK, a fruitful line of research emerged and showed that loss functions of deep neural networks trained by (stochastic) gradient descent can converge to the global minimum [22, 4, 21, 54, 53]. The generalization bounds for overparameterized deep neural networks are also established in Arora et al. [6. 71, Allen-Zhu et al. [3], Cao and Gu [12, 13]. Recently, the NTK based analysis is also extended to the study of sequential decision problems including bandits [52, 51], and reinforcement learning algorithms 11, 36, 47].
83
84
85
87 Our algorithm is also different from Langford and Zhang [29], Agarwal et al. [2] which reduce the bandit problem to supervised learning. Moreover, their algorithms need to access an oracle that returns the optimal policy in a policy class given sequence of context and reward vectors, whose regret depends on the VC-dimension of the policy class.
88
89

---

91
Notation We use [k] to denote a set [l,....k), EN ||x|| ' 82 a vector x E Rd. For a matrix W E Rmxx, we denote by [Wll and || its operator norm and Frobenius norm respectively. For a semi-definite matrix A E IRddd and a vector x E IR", we denote the Mahalanobis norm as ||x||A = v Ax. Throughout this paper, we reserve the notations it,,,....... represent absolute positive constants that are independent of problem parameters such as dimension, sample size, iteration number, step size, network length and so on. The specific values of {C.)i=0.1... can be different in different context. For a parameter of interest T and a function ((T), we use notations such as O()(T)) and ((((T) to hide constant factors and (((()) to hide constant and logarithmic dependence of T.
v is the Euclidean norm of
93
94
95
96
97
98
89
2
Preliminaries
100
101
In this section, we provide the background of contextual bandits and deep neural networks.
102
2.1
Linear contextual bandits
103
contextual bandit is characterized by a tuple (S, A.). where S is the context (state) space, is the arm (action) space, and r encodes the unknown reward generating function at all context-arm pairs. learning agent, who knows and A but does not know the true reward r (values bounded in (0. 1) for simplicity), needs to interact with the contextual bandit for T rounds. At each round i = 1..... T. the agent first observes a context 8; E S chosen by the environment; then needs adaptively select an arm E A based on its past observations; finally it receives reward Fr (Xs,a,) r(x.a,) + & where x..a Rd is a known feature vector for context-arm pair (s, a) E S x A, and & is a random noise with zero mean. The agent's objective is to maximize its expected total reward over these T rounds, which is equivalent to minimizing the pseudo regret [8]:
104
105
106
107
109
110
T
RT Σ (F(x)),;;) - - ((Xx)a)))
(2.1)
112 where oz E (frmaxxexfr(X.... (x,(,,,, )). To simplify the exposition, we use Xt,a to denote
113 X since it only depends on the round index in most bandit problems, and we assume A [K].
114 In some practical problems, the agent has a prior knowledge that the reward-generating function
115 r has some specific parametric form. For instance, in linear contextual bandits, the agent knows
116 that r(x,.a) = x 0" for some unknown weight vector 0 с Rd One provably sample efficient algorithm for linear contextual bandits is Linear Upper Confidence Bound (LinUCB) [1]. Specifically,
118 at each round f, LinUCB chooses action by the following strategy
xa Os + Cg (xx )
ag arginax aE[K]
119
where 0, is a point estimate of 0", A, = AI Σl defined based on the historical context-arm pairs, and ar > O tuning parameter that controls the exploration rate in LinUCB
Xi,
x L.o with some > 0 is a matrix
120
121
122
2.2
Deep neural networks
In this paper, we use f(x) to denote a neural network with input data x E Rd. Let L be the number of hidden layers and W: Rm be the weight matrices in the 1-th layer, where - 1,..., L,
123
125 m. = =... m = m and mg = m, = d. Then a L-hidden layer neural network is defined as
f(x) 0 oz. (W 1 (W f--1 oi (W .)x)...)),
(2.2)
where is an activation function and 0* E Rd is the weight of the output layer. To simplify the presentation, we will assume 01 02
126
127
= ar. = a is the ReLU activation function, i.e., (x) max (0, 2r for E RR We denote = (vec(W,)T ...., vec(W,,))
which is the 129 concatenation of the vectorized weight parameters of all hidden layers of the neural network. We also
write fx; 0*, w) fx) in order to explicitly specify the weight parameters of neural network f. It
3

---

131 is easy to show that the dimension p of vector w satisfies p (L - 2)m² + 2md. To simplify the
132 notation, we define Φ(x; w) as the output of the L-th hidden layer of neural network f.
(x:: w) = Vmo W L WL-1 ... ..x)...)).
(2.3)
133
Note that Φ(x; w) itself can also be viewed as neural network with vector-valued outputs.
3
Deep Representation and Shallow Exploration
134
135
The linear parametric form in linear contextual bandits might produce biased estimates of the reward due to the lack of representation power [42, 38.. In contrast, it is well known that deep neural networks powerful enough to approximate an arbitrary function [18]. Therefore, natural extension of linear contextual bandits is to use a deep neural network to approximate the reward generating
136
137
138
139
function r(-). Nonetheless, DNNs usually have a prohibitively large dimension for weight parameters.
140
which makes the exploration in neural networks based UCB algorithm inefficient [28, 52].
In this work, we study neural contextual bandit algorithm, where the hidden layers of a deep neural network are used to represent the features and the exploration is only performed in the last layer of the neural network. In particular, we assume that the reward generating function r(-) can be expressed as the inner product between a deep represented feature vector and an exploration weight parameter, namely, r(.) = (0", vb()), where 0" E Rd is some weight parameter and (b()) is an unknown feature mapping. This decoupling of the representation and the exploration will achieve the best of both worlds: efficient exploration in shallow (linear) models and high expressive power of deep models. To learn the unknown feature mapping, we propose to use a neural network to approximate it. In what follows, we will describe a neural contextual bandit algorithm that uses the output of the last hidden layer of a neural network to transform the raw feature vectors (deep representation) and performs UCB-type exploration in the last layer of the neural network (shallow exploration). Since the exploration is performed only in the last linear layer, we call this procedure Neural-LinUCA which is displayed in Algorithm 1.
142
144
145
146
147
148
149
150
151
152
153
154
Specifically, in round 1, the agent receives an action set with raw features X₂ = (x..1....,,. x. Then the agent chooses
155
a, that maximizes the following upper confidence bound:
ag = argmax { ( (o((xxi:.--)) 0.-1) + aello(x,,x wi-1)lla=1 kE(K]]
(3.1)
156
where 0,- is point estimate of the unknown weight in the last layer, ((x; w) is defined as in (2.3),
Wi-1 is estimate of all the weight parameters in the hidden layers of the neural network, ay > 0 is the algorithmic parameter controlling the exploration, and A, is a matrix defined based on historical transformed features:
158
A, = AI Σ (.-))()( T
(3.2)
160 and À >>0 0. After pulling arm ae, the agent will observe a noisy reward P. = F(xe,a)) defined
F(x,,) = r(x,,)) + Ee:
(3.3)
161
where & is an independent v-subGaussian random noise for some > 0 and r(-) is an unknown reward function. In this paper, we will interchangeably use notation Fr to denote the reward received 163 at the t-th step and an equivalent notation f(x) to express its dependence on the feature vector x.
162
184
Upon receiving the reward fr. the agent updates its estimate 0, of the output layer weight by using the same 8 regellaarie least-squares estimate in linear contextual bandits [1]. In particular, we have
165
0. = A
(3.4)
186 where b, = Ein P.o(Xi,..) 1)
167
To save the computation, the neural network cb:: we) will be updated once every H steps. Therefore,
188 we have W(g-1)H+1 =... Will for q = 1, 1,2, .... We call the time steps - ( +1.... H
an epoch with length H. At time step t = Hq. for any g = 1,2,... .., Algorithm 1 will retrain the

---

170 neural network based on all the historical data. In Algorithm 2, our goal is to minimize the following
171 empirical loss function:
9 (w(w) = Σ (0_ ((xi,a, w) -ri)²
(3.5)
172 In practice, one further save computational cost by only feeding data (Xi,a,; Pi, ) (=(
from the q-th epoch into Algorithm 2 to update the parameter Wt, which does not hurt the performance 174 since the historical information has been encoded into the estimate of 0, In this paper, we will
173
175
perform the following gradient descent step
W (6) w(s-1)
T7 V VwLy(
for s = 1,..., n, where Wq w(O) (0) is chosen as the same random initialization point. We will
176
discuss more about the initial point w in the next paragraph. Then Algorithm 2 outputs (n) and
177
178
we set it as the updated weight parameter w W in Algorithm 1. In the next round, the agent will receive another action set X++1 with raw feature vectors and repeat the above steps to choose the sub-optimal arm and update estimation for contextual parameters.
179
180
Initialization: Recall that w is the collection of all hidden layer weight parameters of the neural network. We will follow the same initialization scheme as used in Zhou et al. [52], where each entry of the weight matrices follows some Gaussian distribution. Specifically, for any 1 f1...., L 1}.
182
W
0
184
we set W, =
O
W
where each entry of W follows distribution N (0, 4/m) independently; for
185
W we set it as IV VI, where each entry of V follows distribution N 2/m) independently.
Comparison with LinUCB and NeuralUCB: Compared with linear contextual bandits in Sec- tion 2.1, Algorithm has a distinct feature that learns a deep neural network to obtain a deep representation of the raw data vectors and then performs UCB exploration. This deep representa- tion allows our algorithm to characterize more intrinsic and latent information about the raw data & k he[T),,E K] Rdd However, the increased complexity of the feature mapping ((: w) also introduces great hardness in training. For instance, a recent work by Zhou et al. [52] also stud- ied the neural contextual bandit problem, but different from (3.1), their algorithm (NeuralUCB) performs the UCB exploration on the entire network parameter space, which is Re+d, where P m + md + (L 1)m² Note that in Zhou et al. [52], they need to compute the inverse of a matrix Z, E ((+++) which is defined in a similar way the matrix A, in our paper except that Z, is defined based on the gradient of the network instead of the output of the last hidden layer as in (3.2). In sharp contrast, A, in our paper is only of size efficient and practical in implementation, which will be seen from our experiments in later sections.
187
188
189
190
181
182
193
194
195
196
197
d and thus is much more
198
We note that there is also a similar algorithm our Neural-LinUCB presented in Deshmukh et al. [00], where they studied the self-supervised learning loss in contextual bandits with neural network representation for computer vision problems. However, no regret analysis has been provided. When the feature mapping Φ(: w) is an identity function, the problem reduces to linear contextual bandits where we directly use x, as the feature vector. In this case, it is easy see that Algorithm 1 reduces to LinUCB [16] since we do not need to learn the representation parameter w anymore.
200
202
203
204
Comparison with Neural-Linear: The high-level idea of decoupling the representation and explo- ration in our algorithm is also similar to that of the Neural-Linear algorithm [38, 49], which trains a deep neural network to learn representation of the raw feature vectors, and then uses Bayesian linear regression to estimate the uncertainty in the bandit problem. However, these two algorithms significantly different since Neural-Lineat [38] is Thompson sampling based algorithm that uses posterior sampling to estimate the weight parameter 0" via Bayesian linear regression, whereas Neural-LinnUc adopts upper confidence bound based techniques to estimate the weight 0". Never- theless, both algorithms share the same idea of deep representation and shallow exploration, and we view our Neural-LinUCB algorithm as one instantiation of the Neural- scheme.
206
208
210
212
213
214
4
Main Results
215
To analyze the regret bound of Algorithm 1, we first lay down some important assumptions on the neural contextual bandit model.
5

---

Algorithm Deep Representation and Shallow Exploration (Neural-LinUCCB)
1: Input: regularization parameter À > O, number of total steps T, episode length H, exploration parameters (az > ()
2: Initialization: Ao = AI, bo 0; entries of 0g follow NN0 1/d), and w( is initialized as described in Section 3; 9 = 1; Wo w())
3: to 1,..,, do
4: receive feature vectors (x.,....... ................................ Xx,K
5: choose arm az kE[K 0 1 (x wi-1) torllo(x,, 1l-1) and obtain
reward Fr
6: update A, and b, as follows:
A, = A,- ((xt,a We-1 (
b, b (xt,aa Wx-1);
7:
update 0, A, b,
8:
if mo H) = 0 then
9:
W: output Algorithm
10:
= +
else
12:
W
end if
14: end for
15:
Output WT
Algorithm Update Weight Parameters with Gradient Descent
1: Input: initial point wa (0)
w maximum iteration number step size Th2 and loss function
defined (3.5).
2: for 1,,..... 1..... do
3: Wq w. (a-1)
(+)
ng V. Cw (
4: end for
5: Output w.
(n)
Assumption 4.1. For all 1 and l [K]. assume that ||x,,elle and its entries satisfy [ = =xy,xlj+d/2-
218
219
The assumption that ||2, = not essential and only imposed for simplicity, which is also used in Zou and Gu [53], Zhou et al. [52]. Finally, the condition the entries of x1, is also mild since otherwise
could always construct x [x]_x- / //2 replace it. An implication of
Assumption 4. 1.1 is that the initialization scheme Algorithm results in Φ(x;, (() = for all
222
223
i
[T] and & [K].
224
assume the following stability condition on the spectral norm of the neural network gradient:
225
Assumption 4.2. There a constant 4p 0 such that holds
Ow (x'; wo)
aΦ
Ow (x: wo)
S & x1122
226
for all x, x' (xx,A)eerT,AEE
227
The inequality in Assumption 4.2 resembles the Lipschitz condition on the gradient of the neural network. However, it is essentially different from the smoothness condition since here the gradient is taken with respect to the neural network weights while the Lipschitz condition is imposed on the feature parameter x. Similar conditions are widely made in nonconvex optimization [46, 10, 48], in the name of first-ordes stability, which is essential to derive the convergence of alternating optimization algorithms. Furthermore, Assumption 4.2 is only required on the TK K training data points
228
229
230
232
specific weight parameter wo. Therefore, the condition will hold if the raw feature data lie in
certain subspace of d We provided some further discussions in the supplementary material about this assumption for interested readers.
234

---

236 In order to analyze the regret bound of Algorithm 1, we need to characterize the properties of the 237 deep neural network in (2.2) that is used represent the feature vectors. Following a recent line of research [27, 12, 7, 52], we define the covariance between two data point x, R as follows.
10 y) ( (x, y) y,
Σ (x.x) Σ yx.
A A (x.y) = Σ (y,))
Σ (y.
(x,y) = 2B (( (
5 (x.y) = 2) (x, y En ( + (x,))
(4.1)
where (u, v) N( A (1-1) (x. y)), and (.) is the derivative of activation function (t). We denote 240 the neural tangent kernel (NTK) matrix H E TR x based on all feature vectors {xt,* [e(T)
241
Renumbering he(T) as (x; (x=),1,,....71 TK. then each entry Hiy is defined as
H = D (0 (x,, (x,,xy) + (x,, x,)),
(4.2)
for all i.j E [TK]. Based on the above definition, impose the following assumption H. Assumption 4.3. The neural tangent kernel defined in (4.2) is positive definite, i.e., Amin (H) 2 Ao for some constant A > O.
244
Assumption 4.3 essentially requires the neural tangent kernel matrix H to be non-singular, which is a mild condition and also imposed in other related work [21, 7, 12, 52]. Moreover, is shown that Assumption 4.3 can be easily derived from Assumption 4.1 for two-layer ReLU networks [37, 53). Therefore, Assumption 4.3 is mild or even negligible given the non-degeneration assumption on the feature vectors. Also note that matrix H is only defined based on layers = 1, ...... I. of the neural network, and does not depend on the output layer O. It is easy to extend the definition of H to the NTK matrix defined on all layers including the output layer 0, which would also be positive definite by Assumption 4.3 and the recursion in (4.2).
246
247
248
250
251
252
Before we present the regret analysis of the neural contextual bandit, need to modify the regret defined in (2.1) to account for the randomness of the neural network initialization. For a fixed time horizon T, we define the regret of Algorithm 1 as follows.
254
T
RT
(F(xea;) - (w
(4.3)
256
where the expectation is taken over the randomness of the reward noise. Note that Ry defined in (4.3) is still a random variable since the initialization of Algorithm 2 is randomly generated.
258
Now are going to present the regret bound of the proposed algorithm.
Theorem 4.4. Suppose Assumptions 4. 4.2 and 4.3 hold. Assume that 100 12 M for some positive constant M > 0. For any E (0, 1), let us choose on in Neural-LinUCCB as
260
a₁ = v (d + t log log(1/6)) M.
We choose the step size Tl of Algorithm 2 as
B1 S (o m. 1 log log(TK/8)) -1
282 and the width of the neural network satisfies m poly d, 1/5, H, (TK()) With probability 263 at least 1 over the randomness of the initialization of the neural network, it holds that
Rr < Carr Tdlos (1
TG2 Xd
1. log log(E) ) log( 6
TK
)|r Fllex
m 1/6
284
where (C, are absolute constants independent of the problem parameters, r E R and F = (f(xi: Co,
285
Or wT-1)) E
TTK and ||||| V
7

---

267
Remark 4.5. Theorem 4.4 shows that the regret of Algorithm 1 can be bounded by two parts: the first part is of order Ö(VT), which resembles the regret bound of linear contextual bandits [I]: the second part is of order O(m 1 - Hr f)). which depends on the estimation error of the neural network f for the reward generating function r and the neural tangent kernel H.
269
270
271
It is worth noting that our theoretical analysis depends on the reward structure assumption that r()) = (0+, (b))) However, the linear structure between Ox and (b(-) is not essential. As long as the deep representation of the feature vector and the uncertainty weight parameter can be decoupled,
272
273
274
Algorithm 1 can be easily extended to settings with milder assumptions on the reward structure such as generalized linear models [41, 24, 35, 28]. For more general bandit models where no assumption is imposed to the reward generating function, still unclear whether the decoupled deep representation and shallow exploration would work especially in cases a thorough exploration may be needed.
276
278
279
Based on the result in Theorem 4.4, we can easily verify the following conclusion:
Corollary 4.6. Under the same conditions of Theorem 4.4, if we choose sufficiently overpa- rameterized neural network mapping (-) such that m 2 T then the regret of Algorithm is
281
RT = ((VVV(r rr H (r-
282
Remark 4.7. For the ease of presentation, let us denote & - If we have & (()) the
total regret in Theorem 4.4 becomes Ö(VT) which matches the regret of linear contextual bandits
284
[1]. We remark that there is similar assumption in [52] where they assume that Hr can be upper bounded by constant. They show that this term can be bounded by the RKHS norm of r if belongs the RKHS induced by the neural tangent kernel [6. 7, 33]. In addition, & here is the difference between the true reward function and the neural network function, which can also be small if the deep neural network function well approximates the reward generating function r(-).
285
286
287
298
289
Experiments
290
291
In this section, we provide empirical evaluations of Neural-LinUCB on real-world datasets. As we have discussed in Section 3, Neural-LinUCBB could be viewed an instantiation of the Neural- Linear scheme studied in Riquelme et al. [38] except that we use the UCB exploration instead of the posterior sampling exploration therein. Note that there has been an extensive comparison [38] of the
292
293
285
Neural-Linear methods with many other baselines such as greedy algorithms, Variational Inference, Bayesian Kon-parametrics and so on. Therefore, we do not seek thorough empirical comparison of Neural-LinUCC with all existing bandits algorithms. We refer readers who interested in the performance of Neural-Linear methods with deep representation and shallow exploration compared with a vast of basclines in the literature to the benchmark study by Riquelme al. [38]. In this experiment. we only aim to show the advantages of our algorithm over the following baselines: (I) Neural-Lines [38]; (2) LinUCB [16], which does not have a deep representation of the
296
Expectation-Propagee
297
298
299
300
301
302
feature vectors; and (3) NeuralUCB [52], which performs UCB exploration on all the parameters of
303
the neural network instead of the shallow exploration used in our paper. All numerical experiments
304
were run on a workstation with Intel(R) Xeon(R) CPU E5-2637 v4 @ 3.50GHz.
305
we evaluate the performances of all algorithms on bandit problems created from real-world data Specifically, following the experimental setting in Zhou et al. [52]. we use datasets (Shuttle) Statlog, Magic and Covertype from UCI machine learning repository [23], and the MINST dataset
Datasets:
306
307
308
from LeCun et al. [31]. The details of these datasets are presented in Table 1. In Table 1, each instance represents a feature vector x E Rd that is associated with one of the K arms, and dimension
309
310
is the number of attributes in each instance.
Table 1: Specifications of datasets from the UCI machine learning repository used in this paper.
Starlog
Magic
Covertype
MNIST
Number of attributes
9
11
54
784
Number of arms
7
2
7
10
Number of instances
58,000
19,020
581,012
60,000
8

---

800
Ledca
4930
5330
knuca
5002
2000
200
3920
5300
2007
400
2008
2230
3330
4330
1003
1583
sourd
rsund
round
sund
(a) Statlog
(b) Magic
(c) Covertype
(d) MNIST
Figure I: The cumulative regrets of LinUCB, NeuralUCB, Neural-Linear and Neural-LinUCK over 15, 000 rounds. Experiments are averaged over 10 repetitions.
311
Implementations: for LinUCB, we follow the setting in Li et al. [34] use disjoint models for different arms. For neural network based algorithms such as NeuralUCB, Neural-Linear and Ninral-LinUCCB we use a ReLU neural network defined as in (2.2) with L 2 and 2000 for the UCI datasets (Statlog, Magic, Covertype). Thus the neural network weights are W1 E R respectively, where k 100, m 2000, and d is the dimension of features in the corresponding task. Since the problem size of the MNIST dataset is larger, inspired
312
313
314
315 W2 E Rx and 0
317 by Hinton and Salakhutdinov [26], we use a deeper NN and set = 3. A 100 and m = 100, with weights W, E IRmxx W2 E mm W, E R4xm and 0 E IR* We set the time horizon T = 15, 000, which is the total number of rounds for each algorithm on each dataset. We use gradient decent to optimize the network weights, with step size my =le-5 and maximum iteration number n = 1, .00. To speed up the training process, the network parameter w is updated every H 100 rounds starting from round 2000. We also apply early stopping when the loss difference of two consecutive iterations is smaller than a threshold of 1e-6. We set X = and a₂ = 0.02 for all algorithms, t E [T]. Following the setting in Riquelme et al. [38], we use round-robin to independently select each arm for 3 times at the beginming of each algorithm. For NeuralUCB, since it is computationally unaffordable to perform the original UCB exploration as displayed in Zhou et al.
319
321
322
323
325
326
[52]. we follow their experimental setting to replace the matrix Z, E {(4+))x(d+)) in Zhou et al. [52] with its diagonal matrix.
328
329
we plot the cumulative regret of all algorithms versus round in Figures (a)), 1(b) and 1(c) for UCI datasets and in Figure 1(d) for MNIST. The results are reported based on the average of 10 repetitions over different random shuffles of the datasets. It can be seen that algorithms based on neural network representations (NeuralUCB, Neural-Linear and Neural-LinUCB) consistently outperform the linear contextual bandit method LinUCB, which shows that linear models may lack representation power and find biased estimates for the underlying reward generating function. Furthermore, our proposed Neural- Neural-LinUCB achieves comparable regret with NeuralUCB in all experiments despite the fact that our algorithm only explores in the output layer of the neural network, which is more computationally efficient we will show in the sequel. results in our experiment are well aligned with our theory that deep representation and shallow exploration are sufficient to guarantee good performance of neural contextual bandit algorithms, which is also consistent with the findings in existing literature [38] that decoupling the representation learning and uncertainty estimation improves the performance.
Results:
330
332
334
336
338
340
341
342
We also conducted experiments to study the effects of different widths of deep neural networks on the regret performance and to show the computational efficiency of Neural-L.in compared with existing neural bandit algorithms. Due to the space limit, we defer the results to Appendix A.
3M
6 Conclusions
348
In this paper, we propose a new neural contextual bandit algorithm called Neural-LinUCB, which uses the hidden layers of ReLU neural network as deep representation of the raw feature vectors and performs UCB type exploration on the last layer of the neural network. By incorporating techniques liner contextual bandits and neural tangent kernels, we prove that the proposed algorithm achieves a sublinear regret when the width of the network is sufficiently large. This is the first regret analysis of neural contextual bandit algorithms with deep representation and shallow exploration, which have been observed in practice to work well on many benchmark bandit problems [38]. We also conducted experiments on real-world datasets to demonstrate the advantage of the proposed algorithm over
347
348
349
350
351
353
LinUCB and existing neural contextual bandit algorithms.
9

---

References
355
356
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312- 2011.
358
[2] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference Machine Learning, pages 1638-1646, 2014.
360
362
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparame- terized neural networks, going beyond two layers. In Advances in neural information processing systems, pages 6155-6166, 2019.
364
365
[4] Zeyuan Aluen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via prerpparameteriaatoon. In International Conference on Machine Learning, pages 2422 2019.
366
367
388
[5] Robin Allesiardo, Raphaël Féraud, and Djallel Bouneffouf. A neural networks committee for the contextual bandit problem. In International Conference on Neural Information Processing, pages 374-381. Springer, 2014.
389
370
371
[6] Sanjeev Arora, Simon Du Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332, 2019.
372
373
[7] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pages 8139 9148, 2019.
375
377
[8] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19): 1876-1902, 2009.
379
380
[9] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235 256, 2002.
381
382
[10] Sivaraman Balakrishnan, Martin J Wainwright, Bin Yu, et al. Statistical guarantees for the em algorithm: From population sample-based analysis. The Annals of Statistics, 45(1):77-120, 2017.
383
384
[11] Qi Cai,, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-diiferenee learning converges to global optima. In Advances in Neural Information Processing Systems, 2019.
386
[12] Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint 1902::1922.01844 2019.
388
389
[13] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pages 10835-10845, 2019.
390
392
[14] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pages 2249-2257, 2011.
393
394
[15] Sayak Ray Chowdhury and Aditya Gopalan. On kemelized multi-armed bandits. In International Conference on Machine Learning, pages 844-853, 2017.
385
[16] Wei Chu, Lihong Li. Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-2144 2011.
397
398
399
[17] Mark Collier and Hector Urdiales Llorens. Deep contextual multi-armed bandits. arXiv preprint arXiv:1807.09809 2018.
10

---

401
[18] George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
402
403
[19] Varsha Dani, Thomas P Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. In Conference Learning Theory, 2008
405
[00]
Aniket Anand Deshmukh, Abhimanu Kumar, Levi Boyles, Denis Charles, Eren Manavoglu, and Urun Dogan. Self-supervised contextual bandits in computer vision. arXiv preprint arXiv:2003.08885, 2020.
406
407
408
[21] Simon Du, Jason Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685, 2019.
410
411
[22] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes weeepparameterized neural networks. In International Conference Learning Representations, 2019. URL http://ppneeeeeeee.eeffttoommm www.oorrmmii-SSeeiiee10
413
[23] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URI.http::/arcciie. ics. uci. edu/ml.
415
416
[24] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, pages 586-594, 2010.
418
419
[25]
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
[26] Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):504-007 2006.
421
422
[27] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 2018
424
425
[28]
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 2066- 2076, 2020.
426
427
[29] John Langford and Tong Zhang. The epoch-greedt algorithm for multi-armed bandits with side information. In Advances in neural information processing systems, pages 817-824, 2008.
429
430
[30]
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[31]
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
432
439
[32]
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):433 444, 2015.
435
[33] Jachoon Lee, Lechao Xiao. Samuel Schoenholz, Yasaman Bahri, Roman Novak. Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances neural information processing systems, pages 8570-8581, 2019.
438
437
438
[34] 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, pages 661-670, 2010.
440
442
[35] Lihong Li, Yu Lu, and Dengyong Zhou Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pages 207 2017.
443
[36] Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimization attains globally optimal policy. In Advances Neural Information Processing Systems, pages 10575, 2019.
445
11

---

447
[37] Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization:: global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
448
450
[38] Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In International Conference on Learning Representations, 2018. URL httph:t/////// /tppa/////////ee/////// wwt.wwwwwwwe//oumm id-SyYe6k-CH.
451
452
453
454
[39] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395-411, 2010.
455
456
[40] Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Foundations and Trends(R) in Machine Learning, 11(1):1-96, 2018. ISSN 1935-8237.
457
458
459
[41] Jyotirmoy Sarkar. One-armed bandit problems with covariates. The Annals of Statistics, pages 1908-2002, 1991.
460
461
[42] Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian optimization using deep neural networks. In International conference on machine learning, pages 2171-2180, 2015.
483
[43] William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4) 294, 1933.
465
[44] Michal Valko, Nathan Korda, Rémi Munos, Ilass Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, pages 654 654-663, 2013.
467
488
469
[45] Lingxiao Wang. Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient meth- ods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2020. URL https: / /opp://v/eeeeeeeeeeeeee wwwpeerrviee.ee//forrueeee
471
[46] Zhaoran Wang, Han Liu, and Tong Zhang. Optimal computational and statistical rates of convergence for sparse nonconvex learning problems. Annals of statistics, 42(6):2164, 2014.
473
[47] Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function approximation. In International Conference on Machine Learning, 2020.
475
476
[48] Pan Xu, Jian Ma, and Quanquan Gu. Speeding up latent variable gaussian graphical model estimation via nonconvex optimization. In Advances in Neural Information Processing Systems, pages 1933-1944, 2017.
477
479
[49] Tom Zahavy and Shie Mannor. Deep neural linear bandits: Overcoming catastrophic forgetting through likelihood matching. arXiv preprint arXiv:1901.08612 2019.
481
[50] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017. URL. /tttpss://ppervviiii wwt.://ee///ooeeeeeeeeeeeeeeeeee mett/forumiid-S// Syy=SygdBXxxx
482
483
[51] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arXiv:2010.00827, 2020.
485
486
[52] Dongrue Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, 2020.
487
488
[53] Difan Zou and Quanquan Gu. An improved analysis of training parammetteeee deep neural networks. In Advances in Neural Information Processing Systems, pages 2053-2062, 2019.
489
480
[54] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.08888 2018.
491
12

---

Checklist
492
483
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes]
495
486
(b) Did you describe the limitations of your work? [Yes] We discussed the limitation of the assumptions made in this paper. We also admit in the experiment that the theory maybe conservative since our experiment does not require a very wide neural network achieve good performance.
497
498
499
500
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work focuses on a general methodology in bandit problems and its theoretical analysis. It does not cause any negative social impact.
502
503
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
504
2. If you are including theoretical results...
506
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the assumptions listed in Section
507
508
(b) Did you include complete proofs of all theoretical results? [Yes] Proofs are provided in the appendix.
510
3. If you ran experiments..
511
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as a URL)? [Yes] We provide them in the supplementary material.
512
513
514
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We specify all the details in the Implementations paragraph of Section 5.
515
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] All the figures are plotted with the standard error with respect to random repetitions.
518
520
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We stated the type of workstation at the end of the first paragraph of Section
521
522
523
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
524
(a) If your work uses existing assets, did you cite the creators? [Yes] As we mentioned in Section 5, we used codes from bascline algorithms and public available datasets. All the assets were properly cited.
525
527
(b) Did you mention the license of the assets? [N/A] All the codes and datasets are open-source.
528
529
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We include our code in the supplementary for reproduction.
530
531
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
533
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] The data does not contain any personally identifiable information or offensive content.
534
535
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
538
539
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
541
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
542
13


Reviews:
[{"review_id": "kndjOpHMxQa", "reviewer": "Reviewer_1Vq8", "summary": "This paper proposes a novel contextual bandit algorithm, Neural-LinUCB, that transforms the raw feature vector using the last hidden layer of a deep ReLU neural network (deep representation learning), and uses an upper confidence bound (UCB) approach to explore in the last linear layer (shallow exploration). The algorithm is shown to enjoy the best of two worlds: strong expressiveness due to the deep representation and computational efficiency due to the shallow exploration. In theory, a $\\sqrt{T}$ regret bound is established. Numerical experiments further demonstrated the importance of decoupling representation learning and uncertainty estimation.", "questions": "", "limitations": "", "rating": 7, "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": "Overall, this paper is very well written and is easy to follow. The contribution over NeuralUCB (Zhou et al. 2020) is clear and convincing. Below are some questions for further clarification.\n\n1. The algorithm relies on the exploration parameter $\\alpha_t$, which is set to be an increasing function of $t$ and an unknown constant $M$ in Theorem 4.4. However, in the experiment, $\\alpha_t = 0.02$ for all $t$. Can authors provide any justification or explanations on this inconsistency. \n\n2. As shown in Corollary 4.6, the final rate is $\\sqrt{T}$ only when $\\sqrt{(r-\\tilde{r})^{\\top} H^{-1} (r-\\tilde{r})}$ is bounded. Note that $r \\in R^{TK}$ and $H\\in R^{TK \\times TK}$. The authors justified this by claiming that Zhou et al. (2020) assumed that this can be upper bounded by a constant. Personally, I would like to see more justifications on this statement as the $\\sqrt{T}$ regret bound was claimed in the abstract and introduction. \n\n3. Suggestion: one advantage of the proposed Neural-LinUCB over NeuralUCB (Zhou et al. 2020) is the computational efficiency. I would suggest the authors to move some runtime comparisons in Section A.1 of the supplement to the main paper. \n\n4. Typo: line 313, \"$L=2$ and $2000$\" should be \"$L=2$ and $m=2000$\".\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "cTJhcF5pNAP", "reviewer": "Reviewer_7ZGH", "summary": "The paper studies a contextual bandit problem for which the authors propose a neural network-based policy that takes a raw feature vector as an input without knowledge of the specific reward generating function. The proposed policy transforms the raw feature vector using the last hidden layer of a deep ReLU neural network and uses the upper confidence bound (UCB) approach to explore in the last linear layer which the authors call \"shallow exploration\" instead of using the entire network to explore. The paper provides regret analysis which shows O(\\sqrt{T}) regret. The proposed method enjoys computational advantages over existing neural contextual bandit policies.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 authors argue that the proposed decoupling of the representation and the exploration will achieve the best of both worlds: efficient exploration in shallow (linear) models and the high expressive power of deep models. However,  the high-level idea of decoupling the representation and exploration has already been proposed in previous literature [38] although those works focused on a Thompson sampling-based algorithm. Hence, I am not convinced that credit should be given to this paper for the decoupling idea. I believe the paper should be evaluated on theoretical merit and wish that the authors are more explicitly clear about what is technically challenging and what technical innovations they are providing to the community compared to the existing techniques in [51,52].\n\nIn Line 262, the authors state that the width of the neural network satisfies m = poly(L, d, 1/δ, H, log(T K/δ)). Is it the same order of m as shown in the previous works [51,52] which is too large (hence very restrictive) for any practical settings? I wish the authors are more clear about this. I feel that what the authors are appealing for is a more practical version of neural contextual bandits with \"shallow exploration\" But, not stating what is crucial information for their result to hold, which does hinder practicality, is clearly not helping the readers.\n\nWhile the numerical results show that the performance of the proposed method is slightly better than the existing methods. The plots are not showing any sublinear regret in Figure 1 which is a bit disappointing despite the claim of achieving the best of both worlds.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Ex-kTilNzHX", "reviewer": "Reviewer_LYF3", "summary": "The paper studies the contextual bandit without knowing the specific reward generating function. The authors propose to use a deep neural network to model the reward function where the hidden layers of the deep neural network are used to represent the features and the exploration is only performed in the last layer of the\nneural network. In this way, the reward generating function can be expressed as the inner product between a deeply represented feature vector and an exploration weight parameter. As the author explained, the main advantage of this reward model is to efficiently reduce computation because we only need to explore the last layer of the deep neural network instead of exploring the whole network like existing neural bandit algorithms. \nThe authors show that the proposed algorithm for this problem obtains a near-optimal regret which matches the regret bound of linear contextual bandits. They also provided experiments based on real-world datasets to show the performance and computational efficiency.\n", "questions": "", "limitations": "", "rating": 6, "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 a deep representation and an exploration at the last layer of a neural network has been exploited in the literature. I think that their main contribution consists of a novel algorithm using the UCB approach and their theoretical results. The paper sounds technically correct. \nOverall, the paper is very well written and easy to follow. It would be better if the authors can clearly explain the notation of “exploration” used in the last layer. I understand that this notation is different from that of the exploitation-exploration tradeoff in the contextual bandit. \nI have several questions as follows:\nTo guarantee the near-optimal regret, the neural network must be over-parameterized. As Corollary 4.6 showed, m > T^3 is needed. If T =1000, then m > 10^9. Such a network is so large to implement and train. How did you solve this issue in your experiments and what is a potential solution? \nIn the experimental results in Figure 1, I see that Neural-LinUCB always outperforms NeuralUCB on all the datasets. Why? Is it because of the computational issue of the inverse matrix Z^{-1} of NeuralUCB?\nIn contextual bandit, Thompson Sampling algorithms often outperform UCB-based algorithms. See paper “Neural Thompson Sampling”. Why does your UCB-based algorithm always outperform Neural-Linear, a Thompson-Sampling-based algorithm?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "2wMoVw8RNd3", "reviewer": "Reviewer_M9Rm", "summary": "Authors provide a new regret bound for a recent approach to solving contextual bandits. Previous approaches have introduced deep neural networks to learn context, leading to a paradigm where one must explore over the entire network parameter space, which is inefficient for learning. The authors address this by taking an existing approach that decouples the deep neural network feature representation learning from most of the exploration of the network parameters by only exploring over the final layer of the network. Although this has been done previously in the context of Thompson sampling, there has not been a regret bound given. The authors analyze a UCB version of this approach, then build from techniques from both deep neural contextual bandits and linear contextual bandits to prove an O(\\sqrt(T)) regret bound. Finally, they show experimentally that their algorithm is better than neural-only or linear-only contextual bandits.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "\nStrengths:\n- Authors combine known techniques to create an interesting algorithm for contextual bandits. Although the combination is not novel, the authors make a theoretical contribution by demonstrating that the combination has O(\\sqrt(T)) regret.\n- The paper is well written, limitations clearly addressed, and assumptions made clear.\n- Authors give results from 3 tabular and 1 image domain, providing a decent test bed for their algorithm against competitors under different neural network depths. Their algorithm always outperforms the competitors.\n\n\nWeaknesses:\n- The way the paper is written somewhat undersells the novelty of the authors' contribution. Right now, their contribution is framed such that their algorithm is a subset of the Neural-linear idea from Riquelme et al., and the purpose of the whole paper is mainly to provide this regret bound for one version of a neural-linear contextual bandit. This left me wanting more -- e.g., are there new conceptual ideas here, were there specific challenges to achieving the proof that could be part of the authors' contribution, does the proof provide some more general implication about the way contextual or other bandits can be learned? Similarly the experimental results showed very little separation between the competitor NeuralUCB and the authors' Neural-LinUCB -- one thing that would have been interesting to see would be an analysis of whether more separation could be achieved between the two, as the size of the networks increase -- that would be an interesting way to experimentally verify the differences between the O(d\\sqrt(T)) regret bound of NeuralUCB and the O(\\sqrt(T)) regret bound of the authors' method.\n---------------------------------------------\nUpdate: I have read the other reviews and the author responses. First, I think the authors adequately addressed my concern (also mentioned by reviewer 7ZGH) that the technical challenges over previous literature needed to reach their results were unclear. Authors should make this clear in their final version. Second, authors make a reasonable argument about why running experiments with larger architectures (where they would see more separation against the competitor) were not carried out. However, some version of this experiment really should be included in the final paper. Authors should at least run a small version of this scaling experiment against the competitor (e.g., network widths of 2000, 3000, 4000...) and include it in the main text (they could be added to Figure 1 relatively easily.) I have increased my score by 1 to reflect the authors addressing my main concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work presents a neural contextual bandit algorithm with computational improvements over prior work.  The work is very interesting, however reviewers, throughout both the feedback phase but also the extensive internal discussion, ended up very split; some find the overall approach very exciting and sound, others are concerned about the concrete improvement over prior work, which is powered by additional assumptions and thus a bit hard to measure.  Independent of the final decision, this is a valuable paper and I urge the authors in either their revisions or in re-submission to work to solidify the improvement over prior work, for instance achieving computational benefits without the extra assumptions, or relaxing the assumptions and/or making the analysis with them and the discussion and justification of the assumptions more compelling.
Decision: Reject