Year: 2021

Abstract:
The expected improvement (EI) is a popular technique to handle the tradeoff between exploration and exploitation under uncertainty. However, compared to other techniques as Upper Confidence Bound (UCB) and Thompson Sampling (TS), the theoretical properties of EI have not been well studied even for noncontextual settings such as standard bandit and Bayesian optimization. In this paper, we introduce and study the EI technique as a new tool for the contextual bandits problem which is a generalization of the standard bandit. We propose two novel EI based algorithms for this problem, one when the reward function is assumed to be linear and the other when no assumption is made about the reward function other than it being bounded. With linear reward function, we demonstrate that our algorithm achieves a near-optimal regret. Further, when no assumptions are made about the form of reward, we use deep neural networks to model the reward function. We prove that this algorithm also achieves a near-optimal regret. Finally, we provide an empirical evaluation of the algorithms on both synthetic functions and various benchmark datasets. Our experiments show that our algorithms work well and consistently outperform existing approaches.

heading: 1 INTRODUCTION
text: The stochastic multi-armed bandit (Bubeck and Cesa-Bianchi, 2012; Lattimore and Szepesvári, 2020) has been extensively studied as an important model to optimize the trade-off between exploration and exploitation in sequential decision making. Among its many variants, the contextual bandit is widely used in real-world applications such as recommendation Li et al. (2010), advertising Graepel et al. (2010), robotic control Mahler et al. (2016), and healthcare Greenewald et al. (2017).
In each round of a contextual bandit, the agent observes a feature vector (the “context”) for each of the K arms, pulls one of them, and in return receives a scalar reward. The goal is to maximize the cumulative reward, or minimize regret (see our definition in Section 2), in a total of T rounds. To do so, the agent must find a trade-off between exploration and exploitation. Currently, there are two popular techniques to solve this trade-off. The first technique is called the optimism in face of uncertainty which chooses the optimal action by maximizing upper-confidence bounds (UCB), and the second one using Thompson Sampling (TS) whose basic idea is to estimate a posterior distribution on the reward, and sample an arm that maximises a random reward drawn from this distribution. A series of work has applied both UCB and TS or their variants to explore in contextual bandits with many forms of reward functions - linear and nonlinear. In the line of UCB, there are works of (Li et al., 2010; Chu et al., 2011; Abbasi-yadkori et al., 2011) for the linear bandits, works of (Filippi et al., 2010; Valko et al., 2013) for nonlinear contextual bandits, and very recently Zhou et al. (2020), which uses neural networks to learn the reward function. In the line of TS, Agrawal and Goyal (2013); Russo and Roy (2014) are for linear bandits, Russo and Roy (2014); Kveton et al. (2020) for generalized linear functions, and Riquelme et al. (2018); Zhang et al. (2021) for nonlinear bandits using deep neural networks.
Besides UCB and TS, the expected improvement (EI) (Močkus, 1975) is one of the oldest and popular techniques to handle the tradeoff between exploration and exploitation under uncertainty. Different from UCB and TS, the EI is a greedy improvement-based heuristic that samples an action offering the greatest expected improvement over the incumbent. EI enjoys wide use due to its simplicity and ability to handle uncertainty in Bayesian optimization (Osborne, 2010; Zhan and Xing, 2020) - a
problem that is closely related to infinite-arm multi-arm bandits. There are also several papers Ryzhov (2016); Qin et al. (2017) using EI to study the best-arm identification problem (also known as “pure exploration”) which is a finite variant of Bayesian optimization. However, for a contextual bandit which is a generalization of the standard bandit due to its reward depending on both the actions and contexts, it is yet to be seen whether EI can handle the trade-off between exploration and exploitation well. In fact, to our best knowledge, there are no EI-based algorithms even for the standard bandits in the setting of exploration and exploitation.
A key challenge of analyzing EI-based algorithms comes from its improvement function involving nonlinear, nonconvex term unlike UCB and TS. This causes the difficulty of the analysis of EI. Another challenge comes from the fact that this improvement function is mainly designed to reduce uncertainty, and thus, solely focusing on exploration. These reasons together explains why theoretical analyses of EI based methods is limited, compared to that of UCB and TS. Furthermore, these few notable exceptions typically focus on bounding the simple regret in EI based Bayesian optimisation (Bull, 2011) and best-arm identification (Ryzhov, 2016; Qin et al., 2017). To our best knowledge, none of the existing work has investigated the cumulative regret of EI in the proper bandit setting yet.
Against this background, our work proposes the first theoretical analysis of EI based methods in the classical bandit setting. In particular, we consider contextual bandits and are interested in deriving bounds on cumulative regret for our algorithms which is more suitable for contextual bandits. We note that cumulative regret bounds are stronger than the simple regret bounds and are usually more challenging to establish. In summary, our main contributions in this paper are:
• We introduce and formalize Expected Improvement as a new strategy for contextual bandits creating a parallel to UCB and TS.
• We propose two EI-based algorithms. The first algorithm (LinEI) assumes the reward function to be linear whilst the second algorithm (NeuralEI) is designed for the case when no assumption can be made about the reward function other than boundedness and we model it by a deep neural network.
• For the linear reward function, our LinEI algorithm is able to achieve O(d √ T ln2(T )lnTδ )
regret which matches the information theoretic lower bound Ω(d √ T ) for this problem (up to ln(T )). For the general reward function, we prove that, under standard assumptions (see section 4.1), our NeuralEI algorithm is able to achieve Õ(d̃ √ T ) regret, where d̃ is the “effective” dimension of a neural tangent kernel matrix and T is the number of rounds.
• Finally, we provide an empirical evaluation of the algorithms on both synthetic functions and various benchmark datasets. Our experiments show that LinEI outperforms other baselines for linear bandits, and when the reward function is non-linear, NeuralEI outperforms all baselines.

