Title: NEURAL CONTEXTUAL BANDITS WITH UPPER CONFIDENCE BOUND-BASED EXPLORATION

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 a 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 O( √ T ) regret, 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.

1. INTRODUCTION:

The stochastic contextual bandit problem has been extensively studied in machine learning (Bubeck and Cesa-Bianchi, 2012; Lattimore and Szepesvári, 2019) : at round t ∈ {1, 2, . . . , T }, an 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 a stochastic reward generated from some unknown distribution conditioned on the chosen action'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 et al., 2010) .

The most studied model in the literature is linear contextual bandits (Auer, 2002; Abe et al., 2003; Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Chu et al., 2011; Abbasi-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 et al., 2010; Srinivas et al., 2010; Bubeck et al., 2011; Valko et al., 2013) . However, they still require fairly strong assumptions on the reward function. For instance, Filippi et al. (2010) makes a generalized linear model assumption on the reward, Bubeck et al. (2011) require it to have a Lipschitz continuous property in a 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-linear bandit. More precisely, they use the first L -1 layers of a 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 a theoretical guarantee on the regret of 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 an upper confidence bound constructed by deep neural network-based random feature mappings. Our regret analysis of NeuralUCB 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 O( d √ T ) 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(d √ T ) regret for linear contextual bandit as a special case (Abbasi-Yadkori et al., 2011) , where d is the dimension of context.

• We propose a 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-Yadkori et al., 2011) , from linear reward functions to 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 matrices by upper case bold face letters. For a positive integer k, [k] denotes {1, . . . , k}. For a vector θ ∈ R d , we denote its 2 norm by θ 2 = d i=1 θ 2 i and its j-th coordinate by [θ] j . For a matrix A ∈ R d×d , we denote its spectral norm, Frobenius norm, and (i, j)-th entry by A 2 , A F , and [A] i,j , respectively. We denote a sequence of vectors by {θ j } t j=1 , and similarly for matrices. For two sequences {a n } and {b n }, we use a n = O(b n ) to denote that there exists some constant C > 0 such that a n ≤ Cb n , a n = Ω(b n ) to denote that there exists some constant C > 0 such that a n ≥ C b n . In addition, we use O(•) to hide logarithmic factors. We say a random variable X is ν-sub-Gaussian if E exp(λ(X -EX)) ≤ exp(λ 2 ν 2 /2) for any λ > 0.

2. RELATED WORK:



2.1. CONTEXTUAL BANDITS:

There is a line of extensive work on linear bandits (e.g., Auer, 2002; Abe et al., 2003; Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Li et al., 2010; Chu et al., 2011; Abbasi-Yadkori et al., 2011) . 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 O √ 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 a lower bound of Ω( √ dT ). For the other setting with infinitely many arms, a few authors (Dani et al., 2008; Rusmevichientong and Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011) proposed algorithms that achieve O(d

√:

T ) regret, whereas an Ω(d √ T ) lower bound is given by Dani et 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; Kveton et al., 2019) .

To deal with nonlinearity, generalized linear bandit has been considered, which assumes that the reward function can be written as a composition of a linear function and a link function. In particular, Filippi et al. (2010) proposed a GLM-UCB algorithm, which attains O(d √ T ) regret. Li et al. (2017) proposed SupCB-GLM for generalized contextual bandit problems and showed a O( √ dT ) regret that matches the lower bound. Jun et al. (2017) studied how to 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 exponential in the number of parameters). Another approach is to reduce a bandit problem to supervised learning, such as the epoch-greedy algorithm (Langford and Zhang, 2008) that has an O(T 2/3 ) regret. Later, Agarwal et al. (2014) develop an algorithm that yields a near-optimal regret bound, but relies on an optimization oracle that can be expensive. A third approach uses nonparametric modeling, such as Gaussian processes and kernels (Srinivas et al., 2010; Krause and Ong, 2011; Valko et al., 2013) . More specifically, Srinivas et al. (2010) assumed that the reward function is generated from a Gaussian process with known mean and covariance functions. They proposed a GP-UCB algorithm which achieves O( √ T γ T ) regret, where γ T is the maximum information gain. Krause and Ong (2011) assumed the reward function is defined over the context-arm joint space and proposed a 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 O( dT ) regret, where d is effective dimension of the kernel that can be seen as a generalized notion of the dimension of contexts. There is also work focusing on bandit problems in general metric space with Lipschitz continuous property on the context (Kleinberg et al., 2008; Bubeck et al., 2011) .

2.2. NEURAL NETWORKS:

Different lines of research have been done to provide theoretical understandings of DNNs from different aspects. For example, to understand how the expressive power of DNNs are related to their architecture, Telgarsky (2015; 2016) ; Liang 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, a series of work have been proposed to show that (stochastic) gradient descent can find the global minima of training loss (Li and Liang, 2018; Du et al., 2019b; Allen-Zhu et al., 2019; Du et al., 2019a; Zou et al., 2019; Zou and Gu, 2019) . For the generalization of DNNs, a series of work (Daniely, 2017; Cao and Gu, 2019a; b; Arora et al., 2019) shows that by using (stochastic) gradient descent, the parameters of a DNN are located in a 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 t ∈ [T ], the agent observes the tth context consisting of K feature vectors:

{x t,a ∈ R d | a ∈ [K]}.

The agent selects an action a t and receive a reward r t,at . For simplicity, we denote {x i } T K i=1 as the collection of {x 1,1 , x 1,2 , . . . , x T,K }. Our goal is to maximize the following pseudo regret (or regret for short):

R T = E T t=1 (r t,a * t -r t,at ) , (3.1)

where a * t is the optimal action at round t that maximizes the expected reward, i.e.,

a * t = argmax a∈[K] E[r t,a ].

This work makes the following assumption on reward generation: for any round t,

r t,at = h(x t,at ) + ξ t , (3.2)

where h is some unknown function satisfying 0 ≤ h(x) ≤ 1 for any x, and ξ t is ν-sub-Gaussian noise conditioned on x 1,a1 , . . . , x t-1,at-1 . Note that the ν-sub-Gaussian noise assumption for ξ t is a standard assumption in stochastic bandit literature (e.g., Abbasi-Yadkori et al., 2011) ; 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), we propose to use a fully connected deep neural networks with depth L ≥ 2:

EQUATION

where σ(x) = max{x, 0} is the rectified linear unit (ReLU) activation function,

W 1 ∈ R m×d , W i ∈ R m×m , 2 ≤ i ≤ L -1, W L ∈ R m×1

, and θ = [vec(W 1 ) , . . . , vec(W L ) ] ∈ R p with p = m + md + m 2 (L -1). Without loss of generality, we assume that the width of each hidden layer is the same (i.e., m) for convenience in analysis. We denote the gradient of the neural network function by g(x; θ) = ∇ θ f (x; θ) ∈ R p .

4. THE NEURALUCB ALGORITHM:

We present in Algorithm 1 our algorithm, NeuralUCB. The key idea is to use a deep neural network f (x; θ) to predict the reward of context x, and upper confidence bound-based exploration (Auer, 2002) . In particular, Algorithm 1 first initializes the network by randomly generating each entry of θ from an appropriate Gaussian distribution. More specifically, for each 1 ≤ l ≤ L -1, we initialize W l as W 0 0 W , where each entry of W is generated independently from N (0, 4/m).

For W L , we initialize W L as (w , -w ), where each entry of w is generated independently from N (0, 2/m). At round t, Algorithm 1 observes the contexts for all actions, {x t,a } K a=1 . First, it computes the upper confidence bound, U t,a , based on context x t,a , the current neural network parameter θ t-1 , and a scaling factor γ t-1 . It then chooses action a t with the largest U t,a , and receives the corresponding reward r t,at . At the end of round t, Algorithm 1 updates θ t by applying Algorithm 2 to (approximately) minimize L(θ) using gradient descent, and updates γ t . We choose gradient descent in Algorithm 2 for the simplicity of analysis, although the training method can be replaced by more efficient algorithms like stochastic gradient descent with a more involved analysis (Allen-Zhu et al., 2019; Zou et al., 2019) . Compute U t,a = f (x t,a ; θ t-1 ) + γ t-1 g(x t,a ; θ t-1 ) Z Compute

γ t = 1 + C 1 m -1/6 log mL 4 t 7/6 λ -7/6 • ν log det Z t det λI + C 2 m -1/6 log mL 4 t 5/3 λ -1/6 -2 log δ + √ λS + C 3 (1 -ηmλ) J t/λ + m -1/6

log mL 7/2 t 5/3 λ -5/3 (1 + t/λ) .

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 of each action and chooses the action by -greedy policy. In contrast, our NeuralUCB uses upper confidence bound based exploration, which is more effective than -greedy. In addition, our algorithm only uses one neural network instead of K neural networks, thus can be computationally more efficient.

Algorithm 2 TrainNN(λ, η, J, m, {x i,ai } t i=1 , {r i,ai } t i=1 , θ (0) ) 1: Input: Regularization parameter λ, step size η, number of gradient descent steps U , network width m, contexts {x i,ai } t i=1 , rewards {r i,ai } t i=1 , initial parameter θ (0) . 2: Define L(θ) = t i=1 (f (x i,ai ; θ) -r i,ai ) 2 /2 + mλ θθ (0) 2 2 /2. 3: for j = 0, . . . , J -1 do 4: θ (j+1) = θ (j) -η∇L(θ (j) ) 5: end for 6: return θ (J) . Lipton et al. (2018) used Thompson sampling on deep neural networks (through variational inference) in reinforcement learning. A variant is proposed by Azizzadenesheli et al. (2018) that works well on a set of Atari benchmarks. Riquelme et al. (2018) proposed NeuralLinear, which uses the first L -1 layers of a L-layer DNN to learn a representation, then applies Thompson sampling on the last layer to choose action. Zahavy and Mannor (2019) proposed a NeuralLinear with limited memory (NeuralLinearLM), which also uses the first L -1 layers of a L-layer DNN to learn a representation and applies Thompson sampling on the last layer. Instead of computing the exact mean and variance in Thompson sampling, NeuralLinearLM only computes their approximation. Unlike NeuralLinear and NeuralLinearLM, NeuralUCB uses the entire DNN to learn the representation and constructs the upper confidence bound based on the random feature mapping defined by the neural network gradient.

Variant of NeuralUCB:

We provide a variant of NeuralUCB called NeuralUCB 0 in Appendix E. NeuralUCB 0 can be regarded as a simplified version of NeuralUCB where the neural network parameter vector θ t is not updated at each round. In this sense, NeuralUCB 0 can be seen as Ker-nelUCB (Valko et al., 2013) specialized to the Neural Tangent Kernel (Jacot et al., 2018) , or Lin-UCB (Li et al., 2010) with Neural Tangent Random Features (Cao and Gu, 2019a ). We will include both NeuralUCB and NeuralUCB 0 in the experiments.

Efficient Implementation Algorithm 1 can be implemented efficiently using iterative first-order algorithms, as in linear bandit literature (Li et al., 2010; Valko et al., 2013; Agarwal et al., 2014) . More details are given here for the sake of completeness. At round t, we define d t,a = Z -1 t-1 g(x t,a ; θ t ). Based on d t,a , we update det(Z t ) by matrix determinant lemma (Golub and Van Loan, 1996) :

det(Z t ) = det Z t-1 + g(x t,at ; θ t )g(x t,at ; θ t ) /m = 1 + g(x t,at ; θ t ) Z -1 t-1 g(x t,at ; θ t )/m det(Z t-1 ). (4.1)

Note that (4.1) only requires to compute vector inner product between g(x t,at ; θ t ) and d t,a , which only requires O(p) time. Now we show how to compute d t,a efficiently. By the definition of d t,a , we have

g(x t,a ; θ t ) = Z t-1 d t,a = λI + t-1 i=0 g(x i,ai ; θ i )g(x i,ai ; θ i ) /m d t,a .

Thus, d t,a is the global minimizer of the following convex optimization problem:

min d∈R p λI + t-1 i=0 g(x i,ai ; θ i )g(x i,ai ; θ i ) /m d -g(x t,a ; θ t ) 2 2 ,

and we can use (stochastic) gradient descent to find d t,a efficiently, whose update formula can be written as follows:

d (i+1) = d (i) -η λI + t-1 i=0 g(x i,ai ; θ i )g(x i,ai ; θ i ) /m λI + t-1 i=0 g(x i,ai ; θ i )g(x i,ai ; θ i ) /m d (i) -g(x t,a ; θ t ) ,

which again only requires to compute vector inner products.

5. REGRET ANALYSIS:

In this section, we present a regret analysis for Algorithm 1. Recall that {x i } T K i=1 is the collection of all {x t,a }. Since our regret analysis is built upon the recently proposed neural tangent kernel matrix (Jacot et al., 2018) , we start with its formal definition. Definition 5.1 (Jacot et al. (2018) ; Cao and Gu (2019a) ). For a set of contexts {x i } T K i=1 , define

H (1) i,j = Σ (1) i,j = x i , x j , A (l) i,j = Σ (l) i,i Σ (l) i,j Σ (l) i,j Σ (l) j,j , Σ (l+1) i,j = 2E (u,v)∼N (0,A (l) i,j ) σ(u)σ(v), H (l+1) i,j = 2 H (l) i,j E (u,v)∼N (0,A (l) i,j ) σ (u)σ (v) + Σ (l+1) i,j

.

Then, H = ( H (L) + Σ (L) )/2 is called the neural tangent kernel (NTK) matrix on the context set.

As shown in Definition 5.1, the Gram matrix of the NTK on the contexts {x i } T K i=1 for L-layer neural networks is defined in a recursive way from the input layer all the way to the output layer of the neural network. For more details about the derivation of Definition 5.1, please refer to Jacot et al. (2018) . Based on Definition 5.1, we first lay out the assumption on the contexts

{x i } T K i=1 . Assumption 5.2. H λ 0 I. Moreover, for any 1 ≤ i ≤ T K, x i 2 = 1 and [x i ] j = [x i ] j+d/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 et al., 2019; Cao and Gu, 2019a) . It can be satisfied as long as no two contexts in {x i } T K i=1 are parallel. The second part is also mild: for any context x,

x 2 = 1, we can always construct a new context x = [x , x ] / √ 2 to satisfy Assumption 5.2. It can be verified that if θ 0 is generated by the random initialization scheme in Algorithm 1, then f (x i ; θ 0 ) = 0 for any i ∈ [T K].

Next we define the effective dimension d of the neural tangent kernel matrix on contexts {x i } T K i=1 . Definition 5.3. The effective dimension d of the neural tangent kernel matrix on contexts {x i } T K i=1 is defined as

d = log det(I + H/λ) log(1 + T K/λ) .

(5.1)

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 kernel-based Q-learning. Suppose the effective dimension of the reproducing kernel Hilbert space induced by the given kernel is d and the feature mapping ψ induced by the given kernel satisfies ψ(x) 2 ≤ 1 for any x ∈ R d . 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 T logarithmically in certain specific cases (Valko et al., 2013) .

Now we are ready to present the main result, which provides the regret bound R T of Algorithm 1.

Theorem 5.5. Let d be the effective dimension defined in Definition 5.

3. Let h = [h(x i )] T K i=1 ∈ R T K . Suppose there are constants C 1 , C 2 > 0, such that for any δ ∈ (0, 1), if m = poly(T, L, K, λ -1 , λ -1 0 , S -1 , log(1/δ)), η = C 1 (mT L + mλ) -1 , λ ≥ max{1, S -2 }, and S ≥ √ 2h H -1 h.

Then, with probability at least 1 -δ over the random initialization of θ 0 , the regret of Algorithm 1 satisfies

R T ≤ 3 √ T d log(1 + T K/λ) + 2 ν d log(1 + T K/λ) + 2 -2 log δ + 2 √ λS + C 2 (1 -λ/(T L)) J T /λ + 1.

(5.2)

Remark 5.6. It is worth noting that, simply applying results for linear bandit to our algorithm would lead to a linear dependence of p or √ p in the regret. Such a bound is vacuous since in our setting p would be very large compared with the number of rounds T and the input 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 a term (1 -λ/(T L)) J T /λ, which characterizes the optimization error of Algorithm 2. More specifically, it suffices to set The high-probability result in Theorem 5.5 can be used to obtain a bound on the expected regret. Corollary 5.9. Under the same conditions in Theorem 5.5, we have

J = log(λS/ √ T )/(λ/(T L)) = O(T L/λ) (independent of m) such that (1 -λ/(T L)) J T /λ ≤ √ λS,

E[R T ] ≤ 3 √ T d log(1 + T K/λ) + 2 ν d log(1 + T K/λ) + 2 + 2 log T + 2 √ λS + C 1 (1 -λ/(T L)) J T /λ + 2.

6. 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., 2011; Abbasi-Yadkori et al., 2011) . Furthermore, unlike the fixed feature mapping used in Valko et al. (2013) , NeuralUCB uses neural network f (x; θ t ) and its gradient g(x; θ t ) as a dynamic feature mapping depending on θ t . 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, we 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 gathered in the appendix. Lemma 6.1. There exists some constant C > 0 such that for any δ

∈ (0, 1), if m ≥ CT 4 K 4 L 6 log(T 2 K 2 L/δ)/λ 4 0 , then with probability at least 1 -δ over the random initialization of θ 0 , there is a θ * ∈ R p such that h(x i ) = g(x i ; θ 0 ), θ * -θ 0 , √ m θ * -θ 0 2 ≤ √ 2h H -1 h, (6.1) for all i ∈ [T K].

Lemma 6.1 suggests that with high probability, the reward function restricted on {x i } T K i=1 can be regarded as a linear function of g(x i ; θ 0 ) parameterized by θ * -θ 0 , where θ * lies in a ball centered at θ 0 . Note that here θ * is not a 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., 2011) to show that with high probability, θ * lies in the sequence of confidence sets. Lemma 6.2. There exist constants { Ci } 2 i=1 > 0 such that for any δ ∈ (0, 1), if η ≤ C1 (T mL + mλ) -1 and m ≥ C2 max T 7 λ -7 L 21 (log m) 3 , λ -1/2 L -3/2 (log(T KL 2 /δ)) 3/2 , then with probability at least 1 -δ over the random initialization of θ 0 , we have θ t -θ 0 2 ≤ 2 t/(mλ) and

θ * -θ t Zt ≤ γ t / √ m for all t ∈ [T ]. Lemma 6.3. Denote a * t = argmax a∈[K] h(x t,a ). There exist constants { Ci } 3 i=1 > 0 such that for any δ ∈ (0, 1), if η ≤ C1 (T mL + mλ) -1 , m ≥ C2 max T 7 λ -7 L 21 (log m) 3 , λ -1/2 L -3/2 (log(T KL 2 /δ)) 3/2 ,

then with probability at least 1 -δ over the random initialization of θ 0 , we have

h x t,a * t -h x t,at ≤ 2γ t-1 min g(x t,at ; θ t-1 )/ √ m Z -1 t-1

, 1 + C3 Sm -1/6 log mT 7/6 λ -1/6 L 7/2 + m -1/6 log mT 5/3 λ -2/3 L 3 , Lemma 6.3 gives upper bounds for h x t,a * t -h x t,at , which helps us to bound the regret R T . It is worth noting that γ t has a term log det Z t . A trivial upper bound of log det Z t would result in an dependence on the neural network width m, since the dimension of

Z t is p = md + m 2 (L -2) + m.

The next lemma establishes an upper bound which is independent of m, and is only related to effective dimension d. The dependence on d is similar to Lemma 4 of Valko et al. (2013) , but the proof is different as we use a different notion of effective dimension. Lemma 6.4. There exist constants

{ Ci } 3 i=1 > 0 such that for any δ ∈ (0, 1), if η ≤ C1 (T mL + mλ) -1 , m ≥ C2 max T 7 λ -7 L 21 (log m) 3 , T 6 K 6 L 6 (log(T KL 2 /δ)) 3/2 ,

then with probability at least 1 -δ over the random initialization of θ 0 , we have

T t=1 γ 2 t-1 min g(x t,at ; θ t-1 )/ √ m 2 Z -1 t-1 , 1 ≤ d log(1 + T K/λ) + 1 + C3 m -1/6 log mL 4 T 5/3 λ -1/6 1 + C3 m -1/6 log mL 4 T 7/6 λ -7/6

• ν d log(1 + T K/λ) + 1 + C3 m -1/6 log mL 4 T 5/3 λ -1/6 -2 log δ + √ λS + C3 (1 -ηmλ) J T /λ + m -1/6 log mL 7/2 T 5/3 λ -5/3 (1 + T /λ) .

With above lemmas, we begin to prove Theorem 5.5.

Proof of Theorem 5.5. The total regret R T can be bounded as follows:

R T = T t=1 h x t,a * t -h x t,at ≤ 2 T t=1 γ t-1 min g(x t,at ; θ t-1 )/ √ m Z -1 t-1 , 1 + C 1 Sm -1/6 log mT 13/6 λ -1/6 L 7/2 + m -1/6 log mT 8/3 λ -2/3 L 3 , ≤ 2 T T t=1 γ 2 t-1 min g(x t,at ; θ t-1 )/ √ m 2 Z -1 t-1 , 1 + C 1 Sm -1/6 log mT 13/6 λ -1/6 L 7/2 + m -1/6 log mT 8/3 λ -2/3 L 3 ≤ 3 √ T d log(1 + T K/λ) + 2 ν d log(1 + T K/λ) + 2 -2 log δ + 2 √ λS + C 2 (1 -ηmλ) J T /λ + 1,

where C 1 , C 2 > 0 are constants, the first inequality holds due to Lemma 6.3, the second inequality holds Cauchy-Schwarz inequality, the third inequality holds due to Lemma 6.4 and choosing large enough m. This completes our proof. 

7. EXPERIMENTS:

While the focus of this work is mostly on theoretical analysis of regret, we present results in proofof-concept experiments in simulated problems. We compare it with four representative baselines: (1) LinUCB; (2) Neural -Greedy, which replaces the UCB based exploration in Algorithm 1 by -greedy based exploration; (3) NeuralUCB 0 ; and (4) Neural -Greedy 0 which replaces the UCB based exploration in NeuralUCB 0 by -greedy based exploration. We use the cumulative regret as the performance metric.

In our simulation, we use contextual bandit problems with context dimension d = 20, the number of actions K = 4 and the number of rounds T = 10 000. The contextual vectors {x 1,1 , . . . , x T,K } are randomly chosen from N (0, I) and then normalized to have unit norm, i.e., x t,a 2 = 1. For the reward function h, we investigate the following nonlinear functions:

h 1 (x) = 10(x a) 2 , h 2 (x) = x A Ax, h 3 (x) = cos(3x a),

where A ∈ R d×d 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 h i (•), the reward at round t for action a is generated by r t,a = h i (x t,a ) + ξ t , where ξ t is independently drawn from N (0, 1).

For LinUCB, we follow Li et al. (2010) to implement it with a constant radius α. We do a grid search for α over {0.01, 0.1, 1, 10} and choose the best α for comparison. For NeuralUCB NeuralUCB 0 , Neural -Greedy and Neural -Greedy 0 , we choose a two-layer neural network f (x; θ) = √ mW 2 σ(W 1 x) with network width m = 20, where θ = [vec(W 1 ) , vec(W 2 ) ] ∈ R p and p = md + m. We remark that the bound on the required network width m is likely not tight. Therefore, in experiments we choose m to be relatively large (but not as large as theory suggests). For γ t in NeuralUCB, we choose γ t = γ in the experiment. We do a grid search over {0.01, 0.1, 1, 10} and choose the best γ for comparison. For NeuralUCB 0 , we choose ν = 1, λ = 1, δ = 0.1, and we do a grid search over {0.01, 0.1, 1, 10} for hyper-parameter S to choose the best S for comparison. For Neural -Greedy and Neural -Greedy 0 , we do a grid search for over {0.001, 0.01, 0.1, 0.2} and choose the best for comparison. For all the algorithms, we repeat the experiment for 10 runs and report the averaged results for comparison. For TrainNN, we choose the step size η = 0.1. To accelerate the training process, we update the parameter θ t by TrainNN every 50 rounds. We use stochastic gradient descent with batch size 50 and set J = t at t-th round of NeuralUCB and Neural -Greedy.

We plot the cumulative regret of compared algorithms in Figure 1 , for reward function h ∈ {h 1 , h 2 , h 3 }. We can see that due to the nonlinearity of reward function h, 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 -Greedy is in-between. This suggests that while Neural -greedy can capture the nonlinearity of the underlying reward function, -Greedy based exploration is not as effective as UCB based exploration. This confirms the effectiveness of NeuralUCB for contextual bandit problems with any bounded (nonlinear) reward function. Meanwhile, it is worth noting that NeuralUCB and Neural -Greedy outperform NeuralUCB 0 and Neural -Greedy 0 , which suggests that using deep neural networks to predict the reward function is better than using a fixed feature mapping associated with NTK. Another observation is that although the network width m in the experiment is not as large as our theory suggests, NeuralUCB still achieves a sublinear regret for nonlinear reward functions. We leave it as a future work to investigate the impact of m on regret.

8. CONCLUSIONS AND FUTURE WORK:

In this work, we proposed a new algorithm NeuralUCB for stochastic contextual bandit problems based on neural networks. We show that for arbitrary bounded reward function, our algorithm achieves O( d

T ) 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 it with the state-of-the-art 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 network using other strategies like Thompson sampling.

A PROOF OF ADDITIONAL RESULTS IN SECTION 5:

A.1 VERIFICATION OF REMARK 5.4 Suppose there exists a mapping ψ : R d → R d satisfying ψ(x) 2 ≤ 1 which maps any context x ∈ R d to the Hilbert space H associated with the Gram matrix H ∈ R T K×T K over contexts {x i } T K i=1 . Then H = Ψ Ψ, where Ψ = [ψ(x 1 ), . . . , ψ(x T K )] ∈ R d×T K . Thus, we can bound the effective dimension d as follows

d = log det[I + H/λ] log(1 + T K/λ) = log det I + ΨΨ /λ log(1 + T K/λ) ≤ d • log I + ΨΨ /λ 2 log(1 + T K/λ) .

