Neural Contextual Bandits with Deep Representation and Shallow Exploration
Authors: Pan Xu
Zheng Wen
Handong Zhao
Quanquan Gu
Venue: ICLR 2022 Poster (2022)
Keywords: neural network
deep representation learning

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

Published as a conference paper at ICLR 2022
NEURAL CONTEXTUAL BANDITS WITH DEEP REPRE- SENTATION AND SHALLOW EXPLORATION
Pan Xu
Zheng Wen
Handong Zhao
California Institute of Technology panxuêca weealttecc... edu
DeepMind
Adobe Research hazha @aaaaeeaaabb.... com
zhengwen@google com
Quanquan Gu University of California, Los Angeles qquêcs. ucla.
ABSTRACT
We study neural contextual bandits, a general class of contextual bandits, where each context-action pair associated with raw feature vector, but the specific re- ward generating function is unknown. We propose a novel learning algorithm that transforms the raw feature vector using the last hidden layer of a deep ReLU neu- ral network (deep representation learning), and uses an upper confidence bound (UCB) approach to explore in the last linear layer (shallow exploration). We prove that under standard assumptions, our proposed algorithm achieves Ö(VT) finite- time regret, where T' is the learning time horizon. Compared with existing neural contextual bandit algorithms, our approach is computationally much more effi- cient since only needs to explore in the last layer of the deep neural network.
INTRODUCTION
Multi Aulti-armed bandits (MAB) (Auer et al., 2002; Audibert et al., 2009; Lattimore & Szepesvári, 2020) are a class of online decision-making problems where an agent needs learn maximize its ex- pected cumulative reward by repeatedly interacting with partially known environment. Following a bandit algorithm (also called a strategy or policy), in each round, the agent adaptively chooses an arm, and then receives reward associated with that arm. Since only the reward of the chosen arm will be observed (bandit information feedback), a good bandit algorithm has to deal with the exploration-explootation dilemma: trade-off between pulling the best arm based on existing knowl- edge/history data (exploitation) and trying the arms that have not been fully explored (exploration).
In many real-world applications, the agent will also be able to access detailed contexts associated with the arms. For example, when a company wants to choose an advertisement to present to a user, the recommendation will be much tents, specifications, and other features of the advertisements in the arm set as well as the profile of the user. To encode the contextual information, contextual bandit models and algorithms have been developed, and widely studied both in theory and in practice (Dani et al., 2008; Rusmevichientong & Tsitsiklis, 2010: Li al., 2010; Chu et al., 2011; I; Abbasi-Yadkor et al., 2011). 1). Most existing contex- tual bandit algorithms assume that the expected reward of an arm at context is linear function in known context-acee acttonnttaiinnnoo feature vector, which leads to many useful algorithms such as LinUCB (Chu et al., 201 1), OFUL (Abbasi-Yadee) Yadkori et al., 201 1), etc. The representation power of the linear model can be limited in applications such as marketing, social networking, clinical studies, etc., where the rewards are usually counts or binary variables. The linear contextual bandit problem has also been extended to richer classes parametric bandits such as the generalized linear bandits (Filippi et al., 2010; Li et al., 2017) and kernelised bandits (Valko al., 2013; Chowdhury & Gopalan, 2017).
accurate if the company takes into consideration the
With the prevalence of deep neural networks (DNNs) and their phenomenal performances in many machine learning tasks (LeCun et al., 2015; Goodfellow et al., 2016), there has emerged line of work that employs DNNs to increase the representation power of contextual bandit algorithms (Allesiardo et al., 2014; Riquelme et al., 2018; Collier & Llorens, 2018: Zahavy & Mannor, 2019;

---

Published as a conference paper at ICLR 2022
Zhou et al., 2020; Deshmukh et al., 2020; Zhang al., 2020). The problems they solve usually referred to as neural contextual bandits. For example, Zhou et al. (2020) developed the NeuralUCB algorithm, which can be viewed as a natural extension of UCn (Chu et al., 2011; Abbasi- Yadkori et al., 201 I), where they use the output of a deep neural network with the feature vector as input to approximate the reward. Zhang al. (2020) adapted neural networks in Thompson Sampling (Thompson, 1933; Chapelle & Li, 2011; Russo et al.. 2018) for both exploration and exploitation and proposed NeuralTS For fixed time horizon T, it has been proved that both NeuralUCB and NeuralTS achieve a (dvTT) regret bound, where d is the effective dimension of neural langent kernel matrix which can potentially scale with O(TK) for K-armed bandits. This high complexity is mainly due to that the exploration is performed over the entire huge neural network parameter space, which is inefficient and even infeasible when the number of neurons is large. A more realistic and efficient way of learning neural contextual bandits may be to just explore different arms using the last layer the exploration parameter. More specifically, Riquelme al. (2018) provided an extensive empirical study of benchmark algorithms for contextual-anddis through the lens of Thompson Sampling, which suggests decoupling representation learning and uncertainty estimation improves performance.
In this paper, we show that the decoupling of representation learning and the exploration can be theoretically validated. We study a new neural contextual bandit algorithm, which learns a map- ping to transform the raw features associated with each context-action pair using a deep neural network (deep representation), and then performs upper confidence bound (UCB)-type explo- ration over the linear output layer of the network (shallow exploration). We prove a sublinear regret of the proposed algorithm by exploiting the UCB exploration techniques in linear contextual ban- Yadkori et al., 201 1) and the analysis of deep overparameterized neural networks using
dits (Abbasi-Yadkori neural tangent kernels (Jacot et al., 2018). Our theory confirms the empirically observed effective- ness of decoupling the deep representation learning and the UCB exploration in contextual bandits (Riquelme et al., 2018; Zahavy & Mannor, 2019).
Contributions we summarize the main contributions of this paper as follows.
We propose a contextual bandit algorithm, Neural-LinUCB, for solving general class of con- textual bandit problems without knowing the specific reward generating function. The proposed algorithm learns deep representation to transform the raw feature vectors and performs UCB- type exploration in the last layer of the neural network, which we refer to as deep representation and shallow exploration. Compared with LinUCB (Li al., 2010; Chu et al., 201 and neural bandits such as NeuralUCB (Zhou et al., 2020) and NeuralTS (Zhang et al., 2020), our algo- rithm enjoys the best of two worlds: strong expressiveness due to the deep representation and computational efficiency due to the shallow exploration.
Despite the usage of a DNN the feature mapping, we prove a Ö(vT) regret for the proposed Neural-LinUCBB algorithm, which matches the regret bound of linear contextual bandits (Chu et al., 2011; Abbasi- Yadkori et al., 2011). To the best of our knowledge, this is the first work Abbasi-Yadkorí that theoretically shows the convergence of bandits algorithms under the scheme of deep repre- sentation and shallow exploration. It is notable that a similar scheme called Neural-Linear was proposed by Riquelme et al. (2018) for Thompson sampling algorithms, and they empirically showed that decoupling representation learning and uncertainty estimation improves the perfor- mance. Our work confirms this observation from a theoretical perspective.
We conduct experiments on contextual bandit problems based on real-world datasets, demon- strating a better performance and computational efficiency of Neural- UCB over LinUCB and existing neural bandits algorithms such as NeuralUCB, which well aligns with our theory.
1.1 ADDITIONAL. RELATED WORK
There is a line of related work to ours on the recent advance the optimization and generalization analysis of deep neural networks. In particular, Jacot et al. (2018) first introduced the neural tangent kernel (NTK) to characterize the training dynamics of network outputs in the infinite width limit. From the notion of NTK, fruitful line of research emerged and showed that loss functions of deep neural networks trained by (stochastic) gradient descent can converge to the global minimum (Du et al., 2019b; Allen-Zht et al., 2019b; Du et al., 2019a; Zou et al., 2018; Zou & Gu, 2019). The generalization bounds for overparameterized deep neural networks are also established in Arora et al. (2019a;b), Allen-Zhu al. (2019a); Cao & Gu (2019a;b). Recently, the NTK based analysis
2

---

Published as a conference paper at ICLR 2022
is also extended to the study of sequential decision problems including bandits (Zhou et al., 2020; Zhang et al., 2020), and reinforcement learning algorithms (Cai et al., 2019; Liu et al., 2019; Wang et al., 2020; Xu & Gu, 2020).
Our algorithm is also different from Langford & Zhang (2008); Agarwal et al. (2014) which reduce the bandit problem to supervised learning. Moreover, their algorithms need to access oracle that returns the optimal policy in a policy class given a sequence of context and reward vectors, whose regret depends on the VC-dimension of the policy class.
Notation We use [k] to denote set {I,..., k}. k N+. ||x|2 = vx the Euclidean norm of vector x E Rd For matrix W E I we denote by [[]] and [ r its operator norm and Frobenius norm respectively. For a semi-definite matrix E Raxd and a vector E IR", we denote the Mahalanobis norm as ||x| A = vx Ax. Throughout this paper, we reserve the notations {C; io.......... to represent absolute positive constants that independent of problem parameters such as dimension, sample size, iteration number, step size, network length and so on. The specific values of {C,) can be different in different context. For parameter of interest T and function f(T), we use notations such as O(f(T) and (TT) to hide constant factors and ((f(T) to hide constant and logarithmic dependence of T.
2 PRELIMINARIES
In this section, we provide the background of contextual bandits and deep neural networks.
2.1 LINEAR CONTEXTUAL BANDITS
contextual bandit is characterized by a tuple (S, Arr, where S is the context (state) space, AA is the arm (action) space, and r encodes the unknown reward generating function at all context-arm pairs. A learning agent, who knows S and but does not know the true reward r (values bounded in (0, 1) for simplicity), needs to interact with the contextual bandit for T rounds. At each round t = ,,....,TI T, the agent first observes a context 8t E S chosen by the environment; then it needs to adaptively select an arm a, E A based on its past observations; finally it receives a reward
ax,,
rxx,,..) + Ee.
(2.1)
where X..o E id is a known feature vector for context-arm pair (s, a) S x A, and & is a random noise with zero mean. The agent's ss objective is maximize its expected total reward over these T rounds, which is equivalent to minimizing the pseudo regret (Audibert et al., 2009):
Ri E Σ (F(X)..;;) FiX)s.a)))
(2.2)
(r(s,, [l)(),,,)))) To simplify the exposition, we use Xt,a to denote where of E argmax,ex Xaya since it only depends on the round index L in most bandit problems, and we assume A [K].
In linear contextual bandits, the reward function in (2.1) assumed to have a linear structure r(Xs,a) x_ 0 for some unknown weight vector 0" E IRd One provably sample efficient al- gorithm for linear contextual bandits is Linear Upper Confidence Bound (LinUCB) (Chu et al., 2011) Optimism in the Face of Uncertainty Linear bandit algorithm (OFUL) (Abbasi- Yadkori et al., 2011). Specifically, at each round t, LinUCB chooses the action a = argmax (xT 0, + ar x 1 where Og is point estimate of 0", A, AI + Ei=1 Xi,a; X with some À > a matrix defined based on the historical context-arm pairs, and a₁ > a tuning parameter that controls the exploration rate in LinUCB
2.2 DEEP NEURAL NETWORKS
In this paper, we use fxx to denote a neural network with input data x E Rd. Let L be the number of hidden layers and W, xm be the weight matrices in the (-th layer, where / = 1,..., ... L,
mi = _... -m = m and mg = -m = d. Then a L-hidden layer neural network is defined as
fxx Vmo αo ( WLLL-1WW (W d1 ( (Wix)...)),
(2.3)
3

---

Published as a conference paper at ICLR 2022
where 0r is an activation function and 0 E R is the weight of the output layer. To simplify the presentation, we will assume 01 = 02 = ... = OL = a is the ReLU activation function, i.., ((x) m z for E R. We denote w concatenation of the vectorized weight parameters of all hidden layers of the neural network. We also write [xx; 0", w) = =[() in order to explicitly specify the weight parameters of neural network f. It is easy to show that the dimension of vector w satisfies p = (L 2)m² + 2md. To simplify the notation, we define Φf x; w) as the output of the L-th hidden layer of neural network f.
( ..... vec( (W,, )T, which is the
Φ(x; w) = Vmo L (WL-1- - (Wix)....)
(2.4)
Note that Φ(x; w) itself can also be viewed neural network with vector-valued outputs.
DEEP REPRESENTATION AND SHALLOW EXPLORATION
3.1 HIGH-LEVEL. IDEA OF THE PROPOSED ALGORRTHH
The linear parametric form in linear contextual bandits might produce biased estimates of the reward due to the lack of representation power (Snoek et al., 2015; Riquelme et al., 2018). In contrast, is well known that deep neural networks are powerful enough to approximate an arbitrary function (Cybenko, 1989). Therefore, a natural extension of linear contextual bandits is to use a deep neural network to approximate the reward generating function r(-). Nonetheless, DNNs usually have pro- hibitively large dimension for weight parameters, which makes the exploration in neural networks based UCB algorithm inefficient (Kveton et al., 2020; Zhou et al., 2020).
In this work, we study a neural contextual bandit algorithm, where the hidden layers of a deep neural network are used to represent the features and the exploration is only performed in the last layer of the neural network. In particular, for any arm feature vector x, we use (0", Φ(x: w)) to approximate the unknown reward function r(x), where <(x; w) defined as in (2.4) is neural network with weight w, and 0* is unknown weight parameter. Note that we can also view (0", Φ(x; w)) as a neural network with ((x; w) being the output of the last hidden layer and O" the weight parameter of the last (linear) layer. Different from existing neural bandit algorithms,, we only add a UCB bonus term involving the last layer instead of all the weight parameter of this large neural network.
This decoupling of the representation and the exploration achieves the best of both worlds: efficient exploration of shallow (linear) models and high expressive power of deep models. In what follows, we will describe a neural contextual bandit algorithm that uses the output of the last hidden layer of a neural network to transform the raw feature vectors (deep representation) and performs UCB-type exploration in the last layer of the neural network (shallow exploration). Since the exploration is performed only in the last linear layer, we call this procedure Neural-LinUCB, which is displayed in Algorithm
3.2 DETAILED IMPLEMENTATIO OF DEEP REPRESENTATION AND SHALLOW EXPLORATION
Now we describe the details of Algorithm 1. In round I, the agent receives an action set with raw features X, 1x.., Xt, J. Then the agent chooses an arm de that maximizes the following upper confidence bound:
Ge = argmaxx ((((x)); wI-)) 0.-1) + axllo w. w.--I)ll= kE(K]
(3.1)
where 0:-1 is point estimate of the unknown weight in the last layer, Φ(x; w) is defined as in (2.4), W an estimate of all the weight parameters in the hidden layers of the neural network, 0t >> is the algorithmic parameter controlling the exploration, and A, defined as follows.
A, = AI Σ ((xi... w. Wi-1)0(X :
(3.2)
and À > O. After pulling arm a, the agent will observe a noisy reward Fr := F(x,,,,) = rxxxx,)) + where is independent v-subGaussian random noise for some 1/ 0 and r(-) is an unknown reward function. In this paper, we will interchangeably use notation F, to denote the reward received at the (-th step and an equivalent notation f(x) express its dependence the feature vector
4

---

Published as a conference paper at ICLR 2022
Upon receiving the reward ft, the agent updates its estimate 0, of the output layer weight by using the same e regulaaare least-squares estimate in linear contextual bandits (Abbasi- Yadkori et al., 2011), In particular, we have 0, = A,, where b, = E'= F;o(xi,,,; ;W;
To save the computation, the neural network $ w:) will be updated once every H steps. Therefore, we have ( .... = WaHt for q = ........ We call the time steps {(g ( H + +1.... .HH an epoch with length H. At time step Hy. we will retrain the neural network based on all the historical data via Algorithm 2, which minimizes the following empirical loss function:
(w) (0T o' w) -F))
Σ
(3.3)
In practice, one can further save computational cost by only feeding data {xi,a.;Fis 0;) 0
(n 1)#++
from the q-th epoch into Algorithm update the parameter Wt, which does not hurt the perfor- mance since the historical information has been encoded into the estimate of 0, In this paper, we will
perform the following gradient descent step w!)) w (s-1) Th Co (w((-1)) for s I,...,
where w (0) w (0) is chosen as the same random initialization point. We will discuss more about the initial point (0) in the next paragraph. Then Algorithm outputs w and we set it as the updated weight parameter WHg+1 in Algorithm 1. In the next round, the agent will receive another action set Xt+1 with raw feature vectors and repeat the above steps to choose the sub-optimal arm and update estimation for contextual parameters.
Initialization: Recall that w is the collection of all hidden layer weight parameters of the neural net- work. We will follow the same initialization scheme used in Zhou et al. (2020), where each entry of the weight matrices follows some Gaussian distribution. Specifically, for any E (1,..., . L 1},
W
0
we set W
W] where each entry of W follows distribution N N0, 4/m) independently; for
WL, L. we set it as IV -V], where each entry of V follows distribution NO 2/m) independently.
Comparison with LinUCB and NeuralUCB: Compared with linear contextual bandits in Sec- tion 2.1, Algorithm 1 has a distinct feature that Iearns a deep neural network to obtain deep representation of the raw data vectors and then performs UCB exploration. This deep representa- tion allows our algorithm to characterize more intrinsic and latent information about the raw data {xt, he [ Rdd However, the increased complexity of the feature mapping ( w) also introduces great hardness in training. For instance, a recent work by Zhou et al. (2020) also stud- ied the neural contextual bandit problem, but different from (3.1), their algorithm (NeuralUCB) performs the UCB exploration on the entire network parameter space, which is Ro+d, where m md + (L 1)m². Note that in Zhou et al. (2020), they need to compute the inverse of a matrix Z, E ()(++))((++4) which is defined in a similar way to the matrix A, in our paper except that Z, is defined based on the gradient of the network instead of the output of the last hidden layer in (3.2). In sharp contrast, A, in paper is only of size d x d and thus is much more efficient and practical in implementation, which will be seen from our experiments in later sections.
We note that there is also similar algorithm (2020), where they studied the self-supervised learning loss in contextual bandits with neural net- work representation for computer vision problems. However, no regret analysis has been provided. When the feature mapping Φ(:: w) is an identity function, the problem reduces to linear contextual bandits where we directly use x, as the feature vector. In this case, it easy to see that Algorithm reduces to LinUCB (Chu et al., 201 1) since we do not need to learn the representation parameter w.
Neural-LinUCBB presented in Deshmukh et al.
Comparison with Neural-Linear: The high-level idea of decoupling the representation and explo- ration in our algorithm is also similar to that of the Neural-Linear algorithm (Riquelme et al., 2018; Zahavy & Mannor, 2019), which trains deep neural network to learn a representation of the raw feature vectors, and then uses Bayesian linear regression to estimate the uncertainty in the bandit problem. However, these two algorithms are significantly different since Neural-Lineat (Riquelme et al., 2018) is a Thompson sampling based algorithm that uses posterior sampling to estimate the weight parameter 0* via Bayesian linear regression, whereas Neural-LinUCB adopts upper confi- dence bound based techniques to estimate the weight 0*. Nevertheless, both algorithms share the same idea of deep representation and shallow exploration, and we view our rithm one instantiation of the Neural-Linear scheme.
algo-
5

---

Published as a conference paper at ICLR 2022
Algorithm Deep Representation and Shallow Exploration (Neural-LinUCB)
Input: regularization parameter À > number of total steps T, episode length H, exploration parameters (ar > (ET
2: Initialization: Ao AI, bo 0: entries of Pg follow N(0, 1/d), and w(O) is initialized as
described in Section 3; q 1; We w())
3: for f 1,....,. do
4: receive feature vectors (xr, ................................ x,
5: choose at ke[]] 01-10(x1,55 wi-1) +0ello(xx,;; w and obtain
reward Pr
6: update A, and b, as follows:
A, A,- + (xx,, wi-1 (V-1)0((xtaaj) ( Wt-1)
b: b;-1 + F We-1);
7:
update 0: -A, bb
8:
if mt ) = then
9:
Wt output of Algorithm 2
10:
q = 4
else
12:
W. W
end if
14:
end for
Output Wr
Algorithm 2 Update Weight Parameters with Gradient Descent
1: Input: initial point Wy (0)
w (0)) maximum iteration number n, step size 77g- and loss function
defined in (3.3).
2: for 1..... do
(5-1)
T1 V (Wg (w).
3: Wy Wg
4: end for
(n)
5: Output wq
4 MAIN RESULTS
To analyze the regret bound of Algorithm 1, we first lay down some important assumptions on the neural contextual bandit model.
Assumption 4.1. For all 2 1 and As E [K], we assume that ||x, = 1 and its entries satisfy [x, = /
The assumption that ||x = 1 is not essential and is only imposed for simplicity, which is also used in Zou & Gu (2019); Zhou et al. (2020). The condition on the entries of Xi, is also mild since otherwise we could always construct x xx]]R.TTT] x., //2 2 to replace it. An implication of
/
Assumption 4. 1 is that the initialization scheme in Algorithm results (x w()) for all i [T] and & E [K].
We assume the following stability condition on the spectral norm of the neural network gradient: Assumption 4.2. There is constant <pip > such that it holds Oib Bw (x: wo)
Heb 8w
(x': wo) S
(ipp/ x1|22 for x, x' E (x)
The inequality in Assumption 4.2 resembles the Lipschitz condition on the gradient of the neural network. However, it is essentially different from the smoothness condition since here the gradient is taken with respect to the neural network weights while the Lipschitz condition is imposed on the feature parameter x. Similar conditions are widely made in nonconvex optimization (Wang et al., 2014; Balakrishnan et al., 2017; ;; Xu et al., 2017), in the name of first-order stability, which is essential to derive the convergence of alternating optimization algorithms. Furthermore, Assumption 4.2 is only required the TK training data points and specific weight parameter Wa. Therefore, the condition will hold the raw feature data lie certain subspace of & We provided some further discussions in the supplementary material about this assumption for interested readers.

---

Published as a conference paper at ICLR 2022
In order to analyze the regret bound of Algorithm 1, we need to characterize the properties of the deep neural network in (2.3) that is used to represent the feature vectors. Following a recent line of research (Jacot et al., 2018; Cao & Gu, 2019a; Arora et al., 2019b; Zhou al., 2020), we define the covariance between two data point x, E IR as follows.
(x. y) = Σ (0) (x, y) = y,
1 (x. = -x-((x xx,
3y-'(y,x) (y.))
E (x, = (B. (x) (o
500 = 25 (x. (u)o -
(4.1)
where o) ~ (O,, A (x)))(x.))))) (x.y)) and a..) is the derivative of activation function. We denote the neural tangent kernel (NTK) matrix H E R2KX based all feature vectors (x),,)))))),))]])) Renumbering (xr,) [E]] as {x:}
I...,KKK then each entry Hay is defined as
H = D (x,xx)) + (10)( x))),
(4.2)
for all i.j E [TK]. Based on the above definition, we impose the following assumption on H. Assumption 4.3. The neural tangent kernel defined in (4.2) is positive definite, i.c., Amin (H) Ao for some constant A > O.
Assumption 4.3 essentially requires the neural tangent kernel matrix to non-singular, which is mild condition and also imposed in other related work (Du et al., 2019a; Arora et al., 2019b; Cao & Gu, 2019a; Zhou et al., 2020). Moreover, it is shown that Assumption 4.3 can be easily derived from Assumption 4.1 for two-layer ReLU networks (Oymak & Soltanolkotabi, 2020; Zou & Gu, 2019). Therefore, Assumption 4.3 is mild or even negligible given the non-degeneration assumption on the feature vectors. Also note that matrix H is only defined based neural network, and does not depend on the output layer O. It is easy to extend the definition of H the NTK matrix defined all layers including the output layer 0, which would also be positive definite by Assumption 4.3 and the recursion in (4.2).
layers 1 1, 1..... L of the
Before we present the regret analysis of the neural contextual bandit, we need to modify the regret defined in (2.2) to account for the randomness of the neural network initialization. For a fixed time horizon T,, we define the regret of Algorithm follows.
T
RT E
(F(xt,a;) F(xt,o)))lw!!
(4.3)
where the expectation is taken over the randomness of the reward noise. Note that Rr defined in (4.3) is still a random variable since the initialization of Algorithm 2 is randomly generated.
Now are going to present the regret bound of the proposed algorithm.
Theorem 4.4. Suppose Assumptions 4.1, 4.2 and 4.3 hold. Assume that 0 M for some positive constant M > 0. For any 8 E (0, 1), let us choose a, in NeuB as
u/ 2 (oggllg(11111 + (loollog(())))) + + log(1/5)) + 1
We choose the step size Ny of Algorithm 2 as 14 I Co (dl m log log(TK/5)) and the width of the neural network satisfies m = poly(L. (L, d, 1/5, H, log(TK/0)). With probability at least 1 - over the randomness of the initialization of the neural network, it holds that
TK }|[r- Fl Collnp' log log(() log( 0
Pr S Carry To (1
TG2 Xd
m/
where constants (C, are independent of the problem, r= (r(xi), (e(x)))r(xx))..) RTK and F (x1 Oo wo), (o))--.,[(xT:)) [XTT:; 0r-1, WT) RTK and |||||A Ar.
E
7