heading: 2 PROBLEM SETTING
text: We consider the problem of K-arm contextual bandits. At time t = 1, 2, ..., the agent observes K contextual vectors xi,t ∈ Rd, then selects an arm a(t) and receives a reward ra(t),t which has a general form as follows:
ra(t),t = h(xa(t),t) + ξa(t),t,
where h is an unknown reward function satisfying 0 ≤ h(x) ≤ 1 for any x ∈ Rd, and ξa(t),t is conditionally R-subGaussian for a constant R ≥ 0, i.e., ∀λ ∈ R,E[eλξa(t),t |{xi,t}Ki=1] ≤ exp(λ 2R2
2 ). In our setting, we assume that these context vectors may be chosen by an adversary in an adaptive manner after observing the arms played and their rewards up to time t− 1. For the unknown function h, we consider two cases as follows:
• the reward function h is linear, i.e., h(xt,i) = xTt,iθ∗, where θ∗ ∈ Rd are fixed but unknown parameters. Without loss of generality, we here assume that ||xi,t|| ≤ 1, ||θ∗|| ≤ 1. • the reward function h is modelled by a fully connected neural network with depth L ≥ 2
defined recursively by
f(x; θ) = √ mWLσ(WL−1σ(...σ(W1x))),
where σ(x) := max{x, 0} is the ReLU activation, θ = (vec(W1); ...; vec(WL)) ∈ Rp is the collection of parameters of the neural network, p = dm + m2(L − 2) + m. Without loss of generality, we assume that the width of each hidden layer is the same (i.e., m) for convenience in analysis. We denote the gradient of the neural network function by g(x; θ) = 5θf(x; θ) ∈ Rp.
Performance Measure. Let a∗(t) denote the optimal arm at time t. The objective is to minimize the cumulative regret R(T ) = ∑T t=1(x T a∗(t),tθ ∗ − xTa(t),tθ ∗).

heading: 3 THE LINEI ALGORITHM FOR LINEAR BANDITS
text: Prior and Posterior Distributions. We follow the design for priors of the reward function like TS algorithm (Agrawal and Goyal, 2013). We assume that the likelihood of reward ri,t of each arm i follows a Gaussian distribution N (x>i,tθ∗, v2), where the variance v2 will be specified later. Let X(t) = λI + ∑t−1 j=1 xa(j),jx > a(j),j , θ̂t = X(t) −1( ∑t−1 j=1 xa(j),jra(j),j). Then if we assume that the prior for θ∗ at time t is given byN (θ̂t, v2X2(t)), then the posterior distribution of θ∗ at time t+ 1 is N (θ̂t+1, v2X2(t+ 1)) ( see the proof in Appendix A.1 in (Agrawal and Goyal, 2013)).
Expected Improvement for Linear Contextual Bandits. We now use this posterior distribution update to define the form of the expected improvement of each arm in contextual bandits. We denote r+t = maxi∈K{xTi,tθ̂t} which is the largest mean estimate of reward among all arms at time t. We define the expected improvement of an arm i at time t as
αEIi,t = Eµ∼N (θ̂t,v2tX(t)−1)[max{0, x > i,tµ− r+t }], (1)
The αEIi,t measures the potential of arm i to improve upon the largest posterior reward mean at time t. We note that in Eq(1), r+t plays a role as an incumbent. In Bayesian optimization, the incumbent is usually selected as the best reward value so far, or the largest reward mean so far. In our setting with contextual bandits, we choose the latter for convenient in analysis.
Further, we define si,t = √ xTi,tX(t) −1xi,t. We see that if µ ∼ N (θ̂t, v2X(t)−1) then the marginal
distribution of xTi,tµ is Gaussian with mean x T i,tθ̂t and standard deviation vsi,t. Thus, we can express the expected improvement in closed form as follows
αEIi,t = (x T i,tθ̂t − r+t )Φ(
x>i,tθ̂t − r + t
vsi,t ) + vsi,tφ(
x>i,tθ̂t − r + t
vsi,t ), (2)
where Φ(.) and φ(.) are the standard normal cdf and pdf function of the normal distribution respectively.
LinEI Algorithm. We use this expected improvement to design our algorithm. We consider two particular arms among all arms: the arm selected by the EI mechanism, denoted by a(t). Formally, a(t) = argmaxi∈[K]α EI i,t ; and the best-so-far arm, denoted by ã(t). Formally, ã(t) = argmaxi∈[K]{x>i,tθ̂t}.
Algorithm 1 The Linear Expected Improvement Algorithm (LinEI) Input: parameters C0, β
1: for t = 1 to T do 2: Observe contexts {xi,t}Ki=1 3: Set a(t) := argmaxi∈Kα EI i,t , ã(t) = argmaxi∈K{x>i,tθ̂t} 4: if αEIa(t),t ≥ C0 tβ
then 5: a(t) = a(t) 6: else 7: a(t) = ã(t) 8: end if 9: Play arm a(t), and observe reward ra(t),t
10: Update X(t+ 1) = λId + ∑t j=1 xa(j),jx > a(j),j , θ̂t+1 = X(t+ 1) −1( ∑t j=1 xa(j),jra(j),j) 11: end for
Selecting arm a(t) by the EI strategy yields potentially the highest expected improvement over maxi∈[K]{x>i,tθ̂t}. However, when the expected improvement (measured by αEIi,t of all arms) is small, an empirical observation is that the exploitation using ã(t) is often better than the solution a(t). To make use of this intuition, we propose a modification in the EI algorithm by introducing a threshold function g(t). If maxi∈[K]αEIi,t ≥ g(t) then the algorithm selects a(t), otherwise selects ã(t) for the pure exploitation. We consider g(t) = C0
tβ which is controlled by two parameters C0, β. Our
algorithm is summarized in Algorithm 1. The threshold function is a crucial factor in achieving our optimal convergence rate for our algorithm and a relevant choice of parameters of the threshold function is discussed in the next section.
Comparison with several related works. Our LinEI is related to the -Greedy strategy. The -Greedy strategy in the standard bandit plays the best arm based on current estimates with probability 1 − and otherwise explores uniformly at random. The -Greedy EI algorithm in Bayesian optimization (Bull, 2011)) plays the arm with the highest EI with probability 1− and otherwise explores uniformly at random. Unlike these algorithms, our algorithm removes the exploration at random, and uses a time-varying threshold function for arm-selection instead of a coin flip. Our algorithm is also different from the TTEI algorithm (Qin et al., 2017) for the best arm identification in a non-contextual setting. TTEI algorithm is designed to allocate a sufficient number of samples to the suboptimal arms to eliminate these arms with high confidence. While this is appropriate to solve BAI but it can not be used for contextual bandit problems. This is because it is not possible to eliminate an arm completely as in contextual bandits, this arm could be the best arm in some context. See Section C in our Supplementary Material for more discussion.

heading: 3.1 THEORETICAL ANALYSIS
text: In this section, we provide the regret bound for the proposed LinEI algorithm. There are the two main challenges in our theoretical analysis. The first one is to extend several original techniques of (Bull, 2011) in Bayesian optimization which is non-contextual and noise-free setting to our setting with contexts and noisy. Different from the work of (Bull, 2011) where the reward is assumed to be in a RKHS space with a Matérn kernel, our setting assumes that the reward is a linear function of contexts and an unknown parameter θ∗. The second challenge is that the EI strategy is suitable for BAI problem whose goal is to seek the arm with the best reward rather for contextual bandits which the concept “best arm” does not make sense. Solving these challenges is non-trivial. See our discussion in section C in the Supplementary Material. We achieve an upper bound for the instantaneous regret rt = x > a∗(t),tθ ∗ − x>a(t),tθ ∗ as in Lemma 9 in our Supplementary Material:
rt ≤ [ τ(βtvt )
τ(−βtvt ) (2βt + vt) + (
√ 2ln(Rtβ) + 6 √ C−20 dln( t+ 1
δ ) + 1)vt]sa(t),t +
τ(βtvt )
τ(−βtvt ) C0 tβ ,
Algorithm 2 Neural Expected Improvement Algorithm (NeuralEI) Input: Number of rounds T , exploration variance ν, network width m, regularization parameter λ and parameters C0, β
1: Set U0 = λI 2: for t = 1 to T do 3: Set a(t) := argmaxi∈[K]α EI i,t , ã(t) = argmaxi∈[K]{f(xi,t; θt−1)} 4: if αEIa(t),t ≥ C0 tβ
then 5: a(t) = a(t) 6: else 7: a(t) = ã(t) 8: end if 9: Play arm a(t), and observe reward ra(t),t
10: Set θt to be the output of gradient descent for solving Eq(3) 11: Ut = Ut−1 + g(xa(t),t; θt)g
>(xa(t),t; θt)/m 12: end for with probability at least 1 − δ, where vt = R √ 9dln t+1δ , βt = R √ dln( t3δ ) + 1, si,t =√
x>i,tX(t) −1xi,t and the function τ is defined as τ(z) = zΦ(z) + φ(z). Here, we note that
parameter vt plays the role of parameter v at time t we discussed above. In our analysis, vt is used to eliminate the influence of βt so that βtvt is bounded as t grows.
Finally, we achieve the following regret bound for our proposed algorithm with a completed proof as well as the relevant choice of parameters in Supplementary Material.
Theorem 1. Given any δ ∈ (0, 1). If vt = R √ 9dln t+1δ , √ d ≤ C0 ≤ d and 0.5 ≤ β ≤ 3 then with probability 1− δ, the cumulative regret of the LinEI algorithm is bounded as
R(T ) = O(d √ T ln2(T )ln T
δ ).

