Year: 2021

Abstract:
Thompson Sampling (TS) is one of the most effective algorithms for solving contextual multi-armed bandit problems. In this paper, we propose a new algorithm, called Neural Thompson Sampling, which adapts deep neural networks for both exploration and exploitation. At the core of our algorithm is a novel posterior distribution of the reward, where its mean is the neural network approximator, and its variance is built upon the neural tangent features of the corresponding neural network. We prove that, provided the underlying reward function is bounded, the proposed algorithm is guaranteed to achieve a cumulative regret of O(T ), which matches the regret of other contextual bandit algorithms in terms of total round number T . Experimental comparisons with other benchmark bandit algorithms on various data sets corroborate our theory.

heading: 1 INTRODUCTION
text: The stochastic multi-armed bandit (Bubeck & Cesa-Bianchi, 2012; Lattimore & Szepesvári, 2020) has been extensively studied, as an important model to optimize the trade-off between exploration and exploitation in sequential decision making. Among its many variants, the contextual bandit is widely used in real-world applications such as recommendation (Li et al., 2010), advertising (Graepel et al., 2010), robotic control (Mahler et al., 2016), and healthcare (Greenewald et al., 2017).
In each round of a contextual bandit, the agent observes a feature vector (the “context”) for each of the K arms, pulls one of them, and in return receives a scalar reward. The goal is to maximize the cumulative reward, or minimize the regret (to be defined later), in a total of T rounds. To do so, the agent must find a trade-off between exploration and exploitation. One of the most effective and widely used techniques is Thompson Sampling, or TS (Thompson, 1933). The basic idea is to compute the posterior distribution of each arm being optimal for the present context, and sample an arm from this distribution. TS is often easy to implement, and has found great success in practice (Chapelle & Li, 2011; Graepel et al., 2010; Kawale et al., 2015; Russo et al., 2017).
Recently, a series of work has applied TS or its variants to explore in contextual bandits with neural network models (Blundell et al., 2015; Kveton et al., 2020; Lu & Van Roy, 2017; Riquelme et al., 2018). Riquelme et al. (2018) proposed NeuralLinear, which maintains a neural network and chooses the best arm in each round according to a Bayesian linear regression on top of the last network layer. Kveton et al. (2020) proposed DeepFPL, which trains a neural network based on perturbed training data and chooses the best arm in each round based on the neural network output. Similar approaches have also been used in more general reinforcement learning problem (e.g., Azizzadenesheli et al., 2018; Fortunato et al., 2018; Lipton et al., 2018; Osband et al., 2016a). Despite the reported empirical success, strong regret guarantees for TS remain limited to relatively simple models, under fairly restrictive assumptions on the reward function. Examples are linear
functions (Abeille & Lazaric, 2017; Agrawal & Goyal, 2013; Kocák et al., 2014; Russo & Van Roy, 2014), generalized linear functions (Kveton et al., 2020; Russo & Van Roy, 2014), or functions with small RKHS norm induced by a properly selected kernel (Chowdhury & Gopalan, 2017).
In this paper, we provide, to the best of our knowledge, the first near-optimal regret bound for neural network-based Thompson Sampling. Our contributions are threefold. First, we propose a new algorithm, Neural Thompson Sampling (NeuralTS), to incorporate TS exploration with neural networks. It differs from NeuralLinear (Riquelme et al., 2018) by considering weight uncertainty in all layers, and from other neural network-based TS implementations (Blundell et al., 2015; Kveton et al., 2020) by sampling the estimated reward from the posterior (as opposed to sampling parameters). Second, we give a regret analysis for the algorithm, and obtain an Õ(d̃ √ T ) regret, where d̃ is the effective dimension and T is the number of rounds. This result is comparable to previous bounds when specialized to the simpler, linear setting where the effective dimension coincides with the feature dimension (Agrawal & Goyal, 2013; Chowdhury & Gopalan, 2017).
Finally, we corroborate the analysis with an empirical evaluation of the algorithm on several benchmarks. Experiments show that NeuralTS yields competitive performance, in comparison with stateof-the-art baselines, thus suggest its practical value in addition to strong theoretical guarantees.
Notation: Scalars and constants are denoted by lower and upper case letters, respectively. Vectors are denoted by lower case bold face letters x, and matrices by upper case bold face letters A. We denote by [k] the set {1, 2, · · · , k} for positive integers k. For two non-negative sequence {an}, {bn}, an = O(bn) means that there exists a positive constant C such that an ≤ Cbn, and we use Õ(·) to hide the log factor inO(·). We denote by ‖ · ‖2 the Euclidean norm of vectors and the spectral norm of matrices, and by ‖ · ‖F the Frobenius norm of a matrix.