---

Published as a conference paper at ICLR 2022
Remark 4.5. Theorem 4.4 shows that the regret of Algorithm 1 can be bounded by two parts: the first part is of order O(vT), which resembles the regret bound of linear contextual bandits (Abbasi- Yadkori et al., 2011); the second part is of order 11/6T//T/ /(r F) (r- f)), which de- pends on the estimation error of the neural network f for the reward generating function r and the neural tangent kernel H.
is worth noting that our theoretical analysis depends on the reward structure assumption that r(-) = (0*, (b)).. However, the linear structure between O* and (b(-) is not essential. As long as the deep representation of the feature vector and the uncertainty weight parameter can be decoupled, Algorithm can be easily extended to settings with milder assumptions on the reward structure such as generalized linear models (Sarkar, 1991; Filippi et al., 2010; Li et al., 2017; Kveton et al., 2020). For more general bandit models where assumption is imposed to the reward generating function, it is still unclear whether the decoupled deep representation and shallow exploration would work especially in cases a thorough exploration may be needed.
Based on the result in Theorem 4.4, we can easily verify the following conclusion:
Corollary 4.6. Under the same conditions of Theorem 4.4, if we choose a sufficiently overpa- rameterized neural network mapping Φ6.) such that m 2 T then the regret of Algorithm is
RT = ((VVV(r- F) H
Remark 4.7. For the case of presentation, let us denote E := ---r--i|l--- If we have & = O()) the total regret in Theorem 4.4 becomes Ö(vT) which matches the regret of linear contextual bandits (Abbasi-Yadkori Yadkori et al., 201 1). We remark that there is a similar assumption in Zhou al. (2020) where they assume that r' "H-rr can be upper bounded by constant. They show that this term can be bounded by the RKHS norm of r if it belongs to the RKHS induced by the neural tangent kernel (Arora et al., 2019a;b Lee et al., 2019). In addition, & here is the difference between the true reward function and the neural network function, which can also be small if the deep neural network function well approximates the reward generating function r()).
5 EXPERIMENTS
In this section, we provide empirical evaluations of Neural-LinUCB on real-world datasets. As we have discussed in Section 3. Neural-LinUCB could be viewed as an instantiation of the Neural- Linear scheme studied in Riquelme et al. (2018) except that we use the UCB exploration instead of the posterior sampling exploration therein. Note that there has been an extensive comparison (Riquelme et al., 2018) of the Neural-Linear methods with many other baselines such as greedy algorithms, Variational Inference, SenectatioonPPopagatti Therefore, we do not seek thorough empirical comparison of Neural-LinUCB with all existing bandits algorithms. In this experiment, we only aim to validate the advantages of our algorithm over the following baselines: (1) Neural- -Lnear (Riquelme et al., 2018); (2) LinUCB (Chu et al., 201 1), which does not have a deep representation of the feature vectors; (3) NeuralUCB (Zhou et al., 2020), and (4) NeuralTS (Zhang al., 2020) which perform UCB/TS exploration all the parameters of the neural network. All numerical experiments were run on a workstation with Intel(R) Xcon(R) CPU E5-2637 v4 @ 3.50GHz.
Bayesian Non-parametrics and so on.
we evaluate the performances of all algorithms on bandit problems created from real- world data. Specifically, following the experimental setting in Zhou et al. (2020), we use datasets (Shuttle) Statlog, Magic and Covertype from UCI machine learning repository (Dua & Graff, 2017), and the MINST dataset from LeCun et al. (1998). The details of these datasets are presented in Table 1. In Table 1, each instance represents feature vector x E Rdd that is associated with one of the K arms, and dimension d the number of attributes in each instance.
Datasets:
Implementations: for LinUCB, we follow the setting in Li et al. (2010) to use disjoint models for different arms. For neural network based algorithms, we use ReLU neural network defined as in (2.3) with L 2 and
100 for the UCI datasets (Statlog, Magic, Covertype). Thus the neural network weights are W1 E md W2 E IR f=mm and O E R² respectively, where = 100, m 100, and d is the dimension of features in the corresponding task. Since the problem size of the MNIST dataset is larger, inspired by Hinton & Salakhutdinov (2006), we use a deeper NN and
set I. = 3, k 100 and 100, with weights W, Rmxd W2 E Rmxm W E R4xm.
8

---

Published as a conference paper at ICLR 2022
Table I: Specifications of datasets from the UCI machine learning repository and the MNIST dataset used in this paper.
Starlog
Magic
Covertype
MNIST
Number of attributes
9
11
54
784
Number of arms
7
2
7
10 60,000
Number of instances
58,000
19,020
581
581,012
-00)
200
Lntiza
#000
LeLGs
1930
8000
LauCs NarraCCO Neurs-LinUcs
6680
Nauml.co
-00
2000
0
Neusi- iicc
heurs-Linnic
1993 Naumi LPLCO
3300
2000
1930
3000
5000
12000 10003
2000
0000
5000
-2006
15660
3030
0000
5000
12000
12000
2000
5000
12000 10000
nund
sundd
runnd
(a) Statlog
(b) Magic
(c) Covertype
(d) MNIST
Figure I: The cumulative regrets of LinUCB, NeuralUCB, Neural-Lineat and Neural-L.nnUCB over 15, 000 rounds. Experiments are averaged over 10 repetitions.
and 0 E R We set the time horizon T = 15, 000, which is the total number of rounds for each algorithm on each dataset. We stochastic gradient decent to optimize the network weights, with a step size 724 =le-5 and maximum iteration number = 1, 000. To speed up the training process, the network parameter w is updated every H 100 rounds starting from round 2000. We also apply early stopping when the loss difference of two consecutive iterations is smaller than a threshold of and a = 0.02 for all algorithms, E [T]. For NeuralUCB and NeuralTS, since
1e-6. We set it is computationally unaffordable to perform the original UCB exploration as displayed in Zhou et al. (2020), we follow their experimental setting to replace the matrix Z E (d (d+7) in their papers with its diagonal matrix.
we plot the cumulative regret of all algorithms versus round in Figures I(a), 1(b) and I(c) for UCI datasets and in Figure ((d) for MNIST. The results are reported based on the average of 10 repetitions over different random shuffles of the datasets. It can be seen that algorithms based on neural network representations (NeuralUCB, NeuralTS, Neural-Linear and Neural-LinUCB: consis- tently outperform the linear contextual bandit method LinUCB, which shows that linear models may lack representation power and find biased estimates for the underlying reward generating function. Furthermore, our proposed Neural-LinUCB achieves comparable regret with NeuralUCB in all ex- periments despite the fact that our algorithm only explores in the output layer of the neural network, which is more computationally efficient we will show in the sequel. results in our experiment are well aligned with our theory that deep representation and shallow exploration are sufficient to guarantee good performance of neural contextual bandit algorithms, which is also consistent with the findings in existing literature (Riquelme et al., 2018) that decoupling the representation learning and uncertainty estimation improves the performance.
Results:
We also conducted experiments to study the effects of different widths of deep neural networks on the regret performance and to show the computational efficiency of Neural-LinUCB compared with existing neural bandit algorithms. Due to the space limit, we defer the results to Appendix A.
6 CONCLUSIONS
In this paper. we propose new neural contextual bandit algorithm called Neural-LinUCB, which uses the hidden layers of a ReLU neural network as a deep representation of the raw feature vectors and performs UCB type exploration on the last layer of the neural network. By incorporating tech- niques in liner contextual bandits and neural tangent kernels, we prove that the proposed algorithm achieves a sublinear regret when the width of the network is sufficiently large. This is the first regret analysis of neural contextual bandit algorithms with deep representation and shallow exploration, which have been observed in practice work well on many benchmark bandit problems (Riquelme et al., 2018). We also conducted experiments on real-world datasets to demonstrate the advantage of the proposed algorithm over LinUCB and existing neural contextual bandit algorithms.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their helpful comments. PX and QG are partially supported by the National Science Foundation CAREER Award 1906169 and IIS- 199-190. The views and conclusions contained in this paper are those of the authors and should not be interpreted as repre- senting any funding agencies.
REFERENCES
Yasin Abbasi- 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.
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, pp. 1638-1646, 2014.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization overparameter- ized neural networks, going beyond two layers. In Advances in neural information processing systems, pp. 6155-6166, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242-252, 2019b.
Robin Allesiardo, Raphaël Féraud, and Djallel Bouneffouf. A neural networks committee for the contextual bandit problem. In International Conference on Neural Information Processing, pp. 374 381. Springer, 2014.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang- On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pp. 8139-8148, 2019b.
Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-eepploiaatonn tradeoff using variance estimates in multi-armes bandits. Theoretical Computer Science, 410(19):1876-1902 2009.
Peter Auer, Nicolo Cesa-Biancha and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-222 2266, 2002.
Sivaraman Balakrishnan, Martin J Wainwright, Bin Yu, et al. Statistical guarantees for the em algorithm: From population to sample-based analysis. The Annals of Statistics, 45(1):77-120, 2017.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-difference learning con- verges to global optima. In Advances Neural Information Processing Systems, 2019.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint 1rXiv:1902.01384, 2019a.
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, 2019b.
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 kemnllized aumti-armed bandits. In International Conference Machine Learning, pp. 844 853, 2017.
10

---

Published as a conference paper at ICLR 2022
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff fune- tions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208 214, 2011.
Mark Collier and Hector Urdiales Llorens. Deep contextual multi-armed bandits. arXiv preprint arXiv:1807.09809, 2018.
George Cybenko.
Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Varsha Dani, Thomas Hayes, and Sham Kakade. Stochastic linear optimization under bandit feedback. In Conference Learning Theory, 2008.
Aniket Anand Deshmukh, Abhimanu Kumar, Levi Boyles, Denis Charles, Eren Manavoglu, and Urun Dogan. Self-supervised contextual bandits in computer vision. arXiv preprint arXiv:2003.08485 2020.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019a.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameteriize neural networks. In International Conference on Learning Representations, 2019b. URL https: /ttess///ppeeeeee
net wwt/tettteeeee
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL htLLtt/p//achivee ics. uci. edd.mldu
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.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786) 2006.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in neural information processing systems, pp. 8571- 8580, 2018.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Confer- on Artificial Intelligence and Statistics, pp. 2066-2076 2020.
John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in neural information processing systems, pp. 817-824, 2008.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228--2324 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):436 444, 2015.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems, pp. 8570-8581, 2019.
Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A personalized news article recommendation. In Proceedings of the 19th international conference World wide web, pp. 661-670, 2010.
approach to

---

Published as a conference paper at ICLR 2022
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contex- tual bandits. In International Conference on Machine Learning. pp- 2071-01222 2071-2000, 2017.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural trust region/proximal policy optimiza- tion attains globally optimal policy. Advances in Neural Information Processing Systems, pp- 10564-10575, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterizaaton:: global con- vergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory. 2020.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An em- pirical comparison of bayesian deep networks for thompson sampling. In International Confer- ence on Learning Representations, 2018. URL / http///pppe/reieeeee net/ wwrmm/ormmme/mmmm ?id=
SyYe6k-CW.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 1112:139--11, 2010.
Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018. ISSN 1935-8237.
Jyotirmoy Sarkar. One-armed bandit problems with covariates. The Annals of Statistics, pp. 1978- 2002, 1991.
Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian optimization using deep neural networks. In International conference on machine learning, pp. 2171-2180, 2015.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 2583/4), 1933.
Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini, Finite-time anal- ysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninh Conference on Uncer- tainty in Artificial Intelligence, pp. 654 654-663, 2013.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2020. URL https:t//// owwnreview....e.... net http://oruunii-BBssgeosrr00
Zhaoran Wang, Han Liu, and Tong Zhang. Optimal computational and statistical rates conver- gence for sparse nonconvex learning problems. Annals statistics, 42(6):2164, 2014.
Pan Xu and Quanquan Gu. A finite-time analysis of q-learning with neural network function ap- proximation. In International Conference on Machine Learning. 2020.
Pan Xu, Jian Ma, and Quanquan Gu. Speeding up latent variable gaussian graphical model esti- mation via nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 1933-1944, 2017.
Tom Zahavy and Shic Mannor. Deep neural linear bandits: Overcoming catastrophic forgetting through likelihood matching. arXiv preprint 1rXiv:1901.06111 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations, 2017. URL https: wpwprevenr...eeeeeop/pp/.. net httt//foummiice /tt///ourmmminyyaaaaaaaaa Sy8gdB9xx.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arX1v:2010.00822, 2020.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-basee exploration. In International Conference on Machine Learning, 2020.
12

---

Published as a conference paper at ICLR 2022
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. In Advances in Neural Information Processing Systems, pp. 2053- 2053-2062, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterizee deep relu networks. arXiv preprint orXiv1881.008888 2018.
13

---

Published as a conference paper at ICLR 2022
A ADDITIONAL EXPERIMENTAL RESULTS
In this section, we provide more experimental results that are omitted in Section 5 due to space limit.
A.1 COMPUTATIONAL EFFICIENCY OF NEURAL-LINUCB
Throughout the experiments, our Neural-LinUCCB algorithm is much more computationally efficient than NeuralUCB since we only perform the UCB exploration on the last layer of the neural network, where the dimension is much lower. In specific, on the Statlog dataset, it takes on average 1.11 seconds for NeuralUCB to finish 100 rounds (one epoch in Algorithm 1) and achieve the regret in Figure (()), while it only takes 0.58 seconds for Neural-LinUCB to finish 100 rounds and achieve the comparable or even better regret in Figure I(a). On the Magic dataset, the average runtimes for 100 rounds of NeuralUCB and Neural-LinUCB are 1.32 seconds and 0.81 seconds respectively. On the Covertype dataset, the runtimes of NeuralUCB and Neural-LinUCB are 1.02 seconds and 0.66 seconds respectively. And the MNIST dataset, the average runtimes for 100 rounds of NeuralUCB and Neural-LinUCB are 4.67 seconds and 1.29 seconds respectively. For practical applications in the real-world with larger problem sizes, believe that the improvement of our algorithm in terms of the computational efficiency will be more pronounced.
As we discussed in Section 5 and in the above paragraph as well, the computational efficiency of Neural-LinnUCH mainly stems from the design of shallow exploration. This is because in UCB based bandit algorithms we need to compute the inverse of matrix A every time step for selection (Line of Algorithm 1). Due to the large width of the neural network used in practice, the arm selection operation could be rather time consuming. However, the neural network weight can be updated periodically (i.e., in our paper it is only updated every H steps). To validate our analysis on computational efficiency, we further studied the time profiling the experiments conducted on MNIST to compared our proposed algorithm with NeuralUCB in more details.
Table 2: Profiling experiment on MNIST for running 100 rounds: runtime (seconds) for different algorithms on arm selection and network weight update.
Operations
NeuralUCB
Neural-LinUCB
Arm selection (Line 5 in Algorithm 1) Network weight update (Line 9 in Algorithm 1)
3.60
0.28
0.96
0.92
In particular, the setting is the same as that in Section 5 for MNIST experiments. We record the time cost of the most expensive two subroutines: (I) the operation of arm selection (Line 5 in Algorithm I); and (2) the operation of updating the neural network weights (Line 9 in Algorithm 1), for H 100 rounds. The time cost is presented in Table 2. For Neural-LinUCB, the arm selection operation takes about 0.28 seconds (this is 21.71% of the total time cost by the algorithm 100 rounds), among which the matrix inverse step only takes 0.17 seconds. For NeuralUCB, the arm selection operation takes 3.60 seconds (this is 77. 77.19% of the total time time cost by NeuralUCB for H 100 rounds). Therefore, the operation of arm selection in NeuralUCB much (almost 13 times) more time consuming than that in Neural- the UCB matrix Z: in NeuralUCB is defined as f w) fxx w) it needs to compute the gradients via back-propagation (0.93 seconds) and compute the matrix inverse (1.54 seconds), while our Neural-LinUCH algorithm only needs to compute the matrix inverse of a small matrix (0.17 seconds). To summarize, our method is much more computationally efficient.
in these
Moreover, since
A.2 IMPACT OF LARGE WIDTHS
Note that the requirement of width m in our Theorem 4.4 is extremely high. On one hand, our the- ory may be too conservative since the current understanding of deep learning is still very limited in the field. We believe our work is a good starting point towards understanding the behavior of deep bandits algorithms. On the other hand, we would also like to investigate the impact of mild overpa- rameterization on the regret performance of additional experiments the Statlog dataset with wider neural networks. In particular, the neural
in practice. Therefore, we conducted
14

