EE-NET: EXPLOITATION-EXPLORATION NEURAL NETWORKS IN CONTEXTUAL BANDITS
Year: 2022

Abstract:
In this paper, we propose a novel neural exploration strategy in contextual bandits, EE-Net, distinct from the standard UCB-based and TS-based approaches. Contextual multi-armed bandits have been studied for decades with various applications. To solve the exploitation-exploration tradeoff in bandits, there are three main techniques: epsilon-greedy, Thompson Sampling (TS), and Upper Confidence Bound (UCB). In recent literature, linear contextual bandits have adopted ridge regression to estimate the reward function and combine it with TS or UCB strategies for exploration. However, this line of works explicitly assumes the reward is based on a linear function of arm vectors, which may not be true in real-world datasets. To overcome this challenge, a series of neural bandit algorithms have been proposed, where a neural network is used to learn the underlying reward function and TS or UCB are adapted for exploration. Instead of calculating a large-deviation based statistical bound for exploration like previous methods, we propose "EE-Net", a novel neural-based exploration strategy. In addition to using a neural network (Exploitation network) to learn the reward function, EE-Net uses another neural network (Exploration network) to adaptively learn potential gains compared to the currently estimated reward for exploration. Then, a decision-maker is constructed to combine the outputs from the Exploitation and Exploration networks. We prove that EE-Net can achieveO( √ T log T ) regret, which is tighter than existing state-ofthe-art neural bandit algorithms (O( √ T log T ) for both UCB-based and TS-based). Through extensive experiments on four real-world datasets, we show that EE-Net outperforms existing linear and neural contextual bandit approaches.

text: √ T log T ) regret, which is tighter than existing state-of-
the-art neural bandit algorithms (O( √ T log T ) for both UCB-based and TS-based). Through extensive experiments on four real-world datasets, we show that EE-Net outperforms existing linear and neural contextual bandit approaches.

heading: 1 INTRODUCTION
text: The stochastic contextual multi-armed bandit (MAB) (Lattimore and Szepesvári, 2020) has been studied for decades in machine learning community to solve sequential decision making, with applications in online advertising (Li et al., 2010), personal recommendation (Wu et al., 2016; Ban and He, 2021b), etc. In the standard contextual bandit setting, a set of n arms are presented to a learner in each round, where each arm is represented by a context vector. Then by certain strategy, the learner selects and plays one arm, receiving a reward. The goal of this problem is to maximize the cumulative rewards of T rounds.
MAB algorithms have principled approaches to address the trade-off between Exploitation and Exploration (EE), as the collected data from past rounds should be exploited to get good rewards but also under-explored arms need to be explored with the hope of getting even better rewards. The most widely-used approaches for EE trade-off can be classified into three main techniques: Epsilon-greedy (Langford and Zhang, 2008), Thompson Sampling (TS) (Thompson, 1933), and Upper Confidence Bound (UCB) (Auer, 2002; Ban and He, 2020).
Linear bandits (Li et al., 2010; Dani et al., 2008; Abbasi-Yadkori et al., 2011), where the reward is assumed to be a linear function with respect to arm vectors, have been well studied and succeeded both empirically and theoretically. Given an arm, ridge regression is usually adapted to estimate its reward based on collected data from past rounds. UCB-based algorithms (Li et al., 2010; Chu et al., 2011; Wu et al., 2016; Ban and He, 2021b) calculate an upper bound for the confidence ellipsoid of estimated reward and determine the arm according to the sum of estimated reward and UCB.
TS-based algorithms (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017) formulate each arm as a posterior distribution where mean is the estimated reward and choose the one with the maximal sampled reward. However, the linear assumption regarding the reward may not be true in real-world applications (Valko et al., 2013).
To learn non-linear reward functions, recent works have utilized deep neural networks to learn the underlying reward functions, thanks to its powerful representation ability. Considering the past selected arms and received rewards as training samples, a neural network f1 is built for exploitation. Zhou et al. (2020) computes a gradient-based upper confidence bound with respect to f1 and uses UCB strategy to select arms. Zhang et al. (2021) formulates each arm as a normal distribution where the mean is f1 and deviation is calculated based on gradient of f1, and then uses the TS strategy to choose arms. Both Zhou et al. (2020) and Zhang et al. (2021) achieve the near-optimal regret bound of O( √ T log T ).
In this paper, we propose a novel neural-based exploration strategy, named "EE-Net". Similar to other neural bandits, EE-Net has an exploitation network f1 to estimate rewards for each arm. The crucial difference from existing works is that EE-Net has an exploration network f2 to predict the potential gain for each arm compared to current reward estimate. The input to the exploration network is the gradient of f1 and the ground-truth is residual difference between the true received reward and the estimated reward from f1. The strategy is inspired by recent advances in the neural UCB strategies (Ban et al., 2021; Zhou et al., 2020). Finally, a decision-maker f3 is constructed to select arms. f3 has two modes: linear or nonlinear. In linear mode, f3 is a linear combination of f1 and f2, inspired by the UCB strategy. In the nonlinear mode, f3 is formulated as a neural network with input (f1, f2) and the goal is to learn the probability of being an optimal arm for each arm. Table 1 summarizes the selection criterion difference of EE-Net from other neural bandit algorithms. To sum up, the contributions of this paper can be summarized as follows:
1. We propose a novel neural exploration strategy, EE-Net, where a neural network is assigned to learn the potential gain compared to the current reward estimate.
2. Under standard assumptions of over-parameterized neural networks, we prove that EENet can achieve the regret upper bound of O( √ T log T ), which is tighter than existing
state-of-the-art conteextual bandit algorithms. 3. We conduct extensive experiments on four real-world datasets, showing that EE-Net out-
performs baselines including linear and neural versions of -greedy, TS, and UCB, and establishing EE-net as the new state-of-the-art exploration strategy.
Next, we discuss the problem definition in Sec.3, elaborate on the proposed EE-Net in Sec.4, and present our theoretical analysis in Sec.5. In the end, we provide the empirical evaluation (Sec.6) and conclusion.

heading: 2 RELATED WORK
text: Constrained Contextual bandits. The common constrain placed on the reward function is the linear assumption, usually calculated by ridge regression (Li et al., 2010; Abbasi-Yadkori et al., 2011; Valko
et al., 2013; Dani et al., 2008). The linear UCB-based bandit algorithms (Abbasi-Yadkori et al., 2011; Li et al., 2016) and the linear Thompson Sampling (Agrawal and Goyal, 2013; Abeille and Lazaric, 2017) can achieve successful performance and the near-optimal regret bound of Õ( √ T ). To break the linear assumption, Filippi et al. (2010) generalizes the reward function to a composition of linear and non-linear functions and then adopt a UCB-based algorithm to deal with it; Bubeck et al. (2011) imposes the Lipschitz property on reward metric space and constructs a hierarchical optimistic optimization to make selections; Valko et al. (2013) embeds the reward function into Reproducing Kernel Hilbert Space and proposes the kernelized TS/UCB bandit algorithms.
Neural Bandits. To learn non-linear reward functions, deep neural networks have been adapted to bandits with various variants. Riquelme et al. (2018); Lu and Van Roy (2017) build L-layer DNN to learn the arm embeddings and apply Thompson Sampling on the last layer for exploration. Zhou et al. (2020) first introduces a provable neural-based contextual bandit algorithm with a UCB exploration strategy and then Zhang et al. (2021) extends the neural network to Thompson sampling framework. Their regret analysis is built on recent advances on the convergence theory in over-parameterized neural networks(Du et al., 2019; Allen-Zhu et al., 2019) and utilizes Neural Tangent Kernel (Jacot et al., 2018; Arora et al., 2019) to construct connections with linear contextual bandits (AbbasiYadkori et al., 2011). Ban and He (2021a) further adopts convolutional neural networks with UCB exploration aiming for visual-aware applications. Xu et al. (2020) performs UCB-based exploration on the last layer of neural networks to reduce the computational cost brought by gradient-based UCB. Different from the above existing works, EE-Net keeps the powerful representation ability of neural networks to learn reward function and first assigns another neural network to determine exploration.