heading: 2 PROBLEM SETTING AND PROPOSED ALGORITHM
text: In this work, we consider contextualK-armed bandits, where the total number of rounds T is known. At round t ∈ [T ], the agent observes K contextual vectors {xt,k ∈ Rd | k ∈ [K]}. Then the agent selects an arm at and receives a reward rt,at . Our goal is to minimize the following pseudo regret:
RT = E [ T∑ t=1 (rt,a∗t − rt,at) ] , (2.1)
where a∗t is the optimal arm at round t that has the maximum expected reward: a ∗ t = argmaxa∈[K] E[rt,a]. To estimate the unknown reward given a contextual vector x, we use a fully connected neural network f(x;θ) of depth L ≥ 2, defined recursively by
f1 = W1 x,
fl = Wl ReLU(fl−1), 2 ≤ l ≤ L, f(x;θ) = √ mfL, (2.2)
where ReLU(x) := max{x, 0},m is the width of neural network, W1 ∈ Rm×d,Wl ∈ Rm×m, 2 ≤ l < L, WL ∈ R1×m, θ = (vec(W1); · · · ; vec(WL)) ∈ Rp is the collection of parameters of the neural network, p = dm + m2(L − 2) + m, and g(x;θ) = ∇θf(x;θ) is the gradient of f(x;θ) w.r.t. θ.
Our Neural Thompson Sampling is given in Algorithm 1. It maintains a Gaussian distribution for each arm’s reward. When selecting an arm, it samples the reward of each arm from the reward’s posterior distribution, and then pulls the greedy arm (lines 4–8). Once the reward is observed, it updates the posterior (lines 9 & 10). The mean of the posterior distribution is set to the output of the neural network, whose parameter is the solution to the following minimization problem:
min θ L(θ) = t∑ i=1 [f(xi,ai ;θ)− ri,ai ]2/2 +mλ‖θ − θ0‖22/2. (2.3)
We can see that (2.3) is an `2-regularized square loss minimization problem, where the regularization term centers at the randomly initialized network parameter θ0. We adapt gradient descent to solve (2.3) with step size η and total number of iterations J .
Algorithm 1 Neural Thompson Sampling (NeuralTS) Input: Number of rounds T , exploration variance ν, network width m, regularization parameter λ.
1: Set U0 = λI 2: Initialize θ0 = (vec(W1); · · · ; vec(WL)) ∈ Rp, where for each 1 ≤ l ≤ L − 1,
Wl = (W,0; 0,W), each entry of W is generated independently from N(0, 4/m); WL = (w>,−w>), each entry of w is generated independently from N(0, 2/m).
3: for t = 1, · · · , T do 4: for k = 1, · · · ,K do 5: σ2t,k = λg >(xt,k;θt−1) U −1 t−1 g(xt,k;θt−1)/m 6: Sample estimated reward r̃t,k ∼ N (f(xt,k;θt−1), ν2σ2t,k) 7: end for 8: Pull arm at and receive reward rt,at , where at = argmaxa r̃t,a 9: Set θt to be the output of gradient descent for solving (2.3)
10: Ut = Ut−1 + g(xt,at ;θt)g(xt,at ;θt) >/m 11: end for
A few observations about our algorithm are in place. First, compared to typical ways of implementing Thompson Sampling with neural networks, NeuralTS samples from the posterior distribution of the scalar reward, instead of the network parameters. It is therefore simpler and more efficient, as the number of parameters in practice can be large.
Second, the algorithm maintains the posterior distributions related to parameters of all layers of the network, as opposed to the last layer only (Riquelme et al., 2018). This difference is crucial in our regret analysis. It allows us to build a connection between Algorithm 1 and recent work about deep learning theory (Allen-Zhu et al., 2018; Cao & Gu, 2019), in order to obtain theoretical guarantees as will be shown in the next section.
Third, different from linear or kernelized TS (Agrawal & Goyal, 2013; Chowdhury & Gopalan, 2017), whose posterior can be computed in closed forms, NeuralTS solves a non-convex optimization problem (2.3) by gradient descent. This difference requires additional techniques in the regret analysis. Moreover, stochastic gradient descent can be used to solve the optimization problem with a similar theoretical guarantee (Allen-Zhu et al., 2018; Du et al., 2018; Zou et al., 2019). For simplicity of exposition, we will focus on the exact gradient descent approach.

heading: 3 REGRET ANALYSIS
text: In this section, we provide a regret analysis of NeuralTS. We assume that there exists an unknown reward function h such that for any 1 ≤ t ≤ T and 1 ≤ k ≤ K,
rt,k = h(xt,k) + ξt,k, with |h(xt,k)| ≤ 1 where {ξt,k} forms an R-sub-Gaussian martingale difference sequence with constant R > 0, i.e., E[exp(λξt,k)|ξ1:t−1,k,x1:t,k] ≤ exp(λ2R2) for all λ ∈ R. Such an assumption on the noise sequence is widely adapted in contextual bandit literature (Agrawal & Goyal, 2013; Bubeck & CesaBianchi, 2012; Chowdhury & Gopalan, 2017; Chu et al., 2011; Lattimore & Szepesvári, 2020; Valko et al., 2013).
Next, we provide necessary background on the neural tangent kernel (NTK) theory (Jacot et al., 2018), which plays a crucial role in our analysis. In the analysis, we denote by {xi}TKi=1 the set of observed contexts of all arms and all rounds: {xt,k}1≤t≤T,1≤k≤K where i = K(t− 1) + k. Definition 3.1 (Jacot et al. (2018)). Define
H̃ (1) i,j = Σ (1) i,j = 〈x i,xj〉,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) max{u, 0}max{v, 0},
H̃ (l+1) i,j = 2H̃ (l) i,jE(u,v)∼N(0,A(l)i,j) 1(u ≥ 0)1(v ≥ 0) + Σ (l+1) i,j .
Then, H = (H̃(L) + Σ(L))/2 is called the neural tangent kernel matrix on the context set.
The NTK technique builds a connection between deep neural networks and kernel methods. It enables us to adapt some complexity measures for kernel methods to describe the complexity of the neural network, as given by the following definition.
Definition 3.2. The effective dimension d̃ of matrix H with regularization parameter λ is defined as
d̃ = log det(I + H/λ)
log(1 + TK/λ) .
Remark 3.3. The effective dimension is a metric to describe the actual underlying dimension in the set of observed contexts, and has been used by Valko et al. (2013) for the analysis of kernel UCB. Our definition here is adapted from Yang & Wang (2019), which also considers UCB-based exploration. Compared with the maximum information gain γt used in Chowdhury & Gopalan (2017), one can verify that their Lemma 3 shows that γt ≥ log det(I + H/λ)/2. Therefore, γt and d̃ are of the same order up to a ratio of 1/(2 log(1 + TK/λ)). Furthermore, d̃ can be upper bounded if all contexts xi are nearly on some low-dimensional subspace of the RKHS space spanned by NTK (Appendix D).
We will make a regularity assumption on the contexts and the corresponding NTK matrix H. Assumption 3.4. Let H be defined in Definition 3.1. There exists λ0 > 0, such that H λ0I. In addition, for any t ∈ [T ], k ∈ [K], ‖xt,k‖2 = 1 and [xt,k]j = [xt,k]j+d/2.
The assumption that the NTK matrix is positive definite has been considered in prior work on NTK (Arora et al., 2019; Du et al., 2018). The assumption on context xt,a ensures that the initial output of neural network f(x;θ0) is 0 with the random initialization suggested in Algorithm 1. The condition on x is easy to satisfy, since for any context x, one can always construct a new context x̃ as [x/( √ 2‖x‖2),x/( √
2‖x‖2)]>. We are now ready to present the main result of the paper: Theorem 3.5. Under Assumption 3.4, set the parameters in Algorithm 1 as λ = 1 + 1/T , ν =
B + R √ d̃ log(1 + TK/λ) + 2 + 2 log(1/δ) where B = max { 1/(22e √ π), √ 2h>H−1h } with
h = (h(x1), . . . , h(xTK))>, and R is the sub-Gaussian parameter. In line 9 of Algorithm 1, set η = C1(mλ+mLT )
−1 and J = (1 +LT/λ)(C2 + log(T 3Lλ−1 log(1/δ)))/C1 for some positive constants C1, C2. If the network width m satisfies:
m ≥ poly ( λ, T,K,L, log(1/δ), λ−10 ) ,
then, with probability at least 1− δ, the regret of Algorithm 1 is bounded as RT ≤ C3(1 + cT )ν √ 2λL(d̃ log(1 + TK) + 1)T + (4 + C4(1 + cT )νL) √ 2 log(3/δ)T + 5, where C3, C4 are some positive absolute constants, and cT = √
4 log T + 2 logK. Remark 3.6. The definitionB in Theorem 3.5 is inspired by the RKHS norm of the reward function defined in Chowdhury & Gopalan (2017). It can be verified that when the reward function h belongs to the function space induced by NTK, i.e., ‖h‖H <∞, we have √ h>H−1h ≤ ‖h‖H according to
Zhou et al. (2019), which suggests that B ≤ max{1/(22e √ π), √
2‖h‖H}. Remark 3.7. Theorem 3.5 implies the regret of NeuralTS is on the order of Õ(d̃T 1/2). This result matches the state-of-the-art regret bound in Chowdhury & Gopalan (2017); Agrawal & Goyal (2013); Zhou et al. (2019); Kveton et al. (2020). Remark 3.8. In Theorem 3.5, the requirement of m is specified in Condition 4.1 and the proof of Theorem 3.5, which is a high-degree polynomial in the time horizon T , number of layers L and number of actions K. However, in our experiments, we can choose reasonably small m (e.g., m = 100) to obtain good performance of NeuralTS. See Appendix A.1 for more details. This discrepancy between theory and practice is due to the limitation of current NTK theory (Du et al., 2018; Allen-Zhu et al., 2018; Zou et al., 2019). Closing the gap is a venue for future work. Remark 3.9. Theorem 3.5 suggests that we need to know T before we run the algorithm in order to set m. When T is unknown, we can use the standard doubling trick (See e.g., Cesa-Bianchi & Lugosi (2006)) to set m adaptively. In detail, we decompose the time interval (0,+∞) as a union of non-overlapping intervals [2s, 2s+1). When 2s ≤ t < 2s+1, we restart NeuralTS with the input T = 2s+1. It can be verified that similar Õ(d̃ √ T ) regret still holds.

heading: 4 PROOF OF THE MAIN THEOREM
text: This section sketches the proof of Theorem 3.5, with supporting lemmas and technical details provided in Appendix B. While the proof roadmap is similar to previous work on Thompson Sampling (e.g., Agrawal & Goyal, 2013; Chowdhury & Gopalan, 2017; Kocák et al., 2014; Kveton et al., 2020), our proof needs to carefully track the approximation error of neural networks for approximating the reward function. To control the approximation error, the following condition on the neural network width is required in several technical lemmas. Condition 4.1. The network width m satisfies
m ≥ C max {√ λL−3/2[log(TKL2/δ)]3/2, T 6K6L6 log(TKL/δ) max{λ−40 , 1}, }
m[logm]−3 ≥ CTL12λ−1 + CT 7λ−8L18(λ+ LT )6 + CL21T 7λ−7(1 + √ T/λ)6,
where C is a positive absolute constant.
For any t, we define an event Eσt as follows Eσt = {ω ∈ Ft+1 : ∀k ∈ [K], |r̃t,k − f(xt,k;θt−1)| ≤ ctνσt,k}, (4.1) where ct = √
4 log t+ 2 logK. Under event Eσt , the difference between the sampled reward r̃t,k and the estimated mean reward f(xt,k;θt−1) can be controlled by the reward’s posterior variance.
We also define an event Eµt as follows Eµt = {ω ∈ Ft : ∀k ∈ [K], |f(xt,k;θt−1)− h(xt,k)| ≤ νσt,k + (m)}, (4.2)
where (m) is defined as (m) = p(m) + C ,1(1− ηmλ)J √ TL/λ
p(m) = C ,2T 2/3m−1/6λ−2/3L3 √ logm+ C ,3m −1/6 √ logmL4T 5/3λ−5/3(1 + √ T/λ)
+ C ,4
( B +R √ log det(I + H/λ) + 2 + 2 log(1/δ) )√ logmT 7/6m−1/6λ−2/3L9/2,
(4.3)
and {C ,i}4i=1 are some positive absolute constants. Under event E µ t , the estimated mean reward f(xt,k;θt−1) based on the neural network is similar to the true expected reward h(xt,k). Note that the additional term (m) is the approximate error of the neural networks for approximating the true reward function. This is a key difference in our proof from previous regret analysis of Thompson Sampling Agrawal & Goyal (2013); Chowdhury & Gopalan (2017), where there is no approximation error.
The following two lemmas show that both events Eσt and E µ t happen with high probability. Lemma 4.2. For any t ∈ [T ], Pr ( Eσt ∣∣Ft) ≥ 1− t−2.
Lemma 4.3. Suppose the width of the neural network m satisfies Condition 4.1. Set η = C(mλ+ mLT )−1, then we have Pr ( ∀t ∈ [T ], Eµt ) ≥ 1− δ, where C is an positive absolute constant.
The next lemma gives a lower bound of the probability that the sampled reward r̃ is larger than true reward up to the approximation error (m).
Lemma 4.4. For any t ∈ [T ], k ∈ [K], we have Pr ( r̃t,k + (m) > h(xt,k) ∣∣Ft, Eµt ) ≥ (4e√π)−1. Following Agrawal & Goyal (2013), for any time t, we divide the arms into two groups: saturated and unsaturated arms, based on whether the standard deviation of the estimates for an arm is smaller than the standard deviation for the optimal arm or not. Note that the optimal arm is included in the group of unsaturated arms. More specifically, we define the set of saturated arms St as follows
St = { k ∣∣k ∈ [K], h(xt,a∗t )− h(xt,k) ≥ (1 + ct)νσt,k + 2 (m)}. (4.4)
Note that we have taken the approximate error (m) into consideration when defining saturated arms, which differs from the Thompson Sampling literature (Agrawal & Goyal, 2013; Chowdhury & Gopalan, 2017). It is now easy to show that the immediate regret of playing an unsaturated arm can be bounded by the standard deviation plus the approximation error (m).
The following lemma shows that the probability of pulling a saturated arm is small in Algorithm 1.
Lemma 4.5. Let at be the arm pulled at round t ∈ [T ]. Then, Pr ( at /∈ St|Ft, Eµt ) ≥ 1 4e √ π − 1t2 .
The next lemma bounds the expectation of the regret at each round conditioned on Eµt . Lemma 4.6. Suppose the width of the neural network m satisfies Condition 4.1. Set η = C1(mλ+ mLT )−1, then with probability at least 1− δ, we have for all t ∈ [T ] that
E[h(xt,a∗t )− h(xt,at)|Ft, E µ t ] ≤ C2(1 + ct)ν √ LE[min{σt,at , 1}|Ft, E µ t ] + 4 (m) + 2t −2,
where C1, C2 are some positive absolute constants.
Based on Lemma 4.6, we define ∆̄t := (h(xt,a∗t )− h(xt,at))1(E µ t ), and
Xt := ∆̄t − ( C∆(1 + ct)ν √ Lmin{σt,at , 1}+ 4 (m) + 2t−2 ) , Yt = t∑ i=1 Xi, (4.5)
where C∆ is the same with constant C in Lemma 4.6. By Lemma 4.6, we can verify that with probability at least 1− δ, {Yt} forms a super martingale sequence since E(Yt − Yt−1) = EXt ≤ 0. By Azuma-Hoeffding inequality (Hoeffding, 1963), we can prove the following lemma. Lemma 4.7. Suppose the width of the neural network m satisfies Condition 4.1. Then set η = C1(mλ+mLT )
−1, we have, with probability at least 1− δ, that T∑ i=1 ∆̄i ≤ 4T (m) + π2/3 + C2(1 + cT )ν √ L T∑ i=1 min{σt,at , 1}
+ (4 + C3(1 + cT )νL+ 4 (m)) √ 2 log(1/δ)T ,
where C1, C2, C3 are some positive absolute constants.
The last lemma is used to control ∑T i=1 min{σt,at , 1} in Lemma 4.7. Lemma 4.8. Suppose the width of the neural network m satisfies Condition 4.1. Then set η = C1(mλ+mLT )
−1, we have, with probability at least 1− δ, it holds that T∑ i=1 min{σt,at , 1} ≤ √ 2λT (d̃ log(1 + TK) + 1) + C2T 13/6 √ logmm−1/6λ−2/3L9/2,
where C1, C2 are some positive absolute constants.
With all the above lemmas, we are ready to prove Theorem 3.5.
Proof of Theorem 3.5. By Lemma 4.3, Eµt holds for all t ∈ [T ] with probability at least 1 − δ. Therefore, with probability at least 1− δ, we have
RT = T∑ i=1 (h(xt,a∗t )− h(xt,at))1(E µ t )
≤ 4T (m) + π 2
3 + C̄1(1 + cT )ν
√ L T∑ i=1 min{σt,at , 1}
+ (4 + C̄2(1 + cT )νL+ 4 (m)) √ 2 log(1/δ)T
≤ C̄1(1 + cT )ν √ L (√ 2λT (d̃ log(1 + TK) + 1) + C̄3T 13/6 √ logmm−1/6λ−2/3L9/2 )
+ π2
3 + 4T (m) + 4 (m)
√ 2 log(1/δ)T + (4 + C̄2(1 + cT )νL) √ 2 log(1/δ)T ,
= C̄1(1 + cT )ν √ L (√ 2λT (d̃ log(1 + TK) + 1) + C̄3T 13/6 √ logmm−1/6λ−2/3L9/2 )
+ π2
3 + p(m)(4T +
√ 2 log(1/δ)T ) + (4 + C̄2(1 + cT )νL) √ 2 log(1/δ)T
+ C ,1(1− ηmλ)J √ TL/λ(4T + √ 2 log(1/δ)T ),
where C̄1, C̄2, C̄3 are some positive absolute constants, the first inequality is due to Lemma 4.7, and the second inequality is due to Lemma 4.8. The third equation is from (4.3). By setting η = C̄4(mλ+mLT ) −1 and J = (1 + LT/λ)(log(24C ,1) + log(T 3Lλ−1 log(1/δ)))/C̄4, we have
C ,1(1− ηmλ)J √ TL/λ(4T + √ 2 log(1/δ)T ) ≤ 1
3 ,
Then choosing m such that
C̄1C̄3(1 + cT )νT 13/6 √ logmm−1/6λ−2/3L5 ≤ 1
3 , p(m)(4T +
√ 2 log(1/δ)T ) ≤ 1
3 .
RT can be further bounded by RT ≤ C̄1(1 + cT )ν √ 2λL(d̃ log(1 + TK) + 1)T + (4 + C̄2(1 + cT )νL) √ 2 log(1/δ)T + 5.
Taking union bound over Lemmas 4.3, 4.7 and 4.8, the above inequality holds with probability 1− 3δ. By replacing δ with δ/3 and rearranging terms, we complete the proof.

heading: 5 EXPERIMENTS
text: This section gives an empirical evaluation of our algorithm in several public benchmark datasets, including adult, covertype, magic telescope, mushroom and shuttle, all from UCI (Dua & Graff, 2017), as well as MNIST (LeCun et al., 2010). The algorithm is compared to several typical baselines: linear and kernelized Thompson Sampling (Agrawal & Goyal, 2013; Chowdhury & Gopalan, 2017), linear and kernelized UCB (Chu et al., 2011; Valko et al., 2013), BootstrapNN (Osband et al., 2016b; Riquelme et al., 2018), and -greedy for neural networks. BootstrapNN trains multiple neural networks with subsampled data, and at each step pulls the greedy action based on a randomly selected network. It has been proposed as a way to approximate Thompson Sampling (Osband & Van Roy, 2015; Osband et al., 2016b).

heading: 5.1 EXPERIMENT SETUP
text: To transform these classification problems into multi-armed bandits, we adapt the disjoint models (Li et al., 2010) to build a context feature vector for each arm: given an input feature x ∈ Rd of a k-class classification problem, we build the context feature vector with dimension kd as: x1 =( x; 0; · · · ; 0 ) ,x2 = ( 0; x; · · · ; 0 ) , · · · ,xk = ( 0; 0; · · · ; x ) . Then, the algorithm generates a set of predicted reward following Algorithm 1 and pulls the greedy arm. For these classification problems, if the algorithm selects a correct class by pulling the corresponding arm, it will receive a reward as 1, otherwise 0. The cumulative regret over time horizon T is measured by the total mistakes made by the algorithm. All experiments are repeated 8 times with reshuffled data.
We set the time horizon of our algorithm to 10 000 for all data sets, except for mushroom which contains only 8 124 data. In order to speed up training for the NeuralUCB and Neural Thompson Sampling, we use the inverse of the diagonal elements of U as an approximation of U−1. Also, since calculating the kernel matrix is expensive, we stop training at t = 1000 and keep evaluating the performance for the rest of the time, similar to previous work (Riquelme et al., 2018; Zhou et al., 2019). Due to space limit, we defer the results on adult, covertype and magic telescope, as well as further experiment details, to Appendix A. In this section, we only show the results on mushroom, shuttle and MNIST.

heading: 5.2 EXPERIMENT I: PERFORMANCE OF NEURAL THOMPSON SAMPLING
text: The experiment results of Neural Thompson Sampling and other benchmark algorithms are shown in Figure 1. A few observations are in place. First, Neural Thompson Sampling’s performance is among the best in 6 datasets and is significantly better than all other baselines in 2 of them. Second, the function class used by an algorithm is important. Those with linear representations tend to perform worse due to the nonlinearity of rewards in the data. Third, Thompson Sampling is competitive with, and sometimes better than, other exploration strategies with the same function class, in particular when neural networks are used.

heading: 5.3 EXPERIMENT II: ROBUSTNESS TO REWARD DELAY
text: This experiment is inspired by practical scenarios where reward signals are delayed, due to various constraints, as described by Chapelle & Li (2011). We study how robust the two most competitive methods from Experiment I, Neural UCB and Neural Thompson Sampling, are when rewards are delayed. More specifically, the reward after taking an action is not revealed immediately, but arrive in batches when the algorithms will update their models. The experiment setup is otherwise identical to Experiment I. Here, we vary the batch size (i.e., the amount of reward delay), and Figure 2 shows the corresponding total regret. Clearly, we recover the result in Experiment I when the delay is 0. Consistent with previous findings (Chapelle & Li, 2011), Neural TS degrades much more gracefully than Neural UCB when the reward delay increases. The benefit may be explained by the algorithm’s randomized exploration nature that encourages exploration between batches. We, therefore, expect wider applicability of Neural TS in practical applications.

heading: 6 RELATED WORK
text: Thompson Sampling was proposed as an exploration heuristic almost nine decades ago (Thompson, 1933), and has received significant interest in the last decade. Previous works related to the present paper are discussed in the introduction, and are not repeated here.
Upper confidence bound or UCB (Agrawal, 1995; Auer et al., 2002; Lai & Robbins, 1985) is a widely used alternative to Thompson Sampling for exploration. This strategy is shown to achieve near-optimal regrets in a range of settings, such as linear bandits (Abbasi-Yadkori et al., 2011; Auer, 2002; Chu et al., 2011), generalized linear bandits (Filippi et al., 2010; Jun et al., 2017; Li et al., 2017), and kernelized contextual bandits (Valko et al., 2013).
Neural networks are increasingly used in contextual bandits. In addition to those mentioned earlier (Blundell et al., 2015; Kveton et al., 2020; Lu & Van Roy, 2017; Riquelme et al., 2018), Zahavy
& Mannor (2019) used a deep neural network to provide a feature mapping and explored only at the last layer. Schwenk & Bengio (2000) proposed an algorithm by boosting the estimation of multiple deep neural networks. While these methods all show promise empirically, no regret guarantees are known. Recently, Foster & Rakhlin (2020) proposed a special regression oracle and randomized exploration for contextual bandits with a general function class (including neural networks) along with theoretical analysis. Zhou et al. (2019) proposed a neural UCB algorithm with near-optimal regret based on UCB exploration, while this paper focuses on Thompson Sampling.

heading: 7 CONCLUSIONS
text: In this paper, we adapt Thompson Sampling to neural networks. Building on recent advances in deep learning theory, we are able to show that the proposed algorithm, NeuralTS, enjoys a Õ(d̃T 1/2) regret bound. We also show the algorithm works well empirically on benchmark problems, in comparison with multiple strong baselines.
The promising results suggest a few interesting directions for future research. First, our analysis needs NeuralTS to perform multiple gradient descent steps to train the neural network in each round. It is interesting to analyze the case where NeuralTS only performs one gradient descent step in each round, and in particular, the trade-off between optimization precision and regret minimization. Second, when the number of arms is finite, Õ( √ dT ) regret has been established for parametric bandits with linear and generalized linear reward functions. It is an open problem how to adapt NeuralTS to achieve the same rate. Third, Allen-Zhu & Li (2019) suggested that neural networks may behave differently from a neural tangent kernel under some parameter regimes. It is interesting to investigate whether similar results hold for neural contextual bandit algorithms like NeuralTS.

heading: ACKNOWLEDGEMENT
text: We would like to thank the anonymous reviewers for their helpful comments. WZ, DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169 and IIS-1904183. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

heading: A FURTHER DETAIL OF THE EXPERIMENTS IN SECTION 5

heading: A.1 PARAMETER TUNING
text: In the experiments, we shuffle all datasets randomly, and normalize the features so that their `2- norm is unity. One-hidden-layer neural networks with 100 neurons are used. Note that we do not choose m as suggested by theory, and such a disconnection has its root in the current deep learning theory based on neural tangent kernel, which is not specific in this work. During posterior updating, gradient descent is run for 100 iterations with learning rate 0.001. For BootstrapNN, we use 10 identical networks, and to train each network, data point at each round has probability 0.8 to be included for training (p = 10, q = 0.8 in the original paper (Schwenk & Bengio, 2000)) For - Greedy, we tune with a grid search on {0.01, 0.05, 0.1}. For (λ, ν) used in linear and kernel UCB / Thompson Sampling, we set λ = 1 following previous works (Agrawal & Goyal, 2013; Chowdhury & Gopalan, 2017), and do a grid search of ν ∈ {1, 0.1, 0.01} to select the parameter with best performance. For the Neural UCB / Thompson Sampling methods, we use a grid search on λ ∈ {1, 10−1, 10−2, 10−3} and ν ∈ {10−1, 10−2, 10−3, 10−4, 10−5}. All experiments are repeated 20 times, and the average and standard error are reported.