heading: 4 THE NEURALEI ALGORITHM FOR NEURAL CONTEXTUAL BANDITS
text: In this section, we extend our Algorithm 1 when the reward function is modelled by a fully connected neural network. Similar to the Neural Thompson Sampling approach (Zhang et al., 2021), our algorithm maintains a Gaussian distribution for each arm’s reward. At time t, the posterior distribution of the reward of arm i is updated as follows. The mean is set to the output of the neural network, denoted by f(xi,t; θt−1), and the variance is defined as σ2i,t = λg >(xi,t; θt−1)U −1 t−1g(xi,t; θt−1)/m, where the matrix U−1t is updated as Ut = Ut−1 + g(xa(t),t; θt)g >(xa(t),t; θt)/m and parameter θt is the solution to the following minimization problem:
minθL(θ) = t∑ i=1 [f(xa(i),i;θ)− ra(i),i]2/2 +mλ||θ − θ0||22/2, (3)
where θ0 is randomly initialized network parameter. We can adapt gradient descent algorithms to solve this problem with step size η and total number of iterations J like the gradient descent algorithm of (Zhou et al., 2020).
Expected Improvement for Neural Contextual Bandits. We now define the form of the expected improvement in this setting. At each time step t, we denote f+t = maxi∈[K]{f(xi,t; θt−1)} which is the highest mean estimate of f(x, θt−1) among all arms at time t. We define the expected improvement value of an arm i at time t as
αEIi,t = Ef̃i,k∼N (f(xi,t;θt−1),ν2σ2i,t)[max{0, f̃i,k − f + t }].
Further, the above expectation can be computed analytically as follows
αEIi,t = (f(xi,t; θt−1)− f+t )Φ( f(xi,t; θt−1)− f+t
νσi,t ) + νσi,tφ( f(xi,t; θt−1)− f+t νσi,t ) (4)
Our NeuralEI algorithm is given in Algorithm 2. It starts by initializing θ0 = (vec(W1); ...; vec(WL)), where for each 1 ≤ l ≤ L − 1,Wl = (W, 0; 0,W ), each entry of W is generated independently from N(0, 4/m); WL = (w>,−w>), each entry of w is generated independently from N(0, 2/m). NeuralEI extends our LinEI algorithm to the setting where the reward function h is modelled by a fully connected neural network.

heading: 4.1 REGRET ANALYSIS
text: In this section, we provide a regret analysis of the NeuralEI algorithm. We first provide necessary background on the neural tangent kernel (NTK) theory, which plays an important role in our analysis. Following a recent line of research (Zhou et al., 2020; Zhang et al., 2021), we define the covariance between two data point x, y ∈ Rd as follows: H̃(1)(x, y) = σ(1)(x, y) =
x>y, A(l)(x, y) = ( σ(l)(x, x) σ(l)(x, y) σ(l)(x, y) σ(l)(y, y) ) , σl+1(x, y) = 2E(u,v)∼N(0,A(l)(x,y))[σ(u)σ(v)], H̃(l+1)(x, y) = 2H̃(l)(x, y)E(u,v)∼N(0,A(l)(x,y))[σ′(u)σ′(v)] + σ(l+1)(x, y). Similar to (Zhou et al., 2020; Zhang et al., 2021), we assume that the number of rounds T is known and denote the neural tangent kernel (NTK) matrix H ∈ RTK×TK based on all contextual vectors {xt,k}t∈[T ],k∈[K]. Renumbering {xt,k}t∈[T ],k∈[K] as {xi}i=1,...,TK , then each entry Hij is defined as
Hij = (H̃ (L)(xi, xj) + σ (L)(xi, xj))/2, (5)
for all i, j ∈ [TK]. Based on the above definition, we impose the following assumption on the contexts generated by the adversary and the corresponding NTK matrix H .
Assumption 1. Let H be defined in Eq(5). There exists λ0 > 0 such that H ≥ λ0I . In addition, for any t ∈ [T ], k ∈ [K], ||xt,k||2 = 1 and [xt,k]j = [xt,k]j+d/2.
Remark 1. Compared to Algorithm 1 for linear bandits, our Algorithm 2 needs an additional Assumption 1 to guarantee the convergence. The assumption that the NTK matrix is positive definite has been considered in prior work on NTK which is a mild condition and also imposed in other related works (Arora et al., 2019; Du et al., 2019; Zhou et al., 2020; Zhang et al., 2021). The assumption on contexts ensures that f(xi,t; θ0) = 0 for any i ∈ [K], t ∈ [T ]. The NTK technique builds a connection between deep neural networks and kernel methods. It enables us to adapt some complexity measures for kernel methods to describe the complexity of the neural network through the notation of the effective dimensions as defined in (Zhou et al., 2020; Zhang et al., 2021). The effective dimension d̃ of matrix H with regularization parameter λ is defined as d̃ = log det(I+H/λ)log(1+TK/λ) .
Using these notations, we are now ready to present the second main result of the paper. Let a∗(t) = argmaxi∈[K]E[ri,t] be the optimal action at round t that maximizes the expected reward, we define the expected cumulative regret after T iterations as R(T ) = E[ ∑T t=1(ra∗(t),t− ra(t),t)]. Then, we achieve the following upper regret bound for our Algorithm 2 by combining our EI techniques for LinEI with NTK techniques. A completed proof is provided in Supplementary Material.
Theorem 2. Under Assumption 1, set the parameters in Algorithm 2 as λ = 1 + 1/T , ν = B + R √ d̃log(1 + TK/λ) + 2 + 2log(1/δ), where B = max{1, √ 2h>H−1h} with h =
(h(x1), ..., h(xTK)) >. If √ d̃ ≤ C0 ≤ d̃, β ≥ 2, and the network width m satisfies m ≥ poly(γ, T,K,L, log(1/δ)), then with probability at least 1− δ, the regret of Algorithm 2 is bounded as
R(T ) ≤ O(d̃ √ βlog(1 + TK)log(T )T ).
Remark 2. The regret bound depends on the parameter β. The best choice is β = 2 that tightens the regret. Theorem 2 implies the regret of NeuralEI is on the order of Õ(d̃ √ T ). Similar to previous results (Zhou et al., 2020; Zhang et al., 2021), our results require a large value of m. This is rooted in the current deep learning theory based on the neural tangent kernel.

