Expected Improvement for Contextual Bandits
Authors: Hung Tran-The
Sunil Gupta
Santu Rana
Tuan Truong
Long Tran-Thanh
Svetha Venkatesh
Venue: NeurIPS 2022 Accept (2022)
Keywords: Expected Improvement
Linear Bandits
Neural Contextual Bandits
Contextual Bandits
Neural Tangent Kernel
Greedy Strategy

Abstract: The expected improvement (EI) is a popular technique to handle the tradeoff between exploration and exploitation under uncertainty. This technique has been widely used in Bayesian optimization but it is not applicable for the contextual bandit problem which is a generalization of the standard bandit and Bayesian optimization. In this paper, we initiate and study the EI technique for contextual bandits from both theoretical and practical perspectives. We propose two novel EI-based algorithms, one when the reward function is assumed to be linear and the other for more general reward functions. With linear reward functions, we demonstrate that our algorithm achieves a near-optimal regret. Notably, our regret improves that of LinTS \cite{agrawal13} by a factor $\sqrt{d}$ while avoiding to solve a NP-hard problem at each iteration as in LinUCB \cite{Abbasi11}. For more general reward functions which are modeled by deep neural networks, we prove that our algorithm achieves a $\tilde{\mathcal O} (\tilde{d}\sqrt{T})$ regret, where $\tilde{d}$ is the effective dimension of a neural tangent kernel (NTK) matrix, and $T$ is the number of iterations. Our experiments on various benchmark datasets show that both proposed algorithms work well and consistently outperform existing approaches, especially in high dimensions.