heading: A.2 DETAILED RESULTS
text: Table 1 summarizes the total regrets measured at the last round on different data sets, with mean and standard deviation error computed based on 20 independent runs. The Bold Faced data is the top performance over 8 experiments. Table 2 shows the number of times the algorithm in that row significantly outperforms, ties, or significantly underperforms, compared with other algorithm with t-test at 90% significance level. Figure 3 shows the performance of Neural Thompson Sampling compared with other baseline method. Figure 4 shows the comparison between Neural Thompson Sampling and Neural UCB in delay reward settings.

heading: A.3 RUN TIME ANALYSIS
text: We compare the run time of the four algorithms based on neural networks: BootstrapNN, -greedy for neural networks, NeuralUCB, and NeuralTS. The comparison is shown in Figure 5. We can see that NeuralTS and NeuralUCB are about 2 to 3 times slower than -greedy, which is due to the extra calculation of the neural network gradient for each input context. BootstrapNN is often more than 5 times slower than -greedy because it has to train several neural networks at each round.

heading: B PROOF OF LEMMAS IN SECTION 4
text: Under Condition 4.1, we can show that the following inequalities hold. 2 √ 1/λ ≥ Cm,1m−1L−3/2[log(TKL2/δ)]3/2,
2 √ T/λ ≤ Cm,2 min { m1/2L−6[logm]−3/2,m7/8 ( (λη)2L−6T−1(logm)−1 )3/8} ,
m1/6 ≥ Cm,3 √ logmL7/2T 7/6λ−7/6(1 + √ T/λ)
m ≥ Cm,4T 6K6L6 log(TKL/δ) max{λ−40 , 1}, where {Cm,1, Cm,2, . . . , Cm,4} are some positive absolute constants.