---

Published as a conference paper at ICLR 2022
500
Neural-LinUCB (100)
Neural-LinUCB (1000)
400
Neural-LinUCB (10000)
cumulative regret
Neural-LinUCB (50000)
Neural-LinUCB (10000, 10000)
300
Neural-LinUCB (10000, 10000, 10000)
200
100
2000
4000
6000
8000
10000 12000 14000
round
Figure 2: Performance of Neural-LinUCB with different widths on Starlog dataset.
network parameters are listed follows
W I mx W2 m Wt E Økxm R²
where is the depth, & 100, d is the feature dimensions, and m the width. We conducted experiments for the following settings: (1) L 2, m = 100, and thus the hidden layer width is (100); (2) L. 2, m 1000, and thus the hidden layer width (1000); (3) thus the hidden layer width is (10000); (4) L- 2, and the hidden layer width is (50000); (5) L= 3, m 10000, and thus the hidden layer width (10000, 10000); and (6) = 4, m 10000, and thus the hidden layer width is (10000, 10000, 10000). The results are plotted in Figure A.2. We observe that the performance of our Neural-LinUCB algorithm is not negatively impacted by the width of the neural network. In fact, Figure A.2 shows improved performance of Neural-LinUCH when the total number of hidden nodes increases. This is consistent to the observations in Zhang et al. (2017) that overparameterrize neural network trained by gradient descent does not necessarily lead to overfitting and also aligns with our Theorem 4.4 that the regret bound of Neural-LinUCB decreases the width m increases.
2. m 10000, and
B MORE DISCUSSIONS ON ASSUMPTION 4.2
In this section, we are going to show that Assumption 4.2 could be satisfied as long as the feature vectors {x} lie in a begin subspace of Rdd Let us start with the case that Φ Rd Rm is two-layer ReLU neural network with vector output. In particular, we define Φ(x; w) as follows Φ(x; w) ofW (W2o 20 (W)x)), where w = (vec(W) 1), vec(W2)) W, E RRd W, E Rdxmm and is the ReLU activation function applied elementwise. We use u, to denote the i-th row of W1 and thus W, (u....., um)T where E Rd, Vi E [m]. Similarly, we have W₂ (V1,.... va)T. where v, E Rmm the j-th row W2. Vj E [d]. Let us denote h as the vector o 1x). We thus obtain
[u x 2 03u
1(v h 0 h
h
((x:w)
1(u 2 0) Ol
1 h 2 0) h
We use (x; w) to denote the [-th entry of vector ob(x; w). for any / [d]. Then it holds that ( w)
dvec iW 1[v] 0){1) 1u, 2 0}x of 1 0}x]],
for all E [d], where of the i-th element in vI. i E [m]. This further implies that
1 1(v h (u) [ 2 0}x of 1 [u 2 0}x T)
0Ø((: w) (vec(W,)
Bdxmd
1 20
03x ..... o/ 1, 2 0}x T)
15