heading: 5 RELATED WORKS AND DISCUSSION
text: Given the vast literature on bandit algorithms, we restrict our review to linear bandits and neural contextual bandits.
Linear Contextual Bandit. A lower bound of Ω(d √ T ) for linear bandits was given by Dani et al. (2008), when the number of arms is allowed to be infinite. (Abbasi-yadkori et al., 2011) analyze a UCB-style algorithm and provide a regret upper bound O(dlog(T ) √ T + √ dT log(T/δ)). When the
number of arms K is finite, (Chu et al., 2011) achieve a regret bound of O( √ Tdln3(KT lnT )/δ)
with probability at least 1 − δ. (Bubeck et al., 2012) provides an algorithm based on exponential weights, with regret of orderO(d √ T logK). These algorithms may not be effective when the number of arms K is large. For example, when K is exponential in d, the regret bound of (Chu et al., 2011) would become O(d2 √ T ) showing a quadratic growth in d. We note that although our algorithm is a Bayesian approach, our regret bounds will hold irrespective of whether or not the actual reward distribution matches the Gaussian likelihood function. Thus, our bounds for EI algorithm are directly comparable to the UCB family of algorithms. This is also mentioned in Agrawal and Goyal (2013).
The Thompson Sampling algorithm (Agrawal and Goyal, 2013) and an alternative given by Abeille and Lazaric (2017) often bear an additional √ d in the regret bound compared to UCB based bounds. See our Table 1. Very recently, Kim et al. (2021) improved this regret bound of TS by integrating a doubly robust estimator with TS. However, this work requires additional significant computations and their setting is restrictive in the sense that contexts need to be independent. Our EI-based algorithm achieves the same regret bound order as in Kim et al. (2021), however, it caters to a more general setting where the contexts may be controlled by an adaptive adversary and therefore may not be independent.
Another approach for linear bandits is the Information Directed Sampling (IDS) which was introduced by Russo and Van Roy (2014). It provides an action-selection mechanism by minimizing the information ratio between the squared expected regret and the mutual information between optimal action and the next observation over all action sampling distributions. IDS obtains a performance improvement over TS and UCB algorithms in some cases, but has heavy sampling requirements. It has been shown in their experiments that IDS requires significantly more compute time than Thompson sampling and UCB algorithms. Recently, (Baek and Farias, 2021) provided a modification of the arm scoring rule of IDS to reduce computations. However, both Russo and Van Roy (2014) and (Baek and Farias, 2021) only provide the bounds on expected regret. In contrast, our work provides regret bounds in terms of cumulative regret which is tighter than expected regret.
Neural Contextual Bandit. Neural contextual bandits are becoming attractive due to the current advancement in optimization and generalization of deep neural networks (Arora et al., 2019; Du et al., 2019). While Neural contextual bandits have been considered in both popular techniques UCB (Zhou et al., 2020) and TS (Zhang et al., 2021), we consider this problem in a new setting using the EI technique. A recent work of Xu et al. (2020) combines the deep learning and the representation learning to improve the computational efficiency of the previous works, however, it considers a weaker version of the general reward function that is a linear function of deep network based extracted features.
Due to the space limitation, we added more discussion on related works in Section B in the Supplementary Material.

