Neural Thompson Sampling
Authors: Weitong ZHANG
Dongruo Zhou
Lihong Li
Quanquan Gu
Venue: ICLR 2021 Poster (2021)
Keywords: Deep Learning
Contextual Bandits
Thompson sampling

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^{1/2})$, 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.

Published as a conference paper at ICLR 2021
NEURAL THOMPSON SAMPLING
Weitong Zhang
Dongruo Zhou
Department of Computer Science University of California, Los Angeles Los Angeles, CA, USA, 90095 wt. zhang@ucla.ed.
Department of Computer Science University of California, Los Angeles Los Angeles, CA, USA, 90095 drzhouêcs www..caa...... edu
Lihong Li Google Research USA Lihongegoogle.com
Quanquan Gu
Department of Computer Science University of California, Los Angeles Los Angeles, CA, USA, 90095 qguê cs ucla.edu
ABSTRACT
Thompson Sampling (TS) one of the most effective algorithms for solving con- textual multi-armed bandit problems. In this paper, we propose new algorithm, called Neural Thompson Sampling, which adapts deep neural networks for both exploration and exploitation. At the core of our algorithm is novel posterior dis- tribution the reward, where its mean is the neural network approximator, and its variance is built upon the neural tangent features of the corresponding neu- ral network. We prove that, provided the underlying reward function is bounded, the proposed algorithm is guaranteed to achieve a cumulative regret of (3) which matches the regret of other contextual bandit algorithms in terms of total round number T. Experimental comparisons with other benchmark bandit algo- rithms various data sets corroborate our theory.
INTRODUCTION
The stochastic multi-armed bandit (Bubeck & CisaaBianchij 2012 Lattimore & Szepesvári 2020) has been extensively studied, as an important model to optimize the trade-off between exploration and exploitation sequential decision making. Among its many variants, the contextual bandit is widely used in real-world applications such recommendation (Li et al. 2010), advertising (Grae- pel et al. 2010), robotic control (Mahler et al. 2016), and healthcare (Greenewald et al.) 2017).
In each round of contextual bandit, the agent observes feature vector (the "context") for each of the arms, pulls one of them, and return receives a scalar reward. The goal is to maximize the cumulative reward, minimize the regret (to be defined later), in 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 sam- ple 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 explore in contextual bandits with neu- ral network models (Blundell et al. 2015: Kveton et al.) [2000] Lu & Van Roy] 2017] Riquelme al. 2018). Riquelme al. (2018) proposed NeuralLinear, which maintains a neural network and chooses the best arm in each round according to 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 out- put. 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). De- spite the reported empirical success, strong regret guarantees for TS remain limited to relatively simple models, under fairly restrictive assumptions the reward function. Examples are linear

---

Published as a conference paper at ICLR 2021
functions (Abeille & Lazaric 2017 Agrawal & Goyal 2013 Kocá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 threefold. First, we propose new algo- rithm, Neural Thompson Sampling (NeuralTSS) to incorporate TS exploration with neural networks. It differs from NeuralLinea (Riquelme et al. 2018) by considering weight uncertainty in all layers. and from other neural network-based TS implementations (Blundell et al. 2015 K Kveton et al. 2020) by sampling the estimated reward from the posterior (as opposed to sampling parameters).
Second, we give regret analysis for the algorithm, and obtain an ((dVT) regret, where d is the effective dimension and 7 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 bench- marks. Experiments show that NeuralTS yields competitive performance, in comparison with state- of-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 de- note by [k| the set 21. }} for positive integers k. For two non-negative sequence {an); (b,), an = (b,.) means that there exists positive constant C such that on S Cbn, and we use (-) to hide the log factor in O(). We denote by || ||2 the Euclidean norm of vectors and the spectral norm of matrices, and by || | the Frobenius norm of a matrix.
2 PROBLEM SETTING AND PROPOSED ALGORITHM
In this work, we consider contextual K-armed bandits, where the total number of rounds T is known. At round E (T), the agent observes K contextual vectors (x,,s E Rd k E [K]). Then the agent selects an arm a, and receives a reward rt,e, Our goal is to minimize the following pscudo regret:
R = E
(naa re,0.)
(2.1)
where of is the optimal arm at round t that has the maximum expected reward: of [r E[rea]. To estimate the unknown reward given a contextual vector x, we use a fully connected neural network fx; 0) of depth 2 2, defined recursively by
f1 W1
f: = W, ReLU(fi-1,, 2515L,
[x: 0) Vmfl.
(2.2)
where ReLU(xr) == max(x, 0}, m is the width of neural network, W1 E mxd WT E R mm 2 < I < L, WL E <l 0 = (vee Wt W.):... vvec(W) (WL)) E RP is the collection of parameters of the neural network, = dm + m² (L- 2) + m. and g(x; 0 = Vos(x; 0) is the gradient of [(x; 0) w.r.t. O.
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 ( Once the reward is observed, it updates the posterior (lines p & TO). The mean of the posterior distribution is the output of the neural network, whose parameter is the solution to the following minimization problem:
min L( = iif(x,. -ri,a,1,/22 12/2 mA @ 0.13//2. 0
(2.3)
We can that 2..3 an regulluar square loss minimization problem, where the regularization term centers at the randomly initialized network parameter 0g. We adapt gradient descent to solve 2.3 with step size 7) and total number of iterations J.
2

---

Published as a conference paper at ICLR 2021
Algorithm Neural Thompson Sampling (NeuralTS)
Input: Number of rounds T, exploration variance v, network width m. regularization parameter A.
1: Set Ug = AI
2: Initialize 0g = (vec(W) (1):: ... vee (WL)
RP, where for each < < L 1, W, [W. 0; 0, W), each entry of W is generated independently from (N, 4/m); W. each entry of w is generated independently from N (0, 2/m).
(w")
3: for ( 1,... ,T do
4: for k 1........ 1....... do
5:
ii Ag (x 0--1) - g(x, 0m-1)/m Sample estimated reward Fe,k (f( 11-1), o,, end for
6:
7:
8:
Pull arm and receive reward Tt, where a, = argmax, Tt,a
9:
Set 02 to be the output of gradient descent for solving 2..
10: U, = U,=U,-1 + g(xi,a;; (e)g(xxr, :..) /m
end for
A few observations about our algorithm are in place. First, compared to typical ways of implement- ing 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 to build connection between Algorithm and recent work about deep learning theory (Allen-Zhu et al. 2018 Cao & Gu 2019), in order to obtain theoretical guarantees will be shown in the section.
Third, different from linear or kernelized TS (Agrawal & Goyal 2013 Chowdhury & Gopalan 2017), whose posterior be computed in closed forms, NeuralT'S solves non-convex optimiza- tion problem (2.3) by gradient descent. This difference requires additional techniques in the regret analysis. Moreover, stochastic gradient descent can be used solve the optimization problem with a similar theoretical guarantee (Allen-Zhu et al.) 2018 Du et al. 2018 Zou et al. (019). For sim- plicity of exposition, we will focus on the exact gradient descent approach.
REGRET ANALYSIS
In this section, provide regret analysis of NeuralTS. We assume that there exists an unknown reward function such that for any $ t $ T and S k K,
Tt, = h(x,,)) + Ee.k. with |h(x),))) <
where } forms an R-sub-Gaussian martingale difference sequence with constant R > 0, i.c., Elexp(XCt,e)) (1:t, x1 S exp(X2 R2) for
Such an assumption on the noise se- quence is widely adapted in contextual bandit literature (Agrawal & 2013] Bubeck & Cesa-
(2033
Bianchi 2012: Chowdhury & Gopalan 2017 Chu et al. 2011 Lattimore Szepesvári 2020 Valko
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, denote by {x' 17 the set of observed contexts of all arms and all rounds: (xx
where = k(t 1) k.
Definition 3.1 (Jacot al. (018)). Define
Σ
H
و (x
x) A
(1+1) = 2E (u.))~N(O (0) max 0} max fox 0},
((41) -2H!! - 1uu > 0) (1 > 0) - (41)
Then, H (4) + (()))/2 is called the neural tangent kernel matrix the context set.
3

---

Published as a conference paper at ICLR 2021
The NTK technique builds 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 del + H/A) log + TK/A)
Remark 3.3. The effective dimension is 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 (211)), which also considers UCB-based exploration. Compared with the maximum information gam % used in Chowdhury & Gopalan (2017), one can verify that their Lemma 3 shows that Y 2 log det(I H/A))22 Therefore, "/t and are of the same order up a ratio of (2 log(1 (1 + TK/A)) Furthermore, d can be upper bounded if all contexts x; are nearly on some low-dimensional subspace of the RKHS space spanned by NTK (Appendix D)
We will make regularity assumption the contexts and the corresponding NTK matrix H. Assumption 3.4. Let H be defined in Definition 3.1 There exists Ao > O, such that H > AoI. In addition, for any & E [T], k E [K], |x,xll2 and Xt,kly [x.,lj++/22-
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 context Xr,a ensures that the initial output of neural network [x; 0o) is with the random initialization suggested in Algorithm|] [ The con- dition x is easy to satisfy, since for any context x, one always construct new context x as (x/(v2]|xlll) X (22
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 X 1
1/T,
B + Rv (og(( + TK/A) + 2 1og(1/5) where B max 1126 n 22h H
1h with
= ..... (((x) TK h(xTTK))* T)_ and R is the sub-Gaussian parameter. In line 9 of Algorithm
I set
7 Ci (m. + mLT)-1 and J= (1 (T/ + log ( LX- log(1 (1))))) 7)) for some positive
constants C1, C2. If the network width m satisfies:
m 2 poly (A, K, L, logglo/)0,111
then, with probability at least 1 - 6, the regret of Algorithm bounded as
Pr S C1(1 + eT) (x + TK) + 1)7 + (4 C1 2lgg(3/8)7 + +5, where Cg, C4 are some positive absolute constants, and er A T 2lo K.
Remark 3.6. The definition B in Theorem 3.5 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 the function space induced by NTK, i.e., |/A|| x < 00, we have vh H- S ||i|| according to Zhou et al. 2019). which suggests that B < max max(11/22e v2llbllx)
Remark 3.7. Theorem 3.5 implics the regret of NeuralTS is on the order of (dT11/2) This re-
sult matches the -fate-of-the-aa regret bound in Chowdhury & Gopalan (2017); Agrawal & Goyal
2013): /Zho et al. (2019); Kveton et al. 22020).
Remark 3.8. In Theorem 3.5 the requirement of m is specified in Condition and the proof of Theorem 3.5 which is a high-degree polynomial in the time horizon T, number of layers and number of actions K. However, in our experiments, we can choose reasonably small (e.g.. m = 100) to obtain good performance of NeuralTSS. See Appendix I for more details. This discrepancy between theory and practice due to the limitation of current NTK theory (Du al.) 2018 Allen-Zhu et al., 2018: Zou et al., 2019). Closing the gap is venue for future work.
Remark 3.9. Theorem 3.5 suggests that we need to know before we run the algorithm in order to set m. When 7' is unknown, we can use the standard doubling trick (See e.g.. CCea--Bianch & Lugosi (2006)) to set m adaptively. In detail, we decompose the time interval (0, +00) as union of overllllgg intervals [2e, 2*+1). When 2a < t < 2 we restart NeuralT'S with the input
T = 29+1 It can be verified that similar Ö(dVT) regret still holds.
4

---

Published as a conference paper at ICLR 2021
4 PROOF OF THE MAIN THEOREM
This section sketches the proof of Theorem 3.5 with supporting lemmas and technical details pro- vided in Appendix B
While the proof roadmap is similar to previous work Thompson Sam- pling (e.g.. Agrawal & Goyal] 2013) Chowdhury & Gopalan 2017 Kocák et al.) 2014] K al., (020), our proof needs carefully track the approximation error of neural networks for ap- proximating 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 2 C max (0003//(0(((TT13)
7 (ogg (ax (xo (A0". LTY C1.2 x- VT/A)0
m [log m] -3 2 CTL + > - L
where C' is positive absolute constant.
For any L, we define an event E/ as follows
Eg = fw E Fit1 : Vk E [K]. FL. - f(xLA:: 01-1) S cvvon
(4.1)
where a Vll log K. Under event & the difference between the sampled reward fi.k and the estimated mean reward fxxx,x 12- can be controlled by the reward's posterior variance.
We also define an event E. follows E/ {w F.: Vk E [K], ((xx,00-111 1(xx,x)) S vork + {(m)),
(4.2)
where c(m) defined as <(m) =p(mm + C1, mymAa TT//X
(m(m) C2,TT233 1/1111//////// 2/ /lg m + C,,3m-1/8 VlogmI.TT/// 5//3 + (T/A)
+ Ce. B + / det H/A) + 2 2log(1/0))
(on(1//)))llmmml /lllommm////// 1/6 2/3 1/2
(4.3)
and i1 are some positive absolute constants. Under event E,", the estimated mean reward (xx: 0,-1) based on the neural network is similar to the true expected reward (xx,,,). Note that the additional term e(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 Agraling/Agrawal Goyal (2013); Chowdhury & Gopalan (2017). where there is no approximation error.
The following two lemmas show that both events E7 and Ef' happen with high probability. Lemma 4.2. For any E [7]. Pr (ET (F) 2 1 1-1-?
Lemma 4.3. Suppose the width of the neural network m satisfies Condition 4.1 Set C(mA +
mL.T) then we have Pr (Al E (7),&() 2 1 - 5, where C' is an positive absolute constant.
The next lemma gives lower bound of the probability that the sampled reward 7 Fis larger than true reward up to the approximation error e(m).
Lemma 4.4. For any E [T). E [K]. we have Pr (Fr,s + <(m) > (x.. 2 (1
Following Agrawal & Goyal (2013), for any time I, 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 not. Note that the optimal arm is included in the group of unsaturated arms. More specifically, we define the set of saturated arms S, as follows
S = [ E [K],A(xx,a; h(xx,))) 2 (1 + c.)oor + 2e(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 unsaturated arm can be bounded by the standard deviation plus the approximation error e(m).
The following lemma shows that the probability of pulling saturated arm is small in Algorithm
5

---

Published as a conference paper at ICLR 2021
Lemma 4.5. Let de be the arm pulled round [T] Then, Pr (ar & FtlFi, E(¹)
1
lev 12.
The next lemma bounds the expectation of the regret at each round conditioned on E/-
Lemma 4.6, Suppose the width of the neural network m satisfies Condition 4.1 Set 1) CimmA+ mITT)= then with probability at least 6, we have for all & (7] that
[[h((x,,;;) h( m F E - C2 + L.) 0z F, Ef 4c(m) 2t
where C1, C2 are some positive absolute constants.
Based on Lemma 4.6 define Â (h(x),a;) h (xx,,a)) 1(E"), and
X = A. (Ca(1+ ce)uv min + 4e + 2 Yt Σ X₁
(4.5)
where Co is the same with constant C in Lemma 4.6 By Lemma 4.6 we can verify that with
probability least 1- 6, {Yr} forms a super martingale sequence since - EX, S 0. By Szuma-Hoeffding inequality (Hoeffding) 1963), we can prove the following lemma.
Lemma 4.7. Suppose the width the neural network m satisfies Condition 4.1 C (mm + mLT) we have, with probability least 1 8, that
Then set =
T
A < 4 +
minfor.a.. 1}
(4 C11+ cT) 4e llg((1/
where C1, C22 C3 are some positive absolute constants,
The last lemma is used to control Σ min(or,a. 1} in Lemma 4.7
Lemma 4.8. Suppose the width of the neural network m satisfies Condition 4.1 Then set = Ci Ci(m) + mLL) 1 have, with probability least 1 5, it holds that
Σ Cminfor,,,11 1) V2xT(ālog(1 + TK) + + 13/ Vlog mm 1
2/3 1//2
where C1, C2 are some positive absolute constants.
With all the above lemmas, ready to prove Theorem 3.5
Proof of Theorem 3.5 By Lemma 4.3 E/¹ holds for all E [7] with probability at least 1 - 6.
Therefore, with probability least
have
RT Σ (h(x),a;) h(xx,a))) 1((7))
T S <4Tc(m) + x² + +il1 + 3
min mon 1)
+ + + 2log((/00
c 2 ( +TK)) 13713/6 Vlo 11/6 9/2
=²
cT)ull) 4Te(m) + 4((m))+4)m)))1100007) C2 (1 22og(1//111111
(2XT(2 - C3 1/6 log mm 1/6 2/3 9/2
Ci(1 +r
2 +
-
Cc,((1 -1-1)mm)) /TLA/ATT 22og

---

Published as a conference paper at ICLR 2021
where C1 C2, C3 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 (.3). By setting
Ca(mA + mLT) and J (1+ (lgg( log(T log( 1 D)))/Ca, we have
C. - (1-)mmA) TTL/XA4 + /2log(1/001) -
Then choosing m such that
Vlogooggee log mm 1//6 21/6X-2/31 - cp(m) VVlggT++2oog0/0111
RT can be further bounded by
- + 1)T + (4+ CL(L+ +
Ry S C1 cT) C 22
Taking union bound over Lemmas 4.3 4.7 and 4.8. the above inequality holds with probability 1- 36. By replacing å with 6/3 and rearranging terms, complete the proof.
EXPERIMENTS
This section gives empirical evaluation of algorithm in several public benchmark datasets, including adult, covertype, magic te celescope, mushroom and shuttle, all from UCI (Dua & Graff 2017). as well as MNIST (LeCun al., 2010). The algorithm compared
to several typical baselines: linear and kernelized Thompson Sampling (Agrawal & Goyal 2013
Chowdhury & Gopalan 2017), linear and kernelized UCB (Chu al., [011] Valko et al. 2013).
BootstrapNN (Osband et 20166) Riquelme et al.] 2018), and c-greedy for neural networks. Boot- strapNN trains multiple neural networks with subsampled data, and at each step pulls the greedy ac- tion based on randomly selected network. It has been proposed way to approximate Thompson Sampling (Osband Van Roy
2015 Osband et al. 2016b).
5.1 EXPERIMENT SETUP
To transform these classification problems into multi-armed bandits, adapt the disjoint models et al. 2010)) to build a context feature vector for each arm: given an input feature x E Rd of k-class classification problem, we build the context feature vector with dimension kd as: X1
LLi
(x: 0: 0), X2 = x0:x;-. -)) X (0; O:-.. :x). Then, the algorithm generates a set of predicted reward following Algorithm I and pulls the greedy arm. For these classification problems, if the algorithm selects correct class by pulling the corresponding arm, it will receive reward as 1, otherwise The cumulative regret over time horizon T measured by the total mistakes made by the algorithm. All experiments are repeated 8 times with reshufiled data.
We set the time horizon of our algorithm to 10 000 for 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 the diagonal elements of U as an approximation of U-1 Also, since calculating the kernel matrix is expensive, the performance for the rest of the time, similar to previous work (Riquelme et al. 2018 Zhou et al., 2019). Due to space limit, defer the results adult, t, covertype and magic e te 1 escope, as well as further experiment details, to Appendix A this section, we only show the results on mushroon, shuttle and MNIST.
stop training at t 1000 and keep evaluating
5.2 EXPERIMENT PERFORMANCE OF NEURAL THOMPSON SAMPLING
The experiment results of Neural Thompson Sampling and other benchmark algorithms are shown in Figure [] few observations are place. First, Neural Thompson Sampling's 's performance 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 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, particular when neural networks are used.

---

Published as a conference paper at ICLR 2021
Lear RDB
X4
1000
SEB
Seardf (own)
2000
1993
1830
580
2000
238
0053
MNIST
Mushroom
Shuttle
Figure 1: Comparison of Neural Thompson Sampling and basclines UCI datasets and MNIST dataset. The total regret measures cumulative classification errors made by an algorithm. Results averaged over 8 runs with standard errors shown shaded areas.
5.3 EXPERIMENT II: ROBUSTNESS TO REWARD DELAY
This experiment inspired by practical scenarios where reward signals are delayed, due to various constraints, as described by Chapellee & Li (201)). We study how robust the two most competitive methods from Experiment 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 batches when the algorithms will update their models. The experiment setup otherwise identical to Experiment Here, we vary the batch size (i.e., the amount of reward delay), and Figure shows the corresponding total regret. Clearly, we recover the result Experiment when the delay is O. 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 's randomized exploration nature that encourages exploration between batches. We, therefore, expect wider applicability of Neural TS in practical applications.
Mas
1902
300
330
200
198
MNIST
(b) Mushroom
(c) Shuttlc
Figure 2: Comparison of Neural Thompson Sampling and Neural UCB on UCI datasets and MNIST dataset under different scale of delay. The total regret measures cumulative classification errors made by an algorithm. Results are averaged over 8 runs with standard errors shown as error bar.
RELATED WORK
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 the introduction, and are not repeated here.
Upper confidence bound UCB (Agrawal 1995 Auer et al. 2002 Lai & Robbins 1985 is
widely used alternative to Thompson Sampling for exploration. This strategy is shown to achieve near-optimal regrets in range of settings, such as linear bandits (Abbasi-
al. 201 Auer
2002
Chu et al. 2011), generalized linear bandits (Filippi et al. 2010;Jun et al. 2017 et al.
2017 and kernelized contextual bandits /Vlkoo et al.) 2013).
Neural networks are increasingly used in contextual bandits. In addition to those mentioned ear-
lier Blundell al. 2015 Kveton al. 2020 Lu & Van Roy 2017 Riquelme et al.) 2018 Zahavy
8

---

Published as a conference paper at ICLR 2021
& Mannor 2019) used deep neural network to provide feature mapping and explored only the last layer. Schwenk & Bengio (2000) proposed an algorithm by boosting the estimation multiple deep neural networks. While these methods all show promise empirically, no regret guarantees known. Recently, Foster & Rakhlin (2020) proposed a special regression oracle and randomized exploration for contextual bandits with general function class (including neural networks) along with theoretical analysis. ZZhou et al. (2019) proposed a neural UCB algorithm with near-optimal regret based UCB exploration, while this paper focuses on Thompson Sampling.
CONCLUSIONS
In this paper, we adapt Thompson Sampling neural networks. Building recent advances in deep learning theory, we are able to show that the proposed algorithm, NeuralTS, enjoys a (dT")/2 regret bound. We also show the algorithm works well empirically on benchmark problems, in com- parison with multiple strong baselines.
The promising results suggest few interesting directions for future research. First, our analysis needs NeuralTSS to perform multiple gradient descent steps to train the neural network 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, ((VaT) regret has been established for parametric bandits with linear and generalized linear reward functions. It is open problem how to adapt NeuralTS to achieve the same rate. Third, Allen-ZZhu & Li (2019) suggested that neural networks may behave differently from neural tangent kernel under some parameter regimes. It is interesting to investigate whether similar results hold for neural contextual bandit algorithms like NeuralTS.
ACKNOWLEDGEMENT
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-190411 183. The views and conclusions contained in this paper are those of the authors and should not be inter- preted representing any funding agencies.
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Mare Abeille and Alessandro Lazaric. Linear Thompson sampling revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 176-184, 2017.
Rajeev Agrawal. Sample mean based index policies by o(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 2754):105411075 1995.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pp. 127-135, 2013.
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems, pp. 9015-9025, 2019.
Zeyuan Allen-Zhu Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint 1mXiv:811.00990 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv: 2019.
Peter Auer. Using confidence bounds for exploitation-exxplrraion trade-offs. Journal of Machine Learning Research, 3(N0v):397-422, 2002.
Peter Auer, Nicolò Desa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-2555 256. 2002.

---

Published as a conference paper at ICLR 2021
Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through Bayesian deep Q-networks. In Proceedings of the 2018 Information Theory and Appli- cations Workshop, pp. 1-9, 2018.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In Advances in Neural Information Processing Systems, pp. 1 12904, 2019.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural network. In Proceedings of the 32nd International Conference Machine Learning, pp- 1613-1622, 2015.
Sébastien Bubeck and Nicolò Cesa-Bianche Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, pp. 10835-10845, 2019.
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Ding-Xuan Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint 1912.1 2019.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Advances in neural information processing systems, pp. 2249-2257, 2011.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference Machine Learning, pp. 844 853, 2017.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings the 14th International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL des.uci.ed udi.eld/ml
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, pp. 586-594, 2010.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Os- band, Alex Graves, Volodymyr Mnih, Rémi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In Proceedings of the 6th Interna- tional Conference on Learning Representations, 2018.
Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. arXiv preprint arXiv:2002.04492 2020.
Thore Graepel, Joaquin Quinonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale Bayesian click-through rate prediction for sponsored search advertising in Microsoft's 's Bing search engine. In Proceedings of the 27th International Conference on Machine Learning, pp- 13-20, 2010.
Kristjan Greenewald, Ambuj Tewari, Susan Murphy, and Predag Klasnja. Action centered contextual bandits. In Advances in Neural Information Processing Systems 30, pp. 5977-5985, 2017.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301): 1963.
Matthew W Hoffman, Bobak Shahriari, and Nando de Freitas. Exploiting correlation and budget constraints in bayesian multi-armed bandit optimization. arXiv preprint arXiv:1303. 1303.6746, 2013.
10

---

Published as a conference paper at ICLR 2021
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and gen- eralization in neural networks. In Advances in Neural Information Processing Systems, pp. 8571- 8580, 2018.
Kwang-Sung Jun, Aniruddha Bhargava, Robert D. Nowak, and Rebecca Willett. Scalable gen- eralized linear bandits: Online computation and hashing. In Advances in Neural Information Processing Systems 30. pp. 99-109, 2017.
Jaya Kawale, Hung Hai Bui, Branislav Kveton, Long Tran-Thanks and Sanjay Chawla. Efficient Thompson sampling for online matrix-factorizze Information Processing Systems 28, pp. 1297-1305, 2015.
recommendation. In Advances in Neural
Tomáš Kocák, Michal Valko, Rémi Munos, and Shipra Agrawal. Spectral Thompson sampling. In 28th AAAI Conference on Artificial Intelligence, 2014.
Tomáš Kocák, Michal Valko, Rémi Munos, and Shipra Agrawal. Spectral Thompson sampling. In Proceedings of the 28th AAAI Conference on Artificial Intelligence, pp. 1911-1917, 2014.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration generalized linear bandits. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2020.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules, Advances in Applied Mathematics, 6(1):4-22, 1985.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. 2010.
Available: http://yann.lecun http:///ammleeuu..comeedddmmimm
Lihong Li. Wei Chu, John Langford, and Robert Schapire. cantextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, pp. 661-670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou Provably optimal algorithms for generalized linear contex- tual bandits. In Proceedings of the 34th International Conference on Muchine Learning- Volume 70, pp. 2071 2071-2080. JMLR. org. 2017.
Zachary C. Lipton, Jianfeng Gao, Lihong Li, Xiujun Li, Faisal Ahmed, and Li Deng. BBQ- networks: Efficient exploration in deep reinforcement learning for task-oriented dialogue systems. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 5237-5244, 2018
Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. In Advances in Neural Information Processing Systems 30, pp.
2017.
Jeffrey Mahler, Florian T Pokorny, Brian Hou, Melrose Roderick, Michael Laskey, Mathieu Aubry, Kai Kohlhoff, Torsten Kröger, James Kuffner, and Ken Goldberg. Dex-net 1.0: A cloud-based network of 3d objects for robust grasp planning using multi-armed bandit model with correlated rewards. In 2016 IEEE international conference robotics and automation (ICRA), pp. 1957- 1964. IEEE, 2016.
Ian Osband and Benjamin Van Roy. Bootstrapped thompson sampling and deep exploration. arXiv preprint
2015.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems 29, pp. 4026-4034, 2016a.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Advances in neural information processing systems, pp. 4026-4034, 2016b.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep Bayesian bandits showdown: An empirical comparison of Bayesian deep networks for Thompson sampling. arXiv preprint 1802 2018.
11

---

Published as a conference paper at ICLR 2021
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1211-1243, 2014.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. arXiv preprint 1rXiv:1707.02033 2017.
Holger Schwenk and Yoshua Bengio. Boosting neural networks. Neural computation, 12(8):1869- 2000.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-22 1933.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint 1xXiv:3309.60 2013.
Lin Yang and Mengdi Wang. Reinforcement leaning in feature space: Matrix bandit, kernels, and regret bound. arXiv preprint 19Xiv: 2019.
Tom Zahavy and Shie Mannor. Deep neural linear bandits: Overcoming catastrophic forgetting through likelihood matching. arXiv preprint arXiv: 01990108612, 2019.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based explo- ration. arXiv preprint arXiv: 1e:::991110000 1.04462, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep relu networks. Machine Learning, 1-26, 2019.
12

---

Published as a conference paper at ICLR 2021
A FURTHER DETAIL OF THE EXPERIMENTS IN SECTION
A.I PARAMETER TUNING
In the experiments, we shuffle all datasets randomly, and normalize the features so that their l norm is unity. One-hidden-layer neural networks with 100 neurons used. Note that we do not choose m as suggested by theory, and such 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 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 c- Greedy, we tune with a grid search on {0.01, 0.05, 0.1). For (A, used linear and kernel UCB / Thompson Sampling. we set À = following previous works (Agrawal & Goyal, 2013 Chowdhury & Gopalan 2017). and a grid search of E 0,1, to select the parameter with best performance. For the Neural UCB Thompson Sampling methods, All experiments are repeated
grid search on
{1, 10-1 10 10 10-3} and {10-1 10 10 10 10 1.0b)) 5j. 20 times, and the average and standard error reported.
A.2 DETAILED RESULTS
Table summarizes the total regrets measured at the last round on different data sets, with mean and standard deviation error computed based 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 shows the comparison between Neural Thompson Sampling and Neural UCB in delay reward settings.
Table I: Total regrets get at the last step with standard deviation attached
Adult
Covertype
Magid
MNIST
Mushroom
Shuttle
Round#
10000
10000
10000
10000
8 122
10000
Input Dim
2 x 15
2 x 55
2 x 12
10 x 784
2 23
7 x 9
Random
5000
5000
5000
9000
4062
8571
2097.5
3222.7
2604.4
2544.0
562.7
966.6
Linear UCB
+50.3
#67.2
#34.6
+235.4
+23.1
#39.0
2154.7
4297.3
2700.5
2781.4
643.3
1020.9
Linear TS
+40.5
1328.7
146.7
1338.3
+33.4
+42.8
2080.1
3546.2
2406.5
3595.8
199.0
166.5
Kernel UCB
+44.8
+175.7
#79.4
5580.1
#41.0
#39.4
2111.5
3659.9
2442.6
3406.0
291.2
283.3
Kernel TS
187.4
+113.8
164.
#411.7
+40.0
180.5
2097.3
3067.0
2269.4
1765.6
132.3
211.7
BooststrapNN
+39.3
#56.1
+27.9
+321.1
+8.6
+20.9
2328.5
3334.2
2381.8
1893.2
323.2
682.0
eps-greedy
+50.4
172.6
+37.3
193.7
+32.5
+79.8
2061.8
3012.1
2033.0
2071.6
160.4
338.6
NeuralUCB
+42.8
+87.0
+48.6
+922.2
195.3
+386.4
NeuralTSS
2092.5
2999.1
2037.4
1583.4
115.0
232.0
(ours) +48.0
774.3
+61.3
+ 198.5
+35.8
+149.5
Maggc is short for data set MagicTeelssoue
Using disjoint encoding thus NumofClass NumofFeatures
'Random pulling an arm at cach round
MMagic is short for data set MagicTelescope
13

---

Published as a conference paper at ICLR 2021
Table 2: Performance on total regret comparing with other methods on all datasets. Tuple (w/t/l indicates the times of the algorithm at that row wins, ties with or loses, compared to all other algorithms with t-test at 90% significant level.
Adult
Covertype
Magic
MNIST
Mushroom
Shuttle
Linear UCB
2/3/2
4/0/3
1/0/6
2/2/3
1/0/6
1/0/6
Linear TS
1/0/6
0/0/7
0/0/7
2/1/4
0/0/7
0/0/7
Kernel UCB
4/3/0
2/0/5
3/1/3
0/0/7
4/0/3
7/0/0
Kernel TS
2/3/2
1/0/6
2/0/5
1/0/6
3/0/4
3/3/1
BooststrapNN 2/4/1
5/0/2
5/0/2
4/3/0
5/2/0
3/3/1
eps- eps-greedy
0/0/7
3/0/4
3/1/3
4/2/1
2/0/5
2/0/5
NeuralUCB
6/1/0
6/1/0
6/1/0
3/3/1
5/1/1
3/3/1
NeuralTS
2/4/1
6/1/0
6/1/0
6/1/0
6/1/0
3/3/1
(ours)
Lana 75
208
355
Marm1: bust
1400
1200
PPofourd
#at/oand
(a) Adult
(b) Covertype
(c) Magic Telescope
Figure 3: Comparison of Neural Thompson Sampling and baselines on UCI datasets and MNIST dataset. The total regret measures cumulative classification errors made by an algorithm. Results averaged over multiple runs with standard errors shown shaded arcas.
4200
200
220
2000
(a) Adult
(b) Covertype
(c) Magic Telescope
Figure 4: Comparison of Neural Thompson Sampling and Neural UCB on UCI datasets and MNIST dataset under different scale of delay. The total regret measures cumulative classification errors made by an algorithm. Results are averaged over multiple runs with standard errors shown error bar.
14

---

Published as a conference paper at ICLR 2021
138
1000
4000
2000
30.0
2000
13
1000
MaaNTS sum
(a) Adult
(b) Covertype
(c) Magic Telescope
17900
1500
1003
2000
1903
2500
UCO INwisS
Commrpiin
MursiCa
MNIST
(c)
mushroom
shuttle
Figure 5: Comparison of the running time for Neural TS, Neural UCB and e-greedy for neural networks on UCI datasets and MNIST dataset.
A.3 RUN TIME ANALYSIS
We compare the time of the four algorithms based neural networks: BootstrapNN, e-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 e-greedy, which is due the extra calculation of the neural network gradient for each input context. BootstrapNN is often more than times slower than e-greedy because has train several neural networks at each round.
B PROOF OF LEMMAS IN SECTION
Under Condition 4.1
show that the following inequalities hold.
2 2/1/X 2 LL- /
2 T/X s Cm min (m2 m] 3/2 m3/322 m/7 ((A1)
(log m) "
m))1)3/8
// 0 2 Cm.3 3 / Vlo MlogmL?/2gpe /
/T/A)
m 2 Cm 6 K I log (og() max 1) 1}.
where {Cm,11 Cm, 2........ 4m,4 are some positive absolute constants.
B. PROOF OF LEMMA
The following concentration bound on Gaussian distributions will useful our proof.
Lemma B.1 (Hoffman et al. (2013)). Consider normally distributed random variable X N(,, and 3 2 O. The probability that X is within a radius of 3r from its mean can then be written
Pr (IX pl $ Bo) 2 exp(-8212).
Proof of Lemma 4.2 Since the estimated reward Fr,6 sampled from [(f(xx, O, 0z-1), uPoP.N given filtration Fr, Lemma B.T implies that, conditioned on F, and given k;
Pr (IFt, fxx,,e; 0.-1)l S Guvor (FF) 2 exp( - 22/2).
Taking a union bound over K arms, we have that for any t
Pr (Vk, Fe. f(x,,x; 0,-1)l S CHNOR (Fi 1 K expl(ce
15

---

Published as a conference paper at ICLR 2021
Finally, choose c v log 2og K as defined in (4.1 get the bound that
Pr Fi) Fi)
Pr (4k, Fe,k f(x,, 01-1) scvor
82
B.2 PROOF OF LEMMA 4.3
Before going into the proof, some notation is needed about linear and kerneiized models.
Definition B.2. Define U, = AI + Σ
==1 g(xi,a, (x), 0o) //mm/m and based on U, we further define oř, >g (xt,k; 0 1-
, 0m)/m. Furthermore, for convenience we define
J. (g(X1,a,1) 01)
g(xi,a, 0.))
J. (g(X1,01 10)
g(Xi,a, 0b))
h, (h(X1,01)
... h(xt,o,))
r, = (ri rt)
G (h(x1,a:) 1i h(X1,a)) - rz)
where E; is the reward noise. We can verify that U, AI J.J. /m, U, AI J,JJ We further define K, = J. Jr/m.
The first lemma shows that the target function 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 > 0 such that for any 8 E (0, 1), if
CT (ogT'""
then with probability at least over the random initialization of 0o, there exists a 0 E R such that
h(x') = (g(x:; 0o), 0- - 0o), v 0oll2 I H 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 Gu, we have that h, ( 0.)
The next lemma bounds the difference between the हi from the linearized model and the de. 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 = Ci(mA + mLT) then with probability least 1 5,
Jō Jeuul S C2v/lg m0 1/6 2/3 9/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.S. Suppose the network width m satisfies Condition 4.1
Then, set y Ci (mm + mLT)-1 with probability at least 5 over the random initialization of lg. we have
( 0,-1) (g(x), 0o), U J. < 33 1166 2/3 log
+ Cs(1 mm2)) VIL.A
+ C4m -4/6 / (/533 5/3 1-533 + V1/A),
where (C.M_ are positive constants.
16

---

Published as a conference paper at ICLR 2021
The next lemma, due to Chowdhhry & Gopalan (2017). controls the quadratic value generated by an
random vector E:
Lemma B.6 (Theorem 1, Chowdhury & Gopalan 2017 ). Let f be real-valued stochastic
process such that for some R 2 and for all 1. G is Fe-measurable and sub-Ganssi
conditioned on F,, Recall K, defined in Definition B.2] With probability 0 < 8 < and for given
? > with probability - 6, the following holds for all 4,
ei + -/11 + + Elit S 12 logdet((1 + +) K.) 2 log(1/0).
Finally, the following lemma shows the linearized kernel and the neural tangent kernel are closed: Lemma B.7. For all E [7], there exists positive constants C' such that the following holds: if the network width m satisfies
m 2 LT (TKL/))))
then with probability at least 1 - 8,
log det + K2) I log det X H +1.
We are now ready to prove Lemma
Proof of Lemma 4.3 First of all, since m satisfies Condition 4.1 then with the choice of v) ,the condition required in Lemmas [.7] are satisfied. Thus, taking a union bound, we have with probability least
56, that the bounds provided by these lemmas hold. Then for any t E [2], we will first provide the difference between the target function and the linear function (g(0),,5 0o), 1- as:
M(xxx) - (g( 0o), U
11(x,,)) (g( 0o) U 1 (g( 0o). U -
(g(x,,s; 0o), 0, U. -00000--000000 10000m))m)))m))mm)))))))) |g(x Oo) ",, -
(8(x,, -I- (U, - - -bo) + (x 0o) J-
Alg(xe, 0o) - (0' 00) + g(x 00) "U) - U
S A x( 0o)
TÜ x 0o)
/00 (0--0p) -0) [,)TU,1 (0) 0m)
+ V M 0p)
U gx 0o)
JL U -
S vm 0ol12ōt,k o 1/2
(B.2)
where the first inequality uses triangle inequality and the fact that rt-1 h, + 4- the first equality is from Lemma B.3 and the second equality uses the fact that J,-JJ,1 = m U, - AI
m(
which can be verified using Definition B.2, the second inequality is from the fact that |a A, < V Aay B A3. Since U.! { and or defined in Definition B.2 obtain the last in- equality.
Furthermore, by obtaining
J_ U = JTL J.JJ.[ J,-1
= = -
J J -IJ /
J,, m) Je-1/m /m2
=X-'K,-1(1 -AI K,-,) K, K,-1)-1,
where the first equality is from the therman-Morrisse formula, and the second equality uses Defi-
nition B.2 and the fact that (AI + -AI+K,,)) K,-1)- 'K I A(II K,-1)~ which could be verified
by multppyyng the LHS and RHS together, we have that
I.J. J-m- & KAI KK-1)
[K, + 1A-1) +
[[ (K,_ + (A 1)1)-11---e E6-1
(B.3)
17

---

Published as a conference paper at ICLR 2021
where the second inequality is because À = 1=1+1/7T set in Theorem 3.5
Based on B and [B3)). by utilizing the bound on ||0 0|1 provided Lemma B.3 as well as the bound given in Lemma B.6, and À 1, we have
[x(,,))) (g(x,,; Oo), - s (B Ry det K(-1) log(1/6) de
since obvious that
log del + +
( + (t 1) log A
let ( 1oAX-K,,,, K(-)) t(A 1)
logdet - - H) + +2
where the first equality moves the À outside the log det, the first inequality is due to log X < A and the second inequality is from Lemma B.7 and the fact that 1++1/ 1/T (as set in Theorem 3.5 Thus, we have
[x(x,x)
(g( 0o), J 1 J & vōl.k.
where set B RV/og det + H/A) + log(11/)). Then, by combining this bound with Lemma B.5 conclude that there exist positive constants C₁ C22 C3 that
[x 0--1) - h(xx,,)) S VōLA + 1 logm m O2(1 rmA)' VLLAA + Csm 1166 Vlg 115m3//5//////////////// X-63 + vt/A),
S voL 2/ 1/6 2/3 log m (m1)) VLLAA
+ Oxm
1/6 -1/6 /lg //3/3///////////// X - 5/3 v(/A)
B RV det H H/A) + 2 (og((1/))
(or, or,
Finally, by utilizing the bound of |ōt, Ji provided in Lemma B.4 we conclude that
(x 0.-1) h(x,,x) S vork + c(m),
where e(m) is defined by adding all of the additional terms and taking = T:
<(m) = C,72/3 m 111mmm1-16------ 2//3, 1
log m + C2(1 - -mmAA VTL/++ + +3m 1/6 Vlg 5 3 51 + /T/X)
CC B Rog del (I H/X) +2+ 2l0g(1/)) Vlogm//// 7/00 -1/0 2
where is exactly the same form defined in By setting to 8/5 (required by the union bound discussed at the beginning the proof), we get the result presented Lemma 4.3
B.3 PROOF OF LEMMA 4.4
Our proof requires 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 o, for any O.
X p 2
exp(-332
Pr
4 nB
18

---

Published as a conference paper at ICLR 2021
Proof of Lemma 4.4 Since Fi,k ((-))) conditioned on Fi, we have
Pr (Fi + c(m) > (((,,,)))) F1, F(,
Pt, [(x,,k: 11-1) + ((m)
M(x111)) - f(xL1) O2-1)
Pr
Fr, E1
VOr.
1Ork
Tt,k s(x,, 0.-1) + =((m)
[h(xe.x) - (X 02-1) 1)1
2 Pr
Fr, Eu
Vot.
VOr,k
Tt,k f(x,, (1-11)
[h(xCx) - f(x,, 01-101) c(m)
Pr
Fe, 8/
1or
Tt.k
f(xI,x; 01-1)
> Fr.
2 Pr
V0T,k
4ev
where the first inequality is due to |x| 2 x, and the second inequality follows from event & i.c.
Yk E [K], If 1x 01-1) h(xx,,)) S vork + c(m).
B.4
PROOF OF LEMMA 4.5
Proof of Lemma 4.5
Consider the following two events at round t:
A (Ak: Sr, Fe. < FF,, E(1)
B {ar $ s
Clearly, A implies B, since = argmax Pi,k. Therefore,
Pr (a: & S. F., E 2 Pr (Ak St, < Fraa F(, ((.
Suppose EH also holds, then is easy to show that Ak E [K].
(h(x(,)) Fe,al I ( f(x(,x: (x 01) Fe,xl s c(m) + (1+ M (B.4)
Hence, for all &s E St, we have that
(xx Fr,x 2 h(xx,a;) h(xx,,)) [1(xx,,)) - Fr 2 c(m),
where we used definitions of saturated arms Definition 4.4 and of E/e and &g in Consider the following event
C= (1((x1a;)) e(m) < Fr E(t)
Since E/ implies - 2 Fr, we have that Cf holds, then A i.c. Ef nC C A. Taking union with & we have that C Eq UET nc C AUET, Er, which implies
Pr(A) Pr(E7) > Pr(C).
(B.5)
Then,
B.5
implics that
Pr (Vk E Fek Fr.o;FFF 2 Pr (Fr.;; + +((m)= (xx Pr (()
lev
where the first inequality is from of is a special case of vk E [K]. the second inequality is from Lemmas
4.2 and 4.4
19

---

Published as a conference paper at ICLR 2021
B.5 PROOF OF LEMMA 4.6
To prove Lemma 4.6 we will need an upper bound bound on òz,k-
Lemma B.9. For any time & E (T), k [K], and E (0, if the network width m satisfies Condition 4.1 we have, with probability at least 1 - 5, that
Jr S CVL,
where a positive constant.
Proof of Lemma 4.6 Recall that given F, and E the only randomness comes from sampling Ft, for & E [K]. Let ky be the unsaturated arm with the smallest oe,,, i.e.
h argmin oekk,
kgS.
then we have that
Bl Fr, 8/1 2 E. Rlota, Fr, Et, at & Pr(ay & S()F,
ttke
(B.6)
40
t2
where the first inequality ignores the case when dz E S., and the second inequality is from Lemma and the definition of k; mentioned above.
If both Eg and Et² hold, then
Vk E [K], [h(xL,)) Fe,Kl S c(m) + (1 +.c
(B.7)
as proved in equation (B.4) 4). Thus,
h(xi,a;) (xx,,0)) h(xx,,;) h(xx,x,)) + ((x,,,,)) h(xx),0)
s (1 + c)vo,,k + 20(m) + h(xx,E,) FL, h(x(,ax)
Fr.er + Fee,ke Fr.a.
S c)) + 0(,ae) + 4e(m),
(B.8)
where the first inequality from Definition 4.4 ky $ S,, and the second inequality comes from equation (B.7). Since trivial bound on h(xr,az) h((t..,) could be get by h(xx,a;) h (Xt,,,) S
(h(xx,,a) ) + (x ) < 2. then we have
(x),,))))) ) 1(x ((xr Fr, 8(' = EE(((x,,;)) - h(xx, Et, E7T Pr(E()
+ E[h(xr,a;) a(x),)))) Er Et Pr(ET)
2
< (1 + ct)u(20,.R + Biorra [Fr, 8(1)) + 4c(m) +
1
2B(or, FF,, [F,, 814
< <1+aa)v
+ Elor, [T E/4
+ +e((m) + 8
deva 7
< (1)
+ 4e(m) + 2t-
where the inequality on the second line uses the bound provide in (B.8) and the trivial bound of 1(x(,a;) h(Xt,a;) for the second term plus Lemma 4.2 the inequality the third line uses the bound of o,R, provide in (B.6), inequality on the forth line is directly calculated by S 4ey/T and
S 20eymT,
Jeva
which trivially holds since LHS is negative when t and when t 5, the LHS reach its maximum as RJ 84.11 < 96.36 s RHS.
Noticing that [x(x) 1, it is trivial to further extend the bound as
E E[h(xx, h(xx, Fe, Ef1] < min(44e + c.) (F, FF.
+ 4e(m) + 2
20

---

Published as a conference paper at ICLR 2021
and since have 1 + c 2 1 and B + Ry log det(I H/A) + 2 llg(11/) B, recall 22e/ T B 2 1, it is easy to verify the following inequality also holds:
E(h(xi,a;)
s (1 min FF et 4e(m) 21-
- 44e + V LB]min(or.ar 1) Fr, Et' + 4e(m) + 2t
where we use the fact that there exists a constant C₁ such that dro is bounded by Cj CIvL with probability å provided by Lemma B.9 Merging the positive constant C₁ with 44e/T, /, we gel the statement in Lemma 4.6
B.6 PROOF LEMMA 4.7
We start with introducing the Azuma-Hoeffdinn inequality for super-martingae:
Lemma B.10 (Azuma-Hoefiding Inequality for Super Martingale). If a super-martingale Y,, corre- sponding to filtration Fi satisfies that [Y Yz-1 & Bt, then for any 8 E (0, w.p. 1 8, we have
Y Y
2log 1/6) (log(1/0)
Σ B?.
Proof of Lemma 4.7
From Lemma B.9 we have that there exists positive constant C1 such that bounded with probability - by
X, defined in (45
Xx < + Ca(+ (.a 1) 4c(m) + 2
2 +
< +) 4e(m)
where the first inequality uses the fact that |a - b < |a| + bb|: the second inequality is from Lemma B.9 and the fact that h third incquality uses the fact that t- < 1. Noticing the fact that o S CT, and from Lemma 4.6 we
where C2 is positive constant used in Lemma B.9 the
know that with probability least 1 8, is super martingale. From Lemma 1.10 have
YT Yo (4 + (1 cr) (((m)))2log(11//))
(B.9)
Considering the definition of Y in 445
BB.9 is equivalent to
T
T
Σ S 4Te(m) +2
Σ
2- Ci(1 L Σ
min 1}
1=1
1=1
+ (4+C1 + (mm)
then by utilizing x² 1 -²
7² and merge the constant C₁ with 44c taking union bound of
the probability bound Lemma 4.6 B. 10 B.9 we have the inequality above hold with probability at least 35. Re-scaling 5 to 0/3 and merging the product of C C2 new positive constant leads to the desired result.
B.7 PROOF OF LEMMA 4.8
We first state technical lemma that will be useful:
Lemma B.11 (Lemma 11, Abbasi- Yadkori et al. (0111). Let {velee be sequence in Rd, and
define V, = AI + E V.V. If 1, then
T
i Σ v.v!) i=1
Σ
min(v, V v-1, 1) 2og det I+
21

---

Published as a conference paper at ICLR 2021
Proof of Lemma 4.8 First, recall o defined in Definition the bound of 01 provided in Lemma B.4 We have that there exists a positive constants C1 such that
min(or.ac 1)
min ar or. 1 + Σ
0r.0r o(,a.)
==1
T
min 11 + C,713//6 Vlog mmm 1 L,/2,
where the first term in the inequality on the second line from Cauchy-Schwartz inequality, and the second term is from Lemma B.4
From Definition
B.2 have
min 13
S
(i Xt,0rs 0o)
Uū 0o)/m, 1}
T
< 2A log det
1+X-1 I
Σ g(xe,ari 0 /m
2Alog det (I + - -Td
2A 2Ag de
+ J /m)
-A d
where the first inequality moves the positive parameter À outside the min operator and uses the definition of 0z in Definition B.2 then the second inequality utilizes Lemma B.11 the first equality
use the definition of J, 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 K, in Definition B.2 From Lemma B.7 we have that
log det + A -K,) log det H +1
under condition on m and n presented in Theorem 3.5 By taking union bound we have, with probability 26, that
min 1) V 22TT(dlog(1 TK) + 13/6 Vlog nmm X- 22/3 1//2
where we use the definition of d Definition 3.2 Replacing ó with 8/2 completes the proof.
C PROOF AUXILIARY LEMMAS IN APPENDIX B
In this section, 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.
about to show the proof of the Lemmas used in Appendix we will start
B
Lemma C.1 (Lemma B.2, Zhou et al. (2019).. There exist constants (C,) > such that for any 5 > 0, if 7, m satisfy that for all E [7).
2 2/11/2 2 Cim L L-3/2 3/2 1000loo(
[og[TKL ( /6)]3/2
2 2/t/A C2 min L "logg m] 3/2 1/,,7/ 66-1 (1ogm)-1)
" S Ca -1
m 1/6 > C4 Coylo mL 7/2 7//66/66 7/8 VI/A),
then with probability at least 1 over the random initialization of G. for any E [T], we have that ||0,- - 0all2 5 2, / (m)) and
10 - Oy - UJ-JJe-Vo-//mll
< ')ma) Vi/(mA) -5m--/33 2/3 1 V1/A).
22

---

Published as a conference paper at ICLR 2021
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 {C, } > 0 such that for any
> 0, r satisfies that
Cim 3/2 3/2 [log(TLL"/0) < C2L C2L m
3/2 -3/2
then with probability at least over the random initialization of 0., for all 0, satisfying |10 - 0ol12 S r, 110 0oll2 - and E [TK] we have
0(x);0) [(x: 0) (g(x 0), 0 0) C3T L3 m log m.
Furthermore, to continue with, next lemma is proposed to control the difference between the gradient and the gradient the initial point.
Lemma C.3 (Theorem 5, Allen-Zhu et 2018)). There exist constants {Ci} > such that for any 8 (0, 1). if satisfies that
-3/2 Cim 3/2 L 3/2
[logg [ (T (TK L2 /8)) < C22-~(log m) 3/2
then with probability least j E [TK] we have
5 over the random initialization of Oo. for all ||e 0ol12 S t and
Ig(x 0) - g(x;; 00) S C3 1/333m///3331311 0o)l2.
Also, we need the next lemma 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 {C; 3 > such that for any 5 > 0, if satisfies that
Cim 3/2 2/2 3/2 [looooTL /8))3/2 S C2L m
3/2 m
then with probability at least 1 over the random initialization of 0u. for any | 00ll2 S r and j E [TK] we have []g(x); 0) < CavmL.
Finally, literally shows, model and the NTK kernel if the network is width enough.
also provide bounds the kemee provided by the linearized
Lemma C.5 (Lemma B. Zhou et al. (2019)). Set K = E Ei=1 (xx,, 0o)g(x,,e: 0o)/m. recall the definition of H in Defimition then there exists a constant C1 such that
C L (
could get that K H F < TKe.
Equipped with these lemmas, we could continue for our proof.
C.1 PROOF LEMMA
Proof of Lemma B.4 Firstly, set 2 t////(nni (m/)) then we have the condition on the network
and learning rate satisfy all the condition need from Lemma C.I to Lemma C.5 Thus from
Lemma C.I we have that there exists | Oull2 5 r, thus from Lemma C.4 we have that there
exists positive constant C1 such that [gg(x; 0e-1)1l < CivmL, [g(( 00) the function defined as
C VmL, consider
-1
( aj. ... a.-1)== T
AI + AI+aaa? a.
it is then easy to verify that
g(x,:::0
1--1)
g(X1,a,: 01)
g(X;-1,ar-) 1,,-1, 0--1)
vb
oi.k
Vm
Vm
v m
8(x,,1; 00)
g(Xi,ay 0p)
g(x: 1,0- 0v)
1/
Vm
mm
v m
23

---

Published as a conference paper at ICLR 2021
then obtain that the function 2) is defined under the domain ||a]|2 by taking the derivation w.r.t. 2² we have that
CIVL,
CIVL then
-1
20/ = (da)
Σ AI + A
a+a
T
Σ IK + ata?
da
1-1
-1
+ a
Σ
AI + aca!
Σ
(Ba.)aa + +,O0a )
Σ
+I+ AI+aaaa ara!
a.
1=1
1=1
1=1
by taking trace with both side and utilizing that
(r(AB)= = tr(BA) and tr(a [33 = tr(a we have
1-1
-1
2 tt(()00) = tr 2(0a))
Σ
+ + a.a
a
-1
+ 2
(Daj)
Σ AI + aaa
aa' Σ AI ata
ag
3=1
thus by setting C where D diag(e1, . (p) as the eigen-values value of C, we have that
E AK a
for simplicity and decompose C
QD
Qa
Ca |aabl22 =
Caa bDb
Cu | Ei bie
Va
Va Ca
= Ca
a
b Db
1//4
where the last inequality is from the fact that C N 1/AI, which indicates that all eigen-value 2: S 1/X, A for the same reason, we have
| 1 = Caa T Caillz
CCaa TCl2 = ||a ||2 Calla
CT I ||a/||aa||/
$ ||a:|12
/V/..
Va Ca
Va Ca
Va Ca
Thus under the domain that ||a/|2 S Ō CIVT,, S CiVI, we have that
Vatbl2 1/VA, 112 CLI/A.
Then, Lipschitz continuity implies
g(xixx:
1
g g(X1,an 01)
3(x--1a;1) 01-1)
ot - -
=
Vm
Vm
Vm
g g(Xr,x; On)
g(xi,a 0o)
g(x,-1,0
15 00)
Vm
v m
mm
g g(x,, 0.-1)
g(x,,e; k 0o)
< sup V
mm
Vm
g(xio,; 0.) Vm
g(Xi,, 0o)
V
vm
g(xi,, 0.)
00) g(xi,
C.. f-1
g
( Oc)
a(x 0p)
v
m
mm
2
(C.1)
with T = 2 2 t/m,, there exist positive constants C₂ and C3 so that each gradient difference in is bounded by
By Lemma C.3
[g(x; 0) - g(x; - C2 mT 1/3 1 0n)le/vm
$ Cs C3y/logm' mt 11/6 1/6 7/2
24

---

Published as a conference paper at ICLR 2021
Thus, since obtain that there exists constant C3 such that
10 Tr S C1 log mt
7/6 m 2/11
where we use the fact that C1 = max CC,, C₂C and L 2 1 to merge the first term into the summation. This inequality is based on Lemma C.I Lemma C and Lemma C.4 thus it holds with probability at least 1 36. Replacing with 6/3 completes the proof.
C.2 PROOF OF LEMMA B.5
Proof of Lemmal B.5
Setting T t/mmm,, we have the condition on the network m and learning
rate 1i satisfy all of the condition needed by Lemmas C.I to C.5 From Lemma C.I we have ||0,-1
foll2 S т. Then, by Lemma C.2 there exists a constant C₁ such that
[f(x 0,-1) (g (x 0o), 0: - 0o)1 s C, m 1/6 2/3
12/3 L log m,
(C.2)
Using the bound on 0:-1- 0g- Ü J. -- 1 /m provided Lemma C.1 and the norm of gradient bound given in Lemma C.4 we have that there exist positive constants C1, C2 such that
(g(xx,, 0o), 0 Oo) - (g(x( 0o), U, J.
$ [gg( 112 0 Ou J-
2/3 Ci mL (1- mymaaa (t/(m))) C2m -2/3 Vlog mL //2 1 v(/A))
= = mmm)) VLL/A+ Cam 1/6 // 5/3 (1 + (t/A),
(C.3)
where C2 = C1, C3 = =0,02. Combining
C.2
and
C.3
we have
[f(x,, 0.-1) - (g(#r. 0o), J. S 1/3 1 2- 2/3 L log m
+ C2 /tL/A
+ +ym log m 4,/33 5/3 (1+ /t/x),
which holds with probability 1 35 with union bound (Lemma C.4 Lemma Replacing å with 5/3 completes the proof.
and Lemma
C.3
PROOF OF LEMMA B.7
Proof of Lemma B.7 From the definition of K,, have that
log det (1 + X -K,) = log det
I+
Σ
g
g(xi,
(o)g(x;,; 0o) /
i=1
T
K
< log det
I+
g(Xia.. 6 (o)g(xi.. 60) / (mz))
t=1
k=1
log det(I + K/X)
< log det + H/A + (H KJA) T(A -(A-
< log det(I + H/A) + ((I+ H/A) (K -H)/A)
< log H + [[(+++/))~ [K -H)
< log det + H/A) VTK (" -H]FF
I log dI H/X) +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 in Lemma C.5 and H in Definition 3.1 the third inequality is from the convexity of log del (-) function, and the forth inequality is from the fact that (A, B) < | [[B]] [|.. Then the fifth inequality is from the fact that |||| S VTK |A] 1|2 if A E IR TK TK TK and 2 0. Finally, the sixth inequality utilizes Lemma C.5 by setting = (TK) 3/2 with m 2 C, L K ( where we conclude our proof.
25

---

Published as a conference paper at ICLR 2021
C.4 PROOF OF LEMMA B.9
Proof of Lemma B.9 Set T in Lemma C.4 as 2/L)(mA), Then the network width m and learning
rate yy satisfy all of the condition needed by Lemma C.1 C.5 Hence, there exists C₁ such that (x:: 0)ll2 S (lg(x; 0)ll F I CLvLL for all x, since it easy verify that U, 3 --II. Thus we have that for all E [T' k E [K],
oit Ag (xi,Ai 0 1,
(((x,x:0-11)1) C.L.
Therefore, we could get that ot. I CIVL, with probability 28 by taking a union bound (Lemmas C.1 and C.4). Replacing with 8/2 completes the proof.
D AN UPPER BOUND OF EFFECTIVE DIMENSION
We now provide an example, showing when all contexts X; concentrate on a d'-dimensional non- linear 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 such that for any
i > d', 0 < (H) < (/KK) Then the effective dimension can be bounded as
d = log de H
TK
TK
TK Σ i=d'+1
log(1 (H)
Σ
(H)
(H)
(H))
log(1 + TTK)
For 1 and Lz we have
h S
H O(d), 12 < TKK 1/(TK) =
Therefore, the effective dimension satisfies that d < d' 1. To show how to satisfy the requirement, first give 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:
20
[(dk)
H Σ Pk Σ
(x, 1=1
where YE, for = 1...., (dd, k) are linearly independent spherical harmonics of degree k: in d variables, d is the input dimension, Ndd,k) = (2k d 2)/k: k ktd-3- A = (maxx( (d 1)-k+1)). In that case, the feature mapping Yi. (x))k.j maps any context x from Rd RKHS space R corresponding to H. Let y, R denote the mapping for x;, Then if there exists d' d'-immension subspace R' such that for all i, |ly; zill < 1 where z; is the projection y, onto Rx, the requirement for A; (HH) holds.
26


Reviews:
[{"review_id": "tge1iOd-HOE", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*****  Paper's Summary  *****\n\nThe authors proposed an algorithm named Neural Thompson Sampling (NeuralTS) for solving contextual multi-armed bandit problems. NeuralTS uses deep neural networks for dealing with exploration and exploitation. In the paper, the authors proved the sub-linear regret of NeuralTS, which is also verified using experiments. \n\n\n*****  Paper's Strengths  *****\n\nAs NeuralTS uses the deep neural network, it can be used for estimating non-linear reward function in the contextual bandits problem.\n\nThe authors proved the sub-linear regret using the recent theoretical results from deep learning. The regret upper bound is similar (in terms of the number of contexts and effective dimension) to the regret bound of existing methods.\n\nThe performance of NeuralTS matches with the state-of-the-art baselines. In some cases, the performance is even better than the existing methods.\n\n\n*****  Paper's Weaknesses  *****\n\nThe weak point of the paper is its novelty. The result incorporates recent deep learning and contextual bandits results [Zhou et al. 2019] (paper in ICML 2020) with the existing Thompson Sampling variant for contextual bandits problem.\n\nSince the neural network (parameters m and L) is fixed before using the algorithm, it may not be possible to estimate any arbitrary reward function with the fixed neural network. Therefore, NeuralTS can have linear regret for the cases where the reward function can not be estimated.\n\n\n*****  Comments  *****\n\nIt is difficult to understand the second part of Assumption 3.4. More clarity may help readers.\n\nThe experiments can be repeated 50 or more times to get a better confidence interval.\n\n\n*****  Questions for the Authors  *****\n\nPlease address the above weaknesses of the paper.\n\nHow are the values of '\\nu,' 'L,' and 'm' set in the experiments?\n\nWhy does NeuralTS need T as input? \n\n\n***** Post Rebuttal *****\n\nI thank authors for the clarifications! After reading the rebuttal and comments of other reviewers, I am increasing my score. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "q0VN1wLVZ5d", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe 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).\n\nReason for Score:\n\nI vote for accepting. I believe the contribution of the paper is significant, as it is the first to construct a valid posterior distribution for the parameters in the neural networks. The method also achieves a tight regret upper bound that matches the bound of NeuralUCB. The experiments show that empirically, neuralTS performs better than the state of the art, neuralUCB.\n\nPros\n\nThe paper provides an efficient way for doing directed exploration in bandits with neural network reward models.\nThe presentation of the algorithm, theorem, and experiments is clear and concrete.\n\nCons\n\nAccording to the proofs, the neural TS algorithm that uses initial parameter \\theta_0 instead of \\theta_t should have smaller regret than the current algorithm. That is to say, according to the proofs, the regret can be decomposed as (the regret of the algorithm which does not update \\theta ) + (a term related to the difference of \\theta_t and \\theta_0).  I think the authors should add discussion about this point.\n \nMinor comments\n\n In the last line of page 1:\n“Sampling the estimated reward from posterior” is a confusing statement. Actually, we sample a parameter from the posterior. The same goes for “sampling the reward” between equations (2.2) and (2.3)\n\nIn the last line of Related work, authors mention Foster and Rhaklin. I don’t think they use UCB exploration. They also use a randomized algorithm although it isn't TS.\n \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "UgfxVCRYdv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe paper also is the first paper to provide regret guarantees for a neural TS algorithm. Experiments show that their algorithm performs better than other baselines.\n\nMy concern with the theoretical results is a missing discussion on their utility with respect to the assumptions. The necessary assumption for all results in the paper is Condition 4.1, which assumes that m, the width of the network is larger than T^6 L^6 K^6. With T as the horizon, this assumes a neural network width of 10^18 even for a modest horizon of 1000 (as used in the experiments). I don't think the experiments used this width in their implementation. I would like if the authors point out this disconnect for the benefit of the readers, and have a discussion section. I believe this assumption may be necessitated by the use of NTK.\n\nSecond, the algorithm uses the function g to model the variance of the distribution, but I did not find any discussion. Is g assumed to be known? If not, how is it learned?\n\nI like that the authors study the delayed reward experiments as it is often the case in practical situations. What will also be useful is to discuss the implementation complexity (computation required to decide the next arm to be sampled) of various algorithms (ideally through a plot). Some algorithms may be faster than others, and readers can use this plot to make an informed choice.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LDBwsAmn1VA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a neural network based thompson sampling algorithm for general bounded reward contextual bandit problems.  They provide a theoretical regret guarantee for the proposed algorithm with the help of recent advances of Neural Tanget Kernel.\n\nThe main techniques that use the gradient of the neural networks and NTK have been developed in a recent paper, Neural UCB, as cited by the authors as well. Based on estimations of mean and variance developed in the Neural UCB, NeuralTS is a variant that uses a Gaussian posterior on the top of those estimations. The theoretical contribution is adapting some well-known tricks in the bandit literature to analyze the regret of TS algorithm. That is why I think the contribution is quite incremental.\n\nThe authors provide sufficient experimental data points to justify the advances of the proposed Neural TS against all the existing benchmarks, which is a plus.\n\nBesides, I have the following detailed comments:\n\n1. In Section 2, I didn't find a clear definition of $m$. I have to infer that it is the nework width until Algorithm 1.\n2. In the entire paper, I didn't find a definition for $g(x,\\theta)$. I have to infer its meaning by reading Neural UCB paper.\n3. In Theorem 3.5, many parameters depend on the time horizon T. However, in some use case, we may not have the information of T and some algorithms have this advantage of so-called any-time regret bound. Is it possible to get rid of this dependence by playing some doubling trick?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers tend towards accepting the paper, and I agree.
Decision: Accept (Poster)