heading: B.1 PROOF OF LEMMA 4.2
text: The following concentration bound on Gaussian distributions will be useful in our proof. Lemma B.1 (Hoffman et al. (2013)). Consider a normally distributed random variable X ∼ N (µ, σ2) and β ≥ 0. The probability that X is within a radius of βσ from its mean can then be written as
Pr ( |X − µ| ≤ βσ ) ≥ 1− exp(−β2/2).
Proof of Lemma 4.2. Since the estimated reward r̃t,k is sampled from N (f(xt,k;θt−1), ν2σ2t,k) if given filtration Ft, Lemma B.1 implies that, conditioned on Ft and given t, k,
Pr ( |r̃t,k − f(xt,k;θt−1)| ≤ ctνσt,k ∣∣Ft) ≥ 1− exp(−c2t/2). Taking a union bound over K arms, we have that for any t
Pr ( ∀k, |r̃t,k − f(xt,k;θt−1)| ≤ ctνσt,k ∣∣Ft) ≥ 1−K exp(−c2t/2).
Finally, choose ct = √ 4 log t+ 2 logK as defined in (4.1), we get the bound that
Pr ( Eσt ∣∣Ft) = Pr (∀k, |r̃t,k − f(xt,k;θt−1)| ≤ ctνσt,k∣∣Ft) ≥ 1− 1
t2 .

heading: B.2 PROOF OF LEMMA 4.3
text: Before going into the proof, some notation is needed about linear and kernelized models. Definition B.2. Define Ūt = λI+ ∑t i=1 g(xi,ai ;θ0)g(xt,at ;θ0)
>/m and based on Ūt, we further define σ̄2t,k = λg >(xt,k;θ0)Ū −1 t−1g(xt,k;θ0)/m. Furthermore, for convenience we define
Jt = (g(x1,a1 ;θt) · · · g(xt,at ;θt)) , J̄t = (g(x1,a1 ;θ0) · · · g(xt,at ;θ0)) ht = (h(x1,a1) · · · h(xt,at)) > , rt = (r1 · · · rt) > ,
t = (h(x1,a1)− r1 · · · h(xt,at)− rt) > ,
where t is the reward noise. We can verify that Ut = λI + JtJ>t /m, Ūt = λI + J̄tJ̄ > t /m . We further define Kt = J̄>t J̄t/m.
The first lemma shows that the target function is well-approximated by the linearized neural network if the network width m is large enough. Lemma B.3 (Lemma 5.1, Zhou et al. (2019)). There exists some constant C > 0 such that for any δ ∈ (0, 1), if
m ≥ CT 4K4L6 log(T 2K2L/δ)/λ40,
then with probability at least 1− δ over the random initialization of θ0, there exists a θ∗ ∈ Rp such that
h(xi) = 〈g(xi;θ0),θ∗ − θ0〉, √ m‖θ∗ − θ0‖2 ≤ √ 2h>H−1h ≤ B, (B.1)
for all i ∈ [TK], where B is defined in Theorem 3.5.
From Lemma B.3, it is easy to show that under this initialization parameter θ0, we have that ht = J̄>t (θ
∗ − θ0) The next lemma bounds the difference between the σ̄t,k from the linearized model and the σt,k actually used in the algorithm. Its proof, together with other technical lemmas’, will be given in the next section. Lemma B.4. Suppose the network size m satisfies Condition 4.1. Set η = C1(mλ + mLT )−1, then with probability at least 1− δ,
|σ̄t,k − σt,k| ≤ C2 √ logmt7/6m−1/6λ−2/3L9/2,
where C1, C2 are two positive constants.
We next bound the difference between the outputs of the neural network and the linearized model. Lemma B.5. Suppose the network width m satisfies Condition 4.1.
Then, set η = C1(mλ + mLT )−1, with probability at least 1 − δ over the random initialization of θ0, we have∣∣f(xt,k;θt−1)− 〈g(xt,k;θ0), Ū−1t−1J̄t−1rt−1/m〉∣∣ ≤ C2t2/3m−1/6λ−2/3L3√logm
+ C3(1− ηmλ)J √ tL/λ
+ C4m −1/6 √ logmL4t5/3λ−5/3(1 + √ t/λ),
where {Ci}4i=1 are positive constants.
The next lemma, due to Chowdhury & Gopalan (2017), controls the quadratic value generated by an R-sub-Gaussian random vector : Lemma B.6 (Theorem 1, Chowdhury & Gopalan (2017)). Let { t}∞t=1 be a real-valued stochastic process such that for some R ≥ 0 and for all t ≥ 1, t is Ft-measurable and R-sub-Gaussian conditioned on Ft, Recall Kt defined in Definition B.2. With probability 0 < δ < 1 and for a given η > 0, with probability 1− δ, the following holds for all t,
>1:t((Kt + ηI) −1 + I)−1 1:t ≤ R2 log det((1 + η)I + Kt) + 2R2 log(1/δ).
Finally, the following lemma shows the linearized kernel and the neural tangent kernel are closed: Lemma B.7. For all t ∈ [T ], there exists a positive constants C such that the following holds: if the network width m satisfies
m ≥ CT 6L6K6 log(TKL/δ), then with probability at least 1− δ,
log det(I + λ−1Kt) ≤ log det(I + λ−1H) + 1.
We are now ready to prove Lemma 4.3.
Proof of Lemma 4.3. First of all, since m satisfies Condition 4.1, then with the choice of η ,the condition required in Lemmas B.3–B.7 are satisfied. Thus, taking a union bound, we have with probability at least 1 − 5δ, that the bounds provided by these lemmas hold. Then for any t ∈ [T ], we will first provide the difference between the target function and the linear function〈 g(xt,k;θ0), Ū −1 t−1J̄t−1rt−1/m
〉 as:∣∣h(xt,k)− 〈g(xt,k;θ0), Ū−1t−1J̄t−1rt−1/m〉∣∣
≤ ∣∣h(xt,k)− 〈g(xt,k;θ0), Ū−1t−1J̄t−1ht−1/m〉∣∣+ ∣∣〈g(xt,k;θ0), Ū−1t−1J̄t−1 t−1/m〉∣∣
= ∣∣〈g(xt,k;θ0),θ∗ − θ0 − Ū−1t−1J̄t−1J̄>t−1(θ∗ − θ0)/m〉∣∣+ ∣∣g(xt,k;θ0)>Ū−1t−1J̄t−1 t−1/m∣∣
= ∣∣〈g(xt,k;θ0), (I− Ū−1t−1(Ūt−1 − λI))(θ∗ − θ0)〉∣∣+ ∣∣g(xt,k;θ0)>Ū−1t−1J̄t−1 t−1/m∣∣
= λ ∣∣g(xt,k;θ0)>Ū−1t−1(θ∗ − θ0)∣∣+ ∣∣g(xt,k;θ0)>Ū−1t−1J̄t−1 t−1/m∣∣
≤ λ √
g(xt,k;θ0)>Ū −1 t−1g(xt,k;θ0) √ (θ∗ − θ0)>Ū−1t−1(θ∗ − θ0)
+ √
g(xt,k;θ0)>Ū −1 t−1g(xt,k;θ0) √ >t−1J̄ > t−1Ū −1 t−1J̄t−1 t−1/m
≤ √ m‖θ∗ − θ0‖2σ̄t,k + σ̄t,kλ−1/2 √ >t−1J̄ > t−1Ū −1 t−1J̄t−1 t−1/m (B.2)
where the first inequality uses triangle inequality and the fact that rt−1 = ht−1 + t−1; the first equality is from Lemma B.3 and the second equality uses the fact that J̄t−1J̄>t−1 = m(Ūt−1 − λI) which can be verified using Definition B.2; the second inequality is from the fact that |α>Aβ| ≤√ α>Aα √ β>Aβ. Since U−1t−1 1λI and σ̄t,k defined in Definition B.2, we obtain the last inequality.
Furthermore, by obtaining J̄>t−1U −1 t−1J̄t−1/m = J̄ > t−1(λI + J̄t−1J̄ > t−1/m) −1Jt−1
= J̄>t−1(λ −1I− λ−2J̄t−1(I + λ−1J̄>t−1J̄t−1/m)−1J̄>t−1/m)J̄t−1/m = λ−1J̄>t−1J̄t−1/m− λ−1J>t−1J̄t−1(λI + J̄>t−1J̄t−1/m)−1J̄>t−1J̄t−1/m2
= λ−1Kt−1(I− (λI + Kt−1)−1Kt−1) = Kt−1(λI + Kt−1)−1, where the first equality is from the Sherman-Morrison formula, and the second equality uses Definition B.2 and the fact that (λI + Kt−1)−1Kt−1 = I − λ(λI + Kt−1)−1 which could be verified by multiplying the LHS and RHS together, we have that√
>t−1J̄ > t−1U −1 t−1J̄t−1 t−1/m ≤ √ >t−1Kt−1(λI + Kt−1) −1 t−1
≤ √ >t−1(Kt−1 + (λ− 1)I)(λI + Kt−1)−1 t−1
= √ >t−1(I + (Kt−1 + (λ− 1)I)−1)−1 t−1 (B.3)
where the second inequality is because λ = 1 + 1/T ≥ 1 set in Theorem 3.5. Based on (B.2) and (B.3), by utilizing the bound on ‖θ∗ − θ‖2 provided in Lemma B.3, as well as the bound given in Lemma B.6, and λ ≥ 1, we have ∣∣h(xt,k)− 〈g(xt,k;θ0), Ū−1t−1J̄t−1rt−1m〉∣∣ ≤ (B +R√log det(λI + Kt−1) + 2 log(1/δ))σ̄t,k, since it is obvious that
log det(λI + Kt−1) = log det(I + λ −1Kt−1) + (t− 1) log λ
≤ log det(I + λ−1Kt−1) + t(λ− 1) ≤ log det(I + λ−1H) + 2,
where the first equality moves the λ outside the log det, the first inequality is due to log λ ≤ λ− 1, and the second inequality is from Lemma B.7 and the fact that λ = 1 + 1/T (as set in Theorem 3.5). Thus, we have ∣∣h(xt,k)− 〈g(xt,k;θ0), Ū−1t−1J̄t−1rt−1m〉∣∣ ≤ νσ̄t,k, where we set ν = B + R √ log det(I + H/λ) + 2 + 2 log(1/δ). Then, by combining this bound
with Lemma B.5, we conclude that there exist positive constants C̄1, C̄2, C̄3 so that
|f(xt,k;θt−1)− h(xt,k)| ≤ νσ̄t,k + C̄1t2/3m−1/6λ−2/3L3 √ logm+ C̄2(1− ηmλ)J √ tL/λ
+ C̄3m −1/6 √ logmL4t5/3λ−5/3(1 + √ t/λ),
≤ νσt,k + C̄1t2/3m−1/6λ−2/3L3 √ logm+ C̄2(1− ηmλ)J √ tL/λ
+ C̄3m −1/6 √ logmL4t5/3λ−5/3(1 + √ t/λ)
+ ( B +R √ log det(I + H/λ) + 2 + 2 log(1/δ) ) (σ̄t,k − σt,k).
Finally, by utilizing the bound of |σ̄t,k − σt,k| provided in Lemma B.4, we conclude that
|f(xt,k;θt−1)− h(xt,k)| ≤ νσt,k + (m),
where (m) is defined by adding all of the additional terms and taking t = T :
(m) = C̄1T 2/3m−1/6λ−2/3L3 √ logm+ C̄2(1− ηmλ)J √ TL/λ+
+ C̄3m −1/6 √ logmL4T 5/3λ−5/3(1 + √ T/λ)
+ C̄4
( B +R √ log det(I + H/λ) + 2 + 2 log(1/δ) )√ logmT 7/6m−1/6λ−2/3L9/2,
where is exactly the same form defined in (4.3). By setting δ to δ/5 (required by the union bound discussed at the beginning of the proof), we get the result presented in Lemma 4.3.

heading: B.3 PROOF OF LEMMA 4.4
text: Our proof requires an anti-concentration bound for Gaussian distribution, as stated below:
Lemma B.8 (Gaussian anti-concentration). For a Gaussian random variable X with mean µ and standard deviation σ, for any β > 0,
Pr ( X − µ σ > β ) ≥ exp(−β 2) 4 √ πβ .
Proof of Lemma 4.4. Since r̃t,k ∼ N (f(xt,k;θt−1), ν2t σ2t,k) conditioned on Ft, we have
Pr ( r̃t,k + (m) > h(xt,k) ∣∣Ft, Eµt ) = Pr ( r̃t,k − f(xt,k;θt−1) + (m)
νσt,k > h(xt,k)− f(xt,k;θt−1) νσt,k ∣∣∣∣Ft, Eµt ) ≥ Pr ( r̃t,k − f(xt,k;θt−1) + (m)
νσt,k > |h(xt,k)− f(xt,k;θt−1)| νσt,k ∣∣∣∣Ft, Eµt ) = Pr ( r̃t,k − f(xt,k;θt−1)
νσt,k > |h(xt,k)− f(xt,k;θt−1)| − (m) νσt,k ∣∣∣∣Ft, Eµt ) ≥ Pr ( r̃t,k − f(xt,k;θt−1)
νσt,k > 1 ∣∣∣∣Ft, Eµt ) ≥ 14e√π , where the first inequality is due to |x| ≥ x, and the second inequality follows from event Eµt , i.e.,
∀k ∈ [K], |f(xt,k;θt−1)− h(xt,k)| ≤ νσt,k + (m).

heading: B.4 PROOF OF LEMMA 4.5
text: Proof of Lemma 4.5. Consider the following two events at round t:
A = {∀k ∈ St, r̃t,k < r̃t,a∗t |Ft, E µ t }, B = {at /∈ St|Ft, Eµt }.
Clearly, A implies B, since at = argmaxk r̃t,k. Therefore, Pr ( at /∈ St ∣∣Ft, Eµt ) ≥ Pr (∀k ∈ St, r̃t,k < r̃t,a∗t ∣∣Ft, Eµt ). Suppose Eµ also holds, then it is easy to show that ∀k ∈ [K],
|h(xt,k)− r̃t,k| ≤ |h(xt,k)− f(xt,k;θt)|+ |f(xt,k;θt)− r̃t,k| ≤ (m) + (1 + c̃t)νtσt,k. (B.4)
Hence, for all k ∈ St, we have that
h(xt,a∗t )− r̃t,k ≥ h(xt,a∗t )− h(xt,k)− |h(xt,k)− r̃t,k| ≥ (m),
where we used the definitions of saturated arms in Definition 4.4, and of Eµt and Eσt in (4.1). Consider the following event
C = {h(xt,a∗t )− (m) < r̃t,a∗t |Ft, E µ t }.
Since Eσt implies h(xt,a∗t )− (m) ≥ r̃t,k, we have that if C, E σ t holds, thenA holds, i.e. Eσt ∩C ⊆ A. Taking union with Ēσt we have that C = Ēσt ∪ Eσt ∩ C ⊆ A ∪ Ēσt , which implies
Pr(A) + Pr(Ēσt ) ≥ Pr(C). (B.5)
Then, (B.5) implies that
Pr ( ∀k ∈ St, r̃t,k < r̃t,a∗t ∣∣Ft, Eµt ) ≥ Pr (r̃t,a∗t + (m) > h(xt,a∗t )∣∣Ft, Eµt )− Pr (Ēσt |Ft, Eµt ) ≥ 1
4e √ π − 1 t2 ,
where the first inequality is from a∗t is a special case of ∀k ∈ [K], the second inequality is from Lemmas 4.2 and 4.4.

heading: B.5 PROOF OF LEMMA 4.6
text: To prove Lemma 4.6, we will need an upper bound bound on δt,k. Lemma B.9. For any time t ∈ [T ], k ∈ [K], and δ ∈ (0, 1), if the network width m satisfies Condition 4.1, we have, with probability at least 1− δ, that
σt,k ≤ C √ L,
where C is a positive constant.
Proof of Lemma 4.6. Recall that given Ft and Eµt , the only randomness comes from sampling r̃t,k for k ∈ [K]. Let k̄t be the unsaturated arm with the smallest σt,·, i.e.
k̄t = argmin k/∈St σt,k,
then we have that
E[σt,at |Ft, E µ t ] ≥ E[σt,at |Ft, E µ t , at /∈ St] Pr(at /∈ St|Ft, E µ t )
≥ σt,k̄t
( 1
4e √ π − 1 t2
) , (B.6)
where the first inequality ignores the case when at ∈ St, and the second inequality is from Lemma 4.5 and the definition of k̄t mentioned above.
If both Eσt and E µ t hold, then
∀k ∈ [K], |h(xt,k)− r̃t,k| ≤ (m) + (1 + ct)νσt,k, (B.7) as proved in equation (B.4). Thus,
h(xt,a∗t )− h(xt,at) = h(xt,a∗t )− h(xt,k̄t) + h(xt,k̄t)− h(xt,at) ≤ (1 + ct)νσt,k̄t + 2 (m) + h(xt,k̄t)− r̃t,k̄t − h(xt,at)
+ r̃t,at + r̃t,k̄t − r̃t,at ≤ (1 + ct)ν(2σt,k̄t + σt,at) + 4 (m), (B.8)
where the first inequality is from Definition 4.4 and k̄t /∈ St, and the second inequality comes from equation (B.7). Since a trivial bound on h(xt,a∗t )− h(xt,at) could be get by h(xt,a∗t )− h(xt,at) ≤ |h(xt,a∗t )|+ |h(xt,at)| ≤ 2, then we have
E[h(xt,a∗t )− h(xt,at)|Ft, E µ t ] = E[h(xt,a∗t )− h(xt,at)|Ft, E µ t , Eσt ] Pr(Eσt )
+ E[h(xt,a∗t )− h(xt,at)|Ft, E µ t , Ēσt ] Pr(Ēσt )
≤ (1 + ct)ν(2σt,k̄t + E[σt,at |Ft, E µ t ]) + 4 (m) +
2
t2
≤ (1 + ct)ν
( 2E[σt,at |Ft, E µ t ]
1 4e √ π − 1t2
+ E[σt,at |Ft, E µ t ]
) + 4 (m) + 2
t2
≤ 44e √ π(1 + ct)νE[σt,at |Ft, E µ t ] + 4 (m) + 2t −2,
where the inequality on the second line uses the bound provide in (B.8) and the trivial bound of h(xt,a∗t ) − h(xt,at) for the second term plus Lemma 4.2, the inequality on the third line uses the bound of σt,k̄t provide in (B.6), inequality on the forth line is directly calculated by 1 ≤ 4e √ π and
1 1
4e √ π − 1t2
≤ 20e √ π,
which trivially holds since LHS is negative when t ≤ 4 and when t = 5, the LHS reach its maximum as ≈ 84.11 < 96.36 ≈ RHS. Noticing that |h(x)| ≤ 1, it is trivial to further extend the bound as
E[h(xt,a∗t )− h(xt,at)|Ft, E µ t ] ≤ min{44e √ π(1 + ct)νE[σt,at |Ft, E µ t ], 2}+ 4 (m) + 2t−2,
and since we have 1 + ct ≥ 1 and ν = B + R √
log det(I + H/λ) + 2 + 2 log(1/δ) ≥ B, recall 22e √ πB ≥ 1, it is easy to verify the following inequality also holds:
E[h(xt,a∗t )− h(xt,at)|Ft, E µ t ]
≤ 44e √ π(1 + ct)νmin{E[σt,at |Ft, E µ t ], 1}+ 4 (m) + 2t−2 ≤ 44e √ π(1 + ct)νC1 √ LE[min{σt,at , 1}|Ft, E µ t ] + 4 (m) + 2t −2,
where we use the fact that there exists a constant C1 such that σt,at is bounded by C1 √ L with
probability 1 − δ provided by Lemma B.9. Merging the positive constant C1 with 44e √ π, we get the statement in Lemma 4.6.

heading: B.6 PROOF OF LEMMA 4.7
text: We start with introducing the Azuma-Hoeffding inequality for super-martingale:
Lemma B.10 (Azuma-Hoeffding Inequality for Super Martingale). If a super-martingale Yt, corresponding to filtration Ft satisfies that |Yt − Yt−1| ≤ Bt, then for any δ ∈ (0, 1), w.p. 1 − δ, we have
Yt − Y0 ≤ √√√√2 log(1/δ) t∑ i=1 B2i .
Proof of Lemma 4.7. From Lemma B.9, we have that there exists a positive constant C1 such that Xt defined in (4.5) is bounded with probability 1− δ by
|Xt| ≤ |∆̄t|+ C1(1 + ct)ν √ Lmin{σt,at , 1}+ 4 (m) + 2t−2
≤ 2 + 2t−2 + C1C2(1 + ct)νL+ 4 (m) ≤ 4 + C1C2(1 + ct)νL+ 4 (m)
where the first inequality uses the fact that |a − b| ≤ |a| + |b|; the second inequality is from Lemma B.9 and the fact that h ≤ 1, where C2 is a positive constant used in Lemma B.9; the third inequality uses the fact that t−2 ≤ 1. Noticing the fact that ct ≤ cT , and from Lemma 4.6, we know that with probability at least 1− δ, Yt is a super martingale. From Lemma B.10, we have
YT − Y0 ≤ (4 + C1C2(1 + cT )νL+ 4 (m)) √ 2 log(1/δ)T . (B.9)
Considering the definition of YT in (4.5), (B.9) is equivalent to
T∑ i=1 ∆̄i ≤ 4T (m) + 2 T∑ i=1 t−2 + C1(1 + cT )ν √ L T∑ i=1 min{σt,at , 1}
+ (4 + C1C2(1 + cT )νL+ 4 (m)) √ 2 log(1/δ)T ,
then by utilizing ∑∞ i=1 t −2 = π2/6, and merge the constant C1 with 44e √ π, taking union bound of the probability bound of Lemma 4.6, B.10, B.9, we have the inequality above hold with probability at least 1 − 3δ. Re-scaling δ to δ/3 and merging the product of C1C2 as a new positive constant leads to the desired result.

heading: B.7 PROOF OF LEMMA 4.8
text: We first state a technical lemma that will be useful:
Lemma B.11 (Lemma 11, Abbasi-Yadkori et al. (2011)). Let {vt}∞t=1 be a sequence in Rd, and define Vt = λI + ∑t i=1 viv > i . If λ ≥ 1, then
T∑ i=1 min{v>t V−1t−1vt−1, 1} ≤ 2 log det ( I + λ−1 t∑ i=1 viv > i ) .
Proof of Lemma 4.8. First, recall σ̄t,k defined in Definition B.2 and the bound of σ̄t,k−σt,k provided in Lemma B.4. We have that there exists a positive constants C1 such that
T∑ i=1 min{σt,at , 1} = T∑ i=1 min{σ̄t,at , 1}+ T∑ i=1 (σt,at − σ̄t,at)
≤ √√√√T T∑ i=1 min{σ̄2t,at , 1}+ C1T 13/6 √ logmm−1/6λ−2/3L9/2,
where the first term in the inequality on the second line is from Cauchy-Schwartz inequality, and the second term is from Lemma B.4.
From Definition B.2, we have T∑ i=1 min{σ̄2t,at , 1} ≤ λ T∑ i=1 min{g(xt,at ,θ0)>Ū−1t−1g(xt,at ,θ0)/m, 1}
≤ 2λ log det ( I + λ−1 T∑ i=1 g(xt,at ;θ0)g(xt,at ;θ0) >/m ) = 2λ log det(I + λ−1J̄T J̄ > T /m) = 2λ log det(I + λ−1J̄>T JT /m) = 2λ log det(I + λ−1KT )
where the first inequality moves the positive parameter λ outside the min operator and uses the definition of σ̄t,k in Definition B.2, then the second inequality utilizes Lemma B.11, the first equality use the definition of J̄t in Definition B.2, the second equality is from the fact that det(I + AA>) = det(I + A>A), and the last equality uses the definition of Kt in Definition B.2. From Lemma B.7, we have that
log det(I + λ−1KT ) ≤ log det(I + λ−1H) + 1 under condition on m and η presented in Theorem 3.5. By taking a union bound we have, with probability 1− 2δ, that
T∑ i=1 min{σ̄t,at , 1} ≤ √ 2λT (d̃ log(1 + TK) + 1) + C1T 13/6 √ logmm−1/6λ−2/3L9/2,
where we use the definition of d̃ in Definition 3.2. Replacing δ with δ/2 completes the proof.

heading: C PROOF OF AUXILIARY LEMMAS IN APPENDIX B
text: In this section, we are about to show the proof of the Lemmas used in Appendix B, we will start with the following NTK Lemmas. Among them, the first is to control the difference between the parameter learned via Gradient Descent and the theoretical optimal solution to linearized network. Lemma C.1 (Lemma B.2, Zhou et al. (2019)). There exist constants {Ci}5i=1 > 0 such that for any δ > 0, if η,m satisfy that for all t ∈ [T ],
2 √ t/λ ≥ C1m−1L−3/2[log(TKL2/δ)]3/2,
2 √ t/λ ≤ C2 min { m1/2L−6[logm]−3/2,m7/8 ( (λη)2L−6t−1(logm)−1 )3/8} ,
η ≤ C3(mλ+ tmL)−1, m1/6 ≥ C4 √ logmL7/2t7/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−1 − θ0‖2 ≤ 2 √ t/(mλ) and
‖θt−1 − θ0 − Ū−1t−1J̄t−1rt−1/m‖2 ≤ (1− ηmλ)J √ t/(mλ) + C5m −2/3 √ logmL7/2t5/3λ−5/3(1 + √ t/λ).
And the next lemma, controls the difference between the function value of neural network and the linearized model: Lemma C.2 (Lemma 4.1, Cao & Gu (2019)). There exist constants {Ci}3i=1 > 0 such that for any δ > 0, if τ satisfies that
C1m −3/2L−3/2[log(TKL2/δ)]3/2 ≤ τ ≤ C2L−6[logm]−3/2,
then with probability at least 1 − δ over the random initialization of θ0, for all θ̃, θ̂ satisfying ‖θ̃ − θ0‖2 ≤ τ, ‖θ̂ − θ0‖2 ≤ τ and j ∈ [TK] we have∣∣∣∣f(xj ; θ̃)− f(xj ; θ̂)− 〈g(xj ; θ̂), θ̃ − θ̂〉∣∣∣∣ ≤ C3τ4/3L3√m logm. Furthermore, to continue with, next lemma is proposed to control the difference between the gradient and the gradient on the initial point. Lemma C.3 (Theorem 5, Allen-Zhu et al. (2018)). There exist constants {Ci}3i=1 > 0 such that for any δ ∈ (0, 1), if τ satisfies that
C1m −3/2L−3/2[log(TKL2/δ)]3/2 ≤ τ ≤ C2L−6[logm]−3/2,
then with probability at least 1 − δ over the random initialization of θ0, for all ‖θ − θ0‖2 ≤ τ and j ∈ [TK] we have
‖g(xj ;θ)− g(xj ;θ0)‖2 ≤ C3 √ logmτ1/3L3‖g(xj ;θ0)‖2.
Also, we need the next lemma to control the gradient norm of the neural network with the help of NTK. Lemma C.4 (Lemma B.3, Cao & Gu (2019)). There exist constants {Ci}3i=1 > 0 such that for any δ > 0, if τ satisfies that
C1m −3/2L−3/2[log(TKL2/δ)]3/2 ≤ τ ≤ C2L−6[logm]−3/2,
then with probability at least 1− δ over the random initialization of θ0, for any ‖θ − θ0‖2 ≤ τ and j ∈ [TK] we have ‖g(xj ;θ)‖F ≤ C3 √ mL.
Finally, as literally shows, we can also provide bounds on the kernel provided by the linearized model and the NTK kernel if the network is width enough.
Lemma C.5 (Lemma B.1, Zhou et al. (2019)). Set K = ∑T t=1 ∑K k=1 g(xt,k;θ0)g(xt,k;θ0)/m, recall the definition of H in Definition 3.1,then there exists a constant C1 such that m ≥ C1L6 log(TKL/δ) −4, we could get that ‖K−H‖F ≤ TK .
Equipped with these lemmas, we could continue for our proof.