heading: 6 EXPERIMENTS

heading: 6.1 LINEAR BANDITS
text: In this subsection, we assess the performance of our LinEI algorithm on several benchmark dataset including covertype, magic, avila, dry bean, statlog, letter, pendigits, all from UCI (Dua and Graff, 2017). We compare the LinEI with methods designed for linear bandits including: LinTS (Agrawal and Goyal, 2013), LinUCB (Abbasi-yadkori et al., 2011), Linear Epsilon Greedy for the linear reward, LinIDS Russo and Van Roy (2014) for linear bandits. To transform these classification problems into multi-armed bandits, we adapt the disjoint models to build a context
feature vector for each arm: given an input feature x ∈ Rd of a k-class classification problem, we build the context feature vector with dimension kd as x1 = (x; 0; ...; 0), x2 = (0;x; ...; 0), ..., xk = (0; 0...;x). The algorithm generates a set of predicted reward and pulls the greedy arm. For these classification problems, if the algorithm selects a correct class by pulling the corresponding arm, it will receive a reward as 1, otherwise 0. The cumulative regret over time horizon T is measured by the total mistakes made by the algorithm.
We set the time horizon of our algorithm to 10000 for all data sets. In the experiments, we shuffle all datasets randomly. For (λ, ν) used in LinUCB and LinTS and our algorithm, we set λ = 1 following previous works and do a grid search of ν ∈ {1, 0.1, 0.01} to select the parameter with the best performance. All experiments are repeated 10 times, and the average with standard error are reported. For LinIDS, we use the number of samples M = 100. For Linear Epsilon Greedy, we use = 0.1. For our LinEI algorithm, we can choose any value C0 ∈ [ √ d, d] and β ∈ [0.5, 3]. For LinEI, we set
C0 = √ d and β = 2.
Figure 1 shows the total regret of all algorithms for datasets bean, covertype and statlog. The Linear Epsilon Greedy performs the worst. This implies that the random exploration is not as effective as other methods. While LinUCB, LinTS and LinIDS are competitive, all these methods are significantly outperformed by the proposed algorithm. The arm-selection of our LinEI bases on two strategies: expected improvement and greedy strategy. Compared to Linear Epsilon Greedy, our greedy strategy is similar. It confirms that the exploration of the expected improvement is effective. This suggests that using the expected improvement strategy is efficient in linear bandits. Due to space limit, the additional results on magic, pendigits, letter, and avila are shown in Section A of Supplementary Material.

