EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits

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 $f_{1}$ is built for exploitation. Zhou et al. (2020) computes a gradient-based upper confidence bound with respect to $f_{1}$ and uses UCB strategy to select arms. Zhang et al. (2021) formulates each arm as a normal distribution where the mean is $f_{1}$ and deviation is calculated based on gradient of $f_{1}$, 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(\sqrt{T}\log T)$.

In this paper, we propose a novel neural exploration strategy, named "EE-Net". Similar to other neural bandits, EE-Net has another exploitation network $f_{1}$ to estimate rewards for each arm. The crucial difference from existing works is that EE-Net has an exploration network $f_{2}$ to predict the potential gain for each arm compared to current reward estimate. The input to the exploration network is the gradient of $f_{1}$ and the ground-truth is residual difference between the true received reward and the estimated reward from $f_{1}$. The strategy is inspired by recent advances in the neural UCB strategies (Zhou et al., 2020; Ban et al., 2021). Finally, a decision-maker $f_{3}$ is constructed to select arms. $f_{3}$ has two modes: linear or nonlinear. In linear mode, $f_{3}$ is a linear combination of $f_{1}$ and $f_{2}$, inspired by the UCB strategy. In the nonlinear mode, $f_{3}$ is formulated as a neural network with input ($f_{1},f_{2}$) and the goal is to learn the probability of being an optimal arm for each arm. Figure 1 depicts the workflow of EE-Net and its advantages for exploration compared to UCB or TS-based methods (see more details in Appendix D). To sum up, the contributions of this paper can be summarized as follows:

1. 1.

   We propose a novel neural exploration strategy, EE-Net, where another neural network is assigned to learn the potential gain compared to the current reward estimate.

2. 2.

   Under standard assumptions of over-parameterized neural networks, we prove that EE-Net can achieve the regret upper bound of $\mathcal{O}(\sqrt{T\log T})$, which improves a multiplicative factor of $\sqrt{\log T}$ and is independent of either input or effective dimension, compared to existing state-of-the-art neural bandit algorithms.

3. 3.

   We conduct extensive experiments on four real-world datasets, showing that EE-Net outperforms baselines including linear and neural versions of $\epsilon$-greedy, TS, and UCB.

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.

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 $\tilde{\mathcal{O}}(\sqrt{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 (Abbasi-Yadkori 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.

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\in[T]$, where the sequence $[T]=[1,2,\dots,T]$, the learner is presented with $n$ arms, $\mathbf{X}_{t}=\{\mathbf{x}_{t,1},\dots,\mathbf{x}_{t,n}\}$, in which each arm is represented by a feature vector $\mathbf{x}_{t,i}\in\mathbb{R}^{d}$ for each $i\in[n]$. After playing one arm $\mathbf{x}_{t,i}$, its reward $r_{t,i}$ is assumed to be generated by the function:

where the unknown reward function $h(\mathbf{x}_{t,i})$ can be either linear or non-linear and the noise $\eta_{t,i}$ is drawn from certain distribution with expectation $\mathbb{E}[\eta_{t,i}]=0$. Following many existing works (Zhou et al., 2020; Ban et al., 2021; Zhang et al., 2021), we consider bounded rewards, $r_{t,i}\in[a,b]$. For the brevity, we denote the selected arm in round $t$ by $\mathbf{x}_{t}$ and the reward received in $t$ by $r_{t}$. The pseudo regret of $T$ rounds is defined as:

where $\mathbb{E}[r_{t}^{\ast}\mid\mathbf{X}_{t}]=\max_{i\in[n]}h(\mathbf{x}_{t,i})$ is the maximal expected reward in the round $t$. The goal of this problem is to minimize $\mathbf{R}_{T}$ by certain selection strategy.

Notation. We denote by $\{\mathbf{x}_{i}\}_{i=1}^{t}$ the sequence $(\mathbf{x}_{1},\dots,\mathbf{x}_{t})$. We use $\|v\|_{2}$ to denote the Euclidean norm for a vector $v$, and $\|\mathbf{W}\|_{2}$ and $\|\mathbf{W}\|_{F}$ to denote the spectral and Frobenius norm for a matrix $\mathbf{W}$. We use $\langle\cdot,\cdot\rangle$ to denote the standard inner product between two vectors or two matrices. We may use $\triangledown_{\boldsymbol{\theta}^{1}_{t}}f_{1}(\mathbf{x}_{t,i})$ or $\triangledown_{\boldsymbol{\theta}^{1}_{t}}f_{1}$ to represent the gradient $\triangledown_{\boldsymbol{\theta}^{1}_{t}}f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t})$ for brevity. We use $\{\mathbf{x}_{\tau},r_{\tau}\}_{\tau=1}^{t}$ to represent the collected data up to round $t$.

EE-Net is composed of three components. The first component is the exploitation network, $f_{1}(\cdot;\boldsymbol{\theta}^{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, $f_{2}(\cdot;\boldsymbol{\theta}^{2})$, which focuses on characterizing the level of exploration needed for each arm in the present round. The third component is the decision-maker, $f_{3}$, which focuses on suitably combining the outputs of the exploitation and exploration networks leading to the arm selection.

1) Exploitation Net. The exploitation net $f_{1}$ is a neural network which learns the mapping from arms to rewards. In round $t$, denote the network by $f_{1}(\cdot;\boldsymbol{\theta}^{1}_{t-1})$, where the superscript of $\boldsymbol{\theta}_{t-1}^{1}$ is the index of network and the subscript represents the round where the parameters of $f_{1}$ finished the last update. Given an arm $\mathbf{x}_{t,i},i\in[n]$, $f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t-1})$ is considered the "exploitation score" for $\mathbf{x}_{t,i}$. By some criterion, after playing arm $\mathbf{x}_{t}$, we receive a reward $r_{t}$. Therefore, we can conduct gradient descent to update $\boldsymbol{\theta}^{1}$ based on the collected training samples $\{\mathbf{x}_{\tau},r_{\tau}\}_{\tau=1}^{t}$ and denote the updated parameters by $\boldsymbol{\theta}^{1}_{t}$.

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 $\mathbf{x}_{t,i}$, with probability at least $1-\delta$, we have the following UCB form:

where $h$ is defined in Eq. (3.1) and $\Psi$ is an upper confidence bound represented by a function with respect to the gradient $\triangledown_{\boldsymbol{\theta}^{1}_{t-1}}f_{1}$ (see more details and discussions in Appendix D). Then we have the following definition.

Let $y_{t,i}=r_{t,i}-f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t-1})$. When $y_{t,i}>0$, the arm $\mathbf{x}_{t,i}$ has positive potential gain compared to the estimated reward $f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t-1})$. A large positive $y_{t,i}$ makes the arm more suitable for exploration, whereas a small (or negative) $y_{t,i}$ makes the arm unsuitable for exploration. Recall that traditional approaches such as UCB intend to estimate such potential gain $y_{t,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 $y_{t,i}$, we use a neural network $f_{2}(\cdot;\boldsymbol{\theta}^{2})$ to represent $\Psi$, where the input is $\triangledown_{\boldsymbol{\theta}^{1}_{t-1}}f_{1}(\mathbf{x}_{t,i})$ and the ground truth is $r_{t,i}-f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t-1})$. Adopting gradient $\triangledown_{\boldsymbol{\theta}^{1}_{t-1}}f_{1}(\mathbf{x}_{t,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 $f_{1}$.

Moreover, in the upper bound of NeuralUCB or the variance of NeuralTS, there is a recursive term $\mathbf{A}_{t-1}=\mathbf{I}+\sum_{\tau=1}^{t-1}\nabla_{\boldsymbol{\theta}^{1}_{\tau-1}}f_{1}(\mathbf{x}_{\tau})\nabla_{\boldsymbol{\theta}^{1}_{\tau-1}}f_{1}(\mathbf{x}_{\tau})^{\top}$ 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 $\boldsymbol{\theta}^{2}_{t-1}$ in the exploration network $f_{2}$ because we have conducted gradient descent for $\boldsymbol{\theta}^{2}_{t-1}$ based on $\{\nabla_{\boldsymbol{\theta}^{1}_{\tau-1}}f_{1}(\mathbf{x}_{\tau})\}_{\tau=1}^{t-1}$. Therefore, this form $\boldsymbol{\theta}^{2}_{t-1}$ is similar to $\mathbf{A}_{t-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 $f_{2}(\triangledown_{\boldsymbol{\theta}^{1}_{t-1}}f_{1}(\mathbf{x}_{t,i});\boldsymbol{\theta}^{2}_{t-1})$ as the "exploration score" of $\mathbf{x}_{t,i}$, because it indicates the potential gain of $\mathbf{x}_{t,i}$ compared to our current exploitation score $f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t-1})$. Therefore, after receiving the reward $r_{t}$, we can use gradient descent to update $\boldsymbol{\theta}^{2}$ based on collected training samples $\{\triangledown_{\boldsymbol{\theta}^{1}_{\tau-1}}f_{1}(\mathbf{x}_{\tau}),r_{\tau}-f_{1}(\mathbf{x}_{\tau};\boldsymbol{\theta}^{1}_{\tau-1}\}_{\tau=1}^{t}$. We also provide other two heuristic forms for $f_{2}$’s ground-truth label: $|r_{t,i}-f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t-1})|$ and $\text{ReLU}(r_{t,i}-f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t-1}))$. We compare them in an ablation study in Appendix B.