heading: C.1 PROOF OF LEMMA B.4
text: Proof of Lemma B.4. Firstly, set τ = 2 √ t/(mλ), then we have the condition on the network m and learning rate η satisfy all of the condition need from Lemma C.1 to Lemma C.5. Thus from Lemma C.1, we have that there exists ‖θt−1 − θ0‖2 ≤ τ , thus from Lemma C.4, we have that there exists positive constant C̄1 such that ‖g(x;θt−1)‖2 ≤ C̄1 √ mL, ‖g(x;θ0)‖2 ≤ C̄1 √ mL, consider the function defined as
ψ(a,a1, · · · ,at−1) = √√√√a>( t−1∑ i=1 λI + aia>i )−1 a,
it is then easy to verify that
ψ ( g(xt,k;θt−1)√
m , g(x1,a1 ;θ1)√ m , · · · , g(xt−1,at−1 ;θt−1)√ m
) = σt,k
ψ ( g(xt,k;θ0)√
m , g(x1,a1 ;θ0)√ m , · · · , g(xt−1,at−1 ;θ0)√ m
) = σ̄t,k,
then we obtain that the function ψ is defined under the domain ‖a‖2 ≤ C̄1 √ L, ‖ai‖2 ≤ C̄1 √ L then by taking the derivation w.r.t. ψ2, we have that
2ψ∂ψ = (∂a)> ( t−1∑ i=1 λI + aia > i )−1 a + a> ( t−1∑ i=1 λI + aia > i )−1 ∂a
+ a> ( t−1∑ i=1 λI + aia > i )−1 t−1∑ i=1 ( (∂ai)a > i + ai∂a > i )( t−1∑ i=1 λI + aia > i )−1 a,
by taking trace with both side and utilizing tr(AB) = tr(BA) and tr(α>β) = tr(αβ>), we have that
2 tr(ψ∂ψ) = tr ( 2(∂a)> ( t−1∑ i=1 λI + aia > i )−1 a
+ 2 t−1∑ j=1 (∂aj) > (( t−1∑ i=1 λI + aia > i )−1 aa> ( t−1∑ i=1 λI + aia > i )−1 aj ) ,
thus by setting C = (∑t−1
i=1 λI + aia > i
)−1 for simplicity and decompose C = Q>DQ,b = Qa
where D = diag(%1, · · · , %p) as the eigen-value of C, we have that
∇aψ = Ca√ a>Ca
, ‖∇aψ‖2 = √ a>C2a
a>Ca =
√ b>D2b
b>Db = √√√√∑di=1 b2i %2i∑d i=1 b 2 i %i ≤ 1/ √ λ
where the last inequality is from the fact that C 1/λI, which indicates that all eigen-value %i ≤ 1/λ, for the same reason, we have
‖∇aiψ‖2 = ‖Caa>Cai‖2√
a>Ca ≤ ‖ai‖2 ‖Caa>C‖2√ a>Ca = ‖ai‖2‖Ca‖2 ‖C>a‖2√ a>Ca ≤ ‖ai‖‖a‖/ √ λ.
Thus under the domain that ‖a‖2 ≤ C̄1 √ L, ‖ai‖2 ≤ C̄1 √ L, we have that
‖∇aψ‖2 ≤ 1/ √ λ, ‖∇aiψ‖2 ≤ C̄21L/ √ λ.
Then, Lipschitz continuity implies |σt,k − σ̄t,k| = ∣∣∣∣ψ(g(xt,k;θt−1)√m , g(x1,a1 ;θ1)√m , · · · , g(xt−1,at−1 ;θt−1)√m ) − ψ ( g(xt,k;θ0)√
m , g(x1,a1 ;θ0)√ m , · · · , g(xt−1,at−1 ;θ0)√ m )∣∣∣∣ ≤ sup{‖∇aψ‖2} ∥∥∥∥g(xt,k;θt−1)√m − g(xt,k;θ0)√m ∥∥∥∥
2
+ t−1∑ i=1 sup{‖∇aiψ‖2} ∥∥∥∥g(xi,ai ;θi)√m − g(xi,ai ;θ0)√m ∥∥∥∥ 2
≤ 1√ λ ∥∥∥∥g(xt,k;θt)− g(xt,k;θ0)√m ∥∥∥∥
2
+ C̄21L√ λ t−1∑ i=1 ∥∥∥∥g(xi,ai ;θi)− g(xi,ai ;θ0)√m ∥∥∥∥ 2 .
(C.1) By Lemma C.3 with τ = 2 √ t/mλ, there exist positive constants C̄2 and C̄3 so that each gradient difference in (C.1) is bounded by
1√ m ‖g(x;θ)− g(x;θ0)‖2 ≤ C̄2
√ logmτ1/3L3‖g(x;θ0)‖2/ √ m
≤ C̄3 √ logmt1/6m−1/6λ−1/6L7/2.
Thus, since we obtain that there exists constant C5 such that |σt,k − σ̄t,k| ≤ C1 √ logmt7/6m−1/6λ−2/3L9/2,
where we use the fact that C1 = max{C̄3, C̄3C̄21} and L ≥ 1 to merge the first term into the summation. This inequality is based on Lemma C.1, Lemma C.3 and Lemma C.4, thus it holds with probability at least 1− 3δ. Replacing δ with δ/3 completes the proof.

heading: C.2 PROOF OF LEMMA B.5
text: Proof of Lemma B.5. Setting τ = 2 √ t/mλ, we have the condition on the network m and learning rate η satisfy all of the condition needed by Lemmas C.1 to C.5. From Lemma C.1 we have ‖θt−1− θ0‖2 ≤ τ . Then, by Lemma C.2, there exists a constant C1 such that
|f(xt,k;θt−1)− 〈g(xt,k;θ0),θt−1 − θ0〉| ≤ C1t2/3m−1/6λ−2/3L3 √ logm, (C.2)
Using the bound on θt−1−θ0−Ū−1t−1J̄t−1rt−1/m provided in Lemma C.1 and the norm of gradient bound given in Lemma C.4, we have that there exist positive constants C̄1, C̄2 such that
|〈g(xt,k;θ0),θt−1 − θ0〉 − 〈g(xt,k;θ0), Ū−1t−1J̄t−1rt−1/m〉| ≤ ‖g(xt,k)‖2‖θt−1 − θ0 − Ū−1t−1J̄t−1rt−1/m‖2
≤ C̄1 √ mL ( (1− ηmλ)J √ t/(mλ) + C̄2m −2/3 √ logmL7/2t5/3λ−5/3(1 + √ t/λ) ) = C2(1− ηmλ)J √ tL/λ+ C3m −1/6 √ logmL4t5/3λ−5/3(1 + √ t/λ), (C.3)
where C2 = C̄1, C3 = C̄1C̄2. Combining (C.2) and (C.3), we have∣∣f(xt,k;θt−1)− 〈g(xt,k;θ0), Ū−1t−1J̄t−1rt−1/m〉∣∣ ≤ C1t2/3m−1/6λ−2/3L3√logm + C2(1− ηmλ)J √ tL/λ
+ C3m −1/6 √ logmL4t5/3λ−5/3(1 + √ t/λ),
which holds with probability 1−3δ with a union bound (Lemma C.4, Lemma C.1, and Lemma C.2). Replacing δ with δ/3 completes the proof.

heading: C.3 PROOF OF LEMMA B.7
text: Proof of Lemma B.7. From the definition of Kt, we have that
log det(I + λ−1Kt) = log det ( I + t∑ i=1 g(xi,ai ;θ0)g(xi,ai ;θ0) >/(mλ) )
≤ log det ( I + T∑ t=1 K∑ k=1 g(xi,ai ;θ0)g(xi,ai ;θ0) >/(mλ)) ) = log det(I + K/λ)
≤ log det(I + H/λ+ (H−K)λ) + T (λ− 1) ≤ log det(I + H/λ) + 〈(I + H/λ)−1, (K−H)/λ〉 ≤ log det(I + H/λ) + ‖(I + H/λ)−1‖F ‖(K−H)‖F /λ ≤ log det(I + H/λ) + √ TK‖(K−H)‖F
≤ log det(I + H/λ) + 1 where the the first inequality is because the double summation on the second line contains more elements than the summation on the first line. The second inequality utilizes the definition of K in Lemma C.5 and H in Definition 3.1, the third inequality is from the convexity of log det(·) function, and the forth inequality is from the fact that 〈A,B〉 ≤ ‖A‖F ‖B‖F . Then the fifth inequality is from the fact that ‖A‖F ≤ √ TK‖A‖2 if A ∈ RTK×TK and λ ≥ 0. Finally, the sixth inequality utilizes Lemma C.5 by setting = (TK)−3/2 with m ≥ C1L6T 6K6 log(TKL/δ), where we conclude our proof.

heading: C.4 PROOF OF LEMMA B.9
text: Proof of Lemma B.9. Set τ in Lemma C.4 as 2 √ t/(mλ). Then the network width m and learning rate η satisfy all of the condition needed by Lemma C.1 to C.5. Hence, there exists C1 such that ‖g(x;θ)‖2 ≤ ‖g(x;θ)‖F ≤ C1 √ mL for all x, since it is easy to verify that U−1t λ−1I. Thus we have that for all t ∈ [T ], k ∈ [K],
σ2t,k = λg >(xt,k;θt−1)U −1 t−1g(xt,k;θt−1)/m ≤ ‖g(xt,k;θt−1)‖22/m ≤ C25L.
Therefore, we could get that σt,k ≤ C1 √ L, with probability 1 − 2δ by taking a union bound (Lemmas C.1 and C.4). Replacing δ with δ/2 completes the proof.
D AN UPPER BOUND OF EFFECTIVE DIMENSION d̃
We now provide an example, showing when all contexts xi concentrate on a d′-dimensional nonlinear subspace of the RKHS space spanned by NTK, the effective dimension d̃ is bounded by d′. We consider the case when λ = 1, L = 2. Suppose that there exists a constant d′ such that for any i > d′, 0 < λi(H) ≤ 1/(TK). Then the effective dimension d̃ can be bounded as
d̃ = log det(I + H)
log(1 + TK) ≤ TK∑ i=1 log(1 + λi(H)) ≤ TK∑ i=1 λi(H) = d′∑ i=1
λi(H)︸ ︷︷ ︸ I1 +
TK∑ i=d′+1
λi(H)︸ ︷︷ ︸ I2 .
For I1 and I2 we have
I1 ≤ d′∑ i=1 ‖H‖2 = Θ(d′), I2 ≤ TK · 1/(TK) = 1,
Therefore, the effective dimension satisfies that d̃ ≤ d′+ 1. To show how to satisfy the requirement, we first give a charcterization of the RKHS space spanned by NTK. By Bietti & Mairal (2019); Cao et al. (2019) we know that each entry of H has the following formula:
Hi,s = ∞∑ k=0 µk N(d,k)∑ j=1 Yk,j(xi)Yk,j(xs),
where Yk,j for j = 1, . . . , N(d, k) are linearly independent spherical harmonics of degree k in d variables, d is the input dimension, N(d, k) = (2k + d− 2)/k · Cd−2k+d−3, µk = Θ(max{k−d, (d− 1)−k+1}). In that case, the feature mapping (√µkYk,j(x))k,j maps any context x from Rd to a RKHS space R corresponding to H. Let yi ∈ R denote the mapping for xi. Then if there exists a d′-dimension subspace R′ such that for all i, ‖yi − zi‖ 1 where zi is the projection of yi onto Rd′ , the requirement for λi(H) holds.

Review summaries:
The paper proposes neural thompson sampling (TS) - a method to run TS without assuming that the reward is a linear function of the context, as is generally assumed in literature. This is not the first paper to use neural networks for TS, however existing papers either a) used TS only in the last layer, or b) maintained uncertainty over the weights and sampled the entire neural network. This paper instead maintains a single network that computes the mean of the reward distribution of an arm. 

The paper proposes a novel Thompson sampling algorithm for neural networks which can be applied to any arbitrary, bounded reward function. While existing works apply Thompson sampling (TS) to neural networks in a heuristic way (e.g., sampling parameters in the last layer only), this algorithm considers the posterior distribution of all the parameters and is the first to provide a theoretical, tight regret upper bound. The work builds on the neural tangent kernel theory, which enables the use of techniques developed for linear reward functions (Agrawal and Goyal, 2013). Actually, the paper is analogous to the work of Zhou et al. (2020) which proposed the NeuralUCB algorithm by combining the neural tangent kernel theory and the Linear UCB methodology (Abbasi-Yadkori et al., 2011).