heading: 6.2 NEURAL BANDITS
text: We compare the proposed NeuralEI with baselines including: LinUCB (Abbasi-yadkori et al., 2011), our LinEI for linear bandits problem, Neural Epsilon Greedy, NeuralUCB (Zhou et al., 2020), NeuralTS (Zhang et al., 2021). We do the same classification problems as the experiments in subsection Linear Bandits. For methods using the neural network, we use one-hidden layer neural networks with 100 neurons to model the reward function. During posterior updating, gradient descent is run for 100 iterations with learning rate 0.001. For Neural UCB/Thompson Sampling and Neural EI, we use a grid search on λ ∈ {1, 101, 10−2, 10−3} and ν ∈ {10−1, 10−2, 10−3, 10−4, 10−5}. We consider our algorithm on both synthetic datasets and real-world datasets.
Synthetic Datasets. In these experiments, we use contextual bandits, we use contextual bandits with dimension d = 10 and K = 5 actions. The context vectors {x1,1, ..., xT,K} are chosen
uniformly at random from the unit ball. The reward function r is one of the following synthetic functions r1(x) = (x>θ)2, r2(x) = (x>θ)2, and r3(x) = cos(3x>θ).
Real-world Datasets. Similar to the subsection Linear Bandit, we build the context feature vector with dimension kd as x1 = (x; 0; ...; 0), x2 = (0;x; ...; 0), ..., xk = (0; 0...;x). We also estimate our algorithm on datasets bean, covertype and statlog.
Figures 2 and 3 show our results in the case of the neural bandits problem. In Figure 2, if the reward function is linear, the LinEI outperforms all other neural-based methods because it is designed for the linear bandits. Otherwise, if reward functions are non-linear, LinEI and LinUCB fail to learn them for nearly all tasks due to the nonlinearity of reward functions h. Neural-based methods perform better because they can capture the nonlinearity of the underlying reward function. In real-datasets, while neural-based methods outperform LinEI and LinUCB for datasets covertype and statlog, these methods are not sample-efficient for learning the reward function of dataset bean. Perhaps, the reward function for dataset bean is linear. However, in all cases, our NeuralEI algorithm performs better than other neural-based methods. This suggests that using the expected improvement strategy is effective in both linear bandits and neural contextual bandits.

heading: 7 CONCLUSION
text: We introduced and formalized Expected Improvement as a new strategy for contextual bandits. We proposed two EI-based algorithms and analyzed them theoretically. The first algorithm assumes the reward function to be linear whilst the second algorithm is designed for the case when the reward function is general and can be modelled by a deep neural network. In particular, our LinEI algorithm for linear bandits achieves a near-optimal regret bound and improves the bounds of OFUL and LinTS algorithms. Our promising empirical results on both synthetic and real-world datasets suggested that our algorithms work well in practice compared to other approaches. We believe our work would be useful for further improvements and extensions. There are several interesting open questions. For example, we can extend our work to non-Gaussian distributions to model the unknown reward model parameters and derive regret bounds as long as concentration inequalities can be established. In another direction, we have used NTK in our work, but the NTK theory assumes overparameterised networks and an extension to narrow networks while maintaining the generalization of the reward function is an interesting open problem.

Review summaries:
The paper introduces and studies the expected improvement (EI) technique as a way to balance exploration and exploitation for the contextual bandit problem. The authors propose two EI-based algorithms for linear bandits and for neural bandits for a general class of reward functions. The paper presents regret bounds for both methods and shows the experimental results to support their theoretical claims.

This paper applies expected improvement to contextual bandits to balance exploration and exploitation. The authors proposed LinEL for linear rewards and NeuralEI for general rewards using neural network for approximation. Theoretical analysis claimed that compared with UCB based approaches, LinEL's regret bound reduces a factor of $\sqrt{\log(T)}$. Empirical results validated the effectiveness of LinEL and NeuralEI. 

The authors study regret analysis of the expected improvement (EI), a popular but theoretically understudied technique to handle the tradeoff between exploration and exploitation in bandits.  They propose two novel EI-based algorithms for this problem, one for linear payoff and for deep neural networks. With a linear reward function, we demonstrate that our algorithm achieves a near-optimal regret. In particular, our regret bound reduces a factor of \sqrt{log T} from UCB. They also present numerical studies using the proposed algorithm.

The paper extends and modifies the expected improvement (EI) algorithm for contextual bandits. Specifically, LinEI and NeuralEI are proposed for the linear reward function and general reward function (under some assumptions), respectively. The paper claims that LinEI and NeuralEI achieve the state-of-the-art regret bounds and they work well on both synthetic functions and benchmark datasets.