where the second equality holds due to the fact that det(I + A A/λ) = det(I + AA /λ) holds for any matrix A, and the inequality holds since det A ≤ A d 2 for any A ∈ R d× d . Clearly, d ≤ d as long as I + ΨΨ /λ 2 ≤ 1 + T K/λ. Indeed,

I + ΨΨ /λ 2 ≤ 1 + ΨΨ 2 /λ ≤ 1 + T K i=1 ψ(x i )ψ(x i ) 2 /λ ≤ 1 + T K/λ ,

where the first inequality is due to triangle inequality and the fact λ ≥ 1, the second inequality holds due to the definition of Ψ and triangle inequality, and the last inequality is by ψ(x i ) 2 ≤ 1 for any 1 ≤ i ≤ T K.

A.2 VERIFICATION OF REMARK 5.8

Let K(•, •) be the NTK kernel, then for any i, j ∈ [T K], we have H i,j = K(x i , x j ). We first prove that h H = β * 2 . Since h ∈ H, we know that

h(x) = n i=1 α i K(x i , x) = n i=1 α i ψ(x i ), ψ(x) = n i=1 α i ψ(x i ), ψ(x) ,

for some {x i } n i=1 , {α i } n i=1 . Thus, we have β * = n i=1 α i ψ(x i ). Therefore, we have

h 2 H = n i,j=1 α i α j K(x i , x j ) = n i,j=1 α i α j ψ(x i ), ψ(x j ) = n i=1 α i ψ(x i ), n j=1 α j ψ(x j ) = β * , β * = β * 2 2 , which immediately suggests that h H = β * 2 . Next we prove that h H ≥ √ h H -1 h. First, h can be decomposed as h = h H + h ⊥ , where h H (x) = T K i=1 α i K(x, x i ) is the projection of h to the function space spanned by {K(x, x i )} T K

i=1 and h ⊥ is the orthogonal part. By definition we have h(

x i ) = h H (x i ) for i ∈ [T K], thus h = [h(x 1 ), . . . , h(x T K )] = [h H (x 1 ), . . . , h H (x T K )] = T K i=1 α i K(x 1 , x i ), . . . , T K i=1 α i K(x T K , x i ) = H α,

which implies that α = H -1 h. Thus, we have

h H ≥ h H H = √ α H α = √ h H -1 HH -1 h = √ h H -1 h.

A.3 PROOF OF COROLLARY 5.9

Proof of Corollary 5.9. Notice that R T ≤ T since 0 ≤ h(x) ≤ 1. Thus, with the fact that with probability at least 1 -δ, (5.2) holds, we can bound E[R T ] as

E[R T ] ≤ (1 -δ) 3 √ T d log(1 + T K/λ) + 2 ν d log(1 + T K/λ) + 2 -2 log δ + 2 √ λS + C 2 (1 -ηmλ) J T /λ + 1 + δT. (A.1)

Taking δ = 1/T completes the proof.

B PROOF OF LEMMAS IN SECTION 6:

B.1 PROOF OF LEMMA 6.1

We start with the following lemma: K) . We denote the neural tangent kernel matrix H the same as Definition 5.1. For any δ ∈ (0, 1), if

Lemma B.1. Let G = [g(x 1 ; θ 0 ), . . . , g(x T K ; θ 0 )]/ √ m ∈ R p×(T

m = Ω L 6 log(T KL/δ) 4 ,

then with probability at least 1 -δ over the random initialization of θ 0 , we have

G G -H F ≤ T K .

We begin to prove Lemma 6.1.

Proof of Lemma 6.1. By Assumption 5.2, we know that λ 0 > 0. Then with probability at least 1-δ, we have

G G H -G G -H F I H -λ 0 I/2 H/2 0, (B.1)

where the second inequality holds due to Lemma B.1 with the choice of m, the third and fourth inequality holds due to H λ 0 I 0. Thus, suppose the singular value decomposition of G is

G = PAQ , P ∈ R p×T K , A ∈ R T K×T K , Q ∈ R T K×T K , we have A 0 and θ * = θ 0 + PA -1 Q h/

√ m satisfies (6.1). To validate that θ * satisfies (6.1), first we have

G √ m(θ * -θ 0 ) = QAP PA -1 Q h = h,

which suggests that for any i, g(x i ; θ 0 ), θ * -θ 0 = h(x i ). We also have

m θ * -θ 0 2 2 = h QA -2 Q h = h (G G) -1 h ≤ 2h H -1 h

, where the last inequality holds due to (B.1). Thus, our proof finishes.

B.2 PROOF OF LEMMA 6.2:

In this section we prove Lemma 6.2. For the simplicity, we denote Zt , bt , γt as follows:

Zt = λI + t i=1 g(x i,ai ; θ 0 )g(x i,ai ; θ 0 ) /m, bt = t i=1 r i,ai g(x i,ai ; θ 0 )/ √ m, γt = ν log det Zt det λI -2 log δ + √ λS.

We need the following lemmas. The first lemma shows that the network parameter at each round θ t can be well approximated by

θ 0 + Z-1 t bt / √ m.

Lemma B.2. There exist constants { Ci } 5 i=1 > 0 such that for any δ > 0, if η, m satisfy that for all t ∈ [T ],

2 t/(mλ) ≥ C1 m -3/2 L -3/2 [log(T KL 2 /δ)] 3/2 , 2 t/(mλ) ≤ C2 min L -6 [log m] -3/2 , m(λη) 2 L -6 t -1 (log m) -1 3/8 , η ≤ C3 (mλ + tmL) -1 , m 1/6 ≥ C4 log mL 7/2 t 7/6 λ -7/6 (1 + t/λ),

then with probability at least 1 -δ over the random initialization of θ 0 , for any t ∈ [T ], we have that θ t -θ 0 2 ≤ 2 t/(mλ) and

θ t -θ 0 -Z-1 t bt / √ m 2 ≤ (1 -ηmλ) J t/(mλ) + C5 m -2/3 log mL 7/2 t 5/3 λ -5/3 (1 + t/λ).

Next lemma shows the error bounds for Zt and Z t .

Lemma B.3. There exist constants { Ci } 5 i=1 > 0 such that for any δ > 0, if m satisfies that C1 m -3/2 L -3/2 [log(T KL 2 /δ)] 3/2 ≤ 2 t/(mλ) ≤ C2 L -6 [log m] -3/2 , ∀t ∈ [T ],

then with probability at least 1 -δ over the random initialization of θ 0 , we have the following inequalities for any t ∈ [T ]:

Z t F ≤ C3 tL, Zt -Z t F ≤ C4 m -1/6 log mL 4 t 7/6 λ -1/6 , log det( Zt ) det(λI) -log det(Z t ) det(λI) ≤ C5 m -1/6 log mL 4 t 5/3 λ -1/6 .

With above lemmas, we prove Lemma 6.2 as follows.

Proof of Lemma 6.2. By Lemma B.2 we know that θ t -θ 0 2 ≤ 2 t/(mλ). By Lemma 6.1, with probability at least 1 -δ, there exists θ * such that for any

1 ≤ t ≤ T , h(x t,at ) = g(x t,at ; θ 0 )/ √ m, √ m(θ * -θ 0 ) , √ m θ * -θ 0 2 ≤ √ 2h H -1 h ≤ S,

where the second inequality holds due to the choice of S. Thus, by Theorem 2 in Abbasi-Yadkori et al. (2011) , with probability at least 1 -2δ, for any

1 ≤ t ≤ T , θ * satisfies that √ m(θ * -θ 0 ) -Z-1 t bt Zt ≤ γt . (B.2)

We now prove that θ * -θ t Zt ≤ γ t / √ m. From the triangle inequality,

θ * -θ t Zt ≤ θ * -θ 0 -Z-1 t bt / √ m Zt I1 + θ t -θ 0 -Z-1 t bt / √ m Zt I2 . (B.3)

We bound I 1 and I 2 separately. For I 1 , we have

I 2 1 = (θ * -θ 0 -Z-1 t bt / √ m) Z t (θ * -θ 0 -Z-1 t bt / √ m) = (θ * -θ 0 -Z-1 t bt / √ m) Zt (θ * -θ 0 -Z-1 t bt / √ m) + (θ * -θ 0 -Z-1 t bt / √ m) (Z t -Zt )(θ * -θ 0 -Z-1 t bt / √ m) ≤ (θ * -θ 0 -Z-1 t bt / √ m) Zt (θ * -θ 0 -Z-1 t bt / √ m) + Z t -Zt 2 λ (θ * -θ 0 -Z-1 t bt / √ m) Zt (θ * -θ 0 -Z-1 t bt / √ m) ≤ (1 + Z t -Zt 2 /λ)γ 2 t /m, (B.4)

where the first inequality holds due to the fact that x Ax ≤ x Bx• A 2 /λ min (B) for some B 0 and the fact that λ min ( Zt ) ≥ λ, the second inequality holds due to (B.2). By Lemma B.3, we have

Zt -Z t 2 ≤ Zt -Z t F ≤ C 1 m -1/6 log mL 4 t 7/6 λ -1/6 , (B.5) and γt = ν log det Zt det λI -2 log δ + √ λS ≤ ν log det Z t det λI + C 2 m -1/6 log mL 4 t 5/3 λ -1/6 -2 log δ + √ λS, (B.6)

where C 1 , C 2 > 0 are two constants. Substituting (B.5) and (B.6) into (B.4), we have

I 1 ≤ 1 + Z t -Zt 2 /λγ t / √ m ≤ 1 + C 1 m -1/6 log mL 4 t 7/6 λ -7/6 / √ m • ν log det Z t det λI + C 2 m -1/6 log mL 4 t 5/3 λ -1/6 -2 log δ + √ λS . (B.7)

For I 2 , we have The proof starts with three lemmas that bound the error terms of the function value and gradient of neural networks. Lemma B.4 (Lemma 4.1, Cao and Gu (2019a)). There exist constants { Ci } 3 i=1 > 0 such that for any δ > 0, if τ satisfies that

I 2 ≤ C 3 tL θ t -θ 0 -Z-1 t bt / √ m 2 ≤ C 4 (1 -ηmλ) J t/(mλ) + m -2/3 log mL 7/2 t 5/3 λ -5/3 (1 + t/

C1 m -3/2 L -3/2 [log(T KL 2 /δ)] 3/2 ≤ τ ≤ C2 L -6 [log m] -3/2 ,

then with probability at least 1 -δ over the random initialization of θ 0 , for all θ, θ satisfying θθ 0 2 ≤ τ, θθ 0 2 ≤ τ and j ∈ [T K] we have 2019)). There exist constants { Ci } 3 i=1 > 0 such that for any δ ∈ (0, 1), if τ satisfies that