3) Decision-maker. In round $t$, given an arm $\mathbf{x}_{t,i},i\in[n]$, with the computed exploitation score $f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1}_{t-1})$ and exploration score $f_{2}(\triangledown_{\boldsymbol{\theta}^{1}_{t-1}}f_{1};\boldsymbol{\theta}^{2}_{t-1})$, we use a function $f_{3}\left(f_{1},f_{2};\boldsymbol{\theta}^{3}\right)$ to trade off between exploitation and exploration and compute the final score for $\mathbf{x}_{t,i}$. The selection criterion is defined as

Note that $f_{3}$ can be either linear or non-linear functions. We provide the following two forms.

(1) Linear function. $f_{3}$ can be formulated as a linear function with respect to $f_{1}$ and $f_{2}$ :

where $w_{1}$, $w_{2}$ are two weights preset by the learner. When $w_{1}=w_{2}=1$, $f_{3}$ can be thought of as UCB-type policy, where the estimated reward $f_{1}$ and potential gain $f_{2}$ are simply added together. In experiments, we report its empirical performance in ablation study (Appendix B).

(2) Non-linear function. $f_{3}$ also can be formulated as a neural network to learn the mapping from $(f_{1},f_{2})$ to the optimal arm. We transform the bandit problem into a binary classification problem. Given an arm $\mathbf{x}_{t,i}$, we define $p_{t,i}$ as the probability of being the optimal arm for $\mathbf{x}_{t,i}$ in round $t$. For brevity, we denote by $p_{t}$ the probability of being the optimal arm for the selected arm $\mathbf{x}_{t}$ in round $t$. According to different reward distributions, we have different approaches to determine $p_{t}$.

1. 1.

   Binary reward. $\forall t\in[T]$, suppose $r_{t}$ is a binary variable over $a,b(a<b)$, it is straightforward to set: $p_{t}=1.0$ if $r_{t}=b$; $p_{t}=0.0$, otherwise.

2. 2.

   Continuous reward. $\forall t\in[T]$, suppose $r_{t}$ is a continuous variable over the range $[a,b]$, we provide two ways to determine $p_{t}$. (1) $p_{t}$ can be directly set as $\frac{r_{t}-a}{b-a}$. (2) The learner can set a threshold $\theta,(a<\theta<b)$. Then $p_{t}=1.0$ if $r_{t}>\theta$; $p_{t}=0.0$, otherwise.

Therefore, with the collected training samples $\left\{\left(f_{1}(\mathbf{x}_{\tau};\boldsymbol{\theta}_{\tau-1}^{1}),f_{2}(\triangledown_{\boldsymbol{\theta}_{\tau-1}^{1}}f_{1};\boldsymbol{\theta}_{\tau-1}^{2})\right),p_{\tau}\right\}_{\tau=1}^{t}$ in round $t$, we can conduct gradient descent to update parameters of $f_{3}(\cdot;\boldsymbol{\theta}^{3})$.

Table 1 details the working structure of EE-Net. Algorithm 1 depicts the workflow of EE-Net, where the input of $f_{2}$ is normalized, i.e., $\phi(\triangledown_{\boldsymbol{\theta}^{1}_{t-1}}f_{1}(\mathbf{x}_{t,i}))$. Algorithm 1 provides a version of gradient descent (GD) to update EE-Net, where drawing $(\boldsymbol{\theta}_{t}^{1},\boldsymbol{\theta}_{t}^{2})$ 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.

