NeuralUCB: Contextual Bandits with Neural Network-Based Exploration
Authors: Dongruo Zhou
Lihong Li
Quanquan Gu
Venue:  (2020)
Keywords: contextual bandits
neural network
upper confidence bound

Abstract: We study the stochastic contextual bandit problem, where the reward is generated from an unknown bounded function with additive noise. We propose the NeuralUCB algorithm, which leverages the representation power of deep neural networks and uses the neural network-based random feature mapping to construct an upper confidence bound (UCB) of reward for efficient exploration. We prove that, under mild assumptions, NeuralUCB achieves $\tilde O(\sqrt{T})$ regret bound, where $T$ is the number of rounds. To the best of our knowledge, our algorithm is the first neural network-based contextual bandit algorithm with near-optimal regret guarantee.  Preliminary experiment results on synthetic data corroborate our theory, and shed light on potential applications of our algorithm to real-world problems.

Under review as a conference paper at ICLR 2020
NEURAL CONTEXTUAL BANDITS WITH UPPER CONFIDENCE BOUND-BASED EXPLORATION
Anonymous authors Paper under double-blind review
ABSTRACT
We study the stochastic contextual bandit problem, where the reward is gener- ated from unknown bounded function with additive noise. We propose the NeuralUCB algorithm, which leverages the representation power of deep neural networks and uses neural network-based random feature mapping construct an upper confidence bound (UCB) of reward for efficient exploration. We prove that, under mild assumptions, NeU achieves ((VT) regret, where T is the number of rounds. To the best of our knowledge, our algorithm is the first neu- ral network-basse contextual bandit algorithm with near-optimal regret guarantee. Preliminary experiment results on synthetic data corroborate our theory, and shed light potential applications of our algorithm to real-world problems.
INTRODUCTION
The stochastic contextual bandit problem has been extensively studied machine learning (Bubeck and Cesa-Bianchi) 2012 Lattimore and Szepesvári 2019] at round E (1, T), agent is presented with a set of K actions, each of which is associated with a d-dimensional feature vector. After choosing an action, the agent will receive stochastic reward generated from some unknown distribution conditioned on the chosen action's 's feature vector. The goal of the agent is to maximize the expected cumulative rewards over T rounds. Contextual bandit algorithms have been applied to many real-world applications, such as personalized recommendation, advertising and Web search (e.g.. Agarwal et al. 2009 Li al., 2010).
The most studied model in the literature is linear contextual bandits (Auer 2002 Abe et al. 2003
Dani et 2008 Rusmevichientong and Tsitsiklis 2010 Chu et al. 2011 Yadkori et al, 2011]. which assumes that the expected reward at each round is a linear function of the feature vector. Linear bandit algorithms have achieved great success in both theory and practice, such as news article recommendation (Li et al. 2010). However, the linear-reward assumption often fails to hold exactly in practice, which motivates the study of nonlinear contextual bandits (e.g., Filippi let al. 2010 (Srinivas al.) [2010) Bubeck et al.] [011] Valko et al.] 2013). However, they still require fairly strong assumptions on the reward function. For instance. Filippi et al. (2010) makes generalized linear model assumption the reward, [Bbbeck et al.]
2011 require it to have Lipschitz continuous property in proper metric space, and Valko et al. (2013) assume the reward
function belongs to some Reproducing Kernel Hilbert Space (RKHS).
In order to overcome the above shortcomings, deep neural networks (DNNs) (Goodfellow et al., 2016) have been introduced to learn the underlying reward function in contextual bandit problem, thanks to their strong representation power. Given the fact that DNNs enable the agent to make use of nonlinear models with less domain knowledge, existing work (Riquelme et al. 2018 Zahavy and Mannor 2019) focuses on the idea called neural-linedd bandit. More precisely, they use the first layers of DNN as a feature map, which transforms contexts from the raw input space to a low-dimensional space, usually with better representation and less frequent update. Then they learn a linear exploration policy on top of the last hidden layer of the DNN with a more frequent update. These attempts have achieved great empirical success. However, none of these work provides theoretical guarantee on the regret the algorithms.
In this paper, we take the first step towards provable efficient contextual bandit algorithms based on deep neural networks. Specifically, we propose a new algorithm, NeuralUCB, which uses a deep neural network to learn the underlying reward function. At the core of the algorithm is upper

---

Under review as a conference paper at ICLR 2020
confidence bound constructed by deep neural network- random feature mappings. Our regret analysis of CC is built on recent results on optimization and generalization of deep neural networks (Jacot et al., 2018 Arora et al., 2019 Cao and Gu 2019a). While the main focus of our paper is mostly theoretical, we also carry out proof-of-concept experiments on synthetic data to validate the effectiveness of our proposed algorithm.
Our contributions are summarized as follows:
We prove that, under mild assumptions, our algorithm is able to achieve a Ö(dVT) regret, where d is the effective dimension of a neural tangent kernel matrix and T is the number of rounds. Our regret bound recovers the O(dvT) T) regret for linear contextual bandit as special case (Abbasi- Yadkori et al. 2011), where d is the dimension of context.
We propose neural contextual bandit algorithm using neural network-based exploration. It can be regarded as an extension of existing linear bandit algorithms (Li et al., 2010 Abbasi-Yadkon et al. 201T. from linear reward functions any bounded reward functions.
We provide empirical evidence in several proof-of-concept experiments to demonstrate potential applications of our algorithm to real-world problems.
Notation: Scalars are denoted by lower case letters, vectors by lower case bold face letters, and For
matrices by upper case bold face letters. For positive integer k. [R:] denotes {1,...,Ai) k)).
vector 0 E R4, we denote its & norm by ||0|| Vi 0z and its j-th coordinate by [0],- For a matrix A [ddxd, we denote its spectral norm, Frobenius norm, and (ith)-th entry by ||A|| 2. | F, and [A]k. respectively. We denote sequence of vectors by {0z}}=ı and similarly for matrices. For two sequences {a,} and }b, we use an (b,,) to denote that there exists some constant C > 0 such that an S Cb,,, an (bbb,)) to denote that there exists some constant C² > 0 such that a, 2 C'b,, In addition, we use (()) to hide logarithmic factors. We say a random variable X is Dusub-Gaussiat if E exp(X(XX EX))= I exp(X²>² /2) for any X > 0.
2 RELATED WORK
2.1
CONTEXTUAL. BANDITS
There is a line of extensive work on linear bandits (c.g., Auer 2002 Abe ct al. 2003; Dani et al, 2008
Rusmevichientong and Tsitsiklis 2010 Li et al. 2010 Chu et al. 20 1 Abbasi- Yadkori et al, For the setting with finitely many arms, Abe et al. (2003 formalized the linear bandit setting and analyzed some of the earliest algorithms. Auer (2002) proposed SupLinRel algorithm that achieves Õv dT regret. Chu et al. (2011) obtained the same regret with SupLinUCB that is based on LinUCB (Li et al. 2010); the authors also provided lower bound of O v dT') For the other setting with infinitely many arms, a few authors (Dani al., 2008 Rusmevichientong and Tsitsiklis 2010
2011
Abbasi- Yadkori et al. 201 proposed algorithms that achieve Odv'T) regret, whereas an (dVTT)
lower bound is given by Dani al. (2008).
While most algorithms above are based on the idea of upper confidence bounding, it is also possible to use proper randomization to achieve strong regret guarantees, such as Thompson sampling and reward perturbation Thompson! 1933 Chapelle and Li 2011 Agrawal and Goyal 2013 Russo and Van Roy| 2014 2016 K et al. 2019))
To deal with nonlinearity, generalized linear bandit has been considered, which assumes that the reward function can be written a composition of linear function and link function. In particular, Filippi et al. (2010) proposed a GLM-UCB algorithm, which attains Ö(dVT) regret. Li et al. (017)) proposed SupCB-GI G-M for generalized contextual bandit problems and showed a O(V regret that matches the lower bound. Jun et al. (001)) studied how scale up algorithms for GLM bandits.
A few authors have also explored more general nonlinear bandits without making strong modeling assumptions. One line of work is variants of expert learning algorithms (Auer et al. 2002). which typically have a time complexity linear in the number of experts (which in many cases can be expo- nential in the number of parameters). Another approach is reduce bandit problem supervised
2

---

Under review as a conference paper at ICLR 2020
learning, such as the epoch-greedy algorithm (Langford and Zhang 2008 that has (
gret. Later, Agarwal et al. (2014) develop an algorithm that yields near optimall regret bound, but relies on an optimization oracle that can be expensive. A third approach uses nonparametric mod- eling, such as Gaussian processes and kernels (Srinivas et al. 2010 Krause and Ong 2011 Valko et al. 2013). More specifically, (Srinivas et al. (010)) assumed that the reward function is generated from Gaussian process with known mean and covariance functions. They proposed a GP-UCB
algorithm which achieves (T) regret, where "T is the maximum information gain. Krause and Ong (201T) assumed the reward function is defined over the context-arm joint space and pro- posed Contextual GP-UCB, Valko et al. (2013) assumed that the reward function lies in a RKHS
with bounded RKHS norm. They proposed a SupKernelUCB algorithm and showed an Ö dT) regret, where d is effective dimension of the kernel that can be seen generalized notion of the dimension of contexts. There is also work focusing on bandit problems in general metric space with Lipschitz continuous property the context (Kleinberg al. 2008 Bubeck al. 2011)
2.2 NEURAL NETWORKS
Different lines of research have been done to provide theoretical understandings of DNNs from different aspects. For example, understand how the expressive power of DNNs are related to their architecture, architecuure_Telaarskk (2015) 20T6); [iang and Srikant (2016); Yarotsky (2017) 2018): Hanin (2017) showed that deep neural networks can express more function classes than shallow networks. Lu et al. 2017): |Hanin and Sellke (2017) suggested that the width of neural networks is crucial to improve the expressive power of neural networks.
For the optimization of DNNs, series of work have been proposed to show that (stochastic) gradient descent can find the global minima of training loss (Li and Liang [0018: Du et al.] [019b] Allen-
Zhu et al. 2019 Du al., 2019a. Zou al. 2019) Zou and Gul (019). For the generalization of DNNs, a series of work (Daniely 2017; Cao and Gu [019a b) Arora et al., 2019) shows that by
using (stochastic) gradient descent, the parameters of DNN are located in particular regime and
the generalization bound of DNNs can be characterized by the best function in the corresponding
neural tangent kernel space (Jacot et al. 2018).
3 PROBLEM SETTING
We consider the stochastic K-armed contextual bandit problem, where the total number of rounds T is known. At round & E [T), the agent observes the tth context consisting of K feature vectors: {xt,a E Idd E [K]]. The agent selects an action a and receive reward rt,a,- For simplicity, we denote (x" { as the collection of .1, , Our goal is maximize the following pseudo regret (or regret for short):
T (re,a - re.a))
RT E
(3.1)
where a; is the optimal action round t that maximizes the expected reward, i.e., aj argmax B[reaa).
This work makes the following assumption on reward generation: for any round f, Ft,a, h(x(,a,) + Et.
(3.2)
where / is some unknown function satisfying 0 < hxx) S 1 for any x, and & is u-sub-Gaussian noise conditioned on x1,a1----3 Xt-1,0, Note that the u-sub-Gaussian noise assumption for & is a standard assumption in stochastic bandit literature rc...,(Abbass Yadkori et al.) (011T; in particular, any bounded noise satisfies such an assumption. Our reward function class contains linear functions, generalized linear functions, Gaussian processes, and kernel functions with bounded RKHS norm over a bounded domain.
In order to learn the reward function h in 3.2 networks with depth L 2 2:
we propose to use a fully connected deep neural
f(x:0)= VmWLd WL WW (Wix)))
(3.3)
3