heading: 3 PROBLEM DEFINITION
text: We consider the standard contextual multi-armed bandit with the known number of rounds T (Zhou et al., 2020; Zhang et al., 2021). In each round t ∈ [T ], where the sequence [T ] = [1, 2, . . . , T ], the learner is presented with n arms, Xt = {xt,1, . . . ,xt,n}, in which each arm is represented by a feature vector xt,i ∈ Rd for each i ∈ [n]. After playing one arm xt,i, its reward rt,i is assumed to be generated by the function: rt,i = h(xt,i) + ηt,i, (3.1) where the unknown reward function h(xt,i) can be either linear or non-linear and the noise ηt,i is drawn from certain distribution with expectation E[ηt,i] = 0. Following many existing works (Zhou et al., 2020; Ban et al., 2021; Zhang et al., 2021), we consider bounded rewards, rt,i ∈ [a, b]. For the brevity, we denote the selected arm in round t by xt and the reward received in t by rt. The expected regret of T rounds is defined as:
RT = E [ T∑ t=1 (r∗t − rt) ] , (3.2)
where E[r∗t | Xt] = maxi∈[n] h(xt,i) is the maximal expected reward in the round t. The goal of this problem is to minimize RT by certain selection strategy.
Notation. We denote by {xi}ti=1 the sequence (x1, . . . ,xt). We use ‖v‖2 to denote the Euclidean norm for a vector v, and ‖W‖2 and ‖W‖F to denote the spectral and Frobenius norm for a matrix W. We use 〈·, ·〉 to denote the standard inner product between two vectors or two matrices. We may use Oθ1t f1(xt,i) or Oθ1t f1 to represent the gradient Oθ1t f1(xt,i;θ 1 t ) for brevity. We use {xτ , rτ}tτ=1 to represent the collected data up to round t.

heading: 4 PROPOSED METHOD: EE-NET
text: EE-Net is composed of three components. The first component is the exploitation network, f1(·;θ1), which focuses on learning the unknown reward function h based on the data collected in past rounds. The second component is the exploration network, f2(·;θ2), which focuses on characterizing the level of exploration needed for each arm in the present round. The third component is the decision-maker, f3, which focuses on suitably combining the outputs of the exploitation and exploration networks leading to the arm selection.
Published as a conference paper at ICLR 2022
1) Exploitation Net. The exploitation net f1 is a neural network which learns the mapping from arms to rewards. In round t, denote the network by f1(·;θ1t−1), where the superscript of θ 1 t−1 is the index of network and the subscript represents the round where the parameters of f1 finished the last update. Given an arm xt,i, i ∈ [n], f1(xt,i;θ1t−1) is considered the "exploitation score" for xt,i. By some criterion, after playing arm xt, we receive a reward rt. Therefore, we can conduct gradient descent to update θ1 based on the collected training samples {xτ , rτ}tτ=1 and denote the updated parameters by θ1t .
2) Exploration Net. Our exploration strategy is inspired by existing UCB-based neural bandits (Zhou et al., 2020; Ban et al., 2021). Based on the Lemma 5.2 in (Ban et al., 2021), given an arm xt,i, with probability at least 1− δ, we have the following UCB form:
|h(xt,i)− f1(xt,i;θ1t−1)| ≤ Ψ(Oθ1t−1f1(xt,i;θ 1 t−1)), (4.1)
where h is defined in Eq. (3.1) and Ψ is an upper confidence bound represented by a function with respect to the gradient Oθ1t−1f1 (see more details and discussions in Appendix D). Then we have the following definition.
Definition 4.1. In round t, given an arm xt,i, we define h(xt,i) − f1(xt,i;θ1t−1) as the "expected potential gain" for xt,i and rt,i − f1(xt,i;θ1t−1) as the "potential gain" for xt,i.
Let yt,i = rt,i − f1(xt,i;θ1t−1). When yt,i > 0, the arm xt,i has positive potential gain compared to the estimated reward f1(xt,i;θ1t−1). A large positive yt,i makes the arm more suitable for exploration, whereas a small (or negative) yt,i makes the arm unsuitable for exploration. Recall that traditional approaches such as UCB intend to estimate such potential gain yt,i using standard tools, e.g., Markov inequality, Hoeffding bounds, etc., from large deviation bounds.
Instead of calculating a large-deviation based statistical bound for yt,i, we use a neural network f2(·;θ2) to represent Ψ, where the input is Oθ1t−1f1(xt,i) and the ground truth is rt,i−f1(xt,i;θ 1 t−1). Adopting gradient Oθ1t−1f1(xt,i) as the input also is due to the fact that it incorporates two aspects of information: the feature of the arm and the discriminative information of f1.
Moreover, in the upper bound of NeuralUCB or the variance of NeuralTS, there is a recursive term At−1 = I + ∑t−1 τ=1∇θ1τ−1f1(xτ )∇θ1τ−1f1(xτ )
> which is a function of past gradients up to (t− 1) and incorporates relevant historical information. On the contrary, in EE-Net, the recursive term which depends on past gradients is θ2t−1 in the exploration network f2 because we have conducted gradient descent for θ2t−1 based on {∇θ1τ−1f1(xτ )} t−1 τ=1. Therefore, this form θ 2 t−1 is similar to At−1 in neuralUCB/TS, but EE-net does not (need to) make a specific assumption about the functional form of past gradients, and is also more memory-efficient.
To sum up, in round t, we consider f2(Oθ1t−1f1(xt,i);θ 2 t−1) as the "exploration score" of xt,i, because it indicates the potential gain of xt,i compared to our current exploitation score f1(xt,i;θ1t−1). Therefore, after receiving the reward rt, we can use gradient descent to update θ2 based on collected training samples {Oθ1τ−1f1(xτ ), rτ − f1(xτ ;θ 1 τ−1}tτ=1. We also provide other two heuristic forms for f2’s ground-truth label: |rt,i − f1(xt,i;θ1t−1)| and ReLU(rt,i − f1(xt,i;θ 1 t−1)). We compare them in an ablation study in Appendix B.
3) Decision-maker. In round t, given an arm xt,i, i ∈ [n], with the computed exploitation score f1(xt,i;θ
1 t−1) and exploration score f2(Oθ1t−1f1;θ 2 t−1), we use a function f3
( f1, f2;θ 3 )
to trade off between exploitation and exploration and compute the final score for xt,i. The selection criterion
Algorithm 1 EE-Net Input: f1, f2, f3, T (number of rounds), η1 (learning rate for f1), η2 (learning rate for f2), η3
(learning rate for f3), K1 (number of iterations for f1), K2 (number of iterations for f2) , K3 (number of iterations for f3), c (normalization parameter)
1: Initialize θ10,θ 2 0,θ 3 0; θ̂
1 0 = θ 1 0, θ̂ 2 0 = θ 2 0, θ̂ 3 0 = θ 3 0
2: for t = 1, 2, . . . , T do 3: Observe n arms {xt,1, . . . ,xt,n} 4: for each i ∈ [n] do 5: Compute f1(xt,i;θ1t−1), f2(Oθ1t−1f1(xt,i)/c √ mL;θ2t−1), f3((f1, f2);θ 3 t−1) 6: end for 7: xt = arg maxi∈[n] f3 ( f1(xt,i;θ
1 t−1), f2(Oθ1t−1f1;θ 2 t−1);θ 3 t−1 ) 8: Play xt and observe reward rt 9: θ1t ,θ 2 t ,θ 3 t = GRADIENTDESCENT(θ0, {xτ}tτ=1, {rτ}tτ=1)
10: end for 11: 12: procedure GRADIENTDESCENT(θ0, {xτ}tτ=1, {rτ}tτ=1) 13: L1 = 12 ∑t τ=1 ( f1(xτ ;θ 1)− rτ )2 14: θ1,(0) = θ10 15: for k ∈ {1, . . . ,K1} do 16: θ1,(k) = θ1,(k−1) − η1Oθ1,(k−1)L1 17: end for 18: θ̂ 1
t = θ 1,(K1) 19: L2 = 12 ∑t τ=1 ( f2(Oθ1τ−1f1(xτ )/c √ mL;θ2)− (rτ − f1(xτ ;θ1τ−1)) )2 20: θ2,(0) = θ20 21: for k ∈ {1, . . . ,K2} do 22: θ2,(k) = θ2,(k−1) − η2Oθ2,(k−1)L2 23: end for 24: θ̂ 2
t = θ 2,(K2)
25: Determine label pt 26: L3 = − 1t ∑t i=1 [ pt log f3((f1, f2);θ 3) + (1− pt) log(1− f3((f1, f2);θ3)) ] 27: θ3,(0) = θ30 28: for k ∈ {1, . . . ,K3} do 29: θ3,(k) = θ3,(k−1) − η3Oθ3,(k−1)L3 30: end for 31: θ̂ 3
t = θ 3,(K3)
32: Randomly choose (θ1t , θ 2 t ) uniformly from {(θ̂
1 0, θ̂ 2 0), (θ̂ 1 1, θ̂ 2 1), . . . , (θ̂ 1 t , θ̂ 2
t )} 33: Randomly choose θ3t uniformly from {θ̂ 3 0, θ̂ 3 1, . . . , θ̂ 3
t} 34: Return θ1t , θ 2 t , θ 3 t 35: end procedure
is defined as
xt = arg max i∈[n] f3
( f1(xt,i;θ 1 t−1), f2 ( Oθ1t−1f1(xt,i);θ 2 t−1 ) ;θ3t−1 ) .
Note that f3 can be either linear or non-linear functions. We provide the following two forms.
(1) Linear function. f3 can be formulated as a linear function with respect to f1 and f2 :
f3(f1, f2;θ 3) = w1f1(xt,i;θ 1) + w2f2(Oθ1f1;θ 2)
where w1, w2 are two weights preset by the learner. When w1 = w2 = 1, f3 can be thought of as UCB-type policy, where the estimated reward f1 and potential gain f2 are simply added together. In experiments, we report its empirical performance in ablation study (Appendix B).
(2) Non-linear function. f3 also can be formulated as a neural network to learn the mapping from (f1, f2) to the optimal arm. We transform the bandit problem into a binary classification problem. Given an arm xt,i, we define pt,i as the probability of being the optimal arm for xt,i in round t. For brevity, we denote by pt the probability of being the optimal arm for the selected arm xt in round t. According to different reward distributions, we have different approaches to determine pt.
1. Binary reward. ∀t ∈ [T ], suppose rt is a binary variable over a, b(a < b), it is straightforward to set: pt = 1.0 if rt = b; pt = 0.0, otherwise.
2. Continuous reward. ∀t ∈ [T ], suppose rt is a continuous variable over the range [a, b], we provide two ways to determine pt. (1) pt can be directly set as rt−ab−a . (2) The learner can set a threshold θ, (a < θ < b). Then pt = 1.0 if rt > θ; pt = 0.0, otherwise.
Therefore, with the collected training samples {( f1(xτ ;θ
1 τ−1), f2(Oθ1τ−1f1;θ 2 τ−1)
) , pτ }t τ=1 in
round t, we can conduct gradient descent to update parameters of f3(·;θ3). Table 2 details the working structure of EE-Net. Algorithm 1 depicts the workflow of EE-Net, where the input of f2 is normalized, i.e., Oθ1t−1f1(xt,i)/c √ mL. Algorithm 1 provides a version of gradient descent (GD) to update EE-Net, where drawing (θ1t ,θ 2 t ) uniformly from their stored historical parameters is for the sake of analysis. One can easily extend EE-Net to stochastic GD to update the parameters incrementally. Remark 4.1 (Network structure). The networks f1, f2, f3 can be different structures according to different applications. For example, in the vision tasks, f1 can be set up as convolutional layers (LeCun et al., 1995). For the exploration network f2, the input Oθ1f1 may have exploding dimensions when the exploitation network f1 becomes wide and deep, which may cause huge computation cost for f2. To address this challenge, we can apply dimensionality reduction techniques to obtain lowdimensional vectors of Oθ1f1. In the experiments, we use Roweis and Saul (2000) to acquire a 10-dimensional vector for Oθ1f1 and achieve the best performance among all baselines. Remark 4.2 (Exploration direction). EE-Net has the ability to determine exploration direction. Given an arm xt,i, when the estimation f1(xt,i) is lower than the expected reward h(xt,i), the learner should make the "upward" exploration, i.e., increase the chance of xt,i being explored; When f1(xt,i) is higher than h(xt,i), the learner should do the "downward" exploration, i.e., decrease the chance of xt,i being explored. EE-Net uses the neural network f2 to learn h(xt,i) − f1(xt,i) (which has positive and negative scores) and has the ability to determine the exploration direction. In contrast, NeuralUCB will always make "upward" exploration and NeuralTS will randomly choose between "upward" exploration and "downward" exploration (see selection criteria in Table 1 and more details in Appendix D). Remark 4.3 (Space complexity). NeuralUCB and NeuralTS have to maintain the gradient outer product matrix (e.g., At = ∑t τ=1 Oθ1f1(xτ ;θ 1 τ )Oθ1f1(xτ ;θ 1 τ ) > ∈ Rp×p) and, for θ1 ∈ Rp, have a space complexity of O(p2) to store the outer product. On the contrary, EE-Net does not have this matrix and only regards Oθ1f1 as the input of f2. Thus, EE-Net reduces the space complexity from O(p2) to O(p).