In this section, we provide the regret analysis of EE-Net when $f_{3}$ is set as the linear function $f_{3}=f_{1}+f_{2}$, 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 $\mathcal{D}$. In each round $t$, $n$ samples $\{(\mathbf{x}_{t,1},r_{t,1}),(\mathbf{x}_{t,2},r_{t,2}),\dots,(\mathbf{x}_{t,n},r_{t,n})\}$ are drawn i.i.d. from $\mathcal{D}$. This is standard distribution assumption in over-parameterized neural networks (Cao and Gu, 2019). Then, for the analysis, 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).

For example, the operator can be designed as $\phi(\triangledown_{\boldsymbol{\theta}^{1}}f_{1}(\mathbf{x}_{t,i}))=(\frac{\triangledown_{\boldsymbol{\theta}^{1}}f_{1}(\mathbf{x}_{t,i})}{\sqrt{2}\|\triangledown_{\boldsymbol{\theta}^{1}}f_{1}(\mathbf{x}_{t,i})\|_{2}},\frac{\mathbf{x}_{t,i}}{\sqrt{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 $\mathbf{x}\in\mathbb{R}^{d}$, without loss of generality, we define the fully-connected network $f$ with depth $L\geq 2$ and width $m$:

where $\sigma$ is the ReLU activation function, $\mathbf{W}_{1}\in\mathbb{R}^{m\times d}$, $\mathbf{W}_{l}\in\mathbb{R}^{m\times m}$, for $2\leq l\leq L-1$, $\mathbf{W}^{L}\in\mathbb{R}^{1\times m}$, and $\boldsymbol{\theta}=[\text{vec}(\mathbf{W}_{1})^{\intercal},\text{vec}(\mathbf{W}_{2})^{\intercal},\dots,\text{vec}(\mathbf{W}_{L})^{\intercal}]^{\intercal}$.

Initialization. For any $l\in[L-1]$, each entry of $\mathbf{W}_{l}$ is drawn from the normal distribution $\mathcal{N}(0,\frac{2}{m})$ and $\mathbf{W}_{L}$ is drawn from the normal distribution $\mathcal{N}(0,\frac{1}{m})$. Note that EE-Net at most has three networks $f_{1},f_{2},f_{3}$. 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 $\eta_{1},\eta_{2}$ are the learning rates for $f_{1},f_{2}$; $K_{1}$ is the number of iterations of gradient descent for $f_{1}$ in each round; and $K_{2}$ is the number of iterations for $f_{2}$.

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

where $\mathbf{H}$ is the neural tangent kernel matrix (NTK) (Jacot et al., 2018; Arora et al., 2019) and $\lambda$ is a regularization parameter. Similarly, in linear contextual bandits, Abbasi-Yadkori et al. (2011) achieve $\mathcal{O}(d\sqrt{T}\log T)$ and Li et al. (2017) achieve $\mathcal{O}(\sqrt{dT}\log 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.

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 ¹¹1https://github.com/banyikun/EE-Net-ICLR-2022.

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. 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. 2.

   KernelUCB (Valko et al., 2013) adopts a predefined kernel matrix on the reward space combined with a UCB-based exploration strategy.

3. 3.

   Neural-Epsilon adapts the epsilon-greedy exploration strategy on exploitation network $f_{1}$. I.e., with probability $1-\epsilon$, the arm is selected by $\mathbf{x}_{t}=\arg\max_{i\in[n]}f_{1}(\mathbf{x}_{t,i};\boldsymbol{\theta}^{1})$ and with probability $\epsilon$, the arm is chosen randomly.

4. 4.

   NeuralUCB (Zhou et al., 2020) uses the exploitation network $f_{1}$ to learn the reward function coming with an UCB-based exploration strategy.

5. 5.

   NeuralTS (Zhang et al., 2021) adopts the exploitation network $f_{1}$ 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 $f_{1}$ is built by a 2-layer fully-connected network with 100 width. For the exploration network $f_{2}$, we use a 2-layer fully-connected network with 100 width as well. For the decision maker $f_{3}$, 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\leq 500$, $f_{3}$ is set as $f_{3}=f_{2}+f_{1}$, and for $t>500$, $f_{3}$ is set as a neural network with two 20-width fully-connected layers. Setting $f_{3}$ 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 2 and Figure 3 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 $f_{2}$ 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 $f_{2}$ and the different setting of $f_{3}$.

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: We are grateful to Shiliang Zuo and Yunzhe Qi for the valuable discussions in the revisions of EE-Net. This research work is supported by National Science Foundation under Awards No. IIS-1947203, 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.