Expected Improvement-based Contextual Bandits
Authors: Hung Tran-The
Sunil Gupta
Santu Rana
Long Tran-Thanh
Svetha Venkatesh
Venue: ICLR 2022 Submitted (2022)
Keywords: Linear Bandits
Contextual Bandits
Expected Improvement
Neural Tangent Kernel

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 non-contextual 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 bandit 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 a linear reward function, we demonstrate that our algorithm achieves a near-optimal regret. In particular, our regret bound reduces a factor of $\sqrt{\text{log}(T)}$ compared to the popular OFUL algorithm \citep{Abbasi11} which uses the UCB approach, and reduces a factor of $\sqrt{d\text{log}(T)}$ compared to another popular algorithm \citep{agrawal13} which uses the TS approach. Here $T$ is the horizon and $d$ is the feature vector dimension. 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.

Under review as a conference paper at ICLR 2022
EXPECTED IMPROVEMENT-BASEE CONTEXTUAL BAN- DITS
Anonymous authors
Paper under double-blind review
ABSTRACT
The expected improvement (EI) is popular technique to handle the tradeoff between exploration and exploitation under uncertainty. However, compared other techniques as Upper Confidence Bound (UCB) and Thompson Sampling (TS), the theoretical properties of have not been well studied even for non- contextual settings such standard bandit and Bayesian optimization. In this paper, we introduce and study the EI technique as new tool for the contextual bandits problem which is 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 assumption is made about the reward function other than it being bounded. With linear reward function, we demonstrate that algorithm achieves near-optimal regret. Further, when 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.
INTRODUCTION
The stochastic multi-an aamti- bandit (Bubeck and Cesa- Cesa-Bianchi 2012 Lattimore and Szepesvá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 real-world applications such as recommendation [i 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 feature vector (the "context") for each of the K arms, pulls one of them, and in return receives 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 the agent must find trade-off between exploration and exploitation. Currently. there are two popular techniques to solve this orfde-off. The first technique 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 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 Abbbai-yyadkon et al., 201T) for the linear bandits, works of (Filippi 2010 Valko al. (003) for nonlinear contextual bandits, and very recently Zhou et al. (2020).
al.
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 al. (2020) for
generalized linear functions, and Riquelme et al. (2018) Zhang al. 202 for nonlinear bandits
using deep neural networks.
Besides UCB and TS, the expected improvement (EI) (Moč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 El is greedy improvement-barte based heuristic that samples the greatest expected improvement over the incumbent. El enjoys wide use due to its simplicity and ability to handle uncertainty in Bayesian optimization (Osboree) 2010 Zhan and Xing 2020)-
action offering

---

Under review as a conference paper at ICLR 2022
Table 1: The summary of the regret Bounds of the two popular algorithms in linear bandits.
Algorithm
Regret Bound
Dani et 2008)
( (lower bound)
OFUL Abbasi-yadkori et al. 2011
OdIn (T)) V + v (JTin(T/0)
LinTS Agrawal and Goyal 2013)
(ld (T + (In(T)i((188))
Our LinEl
Oidy TIn (T)(
problem that is closely related to infinite-ame arm multi-arm bandits. There also several papers (yzhhv (2016): Qin et al. (2017) using El to study the best-arm identification problem (also known as "pure exploration") which which is generalization of the standard bandit due to its reward depending on both the actions and contexts, 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 El-based algorithms even for the standard bandits in the setting of exploration and exploitation.
finite variant of Bayesian optimization. However, for contextual bandit
A key challenge of analyzing El-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 that of UCB and TS. Furthermore, these few notable exceptions typically focus on bounding the simple regret in El based Bayesian optimisation (Bull, 201T) and best-arm identification (Ryzhov) [016 Qin al.) 2017). To our best knowledge, none of the existing work has investigated the cumulatiin lumulative regret of EI the proper bandit setting yet.
Against this background. work proposes the first theoretical analysis of EI based methods in the classical bandit setting. In particular, we consider contextual bandits and are interested deriving bounds 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 establish. In summary, our main contributions in this paper are:
We introduce and formalize Expected Improvement as new strategy for contextual bandits creating a parallel to UCB and TS.
We propose two El-based algorithms. The first algorithm (LinEl) 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 deep neural network.
For the linear reward function, our LinEI algorithm able to achieve Old ((dd/Tln" (T)
regret which matches the information theoretic lower bound ((dvT) for this problem (up to In(T)). For the general reward function, we prove that, under standard assumptions (see section 4)1,, NeuralEI algorithm is able to achieve (dvTT 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 LinEl outperforms other baselines for linear bandits, and when the reward function is non-linear, NeuralEI outperforms all baselines.
2 PROBLEM SETTING
We consider the problem of K-arm contextual bandits. At time t 1,2,.., ., the agent observes K contextual vectors Zi.t E Rd, then selects an arm a()) and receives a reward Pa(e),t which has general form as follows:
Tott) M(F((O,)) Ea(t),
2

---

Under review as a conference paper at ICLR 2022
where h is an unknown reward function satisfying 0 h(z) I 1 for any RR, and Ea(t).r is conditionally R-suuGGausian for constant R 2 0, i.e. AA E R, [ LK S exp( 2iR² In our setting, we assume that these context vectors may be chosen by an adversary 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(rr,,)) =0,00 0", where 0" IR are fixed but unknown parameters. Without loss of generality, we here assume that || S 1, ||0"1| S L.
the reward function is modelled by a fully connected neural network with depth 2 defined recursively by
f(z;0) -WW.
where (z) := max 0} is the ReLU activation, 0 = (vec Wi :e:::...:e the collection of parameters of the neural network, p dm + mL 2) + m. Without loss of generality, we assume that the width of each hidden layer is the same (i.e., m) for convenience analysis. We denote the gradient of the neural network function by g(2; 0) = VoJ (z; 0) E RP.
E R is
Performance Measure. Let (t) denote the optimal arm at time f. The objective is to minimize the cumulative regret R(T) = Eizi (2 (0,, x a(t)) 0*).
3 THE LINEI ALGORITHM FOR LINEAR BANDITS
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,e of each arm i follows Gaussian distribution Max,, 0" x²), where the variance 2 will be specified later. Let (t) Al + Σz Fa(l) "o))) Ó X( (()- Fa(i)-/aa()i.) Then if we assume that the prior for 0* at time t is given by (i,,, 12 (t)) then the posterior distribution of 0 at time & + 1 is (( xx² 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. maxiex (x.", 0.} which is the largest mean estimate of reward among all arms time t. We define the expected improvement of an arm at time t as
a (A Imax (0,
}}
El measures the potential of arm to improve upon the largest posterior reward mean at time t. The o,t
We note that in Eq ri plays 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 analysis.
Further, define Si,t V Vor, x We that if μ x then the marginal
distribution of xT_,/" is Gaussian with mean 2T and standard deviation US,, Thus, we can express the expected improvement closed form as follows
2T,,0 rt.
2T r )
a = (1:T, -r;"" r
+ us
US
US
where (.) and (b.) are the standard normal edf and pdf function of the normal distribution respec- tively.
LinEI Algorithm. We use this expected improvement to design our algorithm. We consider two particular arms among all arms: the arm selected by the El mechanism. denoted by a()). El. Formally, a(t) argmax a and the best-so-far arm, denoted by a(t). Formally, a(t)
argmax (x.
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1 The Linear Expected Improvement Algorithm (LinEl)
Input: parameters Co. 3
1: for /= = 1 to T do
2: Observe contexts {
3: Set a(t) == ax a(t) argmax (r)
4:
if' EI
(t)) 2 Co then
5:
a(t) a(t)
6:
else
7:
al)) a(l)
8:
end if'
9:
Play arm a(t), and observe reward ra(t),
10: Update X 1) Ala + Ej=1 Fali)s a Bit1 = x (( Fa(i))Ta(jaa))
11: end for
Selecting arm a(t) by the El strategy yields potentially the highest expected improvement over xa 0,) However, when the expected improvement (measured by of! all arms) small, an empirical observation is that the exploitation using ā(t) is often better than the solution ā(t). To make use of this intuition, propose a modification in the EI algorithm by introducing a threshold function (t).. If max ET 2 g(t) then the algorithm selects a(t), otherwise selects a(t) for the pure exploitation. We consider g(t) Cp which is controlled by two parameters Co 8. Our algorithm is summarized in Algorithm 1. The threshold function is a crucial factor in achieving optimal convergence rate for algorithm and relevant choice of parameters of the threshold function is discussed in the next section.
Comparison with several related works. Our LinEl is related to the e-Greedy strategy. The e-Greedy strategy in the standard bandit plays the best arm based on current estimates with proba- bility 1 - and otherwise explores uniformly at random. The e-Greedy EI algorithm in Bayesian optimization (Bull (01Th) 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 time- varying threshold function for arm- selectinn instead of coin flip. Our algorithm is also different from the TTEI algorithm (Qin et al., 2017) for the best arm identification in non-contextual setting. TTEI algorithm 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 arm completely in contextual bandits, this arm could be the best arm in some context. See Section C in our Supplementary Material for more discussion.
3.1 THRORETICAL ANALYSIS
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 our setting with contexts and noisy. Different from the work of (Bull) (0TT] RKHS space with Matérn kernel, setting assumes that the reward is linear function of contexts and an unknown parameter 0*, The second challenge 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 upper bound for the instantaneous regret o (1), -xale) 0" as in Lemma 9 in our Supplementary Material:
(BuTT]20TT] T) where the reward assumed to in
that the El strategy suitable for BAI
T
8
t+1 -+1) + 1)..)a(0), + (2 + vz)) + +11 2ln(1))) + +6 CT cr2
Co
<
T(
7(- 2 10
4

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Neural Expected Improvement Algorithm (NeuralEI)
Input: Number of rounds T, exploration variance v, network width m, regularization parameter and parameters Co,
1: Set Uo XI
2: for = 1 to T do
3: Set a() := [ 1 ,, a(t) argmax (f((((()))))
4:
if a EI att
2 Co then
5:
(t)) a(t)
6:
else
7:
att) ä(t)
8:
end if
9:
Play arm al)), and observe reward ra(t).t
10: Set 02 to be the output of gradient descent for solving Eq(3)
U, = ---1 ((Fa(t) Oe)g (Fa(t), 0c)mm
12:
end for
with probability at least 1 - 8, where U, = 9ddnn B. = R dln( ( + 1, Si,
Rydln((
V "T,, ((), and the function is defined r(=) = x=)) + 6(=). Here, note that parameter v plays the role of parameter v at time we discussed above. In our analysis, et is used to eliminate the influence of Bg so that & 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 8 E (). If vr = RV Rddn 1+1 5) Vd < Co S d and 0.5 s B < then with probability 8, the cunulative regret of the LinEl algorithm is bounded as
R(T) = O(dy (Ti(h
THE NEURALEI ALGORITHM FOR NEURAL CONTEXTUAL BANDITS
In this section, extend our Algorithm I when the reward function modelled by fully connected neural network. Similar to the Neural Thompson Sampling approach (Zhang et al. 2021 our algorithm maintains a Gaussian distribution for each arm't reward. At time 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 ( 0,-1), and the variance is defined as of Ag (Ix,, 1rt 0,-1)/m, where the matrix U,1 is updated as U, UL-1 + g (Fa(t)) 0z)g (Za(t).: 0z) /m and parameter 0 the solution to the following minimization problem:
mA|10 1-t 12/2,
m()) Di P2d
where Og is randomly initialized network parameter. We adapt gradient descent algorithms to solve this problem with step size 77 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 ft [ (f is the highest mean estimate of f(x 0z-1) among all arms at time t. We define the expected improvement value an arm at time as
0,-1)} which
E F ().ea(()) [max (0, Fr.- HHH
a
Further, the above expectation can be computed analytically as follows
(f(xi,,; - -stt f [1 0c-1) - 1it voreso [1 0c-1) Stt 0 1,t
(4)
vo
Vo
5

---

Under review as a conference paper at ICLR 2022
Our NeuralEI algorithm is given in Algorithm 2. It starts by initializing 8u (vec(Wi1; (ec(W
where for each 1 S 1, = (W; O; 0, W), each entry of W is generated independently from (0,, 4/m); Wt = (w - each entry of wo is generated independently from (0, 2 2/m). Fl extends our LinEl algorithm to the setting where the reward function h is modelled by fully connected neural network.
4.1 REGRET ANALYSIS
In this section, we provide a regret analysis of the NeuralEI algorithm. We first provide neces- sary background on the neural tangent kernel (NTK) theory, which plays important role in our analysis. Following a recent line of research (Zhou et al., 2020; Zhang et al. 202I). we de-
fine the covariance between two data point y, E R' as follows: H (z, y) o (I, =
(x, (0(a (a, v)
x y. (x, = (1, a (W..))
of (2. =
[1(++)) (z, 211 (1.0) (x.a)) lo (o'(w)o (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 neu-
ral tangent kernel (NTK) matrix H TTK based all contextual vectors {II, ME]
Renumbering he(t) as (= TK. then each entry Hiy is defined as
Hij = (I. o (0 (x1,
(5)
for all i,j E [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 There exists An > 0 such that H 2 >oT. In addition, for any & E [2], k E [K], || 12 = and [e, = (xt,//jt//2.
Compared to Algorithm for linear bandits, our Algorithm 2 needs an additional Assumption to guarantee the convergence. The assumption that the NTK matrix is positive definite has been considered in prior work on NTK which is mild condition and also imposed in other related works (Arora et al. 2019 Du et al. 2019 Zhou et al.
Remark 1.
Zhang et al. 2021). The assumption on [K]tt
2020
contexts ensures that f : 80)
for any i
The NTK technique builds a connection between deep neural networks and kernel methods. It enables
us 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. [020 Zhang
et al.
2021). The effective dimension of matrix with regularization parameter is defined as
log del H122)
[Tg(A+
Using these notations, a" (t) = x ] be the optimal action at round t that maximizes the expected reward, we
now ready to present the second main result of the paper. Let
define the expected cumulative regret after iterations as R(T) = (ra - ra(t).)] Then, achieve the following upper regret bound for our Algorithm 2 by combining our EI techniques for LinEI with NTK techniques. completed proof is provided in Supplementary Material.
Theorem 2. Under Assumption 1, set the parameters in Algorithm 2 as X = 1 + 1/T,
B + R / TK/A) 2 2log(1/5), where B max(1, /2h T H-1h) with h (,,,),,,,,,((rd If V < C. < d, 8 > 2, and the network width m satisfies m > poly(n, T, L, logg( then with probability at least 8, the regret of Algorithm 2 bounded as
R(T) < ((āv Blog(1 + (T)T)
The regret bound depends on the parameter 3. The best choice is 3 2 that tightens the regret. Theorem implies the regret of NeuralEI is the order of (ddTT). Similar previous results (Zhou et al. 2020. Zhang et al. 202I), our results require large value of m. This is rooted in the current deep learning theory based on the neural tangent kernel.
Remark 2.

---

Under review as a conference paper at ICLR 2022
5 RELATED WORKS AND DISCUSSION
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 ((dyT) for linear bandits was given by Dani et al.
(2008, when the number of arms is allowed to be infinite. (Abbasi- yadkori et al., (001T) analyze
UCB- style algorithm and provide regret upper bound (ddlog(T)vV + (IC[lo((T8)) When the
number of arms K is finite, (Chu et al. 2011) achieve a regret bound of Olyy (KTTTT)))
with probability at least - 0. (Bubeck ct al. 2012) provides an algorithm based on exponential weights, with regret of order (dv/Tlog))) 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 Odd (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 alternative given by Abeille and Lazaric (017) often bear additional v in the regret bound compared to UCB based bounds. See our Table Il Very recently, Kim et al. (202T) 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 El-based algorithm achieves the same regret bound order in Kim et al. (202T), however, it caters to 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. has been shown in their experiments that IDS requires significantly more compute time than Thompson sampling and UCB algorithms. Recently, (Back and Farias 2021) provided a modification of the arm scoring rule of IDS to reduce computations. However, both Russo and Van Roy| (2014) and (Back and Farias 2021) only provide the bounds 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). 1). we consider this problem in a new setting using the El 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 weaker version of the general reward function that 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 Supple- mentary Material.
6 EXPERIMENTS
6.1 LINEAR BANDITS
In this subsection, we assess the performance of our LinEl algorithm on several benchmark dataset including covertype magi c, avila, dry bean, stat log, letter, pendigits. all from UCI (Dua and Graft 2017). We compare the LinEl with methods designed for linear bandits including: LinTS (Agrawal and Goyal 2013), LinUCB (Abbasi-yadkon) et al., 2011). Linear Epsilon Greedy for the linear reward, LinIDS Russo and Van (2014) for linear bandits. To transform these classification problems into multi-armed bandits, we adapt the disjoint models to build context
7

---

Under review as a conference paper at ICLR 2022
Table 2: Characteristics of benchmark datasets used in Section 5.2.
Dataset
letter
pendigits
covertype
avila
magic
dry bean
statlog
Classes (K)
26
10
7
12
2
7
7
Feature Dimension
16
Dataset size
20000
10992
581012
20867
19020
13611
58000
feature vector for each arm: given input feature Rdd of k-class classification problem, build the context feature vector with dimension kd as क = (z; O...; 0), 22 = (0; 2;; .). O),..., Ty = (0; O...; 2r. The algorithm generates classification problems, if the algorithm selects a correct class by pulling the corresponding arm, it will receive a reward as I, otherwise O. The cumulative regret over time horizon T is measured by the total mistakes made by the algorithm.
of predicted reward and pulls the greedy arm. For these
We set the time horizon of our algorithm to 10000 for all data sets. In the experiments, we shuffle all datasets randomly. For (A, 1/) used in LinUCB and LinTS and our algorithm, we set À = following previous works and do a grid search of v {1,0.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 e = 0.1. For our LinEl algorithm, we can choose any value Co E [Vd, d] and B E [0.5, 3]. For LinEI, we set Co = vd and B = 2.
Figure T shows the total regret of all algorithms for datasets bean, covertype and stat log. 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 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 space limit, the additional results on magi i pendi gi ts, letter, and avi la are shown in Section A of Supplementary Material.
1750
BHACS
UELCE
1150
LiUC3
1500
Lrct
Le15
UHES
Unetr Ezii Criieelyy
600
Lrow Esii Greedyy
1150
Lirdd
Spoke Artnlly
1300
3X0
Tonal
Led
500
2003
200
7302
4366
6230
1000
33009
3002
000
E32
1200
33003
2003
603
5300
636
3000
Figure 1: Comparison of our proposed LinEl and baseline algorithms in linear bandits.
6.2 NEURAL BANDITS
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 al. 2020). NeuralTS (Zhang et al. (021I. 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 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 grid search on À {1, 10 10 10 10-33 and {10-1 1, 10 10 10 10 1005). $3. 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 (21,1 "T,, x) are chosen
8

---

Under review as a conference paper at ICLR 2022
1000
3003
7060
Totoh Rogret
500
53009
8000
7003
200
353
440
EX3
BX0
3600
132
1010
1230
2003
6003
6302
2000
terstces
Rersters
110
(a)
(b) (2: 0)2
(c) COS(2
Figure 2: Comparison of NeuralEI and baseline algorithms synthetic reward functions.
Shallog
Cowertppe
8000
1403
130
Exaion Grendy
25000
43/0
303
1000
1310
200
730C
0800
13/00
4355
60.0
5530
1303
2000
6003
6305
2009
Earatons
Revstirrs
18 9839
Figure 3: Comparison of NeuralEI and baseline algorithms on real-world datasets.
uniformly at random from the unit ball. The reward function r is one of the following synthetic functions (x) (x: 0)2 (2()) (x T)) and (2( cos(3r' TQ). ().
Real-world Datasets. Similar to the subsection Linear Bandit, we build the context feature vector with dimension kd as 2 (z.;;...;;)) 0), algorithm on datasets bean, covertype and statlog.
(0; 0), ..., T' (0; 0...; We also estimate our
Figures andd] show results in the case of the neural bandits problem. In Figure 2 if the reward function is linear, the LinEl outperforms all other neural-based methods because is designed for the linear bandits. Otherwise, if reward functions 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. real-datasets, while neural-based methods outperform LinEI and LinUCB for datasets covert ype and stat log, 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.
non-linear, LinEl and LinUCB fail learn them
7 CONCLUSION
We introduced and formalized Expected Improvement as new strategy for contextual bandits. We proposed El-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 deep neural network. In particular, our LinEl 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 non-Gaussian distributions to model the unknown reward model parameters and derive regret bounds as long as concentration inequalities can established. In another direction, networks and an extension to narrow networks while maintaining the generalization the reward function is interesting open problem.
have used NTK in work, but the NTK theory assumes overparameterised

---

Under review as a conference paper at ICLR 2022
REFERENCES
Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In J. ShaworTaylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24, pages 2312 2320- Curran As- sociates, Inc., 2011. URL httpittttt//ppoceediiiiii http://roooeddnnn........s...s neurips https//ccppppppe/////aeeee// e eld5belc7f2E elcbeelc112221555000633333333333 Papp:seea4aaaaa..appppaa .ddf
Mare Abeille and Alessandro Lazarie. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pages 176-184. PMLR, 20-22 Apr 2017.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 127-135, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL.tttpst http:httss/pppoeeeeeeeee /wwpc//eoeeeee//ooeooooooooooooe ings neurips w/wce///bbco//oo/oo of cf24284b be Fb853a pdd
CC pttpp/appr///9//// 20apper/211///111eccc/44440
Jackie Back and Vivek F. Farias. Ts-ucb: Improving on thompson sampling with little to additional computation, 2021.
Sébastien Bubeck and Nicolò Cesa-Bianchi, Regret analysis of stochastic and nonstochastic multi- armed bandit problems, 2012.
Sébastien Bubeck, Nicoló online linear optimization with bandit feedback. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 41.1-41.14, Edinburgh, Scotland, 25-27 Jun 2012. PMLR.
and Sham M. Kakade. Towards minimax policies for
Adam D. Bull. Convergence rates of efficient global optimization algorithms. J. Mach. Learn. Res., 12:2879-2904, November 2011. ISSN 1532-4435.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statisties, volume 15 of Proceedings of Machine Learning Research, pages 208-214, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In 2/ Annual Conference on Learning Theory COLT 2008, Helsinki, Finland, July 9-12, 2008, pages 355-366, 2008. 80 Dani.
cs hewsinki. fttpki.ff.ppp/s.//eeeaam
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1675-1685. PMLR, 09-15 Jun 2019.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive lcs. www.edu/ml
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In J. Lafferty, C. Williams, Shawe-Taylor, R. Zemel, and A. Cu- lotta, editors. Advances in Neural Information Processing Systems, volume 23. Curran Asso- ciates, Inc., 2010. URL http:: pttptppp//pproceeingge nww.ips..p... http://cccccccoooooooooooo/////a 025
pdf
10

---

Under review as a conference paper at ICLR 2022
Thore Graepel, Joaquin Quiñonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian click-thros through rate prediction for sponsored search advertising in microsoft's 's bing search engine. ICML' 10, page 13-20, Madison, WI, USA, 2010. Omnipress. ISBN 978 1755689597
Kristjan Greenewald, Ambuj Tewari, Predrag Klasnja, and Susan Murphy, Action centered contextual bandits, 2017.
Wonyoung Kim, Gi soo Kim, and Myunghee Cho Paik. Doubly robust thompson sampling for linear payoffs, 2021.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration generalized linear bandits. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisties, volume 108 of Proceedings of Machine Learning Research, pages 2066-2076. PMLR, 26-28 Aug 2020.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.1017/9781 108571400 1401.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bande approach to personalized news article recommendation. In Michael Rappa, Paul Jones, Juliana Freire, and Soumen Chakrabarti, editors, WWW. pages 661-670. ACM, 2010. ISBN 978- 978-1-60558-799.
Jeffrey Mahler, Florian T. Pokorny, Brian Hou, Melrose Roderick, Michael Laskey, Mathieu Aubry, Kai Kohlhoff, Torsten Kröger, James Kuffner, and Ken Goldberg. Dex-net 1.0: cloud-based network of 3d objects for robust grasp planning using multi-armed bandit model with correlated rewards. In 2016 IEEE International Conference on Robotics and Automation (ICRA), page 1957-1964. IEEE Press, 2016.
Močkus. On bayesian methods for seeking the extremum. In G. Marchuk, editor, Optimization Techniques IFIP Technical Conference Novosibirsk, July 1-7, 1974, pages 400-404, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg. ISBN 978-3-540-37497-88
Michael A. Osborne. Bayesian gaussian processes for sequential prediction, optimisation and quadrature. 2010.
Chao Qin, Diego Klabjan, and Daniel Russo. Improving the expected improvement algorithm. In Pro- ceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 5387-5397, Red Hook, NY, USA, 2017, Curran Associates Inc. ISBN 97815 10860964.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An em- pirical comparison of bayesian deep networks for thompson sampling. International Confer- ence on Learning Representations, 2018. URL
SyYe6k-CW
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling, 2014.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sam- pling. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Asso- ciates, Inc., 2014. URL httlttttst///proceeeed///e octpr//eeeeeooooierreeeeoeeorrrr httpppp.cccpppppe/1111///// 2/
nww.ips pddf
Ilya O. Ryzhov. On the convergence rates of expected improvement methods. Oper. Res., 64(6):
1515-1528, 2016. doi: 10.1287/0pr..2116.4499 URI.
201 6. 1494
Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the Twenty-Ninth Conference Uncertainty in Artificial Intelligence, 13,'13, page 654 663, Arlington, Virginia, USA, 2013. AUAI Press.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration, 2020.
11

---

Under review as a conference paper at ICLR 2022
Dawei Zhan and Huanlai Xing. Expected improvement for expensive optimization: review. J. Glob. Optim., 78(3):507- 544, 2020. doi: 01.11007//11888-0000000000000000 URL [tLLittp:///diooo/// 10 hee//forrun2-ottttttoocctmm
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In
International Conference on Learning Representations, 2021, URL /ttpsssss///ooeeeeiiii
Dongru Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-based exploration. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Leurning, volume 119 of Proceedings of Machine Learning Research, pages 1492-11502, PMLR, 13-18 Jul 2020.
12


Reviews:
[{"review_id": "sF2IHzIVaGK", "reviewer": "Reviewer_vUVo", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major comments:\n1. There are some existing papers that provide regret bounds for EI-type algorithms, for example, [1] and [2]. I think citing and comparing with these papers is necessary.\n2. LinEI and NeuralEI modify the original EI by using a threshold function, see Line 4 in Algorithm 1 or Algorithm 2. Basically, LinEI and NeuralEI only sample the arm with the largest EI value if and only if the largest EI value is larger than this threshold function; otherwise LinEI and NerualEI sample the arm with the largest posterior reward mean. Intuitively speaking, I think if the largest EI value is small, the arm with the largest EI value is (almost) the same as the arm with the largest posterior reward mean. Hence, I am wondering whether introducing this threshold function is necessary. Do regret bounds still hold without this modification? If not, can the authors elaborate more on the technical difficulties as well as how this modification solves the issues?\n3. Inflating the posterior variance is somewhat necessary for randomized algorithms (e.g., Thompson sampling) in order to show the optimism. I am wondering whether inflating the posterior variance is necessary for deterministic algorithms LinEI and NeuralEI.\n4. In my opinion, the uniform constant $C'$ in the proof of Lemma 10 depends on $\\delta$ (for example, consider $t=1$). If so, the uniform constant $C$ also depends on $\\delta$ and then the final regret bound could have worse dependence on $\\delta$.\n5. I am wondering where Lemma 3 is used in the proof.\n6. Both $\\ln$ and $\\log$ are used in the paper. I think it is consistent to use only one of them. \n\nThere are so many typos in this paper. For example,\n1. In the second sentence of Section 2, it should be $x_{i,t}$. \n2. In the paragraph Performance Measure, the summation should from $t=1$ instead of $i=1$.\n3. In the paragraph Prior and Posterior Distributions, there are three normal distribution. I think none of the variance expressions is correct.\n4. In Equation (2), it should be $s_{i,t}$ instead of $s_i(t)$.\n4. There are so many missing brackets in the supplement material.\n\n\n[1] Nguyen, V., Gupta, S., Rana, S., Li, C., Venkatesh, S.. (2017). Regret for Expected Improvement over the Best-Observed Value and Stopping Condition.\n[2] Ziyu Wang, Nando de Fretias. (2014). Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters.\n", "summary_of_the_paper": "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.", "summary_of_the_review": "As mentioned above, some important references are not cited. To show the technical novelty, detailed comparison with these references is needed. In addition, since the uniform constants in the proof do not have clear dependence on the important parameter $\\delta$ and there are so many typos, it is a bit hard for me to evaluate the correctness and significance of the main results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "pmFiSGH0oz", "reviewer": "Reviewer_TJpE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper introduces and formalizes Expected Improvement as a new strategy for contextual bandits. The EI idea has been around in Bayesian optimization but has not been adapted to contextual bandits.\n- The EI is adapted to show regret bounds in linear bandits and neural bandits, both resulting in sublinear regret bounds.\n- The empirical experiments show that LinEI outperforms other baselines for linear bandits and NeuralEI outperforms all baselines under the non-linear reward functions the paper considers.\n\n Weaknesses:\n- In addition to regret analysis in linear bandits for LinEI, the regret analysis for NeuralEI is rather straightforward using the existing NTK techniques used in Zhou et al., 2020; Zhang et al., 2021. I am not sure what the analysis of NeuralEI adds to the contribution given by LinEI.\n- The claim on the neural version that \"no assumption is made about the reward function other than it being bounded\" isn't necessarily true. It needs to satisfy certain conditions besides boundedness. See the discussions in Zhang et al., 2021.", "summary_of_the_paper": "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.", "summary_of_the_review": "For the reasons above, I am leaning towards weak acceptance.\n\n========== Post-reponses =================\nThanks to the authors for the responses, I am staying with the current score.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "elil5jrynSk", "reviewer": "Reviewer_ccLd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper shows an innovative algorithm using expectation improvement and the corresponding regret analysis.  It improves the upper bound from UCB by \\sqrt{T}.   Although it is debatable whether the upper bound is improved from Thompson sampling since the proposed algorithm does not use any randomization, it has a better upper bound than Thompson sampling by \\sqrt{dT}.   Using expected improvement for exploration tools seems to be a good idea.\n\nThe regret analysis is interesting and innovative.  \n\nThe authors may give a more intuitive explanation of how \\sqrt{d} is shaved compared to Thompson sampling.  It seems like computing expected improvement instead of randomly drawing the estimator from the distribution, a new regret decomposition is possible, and thus \\beta_t and v_t appear in an additive manner instead of multiplicative. \n\nExperiments seem to show the regret grows linearly.  Have you tried a larger T?\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper is well written and shows novel contextual bandit algorithms using expected improvement with new regret analysis.   This could be a nice contribution to the bandit community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "c0ErgDUPEZM", "reviewer": "Reviewer_co1L", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Generally speaking, this work is well-organized and it is interesting in the sense that it is the first the analyze EI-based algorithms for RM in linear bandits. Besides, it shows that the theoretical and numerical performance of the two proposed algorithms.  My major comments are as follows:\n1. The design of the algorithm and the analytical methods seem to be quite standard. Despite the existing discussions, it would be better if the author(s) can further highlight the difference between the proposed algorithm in Qin et al. (2017) and also the challenge to derive the bounds. For example, although the analysis of linEI is a bit different from that of linUCB and linTS, what is the key challenge considering the existing EI analysis for BAI?\n2. The lower bound by Dani et al. (2008) should also be placed in Table 1. Moreover, I suggest to compare to the bounds in \"The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits\" (http://proceedings.mlr.press/v54/lattimore17a/lattimore17a.pdf).\n3. Since the linear bandit setting is a generalization of the standard bandit setting, the authors can consider to also compare the linear algorithm to 'non-linear algorithms' in a standard setting. Both theoretical and numerical comparisons should be possible. \n4. The numerical experiments do not consider a traditional bandit problem. Although it is good to generalize the application of bandit algorithms, what is the numerical comparison in a standard bandit problem, e.g. those in Qin et al. (2017)?", "summary_of_the_paper": "This work proposes two Expected Improvement (EI)-based algorithms to solve the regret minimization problem for the linear and neural bandits. It provides regret analysis for both algorithms and also comparison to some existing algorithms.", "summary_of_the_review": "The paper is okay but the contribution to the study of bandit problems does not seem to be significant. I think it would be better if the authors can highlight their contributions pertaining to what I suggested above.\n\n\n=======================\nThanks for response from the authors. I am increasing my score from 5 to 6.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZJj40XiJuRk", "reviewer": "Reviewer_UDHJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nExpected improvement is a popular method to balance exploration and exploitation. While several works analyzed EI in Bayesian optimization and best-arm identification, this paper provides the first analysis of EI in contextual bandits, which I believe is the most significant contribution. The techniques to combine EI with contextual bandits are rather standard, but I do not think this concern is too serious since this topic is novel and important. Still, I would suggest the authors to include more discussions on the technical challenging in combining EI with contextual bandits (e.g., new tools compared with EI for best-arm identification).\n\nTheoretical results, e.g., regret bounds of LinEL and NeuralEI and the claimed $\\sqrt{\\log(T)}$ regret improvement, are arguably the second contribution of the paper. However, the claim on regret improvement seems incorrect when I check the regret proof of LinEL in detail. I also found many typos / minor errors. The analysis of NeuralEI is analogous to LinEL so similar errors may also exist.\n\n  1. The regret of LinEL should be $O(d\\sqrt{T\\ln(T)\\ln(T^3)\\ln(T/\\delta)})$. This should be intuitive as when bounding the regret, $\\sum_t s_{a(t),t}$ contributes $O(\\sqrt{dT\\ln(T)})$ following Lemma 3; when $\\beta < 3$ we have $\\sqrt{2\\ln(RT^\\beta)} \\leq \\sqrt{2\\ln(RT^3)}$ and $v_t$ contributes another $O(\\sqrt{d\\ln(T/\\delta)})$. Thus the claimed regret improvement does not exists (and it seems that the logarithmic term is worse than OFUL/LinUCB). Please correct me if I was wrong here.\n\n  2. Lemma 10 is not rigorous. When bounding $\\beta_t/v_t$, the second equality should be inequality using the fact that $\\ln(t^3/\\delta) \\leq \\ln(t^3/\\delta^3)$ when $\\delta \\leq 1$; the third step (inequality) is also not rigorous. Without fixing the issues, $C'$ will depend on $\\delta$.\n\n  3. Missing the regularization term $\\lambda$. Lemma 1 and Lemma 3 in their original paper used $I$ for initialization instead of $\\lambda I$, which was ignored by the authors when applying the lemmas. The authors should revise the proof to reflect $\\lambda$.\n\n Typos:\n\n  - In proof of Lemma 5: \"The second one comes from Eq(8)\" -> comes from Eq(6); \"fifth inequality holds\" -> sixth inequality holds; \n  - In proof of Lemma 5: \"The second equality holds due to the definition of ..\" is redundant.\n  - Combining Lemma 5 and 6: redundant $(t)$ in the second step; missing a matching ']' in the last step\n  - In proof of Theorem 3: missing $CC_0/t^{\\beta}$ in the second step; summation should be $\\sum_t$ instead of $\\sum_i$.\n\n========================\nIn the revised version the authors fixed the errors mentioned above. I am increasing my score to 5.\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "Although the theoretical results are flawed, I think most of the errors should be fixable.  I am open to increasing my score if the authors could fix the problems and make the analysis rigorous. The topic of combining EI with contextual bandits is novel and could be interesting to many audiences, even without the claimed regret improvement. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary: 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.

Discussion: The reviewers have identified technical issues in the regret bound of LinEL which has been now corrected. Similarly, reviewers have had difficulty assessing the correctness of the paper due to typos and unclear exposition, and raise concerns regarding the amount of corrections that were necessary to reach the current stage. There is no consensus between the reviewers, and some would feel more comfortable if the paper could go through another round of review after major revision.
Reviewer UDHj points that after corrections, "the regret has an additional $O(\sqrt{\ln T})$ dependency compared with the regret of LinUCB and Thompson Sampling." and this should be discussed in the updated version.
Reviewer co1L suggests to compare to the bounds in "The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits". The authors responded that " To our knowledge, the analysis of the optimal asymptotic regret for contextual bandits as we consider (where the context may be controlled by an adversary) is still an open problem.". In fact, this is the topic of several recent works including:
* "Asymptotically Optimal Information-Directed Sampling" COLT 2021
* "An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits", NeurIPS 2021

The connections of the present work with these two references are strong and should be discussed in more depth. I believe it is a more important discussion than the comparison with the regret bound of LinTS which is yet another problem.  

The reviewers have appreciated the originality of the ideas and for that reason we encourage the authors to revise their draft and submit to a future venue.

Recommendation: Reject.
Decision: Reject