f (x j ; θ) -f (x j ; θ) -g(x j ; θ), θ -θ ≤ C3 τ 4/3 L 3 m log m.

C1 m -3/2 L -3/2 [log(T KL 2 /δ)] 3/2 ≤ τ ≤ C2 L -6 [log m] -3/2 ,

then with probability at least 1 -δ over the random initialization of θ 0 , for all θθ 0 2 ≤ τ and j ∈ [T K] we have g(x j ; θ) -g(x j ; θ 0 ) 2 ≤ C3 log mτ 1/3 L 3 g(x j ; θ 0 ) 2 . Lemma B.6 (Lemma B.3, Cao and Gu (2019a) ). There exist constants { Ci } 3 i=1 > 0 such that for any δ > 0, if τ satisfies that

C1 m -3/2 L -3/2 [log(T KL 2 /δ)] 3/2 ≤ τ ≤ C2 L -6 [log m] -3/2 ,

then with probability at least 1 -δ over the random initialization of θ 0 , for any θθ 0 2 ≤ τ and j ∈ [T K] we have g(x j ; θ) F ≤ C3 √ mL.

Proof of Lemma 6.3. We follow the regret bound analysis in Abbasi-Yadkori et al. (2011); Valko et al. (2013) . Denote a * t = argmax a∈[K] h(x t,a ) and C t = {θ : θθ t Zt ≤ γ t / √ m}. By Lemma 6.2, for all 1 ≤ t ≤ T , we have θ t -θ 0 2 ≤ 2 t/(mλ) and θ * ∈ C t . By the choice of m, Lemma B.4, B.5 and B.6 hold. Thus, h(x t,a * t ) -h(x t,at ) can be bounded as follows:

h(x t,a * t ) -h(x t,at ) = g(x t,a * t ; θ 0 ), θ * -θ 0 -g(x t,at ; θ 0 ), θ * -θ 0 ≤ g(x t,a * t ; θ t-1 ), θ * -θ 0 -g(x t,at ; θ t-1 ), θ * -θ 0 + θ * -θ 0 2 ( g(x t,a * t ; θ t-1 ) -g(x t,a * t ; θ 0 ) 2 + g(x t,at ; θ t-1 ) -g(x t,at ; θ 0 ) 2 ) ≤ g(x t,a * t ; θ t-1 ), θ * -θ 0 -g(x t,at ; θ t-1 ), θ * -θ 0 + C 1 √ h H -1 hm -1/6 log mt 1/6 λ -1/6 L 7/2 ≤ max θ∈Ct-1 g(x t,a * t ; θ t-1 ), θ -θ 0 -g(x t,at ; θ t-1 ), θ * -θ 0 + C 1 √ h H -1 hm -1/6 log mt 1/6 λ -1/6 L 7/2 , (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 to θ * ∈ C t-1 . Denote

U t,a = g(x t,a ; θ t-1 ), θ t-1 -θ 0 + γ t-1 g(x t,a ; θ t-1 ) Z -1 t-1 g(x t,a ; θ t-1 )/m, then we have U t,a = max θ∈Ct-1 g(x t,a ; θ t-1 ), θ -θ 0 with the fact that a, b + c √ a A -1 a = max x-b A ≤c a, x .

We also have

|U t,a -U t,a | ≤ C 2 m -1/6 log mt 2/3 λ -2/3 L 3 , (B.10)

where C 2 > 0 is a constant, the inequality holds due to Lemma B.4 with the fact θ t-1 -θ 0 2 ≤ 2 t/(mλ)) and the fact f (x j ; θ 0 ) = 0. Since θ * ∈ C t-1 , then (B.9) can be bounded as

max θ∈Ct-1 g(x t,a * t ; θ t-1 ), θ -θ 0 -g(x t,at ; θ t-1 ), θ * -θ 0 = U t,a * t -g(x t,at ; θ t-1 ), θ * -θ 0 ≤ U t,a * t -g(x t,at ; θ t-1 ), θ * -θ 0 + C 2 m -1/6 log mt 2/3 λ -2/3 L 3 ≤ U t,at -g(x t,at ; θ t-1 ), θ * -θ 0 + C 2 m -1/6 log mt 2/3 λ -2/3 L 3 ≤ U t,at -g(x t,at ; θ t-1 ), θ * -θ 0 + 2C 2 m -1/6 log mt 2/3 λ -2/3 L 3 , (B.11)

where the first inequality holds due to (B.10), the second inequality holds since a t = argmax a U t,a , the third inequality holds due to (B.10). Furthermore,

U t,at -g(x t,at ; θ 0 ), θ * -θ 0 = max θ∈Ct-1 g(x t,at ; θ t-1 ), θ -θ 0 -g(x t,at ; θ t-1 ), θ * -θ 0 = max θ∈Ct-1 g(x t,at ; θ t-1 ), θ -θ t-1 -g(x t,at ; θ t-1 ), θ * -θ t-1 ≤ max θ∈Ct-1 θ -θ t-1 Zt-1 g(x t,at ; θ t-1 ) Z -1 t-1 + θ * -θ t-1 Zt-1 g(x t,at ; θ t-1 ) Z -1 t-1 ≤ 2γ t-1 g(x t,at ; θ t-1 )/ √ m Z -1 t-1 , (B.12)

where the first inequality holds due to Cauchy-Schwarz inequality, the second inequality holds due to Lemma 6.2. Combining (B.9), (B.11) and (B.12), we have

h(x t,a * t ) -h(x t,at ) ≤ 2γ t-1 g(x t,at ; θ t-1 )/ √ m Z -1 t-1 + C 1 √ h H -1 hm -1/6 log mt 1/6 λ -1/6 L 7/2 + 2C 2 m -1/6 log mt 2/3 λ -2/3 L 3 ≤ min 2γ t-1 g(x t,at ; θ t-1 )/ √ m Z -1 t-1 + C 1 √ h H -1 hm -1/6 log mt 1/6 λ -1/6 L 7/2 + 2C 2 m -1/6 log mt 2/3 λ -2/3 L 3 , 1 ≤ min 2γ t-1 g(x t,at ; θ t-1 )/ √ m Z -1 t-1 , 1 + C 1 √ h H -1 hm -1/6 log mt 1/6 λ -1/6 L 7/2 + 2C 2 m -1/6 log mt 2/3 λ -2/3 L 3 ≤ 2γ t-1 min g(x t,at ; θ t-1 )/ √ m Z -1 t-1 , 1 + C 1 √ h H -1 hm -1/6 log mt 1/6 λ -1/6 L 7/2

+ 2C 2 m -1/6 log mt 2/3 λ -2/3 L 3 , (B.13) where the second inequality holds due to the fact that 0 ≤ h(x t,a * t ) -h(x t,at ) ≤ 1, the third inequality holds due to the fact that min{a + b, 1} ≤ min{a, 1} + b, the fourth inequality holds due to the fact γ t-1 ≥ √ λS ≥ 1. Finally, by the fact that √ 2hH -1 h ≤ 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. ( 2011). Lemma B.7 (Lemma 11, Abbasi-Yadkori et al. ( 2011)). We have the following inequality:

T t=1 min g(x t,at ; θ t-1 )/ √ m 2 Z -1 t-1 , 1 ≤ 2 log det Z T det λI .

Proof of Lemma 6.4. First by the definition of γ t , we know that γ t is a monotonic function w.r.t. det Z t . By the definition of Z t , we know that Z T Z t , which implies that det Z t ≤ det Z T . Thus, γ t ≤ γ T . Second, by Lemma B.7 we know that

T t=1 min g(x t,at ; θ t-1 )/ √ m 2 Z -1 t-1 , 1 ≤ 2 log det Z T det λI ≤ 2 log det ZT det λI + C 1 m -1/6 log mL 4 T 5/3 λ -1/6 , (B.14)

where the second inequality holds due to Lemma B.3. Next we are going to bound log det ZT .

Denote G = [g(x 1 ; θ 0 )/ √ m, . . . , g(x T K ; θ 0 )/ √ m] ∈ R p×(T K) , then we have log det ZT det λI = log det I + T t=1

g(x t,at ; θ 0 )g(x t,at ; θ 0 ) /(mλ)

≤ log det I + T K i=1 g(x i ; θ 0 )g(x i ; θ 0 ) /(mλ) = log det I + GG /λ = log det I + G G/λ , (B.15)

where the inequality holds naively, the third equality holds since for any matrix A ∈ R p×T K , we have det(I + AA ) = det(I + A A). We can can be further bound (B.15) by the follows:

log det I + G G/λ = log det I + H/λ + (G G -H)/λ ≤ log det I + H/λ + (I + H/λ) -1 , (G G -H)/λ ≤ log det I + H/λ + (I + H/λ) -1 F G G -H F /λ ≤ log det I + H/λ + √ T K G G -H F ≤ log det I + H/λ + 1 ≤ d log(1 + T K/λ) + 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 ≤ A F B F , the third inequality holds due to the facts that I + H/λ I, λ ≥ 1 and A F ≤ √ T K A 2 for any A ∈ R T K×T K , 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 5.3, and the last inequality holds due to the choice of λ. We now bound γ T , which is

γ T = 1 + C 1 m -1/6 log mL 4 T 7/6 λ -7/6 • ν log det Z T det λI + C 2 m -1/6 log mL 4 T 5/3 λ -1/6 -2 log δ + √ λS + C 3 (1 -ηmλ) J T /(mλ) + m -2/3 log mL 7/2 T 5/3 λ -5/3 (1 + T /λ) ≤ 1 + C 1 m -1/6 log mL 4 T 7/6 λ -7/6 • ν log det ZT det λI + C 2 m -1/6 log mL 4 T 5/3 λ -1/6 -2 log δ + √ λS + C 3 (1 -ηmλ) J T /(mλ) + m -2/3 log mL 7/2 T 5/3 λ -5/3 (1 + T /λ) , (B.17)

where the inequality holds due to Lemma B.3. Finally, substituting (B.15), (B.16) into (B.14), using (B.14) and (B.17), we have

T t=1 γ 2 t-1 min g(x t,at ; θ t-1 )/ √ m 2 Z -1 t-1 , 1 ≤ γ T T t=1 min g(x t,at ; θ t-1 )/ √ m 2 Z -1 t-1 , 1 ≤ log det ZT det λI + C 1 m -1/6 log mL 4 T 5/3 λ -1/6 1 + C 1 m -1/6 log mL 4 T 7/6 λ -7/6

• ν log det ZT det λI + C 2 m -1/6 log mL 4 T 5/3 λ -1/6 -2 log δ + √ λS , then for any i, j ∈ [T K], with probability at least 1 -δ over random initialization of θ 0 , we have

+ C 3 (1 -ηmλ) J T /(mλ) + m -3/2 log mL 7/2 T 5/3 λ -5/3 (1 + T /λ) ≤ d log(1 + T K/λ) + 1 + C 1 m -1/6 log mL 4 T 5/3 λ -1/6 1 + C 1 m -1/6 log mL 4 T 7/6 λ -7/6 • ν d log(1 + T K/λ) + 1 + C 2 m -1/6 log mL 4 T 5/3 λ -1/6 -2 log δ + √ λS + C 3 (1 -ηmλ) J T /(mλ) + m -3/2 log mL 7/2 T 5/3 λ -5/3 (1 + T /λ) .

C PROOFS OF TECHNICAL LEMMAS:

| g(x i ; θ 0 ), g(x j ; θ 0 ) /m -H i,j | ≤ . (C.1)

Proof of Lemma B.1. Taking union bound over i, j ∈ [T K], we have that if

m = Ω L 6 log(T 2 K 2 L/δ) 4 ,

then with probability at least 1 -δ, (C.1) holds for all (i, j)

∈ [T K] × [T K]. Therefore, we have G G -H F = T K i=1 T K j=1 | g(x i ; θ 0 ), g(x j ; θ 0 ) /m -H i,j | 2 ≤ T K . 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 t by default. We define the following quantities: J (j) = g(x 1,a1 ; θ (j) ), . . . , g(x t,at ; θ (j) ) ∈ R (md+m 2 (L-2)+m)×t ,

H (j) = [J (j) ] J (j) ∈ R t×t , f (j) = (f (x 1,a1 ; θ (j) ), . . . , f (x t,at ; θ (j) )) ∈ R t×1 , v = (r 1,a1 , . . . , r t,at ) ∈ R t×1 .

Then the update rule of θ (j) can be written as follows:

θ (j+1) = θ (j) -η J (j) (f (j) -v) + mλ(θ (j) -θ (0) ) . (C.2)

We also define the following auxiliary sequence { θ (k) } during the proof:

θ (0) = θ (0) , θ (j+1) = θ (j) -η J (0) ([J (0) ] ( θ (j) -θ (0) ) -v) + mλ( θ (j) -θ (0) ) .

Next lemma provides perturbation bounds for J (j) , H (j) and f (j+1) -f (j) -[J (j) ] (θ (j+1)θ (j) ) 2 . Lemma C.2. There exist constants { Ci } 6 i=1 > 0 such that for any δ > 0, if τ satisfies that

C1 m -3/2 L -3/2 [log(T KL 2 /δ)] 3/2 ≤ τ ≤ C2 L -6 [log m] -3/2 ,

then with probability at least 1 -δ over the random initialization of θ (0) , if for any j ∈ [J], θ (j)θ (0) 2 ≤ τ , we have the following inequalities for any j ∈ [J],

J (j) F ≤ C4 √ tmL, (C.3) J (j) -J (0) F ≤ C5 tm log mτ 1/3 L 7/2 , (C.4) f (j+1) -f (j) -[J (j) ] (θ (j+1) -θ (j) ) 2 ≤ C6 τ 4/3 L 3 tm log m, (C.5) v 2 ≤ √ t. (C.6)

Next lemma gives an upper bound for f (j) -v 2 . Lemma C.3. There exist constants { Ci } 4 i=1 > 0 such that for any δ > 0, if τ, η satisfy that

C1 m -3/2 L -3/2 [log(T KL 2 /δ)] 3/2 ≤ τ ≤ C2 L -6 [log m] -3/2 , , η ≤ C3 (mλ + tmL) -1 , τ 8/3 ≤ C4 m(λη) 2 L -6 t -1 (log m) -1 ,

then with probability at least 1 -δ over the random initialization of θ (0) , if for any j ∈ [J], θ (j)θ (0) 2 ≤ τ , we have that for any j ∈

[J], f (j) -v 2 ≤ 2 √ t.

Next lemma gives an upper bound of the distance between auxiliary sequence θ (j) -θ (0) 2 . Lemma C.4. There exist constants { Ci } 3 i=1 > 0 such that for any δ ∈ (0, 1), if τ, η satisfy that

C1 m -3/2 L -3/2 [log(T KL 2 /δ)] 3/2 ≤ τ ≤ C2 L -6 [log m] -3/2 , , η ≤ C3 (tmL + mλ) -1 ,

then with probability at least 1 -δ, we have that for any j ∈ [J],

θ (j) -θ (0) 2 ≤ t/(mλ), θ (j) -θ (0) -( Z) -1 b/ √ m 2 ≤ (1 -ηmλ) J t/(mλ)

With above lemmas, we prove Lemma B.2 as follows.

Proof of Lemma B.2. Set τ = 2 t/(mλ). First we assume that θ (j) -θ (0) 2 ≤ τ for all 0 ≤ j ≤ J. Then with this assumption and the choice of m, τ , we have that Lemma C.2, C.3 and C.4 hold. Then we have θ