---

Published as a conference paper at ICLR 2022
Similarly, compute the gradient of (xx;; w) with respect W2. In particular, we have
0 w) 1[v @ve)(vi) [o...., j#1.
[) 0Ju,x.
1( x 2 x},,,},
0Φ1 (x; w) åvec(v;)
Therefore, the gradient of ((x; w) with respect to W2 is
Odb (x:w) (vec(
0σ(x;v w)
E R gedmmd
Övec (2))
0
(x:w) (ve)
Lastly, we have
acp(x; x; w) Ow
Bo(x:w (vee(WW))
a (vec(W2)
E (mdd+m))
Therefore, for any two feature vectors x and x' from (EET,,))))))) if many nodes in the initial neural network ((x; wo) are activated or deactivated at the same time for both x and x', then the spectral norm of the matrix (p(x:wa) @ would satisfy the condition in Assumption 4.2. A ow
2w
more thorough study of this stability condition is out of the scope of this paper, though it would be an interesting open direction in the theory of deep neural networks.
C PROOF OF THE MAIN RESULTS
In this section, we provide the proof of the regret bound for Neural-LinUCB. Recall that in neural contextual bandits, we do not assume a specific formulation of the underlying reward generating function r(-). Instead, we use deep neural networks defined Section 2.2 to approximate r(-). We will first show that the reward generating function r(-) can be approximated by the local linearization of the overparameterized neural network near the initialization weight w() In particular, we denote the gradient of ((x; w) with respect w by g(x; w), namely,
g(x: w) V Vw w),
(C.1)
which matrix in Rdxx, We define Φ, (x; w) to be the j-th entry of vector (xx; w). for any j E [d]. Then, we can prove the following lemma.
Lemma C.1. Suppose Assumptions 4.3 hold. Then there exists w IRP such that |w--w(00]]e S
1//m r) (r r) and it holds that
r(x,,)) 0 ob( we-1) 0 g(x,;; (()) -w(O)).
for all & E [K] and t= I....,
Lemma C.I implies that the reward generating function r(-) at points {xi,s J Mejk can be ap- proximated by linear function around the initial point (o), Note that similar lemma is also proved in Zhou et al. (2020) for NeuralUCB.
The next lemma shows the upper bounds of the output of the neural network & and its gradient. Lemma C.2. Suppose Assumptions 4.1 and 4.3 hold. For any round index t E [T], suppose it is the q-th epoch of Algorithm 2, i.e., = (g - 1)H + for some E [H]. If the step size f in Algorithm 2 satisfies
Co
n R mm 5.5 log
and the width of the neural network satisfies
max(Llog(TK/)), at log(m/0), 5-6 18 16 (og((TK)),
(C.2)
16

---

Published as a conference paper at ICLR 2022
then, with probability at least 5 we have
83/2
|| 11 S n2//2Tn9/2L3 log"(m)
llg(x w ( - CIvdLm.
| w,)k2 5 (olog() log(TK/8),
for all t E (T), & E [K], where the neural network & is defined in (2.4) and its gradient is defined in (C.1).
The next lemma shows that the neural network oxx; w) is close to linear function in terms of the weight parameter around small neighborhood of the initialization point w(O))
Lemma C33 (Theorems 5 in Cao & Gu (2019h)). Let w, w' be in the neighborhood of wo, i.e., w, B (Wo,,) for some w > O. Consider the neural network defined in (2.4), the width m and the radius w of the neighborhood satisfy
m 2 Co max log(m//)), ~ 1// 8/3 (og(m)))lll/////)//
w S (1
then for all x E (xx, (xx.ateep1)eee111 with probability at least - 8 it holds that
1 w) (x; -x,( S 4/3 3 L /m log m,
where (x(x; w) is the linearization of Φb (x; w) at w' defined as follow: ()
(V w'), w w').
(C.3)
Similar results on the local linearization of an overparameterized neural network are also presented in Allen-Zin Zhu et al. (2019b); Cao & Gu (2019b).
For the output layer 0", we perform UCB type exploration and thus we need characterize the uncertainty of the estimation. The next lemma shows the confidence bound of the estimate 0, in Algorithm 1.
Lemma C.4. Suppose Assumption and 4.3 hold. For any ò (0, 1), with probability at least 1- 6, the distance between the estimated weight vector 0, by Algorithm 1 and 0" can be bounded as follows:
0, 0" - A
(xx,a, w.-1)6p g(x,,a, : (w) (ww")( ww
A.
S vy 2ddogg( tllgg HK)/A) log 1/8) 11/2M,
for any & [2].
Note that the confidence bound in Lemma C.4 is different from the standard result for linear textual bandits in Abbasi- Yadkori et al. (2011). The additional term on the left hand side of the confidence bound is due the bias caused by the representation learning using deep neural net- work. To deal with this extra term, we need the following technical lemma.
Lemma C.5. Assume that A, AI E
Φ.Ø. where &i Rd and || < G for all t and some constants X, G > O. Let (G. be a real-value sequence such that [sel < U for some constant U/ 0. Then have
A
Σ
S.C.
S 2U',
=t= = 1,2,
The next lemma provides some standard bounds on the feature matrix A,, which is a combination of Lemma 10 and Lemma 11 in Abbasi- Yadkori al. (2011)
17

---

Published as a conference paper at ICLR 2022
Lemma C.6. Let {xi be sequence in Rd and À 0. Suppose
|xx||2 S G and A 2
m for some G > O. A, AI E X,X; Then have
T
det(Ar) det(AI) I 22dlog(1 + (Ad))
dct(A,) (A + /d)) and
x A I 2og
Now we are ready to prove the regret bound of Algorithm 1.
Proof of Theorem 4.4. For time horizon T, without loss of generality, we assume T QH for some epoch number Q. By the definition of regret in (4.3), we have
T RT Σ (F(x),;;) F(xe,a))) =E ΣE
" (F (Fx F(x
Note that for the simplicity of presentation, we omit the conditional expectation notation of w()) in the rest of the proof when the context is clear. In the second equation, we rewrite the time index t = qll + i as the i-th iteration in the g-th epoch.
By the definition in (2.1), we have E] linearization of reward generating function, we can decompose the instaneous regret into different parts and upper bound them individually. In particular, by Lemma C.I, there exists vector w R" such that we can write the expectation of the reward generating function as a linear function. Then it holds that
r(x.k) for all f [7] and & E K. Based on the
r(Xt,a)) - -r(xt,,,) 0g [g((x (xx,,a;; w()) - -(Xi,aai w w((0)]] [w(])](w>>> w()))
00 (6(xx,0;) Wo-1) 0(xx,,, Wc-1)]
0 [g(Xraji w (0)) - -8(xxaai (8(xraiiw.(00) w.(01)] (w" - -w((o)
+ 0 10 (xx,,a)) W.-1) 2(xx,a W1-1)]
-0,-1 0r) (x1,a7 wi-1) ((xx,a,..... w1]
(C.4)
The first term in (C.4) be easily bounded using the first order stability in Assumption 4.2 and the distance between w and w- in Lemma C. The second term in (C.4) is related to the optimistic rule of choosing arms in Line 5 of Algorithm 1, which can be bounded using the same technique for LinUCB (Abbasi- Yadkori et al., 2011). 1). For the last term in (C.4), need prove that the estimate of weight parameter 0, lies in a confidence ball centered at 0* For the ease of notation, we define
M, AT ((xa,, 1. W. ((x,,,;; (ww))(w" w (0)).
(C.5)
8=1
Then the second term in (C.4) can be bounded in the following way:
(0,-1 0*) (6 (xx,07 W.-1) - 25 ((x1))::(-1))
- - 0" - M,-1) (xr.0; We-1) + (0.-1- 0 -M,-1) ((xraaiWe-i)
M, [ w.-1) 6(x1,00 wt-1)]
110-1 0- - -M,- A 110( w.- |
+ 01 0- - -MMMMM1 M,-IllA | 11 w.
+ -||M,_ (xx,a; (oxx.aa;w..))) w.- - ((xe,ag; w
ov we-1) A,2, + an (oll10(Xxt, w.- A-
+ |M,-ll 1 (10(x0,075 We-1) ((x,,00 we-1)
(C.6)
18

---

Published as a conference paper at ICLR 2022
where the last inequality is due to Lemma C.4 and the choice of ag Plugging (C.6) back into (C.4) yields
r(x),a)) - r(x(,a)) S ail arll@(xi,, w. wi- 1) A - aell@(xx,, i wi-1)lla, 1
aall@(xx,a) W wi- 1011 a W W 1
| l2 (xL,;; Wi-1) (xxx,.ii wc-1)llz
+ 180ll2 (lg( w(()) g(Xi,axi w (l) || - w
20x Bov,l<b(xt.nn (xt,, wr-1) - + ||M ||2 |1 Xt,azi we-1) 2 (xt.ar We 1) ll2
+ 4.pl1 ||Xt,aū Xt,ar l|w"-w 1l
(C.7)
where the first inequality used the definition of upper confidence bound Algorithm 1 and the second inequality is due to Assumption 4.2. Recall the linearization of Ø in Lemma C.3, we have
((x: wt-1) Φ(x; wo) + g(x: wo) - Wo).
Note that by the initialization, we have (x(x; wo) 0 for any E Rd. Thus, it holds that
Φ(xra;i Wr-1) ((xx,ar Wr-1)
(xx,,t1 Wi-1) ((xe,at wo) + (x wo) - @(xi,aii WI-1)
= < (xt,a; Wc-1) 2 (xx,,tt) w(-1) + g(x wo)(w,-) wo)
+ (xx,,, We-1) - (xxx,a we-1) - g(xt,. wo) - -Wo)
(C.8)
which immediately implies that
[| wi-1) - Φ ( w1-1)
$ =|00xxx,;;; Wi-1 (xx,,t) wr-1) llz + (xxx,, wc-1) 2 (xx,or w
+ (g(x,,;; Wo) - g(Xe,a wo)) (W--1 - wo)ll2
I 4/3
L 222 /m log m
Xt,a, llz/ wi-1 w/
(C.9)
where the second inequality is due to Lemma C.3 and Assumption 4.2. Therefore, the instancous regret can be further upper bounded as follows.
r(xi,a;) -r(Xt,a))
S 20rl/ (Xx,, Wt- )ll 1ll, + l 100l2 ||x0,0;
Xt,or ll2 l|w" (0 ||2
+ +||M-lll2 (Cow 4/3 4/3 1/2 mmgoog m + Lxipllxe,, - Xt alllllll [lal|We-1-- - w()) (C.10)
By Assumption 4.1 we have ||se,0; xx.0r 2. By Lemma C.1 and Lemma C.2, have
(w*-w((') w/ v 1/m(r - T) -r--).
83/2
(C.11)
||w, - ww 10 m L log (m)
In addition, since the entries of 0n are i.idd generated from N0, 1/d), we have ||0012 < 2(2 + (og(/)))) with probability at least 1 - 5 for any 8 > 0. By Lemma C.2, we have [gg(X ((()) Ci Vdm. Therefore.
10 gxx,,,, w (") - -w(0))| s 1)
Then, by the definition of M, in (C.5) and Lemma C.5, we have
MM ll2 S Czcl 1og(1 (og(1188(( F f).
(C.12)
19

---

Published as a conference paper at ICLR 2022
Substituting (C.12) and the above results ||xt,a Xt, 112. 100112, || -----(011 and ||w-11 w back into (C.10) further yields
r(x(,a;) r(
I 20,110(Xx,a0 : w + Culuipm log((1/)(r Hr (r-
+ (ow / + m1/2Tn L (m) Cade (og((/ r).
Note that we have w = 11m F(l--1) by Lemma C.I. Therefore, the regret of the Neural-LinUCB is
Q
H
Po S
QH max of RE(T]
ΣΣ
((xx, Wo A, + Caltipm 1/2T Vovllolgg/ log((1/))]1= F
g=1 1=1
CoTI3dV/ Vlo ml|r
4/3
20
Czdl vlog(1/8)]l= -F|lH-
m//6
m2/2 18 log" (m)
s Cs TTV/ollo++1100 (Ad) ( ((lg + log 1/8 11/2
+ LC 1 (
1/6T
FilH-1,
where the first inequality is due to Cauchy's ' inequality, the second inequality comes from the upper bound of a in Lemma C.4 and Lemma C.6. {Cy))=o...., 6 are absolute constants that are independent of problem parameters.
Proof of Corollary 4.6. directly follows the result in Theorem 4.4.
D PROOF OF TECHNICAL LEMMAS
In this section, we provide the proof of technical lemmas used in the regret analysis of Algorithm
D. PROOF OF LEMMA C.I
Before we prove the lemma, first present some notations and supporting lemma for simplifica- tion. L (0 w " E RR+P be the concatenation of the exploration parameter and the hidden
layer parameter of the neural network fxx: 3) 0 oxx;;) w). Note that for any input data vector X E IRd, we have
0 03 fxx = ( w) o o(x:w)
(o(x: g(x:w))"
(D.I)
Ow
where g(x; w) is the partial gradient of (xx; w) with respect to w defined in (C.1), which is matrix in dx Similar to (4.2), we define H to the neural tangent kernel matrix based on all L+1 layers of the neural network f(x; (3). Note that by the definition of H in (4.2), must have H = H B for some positive definite matrix E TK x The following lemma shows that the NTK matrix is close to the matrix defined based the gradients of the neural network TK data points.
Lemma D.1 (Theorem 3.1 in Arora et al. (2019b)). Lete and å E (0, 1). Suppose the activation function in (2.3) is ReLU, i.e., a1(x)) max .)), and the width of the neural network satisfies
1,14
log (7))
2 Ω
(D.2)
Then for any x, x' Rd with =x||=|||x||
with probability at least 1 over the randomness of the initialization of the network weight w it holds that
xf
1
x3)
Hx+1(xx))) Sc.
m 03
Vm
03
20

---

Published as a conference paper at ICLR 2022
Note that in the above lemma, there is factor 1/vm before the gradient. This is due to the ad- ditional ym factor in the definition of the neural network in (2.3), which ensures the value of the neural network function evaluated at the initialization is of the order O(1).
Proof of Lemma C.I. Recall that we renumbered the feature vectors {xr,* hejr [[[]] for all arms from round to round 7 as {xi)i=t,... By concatenating the gradients at different inputs and the gradient in (D.I), we define V E [TKx(d+p)) as follows.
((x::(0))
Og ((xx)w(())
((x1;w)
V
Φ(x;; w (O)T
Og g(x; w(ll)
m
Vm
0 0 Φ x w) ag
[ K; ())T
0 g(xrk; w()))
By Applying Lemma D.I, we know with probability at least ô holds that
y j.. L (-) H (x,, x;) <
for any 0 as long the width satisfies the condition in (D.2). By applying union bound over all data points {xi,..., Xt,...,, XTк ), we further have
M HH++ TKK.
Note that H is the neural tangent kernel (NTK) matrix defined in (4.2) and H is the NTK matrix defined based on + layers. By Assumption 4.3, H minimum eigenvalue Ao > O, which is defined based on the first T. layers of f. Furthermore, by the definition of NTK matrix in (4.2), we know that H = H B for some semi-positive definite matrix B. Therefore, the NTK matrix H4+1 defined based on all L + 1 layers is also positive definite and its minimum By triangle equality we have V eigenvalue is lower bounded by Ag. Let e >g Het1llFI HL+1 An/2I > 1/2H HL+1 T H ||2I HL+1 T
which means that & semi memi-definite positive and thus rank L = TK since m TK.
We assume that y be decomposed as L PDQT, where P E ęТК*тк is the eigenvectors diagonal matrix with the square root of cigenvalues of y& and Q T E (d+xx the eigenvectors of y and thus Q Q IrK- We Q1 RdTT and Q2 E BPXTK to denote the two blocks of Q such that Q IQI Q-
of UT and thus PPT IrK. D E RTК*TK
By definition, we have
Q Q2
Q Qq
Q
- QT ITK.
Note that the minimum singular value of Qı E RdXTK is zero since d is fixed number and TK > d. Therefore, it must hold that rank Q2) = TK and thus Q Q2 is positive definite. Let (r(x1).... r(x))...)(()).........)))))))))) r(x))... r(XTx)) E TK denote the vector of all possible rewards. We further
define E RTTdxx and $ E Tkd as follows
g(x;;
Φ(x1,11 Wo)
1
G
g(x; (0))
Φ(x,, Wt-1)
(D.3)
Vm
g(xTk: w (0)
Φ (x (xxx wT-
and θ O I.T KxTKd follows
T
T
0
Og
0
(D.4)
0
0
21

---

Published as a conference paper at ICLR 2022
It can be verified that v PD Q21 and PDQ Og Note that have Q Q2 is positive definite by Assumption 4.3, which corresponds to the neural tangent kernel matrix defined on the first L layers. Then define w as follows
w w(O) 1tt TD (r-
(D.5)
We can verify that
- Vmp2 (w* - ww
On the other hand, we have
|w" 10 & 1/mm(- -- ( PD QQ "p- O'$)
PPD
11/m(r -0 H r- -
which completes the proof.
D.2 PROOF OF LEMMA C.2
Note that view the output of the last hidden layer Φ((x w) defined in (2.4) vector-outpe outputt neural network with weight parameter w. The following lemma shows that the output of the neural network Φ is bounded at the initialization.
Lemma D.2 (Lemma 4.4 in Cao & Gu (2019b)). Let 5 E (0, 1). and the width of the neural network satisfy m 2 CoL LTT Then all [T]. E [K] and j [d]. we have Jo (i..ki ki (()) s (oo/oo((K/)) with probability at least 8, where w(O) the initialization of the neural network.
In addition, smaller neighborhood of the initialization, the gradient of the neural network Φ is uniformly bounded.
Lemma D.3 (Lemma B.3 in Cao & Gu (2019b)). Let w S. CoL CoL m) and w E I8 [B(wo, w). Then for all E (T). & [K] and j E [d]. the gradient of the neural network & defined in (2.4) satisfies Wy w)ll CivLm with probability least T TK L2 exp(- 223 L).
The next lemma provides upper bound the gradient of the squared loss function defined in (3.3). Note that our definition of the loss function is slightly different from that in Allen Zhu et al. (2019b) due to the output layer 0, and thus there is additional term on the upper bound of ||0,1l2 for all E (T].
Lemma D.4 (Theorem 3 in Allen-Zhi et al. (2019b)). Let w < C683/2 /2/////1////" log* m). For all over the randomness of ((),,
w E B ((w ,w), with probability at least - holds that
|[ (TTm((w)sup,n)) 0
Proof of Lemma C.2. Fix the epoch number q and we omit it in the subscripts in the rest of the proof when no confusion arises. Recall that w()) is the s-th iterate in Algorithm Let be any constant. Let w be defined as follows.
5/2 1/2T 9/2 L log (
(m))
(D.6)
We will prove by induction that with probability at least 8 the following statement holds for all 0, 1....,n
Mog(TK/0)
6y(x;
Co
for Vjj [d]; and [[w( w( S
(D.7)
h+1
h=0
First note that (D.7) holds trivially when = due to Lemma D.2. Now we assume that (D.7) holds for all j O........ The loss function in (3.3) can be bounded follows.
9Hf
q/l
((w(i))
Σ 00 (xxx; w() - 22)3 <
2( 0 12 ||
w0) + 1).
22

---

Published as a conference paper at ICLR 2022
By the update rule of 0t, we have
|00112 = ( (xx; olx:
Σ
(x;; ((;;; -1)
S 2d,
(D.8)
1=1
where the inequality is due to Lemma C.5, which combined with (D.7) immediately implies
((w(0) S C.T. (og(TK/6)
Σ
1 h++1
S.Td log(TK/6) log n.
(D.9)
h=U
Substituting (D.8) and (D.9) into the incquality in Lemma D.4, we also have
|V s C2y dl (m((((6) s CadTTlog(n) llggoTT//))
(D.10)
Now consider w (e+1), By triangle inequality have
[w(++)) - w/ S
w(++1) - w00ll22
f=U
" VL((w))]l1
bd log((n) log
(D.11)
where the last inequality is due (D.10). If we choose the step size By in the q-th epoch such that
17
S
(D.12)
d d'I'n (mlg))///
then we have [[w, (x+1) w 1|2 I w. Note that the choice of m, satisfies the condition in Lemma C.3. Thus know 6, (x; w) is almost linear w, which leads
1 (x: w (x+1)) - (x,
+ (Vá, (x; w())), w(+11) - w())) + Csw C/w 1/3 / log m
Cooo (oo((TK/8) h 1+1
my dm (LC( 2C 4/3 13d m log
Co Mog( (og(((())) +
logn
h+1
2/3 4/3 1/3/4//31100 1/2 Vmllgm
Co Co (TK(/)
wv
+
+ 2/3 log m,
(D.13)
h+1
h=0
where in the second inequality we used the induction hypothesis (D.7), Cauchy- Schwarz inequality and Lemma D.3, and the third inequality is due to (D.10). Note that the definition of w in (D.6) ensures that w wydm 1/2 and 4/3 1,3 /m log & 67- Vlog m 1/n as long as m 2 n. Plugging these two upper bounds back into (D.13) finishes the proof of (D.7).
Note that for any E [7], we have w, = w/!)) for some g = 1,2, Since we have w. E B ( w), the gradient g(x; w()) can be directly bounded by Lemma D.3, which implies [|g(x; (()) < Ce CeVdLm. Applying (D.7) with
have the following bound of the neural network function (xx; w (n)) = ((x; w.) for all in the q-th epoch
[x w.)ll2 S Co Cavdlog(n) log(TK)5),
which completes the proof. In this proof, {C, > 0}}=o,... are constants independent of problem parameters.
23

---

Published as a conference paper at ICLR 2022
D.3 PROOF OF LEMMA C.4
The following lemma characterizes the concentration property of self-normalized martingales.
Lemma D.5 (Theorem in Abbasi-Yadkori et al. (2011)). Let { be real-valued stochastic be a stochastic process in R Let F, (X1, Xx+1, ,, Ex) be process and {xx j
o-algebra such that x2 and & are meeauuraa.. Let A, AI + E.=1 x,x_" for constant If we assume & v-subGaussian conditional on Ft-1, then for any E (0, 1), with probability at least 1 - 8, we have
0 and S. =
|| || S 2v² log dct(A,) 1/2 det deI (AI)-1/2 1/2
6
Proof of Lemma C.4. Let Φ.
[ Wo). ...., a(x,,a. W E Rd be the collection of
feature vectors of the chosen arms up time and i, (fi..... F2) RT)T be the concatenation of all received rewards. According to Algorithm 1, we have A, = XI Φ and thus
0, A, A (AI Φ.Φ +T,
By Lemma C.I, the underlying reward generating function r; = r(Xi,a.) = B[F(xx, Xr,a,l can be rewritten as
= (0" , we-1)) + 0 g(x,,a, w (0) (ww) (())..
By the definition of the reward in (2.1) we have Fr rx & Therefore, it holds that
0, A, + +A,
Σ
(00 g(,,,,, w (0)) - (w( + Ex)
0" - 0 + +
Σ o (xx w. gXxe,,, (ww))(w'-- -w Es).
Note that A, is positive definite long as À > O. Therefore || lla, and || lla, well defindd norms. Then for any E (0, by triangle inequality we have
0 - 0" - D. (())) S 1010 A. + |
(eet(A,) 1/2 del((A)-1) 1/22
S V 2 2og
+ 2/2
holds with probability at least 1 - 6, where in the last inequality we used Lemma D.5 and the fact that ||0* Il I A -- 1/21100 I A 1-1 by Lemma C.I. Plugging the definition of o,, θ and Ge and apply Lemma C.6, further have
0, 0 A
Σ : g(x,,a,; (w)) :
- (w)
A.
Svn 2 t(lo HK)/A) log 1/0) 1122
where we used the fact that [x) Cy7log HK by Lemma C.2.
D.4 PROOF OF LEMMA C.5
We now prove the technical lemma that upper bounds ||A," E.= 2.Col22
Proof of Lemma C.5. We first construct auxiliary vectors Φ. Rd-1 and matrices B, R(d4 (xx+1)x(d+1) for all 1,... in the following way:
G sb
A 0.
0.
B.
(D.14)
v1
+
0
0
24

---

Published as a conference paper at ICLR 2022
where Og Rd is all-zero vector. Then by definition immediately have
A, Σ 0.5o = B,
355
(D.15)
1
For all 8 = 1, let {Ba, } be the coefficients of the decomposition of & the natural basis. Specifically, let fei..... od+1) be the natural basis of Fd+1 such that the entries of ej are all zero except the j-th entry which equals 1. Then we have
U. S. = Σ Be.eoj Vs =,2,,2.... 1,2,...
(D.16)
1=1
We can conclude that 18a,rl S since Kal S U and 11 S Moreover, is easy to verify that | la for all t 2 1. Therefore, we have
B,
B
Φ
==1
1
==1
d
B
0 U
B ej
s=1
B
2 B e/
1=1
8=1
SU) Σ
B,
Φ の
Besl
v A,
Σ 1-1
Σ
Ban
(D.17)
where the inequality is due to triangle inequality and the last equation is due to the definition of Φ and B, in (D.14). For each j = I..... + 1, we have
A
$5 2b Bag
A
Σ
Φ. Ba.
A,
Σ
D. Ban
sc .0.
sE(t):9..300
A
Φ.Φ Pa.j
+
A
Σ
Φ (-
(-Ba.)
S 20
2
(D.18)
Since have [Bag] S 1, it immediately implies
A, = XI+ e=1
Σ
La T
20 20
A, XI
Σ
L. (-Baa).
Further by the fact that ||A B BB|2 I 1 for any A yields
B > O, combining the above results with (D.18)
A,
D
Bad 2.
#=1
2
Finally, substituting the above results into (D.17) and (D.15) we have
A
H.C.
< 2Ud,
1=1
which completes the proof.
25


Reviews:
[{"review_id": "uobTCkYlwpJ", "reviewer": "Reviewer_hPGC", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strengths: \n\n1. The studied neural contextual bandit is very interesting and important in the area of applying neural networks to online learning.\n2. The proposed algorithm significantly reduces the computation costs when compared to existing neural contextual bandit algorithms.\n\nWeakness:\n\nWhile the proposed idea, i.e., transforming the raw feature vector using the last hidden layer of a deep ReLU neural network and adopting an UCB approach to explore in the last linear layer, is simple and effective, this idea is inspired by existing Thompson Sampling based work [Riquelme et al. 2018]. In addition, several techniques in the regret analysis of this paper are similar to existing works, e.g., [Riquelme et al. 2018; Zhou et al. 2020], which reduce the technical novelty of this paper.\n\n\n---After Rebuttal---\n\nI thank the authors for their response. However, my concern on limited contribution and novelty was not well addressed. See my following comments for details. I plan to stick my score 3, i.e., reject.\n\n1. Algorithmic design.\n\nThe high-level idea of decoupling representation learning and exploration is originated from Riquelme et al. (2018). \nAs we know, Thompson Sampling and UCB are two standard algorithmic styles in bandits.\nWhile Riquelme et al. (2018) is a Thompson Sampling based algorithm and you design a UCB based algorithm, I do not think that adapting an existing idea in Thompson Sampling type algorithm to the UCB type algorithm is a significant contribution in algorithmic design. \n\n2. Theoretical analysis\n\nI appreciate that you propose the first theoretical analysis for the idea of decoupling representation learning and exploration on your UCB type algorithm, while prior work [Riquelme et al. (2018)] does not give theoretical analysis on their Thompson Sampling type algorithm. \n\nHowever, it is well known that the Thompson Sampling based analysis is intrinsically more complicated and harder than the UCB based analysis, which reduces the technical challenges of analyzing this idea on your UCB type algorithm to some degree.\n\nI go through the new technical contributions you mentioned, i.e., Lemma C.1 and Lemma C.4. The proofs of Lemma C.1 and Lemma C.4 also rely on prior NTK works, e.g., Theorem 3.1 in Arora et al. (2019b), Lemma 4.4 in Cao & Gu (2019b), Lemma B.3 in Cao & Gu (2019b), Theorem 3 in Allen-Zhu et al. (2019b). \nIn my opinon, the analysis is a standard combination of existing techniques from prior neural contextual bandit [Zhou et al. 2020] and NTK [Arora et al. (2019b); Cao & Gu (2019b); Allen-Zhu et al. (2019b)] papers, following the high-level idea from [Riquelme et al. (2018)].\n\nFrom my view, the biggest technical contribution of this paper is that you borrow many techniques from neural contextual linear bandit [Zhou et al. 2020] and NTK [Arora et al. (2019b); Cao & Gu (2019b); Allen-Zhu et al. (2019b)] to execute the high-level idea of decoupling representation learning and exploration from [Riquelme et al. (2018)] in theoretical analysis. However, I think that the contribution and novelty is weak.\n\n----Additional Response----\n\nI have read the authors' further response. Unfortunately, my concern on technical novelty and contributions was not relieved.\n\nThis paper borrows the high-level idea of decoupling representation learning and exploration from [Riquelme et al. (2018)] to design a UCB-type algorithm, and analyzes it by borrowing many techniques from existing UCB-type neural contextural bandit/NTK papers [Zhou et al. 2020;Arora et al. (2019b); Cao & Gu (2019b); Allen-Zhu et al. (2019b)]. \nAlthough this paper well executes the high-level idea in [Riquelme et al. (2018)] and completes the analysis (in the more well-studied UCB style), I do not think this is a big contribution.\n\nThe technical novelty/contribution of this paper is very limited.\nNot only the theoretical analysis of this paper is mostly built upon existing works  [Zhou et al. 2020;Arora et al. (2019b); Cao & Gu (2019b); Allen-Zhu et al. (2019b)], but also the idea of algorithm design also comes from existing work  [Riquelme et al. (2018)].\n\nMy opinion can be supported by the following facts in the proof details in this paper:\n\nIn Appendix C, to prove the main theorem, the authors wrote Lemmas C.1-C.6, among which Lemmas C.1, C.3, C.6 (or their similar forms) have already appeared in existing papers [Zhou et al. 2020], [Cao & Gu 2019b], [Abbasi-Yadkori et al. 2011], respectively. \n\nIn Appendix D, in the proof of (the only new) Lemmas C.2, C.4, C.5, the authors further borrowed many existing techniques, including Lemmas D.1 [Arora et al. (2019b)], D.2 [Cao & Gu 2019b], D.3 [Cao & Gu 2019b], D.4 [Allen-Zhu et al. (2019b)], D.5 [Abbasi-Yadkori et al. 2011]. \nIn addition, the authors also followed the well-known analysis procedure of self-normalized concentration bound (in the proof of Lemma D.5) and confidence ellipsoid  (in the proof of Lemma D.4) from [Abbasi-Yadkori et al. 2011].\n\nIn conclusion, unfortunately, I do not think this paper has sufficient technical novelty. I will stick to my recommendation 'reject'.\n\n", "summary_of_the_paper": "This paper studies neural contextual bandits and proposes an algorithm that transforms the raw feature vector using the last hidden layer of a deep ReLU neural network, and uses an UCB approach to explore in the last linear layer. Compared with existing neural contextual bandit algorithms, the proposed algorithm attains computation efficiency. Regret guarantees and empirical results are provided to demonstrate the effectiveness of the proposed algorithms", "summary_of_the_review": "Overall, I think that the studied neural contextual bandit problem in this paper is very important. The idea behind the proposed algorithm is simple and effective. Theoretical and experimental results are provided to demonstrate the effectiveness of the proposed algorithm. However, this paper borrows the idea and analytical techniques in prior works and lacks theoretical novelty.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hZ79BvR-W_Z", "reviewer": "Reviewer_pfBo", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\nStrengths:\n- The paper is well written, algorithmic motivations are clear, and the setting is interesting.\n- The theoretical results, which are the main contribution, are nice and the assumptions made are very clearly described and contextualized.\n- Experimental results consider several reasonable domains+baselines and support the claims.\n\nWeaknesses:\n- The main weakness is that the algorithm proposed is not particularly novel, since (Riquelme et al. 2018) already introduce the \"decoupled deep representation+last layer search\" methodology in a previous paper. So the question is whether the new regret analysis is enough on its own. For instance, the results are given for UCB only -- could a similar analysis be extended to the Thompson sampling case (i.e., that used in Riquelme et al. 2018)?\n- There is also some concern about the requirement on the width of the neural network in thm 4.4 being so large in order for the main O(\\sqrt(T)) bound to hold, rather than a maybe more honest O(m^{-1/6}T) bound, but the authors do at least provide some empirical evidence in the appendix that suggests the performance of their algorithm is not heavily reliant on very large values of the network width.\n\n-------------------------------\nUpdate: I have read the author response. They adequately address my few minor concerns and so my opinion to accept stays the same.", "summary_of_the_paper": "Authors tackle the setting of contextual bandits, using deep representation learning combined with an upper confidence bound algorithm. The main contribution of this work is to provide a regret bound for the setup which decouples the representation learning from the UCB search, by searching only over the last layer of the network. The setting had been studied before, but only empirically, and using Thompson sampling rather than UCB. Authors validate their results empirically on several domains from the UCI data repo, as well as on MNIST, comparing against state of the art baselines.\n", "summary_of_the_review": "I am recommending accept because the theoretical results are interesting, and combined with the given very clear discussion about the assumptions in context, I think provide a decent baseline for future such analyses, even if assumptions such as the large network width are restrictive.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bRXU4vyuJpC", "reviewer": "Reviewer_hExw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written. The studied problem is significant. The theoretical results are interesting. \n\nThe reviewer has some comments and questions.\n\nIf Neural-LinUCB reduces the computational cost of NeuralUCB, it remains very high in comparison to LinUCB due to the episodic retraining of the deep neural network. Worst, the computational cost over-linearly increases with T since the deep neural network is retrained every H episode with all data. Neural-LinUCB cannot be used if T is too large. \nDo the authors have any leads for handling this practical problem?\n\nThe theoretical results are very interesting since it concerns the best performer in contextual bandits, but they are still quite weak. \n\nFirst, the regret upper bound depends on r-\\tilde(r), the regret between the obtained mapping of the reward function and the best mapping. It seems not oblivious that the right term of R_T in corollary 4.6 does not scale in \\sqrt(T).\n\nSecond, the condition m \\geq T^3 seems strong and confirms that the proposed algorithm does not scale with T. \n\nAFTER REBUTTAL\nI thank the authors for their answers. The analytical results on the contextual bandits with Deep Neural Networks are not totally news, as well as the algorithm with shallow exploration on the last layer, but together, they constitute a significant step. The proposed algorithm is a LinUCB-like algorithm, but that uses the powerful representation obtained in the last layer of a Deep Neural Nertwork to perform LinUCB. As a result, a clear improvement of performances in comparison to LinUCB, and moreover this fixes a known issue of LinUCB: due to the matrix inversion, LinUCB cannot process more than few hundreds of features. Here due to the use of a representation layer, this issue is fixed. An efficient Neural Contextual Bandit algorithm is analyzed, and this could have a deep impact on the bandit community. That is why I vote for acceptance.\n", "summary_of_the_paper": "This paper study a novel contextual bandit algorithm: Neural-LinUCB.\nAs in (Riquelme et al 2019), the idea of this algorithm is based on decoupling deep representation learning and exploration. A deep neural network learns the mapping between the context $x_{t,a_t}$, while a linear bandit, OFUL (Abbasi-Yadkori 2011), chooses the arm to play.\nIn contrast to (Riquelme et al 2019), a regret upper bound of the algorithm a regret upper bound of the algorithm is stated in Corollary 4.6. The proposed algorithm is also an improvement over NeuralUCB (Zhou et al 2020) for two reasons: the computational cost of the exploration is lesser, since the exploration is only done in the last layer of weights, and the regret upper bound is tighter. Indeed, in contrast to (Zhou et al 2020) it does not depend on the dimension of the tangent kernel matrix, which can be in O(KT).\nExperiments, done on four contextual bandit problems, show that Neura-lLinUCB outperforms LinUCB and performs as well as NeuralUCB and NeuralTS.\n", "summary_of_the_review": "The paper is well written. The studied problem is significant. The theoretical results are interesting. The reviewer accepts this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2dNI7wa2wRp", "reviewer": "Reviewer_16Sn", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The authors combine existing techniques to create an interesting algorithm for contextual bandits. Although the combination is not novel, the authors make a theoretical contribution by demonstrating that the combination has sub-linear O(\\sqrt(T)) regret.\n- The paper is well written, limitations are clearly stated.\n- The authors show that their proposed algorithm outperforms the existing algorithms.\n\nWeaknesses:\n- Is the direct comparison with the existing neural bandit algorithms possible? It appears that this paper has an additional assumption than the existing literature on neural bandits. I am not sure even the regret bounds can be compared.\n- The gap between the theoretically suggested setting and the experiment: there seems to be a huge gap between what is shown theoretically and what is executed in the experiments, for example, $m$. Can you show at least some experiments on how the algorithm behaves with a very large value of  $m$ which is what the theoretical results are based on?\n", "summary_of_the_paper": "The paper presents a new neural-bandit algorithm with shallow exploration and provides a regret bound for the proposed method. The existing approaches have introduced deep neural networks based bandit algorithms to learn reward functions, in which exploration takes place over the entire network parameter space, which can be inefficient for large-size networks which are typical in NTK based approaches. The authors address this by taking an existing approach that decouples the deep neural network feature representation learning from most of the exploration of the network parameters by only exploring over the final layer of the network. \n\nDespite the fact that this idea of shallow exploration has been proposed previously, there has not been a theoretical analysis with a regret bound. The authors analyze a UCB version of this approach, then build from techniques from both deep neural contextual bandits and linear contextual bandits to prove an O(\\sqrt(T)) regret bound. Finally, the authors present experimental results to show that their algorithm work well in practice.", "summary_of_the_review": "With the points I made above, I am leaning slightly on acceptance. I hope the authors address the concerns mentioned above.\n\n========== Post-reponses ================= \n\nThanks to the authors for the responses. I have read the comments of the other reviewers. I am staying with the current score.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the neural contextual bandit problem, for which existing approaches consists rely on bandit algorithms based on deep neural networks to learn reward functions. In these existing strategies, exploration takes place over the entire network parameter space, which can be inefficient for the large-size networks typically used in NTK-based approaches. In this work, the authors address this by building on an existing technique of shallow exploration, which consists in exploring over the final layer of the network only, allowing to decouple the deep neural network feature representation learning from most of the exploration of the network parameters. More specifically, they propose a simple and effective UCB-based strategy using this shallow exploration scheme, for which they provide a theoretical analysis. The proposed approach builds on several ideas for previous works, including borrowing proof techniques and theoretical arguments. Although this limits the novelty of the work, connecting these ideas together is not obvious and constitutes a significant contribution. Moreover, the proposed approach fixes an important known issue due to the matrix inversion in LinUCB, which could have a strong impact on the bandit community.
Decision: Accept (Poster)