heading: 5 REGRET ANALYSIS
text: In this section, we provide the regret analysis of EE-Net when f3 is set as the linear function f3 = f1+f2, which can be thought of as the UCB-type trade-off between exploitation and exploration. For the sake of simplicity, we conduct the regret analysis on some unknown but fixed data distribution D. In each round t, n samples {(xt,1, rt,1), (xt,2, rt,2), . . . , (xt,n, rt,n)} are drawn from D. This is standard distribution assumption in over-parameterized neural networks (Cao and Gu, 2019). Then, we have the following assumption, which is a standard input assumption in neural bandits and over-parameterized neural networks(Zhou et al., 2020; Allen-Zhu et al., 2019). Assumption 5.1 (Arm Separability). For any t ∈ [T ], i ∈ [n], ‖xt,i‖2 = 1. Then, for every pair xt,i,xt′,i′ , t′ ∈ [T ], i′ ∈ [k], and (t, i) 6= (t′, i′), ‖xt,i − xt′,i′‖2 ≥ ρ.
The analysis will focus on over-parameterized neural networks (Jacot et al., 2018; Du et al., 2019; Allen-Zhu et al., 2019). Given an input x ∈ Rd, without loss of generality, we define the fully-
connected network f with depth L ≥ 2 and width m:
f(x;θ) = WLσ(WL−1σ(WL−2 . . . σ(W1x))) (5.1)
where σ is the ReLU activation function, W1 ∈ Rm×d, Wl ∈ Rm×m, for 2 ≤ l ≤ L − 1, WL ∈ R1×m, and θ = [vec(W1)ᵀ, vec(W2)ᵀ, . . . , vec(WL)ᵀ]ᵀ. Initialization. For any l ∈ [L], each entry of Wl is drawn from the normal distribution N (0, 2m ). Note that EE-Net at most has three networks f1, f2, f3. We define them following the definition of f for brevity, although they may have different depth or width. Then, we have the following theorem for EE-Net. Recall that η1, η2 are the learning rates for f1, f2; K1 is the number of iterations of gradient descent for f1 in each round; and K2 is the number of iterations for f2.
Theorem 1. Let f1, f2 follow the setting of f (Eq. (5.1) ) with the same width m and depth L. Let L1,L2 be loss functions defined in Algorithm 1. Set f3 as f3 = f1 + f2. Given δ ∈ (0, 1), ∈ (0,O( 1T )], ρ ∈ (0,O( 1 L )], suppose
m ≥ Ω̃ ( poly(T, n, L, ρ−1) · log(1/δ) · e √ log 1/δ) ) ,
η1 = η2 = min
( Θ ( T 5√ 2δ2m ) ,Θ ( ρ poly(T, n, L) ·m )) ,
K1 = K2 = Θ
( poly(T, n, L)
ρδ2 · log
( −1 ))
.
(5.2)
Then, with probability at least 1− δ, the expected cumulative regret of EE-Net in T rounds satisfies
RT ≤ (2 √ T − 1)(2 √ 2 + 3 √ 2L) + 2(1 + 2ξ)(2 √ T − 1) √ 2 log
O(Tn) δ , (5.3)
where ξ = O(1) +O ( T 3nL logm
ρ √ m
) +O ( T 4nL2 log11/6m
ρm1/6
) . As ≤ 1/T and because of the choice
of m, we have
RT ≤ O(1) + (2 √ T − 1)3 √ 2L+O ( (2 √ T − 1) √ 2 log
O(Tn) δ
) . (5.4)
Comparison with existing works. Under the similar assumptions in over-parameterized neural networks, the regret bounds complexity of NeuralUCB (Zhou et al., 2020) and NeuralTS (Zhang et al., 2021) both are
RT ≤ O (√ d̃T log T ) · O (√ d̃ log T ) , and d̃ =
log det(I + H/λ) log(1 + Tn/λ)
where H is the neural tangent kernel matrix (NTK) (Jacot et al., 2018; Arora et al., 2019) and λ is a regularization parameter. Similarly, in linear contextual bandits, Abbasi-Yadkori et al. (2011) achieve O(d √ T log T ) and Li et al. (2017) achieve O( √ dT log T ).
Remark 5.1. It is easy to observe that the regret bound of EE-Net is tighter than NeuralUCB/TS and linear bandits, which roughly improves by a multiplicative factor of √ log T , because our proof of EE-Net is directly built on recent advances in convergence theory (Allen-Zhu et al., 2019) and generalization bound (Cao and Gu, 2019) of over-parameterized neural networks. Instead, the analysis for NeuralUCB/TS contains three parts of approximation error by calculating the distances between the expected reward and ridge regression, ridge regression and NTK, and NTK and network function.
Remark 5.2. The regret bound of EE-Net does not have the effective dimension d̃ or input dimension d. d̃ or d may cause significant error, when the dimension of H is extremely large or d > T .
The proof of Theorem 1 is in Appendix C and mainly based on the following generalization bound. The bound results from an online-to-batch conversion while using convergence guarantees of deep learning optimization.
Lemma 5.1. Given δ, ∈ (0, 1), ρ ∈ (0,O( 1L )), suppose m, η1, η2,K1,K2 satisfy the conditions in Eq. (5.2). Then, with probability at least 1− δ, there exists a constant c1 > 0, such that it holds for Algorithm 1 that
E (x,r)∼D [∣∣∣∣∣f2 ( Oθ1t−1f1(x;θ 1 t−1) c1 √ mL ;θ2t−1 ) − ( r − f1(x;θ1t−1) )∣∣∣∣∣ |{xτ , rτ}t−1τ=1 ]
≤ √ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(O(1/δ))
t ,
(5.5)
where {xτ , rτ}t−1τ=1 are the data collected up to round t − 1 and the expectation is taken over (θ1t−1,θ 2 t−1) that is uniformly drawn from {(θ̂ 1 τ , θ̂ 2 τ )}t−1τ=0.
Remark 5.3. Lemma 5.1 provides a fixed Õ( 1√ t )-rate generalization bound for exploitationexploration networks f1, f2 in contrast with the relative bound w.r.t. the Neural Tangent Random Feature (NTRF) benchmark (Cao and Gu, 2019). We achieve this by working in the regression rather than classification setting and utilizing the convergence guarantees for square loss (Allen-Zhu et al., 2019). Note that the bound in Lemma 5.1 holds in the setting of bounded (possibly random) rewards r ∈ [0, 1] instead of a fixed function in the conventional classification setting.