(j+1) -θ (j+1) 2 = θ (j) -θ (j) -η(J (j) -J (0) )(f (j) -v) -ηmλ(θ (j) -θ (j) ) -ηJ (0) (f (j) -[J (0) ] ( θ (j) -θ (0) )) 2 = (1 -ηmλ)(θ (j) -θ (j) ) -η(J (j) -J (0) )(f (j) -v) -ηJ (0) f (j) -[J (0) ](θ (j) -θ (0) ) + [J (0) ] (θ (j) -θ (j) ) 2 ≤ I -η(mλI + H (0) ) ( θ (j) -θ (j) ) 2 + η (J (j) -J (0) )(f (j) -v) 2 + η J (0) 2 f (j) -[J (0) ](θ (j) -θ (0) ) 2 ≤ (1 -ηmλ) θ (j) -θ (j) 2 + η (J (j) -J (0) )(f (j) -v) 2 I1 + η J (0) 2 f (j) -[J (0) ](θ (j) -θ (0) ) 2 I2 , (C.7)

where the first inequality holds due to triangle inequality, the second inequality holds due to the fact that ηH (0) = η[J (0) ] J (0) C 1 tmLηI ≤ I with (C.3) in Lemma C.2 for some C 1 > 0. We now bound I 1 , I 2 separately. For I 1 , we have

I 1 ≤ η J (j) -J (0) 2 f (j) -v 2 ≤ ηC 2 t m log mτ 1/3 L 7/2 , (C.8

) where C 2 > 0 is a 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 I 2 , we have

I 2 ≤ η J (0) 2 f (j) -J (0) (θ (j) -θ (0) ) 2 ≤ ηC 3 tmL 7/2 τ 4/3 log m, (C.9)

where C 3 > 0, the first inequality holds due to matrix spectral norm, the second inequality holds due to (C.3) and (C.5) in Lemma C.2 and the fact that f (0) = 0 by random initialization over θ (0) . Substituting (C.8) and (C.9) into (C.7), we have

θ (j+1) -θ (j+1) 2

≤ (1 -ηmλ) θ (j) -θ (j) 2 + C 4 ηt m log mτ 1/3 L 7/2 + ηtmL 7/2 τ 4/3 log m , (C.10) where C 4 > 0 is a constant. Expanding (C.10) for k times, we have

θ (j+1) -θ (j+1) 2 ≤ C 4 ηt √ m log mτ 1/3 L 7/2 + ηtmL 7/2 τ 4/3 √ log m ηmλ = C 5 m -2/3 log mL 7/2 t 5/3 λ -5/3 (1 + t/λ) ≤ τ 2 , (C.11)

where C 5 > 0 is a constant, the equality holds by the definition of τ , the last inequality holds due to the choice of m, where m 1/6 ≥ C 6 log mL 7/2 t 7/6 λ -7/6 (1 + t/λ), C 6 > 0 is a constant. Thus, for any j ∈ [J], we have

EQUATION

C.12) where the first inequality holds due to triangle inequality, the second inequality holds due to Lemma C.4. (C.13) suggests that our assumption θ (j) -θ (0) 2 ≤ τ holds for any u. Note that we have the following inequality by Lemma C.4:

θ (j) -θ (0) -( Z) -1 b/ √ m 2 ≤ (1 -ηmλ) j t/(mλ).

(C.13) Using (C.11) and (C.13), we have

θ (j) -θ (0) -( Z) -1 b/ √ m 2

≤ (1 -ηmλ) J t/(mλ) + C 5 m -2/3 log mL 7/2 t 5/3 λ -5/3 (1 + t/λ). This completes the proof.

C.3 PROOF OF LEMMA B.3:

In this section we prove Lemma B.3.

Proof of Lemma B.3. Set τ = 2 t/(mλ). By Lemma 6.2, we have that θ i -θ 0 2 ≤ τ for i ∈ [t]. Z t F can be bounded as follows.

Z t F = t i=1 g(x i,ai ; θ i )g(x i,ai ; θ i ) /m F ≤ t i=1 g(x i,ai ; θ i ) 2 2 /m ≤ C 0 tL,

where C 0 > 0 is a constant, the first inequality holds due to the fact that aa F = a 2 2 , the second inequality holds due to Lemma B.6 with the fact that θ i -θ 0 2 ≤ τ . We bound Z t -Zt 2 as follows. We have

Z t -Zt F = t i=1 g(x i,ai ; θ 0 )g(x i,ai ; θ 0 ) -g(x i,ai ; θ i )g(x i,ai ; θ i ) /m F ≤ t i=1 g(x i,ai ; θ 0 )g(x i,ai ; θ 0 ) -g(x i,ai ; θ i )g(x i,ai ; θ i ) F /m ≤ t i=1 g(x i,ai ; θ 0 ) 2 + g(x i,ai ; θ i ) 2 g(x i,ai ; θ 0 ) -g(x i,ai ; θ i ) 2 /m, (C.14)

where the first inequality holds due to triangle inequality, the second inequality holds the fact that aabb F ≤ ( a 2 + b 2 ) ab 2 for any vectors a, b. To bound (C.14), we have

g(x i,ai ; θ 0 ) 2 , g(x i,ai ; θ i ) 2 ≤ C 1 √ mL, (C.15)

where C 1 > 0 is a constant, the inequality holds due to Lemma B.6 with the fact that θ i -θ 0 2 ≤ τ . We also have

g(x i,ai ; θ 0 ) -g(x i,ai ; θ i ) 2 ≤ C 2 log mτ 1/3 L 3 g(x j ; θ 0 ) 2 ≤ C 3 m log mτ 1/3 L 7/2 , (C.16)

where C 2 , C 3 > 0 are constants, the first inequality holds due to Lemma B.5 with the fact that θ i -θ 0 2 ≤ τ , the second inequality holds due to Lemma B.6. Substituting (C.15) and (C.16) into (C.14), we have

Z t -Zt F ≤ C 4 t log mτ 1/3 L 4 ,

where C 4 > 0 is a constant. We now bound log det Zt -log det Z t . It is easy to verify that Zt = λI + J[ J] , Z t = λI + JJ , where

J = g(x 1,a1 ; θ 0 ), . . . , g(x t,at ; θ 0 ) / √ m, J = g(x 1,a1 ; θ 0 ), . . . , g(x t,at ; θ t-1 ) / √ m.

We have the following inequalities:

log det( Zt ) det(λI) -log det(Z t ) det(λI) = log det(I + J[ J] /λ) -log det(I + J[J] /λ) = log det(I + [ J] J/λ) -log det(I + [J] J/λ) ≤ (I + [J] J/λ) -1 , [ J] J -[J] J ≤ (I + [J] J/λ) -1 F [ J] J -[J] J F ≤ √ t (I + [J] J/λ) -1 2 [ J] J -[J] J F ≤ √ t [ J] J -[J] J F , (C.17)

where the second equality holds due to the fact that det(I + AA ) = det(I + A A), 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 F B F , the third inequality holds since I + [J] J/λ is a t-dimension matrix, the fourth inequality holds since I + [J] J/λ I. We have

[ J] J -[J] J F ≤ t max 1≤i,j≤t g(x i,ai ; θ 0 ) g(x j,aj ; θ 0 ) -g(x i,ai ; θ i ) g(x j,aj ; θ j ) /m ≤ t max 1≤i,j≤t g(x i,ai ; θ 0 ) -g(x i,ai ; θ i ) 2 g(x j,aj ; θ j ) 2 /m + g(x j,aj ; θ 0 ) -g(x j,aj ; θ j ) 2 g(x i,ai ; θ 0 ) 2 /m ≤ C 5 t log mτ 1/3 L 4 , (C.18)

where C 5 > 0 is a constant, the first inequality holds due to the fact that A F ≤ t max |A i,j | for any A ∈ R t×t , the second inequality holds due to the fact |a a Using the same method, we also have

-b b | ≤ a -b 2 b 2 + a - b 2 a 2 ,

log det(Z t ) det(λI) -log det( Zt ) det(λI) ≤ C 5 t 3/2 log mτ 1/3 L 4 .

This completes our proof.

D PROOFS OF LEMMAS IN APPENDIX C:

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 ∈ [J], the following inequalities hold. We first have

J (j) F ≤ √ t max i∈[t] g(x i,ai ; θ (j) ) 2 ≤ C 1 √ tmL, (D.1)

where C 1 > 0 is a constant, the first inequality holds due to the definition of J (j) , the second inequality holds due to Lemma B.6. We also have

J (j) -J (0) F ≤ C 2 log mτ 1/3 L 3 J (0) F ≤ C 3 tm log mτ 1/3 L 7/2 , (D.2)

where C 2 , C 3 > 0 are constants, the first inequality holds due to Lemma B.5 with the assumption that θ (j) -θ (0) 2 ≤ τ , the second inequality holds due to (D.1). We also have

f (j+1) -f (j) -[J (j) ] (θ (j+1) -θ (j) ) 2 ≤ max i∈[t] √ t f (x i,ai ; θ (j+1) ) -f (x i,ai ; θ (j) ) -g(x i,ai ; θ (j) ), θ (j+1) -θ (j) ≤ C 4 τ 4/3 L 3 tm log m,