---

Under review as a conference paper at ICLR 2020
where (2) max(2; 0} is the rectified linear unit (ReLU) activation function, W1 Rmxd W, E R 2 i L-1, WL E Rmx1, and 0 = vee[[W]] ,.... vee(WD) W E IP with p m + md + m² (L- 1). Without loss of generality, layer is the same (i.e., m)) for convenience in analysis. We denote the gradient of the neural network function by gxx; 0) Vxf(x; E R..
assume that the width of each hidden
4 THE NEURALUCB ALGORITHM
We present in Algorithm I our algorithm, NeuralUCB. The key idea is to use a deep neural network f(;; 9) predict the reward of context x, and upper confidence bound-based exploration (Auer) 2002). In particular, Algorithm first initializes the network by randomly generating each entry of θ from an appropriate Gaussian distribution. More specifically, for each 1 I 1, we
|
(W
0 W
initialize Wi
where each entry of W is generated independently from ((0,4/m).
For WT, we initialize W. as (w -.wT where each entry of is generated independently from [0,, 2/m). At round I, Algorithm observes the contexts for all actions, {xt.e First, computes the upper confidence bound, U, based on context Xt,o- the current neural network parameter -, and scaling factor 7 It then chooses action with the largest Uz and receives corresponding reward rt.a, the end of round I, Algorithm [updatt updates O, by applying Algorithm 2to to (approximately) minimize T.(0) using gradient descent, and updates 7/-- We choose gradient descent in Algorithm for the simplicity of analysis, although the training method can be replaced by more efficient algorithms like stochastic gradient descent with more involved analysis (Allen-
Zhu et al.) 2019 Zou et al. 2019).
Algorithm NeuralUCB
1: Input: Number of rounds regularization parameter X, exploration parameter v, confidence parameter 8, norm parameter S, step size 17, number of gradient descent steps J, network width
m. network depth L.
2: Initialization: Randomly initialize 0g described in the text
3: Initialize Zo = AI, bo
4: for 1, ...., do
5: Observe {xr,a]
6: for 1,..., K do
7: Compute Ur,a (xx, -1 + 7-- g(xra; 1._1) 1
g(xr,i 0z- 1)/m
8:
Let a; = argmax Uz,a
9:
end for
10:
Play a and observe reward re,0r
11:
Let O₂ = TrainNN((, 11, J. { (x Hi fri, 1 0o)
12:
Compute Z, = Z.-1 + g(xe,a,; (x) 0,) /m
13:
Compute
11m-116 /oo.mom1/m/7//-11111
7
( (w/10o det Zi
+ C2m 1/6 /logm145/33 22ogg + VAS
det Al
+ Css (1- mmdd Vt/A 1m10 1tt.////lom/////// /logmL77240/320-//0 vt/A)
14: end for
Comparison with Existing Algorithms Here, we compare NeuralUCB with other neural network based contextual bandit algorithms. Allesiardo et al. (2014) proposed NeuralBandit which consists of K neural networks. It uses a committee of networks to compute the score each action and chooses the action by e-greedy policy. In contrast, based exploration, which is more effective than e-greedy. In addition, our algorithm only uses one neural network instead of K neural networks, thus be computationally more efficient.
NeuralUCB uses upper confidence bound
4

---

Under review as a conference paper at ICLR 2020
Algorithm TrainNN(A, fj, J. m. (xi,,, N==1 1 (ra, ((0)
1: Input: Regularization parameter X, step size 7,, number of gradient descent steps U, network
width m, contexts (x, Vi=1 rewards {ri,a, 1i=1- initial parameter (())
2: Define L(0) [
ri,a;) )2/2 m2] 11/2
3: for ....... ......---................. 1do
4: @G- =
0(5) 7)V)(
5: end for
6: return (())
Lipton et al. 2018 used Thompson sampling on deep neural networks (through variational infer- ence) in reinforcement learning. A variant is proposed by Azizzadenesheli et al. (2018) that works well on set of Atari benchmarks. [Riquelme et al. (2018) proposed Neurall. which uses the first L, - layers of a T-layer DNN to learn representation, then applies Thompson sampling on the last layer to choose action. Zahavy and Mannor (019) proposed NeuralLinear with limited memory (NeuralLinearLMM), which also uses the first L layers of L-layer DNN to learn rep- resentation and applies Thompson sampling on the last layer. Instead of computing the exact mean and variance in Thompson sampling, NeuralLinearL.M only computes their approximation. Unlike NeuralL Linear and constructs the upper confidence bound based on the random feature mapping defined by the neural network gradient.
NeuralUCI uses the entire DNN to learn the representation and
Variant of NeuralUCB We provide a variant of NeuralUCB called NeuralUCB, Appendix NCuralUCBp can be regarded as a simplified version of NeuralUCB where the neural network pa- rameter vector 0, is not updated each round. In this sense, NeuralUCBg can be seen as Ker-
nelUCB Valko et al. 2013) specialized to the Neural Tangent Kernel (Jacot et al. 2018), Lin-
UCB (Li al. 2010) with Neural Tangent Random Features (Cao and Gul 2019a). We will include both NeuralUCB and NeuralUCBg in the experiments.
Efficient Implementation Algorithm I can be implemented efficiently using iterative first-order algorithms, as in linear bandit literature (Li al., 2010 Valko et al.] [013] Agarwal al. 2014). More details are given here for the sake of completeness. At round t, we define de. =
Z, ai 0²). Based on dr we update det(Z;) by matrix determinant lemma (Golub and
Van Loan 1996):
det (Z.) = det Z + g(X,,a, Og ( 0,)T/m/
+ g(xt,a, 0.) O,)TZ (x,,., 0.)/ml del(Ze
(4.1)
Note that 4.1) only requires compute vector inner product between g(Xt,o,; 0t) and dr, which only requires O(p) time. Now we show how to compute de,a efficiently. By the definition of de... we have
g(xi,a:0) Z, id,
AI
Σ g(x,,,,; 0x)g(xx,aci 0.) /4/mm//m dr.a-
==0
Thus, de,a is the global minimizer of the following convex optimization problem:
Σ g(x...; : (x)g(x 0.) /m )a g(xi,a; 0₂)
min
AI
deR
i=U
and we can use (stochastic) gradient descent to find d efficiently, whose update formula can be written as follows:
( = -(t) - AI
Σ
g(x, 0,)g(x;,ar 0.)TT/11 /m
1=0
[
Σ
g( (x 0.) (x;;)
( g(xiaa 0.)
which again only requires compute vector inner products.

---

Under review as a conference paper at ICLR 2020
5 REGRET ANALYSIS
Recall that {x is the collection of all (xra)- Since our regret analysis is built upon the recently proposed neural tangent kernel matrix (acoot et al. 2018), we start with its formal definition.
In this section, we present regret analysis for Algorithm |
Definition 5.1 (Jacot et al. 2018
Cao and Gu (2019a). For a set of contexts fx' {X1TTK
TK define
20 (x x²),
0
(1+1) 2E
(u.o) (w))(())
H 1) 2H (u.o)) o' (u) + E (+1))
Then, H = (H(4) + / is called the neural langent kernel (NTK) matrix on the context set.
As shown in Definition 5.1 the Gram matrix of the NTK on the contexts {x' ITK for L-layer neural networks is defined in recursive way from the input layer all the way the output layer of the neural network. For more details about the derivation of Definition 5. please refer to Jacot et al. 20188. Based on Definition 5.1 we first lay out the assumption on the contexts {x']
Ji=1
Assumption 5.2. H ž AgI. Morcover, for any 1 S xis S TK, ||x||| 1 and [x'],
[x /+//2
The first part of the assumption says that the neural tangent kernel matrix is non-singular, a mild assumption commonly made in the related literature (Du et al. 2019a Arora al. 2019) Cao and Gu 2019a). It can be satisfied as long as no two contexts in {x'
T Ji=l
are parallel. The second part is
also mild: for any context x, ||x|| = 1, we can always construct a new context x' = x
to satisfy Assumption 5.2 can verified that if Og is generated by the random initialization
scheme in Algorithm then [(xx;; 0n) = O for any E [TK].
Next define the effective dimension d of the neural tangent kernel matrix on contexts {x (x')
Definition 5.3. The effective dimension of the neural tangent kernel matrix on contexts fx TK defined as
d log det (I + H/A)
(5.1)
log(1 + TK/A)
Remark 5.4. The notion of effective dimension was introduced by Valko et al. (2013) for analyzing kernel contextual bandits, which was defined by the eigenvalues of any kernel matrix restricted on the given contexts. We adapt a similar but different definition of Yang and Wang (2019), which was used for the analysis of keanel-based Q-learning. Suppose the effective dimension of the reproducing kernel Hilbert space induced by the given kernel is d and the feature mapping vb induced by the given kernel satisfies [/ < 1 for any x E Rd. Then, it is easy to verify that we always have d < d; see Appendix A.1 for details. Intuitively, d measures how quickly the eigenvalues of H decay, and it only depends on I' logarithmically in certain specific cases (Valko et al.) 2013).
Now we are ready to present the main result, which provides the regret bound Rr of Algorithm D
Theorem 5.5. Let d be the effective dimension defined in Definition 5.3 Let h [M(**)]
RTK Suppose there are constants C₁, C2 > 0, such that for any 8 E 10,
m poly(TT L, 1-11 Xo 1 log(//))) 7 Ci + m
A 2 max(1, and 2 22h H Th Then, with probability at least over the random initialization of 0o. the regret of Algorithm satisfies
Ri < <3VT
+ P (log(1++TK))))) +TK/A) + 2 log 6
+ + -
VT/A +1.
(5.2)

---

Under review as a conference paper at ICLR 2020
Remark 5.6. is worth noting that, simply applying results for linear bandit to algorithm would lead to a linear dependence of p or v in the regret. Such a bound is vacuous since in our setting would be very large compared with the number of rounds T and the imput context dimension d. In contrast, our regret bound only depends on d, which is much smaller than p.
Remark 5.7. Our regret bound (5.2) has term (1 (/ vT/A, which characterizes the op- timization error of Algorithm ? More specifically, it suffices to set J = (og(AS//TT//((((TI))
L(T) (independent of m)) such that (/-AA((L)) VT/X S VĀS, and therefore the optimiza- tion error is dominated by VÄS.
Remark 5.8. Treating и/ and À as constants, and taking S 22h H and J log(AS// (P((AS/TT)(A/((LL)) the regret bound (5.2) becomes RT = Ō ō(vTT max h
RKHS H. induced by NTK and it can be represented by h(x) = (x((x) ()), where (x) is the feature mapping induced by NTK, for some 3 in H (Valko
Specifically, suppose h belongs
et al. 2013). Then we can show that ||/|| HM
1/ 2 v H Ha'H-hh see Appendix A.2 for more
details. Thus our regret bound can be further written as Ri Ō( VV max(d, [|]]
The high-probability result in Theorem 5.3 can be used to obtain a bound on the expected regret. Corollary 5.9. Under the same conditions in Theorem 5.5 have
Ej s 3 dlog(1+ + + PV dlog(1 + TK/A) + 2 2 log
+ /T/A +2.
PROOF OF MAIN RESULTS
This section provides the proof of Theorem 5.5 We first point out several technical challenges in this proof:
We do not make parametric assumptions on the reward function as some previous work (Filippi et al. 2010)] Chu et al. [011] Abbasi-Yadkoon al. 201I). Furthermore, unlike the fixed feature mapping used in Valko et al. (2013), NeuralUCB B uses neural network f(x: 0,) and its gradi- ent g(x; 0.) dynamic feature mapping depending on 0,. These differences make the regret analysis of NeuralUCB more difficult.
In practice, the neural network is often overparametrized, which implies m (and thus p) is very large. Thus, need to make sure the regret bound is independent of m.
The two challenges above are addressed by the following technical lemmas. Their proofs are gath- ered in the appendix.
Lemma 6.1. There exists some constant Ö such that for any 8 E (0, if m ČT K L log( L/8) then with probability at least 1 - 8 over the random initialization of 0g there 0- E RR such that
h(x*) = (x" 0p), 0" On), Vmll00 - 0oll2 S T2hTH-1h
(6.1)
for all i [TK].
Lemma 6.1 suggests that with high probability, the reward function restricted on {x*) can be regarded as linear function of g(x:; 0o) parameterized by g'-0.. where 0" lies in ball centered at Oy. Note that here 0" is not ground truth parameter for the reward function. Instead, it is introduced only for the sake of analysis. Equipped with Lemma 6.1 we can utilize existing results on linear bandits (Abbasi- Yadkori et al.] (011]) to show that with high probability, 0- lies in the sequence of confidence sets.
Lemma 6.2. There exist constants {C > 0 such that for any 8 E (0,1), if S (TmLL x 11/2 3",
mA)-1 and m 2 C₂ max over the random initialization of lu. we have |00 10ll2 $ 2 2t/(m2) and |00 0. llz 5 n// /t/mm for all 1 (T).
then with prob-
ability at least
7

---

Under review as a conference paper at ICLR 2020
Lemma 6.3. Denote
argmax h(xxe,)).
There exist constants
{C.) > 0 such that for any 6 (0,1), if Σ Ci mA)-1, m >
C2 max X (log m) x
3/2 (log(TKL) /8)) then with probability least
1 8 over the random initialization of to. we have
h (xt,a;) - (xx..a))
< 27-1 min [| 0c-1)/ 1.21111
+ C3 11m6 1aommm1////o/mmmm
1/6 7/2 m m-116 Vlog m/33 22/33 L3).
gives upper bounds for (x(,a;; / Xt.a.). which helps us to bound the regret Ry. worth noting that "/ has term log det Z, A trivial upper bound of log det Z, would result in dependence on the neural network width m, since the dimension of Z, is The next lemma establishes an upper bound which is independent of m, and only related to effective dimension d. The dependence on d is similar to Lemma of Valko et al. (013)), but the proof is different
Lemma 6.3
md+ mdd+m²(0 ( ( 2) + m.
use different notion of effective dimension.
Lemma 6.4. There exist constants {C > such that for any 8 (0, if S C1 + mA) m 2 C2 max 7,2 1 m) L (log(TK12/0)) }. then with probability at least 1 over the random initialization of Go. we have
T
M-1 min [8(xx,,,; 2
v dlog(1 + TK/A) + Cym-1/6 1
v C3m 1/6 /lo mLTT// --766
( (uV + TK/A) +1 /1
2log vXS)
(1 /T/X+ m -1/6
/ VT/N|
With above lemmas, we begin to prove Theorem 3.5
Proof of Theorem 5.5 The total regret Ry can be bounded as follows:
Rr
(1(x.a))) - 16( (xxxa))
<. 2
- min llg(Xe,0 0011) z, 1 1
[=1
+ Ci (Sm - 1/6 111 + m 1166 /lommT933 -
2
T
2-1 min
||g(xt,aei 0 01-1)
1=1
Ci (Sm 1/6 Vlgmm13366 1//2 1-188 -1/6 Vlogmm - [2
33TV
ālog(1 TK/A)) +2
+2 UV Tlog(1 + TK//A) 2log
+ VT/A +1.
where C1, C2 are constants, the first inequality holds due Lemma 6.3 the second inequality holds Cauchy- Schwarz inequality, the third inequality holds due to Lemma 6.4 and choosing large enough This completes our proof.
8

---

Under review as a conference paper at ICLR 2020
1000
280
Veurs Grreety VeursiiC,
1390
Groady
Veuoiiia
2230
Karsk.
2004
304
10100
2900
4900
6330
1000
2000
400K
2003
6000
1000
2000
4000
5000
1000
(a) (x) 10(x TTa a)²
(b) (x
A
Ax
(c) hx(())
cos(3x T
Figure 1: Comparison LinUCB, Neural c-Greedy and NeuralUCB.
EXPERIMENTS
While the focus of this work is mostly theoretical analysis of regret, we present results in proof- of-concept experiments in simulated problems. We compare it with four representative baselines: (I) LinUCB; (2) Neural e-Greedy, which replaces the UCB based exploration Algorithm [ by e-greedy based exploration; (3) NeuralUCBgj and (4) Neural e-Greedyo which replaces the UCB based exploration NeuralUCB, by e-greedy based exploration. We use the cumulative regret as the performance metric.
In our simulation, we use contextual bandit problems with context dimension d 200, the number of actions K = 4 and the number of rounds 7 10 000. The contextual vectors [x1,1... Xy.K' are randomly chosen from N(0, I) and then normalized to have unit norm, i.e., |x, 1. For the reward function h, we investigate the following nonlinear functions:
h1 10(x a)?;
h2(x)= A ha(x) cos(3x (3xTa)) Ta),
where E Rdddd and each entry of A is randomly generated from N(0, 1). a is randomly chosen from N(0, I) and normalized to have ||a||2 1. For each (-).), the reward round for action is generated by Tr,a = (x(x,,)) ) + &,, where & is independently drawn from N (0, 1).
For LinUCB, grid search for a over {0.01, 0.1, 1, 10J and choose the best a for comparison. For NeuralUCB NeuralUCB,, Neural e-Greedy and Neural e-Greedyo. we choose two-layer neural network fx; 0) W2o
follow Li et al. (2010) implement it with constant radius a. We do
with network width m = 20, where 0 = [vec(Wi)" vec (22) IRP and p md + m. We remark that the bound on the required network width m likely not tight. Therefore, in experiments we choose m to be relatively large (but not as large as the- ory suggests). For % in NeuralUCB, we choose % = 7 in the experiment search over (0.01, 0.1, 1, 10} and choose the best 7 for comparison. For NeuralUCBo, == 1, = 1, 5 0.1, and we do grid search over (0.01, 0.1, 1, 10} for hyper-parameter S to choose the best S for comparison. For Neural e-Greedy and Neural e-Greedyo- we do grid search for e over (0.001, 0.01, 0.1, 0.2} and choose the best e for comparison. For all the algorithms, we repeat the experiment for 10 runs and report the averaged results for comparison. For TrainNN, choose the step size = 0.1. To accelerate the training process, we update the parameter 0, by TrainNN every 50 rounds. We stochastic gradient descent with batch size 50 and set J at 1-th round of NeuralUCB and Neural e-Greedy.
We do a grid choose
We plot the cumulative regret of compared algorithms in Figure I for reward function h (h1, h2 hg). We can see that due to the nonlinearity of reward function ht LinUCB fails to learn the true reward function and hence achieve an almost linear regret, as expected. In contrast, thanks to the neural network representation and efficient exploration, NeuralUCB achieves a sublinear regret which is much lower than that of LinUCB. The performance of Neural c-Greedy is in-between. This suggests that while Neural c-greedy can capture the nonlinearity of the underlying reward function, e-Greedy based exploration is not as effective as UCB based exploration. This confirms the effective- ness of NeuralUCB for contextual bandit problems with any bounded (nonlinear) reward function. Meanwhile, worth noting that NeuralUCB and Neural e-Greedy outperform NeuralUCB, and Neural e-Greedyu, which suggests that using deep neural networks predict the reward function better than using a fixed feature mapping associated with NTK. Another observation is that al- though the network width in the experiment is not as large theory suggests, NeuralUCB still

---

Under review as a conference paper at ICLR 2020
achieves sublinear regret for nonlinear reward functions. We leave it future work to investigate the impact of m on regret.
CONCLUSIONS AND FUTURE WORK
In this work, we proposed a new algorithm NeuralUCB for stochastic contextual bandit problems based neural networks. We show that for arbitrary bounded reward function, algorithm achieves O(dvT) regret bound. Our preliminary experiment results on synthetic data corroborate our theoretical findings. In the future, we are interested in a systematic empirical evaluation of NeuralUCB on real world datasets, and compare with the state-of-the-ar neural network based contextual bandit algorithms (without provable guarantee in regret) (Riquelme et al. 2018 Zahavy and Mannor, 2019). Another interesting direction is provably efficient exploration with neural net- work using other strategies like Thompson sampling.
REFERENCES
ABBASI- YADKOR,, Y., PÁL. D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems.
ABE, N., BIERMANN, A. W. and LONG, P. M. (2003). Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica 37 263-293.
AGARWAL, A., HSU, D., KALE, S., LANGFORD, J., LI, L. and SCHAPIRE, R. E. (2014). Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings the 31st International Conference on Machine Learning (ICML).
AGARWAL, D., CHEN, B.-C., ELANGO, P., MOTGI, N., PARK, S.-T., RAMAKRISHNAN, R., ROY. S. and ZACHARIAH, J. (2009). Online models for content optimization. Advances Neural Information Processing Systems.
AGRAWAL, S. and GOYAL, N. (2013). Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning.
ALLEN-ZHU, Z., LI, Y. and SoNG, Z. (2019). A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning.
ALLESSIARD,, R., FÉRAUD, R. and BOUNEFFOLF, D. (2014). A neural networks committee for the contextual bandit problem. In International Conference Neural Information Processing. Springer.
ARORA, S., DU, S. S., HU, W., LI, Z., SALAKHUTDINOV, R. and WANG, R. (2019). On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems.
AUER. P. (2002). Using confidence bounds for exploitation-exploraa trade-offs. Journal of Machine Learning Research 397-422.
AUER, P., CESA-BIANCHI, N., FREUND, and SCHAPIRE, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM Journal Computing 32 48-77.
AZIZZADENESHELI, K., BRUNSKILL, E. and ANANDKUMAR, A. (2018). Efficient exploration through bayesian deep q networks. In 2018 Information Theory and Applications Workshop (ITA). IEEE.
BUBECK, S. and CESA-BIANCHI N. (2012). Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning 5 1-122.
BUBECK, S., MUNoS, R., STOLTZ, G. and SZEPESVÁRI, C. (2011). X-armed bandits. Journal of Machine Learning Research 12 1655-1695.
CAO. Y. and Gu, Q. (2019a). Generalization bounds stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems.
10

---

Under review as a conference paper at ICLR 2020
CAO, Y. and GU, Q. (2019b). A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint 1rXiv:1902.01384.
CHAPELLE, O. and LI, L. (2011). An empirical evaluation of thompson sampling. In Advances in neural information processing systems.
CHU, W., LI, L., REYZIN, L. and SCHAPIRE, R. (2011). Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics.
DANI, V., HAYES, T. P. and KAKADE, S. M. (2008), Stochastic linear optimization under bandit feedback.
DANIELY, A. (2017). Sgd learns the conjugate kernel class of the network. In Advances in Neural Information Processing Systems.
DU, S., LEE, J., LI, H., WANG, L.. and ZHAI, X. (2019a). Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning.
DU, S. S., ZHAI, X., PoCzOs, B. and SINGH,, A. (2019b). Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations. URL
net
FILIPPI, S., CAPPE, O., GARIVIER, A. and SZEPESVÁRI, C. (2010). Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems.
GOLUB, G. H. and VAN LOAN, C. F. (1996). Matrix Computations (3rd Ed.). Johns Hopkins University Press, Baltimore, MD, USA.
GOODFELLOW, I., BENGIO, Y. and COURVILLE,, A. (2016). Deep Learning. MIT Press. http: 7/www. wwww.deeplearm.nppoooookk
HANIN, (2017). Universal function approximation by deep neural nets with bounded width and ReLU activations. arXiv preprint arXiv:1708.0266
HANIN, B. and SELLKE, M. (2017). Approximating continuous functions by ReLU nets of minimal width. arXiv preprint 17 1/278
JACOT, A., GABRIEL, F. and HONGLER, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. In Advances neural information processing systems.
JUN, K.-S., BHARGAVA, A., NOWAK, R. D. and WILLETT, R. (2017). Scalable generalized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems 30 (NIPS).
KLEINBERG, R., SLIVKINS, A. and UPFAL, E. (2008). Multi-armed bandits in metric spaces. In Proceedings of the fortieth annual ACM symposium on Theory of computing. ACM.
KRAUSE, A. and ONG, C. S. (2011). Contextual gaussian process bandit optimization. In Advances in neural information processing systems.
KVETON, B., SZEPESVÁRI. C., GHAVAMZADEH, M. and BOUTILIER, C. (2019). Perturbed- history exploration in stochastic linear bandits. In Proceedings of the 35th Conference on Uncer- tainty in Artificial Intelligence (UAI).
LANGFORD, J. and ZHANG, T. (2008). The epoch-greedy algorithm for contextual multi-armed bandits. In Advances in Neural Information Processing Systems 20 (NIPS).
LATTIMORE, T. and SZEPESVÁRI, (2019). Bandit Algorithmms Cambridge University Press. In press.
LI, L., CHU, W., LANGFORD. J. and SCHApIRE, R. E. (2010). A contextual-bandi approach to personalized news article recommendation. Proceedings of the 19th international conference World wide web. ACM.
11

---

Under review as a conference paper at ICLR 2020
LI, L.,, LU, Y. and ZHOU, D. (2017). Provably optimal algorithms for generalized linear contextual bandits. In Proceedings of the 34th International Conference on Machine Learning- Volume 70. JMLR. org
LI, Y. and LIANG, (2018). Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems.
LIANG, S. and SRIKANT, R. (2016). Why deep neural networks for function approximation? arXiv preprint orXiv:1610.04161
LIPTON, Z., LI, X., GAO, J., L1, L., AHMED, F. and DENG, L. (2018). BBQ-networks: Efficient exploration in deep reinforcement learning for task-oriented dialogue systems. In Thirty-Second AAAI Conference on Artificial Intelligence.
LU, Z., PU, H., WANG, F., HU, Z. and WANG, L. (2017). The expressive power of neural networks: A view from the width. In Advances in neural information processing systems.
RIQUELME, C.,, TUCKER, and SNOEK, (2018). Deep bayesian bandits showdown. In Inter- national Conference Learning Representations.
RUSMEVICHIENTONG, P. and TSITSIKLIS, J. N. (2010). Linearly parameterized bandits. Mathe- matics of Operations Research 35 395-411.
RUSSO, D. and VAN ROY, B. (2014). Learning to optimize via posterior sampling. Mathematics of Operations Research 39 1221-1243.
RUSSO, D. and VAN ROY, B. (2016). An information-theoreete analysis of thompson sampling- The Journal of Machine Learning Research 17 2442-2471.
SRINIVAS, N., KRAUSE, A., KAKADE, S. and SEEGER, M. (2010). Gaussian process optimization in the bandit setting: no regret and experimental design. In Proceedings of the 27th International Conference International Conference on Machine Learning. Omnipress.
TELGARSKY, M. (2015). Representation benefits of deep feedforward networks. arXiv preprint arXiv:1509.81001.
TELGARSKY, M. (2016). Benefits of depth in neural networks. arXiv preprint 160.v4160..04485.
THOMPSON, W. R. (1933). On the likelihood that unknown probability exceeds another in view of the evidence two samples. Biometrika 25 285-294.
VALKO, M., KORDA, N., MUNOS, R., FLAOUNAS, I. and CRISTIANINT, N. (2013). Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv: /009:66006669
YANG, L. F. and WANG, M. (2019). Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint arXiv: 10389.
YAROTSKY, D. (2017). Error bounds for approximations with deep ReLU networks. Neural Net- works 94 103-114.
YAROTSKY, D. (2018). Optimal approximation of continuous functions by very deep ReLU net- works. arXiv preprint 1802.01000
ZAHAVY, T. and MANNOR, S. (2019). Deep neural linear bandits: Overcoming catastrophic for- getting through likelihood matching. arXiv preprint arXiv:1901.08612
Zou, D., CAO, Y., ZHOU, D. and GU, Q. (2019). Stochastic gradient descent optimizes over- parameterized deep relu networks. Machine Learning
Zou, D. and GU, Q. (2019). An improved analysis training over per-parameterized deep neural networks. In Advances in Neural Information Processing Systems.
12

---

Under review as a conference paper at ICLR 2020
A PROOF OF ADDITIONAL RESULTS IN SECTION 5
A.1 VERIFICATION OF REMARK 5.4
Suppose there exists a mapping &b IR - Rd satisfying |/+( 1l S which maps any context E T2 to the Hilbert space H associated with the Gram matrix H E RTKXTK over contexts
fx 17K
Then H v L where v = [xb(x')...... (((x)))...,(((""")) E ROxTK
Thus, we can bound the
effective dimension as follows
d log det [I + H/A| log det [I+ T
log I L T /All2
log(1 + TK/A) S Sd.
log(1 + TK/A)
log + TK/A)
where the second equality holds due to the fact that det(I AT/A) det + AATAA holds for any matrix A, and the incquality holds since det A - | for any A ddxd Clearly, d < d as long as [I T T /All2 I + TK/A. Indeed,
TK
I+ V /2112 $ + V 1 /1/1
1xx( 11 "
where the first inequality is due to triangle inequality and the fact 2 1, the second inequality holds due to the definition of V and triangle inequality, and the last inequality is by |>x)(x)) S for any
S i < TK.
A.2 VERIFICATION REMARK 5.8
Let K(:)) :) be the NTK kernel, then for any í, E [TK], we have Hi,- = K(x', x)). We first prove that ||ll| ||3 2/ Since h H. we know that
1(x)
Σ o K(x
Σ (c((((x), f=1
(xi( (xx))
for some {x, 1= fa Thus, we have B+ Em= ax1(xx;) Therefore, we have
|1 = Σ a, x,)
f==1
a,ay (x)x))))))))))) ,x(x)))
Σ a.b(x,))
1=1
j=1
(,*,8)
= || 1|:
First, h can be decomposed h æи + hu, where (x)) E (x, is the projection of h to the function space spanned by (K(x, (K(x,')) Y and hy is the orthogonal part. By definition we have (x')) = lx((x') for i E [TK]. thus
which immediately suggests that |/ 11 Next we prove that |hll 2 v
[l(xx)) ), ...., (XXTT)]] IT [ ) 1x TR JT
TK
TK
āxK(x )
C K TK
xX)
Hā.
which implies that ã = H H- 'h Thus, we have
|| 2 ||/|| 11 Vā Ha Vh H- H-TH
13

---

Under review as a conference paper at ICLR 2020
A.3
PROOF OF COROLLARY 5.9
Proof of Corollary 5.9
Notice that Rr S T since 0 < h(x) S 1. Thus, with the fact that with holds, we can bound Rr] as
probability least
8, (
E[RT] S (1 - 6) 3VT V + 2 " d dllo(11 +TK/A) + + log 6
+ 2 2v + C2 - 12(1- VT>
+1 8T.
(A.1)
Taking 8 = 1/T completes the proof.
L
B PROOF OF LEMMAS IN SECTION 6
B. PROOF OF LEMMA 6.1
We start with the following lemma:
Lemma B.1. Let [g(x*; oo).............
g(x TKK
0o)l/ y E (Px(TK), We denote the neural tan-
gent kernel matrix H the same as Definition 5.1
For any 5 E (0,
I log((/
m Ω
then with probability at least 1 over the random initialization of 0g, we have
||G H|| S TKE.
We begin to prove Lemma 6.1
Proof of Lemma 6
By Assumption
5.2 we know that Ag > 0. Then with probability at least 1-5, 6,
we have
G |G
H 1 H/2> 0.
(B.1)
where the second inequality holds due to Lemma B.1 with the choice m, the third and fourth inequality holds due to H > AoI > 0. Thus, suppose the singular value decomposition of G
G PAQ T, P E REXTK A E RTTTTK Q E T we have > and 0
0o +PA Q hmmm satisfies (6.1) To validate that 0 satisfies (6.1). first have
GT Vmv 0n) = QAP PA QQh--k
which suggests that for any (g(x;; 0)), ( 0,) = h(x'). We also have
ml|0" 0,1 h QAA - h (G s 2h 2h where the last inequality holds due to B.I. Thus, our proof finishes.
B.2 PROOF OF LEMMA 6.2
In this section we prove Lemma
6.2
For the simplicity, we denote Z,, b,, T' as follows:
Z. AI +
a 0o) 00)g(xx,.; 0o) m/mm
b, Σ
ri,a; g(xi,a 00) /
det Z. det AI
3: / log
log VĀS.
We need the following lemmas. The first lemma shows that the network parameter at each round 0, can be well approximated by 0, Z, bb.
14

---

Under review as a conference paper at ICLR 2020
Lemma B.2. There exist constants {C 0 such that for any 8 > 0, if n, satisfy that for all t t [T],
2//1/m2X) 1mm-3/21,
L/ 3/2 1///|oog(HH/ (og((KL
2 t/(mm2))= - C2 min ( [log 3/2 ( (logm) )l) --)///}
S C3(mA + tmL))
m / 2 C4 Cav/ogmL 2 + v1/A),
then with probability at least 1 - over the random initialization of o.. for any [T], we have
that ||0, Bull2 I /2 and
00, 0u Z, b,/ Vm222 s (1 mma) /t/(m//) Csm 2/3 Vas////oommmiaiooo log 5/3 vt/A).
Next lemma shows the error bounds for Z, and Z,
Lemma B.3. There exist constants {C:},= such that for any if m satisfies that
Cim L/2L Gim_3/2L 3/2 (lo((TK²//)) 2///(mm)) S C2L "log m| 3/2 Vt [T],
C2L~"log
then with probability least 1 - 5 over the random initialization of Oo. have the following inequalities for any E [T]:
Z, F S C3tT,
12. Z,llF I C4m 1/6 Vog 2
det (Z,) log dct(Z,) log det(AI) deI(AI) I C3m 13mm-1/6 1/6
With above lemmas, prove Lemma 6.2 as follows.
Proof of Lemma 6.2 By Lemma B.2 we know that ||0,- -0lll2 < /2/1/ By Lemma 6.1 with 8, there exists 0r such that for any 515 T,
probability least
h(x,,,,) (g(xt,,, 00)/ Vm, vm(0' Ou)),
vmll0 00l12 S 2h H
where the second inequality holds due to the choice of S. Thus, by Theorem 2 in Abbasi- Yadkori al. 2011), with probability least 26, for any 1 < T, 0* satisfies that
( 0n) Z, b, 2. 5ht-
(B.2)
We now prove that ||0 - -0:1lz. S /// mm. From the triangle inequality.
|10 - -illz, < 0 0g Z, 'b, /ollzmll, + 0, 0u Z, 'b// be/vmllz,
(B.3)
la
We bound J and 1/ separately. For J, we have
1 = (0" 0n 1,. b./
Z. 0 2, /
(0- 0n Z, b.//m)
"0" On Z, b./vm)
+ (0' O 2, bb/
/m) (Z, 2.) 0 2, bb/ /m)
< (0" - 0 2, b./ Vm)
ZZ,00' 0 2, bb, /m)
Zz Z
(0" -0, Z, bb./ '.'b.//oo mm) ".' -bu - 1 Vm)
X
< (1 + Z Z /)?? /m.
(B.4)
15

---

Under review as a conference paper at ICLR 2020
where the first inequality holds due to the fact that x Ax x Bx. |A] 2 Amin (B) for some B and the fact that min
(i) 2 A, the second inequality holds due to (B22) By Lemmal B.3 we have
Z Zu || - Ze Zillr I C1m
1/6 11/6 VlogmL 2
(B.5)
and
det Ze
21 "V log det AI
log 8 + VAS
det Ze / VVoog log det AI
/ 2og + VAS,
(B.6)
where C1 C2 0 two constants. Substituting B3.5 and
B.6
into B.44 have
11 S + 1Z - Z, 12/ m
$ V Cim 1/6 1/6 1og /oogmAA7///27770 /vm
( log det Ze
det AI + 122 /lgmm//mm33m3//3/ 22ogg VAS)
(B.7)
For 12, we have
12 C3tL 0o- Z, b,/ /////lll
cC, (1-mA)) (t/(mA) m233 - VE/A)]
5-/3
(B.8)
where C3, C4
constants, the first inequality holds due to Lemma B33 the second inequality holds due to Lemma [32]] Substituting
[Z,
2
F
& Cyt by
B.7
and
B.8
into B33
have 0 0:|1 01l1z. I 7// /m. Our proof is thus completed.
B.3 PROOF OF LEMMA 6.3
The proof starts with three lemmas that bound the error terms the function value and gradient of neural networks.
Lemma B.4 (Lemmaa 4.1, Cao and Gu 2019a)). There exist constants {C: O such that for any 0, i satisfies that
Cim 3/2 1//2233/ 3/2 (TT, S Cz flog m] m] -3/2
then with probability at least ||0 00l12 S T, |10 0olla and j E [TK] we have
the random initialization of Ob. for all 0, 0 satisfying
f(x'00 f(x': (g(x' 0), Ø 0) O3744/13 m log m.
Lemma B.5 (Theorem 5, Allen-Zhu et al. 2019 ). There exist constants (C.), > 0 such that for
any (0, 1). if satisfies that
C,m-3/2 3/2 L 3/2 (lo (KL)g <T C2L- m)
3/2 m-3//2
then with probability least 1 8 over the random initialization of tg. for all ||0 0nl2 < and j E [TK] we have
g x 0) g(x ;
On)l2 S Ca 1/3 1/33 [g(x] 00)112.
Lemma B.6 (Lemma B.3, Cao and Gu (0019a)) There exist constants {C: > 0 such that for any O, if satisfies that
Cim 3/2 3/2 [log (TKL) /8)33/2 < C2L -3/2,
3/2
then with probability least 1 over the random initialization of 0u, for any | 0ull2 I 7 and j E [TK] we have [[g[x): ()xx) < CaVmT.
16

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 6.3
We follow the regret bound analysis in |Abbasi- Yadkori et al. (2011): Valko
et al. 2013
0el1z. z. S / m//mm/. By Lemma 6.2 for all < < T, we have 10,- - 0ol12 < 2///(mm) and 0 C.. By the choice of
Denote of = argmax [K] h((x).)) and C. = =
m, Lemma B.4 B.5 and B.6 hold. Thus, h(x(,a;) h(()).))) can be bounded as follows:
M(x1,;)) h(xx,a.)
(g(xx,ot 00), 0r 0o) (g( 0o), 0 pn)
S (z 11-1), 0¹ -0) (g(x) 1-))) 0-
0o) 00)
+ 110 O (olla(1gg(xxx)) 02-1) g of 00)112 (lg(xx, ( 0c-1) g(xi,a,; 00)112)
< (g( x 1), 0¹ 0o) - (g(Xt,a, 0 0 0o) + Ci Civh" W Vlog ml 1/6 x-100-111000 1/11//677 7,7/2
1/6
max (x) 11-1), 0 - 0o) - (g (x 0 1)-1), 0" 0o)
OEC--1
Civh H hm 1/6 log mt 1/6 -- 2/6 1,/22
(B.9)
where the first inequality holds due to triangle inequality, the second inequality holds due to Lemma
6.1
Lemma B.5 and B.6. the third inequality holds due 0" E C2-1. Denote
Una (g( 01-1), 0:-1 -0o) + + g(xr,a 0c- 18x 0z-1)/m,
then have Un.. maxpcc.-, ( : 1._1), 0o) with the fact that
(a, + cc A-
max (a, x). bllage
We also have
UUr, - Ural S O2m 11/6 Vlog 2
(B.10)
where C2 > is a constant, the inequality holds due to Lemma B.4 with the fact ||0,-1 Oolla S 2/11(m/)) and the fact [(x;; 0p) = 0. Since 0 E C.-1, then B.9 can be bounded as
max (g( (x 02 ), 0 On) (g(xt,,, 0.-1), 0" 0o)
BEC.-1
-Úa,; (g( 1(-1), )) 0" 0n)
Ut,a; (g(Xt, O.- 1), 0- 0o) + C2m - 1/6 Voooooog ml - -2/3
S Uta. (g(X),,, 1)-1), 0" 0,) + C2m -a/---16-- 1/6
Vlog /logmt233 2/3
-2/3
Ü t,a0 (g(Xi, 1), 0" 0o) + 21/6-116 2/3 -2/3 L3
(B.11)
where the first inequality holds due B. the second inequality holds since a; argmax, U.a. the third inequality holds due to (B.10) Furthermore,
Ü.., (g( 0o), 0" 0
0,) 1-11), 0o) (g(x 0--1), 0r -0o)
max (g(Xt,
DEC.-1
(g(Xt,a,i 2 1) 0 )-11 (g(x),., 1.-1). 0¹ 0.-1)
BEC--1
|| - 0,-1 2 |g(x P |, 0 - - 01-1llz,,, [|g(x(, 02-1))
max
BEC
27 [gg(x(, Or 2
(B.
17

---

Under review as a conference paper at ICLR 2020
where the first inequality holds due to Cauchy-Schwar inequality, the second inequality holds due to Lemma 6.2 Combining (B.9). (B.11) and (B.12) we have
h (x)r,a;) )
h(x,,a)))
< 2
||g ( 02 1/-1)/ m n Civh H H-1hm 1/6 Vlog ml! / m 1 11/6,,,722 1,72
+ 1/6 /lgmm22 2/3 2
$ min
0/-1)/ / Z + +CihhTH-H 1/6 Vlog ml llg 1 1,,6,,222 0r
+ 202m 1/6 Vlogml 2/3 x- 2/// 1
S min
22 P7:-1118(x1,m) Or
CGvhTH-1hm Vlog ml 1 -1/6 1/61,11
2
+ 2220mm 1/6 Vlog 2/3 2//3
< 2- min+ |lg(Xe,r; O2 11/ 2,
+ H- -1 1/6 Vlog x-/6 7
2C2mm /lgmm// 2/3
(B.13)
where the second inequality holds due to the fact that 0 h(xx,a;) h(xx,ae) the third inequality holds due the fact that minfa + b, 1 S min(a, 13 + b. the fourth inequality holds due the fact - VĀS Finally, by the fact that /2hH-1h S, we finish the proof.
B.4 PROOF OF LEMMA 6.4
In this section we prove Lemma 6.4 we need the following lemma from Abbasi- Yadkori et al. (011I). Lemma B.7 (Lemma 11, Abbasi- Yadkon et al. (01T)). We have the following inequality:
Σ
T
min [g((x :0-1)/ m 2 1 s 2og det AI
det Zr
Proof of Lemma 6.4 First by the definition of 7h. we know that Yt monotonic function w.r.t. det Z, By the definition of Z. we know that Zr 2 Z, which implies that det Z. S det Zy. Thus, Yt S .r. Second, by Lemma B.7 we know that
min [lg(xe,. ( 1 z }
< 2 2log del ZT
det
det Zr
$ 22oog det + C.m 1/6 /T..m...7///3
(B.14)
where the second inequality holds due to Lemma B.3
Next we are going to bound log det Zr. Denote G [g(x!: ( fm. .m....,, g((TT KK 0n) vml E (TK), then we have
log det Zr det AI
T
log det
-
Σ
g(x,,.. (0)g(x 00) (ma))
1=1
TK
log det
Σ
g(x': 0 ((x: /
i=1
log det
GGT//
log det
I GT/A
(B.15)
18

---

Under review as a conference paper at ICLR 2020
where the inequality holds naively, the third equality holds since for any matrix A RP*TK have det(I+ + AA = det(I+ AT A). We can can further bound (B.15) by the follows:
log det
G+/TG/A) log det
I I+
log det
H// +
S log det
I+ H/A
+ +|(++ p/A
S log del
I H/A
+ +VT G
log
I+ H/1
+1
s ddoo(1 + TK/A) + +1,
(B.16)
where the first inequality holds due to the concavity of log det()), the second inequality holds due to the fact that (A, B) < || | [B]]F, the third inequality holds due to the facts that I H// > I. and ||A|| I VTK A| for any A RTT the fourth inequality holds by Lemma B.1 with the choice of m, the fifth inequality holds by the definition of effective dimension in Definition and the last inequality holds due to the choice of X. We now bound yr, which is
7T v + Cim-116 /lggm
(uv log del AI + +22m / -20---22lg2
det Zr
2log 8 + Vās)
+ C3 (1((1 (1-(111mm) nmmd)² VT/(mA) + m 2/3 //2 - 5/3 + VT/A)
+ C1m-1/6 /1om=1/0//ommm1777/000111
(uylos log det AI + +22 1/6 /1ggm 2log + VÁS
det Zr
Cs((t - -mnd) (T/(m)) amm22
2/3 2/3 7/2 1 + vT/2)], (B.17)
19

---

Under review as a conference paper at ICLR 2020
where the inequality holds due to Lemma B.3 B.14) and (B.17), we have
Finally, substituting (B.15). B.16 into (B.14) using
T
2 min
t=1
T Σ
min (gg(Xtari0--1))
MT,
2
t=1
+ +1m V log det AI
det ZT
V Cmm-1/6 / I.
(un/on log
del. Zr det AI
+ ( 2log8 VXS
+ C33 (1-mAA) mmA)" VT/(mA) + 3/2 log / T/A)
V dlog(1 + TK/A) +
C1m-116 7.
+ TK/A) + C2m 1 220-221gg 8 + VXS
+ +Ca((1 mmm1) (T/AA//T/(mA/))))) + 3/2 / + TT/A
C PROOFS OF TECHNICAL LEMMAS IN APPENDIX B
C. PROOF LEMMA B.1
In this section we prove Lemma B.1 we need the following lemma from Arora et al. (2019)
Lemma C.1 (Theorem 3.1, Arora et al. (2019). Fix > and E (0, 1). Suppose that
L log(L//))
Ω
e4
then for any i,j E [TK], with probability at least 1- over random initialization of Og. we have
(gg(x";0)): g(x))))ggxx00)))) 00)) H. Se.
(C.1)
Proof of Lemma B.1
Taking union bound over i,j E [TK], we have that if
L log (ogg(T2K2)) (
Ω
e4
then with probability least 1 8, C.I holds for all (i, [TK] [TK). Therefore, we have
Tk TK
|G GG
H
(g(x); g()) -
H 2 TKc.
20

---

Under review as a conference paper at ICLR 2020
C.2 PROOF OF LEMMA B.2
In this section we prove Lemma B.2 During the proof, for the simplicity, we omit the subscript / by default. We define the following quantities:
J (g(X)a1) .... .(.8))))...8x...... : E (l
H ) = [ j(m E !
f() (f(x),r)) (())..... f(x,,a 0(1)) R
(f1,0)1--.) at,, E [
Then the update rule of g0) can be written as follows:
0++1) وهم ( (rl) -v) + mA((5)) )(
(C.2)
We also define the following auxiliary sequence (0(k) during the proof:
i 0) = ( Ø(++1) = (نق - ( (0t) - Ø(0) v) + mA - -
Next lemma provides perturbation bounds for J(,, H and || p(t) [ (6)
(ou+1)
Lemma C.2. There exist constants (C: > 0 such that for any ó > 0, if satisfies that
Cim 3/2 -32-3/2 --32 (loplllo
S C2L 3/22
then with probability at least 5 over the random initialization of (0), if for any j E [J], |0))
((0) 2 I T, we have the following inequalities for any j E [J].
|| |F S C.VtmL,
(C.3)
|| - J( | s Cs Cm (ommloogm//// 1/3 ||r(+]]] pt) - ( - s Cor4/3 ( tmglomm m,
(C.4)
(C.5)
livl2 I Vt.
(C.6)
Next lemma gives an upper bound for ||P()) v/12- Lemma C.3. There exist constants (C: > 0 such that for any 8 > O, if r, satisfy that
Cim 3/2 3/2 [og( /8))3/2 < C2 (log m] 3/2
") S Cs(mA + tmL)
8/3 < (mm 6- (logm)
-6
then with probability at least 1 8 over the random initialization of (()), ffr any j E [J], (06) ((0) ||2 < have that for any j E [J], [[ -v22 < 2v7.
Next lemma gives an upper bound of the distance between auxiliary sequence ||00) o Lemma C.4. There exist constants {C.)²= > 0 such that for any d (0, 1). if 7, satisfy that
C,m-3/22 10223/LL3//220 (TT /8))8/2 <T C2L m] 3/2 3/23/
S Ca(mmL + m
then with probability least 5, we have that for any j E [J].
(06) - 8 000 - /t/(mA).
@ (( (Z) /b//ml S (1- - mmX)' Vt/(mA)
With above lemmas, prove Lemma B.2 follows.
21

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 8.2 Set 2/t/(mA), First we assume that |@00) - - <
for all j < and
J. Then with this assumption and the choice of m, T, we have that Lemma C.2
C.3
C.4 hold.
Then we have
||0 - -
-1060 - -6) - m)(J() - (()) - v) - mm))(00)))))))) - Ō
1,,100 (pb) - [ -
11 (yuur - -
- (ajli _ (r()
(o Ril
(() - (1 (0oo ) T (00) - ((:))] |||
< [I -----7
+ +lll+ p() [] 1 i[[te0 + + (10) - -
1 + 1/ (J - 110 -
< (1 (/
v 1)112
+ 1 |ممم c (0 -
(C.7)
where the first inequality holds due to triangle inequality, the second inequality holds due to the fact that ()) n/ ni] ((0) < CitmLnI S I with (C.3) in Lemma C.2 for some C₁ 0. We now
bound /,, 12 separately. For /,, we have
I S m J || vll2 s n/22 m log l 1/32,/2
(C.8)
where C2 > 0 is constant, the first inequality holds due to matrix spectral norm and the second inequality holds due to (C.4) in Lemma C.2 and Lemma C.3] For I2, we have
I S n
p()) - J e(0)||
||, S xnCgmmL7/2241
(C.9)
where C3 > 0, the first inequality holds due to matrix spectral norm, the second inequality holds
due to CC.3 and (C.5) in Lemma C.2 and the fact that f(() 0 by random initialization over (())
Substituting (C.8) and into (C.7) we have
||0(+1)- 0
$ <(1 (1- (1-mma))ll0") 1 112 + C4 (nt m log mer 1/3 2/2 + 1/ Vlog m), (C.10)
where C. > 0 is a constant. Expanding (C.10) for times, we have
1tt logmmlmmmm 1/3 L/ + 222 ///
[0()+]] - /W++1)|| - C4
ymn
= Csm 2/3 Vo ////// 5/3 (1 v1/A)
(C.11)
2'
where C3 > 0 a constant, the equality holds by the definition of T, the last inequality holds due to the choice of m, where
1/6 Ce / Vlo /2 - vt/A),
Co > 0 is a constant. Thus, for any j E [J], we have
||0()
10 < | ~ || ||0 .0) 1| - (t/(mm) + +//2=1
(C.12)
where the first inequality holds due to triangle inequality, the second inequality holds due to Lemma suggests that our assumption |005) (00) ||2 S 7 holds for any u. Note that we have the following incquality by Lemma C.4
C.4
CC133
|00) (0) (Z)
-2) f 2 S (1 mymy Vt((mA).
(C.13)
Using
C.Il and C.13). we have
((()
(0) (Z) -1/ 155/mm/)
< (1- Vt/(mA) + Csm - 2/3 /lgmL 1/2 1/265/33/ + v1/A).
This completes the proof.
22

---

Under review as a conference paper at ICLR 2020
C.3
PROOF OF LEMMA B.3
In this section we prove Lemma B.3
Proof of Lemma B.3 Set (///(m)). By Lemma 6.2 [| can be bounded as follows.
we have that 110, 0oll2 S for i [t].
Z ||
Σ
g (x 0,) Ox) 0,) /mm
S
(x ax) S CotL,
where Co > a constant, the first inequality holds due to the fact that ||aa || ||a|| the second inequality holds due to Lemma B.6with the fact that |10, Ooll S We bound [Ze Ze || as follows. We have
IZ. ZellF=
g(Xi,aji (oska,000gg(0 (x)g(xi,,;;0)) 0o) ;
0z)g(xx,, /m
g Xi, 0x)g(xx, g(xi,a;; 0:) (x) 0:) (
(lg((x ; + (|g(xx,,;
(| 02) [g( Ou) g(xi, :
(C.14)
where the first inequality holds due to triangle inequality, the second inequality holds the fact that -bb T || I (||a|22 - ||bl2)][aa - bll2 for any vectors a, b. To bound (C.14), we have
Jaa"
e 00)l12 ( 0.)112 s CiVmL,
(C.15)
where C1 > O is a constant, the inequality holds due to Lemma B.6 with the fact that ||0,-0 -oololl2 S т. We also have
[g( ( 0p) g(xi, 0,]122 - C2V/log mor / 1/3 [g(;; 00)ll2 S Cs Cav Im mer 1/3 1/
(C.16)
where C2 C3 > 0 are constants, the first inequality holds due to Lemma B.5 with the fact that
0. Oolle I T, the second inequality holds due to Lemma B.6 Substituting (C.15) and (C.16 into C.14) we have
124 Z. Calvlog mrr 1/3,
where C2 > 0 is a constant. We now bound log det Z, - log det Zy It is easy to verify that where
Z, AI JJJ Z, AI JJJ
= g(xi 0o). g(xi,a,; Oo) /vm,
g(( 0o).... g(xi,..; 0 0--1) /
We have the following inequalities:
det(Z.) loog (Z,)
log (AI) dAI(AI)
= log det (I+ [[]] /A) log det + JJJ] /A)
= log det [I+ log det + [J] J/X)
< ((I+ [J] [J] [J] [J]]]
< ||I++ | [J]]]]p
J
s [ J J||e
(C.17)
23

---

Under review as a conference paper at ICLR 2020
where the second equality holds due to the fact that det AAT) det(I AT,), the first inequality holds due to the fact that log det function is convex, the second inequality hold due to the fact that (A, B) ||A|||||B|]r, the third inequality holds since + [J] R J/A À is a t-dimension matrix, the fourth inequality holds since + JJJJJ/J/ ł I. We have
[[]] [J] J
t max IstJst
g 0o) g(Xj,yy 0n) g(xi,a, 0:) 0 g(x),,,33 (
$ max 15tJ5t
g g(xi,a 0o) g(xi,a 0.) g(xx( Ja, 0z) 1
+ a( 0o) g(x 0,) a( 0u) 00)ll
Cogl/logm= L
(C.18)
where C3 > O is constant, the first inequality holds due to the fact that ||||| S mmax |Ag for
any A E IR the second inequality holds due to the fact la laTa' b < ||a | -bll// 22||bb/l2 +2||aaa a'
b/|2|||||22 the third inequality holds due to (C.55) and (C.16). Substituting (C.18) into (C.17). we have
det det(Z.) (Z.) log (Ze) (AI) S Cst Vlog 1/3 T,*.
log (AI)
Using the same method, also have
log det (Z.) det(AN) det(AI) < Ost (stt/2//oogme m/3
det
log
This completes our proof.
D PROOFS OF LEMMAS IN APPENDIX
D.1 PROOF OF LEMMA C.2
In this section we give the proof of Lemma C.2
Proof of Lemma C.2 For any j
E [J], the following inequalities hold. We first have
| || S max [g( e65))112 S CivtmL
(D.1)
aE[(]
where C1 > O is a constant, the first inequality holds due to the definition of Jú], the second inequality holds due Lemma B.6 We also have
( - J || S C2 C2ylog 1/3 L/ (1] || S Cay tm log me 1/3 7/2
1/3
(D.2)
where C2. C3 > are constants, the first inequality holds due Lemma B.5 with the assumption that ||06] 0(0) 1|
r, the second inequality holds due (D.I). We also have
|| p()) - [ - ((5))11
< max (x ) fxxiaa:; (g(xi,.;; 06)), 00+1) - -E(t)
< 4/T4/3
4/3 L V tm logm,
where C4 0 constant, the first inequality holds due the the fact that ||x||2 S vi max |aral
for any E Rf the second inequality holds due Lemma B.4 with the assumption that |00)
g(0) ||2 < || - g(0)|22 < For ||v]]2, we have ||vl12 S Vm |r(x),a)) S VE. This
completes our proof.
24

---

Under review as a conference paper at ICLR 2020
D.2
PROOF OF LEMMA C.3
Proof of Lemma
C.3
Recall that the loss function L is defined as
mn
L( - |l((0) v +
2 0 0100
We define J()) and f()) as follows:
O(0) (g1x f),................... (x, 0) E R (L
{(0) - (x O).... ......,((xxx (xe, 0)) E RRxx1
Suppose ||0 0 ||2 2 Then by the fact that 12/2 is 1-strongly convex and 1-smooth,
have the following inequalities:
L(0')- L(0)
(f(0) v. f(0') - f(0)) + 1 [|((0)) f(0) || mX(0 ( 0' 0)
mX 0'
e|
2
(f(0) v. [](O]] (0' -0) + + [J]] - -0) + ell2
+ +mx ( 0 + mX 0 0
2
-I(())((()) v) mA ( 0' + (f(() v,e)
1 [(()]] (0' 0 + = mA
0' 0
2
(VL(O), 0' 0) + (f(0) v, e) + 2
[ (0) T (0' 0) +
md
0
1
(D.3)
2
where e f(0') f(0) J(0) T T0' 0). can be bounded as follows:
11 < [|[()) v|l2//e||2 (0) 0' - -01 + |ell
+ md
0'
0
2
Ci (m) + tmL)| 0112 + |If(0) v||2||c||2 ||||2
(D.4)
2
where the first inequality holds due to -Schwar inequality, the second inequality holds due to the fact that [](0]]la < C2 VtL with l|e - 0 - t by (C.3) in Lemma C.2
Substituting
D.4 into D.3). we have
Ci L( (() (VL(0), 0' 0) (m (mm) tmL) -01 [f((0) vlla ||al|e||2 + ||ell2.
(D.5)
Taking 0' = - (O), then by (D55,, we have 10-11 L(e - v)()) L(0) < (L(0) - Ci(mA+ + [|f(0) - -v|22/ol|zz + ||c|
(D.6)
By the 1-strongly convexity || || we further have I(0") L(0)
2 (f(0) v. f(0') f(O)) + m2(0 (0)) 0' 0) + mX
2 0 0 1
mn
(f(0) v. [J( (0' 0) c) + mx 0 0 0' 0 +
0'
2
= (VL 0' - 0) +
md
00 0 + (f(0) v.e)
2
2 (VL(0), 0' 0)
m
2 0 0 ||[(0) - -
VL [[(0) v|12/|e||e,
(D.7)
2md
25

---

Under review as a conference paper at ICLR 2020
where the second inequality holds due to Cauchy-Schwarz inequality, the last inequality holds due
to the fact that (a. x) + c||x 2 - -|al// for any vectors a, x and 0. Substituting (D.7)
into (.6), have
L VV(()) L(0)
s 2mdn(11 - C1(mm+++++ (mL) +
+ (|(00) - v122|e||2 + ||((O) - v + |le|
< mmnmmmnnn [L(0') - L(0) - -|((()) 10--vlla v||2||e||a] + [[((0) vll2lee|12 ||el
< mmd SmAn[1(0) [L(0') - L(0) ||[(0) - -v1//8+4 + + vI 41lell (m)r) + ||el
I mm)n(L(0)) - L(()/2) + ||ellā(1 + 4mAn + 4/(mAn)),
(D.8)
where the second inequality holds due to the choice of n, third inequality holds due to Young's [ S 2L( Now taking 0 Q
inequality, fourth inequality holds due to the fact that | v1
and 0' f rearranging (D.8) with the fact that 0 065) (( we have
T(0(+t))) -
s (1 - (L) ((0 () + ||e| + 4mA1 + 4/(m)ni))
$ - 11- L(O + m2n/2 m
S (1 m)00 [(O + mAnt,
(D.9)
where the second inequality holds due to the fact that L(O(0) [|((0(0) v - 1
and
(1 + 4m2m + 4/(m2n)) 5 5/(m))) =l 8/3 logm S tmmn/22
(D.10)
where the first inequality holds due to (C.5) in Lemma C.2 the second inequality holds due to the choice of r. Expanding (D.9) u times, we have
mdnt
L(0 L(
2f,
mXn/2
which implies that [| - s 2VF. This completes our proof.
D.3 PROOF OF LEMMA C.4
In this section we prove Lemma C.4
Proof of Lemma C.4 It is worth noting that @63 is the sequence generated by applying gradient
descent on the following problem:
min T(()) 2
1
(0--((0) v12 +
md 110
0100
2
Then [0(00)
T 2| can be bounded as
mA ( ,0) 1
1
(T@) )(0)) - -
ml
(TS) (00
2
2
2
mA
[ (0)) 00) vIl2 +
0011
2
2
< T/2
where the first inequality holds trivially, the second inequality holds due to the monotonic decreasing property brought by gradient descent, the third inequality holds due to (C.6) in Lemma C22 It is function, since
easy to verify that L is A-strongly convex and function and C₁
L 3 (I) 12 + mA)I (tmLL + mA),
where the first inequality holds due to the definition of L, the second inequality holds due to C.3
in Lemma C.2 Since choose 7) I C2(tmL + mA)-1 II for some small enough C2 > 0, then by
standard result of gradient descent on ridge linear regression, θ converges to ((0) + (Z) - 1b/ \m with the convergence rate
| - ( (Z) -b/b Vm S (1 ( - vllz/VmX mm & (1 mmd)" T Vt((m)).
26

---

Under review as a conference paper at ICLR 2020
E A VARIANT OF NEURALUCB
In this section, present variant of NeuralUCB called NeuralUCBg- Compared with Algo- rithm | the main differences between NeuralUCB and NeuralUCBo are as follows: NeuralUCB uses gradient descent to train deep neural network learn the reward function h(x) based ob- served contexts and rewards. In contrast, NeuralUCB, uses matrix inversions to obtain parameters in closed forms. At each round, NeuralUCB uses the current DNN parameters (0:) to compute an upper confidence bound. In contrast, NeuralUCBp computes the UCB using the initial parameters (0p).
Algorithm 3 NeuralUCBy
Input: number of rounds T. regularization parameter X, exploration parameter v, confidence parameter 6, norm parameter S, network width m, network depth I,
2: Initialization: Generate each entry of W, independently from (0, 2/m) for 1 S L 1, and each entry of WL independently from N (0, 1/m). Define Φ(x) = g(x; 0o)/ Vm, where
0, |vec W1) w v....,eee( vec(WWL) E R"
3: Zu = AI, by
4: for /= ,,...,''o do do
5: Observe (Xt,a)==1 ) and compute
(a,, 0 0r. argmax (Ø(x,,a), -0p
(E.1)
ae 0EC,10
6: Play a and receive reward Nt,a: Compute
Z: 2:-1 + (
RPx,, b. b:- + Tt,, ((xi,))) E RR
8: Compute 0; = Zz + 00 E R2
9: Construct C2 as
det Z₁ det XI
C. = (0: 110 0l.. S 7hh.
where
Tt u log
2og 8 + VĀS
(E.2)
10: end for
27


Reviews:
[{"review_id": "rJeeYcLztH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposed a neural network based UCB algorithm for bounded reward contextual bandit problems with theoretical guarantee thanks to the recent development of Neural Tangent Kernel (NTK).\n\nThroughout the paper, the authors do not use much of the specific property of neural networks and NTK. They only use the gradient of neural networks as the feature and use the NTK as the kernel in the kernelized contextual bandits. This can be beneficial, for example, it can enriching the class of kernels. However, I feel the whole paper lacks novelty, and have some technical flaws.\n\nDetailed Comments:\n1. In Sec 3, the authors argued that kernelized contextual bandits suffers from the unknown RKHS problem and RKHS realizability problem. However, with universal kernel, RKHS is dense in L^2 space, thus can in principle approximate any function in L^2 space within any precision. So generally, this is not a problem. Moreover, bounded function does not necessarily contain the linear function, generalized linear function and bounded RKHS norm function. At least if we do not add some assumption on the input, linear function can be unbounded. On the other hand, the proposed methods also need p>TK to guarantee the realizability, and we can also design some kernel with feature map dimension larger than TK with some good property to guarantee realizability, so I think this claim is not fair.\n2. In Assumption 5.2, the authors assume that the norm of contexts is smaller than 1. However, as far as I know, most of the existing work assumed the context have norm 1, and can be only relaxed to the norm upper lower bounded by two positive constant c1 and c2 (see [1]). Otherwise, there can be some issue on the positive definiteness of the NTK. Can the authors carefully check this? Meanwhile, I think it is not suitable to directly assume the NTK is positive definite. It is better to follow and refer the readers to the existing work.\n3. It is better to introduce \\theta^* before Sec 6, like for example the parameter that can perfectly predict the mean reward.\n4. I am confusing on the proof of Lemma 6.1 in Page 12. When the authors calculate the norm of \\theta^* - \\theta_0, how to transform Q^\\top A^{-2} Q to G^\\top G? If we use the singular value decomposition, we only have that G^\\top G=QA^2 Q^\\top. If I understand correctly, here we should do an inverse, and we cannot simply get the desired results, as the minimum singular value of G can be small under current assumption. However, it is still possible to upper bound this distance to derive the remaining proof.\n5. In the first line of Equation (B.3), there is a typo that omits the \\phi(x)^\\top.\n6. How does the second inequality of (B.4) derives? I can understand that the authors may use the Cauchy-Schwartz inequality, but Frobenius norm cannot be directly upper bounded by spectral norm (though they are equivalent, but we need to add an additional constant like \\sqrt{TK}). If the authors use the spectral norm, then the second term should be nuclear norm, not Frobenius norm. Probably I do not understand it correctly and it is not the core issue, but I think it is better to clarify it.\n7. There is a typo in the fourth line of (B.4), it should be \\lambda / \\lambda_0,\n8. The last derivation of Appendix B.3 have several typos omitting det(\\lambda I).\n9. The authors should better include the kernelized contextual bandits for a fair comparison, as LinUCB and Neural \\epsilon-greedy both have theoretical issue that can be solved by kernel methods. I doubt that kernelized contextual bandits can solve these cases well.\n\nOverall, I feel that most of the proof can be derived similarly from [2][3]. And Lemma C.1 is also from [4]. The authors only verify some conditions that when use NTK as the kernel in kernelized contextual bandits to adjust the main result from [2][3]. Thus, I think the technique used in this paper is not novel as well.\n\nIn my opinion, the communities are interested in solving contextual bandits with ``''gradient based'' neural network methods that use the neural network to predict the rewards given some contexts as input. But just as the Equation (6.1) shows, the prediction is not based on the neural network, but with a linear model taken \\phi(x_i) as input. Also, throughout the paper, the authors never use the network output f. To this end, I feel this paper is over-claimed on ''neural''. On the other hand, I think it can be interesting to think about how kernel methods can benefit from NTK. Directly use the gradient as the feature map seems not an interesting and meaningful method, I think.\n\n[1] Cao, Yuan, and Quanquan Gu. \"A generalization theory of gradient descent for learning over-parameterized deep relu networks.\" arXiv preprint arXiv:1902.01384 (2019).\n[2] Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. 2013. Finite-time analysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI'13), Ann Nicholson and Padhraic Smyth (Eds.). AUAI Press, Arlington, Virginia, United States, 654-663.\n[3] Abbasi-Yadkori, Yasin, Dávid Pál, and Csaba Szepesvári. \"Improved algorithms for linear stochastic bandits.\" Advances in Neural Information Processing Systems. 2011.\n[4] Arora, Sanjeev, et al. \"On exact computation with an infinitely wide neural net.\" arXiv preprint arXiv:1904.11955 (2019).", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgraylCYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to use the Neural Tangent Kernel (NTK) with the Upper Confidence Bound for stochastic contextual bandits. \n- The paper instantiates Kernel UCB (Valko, 2013) with the NTK and the novelty is limited from a theoretical point of view. \n- There is no experimental comparison with Neural Linear or Kernel UCB using a fixed kernel, (for example, the RBF kernel) or to methods like Thompson sampling that work well in practice even with non-linearities. \n\nDetailed review below:\n- Section 2.2 is not relevant to the paper and it might be more useful to use this space to explain NTK better. \n- Please explain NTK before instantiating the algorithm in Section 4. \n- The \"Efficient Implementation\" section in Section 4 is standard and done in all the linear bandit papers. Please acknowledge this or say how it is different. \n- The NTK description in Definition 5.1 needs to be clarified. At the moment, it is difficult to parse. Please give some intuition about it. \n- For the regret analysis, could you explain how the analysis is different from that of a fixed kernel in Valko, 2013. \n- What is the intuition for having a lower bound on \"S\", the norm parameter? Why is there no upper bound? \n- The width of the neural network depends on T^4. How does this affect the effective dimension \\tilde{d} in the worst case? Can it result in linear regret?\n- For Lemma 6.2, 6.3, please say that these are directly borrowed from Valko, 2013 and Abbasi, 2011. \n- From an experimental perspective, the width of the neural network is a constant wrt to T, K and L and clearly doesn't align with the theoretical bounds. Please justify why this is a valid thing to do? \n- As mentioned earlier, there is no comparison with Kernel UCB with a fixed kernel, Neural Linear or Thompson sampling, methods that work well in practice. \n- Finally, real-world experiments are necessary to show the benefit of using NTK in practice. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1lfDtjXqr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes Neural UCB for the neural-linear bandit setting. The main contribution of the paper is the theorem that the proposed method, Neural UCB, is guarantee to achieved a good regret bound, which for the first time extends bandits result to neural networks. Overall the paper is well written and easy to follow. \n\nWhile the result of this paper seems to be interesting, the idea of the paper is simply combining a recent progress on the neural tangent kernel for overparametrized neural networks and a standard linear UCB algorithm. \n\nThe main concern I have is about the constant S in the regret bound. Note that this constant is an upper bound of \\sqrt{h^T H h}, where h is in the dimension of TK and H is in the dimension of TK by TK. A naive bound for S could be sup-linear in T, which makes the bound vacuous. What would be a lower bound for \\lambda_0 for eg. the setting in the experiments?\n\nOther comment:\n1. It should be explicitly stated somewhere in the paper that x_{t,k} are assumed to be deterministic. Thus \\theta^* is deterministic. It is more important that \\theta^* does NOT depends on a_t. Otherwise lemma 6.2 could be problematic. \n\n=====================\nBased on the new version of the paper and the discussions, I change the score to weak accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: As the reviewers have pointed out and the authors have confirmed, the original version of this paper was not a significant leap beyond combining recent understanding of Neural Tangent Kernels and previous techniques for kernelized bandits. In a revision, the authors updated their draft to allow the point at which gradients are centered around, theta_0, to now equal theta_t. This seems like a more reasonable algorithm and it is satisfying that the authors were able to maintain their regret bound for this dynamic setting. However, the revision is substantial and it seems unreasonable to expect reviewers to read the revised results in detail--the reviewers also felt it may be unfair to other ICLR submissions. All reviewers believe the paper has introduced valuable contributions to the area but should go under a full review process at a future venue. A reviewer would also like to see a comparison to Kernel UCB run on the true NTK (or a good approximation thereof). 
Decision: Reject