heading: 6 EXPERIMENTS
text: In this section, we evaluate EE-Net on four real-world datasets comparing with strong state-of-the-art baselines. We first present the setup of experiments, then show regret comparison and report ablation study. Codes are available at 1.
We use four real-world datasets: Mnist, Yelp, Movielens, and Disin, the details and settings of which are attached in Appendix A.
Baselines. To comprehensively evaluate EE-Net, we choose 3 neural-based bandit algorithms, one linear and one kernelized bandit algorithms.
1. LinUCB (Li et al., 2010) explicitly assumes the reward is a linear function of arm vector and unknown user parameter and then applies the ridge regression and un upper confidence bound to determine selected arm.
2. KernelUCB (Valko et al., 2013) adopts a predefined kernel matrix on the reward space combined with a UCB-based exploration strategy.
3. Neural-Epsilon adapts the epsilon-greedy exploration strategy on exploitation network f1. I.e., with probability 1− , the arm is selected by xt = arg maxi∈[n] f1(xt,i;θ1) and with probability , the arm is chosen randomly.
4. NeuralUCB (Zhou et al., 2020) uses the exploitation network f1 to learn the reward function coming with an UCB-based exploration strategy.
1https://github.com/banyikun/EE-Net-ICLR-2022
5. NeuralTS (Zhang et al., 2021) adopts the exploitation network f1 to learn the reward function coming with an Thompson Sampling exploration strategy.
Note that we do not report results of LinTS and KernelTS in experiments, because of the limited space in figures, but LinTS and KernelTS have been significantly outperformed by NeuralTS (Zhang et al., 2021).
Setup for EE-Net. To compare fairly, for all the neural-based methods including EE-Net, the exploitation network f1 is built by a 2-layer fully-connected network with 100 width. For the exploration network f2, we use a 2-layer fully-connected network with 100 width as well. For the decision maker f3, by comprehensively evaluate both linear and nonlinear functions, we found that the most effective approach is combining them together, which we call " hybrid decision maker". In detail, for rounds t ≤ 500, f3 is set as f3 = f2 + f1, and for t > 500, f3 is set as a neural network with two 20-width fully-connected layers. Setting f3 in this way is because the linear decision maker can maintain stable performance in each running (robustness) and the non-linear decision maker can further improve the performance (see details in Appendix B). The hybrid decision maker can combine these two advantages together. The configurations of all methods are attached in Appendix A.
Results. Figure 1 and Figure 2 show the regret comparison on these four datasets. EE-Net consistently outperforms all baselines across all datasets. For LinUCB and KernelUCN, the simple linear reward function or predefined kernel cannot properly formulate ground-truth reward function existed in real-world datasets. In particular, on Mnist and Disin datasets, the correlations between rewards and arm feature vectors are not linear or some simple mappings. Thus, LinUCB and KernelUCB barely exploit the past collected data samples and fail to select correct arms. For neural-based bandit algorithms, the exploration probability of Neural-Epsilon is fixed and difficult to be adjustable. Thus it is usually hard to make effective exploration. To make exploration, NeuralUCB statistically calculates a gradient-based upper confidence bound and NeuralTS draws each arm’s predicted reward from a normal distribution where the standard deviation is computed by gradient. However, the confidence bound or standard deviation they calculated only consider the worst cases and thus may not be able represent the actual potential of each arm, and they cannot make "upward" and "downward" exploration properly. Instead, EE-Net uses a neural network f2 to learn each arm’s potential by neural network’s powerful representation ability. Therefore, EE-Net can outperform these two state-of-the-art bandit algorithms. Note that NeuralUCB/TS does need two parameters to tune UCB/TS according to different scenarios while EE-Net only needs to set up a neural network and automatically learns it.
Ablation Study. In Appendix B, we conduct ablation study regarding the label function y of f2 and the different setting of f3.

heading: 7 CONCLUSION
text: In this paper, we propose a novel exploration strategy, EE-Net. In addition to a neural network that exploits collected data in past rounds , EE-Net has another neural network to learn the potential gain compared to current estimation for exploration. Then, a decision maker is built to make selections to further trade off between exploitation and exploration. We demonstrate that EE-Net outperforms NeuralUCB and NeuralTS both theoretically and empirically, becoming the new state-of-the-art exploration policy.
Acknowledgements: This work is supported by National Science Foundation under Awards No. IIS1947203, IIS-2002540, IIS-2137468, IIS-1908104, OAC-1934634, and DBI-2021898, and a grant from C3.ai. The views and conclusions are those of the authors and should not be interpreted as representing the official policies of the funding agencies or the government.

heading: A DATASETS AND SETUP
text: MNIST dataset. MNIST is a well-known image dataset (LeCun et al., 1998) for the 10-class classification problem. Following the evaluation setting of existing works (Valko et al., 2013; Zhou et al., 2020; Zhang et al., 2021), we transform this classification problem into bandit problem. Consider an image x ∈ Rd, we aim to classify it from 10 classes. First, in each round, the image x is transformed into 10 arms and presented to the learner, represented by 10 vectors in sequence x1 = (x,0, . . . ,0),x2 = (0,x, . . . ,0), . . . ,x10 = (0,0, . . . ,x) ∈ R10d. The reward is defined as 1 if the index of selected arm matches the index of x’s ground-truth class; Otherwise, the reward is 0.
Yelp2 and Movielens (Harper and Konstan, 2015) datasets. Yelp is a dataset released in the Yelp dataset challenge, which consists of 4.7 million rating entries for 1.57 × 105 restaurants by 1.18 million users. MovieLens is a dataset consisting of 25 million ratings between 1.6 × 105 users and 6 × 104 movies. We build the rating matrix by choosing the top 2000 users and top 10000 restaurants(movies) and use singular-value decomposition (SVD) to extract a 10-dimension feature vector for each user and restaurant(movie). In these two datasets, the bandit algorithm is to choose the restaurants(movies) with bad ratings. We generate the reward by using the restaurant(movie)’s gained stars scored by the users. In each rating record, if the user scores a restaurant(movie) less than 2 stars (5 stars totally), its reward is 1; Otherwise, its reward is 0. In each round, we set 10 arms as follows: we randomly choose one with reward 1 and randomly pick the other 9 restaurants(movies) with 0 rewards; then, the representation of each arm is the concatenation of corresponding user feature vector and restaurant(movie) feature vector.
Disin (Ahmed et al., 2018) dataset. Disin is a fake news dataset on kaggle3 including 12600 fake news articles and 12600 truthful news articles, where each article is represented by the text. To transform the text into vectors, we use the approach (Fu and He, 2021) to represent each article by a 300-dimension vector. Similarly, we form a 10-arm pool in each round, where 9 real news and 1 fake news are randomly selected. If the fake news is selected, the reward is 1; Otherwise, the reward is 0.
Configurations. For LinUCB, following (Li et al., 2010), we do a grid search for the exploration constant α over (0.01, 0.1, 1) which is to tune the scale of UCB. For KernelUCB (Valko et al., 2013), we use the radial basis function kernel and stop adding contexts after 1000 rounds, following (Valko et al., 2013; Zhou et al., 2020). For the regularization parameter λ and exploration parameter ν in KernelUCB, we do the grid search for λ over (0.1, 1, 10) and for ν over (0.01, 0.1, 1). For NeuralUCB and NeuralTS, following setting of (Zhou et al., 2020; Zhang et al., 2021), we use the exploiation network f1 and conduct the grid search for the exploration parameter ν over (0.001, 0.01, 0.1, 1) and for the regularization parameter λ over (0.01, 0.1, 1). For NeuralEpsilon, we use the same neural network f1 and do the grid search for the exploration probability over (0.01, 0.1, 0.2). For the neural bandits NeuralUCB/TS, following their setting, as they have expensive computation cost to store and compute the whole gradient matrix, we use a diagonal matrix to make approximation. For all neural networks, we conduct the grid search for learning rate over (0.01, 0.001, 0.0005, 0.0001). For all grid-searched parameters, we choose the best of them for the comparison and report the averaged results of 10 runs for all methods.
Create exploration samples for f2. When the selected arm is not optimal in a round, the optimal arm must exist among the remaining arms, and thus the exploration consideration should be added to the remaining arms. Based on this fact, we create additional samples for the exploration network f2 in practice. For example, in setting of binary reward, e.g., 0 or 1 reward, if the received reward rt = 0 while select xt, we add new train samples for f2, (xt,i, cr) for each i ∈ [i]∩ xt,i 6= xt, where cr ∈ (0, 1) usually is a small constant. This measure can further improve the performance of EE-Net in our experiments.

heading: B ABLATION STUDY
text: In this section, we conduct ablation study regarding the label function y for exploration network f2 and seting of decision maker f3 on two representative datasets Movielens and Mnist.
2https://www.yelp.com/dataset 3https://www.kaggle.com/clmentbisaillon/fake-and-real-news-dataset
Label function y. In this paper, we use y1 = r − f1 to measure the potential gain of an arm, as the label of f2. Moreover, we provide other two intuitive form y2 = |r − f1| and y3 = ReLU(r − f1). Figure 3 shows the regret with different y, where "EE-Net" denotes our method with default y1, "EE-Net-abs" represents the one with y2 and "EE-Net-ReLU" is with y3. On Movielens and Mnist datasets, EE-Net slightly outperforms EE-Net-abs and EE-Net-ReLU. In fact, y1 can effectively represent the positive potential gain and negative potential gain, such that f2 intends to score the arm with positive gain higher and score the arm with negative gain lower. However, y2 treats the positive/negative potential gain evenly, weakening the discriminative ability. y3 can recognize the positive gain while neglecting the difference of negative gain. Therefore, y1 usually is the most effective one for empirical performance.
Setting of f3. f3 can be set as an either linear function or non-linear function. In the experiment, we test the simple linear function f3 = f1 + f2, denoted by "EE-Net-Lin", and a non-linear function represented by a 2-layer 20-width fully-connected neural network, denoted by "EE-Net-NoLin". For the default hybrid setting, denoted by "EE-Net", when rounds t ≤ 500, f3 = f1 + f2; Otherwise, f3 is the neural network. Figure 4 reports the regret with these three different modes. EE-Net achieves the best performance with small standard deviation. In contrast, EE-Net-NoLin obtains the worst performance and largest standard deviation. However, notice that EE-Net-NoLin can achieve the best performance in certain running (the green shallow) but it is erratic. Because in the begin phase, without enough training samples, EE-Net-NoLin strongly relies on the quality of collected samples. With appropriate training samples, gradient descent can lead f3 to global optimum. On the other hand, with misleading training samples, gradient descent can deviate f3 from global optimum. Therefore, EE-Net-NoLin shows very unstable performance. In contrast, EE-Net-Lin is inspired by the UCB strategy, i.e., the exploitation plus the exploration, exhibiting stable performance. To combine their
advantages together, we propose the hybrid approach, EE-Net, achieving the best performance with strong stability.

heading: C PROOF OF THEOREM 1
text: In this section, we provide the proof of Theorem 1 and related lemmas.
Proof. For brevity, for the selected arm xt in round t, let h(xt) be its expected reward and x∗t = arg maxi∈[n] h(xt,i) be the optimal arm in round t.
Note that (xt,i, rt,i) ∼ D, for each i ∈ [n]. Then, the expected regret of round t is computed by
Rt = E (xt,i,rt,i),i∈[n]
[r∗t − rt|{xτ , rτ}t−1τ=1]
= Ext,i,i∈[n][h(x ∗ t )− h(xt)|{xτ , rτ}t−1τ=1] = Ext,i,i∈[n][h(x ∗ t )− f3(xt) + f3(xt)− h(xt)|{xτ , rτ}t−1τ=1] ≤ Ext,i,i∈[n][h(x ∗ t )− f3(x∗t ) + f3(xt)− f3(xt)︸ ︷︷ ︸
I1
+f3(xt)− h(xt)|{xτ , rτ}t−1τ=1]
= Ext,i,i∈[n][h(x ∗ t )− f3(x∗t ) + f3(xt)− h(xt)|{xτ , rτ}t−1τ=1] = Ext,i,i∈[n][h(x ∗ t )− f3(x∗t )|{xτ , rτ}t−1τ=1] + Ext,i,i∈[n][f3(xt)− h(xt)|{xτ , rτ} t−1 τ=1]
≤ 2Ext,i,i∈[n] [ max i∈[n] ([ |h(xt,i)− f3(xt,i)| |{xτ , rτ}t−1τ=1 ])] = 2Ext,i,i∈[n] [ max i∈[n]
([∣∣Ert,i [rt,i|xt,i]− f3(xt,i)∣∣ |{xτ , rτ}t−1τ=1])] (a)
≤ 2Ext,i,i∈[n] [ max i∈[n] ( Ert,i [ |rt,i − f3(xt,i)| |{xτ , rτ}t−1τ=1,xt,i ])] = 2Ext,i,i∈[n] [ max i∈[n] ( Ert,i
[∣∣∣f1(xt,i;θ1t−1) + f2(Oθ1t−1f1/c√mL;θ2t−1)− rt,i∣∣∣∣∣∣{xτ , rτ}t−1τ=1,xt,i])] = 2Ext,i,i∈[n][
max i∈[n]
( Ert,i [∣∣∣f2(Oθ1t−1f1(xt,i) c1 √ mL ;θ2t−1 ) − ( rt,i − f1(xt,i;θ1t−1) ) ∣∣∣∣∣∣{xτ , rτ}t−1τ=1,xt,i ])] .
(C.1) where I1 is because f3(xt) = maxi∈[n] f3(xt,i) and f3(xt) − f3(x∗t ) ≥ 0, and (a) follows by Jensen’s inequality.
Because, for each i ∈ [n], (xt,i, rt,i) ∼ D, applying Corollary C.1, with probability at least (1− δ), we have
Rt ≤ 2
(√ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(O(tn)/δ)
t
) . (C.2)
Then expected regret of T rounds is computed by
RT = T∑ t=1 Rt
≤ 2 T∑ t=1
(√ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(O(tn)/δ)
t ) ≤ (2 √ T − 1)2 √ 2 + (2 √ T − 1)3 √ 2L+ 2(1 + 2ξ)(2 √ T − 1) √ 2 log(O(Tn)/δ)︸ ︷︷ ︸
I2
= (2 √ T − 1)(2 √ 2 + 3 √ 2L) + 2(1 + 2ξ)(2 √ T − 1) √ 2 log(O(Tn)/δ)
(C.3)
where I2 is because ∑T t=1 1√ t ≤ ∫ T 1 1√ t dx+ 1 = 2 √ T − 1 (Chlebus, 2009).
According to Lemma C.3 (1), with probability at least 1− δ, when ≤ 1/T , we have
RT ≤ O(1) + (2 √ T − 1)3 √ 2L+ 2(1 + 2ξ)(2 √ T − 1) √ 2 log(O(Tn)/δ), (C.4)
As the choice of m, we have ξ ≤ O(1). Therefore, we have
RT ≤ O(1) + (2 √ T − 1)3 √ 2L+O ( (2 √ T − 1) √ 2 log(O(Tn)/δ) ) . (C.5)
The proof is completed.
Lemma C.1. [Lemma 5.1 restated] Given δ, ∈ (0, 1), ρ ∈ (0,O( 1L )), suppose m, η1, η2,K1,K2 satisfy the conditions in Eq. (5.2). Then, with probability at least 1 − δ, such that it holds for Algorithm 1 that
E (x,r)∼D [∣∣∣∣∣f2 ( Oθ1t−1f1(x;θ 1 t−1) c1 √ mL ;θ2t−1 ) − ( r − f1(x;θ1t−1) )∣∣∣∣∣ |{xτ , rτ}t−1τ=1 ]
≤ √ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(O(1/δ))
t ,
(C.6)
where {xτ , rτ}t−1τ=1 are the data collected up to round t − 1 and the expectation is taken over (θ1t−1,θ 2 t−1) that is uniformly drawn from {(θ̂ 1 τ , θ̂ 2 τ )}t−1τ=0.
Proof. In this proof, we consider the collected data of up to round t− 1, {xτ , rτ}t−1τ=1, as the training dataset and then obtain a generalization bound for it, inspired by Cao and Gu (2019).
First, we focus on upper bounding the conditional expectation Ert,i [· · · |xt,i] in (C.17) with high probability. For convenience, we use x := xt,i, r := rt,i, noting that the same analysis holds for each i ∈ [n]. Using the Lemma C.4 (2) and Lemma C.3 (2), for any τ ∈ [t− 1], with probability at least 1− δ, given any x ∼ D and ‖x‖2 ≤ 1, we have
‖O θ̂ 1 τ f(x; θ̂
1 τ )‖2 ≤ O( √ mL).
Now, consider the exploration network f2. Given any x ∼ D and ‖x‖2 ≤ 1, there must exist a constant c1, such that ∥∥∥∥∥∥ O θ̂ 1 τ f1(x; θ̂ 1 τ ) c1 √ mL ∥∥∥∥∥∥ 2 ≤ 1. (C.7) Then, applying Lemma C.2, with probability at least 1− δ, for any t ∈ [T ], we have
∣∣∣∣∣∣f2 Oθ̂1τ f1(x; θ̂1τ ) c1 √ mL ; θ̂ 2 τ ∣∣∣∣∣∣ ≤ ξ. (C.8) Similarly, applying Lemma C.2 again, with probability at least 1− δ, for any t ∈ [T ], we have
|f1(x; θ̂ 1 τ )| ≤ ξ (C.9)
Because for any r ∼ D, |r| ≤ 1, with Eq. (C.8) and (C.9), applying union bound, with probability at least 1− 2δ, we have∣∣∣∣∣∣f2 Oθ̂1τ f1(x; θ̂1τ ) c1 √ mL ; θ̂ 2 τ − (r − f1(x; θ̂1τ )) ∣∣∣∣∣∣ ≤ 1 + 2ξ. (C.10)
For brevity, let f2(x; θ̂ 2 τ ) represent f2
( O
θ̂1τ f1(x;θ̂
1 τ )
c1 √ mL
; θ̂ 2
τ
) .
Recall that, for each τ ∈ [t− 1], θ̂ 1 τ and θ̂ 2
τ are the parameters training on {xτ ′ , rτ ′}ττ ′=1 according to Algorithm 1. Then, we define
Vτ = E(x,r)∼D [∣∣∣f2(x; θ̂2τ−1)− (r − f1(x; θ̂1τ−1))∣∣∣]− ∣∣∣f2(xτ ; θ̂2τ−1)− (rτ − f1(xτ ; θ̂1τ−1))∣∣∣ .
Then, since (xτ , rτ ) ∼ D, we have E(xτ ,rτ )∼D[Vτ |Fτ ] = E(x,r)∼D [∣∣∣f2 (x; θ̂2τ−1)− (r − f1(x; θ̂1τ−1))∣∣∣Fτ]
− E(xτ ,rτ )∼D [∣∣∣f2 (xτ ; θ̂2τ−1)− (rτ − f1(xτ ; θ̂1τ−1))∣∣∣ |Fτ]
= 0 ,
(C.11)
where Fτ denotes the σ-algebra generated by {xτ ′ , rτ ′}τ−1τ ′=1. Moreover, we have
1
t t∑ τ=1 Vτ = 1 t t∑ τ=1 E(x,r)∼D [∣∣∣f2 (x; θ̂2τ−1)− (r − f1(x; θ̂1τ−1))∣∣∣]
− 1 t t∑ τ=1 ∣∣∣f2 (xτ ; θ̂2τ−1)− (rτ − f1(xτ ; θ̂1τ−1))∣∣∣ . Since Vτ is a martingale difference sequence, following Lemma 1 in (Cesa-Bianchi et al., 2004), applying the Hoeffding-Azuma inequality, with probability at least 1− 2δ, we have
P 1t t∑
τ=1
Vτ − 1
t t∑ τ=1
E(x,r)∼D[Vτ |Fτ ]︸ ︷︷ ︸ I1 > (1 + 2ξ)︸ ︷︷ ︸ I2
√ 2 log(1/δ)
t
 ≤ δ
⇒ P
[ 1
t t∑ τ=1 Vτ > (1 + 2ξ)
√ 2 log(1/δ)
t
] ≤ δ ,
(C.12)
where I1 = 0 according to Eq.(C.11) and I2 is because of Eq.(C.10).
According to Algorithm 1, (θ1t−1,θ 2 t−1) is uniformly drawn from {(θ̂
1 τ , θ̂ 2 τ )}t−1τ=0. Thus, with probability 1− 3δ, we have
E (x,r)∼D E (θ1t−1,θ 2 t−1) [∣∣f2 (x;θ2t−1)− (r − f1(x;θ1t−1))∣∣] = 1
t t∑ τ=1 E(x,r)∼D [∣∣∣f2 (x; θ̂2τ−1)− (r − f1(x; θ̂1τ−1))∣∣∣]
≤ 1 t t∑ τ=1 ∣∣∣f2 (xτ ; θ̂2τ−1)− (rτ − f1(xτ ; θ̂1τ−1))∣∣∣︸ ︷︷ ︸ I3 +(1 + 2ξ) √ 2 log(1/δ) t .
(C.13)
For I3, according to Lemma C.5, for any θ̃ 2 satisfying ‖θ̃ 2 − θ20‖2 ≤ O( t 3 ρ √ m logm) , we have
1
t t∑ τ=1 ∣∣∣f2(xτ ; θ̂2τ−1)− (rτ − f1(xτ ; θ̂1τ−1))∣∣∣ ≤ 1 t t∑ τ=1
∣∣∣f2(xτ ; θ̃2)− (rτ − f1(xτ ; θ̂1τ−1))∣∣∣︸ ︷︷ ︸ I4 + 3L√ 2t .
(C.14)
For I4, according to Lemma C.3 (1), these exists θ̃ 2 satisfying ‖θ̃ 2 − θ20‖2 ≤ O( t 3 ρ √ m
logm), such that
1
t t∑ τ=1 ∣∣∣f2(xτ ; θ̃2)− (rτ − f1(xτ ; θ̂1τ−1))∣∣∣ ≤ 1 t √ t √√√√√√√ t∑ τ=1 ( f2(xτ ; θ̃ 2 )− ( rτ − f1(xτ ; θ̂ 1 τ−1) ))2
︸ ︷︷ ︸ I5
≤ 1√ t √ 2 ︸︷︷︸ I5 ,
(C.15)
where I5 follows by a direct application of Lemma C.3 (1) by defining the loss L(θ̃ 2 ) =
1 2 ∑t τ=1 ( f2(xτ ; θ̃ 2 )− ( rτ − f1(xτ ; θ̂ 1 τ−1) ))2 ≤ .
Combining Eq.(C.13), Eq.(C.14) and Eq.(C.15), with probability (1− 3δ) we have E(x,r)∼D [∣∣f2 (x;θ2t−1)− (r − f1(x;θ1t−1))∣∣ |{xτ , rτ}t−1τ=1]
≤ √ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(1/δ)
t .
(C.16)
where the expectation over (θ1t−1,θ 2 t−1) that is uniformly drawn from {(θ̂
1 τ , θ̂ 2 τ )}t−1τ=0. Then, applying union bound and rescaling the δ complete the proof.
Corollary C.1. Given δ, ∈ (0, 1), ρ ∈ (0,O( 1L )), suppose m, η1, η2,K1,K2 satisfy the conditions in Eq. (5.2). Then, with probability at least 1 − δ, for any round τ ∈ [t], i ∈ [n], there exists a constant c1 > 0, such that it holds uniformly for Algorithm 1 that
E xt,i,i∈[n] [ max i∈[n] ( E rt,i [∣∣∣f2(Oθ1t−1f1(xt,i;θ1t−1) c1 √ mL ;θ2t−1 ) − ( rt,i − f1(xt,i;θ1t−1) ) ∣∣∣ | {xτ , rτ}t−1τ=1,xt,i] )]
≤ √ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(O(tn)/δ)
t ,
(C.17) where {xτ , rτ}t−1τ=1 are the data collected up to round t − 1 and the expectation is taken over (θ1t−1,θ 2 t−1) that is uniformly drawn from {(θ̂ 1 τ , θ̂ 2 τ )}t−1τ=0.
Proof. This a direct corollary of Lemma C.1. According to Eq. (C.16), with probability 1− 3δ, given (x, r) ∼ D, we have
E x E r E (θ1t−1,θ 2 t−1) [∣∣f2 (x;θ2t−1)− (r − f1(x;θ1t−1))∣∣ | {xτ , rτ}t−1τ=1] ≤ √ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(1/δ)
t .
(C.18)
Then, in round t, applying the union bound, for (xt,i, rt,i) ∼ D,∀i ∈ [n], with probability 1− 3nδ, we have
∀i ∈ [n], E xt,i E rr,i E (θ1t−1,θ 2 t−1) [∣∣f2 (xt,i;θ2t−1)− (rt,i − f1(xt,i;θ1t−1))∣∣ | {xτ , rτ}t−1τ=1] ≤ √ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(1/δ)
t ,
(C.19)
which is equal to
E xt,i,i∈[n] [ max i∈[n] ( E rt,i E (θ1t−1,θ 2 t−1) [∣∣f2 (xt,i;θ2t−1)− (rt,i − f1(xt,i;θ1t−1))∣∣ | {xτ , rτ}t−1τ=1,xt,i])] ≤ √ 2
t + 3L√ 2t + (1 + 2ξ)
√ 2 log(1/δ)
t .
(C.20) Then, apply union bound for any round τ ∈ [t], to help the proof for Theorem 1. Rescaling the δ and replacing f2 with the formal form complete the proof.
Lemma C.2. Let f(·; θ̂t) follow the stochastic gradient descent of f1 or f2 in Algorithm 1. Suppose m, η1, η2 satisfy the conditions in Eq. (5.2). With probability at least 1− δ, for any x with ‖x‖2 = 1 and t ∈ [T ], it holds that
|f(x; θ̂t)| ≤ O(1) +O ( t3nL logm
ρ √ m
) +O ( t4nL2 log11/6m
ρm1/6
) .
Proof. Considering an inequality |a− b| ≤ c, we have |a| ≤ |b|+ c. Let θ0 be randomly initialized. Then applying Lemma C.4 (1), for any x ∼ D, ‖x‖2 = 1 and ‖θ̂t − θ0‖ ≤ w, we have
|f(x; θ̂t)| ≤ |f(x;θ0)|+ |〈Oθ0f(xi;θ0), θ̂t − θ0〉|+O(L2 √ m log(m))‖θ̂t − θ0‖2w1/3
≤ O(1)︸ ︷︷ ︸ I0 + ‖Oθ0f(xi;θ0)‖2‖θ̂t − θ0‖2︸ ︷︷ ︸ I1
+O(L2 √ m log(m))‖θ̂t − θ0‖2w1/3
≤ O(1) +O(L) · O ( t3
ρ √ m logm ) ︸ ︷︷ ︸
I2
+O ( L2 √ m log(m) ) · O ( t3
ρ √ m logm )4/3 ︸ ︷︷ ︸
I3 = O(1) +O ( t3L logm
ρ √ m
) +O ( t4L2 log11/6m
ρm1/6
) (C.21)
where: I0 is based on the Lemma C.3 (3); I1 is an application of Cauchy–Schwarz inequality; I2 is according to Lemma C.3 (2) and (3) in which θ̂t can be considered as one step gradient descent; I3 is due to Lemma C.3 (2).
Then, the proof is completed. Lemma C.3. Given a constant 0 < < 1, suppose m ≥ Ω̃ ( poly(T, n, L, ρ−1) · e √ log 1/δ ) , the
learning rate η = Ω( ρpoly(t,n,L)m ), the number of iterations K = Ω( poly(t,n,L) ρ2 · log −1). Then, with probability at least 1− δ, starting from random initialization θ0,
(1) (Theorem 1 in (Allen-Zhu et al., 2019)) In round t ∈ [T ], given the collected data {xτ , rτ}ti=τ , the loss function is defined as: L(θ) = 12 ∑t τ=1 (f(xτ ;θ)− rτ ) 2. Then,
there exists θ̃ satisfying ‖θ̃ − θ0‖2 ≤ O ( t3
ρ √ m
logm ) , such that L(θ̃) ≤ in
K = Ω( poly(t,n,L)ρ2 · log −1) iterations;
(2) (Theorem 1 in (Allen-Zhu et al., 2019)) For any k ∈ [K], it holds uniformly that ‖θ(k)t − θ0‖2 ≤ O
( t3
ρ √ m
logm ) ;
(3) Following the initialization, it holds that
‖Oθ0f(xi;θ0)‖2 ≤ O(L), |f(xi;θ0)| ≤ O(1)
where θ(k)t represents the parameters of f after k ∈ [K] iterations if gradient descent in round t.
Proof. Note that the output dimension d in (Allen-Zhu et al., 2019) is removed because the output of network function in this paper always is a scalar. For (1) and (2), the only different setting from (Allen-Zhu et al., 2019) is that the initialization of last layer WL ∼ N (0, 2m ) in this paper while WL ∼ N (0, 1d ) in (Allen-Zhu et al., 2019). Because d = 1 and m > d here, the upper bound in (Allen-Zhu et al., 2019) still holds for WL: with probability at least 1−exp (−Ω(m/L)), ‖WL‖F ≤√ m/d. Therefore, it is easy to verify that (1) and (2) still hold for the initialization of this paper.
For (3), based on Lemma 7.1 in Allen-Zhu et al. (2019), we have |f(xi;θ0)| ≤ O(1). Denote by D the ReLU function. For any l ∈ [L],
‖OWlf(xi;θ0)‖F ≤ ‖WLDWL−1 · · ·DWl+1‖F · ‖DWl+1 · · ·x‖F ≤ O( √ L)
where the inequality is according to Lemma 7.2 in Allen-Zhu et al. (2019). Therefore, we have ‖Oθ0f(xi;θ0)‖2 ≤ O(L).
Lemma C.4 (Lemma 4.1, (Cao and Gu, 2019)). Suppose O(m−3/2L−3/2[log(TnL2/δ)]3/2) ≤ w ≤ O(L−6[logm]−3/2). Then, with probability at least 1 − δ over randomness of θ0, for any t ∈ [T ], ‖x‖2 = 1, and θ,θ′ satisfying ‖θ− θ0‖2 ≤ w and ‖θ′− θ0‖2 ≤ w , it holds uniformly that
(1) |f(xi;θ)− f(xi;θ′)− 〈Oθ′f(xi;θ′),θ − θ′〉| ≤ O(w1/3L2 √ m log(m))‖θ − θ′‖2 (2) ‖Oθf(x;θ)‖2 ≤ O( √ mL).
Lemma C.5. For any δ > 0, suppose m > Õ ( poly(T, n, ρ−1, L, log(1/δ) · e √ log 1/δ) ) , ν = Θ̃(t6/δ2).
Then, with probability at least 1− δ, setting η2 = Θ( ν√2tm ) for algorithm 1, for any θ̃ 2 satisfying ‖θ̃ 2 − θ20‖2 ≤ O( t 3 ρ √ m logm) such that
t∑ τ=1 ∣∣∣∣∣∣∣f2 Oθ̂1τ−1f1(xτ ; θ̂ 1 τ−1) c1 √ mL ; θ̂ 2 τ−1 − (rτ − f1(xτ ; θ̂1τ−1)) ∣∣∣∣∣∣∣
≤ t∑
τ=1 ∣∣∣∣∣∣∣f2 Oθ̂1τ−1f1(xτ ; θ̂ 1 τ−1) c1 √ mL ; θ̂ 2 t − (rτ − f1(xτ ; θ̂1τ−1)) ∣∣∣∣∣∣∣+ 3L √ t√ 2
Proof. This is a direct application of Lemma 4.3 in (Cao and Gu, 2019) by setting R = t 3
ρ logm, =
LR√ 2νt
, and ν = R2. We set Lτ (θ̂ 2 τ−1) = ∣∣∣f2(Oθ̂1τ−1f1; θ̂2τ−1)− (rτ − f1(xτ ; θ̂1τ−1))∣∣∣. Based on
Lemma C.3 (2), for any τ ∈ [t], we have
‖θ̂ 2 τ − θ̂ 2 τ−1‖2 ≤ ‖θ̂ 2 τ − θ0‖2 + ‖θ0 − θ̂ 2 τ−1‖2 ≤ O( t3
ρ √ m logm).
Then, according to Lemma 4.3 in (Cao and Gu, 2019), then, for any θ̃ 2 satisfying ‖θ̃ 2 − θ20‖2 ≤ O( t 3
ρ √ m logm), we have t∑
τ=1
Lτ (θ̂ 2 τ−1) ≤ t∑
τ=1
Lτ (θ̃ 2 ) + 3t . (C.22)
Then, replacing completes the proof.
Case 1: Upward Exploration Case 2: Downward Exploration
Figure 5: Two types of exploration: Upward exploration and Downward exploration. f1 is the exploitation network (estimated reward) and h is the expected reward.

heading: D MOTIVATION OF EXPLORATION NETWORK
text: In this section, we list one gradient-based UCB from existing works (Ban et al., 2021; Zhou et al., 2020), which motivates our design of exploration network f2. Let g(xt;θt) = Oθtf(xt;θt).
Lemma D.1. (Lemma 5.2 in (Ban et al., 2021)). Given a set of context vectors {xt}Tt=1 and the corresponding rewards {rt}Tt=1 , E(rt) = h(xt) for any xt ∈ {xt}Tt=1. Let f(xt;θ) be the L-layers fully-connected neural network where the width is m, the learning rate is η, the number of iterations of gradient descent is K. Then, there exist positive constants C1, C2, S, such that if
m ≥ poly(T, n, L, log(1/δ) · d · e √ log 1/δ), η = O(TmL+mλ)−1, K ≥ Õ(TL/λ),
then, with probability at least 1− δ, for any xt ∈ {xt}Tt=1, we have the following upper confidence bound:
|h(xt)− f(xt;θt)| ≤γ1‖g(xt;θt)/ √ m‖A−1t + γ2 + γ1γ3 + γ4, (D.1)
where γ1(m,L) = (λ+ tO(L)) · ((1− ηmλ)J/2 √ t/λ) + 1
γ2(m,L, δ) = ‖g(xt;θ0)/ √ m‖
A ′−1 t ·
(√ log ( det(A′t) det(λI) ) − 2 log δ + λ1/2S ) γ3(m,L) = C2m −1/6 √ logmt1/6λ−7/6L7/2, γ4(m,L) = C1m −1/6 √ logmt2/3λ−2/3L3
At = λI + t∑ i=1 g(xt;θt)g(xt;θt) ᵀ/m, A′t = λI + t∑ i=1 g(xt;θ0)g(xt;θ0) ᵀ/m.
Note that g(xt;θ0) is the gradient at initialization, which can be initialized as constants. Therefore, the above UCB can be represented as the following form for exploitation network f1: |h(xt,i) − f1(xt,i;θ 1 t )| ≤ Ψ(g(xt;θt)).
EE-Net has smaller approximation error. Given an arm x, let f1(x) be the estimated reward and h(x) be the expected reward. The exploration network f2 in EE-Net is to learn h(x)− f1(x), i.e., the residual between expected reward and estimated reward, which is the ultimate goal of making exploration. There are advantages of using a network f2 to learn h(x)− f1(x) in EE-Net, compared to giving a statistical upper bound for it such as NeuralUCB, (Ban et al., 2021), and NeuralTS (in NeuralTS, the variance ν can be thought of as the upper bound). For EE-Net, the approximation error for h(x) − f1(x) is caused by the genenalization error of the neural network (Lemma B.1. in the
manuscript). In contrast, for NeuralUCB, (Ban et al., 2021), and NeuralTS, the approximation error for h(x)− f1(x) includes three parts. The first part is caused by ridge regression. The second part of the approximation error is caused by the distance between ridge regression and Neural Tangent Kernel (NTK). The third part of the approximation error is caused by the distance between NTK and the network function. Because they use the upper bound to make selections, the errors inherently exist in their algorithms. By reducing the three parts of the approximation errors to only the neural network convergence error, EE-Net achieves tighter regret bound compared to them (improving by roughly √ log T ).
EE-Net has the ability to determine exploration direction. The two types of exploration are described by Figure 5. When the estimated reward is larger than the expected reward, i.e., h(x)− f1(x) < 0, we need to do the ‘downward exploration’, i.e., lowering the exploration score of x to reduce its chance of being explored; when h(x)− f1(x) > 0, we should do the ‘upward exploration’, i.e., raising the exploration score of x to increase its chance of being explored. For EE-Net, f2 is to learn h(x) − f1(x). When h(x) − f1(x) > 0, f2(x) will also be positive to make the upward exploration. When h(x)− f1(x) < 0, f2(x) will be negative to make the downward exploration. In contrast, NeuralUCB will always choose upward exploration, i.e., f1(x) + UCB(x) where UCB(x) is always positive. In particular, when h(x)−f1(x) < 0, NeuralUCB will further amplify the mistake. NeuralTS will randomly choose upward or downward exploration for all cases, because it draws a sampled reward from a normal distribution where the mean is f1(x) and the variance ν is the upper bound.

Review summaries:
This paper studies the neural contextual bandit problem, and proposes a neural-based bandit approach with a novel exploration strategy, called EE-Net. Besides utilizing a neural network (Exploitation network) to learn the reward function, EE-Net also uses another neural network (Exploration network) to adaptively learn potential gains compared to currently estimated reward. Then, a decision-maker is constructed to combine the outputs from the Exploitation and Exploration networks. Theoretical guarantees and extensive experiments are provided to demonstrate the performance superiority of EE-Net over existing linear and neural bandit algorithms. 

This paper proposes EE-NeT for contextual bandits which contains two neutral networks: one for learning the underlying reward function and another for learning the potential gains of arms if explored. They prove that  EE-NeT achieves better regret bounds than state-of-the-art neural bandits algorithms for both UCB-based and TS-based. This paper also shows that EE-NeT outperforms existing linear and neural bandit approaches.

This paper studies neural network-based contextual bandits. Different from existing works which utilize UCB or Thompson sampling for exploration, the exploration component of the proposed method EE-Net is also modeled with a neural network.  Based on theoretical tools on over-parameterized neural networks, it is proved that EE-Net achieves the regret bound of $\mathcal{O}(\sqrt{T\log T})$. In contrast, existing neural network-based contextual bandit methods, such as NeuralUCB and NeuralTS, achieves the regret bound of $\mathcal{O}(\sqrt{T} \log T)$ based on the theoretical tool of the neural tangent kernel.  Experiments are conducted on four public datasets to validate effectiveness of EE-Net, compared with a variety of contextual bandit methods including both neural-based methods and linear contextual bandit methods.

This paper presents a neural net based bandit approach with a novel exploration strategy. Specifically, the solution uses an exploitation network to estimate rewards for each arm and an exploration network to predict the potential gain compared to current reward estimate. It then uses a decision maker to select arms using one of the linear or nonlinear modes. The key differentiator/strength of the paper is using neural net based exploration strategy and demonstrating that the proposed solution has a tighter bound than the existing state-of-the-art bandit algorithms.