where C 4 > 0 is a constant, the first inequality holds due to the the fact that x 2 ≤ √ t max |x i | for any x ∈ R t , the second inequality holds due to Lemma B.4 with the assumption that θ

EQUATION

where e = f (θ ) -f (θ) -J(θ) (θ -θ). I 1 can be bounded as follows: ≤ mλη(L(θ ) -L(θ)/2) + e 2 2 (1 + 4mλη + 4/(mλη)), (D.8) where the second inequality holds due to the choice of η, third inequality holds due to Young's inequality, fourth inequality holds due to the fact that f (θ) -v 2 2 ≤ 2L(θ). Now taking θ = θ (j) and θ = θ (0) , rearranging (D.8), with the fact that θ (j+1) = θ (j) -η∇L(θ (j) ), we have L(θ (j+1) ) -L(θ (0) )

I 1 ≤ f (θ) -v

≤ (1 -mλη/2)[L(θ (j) ) -L(θ (0) )] + mλη/2L(θ (0) ) + e 2 2 (1 + 4mλη + 4/(mλη)) ≤ (1 -mλη/2)[L(θ (j) ) -L(θ (0) )] + mλη/2 • t + mλη/2 • t ≤ (1 -mλη/2)[L(θ (j) ) -L(θ (0) )] + mληt, (D.9)

where the second inequality holds due to the fact that L(θ (0) ) = f (θ (0) ) -v 2 2 /2 = v 2 2 /2 ≤ t, and

(1 + 4mλη + 4/(mλη)) e 2 2 ≤ 5/(mλη) • C 2 τ 8/3 L 6 tm log m ≤ tmλη/2, (D.10) where the first inequality holds due to (C.5) in Lemma C.2, the second inequality holds due to the choice of τ . Expanding (D.9) u times, we have L(θ (j+1) ) -L(θ (0) ) ≤ mληt mλη/2 = 2t, which implies that f (j+1) -v 2 ≤ 2 √ t. 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 θ (j) is the sequence generated by applying gradient descent on the following problem: 0) ] (θ -θ (0) ) -v 2 2 + mλ 2 θθ (0) 2 2 . Then θ (0) -θ (j) 2 can be bounded as

EQUATION

mλ 2 θ (0) -θ (j) 2 2 ≤ 1 2 [J (0) ] ( θ (j) -θ (0) ) -v 2 2 + mλ 2 θ (j) -θ (0) 2 2 ≤ 1 2 [J (0) ] ( θ (0) -θ (0) ) -v 2 2 + mλ 2 θ (0) -θ (0) 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 C.2. It is easy to verify that L is a λ-strongly convex and function and C 1 (tmL + mλ)-smooth function, since ∇ 2 L J (0) 2 2 + mλ I C 1 (tmL + mλ), where the first inequality holds due to the definition of L, the second inequality holds due to (C.3) in Lemma C.2. Since we choose η ≤ C 2 (tmL + mλ) -1 for some small enough C 2 > 0, then by standard result of gradient descent on ridge linear regression, θ (j) converges to θ (0) + ( Z) -1 b/ √ m with the convergence rate

θ (j) -θ (0) -( Z) -1 b/ √ m 2 ≤ (1 -ηmλ) J f (0) -v 2 /

√ mλ ≤ (1 -ηmλ) J t/(mλ).

E A VARIANT OF NEURALUCB:

In this section, we present a variant of NeuralUCB called NeuralUCB 0 . Compared with Algorithm 1, the main differences between NeuralUCB and NeuralUCB 0 are as follows: NeuralUCB uses gradient descent to train a deep neural network to learn the reward function h(x) based on observed contexts and rewards. In contrast, NeuralUCB 0 uses matrix inversions to obtain parameters in closed forms. At each round, NeuralUCB uses the current DNN parameters (θ t ) to compute an upper confidence bound. In contrast, NeuralUCB 0 computes the UCB using the initial parameters (θ 0 ). Algorithm 3 NeuralUCB 0 1: Input: number of rounds T , regularization parameter λ, exploration parameter ν, confidence parameter δ, norm parameter S, network width m, network depth L 2: Initialization: Generate each entry of W l independently from N (0, 2/m) for 1 ≤ l ≤ L -1, and each entry of W L independently from N (0, 1/m). Define φ(x) = g(x; θ 0 )/ √ m, where θ 0 = [vec(W 1 ) , . . . , vec(W L ) ] ∈ R p 3: Z 0 = λI, b 0 = 0 4: for t = 1, . . . , T do 5:

Observe {x t,a } K a=1 and compute 

(

:



Figures and Tables:

Input: Number of rounds T , regularization parameter λ, exploration parameter ν, confidence parameter δ, norm parameter S, step size η, number of gradient descent steps J, network width m, network depth L. 2: Initialization: Randomly initialize θ 0 as described in the text 3: Initialize Z 0 = λI, b 0 = 0 4: for t = 1, . . . , T do

Figure 1: Comparison of LinUCB, Neural -Greedy and NeuralUCB.

Theorem 5, Allen-Zhu et al. (

IN APPENDIX B C.1 PROOF OF 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 > 0 and δ ∈ (0, 1). Suppose that m = Ω L 6 log(L/δ) 4

inequality holds due to Cauchy-Schwarz inequality, the second inequality holds due to the fact that J(θ) 2 ≤ C 2 √ tmL with θθ (0) 2 ≤ τ by (C.3) in Lemma C.2. Substituting (D.4) into (D.3), we have L(θ ) -L(θ) ≤ ∇L(θ), θθ + C 1 2 (mλ + tmL) θθ 2 2 + f (θ) -v 2 e 2 + e 2 2 . (D.5)Taking θ = θ -η∇L(θ), then by (D.5), we haveL(θ -η∇L(θ)) -L(θ) ≤ -η ∇L(θ) 2 2 (1 -C 1 (mλ + tmL)η) + f (θ) -v 2 e 2 + e 2 2 . (D.6) By the 1-strongly convexity of • 2 2 , we further have L(θ ) -L(θ) ≥ f (θ) -v, f (θ ) -f (θ) + mλ θθ (0) , θf (θ) -v, [J(θ)] (θ -θ) + e + mλ θθ (0) , θ -∇L(θ), θθ + mλ 2 θθ 2 2 + f (θ) -v, e ≥ ∇L(θ), θθ + mλ 2 θθ 2 2 -f (θ) -v 2 e 2 ≥ -∇L(θ) 2 2 2mλ -f (θ) -v 2 e 2 , (D.7)where the second inequality holds due to Cauchy-Schwarz inequality, the last inequality holds due to the fact that a, x + c x 2 2 ≥ -a 2 2 /(4c) for any vectors a, x and c > 0. Substituting (D.7) into (D.6), we haveL(θ -η∇L(θ)) -L(θ) ≤ 2mλη(1 -C 1 (mλ + tmL)η) L(θ ) -L(θ) + f (θ) -v 2 e 2 + f (θ) -v 2 e 2 + e 2 2 ≤ mλη L(θ ) -L(θ) + f (θ) -v 2 e 2 + f (θ) -v 2 e 2 + e 2 2 ≤ mλη L(θ ) -L(θ) + f (θ) -v 2 2 /8 + 4 e 2 2 + mλη f (θ) -v 2 2 /8 + 4 e 2 2 /(mλη) + e 2 2

L)), the regret bound (5.2) becomes R T = O dT max{ d, h H -1 h} . Specifically, suppose h belongs to a RKHS H induced by NTK and it can be represented by h(x) = ψ(x), β * , where ψ(x) is the feature mapping induced by NTK, for some β * in H(Valko et al., 2013). Then we can show that h H = β * 2 ≥ √ h H -1 h; see Appendix A.2 for more details. Thus our regret bound can be further written as R T = O dT max{ d, h H } .

Table content: <table><tr><td>tion error is dominated by Remark 5.8. Treating ν and λ as constants, and taking S = √ λS. log(λS/ √ T )/(λ/(T</td><td>and therefore the optimiza-√ 2h H -1 h and J =</td></tr></table>

a t , θ t,at ) = argmax Zt ≤ γ t }, where γ t = ν log det Z t

Table content: <table><tr><td colspan="2">φ(x t,a ), θ -θ 0</td><td/><td>(E.1)</td></tr><tr><td>a∈[K],θ∈Ct-1</td><td/><td/><td/></tr><tr><td/><td>√</td><td/><td/></tr><tr><td>det λI</td><td>-2 log δ +</td><td>λS</td><td>(E.2)</td></tr></table>

Peer review (iclr2020):
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. While 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. The 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? Other comment: 1. It should be explicitly stated somewhere in the paper that x_{t,k} are assumed to be deterministic. Thus 	heta^* is deterministic. It is more important that 	heta^* does NOT depends on a_t. Otherwise lemma 6.2 could be problematic. ===================== Based on the new version of the paper and the discussions, I change the score to weak accept.