Expected Improvement for Contextual Bandits
Hung Tran-The" Applied Artificial Intelligence Institute Deakin University
Sunil Gupta Applied Artificial Intelligence Institute
Deakin University
Santu Sana
Tuan Truong FPT Software Al Center
Applied Artificial Intelligence Institute Deakin University
Long Tran-Thanh University of Warwick, UK
Svetha Venkatesh
Applied Artificial Intelligence Institute Deakin University
Abstract
The expected improvement (EI) is popular technique handle the tradeoff between exploration and exploitation under uncertainty. This technique has been widely used in Bayesian optimization but it is not applicable for the contextual bandit problem which is generalization of the standard bandit and Bayesian optimization. In this paper, we initiate and study the EI technique for contextual bandits from both theoretical and practical perspectives. We propose two novel based algorithms, one when the reward funetion is assumed be linear and the other for more general reward functions. With linear reward functions, we demonstrate that our algorithm achieves a near-optimal regret. Notably, our regret improves that of LinTS by factor v while avoiding to solve a NP-hard problem at each iteration as in LinUCB (1. For more general reward functions which are modeled by deep neural networks, we prove that our algorithm achieves a Ö(dTT) regret, where is the effective dimension of neural tangent kernel (NTK) matrix, and T' is the number of iterations. Our experiments various benchmark datasets show that both proposed algorithms work well and consistently outperform existing approaches, especially in high dimensions.
Introduction
The contextual bandit problem an important field machine learning (9) 23
optimize the trade-
off between exploration and exploitation in sequential decision making, and has been extensively studied real-world applications such as personalized recommendation (24). advertising [8]. robotic control [25). and healthcare [19. At each round, the agent observes feature vector (the "context") for each of the arms, pulls one 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 total of T rounds. To do so, the agent must find a trade-off between exploration and exploitation.
There are two standard techniques to solve the trade-off in contextual bandits. The first technique uses the optimism in face of uncertainty which chooses promising actions 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
"Conespondence Hung Tran-The The <hung, tranthe@deakin.c edu. au>,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

from this distribution. A series of work has applied both UCB and TS techniques or their variants to explore contextual bandits with many forms of reward functions- from linear nonlinear. In
for nonlinear contextual bandits, and very recently [39], which uses neural networks to learn the reward function. In the line of TS, 3 [1 are for linear bandits, [31] [2 for generalized linear functions, and [30 38
the line of UCB, there are works of [24] 13 I for the linear bandits, works of 17 35
for nonlinear bandits using deep neural networks.
Different from UCB and TS, the expected improvement (EI) 226 is a greedy improvement-basee
heuristic that samples an action offering the greatest expected improvement over an incumbent. El is also one of the oldest and popular techniques to handle the tradeoff between exploration and exploitation under uncertainty. Due to its ability handle uncertainty, EI has been widely used in Bayesian optimization [28 37 a problem that is closely related to infinite-arm multi-arm bandits. However, to the best of our knowledge, El has not been used contextual bandits.
In addition, in many situations where the exploration may costly or infeasible, EI can be a safer strategy than UCB and TS which are considered as over-exploration strategies. For example, in medical application of contextual bandits, choosing a treatment that is not the estimated-best choice (pure exploration) for a specific patient may be unethical 77. Compared to UCB and TS strategies, El brings a safer treatment because El only chooses a treatment with high possibilities for improvement over the estimated- choice.
Motivated by these advantages, it is valuable to study EI technique in the contextual bandit setting. Whether El can handle well the trade-off between exploration and exploitation in a contextual bandit setting and further in reinforcement learning is an interesting question. Our main contributions in this paper are follows:
We introduce and formalize Expected Improvement new strategy for contextual bandits creating a parallel to UCB and TS.
We propose two El-based algorithms. The first algorithm (LinEl) is designed for the linear bandits whilst the second algorithm (NeuralEI) is designed for more general reward function and we model it by a deep neural network.
For the linear reward function, our LinEl algorithm is able to achieve (dd regret with probability 1 - 6, which matches the information theoretic lower bound ((dv for this problem (up to In))). Our regret improves that of LinTS 33 by a factor v while avoiding solve NP-hard problem each iteration as in LinUCB (.. By this advantage, we will show in section|6.1. that our proposed LinEl scales to high dimensions (in term of d) better than LinUCB and LinTS; in terms of computations. LinEl is also significantly cheaper than both LinUCB and LinTS. Our source code is publicly available at battps://giii thub. com/ Trennnne
Tren--Telunng/Exeeeeee---i-ei -mprectedIIprroeeeeee
for Contextuall Baaneeiitttll-aaitttttt.aa
For the general reward function, we prove that, under standard assumptions (see section 4.1), our NeuralEI algorithm is able to achieve Ō O(dVI regret, where d is the effective dimension of a neural tangent kernel matrix and T is the number of rounds. The regret bound of NeuralEI has the same order as those of NeuralUCB 39) and NeuralTS (38).
Finally, we demonstrate the performance of our proposed El-based algorithms against UCB and TS based approaches and other baselines on various benchmark datasets. Our experiments show that LinEl outperforms other baselines in the linear setting, and when the reward function is non-linear, NeuralEI outperforms all baselines.
Under a theoretical perspective, we remark that the EI technique have not been well studied compared to UCB and TS even in the Bayesian optimization setting. A key challenge of analyzing El algorithms theoretically comes from its improvement function involving nonlinear, nonconvex term. A notable exception is the work in [1I, which provides a convergence analysis of EI for Bayesian optimization in the noise-free setting. Another work in (34] provides the convergence analysis of EI for Bayesian optimization in the noisy setting. There are also several papers B3 29 using EI to study the best-arm identification problem (also known as "pure exploration") which finite variant of Bayesian optimization. However, none of these works provides the optimal convergence rate in their settings. In contrast, our work is the first to show that El can achieve the optimal convergence rate at least in linear contextual bandit setting.

---

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 R then selects an arm a(t) and receives a reward Ca(t),t which has general form as follows:
Ta(t).r h(za(()))))))))))))))))))))))))) Ea(t),
where is an unknown reward mean function satisfying 0 S. h(x) S 1 for any E R and Sa(t),t zero mean, conditionally R-subGaussian noise with a constant
0, i.c. AA
R. EeeAEcto. (x.,) K exp( A In our setting, 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 follows:
The reward function h is linear, i.c., h(zx,)) = =T, where 0" E R is fixed but unknown
parameters. Without loss of generality, we here assume that | S 1, 1|0*11 S 1.
The reward function h is modelled by a fully connected neural network with depth 2 defined recursively by
( V
where (xx) :- max (z, 0} is the ReLU activation, 0 = (vec(Wi);; vec(W E R is the collection of parameters of the neural network with p = dm + m² L - 2) + m which the number of parameters of the network. Without loss of generality, we assume that the width each hidden layer is the same (i.c., m) for convenience in analysis. We denote the gradient of the neural network function by g(x; 0) Vef 0) RP.
Performance Measure. Let (t) (t) denote the optimal arm at time t. The objective is to minimize the cumulative regret R(T) = (x= (1) 0" xx va(t), 0*).
3 The LinEI algorithm for linear bandits
In this section, we design provable version of EI algorithm for linear bandits. To do this, we make some assumptions on the prior distribution of the reward function before defining form of the expected improvement.
Prior and Posterior Distributions. Inspired from the design of priors of the reward function like TS algorithm 3]. we assume that the reward ri, of each arm follows Gaussian distribution N Nx2T,0" )²),, where the variance 2 is a free parameter (possibly time-dependent) that can be set specific to an algorithm. Let
X(t) AI Σ
aa(l)saaans
= x
Σ
1=1
Then if we assume that the prior for 0* at time t is given by Ai (t)), then the posterior distribution 0 time + 1 (1 x2 1)) see the proof Appendix A.I in 33).
Expected Improvement. 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 (x;, which is the largest mean estimate of reward among all arms at time We define the expected improvement of arm i at time i as
EI 1,
E ( 2y [max (0, x xT rt))
This form similar to those of in the case of the multi-arm bandit (2] and the case of Bayesian optimization [34]. but for contextual bandits. The a
EI value measures the potential of arm to
3

---

improve upon incumbent. Here we define the incumbent as the largest posterior reward mean ri at time In Bayesian optimization, the incumbent is usually selected as the best reward value so choose Algorithm The Linear Expected Improvement Algorithm (LinEl)
Input: Parameters Co: 3
1: fort 1 to T do
2: Observe contexts {-1,))
3: Set a(t) = argmax a(t) arx (x
EI
4:
if ET ( 2 Co then
5:
al) a(l)
6:
else
7:
(() ā(t)
8:
end if
9:
Play arm a(t), and observe reward ra(t),
10: Update ((t + 1) Ala + Ej=1 Fall) x(t "))"(Ejj1 Fa())
11:
end for
far [TT, the largest reward mean far (34). In setting with contextual bandits,
the latter for convenience in analysis. We also note that the El form here can not be considered as an expected version of the TS in 33. Even though the expected version of TS may be considered as E "= (()) ee but the expectation operator cannot be taken inside the max operator as is nonlinear function
The closed form for EL Since μ
the random variable oT u is Gaussian
with mean O,, and standard deviation U5;,t, where we define s1, = X() 22,.. Setting
24,1
express the expected improvement in closed form follows
Fl ( + ((=,,))) oi
where (.) and (b.) are the standard normal edf and pdf function of the normal distribution respec- tively.
3.1 Proposed LinEl Algorithm.
We the above form of expected improvement design algorithm. The algorithm is performed iteratively as follows. At iteration I, it selects the arm suggested by the El strategy if the expected improvement (measured selects the arm suggested by the greedy strategy (corresponding to the arms whose posterior reward mean is x() ). The choice of thresholds plays an important role for convergence of our algorithm. We propose use an adaptive threshold in the form of Co A relevant choice of parameters for convergence guarantee will be discussed in the next section. Our algorithm is summarized Algorithm 1.
off of all arms) is higher than threshold. Otherwise it simply
y which is controlled by two parameters Co, B.
We remark that the proposed algorithm can be considered as a variant of El strategy with a simple modification. This modification comes from observation that at an iteration, when the El value is less than some threshold, using a greedy strategy is better than the El strategy in the sense that the instantaneous regret is smaller. This is interesting observation about the relation between the EI and the greedy strategy, and we use this in our algorithm design. Without the modification, pure El algorithm can make the cumulative regret become unbounded in our theoretical analysis.
Comparison with the LinUCB algorithm ①1 and the LinTS algorithm 3 LinUCB looks for the most optimistic value for arm in ellipsoid defined by level set of the posterior rather than integrating over it, and then chooses an arm that maximizes the optimistic value. LinTS generates a sample y from the posterior distributions A ((,,, of xtt--) of reward, and then chooses an arm that maximizes of. In contrast, LinEI could choose an arm whose maximum optimistic value is lower unlike LinUCB, and/or choose an arm having lower aT unlike LinTS but for which there are more possibilities for improvement.

---

3.2 Theoretical Analysis
In this section, we provide the regret bound for the proposed LinEI algorithm.
The El technique is used so far BAI and BO problems to seek the best arm with the highest reward mean. In such problems, the reward mean of each arm is fixed in advance. To leverage this property, 29 uses the allocation matching technique to allocate enough number of samples to suboptimal arms so that property of incumbent to derive directly an upper bound for the simple regret. However, in contextual bandits where the best arm does not exist, and the mean reward of any arm can be different in different iterations, the monotonicity property of incumbent disappears, and the allocation technique is also no longer applicable. The proposed LinEl addresses these challenges. Moreover, it selects an arm based on not only EI strategy but also a greedy strategy depending on threshold function. This makes our regret analysis different from the standard EI technique 36 [27]
eliminate these with high confidence. In BO, [1]] uses the monotonicity
In our proof, we first extend several results in [[]] in Bayesian optimization in a non-contextual setting setting with contexts and noises. For instance, the following lemma is used to upper bound and lower bound the expected improvement for each arm
Lemma 3.1. Pick 0 < 8 < 1. Set b max
r.). Then with probability 1 z² we have
La 3,5t, S ditt I 1,,t + (3, + v()s,.
Here, 3, = RV dln( ((n(z)) + 1, = x[[, xx,, and Us is used instead of u. Then, depending on the arm selection by our LinEl algorithm, we can upper bound the instantaneous regret r (a- - x =a(t), H" by two different ways. Combining them, we achieve an upper bound for the instantaneous regret Ti = "0-10.00
0 as in section C of our Supplementary Material:
[(
7( (23, + v 8.)0) + 8,8a(0, + 7( 2
Co
2ln(R(0) + 2 30/ 20n2d f
<
7( 2 B
with probability at least 1 8. The function is defined as r(2) = (=)) ((2). Here, we note that parameter e plays the role of parameter v at time we discussed above. In our analysis, 0y is used to climinate the influence of B, so that & is bounded t grows. Ve
Finally, by relevant choice of parameters Co and B, we achieve the regret bound for our proposed algorithm as follows:
Theorem 3.2. Given any d E 1). If R + 1, Vd S Co S d and 0.5 < 8 < 3 then
with probability 6, the cumulative regret of the LinEl algorithu is bounded as
R(T) = Old (T)
4 The NeuralEI algorithm for Neural Contextual Bandits
In this section, we extend our Algorithm 1 to the more general setting where the reward func- tion is modelled by a fully connected neural network. Similar to the Neural Thompson Sam- pling approach (38), our algorithm maintains Gaussian distribution for each arm's 's reward. At time f, the posterior distribution of the reward of arm is updated as follows. The mean is set to the output of the neural network, denoted by (( and the variance is de- fined of, >g T (II, (EL.ri 0m-1//m, where the matrix U, is updated U,- U-1 + g(za(t),: (Ia(t) 01)m m and parameter 6 the solution to the following minimization problem:
ming Ei( - r2/2) mA|10 6p 1
where Og is randomly initialized network parameter. We can adapt gradient descent algorithms to solve this problem with step size 7) and total number of iterations J like the gradient descent algorithm of [39].
5

---

Algorithm 2 Neural Expected Improvement Algorithm (NeuralEI)
Input: Number of rounds T, exploration variance network width m, regularization parameter and parameters Co.
1: Set Uo = Al
2: for 1 to T do
E1 3: Set a(t) == [[[]
i, ä(t) argmax [e[K] [ (
EI 4: if T at 2 ya
then
5:
a(t) = a(t)
6:
else
7:
att) = ä(t)
8:
end if
9:
Play arm a()), and observe reward ra(t).t
Set 0r to be the output of gradient descent for solving Eq(3)
11: U, = Ut- + g(Fa(t) (Fa(t), 01mm
end for
Expected Improvement for Neural Contextual Bandits. We now define the form the expected improvement in this setting. At each time step i, we denote ftr ( which is the highest mean estimate of fax, f2-1) among all arms at time t. We define the expected improvement value of an arm at time as
mmxx(0, (0, JiM Ht
( the above expectation can be computed analytically as vol.
Further, by setting 2,,1 follows
Fl 0i
(2,,, + ((2,,))
(4)
Our NeuralEI algorithm is given Algorithm 2. starts by initializing Oo (vec(W (Wr)).
where for each 1 < 1 < 1, W (W, 0; 0, W), each entry of W is generated independently from N00, 4/m); Wz = (w" w each entry of w is generated independently from (0, 2 2/m). NeuralEI extends our LinEl algorithm the setting where the reward function h is modelled by fully connected neural network.
4.1 Regret Analysis
In this section, we provide regret analysis of the NeuralEI algorithm. We first provide necessary back- ground on the neural tangent kernel (NTK) theory, which plays important role in our analysis. Fol- lowing a recent line of research [39 38), we define the covariance between two data point æ, E Rd
(z.) (x y)
follows: (x)) u) (1) (x,v) v) TT A (x,1)
(Z)))) (0
o (2,
2E (1.0))) (2.w1) (a (u)o (w), H (x,)) = 2x. y) (1. lo (u))o'))) (1+1) (ar, y). Similar to 39 38, assume that the number of rounds T is known and denote the neural tangent kernel (NTK) matrix E TTK*TK based on all contextual vectors heet)
Renumbering (er,:eeett)) as {r:)i=1,.... then each entry Hig is defined as
Hij = (L) (I,, x,) (L) 2;)//,
(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 4.1. Let H be defined in Eq 5). There exists Ao > such that H 2 Ag1. In addition, for any & [2], k [K]. | 1 and Fr, = [zr,k]j+d/2.
Remark 1. Compared to Algorithm for linear bandits, our Algorithm 2 needs additional Assumption to guarantee the convergence. The assumption that the NTK matrix positive definite has been considered in prior work NTK which is mild condition and also imposed in other

---

related works 4 i [ E [T].
15
39
38
The assumption contexts ensures that f 8b) = 0 for any
The NTK technique builds a connection between deep neural networks and kernel methods. enables adapt some complexity measures for kernel methods describe the complexity of the neural network through the notation of the effective dimensions as defined in 33 38). The effective
dimension of matrix H with regularization parameter À is defined as d = log der (4
log( (TTK/)))
Using these notations, we are now ready to present the second main result of the paper. Let at) argmax (Brl ] be the optimal action round & that maximizes the expected reward, we define the expected cumulative regret after T iterations as R(T) = EI
- ra(t),)) Then, we achieve the following upper regret bound for our Algorithm 2 by combining our EI techniques for LinEI with NTK techniques. completed proof provided in Supplementary Material.
Theorem 4.2. Under Assumption 1, set the parameters in Algorithm 2 as X = 1 + 1/T,
B Rv àl TK/X) + + 2log(1/6), where B max/1, 22 22hTH' H-1 with h (h(z1)..... h(TTK)) If vd s Co S d, 8 2 2, and the network width m satisfies > poly(r, T, K, L, 10,1o((166) then with probability at least 6, the regret of Algorithm 2 bounded as
R((T) S O Blog(1 (Koglg(T)))
The regret bound depends on the parameter B. The best choice is B = 2 that tightens the regret. Theorem 4.2 implies the regret of NeuralEI is on the order of ('d This result matches the regret bound NeuralUCB ((39), NeuralTS ((8)), as well of 12. The effective dimension d measures how quickly the eigenvalues of H diminish, and only depends on 7 logarithmically in several special cases ((35), according to [39]. Furthermore, [38] shows that d can be upper bounded if all contexts are nearly some low-dimensional subspace of the RKHS space spanned by NTK. Currently, (20] gives an explicit sublinear regret bound for a neural network based UCB algorithm. However, their solution requires that contexts lie on on the d-dimensional hyper-sphere. Compared to these works, our El based results may be of independent interest.
Remark 2.
Remark 3. Similar to most of existing results in neural bandits, our results require large value of m. This rooted in the current deep learning theory based on the neural tangent kernel.
4.2 Technical Challenges
While the proof of NeuralEI follows the same lines as that of LinEl, we emphasize several key differences. First, define filtration Fi-1 the union of history until time t 1. and the contexts at time t. Given a time f, we define an event Ey as follows:
3 = fw F. Vi E [K], If,. ((11,;;0-11) S auorth
where Alogt + 2logh.
Similarly, define event E follows:
E = {w F. Vi [K], ((1,,;0,-1)) - -((x,,)) S vo,, + e(m)),
where e(m) defined as in 38
Based on the definitions of event Eع and Et, we achieve two different ways to lower bound and upper bound the expected improvement as follows:
Lemma 4.3. Assume that the event Eh holds. Set Jr,t = max(0, - ftt. Then for every
i [K), we have
J - - <(m) S ait
El S Ji,t voi +o =(m).
Lemma 4.4. Assume that the event &y holds. Set Li,t = max(0, Fr. fit Then for every i E [K],
we have
I - QQVOi i & a,3. < I + ules + 1)0
El
7

---

While Lemma 4.3 is an adaptation of Lemma 3.1 to neural contextual bandits, Lemma 4.4 is a novel result compared to the regret analysis in our Section 3.1 for linear bandits. Challenges of analyzing the regret of NeuralEl come from the fact that there exists additionally factor <(m) in 4.3 Compared to LinEl, it hard to analyze directly the regret (1),) ))) - h((Fa(t).)) We divide the analysis into two cases: if a (t), S e(m), we can follow the technique as in LinEI. Otherwise, we use another
way to bound the regret using novel result as we mentioned in the main paper. Please see Lemma D.11 in the appendix for details.
Related Works and Discussion
Given the vast literature on bandit algorithms, restrict review linear bandits and neural contextual bandits.
Linear Contextual Bandit. A lower bound of ((dVT) for linear bandits was given in [4], when the number of arms is allowed to be infinite. [ analyze a UCB-style algorithm and provide regret upper bound ((dlog(T) vT + / (T))o))(()) Compared to this work, the regret of our proposed LinEl has an additional VIn, however, it still matches the information theoretic lower bound in this
setting. When the number of arms K is finite, 13 achieve regret bound of O( T (KTInT)
with probability at least - 5. [1O] provides algorithm based on exponential weights, with regret of order (dv K). 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 3 would become Ódd /T) showing a quadratic growth in d.
The Thompson Sampling algorithm and alternative given in (2] bear additional v in the regret bound. Very recently, (21) improved this regret bound of TS in some cases by integrating a doubly robust estimator with TS. However, this work requires additional significant computations and their setting is limited in independent contexts. In contrast, our El-based algorithm achieves the optimal order of d even in a general setting where the contexts may be controlled by an adaptive adversary.
Another approach for linear bandits is the Information Directed Sampling (IDS) which was introduced in [32]. 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, [5] provided a modification of the arm scoring rule of IDS to reduce computations. However, both (32 and [S] 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 [5). Neural contextual bandits have been considered in both popular techniques UCB [39] and Thompson Sampling (38). Currently, [6] proposes novel neural exploration strategy and their solution achieves a sublinear regret on T. Compared to all existing works in this sub-field, our El based algorithm is new, and may be of independent interest.
Due to space limit, we will add additional related works in Section B of Supplementary Material.
6 Experiments
6.1 Linear Bandits
In this subsection, we assess the performance of our LinEI algorithm on several benchmark datasets including covertype, magic, avila, dry bean, statlog, letter, pendigits, all from UCI [66. See our Table for details. We compare the LinEl with methods designed for linear bandits including: LinTS 3] LinUCB M. Linear Epsilon Greedy for the linear reward, LinIDS (32) for linear bandits. To transform these classification problems into multi-armed bandits, adapt the
8

---

Table 1: Characteristics of benchmark datasets used in Section 6.
Dataset
letter
pendigits
covertype
avila
magic
dry bean
statlog
Classes (K)
26
10
7
12
2
7
Feature Dimension
17
16
54
10
10
16
Dataset size
20000
10992
581012
20867
19020
13611
58000
Beer
Ceeertyp
Statlog
1750
6X0
1900
1580
Greedy
Grendy
Epolos Grenty
1250
150
750
1003
250
terations
Figure 1: Comparison of our proposed LinEl and baseline algorithms in linear bandits.
disjoint models to build context feature vector for each arm: given an input feature z Rd of k-class classification problem, we build the context feature vector with dimension kd as (r;; 0; ...; 0), 22 (0; x; ...; 0), ..., J.. Th (0; 0...; The algorithm generates set of predicted reward and pulls the greedy arm. For these classification problems, if the algorithm selects correct class by pulling the corresponding arm, will receive reward as otherwise 0. The cumulative regret over time horizon 7' 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 (X, v)) used in LinUCB and LinTS and our algorithm, we set À = following previous works and do grid search of y/ {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, and B E [0.5, 3). For LinEI, we set Co = vi and B
Figure shows the total regret of all algorithms for datasets bean, covertype and statlog. The Linear Epsilon Greedy performs the worst. While LinUCB, LinTS and LinIDS are competitive. all these methods are significantly outperformed by the proposed algorithm. This difference in performance is because of the strategy used by each method. Due to space limit, the additional results on magic, pendigits. letter, and avila are shown in Section A of Supplementary Material. Our results on various datasets confirm that the exploration of the expected improvement effective in practice. This also is widely observed in Bayesian optimization.
6.1.1 Comparison I. LinUCB, LinTS and LinEI on a large-seale multi-label dataset
Cumulative Regret
Eurlex-4k dataset
2000
LinUCB
1500
LinTS
1000
LinEl
500
500
1000 1500 2000 2500 3000 Iterations
Figure 2: Comparison of LinUCB, LinTS and our proposed LinEl on a large-scale multi-label dataset.
We now compare our proposed LinEl against LinUCB and LinTS on the eurlex-4k dataset which is a
large multi-label dataset [8]. It contains data with 5000 features and 3993 labels. It corresponds to contextual bandit problem with 3993 actions and the dimension context is 5000 + -3993 = 8993
when mapped to our setting. This can be considered contextual bandit problem with large action

---

Stating
Covertope
0300
3423
130
:200
5530
2.300
2 1900
300
790
1000
1305
4000
1230
400
6508
3009
terstions
torztens
Figure 3: Comparison of NeuralEI and baseline algorithms on real-world datasets.
space and with very high dimensions. Due the heavy computation, we run algorithms on only 3000 datapoints from the test set. Our experimental results show that LinEl scales better to high dimensions and large action space (see our Figure 2 This can be explained the regret of LinEl better than that of LinTS by a factor vd while LinUCB an over- exploration strategy in high dimensions. In terms of required computations, LinEI is significantly cheaper than LinUCB and LinTSS. Please see Section A.2 the supplementary material for details. Due to space limit, we will add additional comparisons in term of dimension d in Section A.1 of Supplementary Material.
6.2 Neural Bandits
compare proposed NeuralEI with baselines including: LinUCB [ our LinEI for linear bandits problem, Neural Epsilon Greedy, NeuralUCB [39], NeuralTS 38). We do the same classification problems as the experiments in subsection Linear Bandits. For methods using the neural network, one-hidden layer neural networks with 100 neurons to model the reward function. During posterior updating, gradient descent run for 100 iterations with learning rate 0.001. For Neural UCB/Thompson Sampling and Neural EI, we use grid search on À {1, 10 1,00,00 1010 10-2, 10-3) and E {10-1, 10-2, 10 3, 10-4, 10-5] as in 39 and [88] We consider our algorithm on both synthetic datasets and wolld datasets. Due to space limit, will provide results on synthetic
datasets in Section of Supplementary Material.
Real-world Datasets. Similar the subsection Linear Bandit, we build the context feature vector with dimension kd as our algorithm on datasets bean, covertype and statlog. Figure 3 show our results the case of the neural bandits problem. Neural-based methods perform better because they can capture the nonlinearity of the underlying reward function. In real-datasets, while neural-based methods outperform LinEl 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.
(r; 0), = (0; .....IIII I = (0; o...: We also estimate
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. Our promising empirical results on walldorld datasets suggested that our El-based algorithms work well in practice compared to other approaches especially in high dimensions. We believe our work would be useful for further improvements and extensions. For example, extending El to the reinforcement learning setting is an interesting open problem.
References
[1] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Percira, and K. Q. Weinberger,
10

---

editors, Advances in Neural Information Processing Systems, volume 24, pages 2312-2320 Curran Associates, Inc., 2011.
[2] Mare Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 176-184, PMLR, 20-22 Apr 2017.
[3] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's 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.
[4] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[5] Jackie Back and Vivek F. Farias. Ts-ucb: Improving on thompson sampling with little to no additional computation, 2021.
[6] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. EE-net:
neural networks in contextual bandits. In International Conference on Learning Representations, 2022.
[7] Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi. Mostly exploration- algorithms for contextual bandits. Management Science.
[8] K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. The extreme classification repository: Multi-label datasets and code, 2016.
[9] Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems, 2012.
[10] Sébastien Bubeck, Nicoló Cesa-Bianche Bianchi, and Sham M. Kakade. Towards minimax policies for 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 Jun 2012. PMLR.
Edinburgh, Scotland, 25-27
[11] Adam D. Bull. Convergence rates of efficient global optimization algorithms. Mach. Learn Res., 12:2879-2904, November 2011.
[12] Sayak Ray Chowdhury, Aditya Gopalan, and abc. On kernelized multi-armed bandits. ICML'17, page 844-853. JMLR.org. 2017.
[13] 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 Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208-214, Fort Lauderdale, FL, USA, 11-13 Apr 2011. PMLR.
[14] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In 21st Annual Conference on Learning Theory COLT 2008, Helsinki, Finland, July 9-12, 2008, pages 355-366, 2008.
[15] 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.
[16] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
11

---

[17] 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. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
[18] Thore Graepel, Joaquin Quiñonero Candela, Thomas Borchert, and Ralf Herbrich. Web-scale bayesian click-through rate prediction for sponsored search advertising in microsoft's s bing search engine. ICML' 10, page 13-20, Madison, WI, USA, 2010. Omnipress.
[19] Kristjan Greenewald, Ambuj Tewari, Predrag Klasnja, and Susan Murphy. Action centered contextual bandits, 2017.
[20] Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret, 2021.
[21]
Wonyoung Kim, Gi soo Kim, and Myunghee Cho Paik. Doubly robust thompson sampling for linear payoffs, 2021.
[22] Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in 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.
[23] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[24] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual- approach to personalized news article recommendation. In Michael Rappa, Paul Jones, Juliana Freire, and Soumen Chakrabarti, editors, WWW, pages 661-670. ACM, 2010.
(25] 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: A cloud-based network of 3d objects for robust grasp planning using multi-armed bandit model with correlated rewards. In 2016 JEEE International Conference on Robotics and Automation (ICRA), page 1957-1964. IEEE Press, 2016.
[26] Močkus. On bayesian methods for seeking the extremum. In G. Marchuk, editor, Optimiza- tion Techniques IFIP Technical Conference Novosibirsk, July 1-7, 1974, pages 400-404, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg.
[27] Vu Nguyen, Sunil Gupta, Santu Rana, Cheng Li, and Svetha Venkatesh. Regret for expected improvement over the best-observed value and stopping condition. In Min-Ling Zhang and Yung-Kyun Noh, editors, Proceedings of the Ninth Asian Conference on Machine Learning. volume 77 of Proceedings of Machine Learning Research, pages 279-294, PMLR, 15-17 Nov 2017.
[28] Michael A. Osborne, Bayesian gaussian processes for sequential prediction, optimisation and quadrature. 2010.
[29] Chao Qin, Diego Klabjan, and Daniel Russo. Improving the expected improvement algorithm. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 5387-5397, Red Hook, NY, USA, 2017. Curran Associates Inc.
[30] Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In International Conference on Learning Representations, 2018.
[31] Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling, 2014.
[32] Daniel Russo and Benjamin Van Roy. Learning to optimize via inoommttion-irectted sampling. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[33] Uyy O. Ryzhov. On the convergence rates of expected improvement methods. Oper Res., 155- 2016.
12

---

[34] Hung Tran-The, Sunil Gupta, Santu Rana, and Svetha Venkatesh. Regret bounds for expected improvement algorithms gaussian process bandit optimization. Gustau Camps-Valls. cisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 8715-8733 8737. PMLR, 28-30 Mar 2022.
Valls. Fran-
[35] 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 on Uncertainty in Artificial Intelligence, 13 page 654-663, Arlington, Virginia, USA, 2013.
AUAI Press.
[36] Ziyu Wang and Nando de Freitas. Theoretical analysis of bayesian optimisation with unknown gaussian process haper-parameters, 2014.
[37] Dawei Zhan and Huanlai Xing. Expected improvement for expensive optimization: a review. J. Glob. Optim., 7803)507-554, 2020.
[38] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference Learning Representations, 2021.
[39] Dongruo 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 on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 11492-11502 PMLR, 13-18 Jul 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A]. You are strongly encouraged to include a justification your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
13

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasng new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "xqCuBv-KvKx", "reviewer": "Reviewer_XWbh", "summary": "The paper shows how to extend the widely-used expected improvement heuristic from into the contextual bandits setting to create a new basic type of contextual bandit algorithm. They propose two novel algorithms, and propose a method for choosing an improvement threshold for controlling the exploration/exploitation cutoff which provably achieves an $\\tilde O(\\sqrt{T})$ regret rate, even in settings with adaptive adversaries. The paper then shows that the proposed methods have strong empirical performance.", "questions": "1) Are $\\Phi$ and $\\phi$ supposed to be the cdf and pdf of the normal distribution? They seem to be introduced on line 143 without that being explicitly stated.", "limitations": "The paper discusses the limitations of using a Gaussian distribution for the reward model, as well the fact that their usage of the NTK kernel restricts the neural network classes that they can use.\n\nThe paper does not address potential negative societal impact of this work.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) Paper extends the expected improvement heuristic into contextual bandits, building a connection with the best arm identification and bayesian optimization literature, providing a novel and significant result.\n2) Paper provides proofs for the results, and is able to get competitive regret rates for linear contextual bandits and neural bandits.\n3) Paper shows experimental evidence for the value of the method.\n4) Paper is clearly written, and contextualizes expected improvement in the broader literature, and clearly shows how the analysis of the linear and neural cases differ.\n\nWeaknesses:\n1) (minor) I wish the paper explained a bit more how the algorithms are able to work even with an adaptive adversary.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "vFKu5uurCCK", "reviewer": "Reviewer_rpMu", "summary": "The authors propose a novel contextual bandit algorithm based on the expected improvement (EI) and study the corresponding regret analysis.  The proposed algorithm contains a modified element from EI for MAB by suggesting a hybrid of EI with pure exploitation. The paper adds different insights to the body of literature in that EI is an understudied technique to handle the tradeoff between exploration and exploitation in contextual bandits. They propose two novel EI-based algorithms for this problem, one for linear payoff and deep neural networks.  The authors provide numerical experiments.", "questions": " Explanations for modifying EI by mixing with pure exploitation is not convincing.  If the EI value is small, that means the posterior variance is small, which will pick greedily anyway.  Is it necessary?  Also, what is the regret upper bound without the modification? \n\nDo authors have experiments comparing TS and LinEI in terms of d?  ", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nThe paper adds different insights to the body of literature in that EI is an understudied technique to handle the tradeoff between exploration and exploitation in contextual bandits. \n\nEI can be viewed as a variation of TS, and in that respect, the proposed algorithm improves the upper bound of TS by \\sqrt{d}.\n\nWeakness:\n\nExplanations for modifying EI by mixing with pure exploitation are not convincing.  \n \nWhy should one use the proposed algorithm over LinUCB since it carries extra \\sqrt{log T}?\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "36IStlUJPZ3", "reviewer": "Reviewer_KPAe", "summary": "The expected improvement (EI) is a classic approach to select the action in Bayesian optimization (BO). This paper extends EI to the contextual bandit setting, including the linear setting and non-linear setting. Based on the fact, the analysis of EI is not well studied, this paper provides the regret analysis of EI in linear contextual bandit and neural contextual bandit. Moreover, authors show good empirical results proposed algorithm.\n\nenecccdejhvddktidjggvrltrghcivbtjdnlekdkejtc\n", "questions": "(1) LinEI and NeuralEI, look like the expected version of TS, adding expectation over the sampled reward. Please author convince me of the significant difference from TS. \n\n(2) Please provide more details about the challenges in the analysis of LinEI and NeuralEI over LinTS and NeuralTS.\n\n", "limitations": ".", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n\nWeakness:\n\n(1) The overall proposed two algorithms, LinEI and NeuralEI,  look very similar to TS to me. Take the linEI as an example. In a round, $r_t^+$ is the same for every arm. So the selection criterion can be considered as $E_{\\mu \\sim N}x^\\top \\mu $, which is the expected version of LinTS. Just add the expectation to the TS. Theoretically, we only need to take the expectation over the normal distribution based on TS. So, I doubt the novelty of the proposed algorithms and their analysis.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2jPMOSg79S7", "reviewer": "Reviewer_s7GF", "summary": "This paper applies the expected improvement (EI) principle to contextual bandits, which contrasts with the more popular approaches of upper-confidence bound (UCB) and Thompson sampling (TS).  For adversarially chosen contexts but realizable (conditional) mean rewards, EI is practically applicable with both linear and neural network predictors.  In the linear case the proposed technique essentially achieves information-theoretic lower bounds given sub-Gaussian residuals.  In the neural case the network tangent kernel can be used to characterize the regret matching analogous results for NeuralUCB and NeuralTS.", "questions": "For clarity state that $\\xi_{a(t),t}$ is mean zero in line 71 (in some works, mean zero is an optional part of the definition of sub-gaussian).  For example, \"... where $h$ is an unknown mean reward function ...\".\n\nI would appreciate some commentary around equation (1) and associated experiments in section 6.1.  For example, compared to equation (1), LinUCB will find the most optimistic value for an arm in an ellipsoid defined by a level set of the posterior, rather than integrating over it.  Thus, relative to LinUCB, LinEI could choose an arm whose maximum optimistic value is lower but for which there are \"more possibilities\" for improvement.  Try to provide similar comparative insight with LinTS.  \n\ntheorem 3.2 and theorem 4.2 have typesetting issues.\n\nThe following combination of statements is confusing:\n  * line 72: ... conditionally R sub-gaussian for some R >= 0 ... \n  * line 230: 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 ...\n  * line 312: 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.\n    * I suspect what you want to say is: \"we've modeled the conditional reward residuals as sub-gaussian; our regret bounds hold for all sub-gaussian residuals; and we want to extend our work to more general residuals such as sub-exponential or sub-gamma.\"  But to be honest, it's a bit unclear.  If my guess is correct, the issue is arguably marginal because: bounded rewards are guaranteed to have sub-gaussian residuals (hence your result is already broadly applicable), and you are already close to the information-theoretic lower bound in Theorem 3.2 (hence you have already squeezed most of the efficiency out of the approach).\n", "limitations": "This reviewer is satisfied.\n\n**Update after author discussion period**:  Authors have addressed concerns, raising score.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths include the novelty of EI in this setting and the connection to NTK theory.\n\nWeaknesses:\n  * the lack of clear motivation for EI.  \n    * is it just \"another way to do contextual bandits that nobody has done yet?\"\n      * if so this paper is likely to be ignored by practitioners.\n    * is it statistically distinct from UCB/TS approaches (i.e., works better)?\n      * in theory no, everybody is achieving the same regret bounds essentially.\n      * in practice, maybe, but that's where the experiments are too limited for a strong conclusion.\n      * one advantage of using older datasets is you can provide exhaustive comparative study as in https://arxiv.org/abs/1802.04064 \n    * is it computationally distinct from UCB/TS approaches (i.e., cheaper to compute or scales better to larger action sets)?\n      * if so you could exhibit on a modern dataset such as amazon-3m from https://arxiv.org/abs/2102.07800\n\nI believe this work would benefit from spending more time better differentiating EI before presenting to the general community, otherwise, it's potential impact will be limited.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept