Improving the Knowledge Gradient Algorithm
Authors: Le Yang
Siyang Gao
Chin Pang Ho
Venue: NeurIPS 2023 poster (2023)
Keywords: best arm identification
knowledge gradient
asymptotic optimality
convergence rate
TL;DR: In this research, we show drawbacks of the knowledge gradient algorithm, a popular police designed for the best arm identification problem,  and propose an improved version of the algorithm that can avoid those drawbacks.

Abstract: The knowledge gradient (KG) algorithm is a popular policy for the best arm identification (BAI) problem. It is built on the simple idea of always choosing the measurement that yields the greatest expected one-step improvement in the estimate of the best mean of the arms. In this research, we show that this policy has limitations, causing the algorithm not asymptotically optimal. We next provide a remedy for it, by following the manner of one-step look ahead of KG, but instead choosing the measurement that yields the greatest one-step improvement in the probability of selecting the best arm. The new policy is called improved knowledge gradient (iKG). iKG can be shown to be asymptotically optimal. In addition, we show that compared to KG, it is easier to extend iKG to variant problems of BAI, with the $\epsilon$-good arm identification and feasible arm identification as two examples. The superior performances of iKG on these problems are further demonstrated using numerical examples.

Improving the Knowledge Gradient Algorithm
Le Yang
Siyang Gao
Department of Systems Engineering City University of Hong Kong 1yang272-c0me wity..tuu...... edu.
Department of Systems Engineering City University of Hong Kong s siyaggaol ei tyu. edu hk
Chin Pang Ho
School of Data Science
City University of Hong Kong clint hw@chtyu.eeu............ooooo...
Abstract
The knowledge gradient (KG) algorithm is a popular policy for the best arm identification (BAI) problem.
built on the simple idea of always choosing the measurement that yields the greatest expected one-step improvement in the estimate of the best mean of the arms. In this research, we show that this policy has limitations, causing the algorithm not asymptotically optimal. We next provide remedy for it, by following the manner one-step look ahead of KG, but instead choosing the measurement that yields the greatest one-step improvement in the probability of selecting the best arm. The new policy is called improved knowledge gradient (iKG). iKG can be shown to be asymptotically optimal. In addition, we show that compared to KG, is easier to extend iKG to variant problems of BAI, with the e-good arm identification and feasible arm identification as two examples. The superior performances of iKG on these problems are further demonstrated using numerical examples.
Introduction
The best arm identification (BAT) is sequential decision problem where in each stage, the agent pulls out of k given arms and observes noisy sample of the chosen arm. At the end of the sampling stage, the agent needs to select the arm that is believed to be the best according to the samples. In this research, we let the best arm be the one with the largest mean. BAI is a useful abstraction of issues faced in many practical settings [1 and has been widely studied in the machine learning community
Since in practical problems, the target arm(s) (to be identified) is not necessarily the best arm, some variant models of BAI have also been proposed in the literature, e.g., top-m arm identification [ 6), Pareto front identification 7. e-good arm identification [ feasible arm identification [9] 10,, etc.
In this research, we focus the fixed-budget BAI, in which the total number of samples (budget) fixed and known by the agent. The goal is to correctly identify the best arm when the budget is used up. To solve this problem, many methods have been proposed, e.g., successive rejects (SR) 4). expected improvements (EI) [Л]] top-two sampling [22 13], knowledge gradient (KG) 15. optimal computing budget allocation (OCBA) [6
17 (8) etc. Among these methods, KG has been prevailing. It was first proposed in [19] and further analyzed in (20) (11) It is built on the simple idea of always pulling the arm that yields the greatest expected one-step improvement in the estimate of the best mean of the arms. This improvement measure is analytical, making the algorithm easily implementable. KG often offers reasonable empirical performances and has been successfully applied in number of real applications [22
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, we observe that this definition of KG has limitations, causing the algorithm not asymptoti- cally optimal. Here by not being asymptotically optimal, we mean that the KG algorithm is not rate optimal, in the sense that the probability of the best arm being falsely selected based on the posterior means of the k arms does not converge to zero at the fastest possible rate. This is resulted from KG allocating too few samples to the best arm and excessive samples to the remaining arms. Note that Frazier et al. [20] claimed that KG is "asymptotically optimal", but in their context, "asympiotically optimal" is consistent, i.e., all the arms will be infinitely sampled as the round n + oo, that the best arm will be correctly selected eventually. This is a relatively weak result for BAI algorithms (the simple equal allocation is also consistent). In this paper, asymptotically optimal refers to rate optimal.
Contributions. We propose a new policy that can overcome this limitation of KG. The new policy follows the manner of one-step look ahead of KG. but pulls the arm that yields the greatest one-step improvement in the probability of selecting the best arm. We call improved knowledge gradient (iKG) and show that it is asymptotically optimal. This policy is originated from the thought of looking at whether the best arm has been selected at the end of sampling, instead of looking at the extent that the mean of the selected arm has been maximized. Although both ways can identify the best arm, it turns out that the algorithms developed from them are significantly different in the rates of posterior convergence. Another advantage of iKG over KG is that iKG is more general and can be more easily extended to variant problems of BAL We use e-good arm identification and feasible arm identification as examples, develop algorithms for them using the idea of iKG and establish asymptotic optimality for the algorithms.
This paper is conceptually similar to [2 which improves the El algorithm for BAI However, for EI, sampling ratios of any two arms the non-best set are already asymptotically optimal. One only needs to introduce parameter ,3 to balance the probabilities of sampling the best arm and the non-best set without changing the sampling policy within the non-best set to further improve EL. For KG, sampling ratios are not asymptotically optimal for any two out of the & arms. It requires a fundamental change on the sampling policy that influences the sampling rates of all the arms to improve KG. Moreover, the improved rate of posterior convergence of El in [22 still depends on B which is not necessarily optimal, while we can show that this rate of iKG is optimal.
2 Knowledge Gradient and its Limitations
In this section, we review KG and discuss its limitations. Suppose there are k arms in BAI In each round f, the agent chooses any arm i pull and obtains noisy sample X,-1,i- After rounds, the agent needs to select an arm that he/she believes to be the best. Under the framework of the KG algorithm, X,+1,''s 's are assumed be independent across different rounds and arms and following the normal distribution (i,, of) with unknown means μ4, and known variances of. The best arm is assumed to be unique. Without loss of generality, let ((1) > ((2) 2 ... 2 paay. where (t) indicates the arm with i-th largest mean.
The KG algorithm can be derived from a dynamic programming (DP) formulation of BAI The state space S consists of all the possible posterior means and variances of the arms, denoted as S & R x (0, ) State S, in round can be written as S, = (H4, Mr,2. Hr,k, of 0?, ........ In the Bayesian model, the unknown mean μ4 is treated as random and let 6, be the random variable following its posterior distribution. We adopt normal distribution priors A (Ho, o. With samples of the arms, we can compute their posterior distributions, which are still normal N(H,,, of,) in round by conjugacy. The posterior mean and variance of arm i are
of,)) . T.
0 i + 0, -2 2X
if =
if Ie i,
P
0,1 + 0,
and 22
01i t
(1)
if 4 + i,
2 of
if I + i.
In this paper, we adopt a non-informative prior for each arm i. E A. i.e., Mo.1 = 0 and 0o. = 00.
Denote the action space as A - (1.2.....k)) k} and transition function as T 2 S x A X + S. Suppose Or,, is a random variable following the posterior distribution N( o?) ) of arm Then, the
state transition can be written as S T(St, i, 0t.z). Let be the sampling policy that guides the agent to pull arm 7, round and be the set of sampling policies π = =(o.. J,...., In-1) adapted to the filtration Lo. Xo. 4,,1, After rounds, the estimated best arm I is selected
2

---

and terminal reward Uy (S,) is received. We can write our objective as
sup Ex Un (S,).
(2)
The DP principle implies that the value function in round 0 S t < can be computed recursively by max () 0c,)) E
Uy (5)) -
FER
We define the Q-factors as and the DP principle tells us that any policy satisfying
(s, & E (T(S, (,,))). S Se
Tx(S) E argmax Qr(S, S
iEA
is optimal. However, the optimal policy is basically intractable unless for problems with very small scales, known the "curse of dimensionality".
On the other hand, note that except the terminal reward vn (S,). this problem has no rewards in the other rounds,
restructure U, (S,) as telescoping sequence
Un (S.)) = (S,) un (1)] +... (Sx(()+)) - v, +
Thus, (S.)) can be treated as the cumulation of multiple one-step improvements (.,) vn (S 1= I + +l..... n. class of one-step look ahead algorithms iteratively pull the arm that maximizes the expectation of the one-step improvement on the value function
E E/ (T i, (r,)) - (S.)).
These algorithms are not optimal in general unless there is only one round left, i.c., n = t 1.
The KG algorithm falls in this class. It sets the terminal reward as u, (S,) pzg- With this reward, the one-step improvement in becomes
KG E[max ( Oc,i), maxxu," max M4,s)
s'pi
AEA
and in each round, the KG algorithm pulls the arm l((S:) E argmaxtea KG
Algorithm 1: KG Algorithm
Input: k 2 2,
Collect no samples for each arm é;
2 while & < n do
Compute KG,,, and I, argmax, KG
Play Is;
Update M1+1, and 0141,55
Output: I
We next characterize for the KG algorithm the rate of posterior convergence of P(I; = -'*, the probability that the best arm falsely selected.
( - (/ (ra) - P:2y -ag))/ (/o
Proposition 1. Let c(j)
2, ..., k. For the KG algorithm,
_
lim
log((1 - P(1;- =13] KG
==000
n
where
(mn) 111i)² 2((E (22//00) + t )o + cu) o Ezes 1/c(0) + to of
KG
min
We observe that KG is not optimal. To make this point, Proposition 2 gives an example that KG is no better than this rate of the TTEI algorithm [12 when the parameter 3 (probability of sampling the best arm) of TTEI is set to some suboptimal value.

---

Proposition 2. For the TTEI algorithm (12,, the rate of posterior convergence of 1 - - = = ex- ists and is denoted I I Let its probability of sampling the best arm 3 (0 Eit1 1/
1) We have k < 1TTE!
According to the proof of Proposition 2 there are configurations of the BAI problem leading to r < I' i.e., LKG is not optimal. In fact, with 3 = (0(2)/ (01) Eipt 1/0(y +1) kKG TTEI achieved only in some special cases, e.g., when h: =
3 Improved Knowledge Gradient
In this section, we propose an improved knowledge gradient (iKG) algorithm. We still follow the manner of one-step look ahead of KG, but the terminal reward of problem (2) (S,) 1 = }. That is, for the goal of identifying the best arm, we reward the selected arm by a 0-1 quantity showing whether this arm is the best arm, instead of the mean of this arm (as KG).
In this case, (( = P } where
PP = 13 = p
n (0s;
> 0.) = -1-P P U (00.)010)
However, the probability P
(0, 01:) in 4 does not have an analytical expression. To 1
U
facilitate the algorithm imple implementation and analysis, we adopt approximation to it using the Bonferroni inequality 24:
P U Σ
P(O, 0r:);
and ([v)) can be approximately computed
(Un, - Mn,1,) )²
E(u 1 P(00>00:)
01:)
Σ exp if
(5)
2(o",, oi.
Note that the Bonferroni inequality has been adopted as an approximation of the probability of correct selection in the literature for development of BAI algorithms [16]. For our purpose, we can show that the use of this approximation still makes the resulting algorithm asymptotically optimal and empirically superior.
Algorithm 2: iKG Algorithm
Input: A >
Collect no samples for each arm i;
while t < n do
3
Compute iKG,,; and set J = argmax iKG
Play It;
Update 1441,6 O1+1, and 1;
Output: T
Let iKGr,; be the one-step improvement in B with I; treated unchanged after more sample and EE[r, (S.)) approximated by (5. We have the following proposition to compute iKG,, The iKG algorithm pulls the arm with the largest iKGr, in each round.
Proposition 3. With the definition of iKGr, above, we have
(mes )2.1;)2 - exp 2 + +
(H4, 11,1;)
exp
2( + to + 2
ii
iKG..
(- ([(Me - -,,11;
(Me. -2(0, + +ot.17)
(urs5 M|, )2
Σ exp
Σ exp 8+1
fi= 1.
22 + +ot + + (ož /
77, 12)
(6)

---

Both KG and iKG are greedy algorithms that look at the improvement only one ahead. The essential difference between them on the reward they use for the event of best arm identification. For KG, it is the mean of the arm selected, while for iKG, it is a 0-1 quantity showing whether the best arm is selected. It is interesting to note that the choice between these two rewards has been discussed in the control community for optimization of complex systems, known as cardinal optimization (similar to KG) vs. ordinal optimization (similar to iKG) [25), with the discussion result in line with this research, indicating that ordinal optimization has advantages over cardinal optimization in the convergence rates the optimization algorithms [26).
Theorem 1. For the iKG algorithm, lim +00 log(1 P(T M) IK where
(P() ((11))2
PIRG
2) /w() + d(ts/was))
and w, is the sampling rate of arm satisfying
k
w
k
(min) M(1 )² 2 /w10 + of /(11))
(1UP) ((1) )
Σ
w 1,
(
and
i 1' +
2/0 ((() + o w (1))))
(8)
In addition, for any BAI algorithms,
sup
log(1 - PP = -1}) < T
22-00
n
Theorem 1 shows that the rate of posterior convergence LikG of the iKG algorithm is the fastest possible. We still use TTEI example. This theorem indicates that I < r for any E (0, 1) and the equality holds only when ,3 is set to S", where 3* is the optimal value of / and is typically unknown.
4 Variant Problems of BAI
Another advantage of iKG over KG is that iKG is more general, in the sense that can be easily extended to solve variant problems of BAL In the variants, the target arms to be identified are not the single best arm, but no matter how the target arms are defined, one can always look at the event that whether these arms are correctly identified at the end of sampling and investigate the probability of this event to develop iKG and the algorithm. In contrast, it is difficult to extend KG to identify arms that cannot be found through optimizing means of these (and/or other) arms. In this section, extend iKG to two BAI variants: e-good arm identification [ and feasible arm identification [[O]. We develop algorithms for them and establish their asymptotic optimality. Note that in these two variant problems, the target arms need to be found by comparing their means with some fixed values. In such cases, the idea of KG is not straightforward.
4.1 e-Good Arm Identification
We follow the notation in Sections and For the is arms, suppose ((1)) 2 (:2) 2 ... 2 (() Given e >> 0, the e-good arm identification problem aims to find all the arms i with (1) > H(1) - e. ie.. all the arms whose means are close enough to the best (c-good). Assume that no arms have means lying on M(1;
Denote the set of c-good arms as G and the estimated set of c-good arms after n rounds as G We set the terminal reward (S.) = 1[G = Go), J, i.c., whether the set G is correctly selected. Then, (Sw)) P(G,, = G),, where
max 02 e) n n (0, < max0, - } i' F'EA
P(G G*} =P
(0,
E'E
SEG;
iEA
max 0, -
-1-P (0+ < max0, 02-
U (0
i'Eh
i'EA
iEGs
iEAYOs
Again, applying the Bonferroni inequality, P(G. = G*) 1-
Σ
P(0
< max 02 -) -)) Σ
P(O, > max 02 - c).
(9)
ek
NEGs
iEAROE
5

---

Let , be the one-step improvement in 3 with I treated as unchanged after one more sample and E(c,,S.,) approximated by the right-hand side of We have the following proposition to compute iKG
Proposition 4. With the definition of ikG above, we have
(14, M4,1, +c2²
(4.5 M1 + c)2
exp
2(07, + +r.11))
-exp
exp
2(02-1,1 + oi,; + 07
fi+
iKG
(Mo, Me.17 + 6)2
(Me Ma +c²
Σ exp F
Σ exp
fi=
2 + oo,12)
(2(0% + + + t 1, (10)
Algorithm 3: iKG- Algorithm (e-good Arm Identification)
Input: k 2 2,
Collect no samples for each arm i;
while ( < n do
Compute iKG; and set 4 = argmax iKG
Play It;
Update 14+1,6 1441 and 1
Output: G
To identify the e-good arms, the iKG-c algorithm pulls the arm with the largest iKG in each round. For this algorithm, we can show that the rate of posterior convergence of P(G; = G*3 the fastest possible.
Theorem 2. For the iKG-c algorithm, limn- log(1 P(G = G r where
(1() M(1 cc²
1
(11)
2(07,) /w(s) + /
and w; is the sampling rate of arm satisfying
k
(M() M() + E)² 2 /ww + ozy, /waa))
(m M()) + t)²
Σ
w
and
2 /w() + ozy /waaa))
i i' #1.
(12)
In addition, for any c-good arm identification algorithms,
sup 2-000
log(1 PPGG, =G]) ST.
n
4.2 Feasible Arm Identification
In the feasible arm identification, samples from pulling arms are m-dimensional vectors X.+1,1 [X++1,0,- ............. ... X1+1,im]
instead of scalars, where each dimension of the vector corresponds some measure of the system performance and X(+1,6 is the observation associated with arm and measure Suppose X1+1.5y 's follow the normal distribution with unknown means μ4j and known variances oly- We impose constraints Pij S % arms i = 1, .., k and measures j = 1,2, m. The find the set of feasible arms S², Let the estimated
of feasible arms after n rounds be S and S = A \ S² We assume that X are independent across different rounds and measures j, and pay do not lie the constraint limits 7j. To facilitate the analysis, also define for round the set of measures El, A {j Pe,is S % satisfied by arm and the set of
goal of this problem
measures EZ,- A ij Pt,y 7r violated by arm i.

---

Set the terminal reward Uú (Sp) = 1 =, i.e., whether the set S' is correctly selected. Then,
El P s'} where
P(S = ( = n
( 23)5
n
(U(e,>1))
>
j=1
( > >
(0i S ?3)) }
= =1-
n
:ES!
/=1
iES? 1=1
Applying the Bonferroni inequality,
P(S =
P(O.j 75)- Σ II
P(O.; $ n5).
(13)
iES,
iES JES,
The inequality holds because Ileeet P(O S 71)) 1
Let iKG,, be the one-step improvement in 3 with S S and E,, treated as unchanged after one more sample and E/u, (S,)) approximated by the right-hand side of 13). We have the following proposition to compute iKG,,
Proposition 5. With the definition of iKG,, above, we huve
m
(3) 185-4e 14,3i) (3a-))))) 1 E (iES::)
(3) - p1,ii) )2
1/1 E 5! ((iEs)) )
iKG =
Σ
exp - ( + o. 141.j /0, 12))2)
1,6
exp
207,1j
j=1
(7j Mr.ii) )
exp (- (- [-E
(7) Mt.ij) )2
lf 87
+ exp
1fi E
20
2 oi ( 04 /o
jEE
jEEt
(14)
Algorithm 4: iKG-F Algorithm (Feasible Arm Identification)
Input: l: 2 2, n
Collect no samples for each arm i;
2 while f < n do
Compute iKG, and I, argmax,ea.KG..
Play Ie:
Update 14+1, 0441,6 S Si+1 Et and E7
Output: S
To identify the feasible arms, the iKG-F algorithm pulls the arm with the largest iKG,, in each round. For this algorithm, can show that the rate of posterior convergence of P(S), S } is also the fastest possible.
Theorem 3. For the iKG-F algorithmm lim log(1 - -P(S) = =51}) = -F, where
(7, - p:y) liE wi Σ
(7, - -1;)² 1fi E S2)
P== W. min JEL!
(15)
20
20
JEE7
and wi the sampling rate of arm satisfying
mc = 1
(7i mey )2
(7/ 125)2
min JEE!
20
1li S + w; Σ
20
1 S²)
(16)
jEE
( )2
(7)
(7-- 1r;)²
wy min
1fi0 st + wy
Σ
1f1 S²), i#1.
jEE),
20%
20
JEE
7

---

In addition, for any feasible arm identification algorithms
Tim sup
log(1
TP(S, =S! s r
n-000
71
Numerical Experiments
In this section, show empirical performances of the iKG, iKG and iKG-F algorithms synthetic and real-world examples. For the best arm identification problem, we compare iKG with the following algorithms.
Expected Improvement (EI) 11 This another common strategy for BAL, In each round, it pulls the offering the maximal expected improvement over the current estimate of the best mean of the arms.
Top-Two Expected Improvement (TTEI) [2]. This is a modification of the EI algorithm by introducing parameter B to control the probabilities of sampling the best arm and the non-best set. We set the parameter 3 in TTEI as its default value 1/2.
Knowledge Gradient. This is the algorithm under study in this research.
For the e-good arm identification problem, we compare iKG-e with the following algorithms.
APT Algorithm 277. is fixedbbudee algorithm for identifying the arms whose means are above given threshold. We set the input tolerance parameter as 0.0001 and the threshold as the posterior mean of the estimated best arm minus 6.
(ST)² Algorithm g It is fixed-confidence algorithm for e-good arm identification. It pulls three arms in each round, the estimated hest arm, one arm above the threshold and one arm below the threshold. We set the input tolerance parameter as 0.0001 and 7 O.
For the feasible arm identification problem, we compare iKG-F with the following algorithms.
MD-UCBE Algorithm 110 This is a fixed-budget algorithm for feasible arm identification based on the upper confidence bound. We set the input tolerance parameter as 0.0001 and hyperparameter a =
25 n where H is a constant that can be computed. Katz-Samuels 36 H
and Scott [10 showed that with a optimal.
the performance of MD-UCBE is nearly 36 H
25 n
MD-SAR Algorithm 10] This is fixed-budget algorithm for feasible arm identification based on successive accepts and rejects. We set the input tolerance parameter as 0.0001.
In addition, iKG, iKG- and iKG-F will be compared with the equal allocation, where each arm is simply played with the same number of rounds. It is naive method and is often used as a benchmark against which improvements might be measured.
The examples for testing include three synthetic examples, called Examples 1-3, and three real examples, namely the Dose- find-iin Problem, Drug Selection Problem, and Caption Selection Problem. For Example 1-3 and the Dose-Finding problem, samples of the arms are two-dimensional. We call the measures of them measures 1 and 2. When the examples identification and e-good identification, only measure I will be used for identifying good/best arms. identification, both measures will be used for
tested for the best arm
When the examples tested for the feasible feasibility detection. For the Drug Selection and Caption Selection problems, samples of the arms are one-dimensional. They are tested for the best arm identification, e-good identification and feasible arm identification.
Synthetic Datasets. We consider three examples, all containing ten arms.
Example The means measure of the ten arms are 0.1927, 0.6438, 3.0594, 3.0220, 1.3753, 1.4215, 0.9108, 1.0126, 0.1119 and 1. 1.8808, and the means in measure 2 of the ten arms are 0.4350, 0.7240, 1.1566, 0.8560, 3.4712, 0.8248, 3.8797,1.98 19819, 3.2431 and 1.4315, all which are uni- formly generated in (0, 4). Samples of the arms are corrupted by normal noises (0, 1). The best arm is arm and 0. -goodd arms are arms 3 and 4. For the feasible arm identification, we choose arms with means in both measures less than 2. Then the feasible arms are arms 1, 2, 6, 8 and 10.
8

---

Example 2. We keep the setting of Example 1. Distributions of the noises for arms 1-5 are changed to 10, 4).
Example 3. Consider functions y: (1) = -0.05a2, (2((0) = - -0.06(7 - x)) and ya(x) = 0.06(a æ 6).
The means in measure of the ten arms are yn (1) with x: 1,2, ..... 10. The means in measure 2 of the ten arms are (2( with z = 1.... 6 and ya (z) with I = 7, 10. Noises follow the normal distribution (0,0 1). The best arm is arm and 0.5-good arms are arms 1-3. For the feasible arm identification, we choose arms with means in measure 1 greater than -0.5 and means in measure 2 less than The feasible arms are arms 1-3.
Dose-Finding Problem. We use the data in [28] (see ACR50 in week 16) for treating rheumatoid arthritis by the drug secukinumab. There are four dosage levels, 25mg, 75mg, 150mg, and 300mg, and a placebo, which are treated as five arms. We develop a simulation model based on the dataset. Each arm is associated with two performance measures: the probability of the drug being effective and the probability of the drug causing infections. The means of the five arms are μ4l = (0.151, 0.259), 42 = (0. 184, 0.184), J43 (0.209, 0.209), M4 (0.171, 0.293) and 14 (0.06, 0.16). Samples of each arm are corrupted by normal noises (0, 0.25). The best arm is arm 3 and the 0.03-good arms are arms 2 and 3. For the feasible arm identification, we find the arms whose probability of being effective is larger than 0.18 and the probability of causing infections is less than 0.25. The feasible arms are arms 2 and 3.
Drug Selection Problem. We consider five contraceptive alternatiees based on the Drug Re- Ethinyl estradiol / levonorgest, Ethinyl estradiol / norethindro, Ethinyl estradiol / norgestimat, Etonogestrel and Nexplanon, which can be treated as five arms. The dataset provides user reviews the five drugs along with related conditions and ratings reflecting overall user satisfaction. We set the means of the five arms as f1 5.8676, p2 = 5.6469, #4 5.8765, μ4 5.8298 and μa 5.6332, and the variances of the five arms as of 3.2756, oz = 3.4171, o3 = 3.2727, of = 3.3198 and o = 3.3251, all calculated by the data. When this example is used for the best arm identification and e-good arm identification, the best arm (with the highest user satisfaction) and 0.003 -ood arm are both arm (Ethinyl estradiol / norgestimat). When this example is used for feasible arm identification, we will select the drugs whose ratings are over 5.6, and the feasible arms are arm 1 (Ethinyl estradiol / levonorgest), arm 2 (Ethinyl estradiol / norethindro), arm 3 (Ethinyl estradiol / norgestimat), arm 4 (Ftonogestrel) and arm (Nexplanon).
view Dataset hhttss//doi.orr/11000 htgg//0.2432/C55SK6
Caption Selection Problem. We aim to select good captions based on the New Yorker Cartoon Caption Contest Dataset (https::/nextml http:://neetll.ggttuu.iie. htt.://///ccpccneeestsiee
In the contests, each caption can be treated as an arm. The dataset provides the mean and variance of each arm, which can be used to set up our experiments. We will test contests 853 (Caption 853) and 854 (Caption 854).
In Caption 853, we randomly select ten captions as arms. We set the means of the ten arms as #1 = 1.1400, #22 1.0779. μ 1.4160, μ4 1.0779, μB = 1.1081, μr 1.1467, M7 1.1333. Mg 1.1075, Ag = 1.1026 and μı00 = 1.4900, and the variances of the arms as o = 0,1418, 2 = 0.0991, 33 0.4871, of = 0.0728, of 0.0977, of 08190, of 0.1843, og 0.0970, o = 0.0932 and o0 = 0.4844, which are all calculated by the data. When this example is used for the best arm identification, the best arm (with the highest funniness score) is arm 10. When this example is used for c-good arm identification, the 0.1-good arms are arms 3 and 10. When this example is used for feasible arm identification, we will select the captions whose funniness scores are over 1.4, and the feasible arms are arms 3 and 10.
In Caption 854, also randomly select ten captions arms. We set the means of the ten arms as #1 = 1.1986. #2 = 1.1890, μ3 = 1.1400, μ1 = 1.2621, μs = 1,1544, μg = 1.0339, #7 = 1.1349. 4g 1.2786, Ag 1.1765 and 1ı0 1.1367, and the variances of the arms as of 0.1879.
Table 1: Prohabilities of false selection for the tested algorithms in best identification problem.
Example
Exumple
Example 2
Example 3
Dose-
Drug Selection
Caption 853
Caption 854
Sample size
Algorithms
1000
5000
4400
18000
400
1000
1200
13000
2400
98000
1600
3000
12000
18000
Equal Allocation
0.38
0022
0.44
0.31
0.25
0.13
0.35
0.05
0.43
0.27
0.17
0.11
0.26
0.18
El
0.36
0.21
0.40
0.28
1.288
0.22
0.46
0.21
0.46
0.37
0.14
0.12
0.26
0.23
BAI
TTEI
0.25
0.07
0.32
0.09
0.13
0.02
0.31
0.03
0.55
0.28
0.04
0.01
0.10
0.06
KG
0.29
0.14
0.32
0.13
0.14
0.03
0.40
0.03
0.44
0.28
0.04
0.11
0.05
IKG
0.21
0.03
0.23
0.03
0.09
0.01
0.29
0.01
0.38
0.23
0.02
0.00
0.07
0.04

---

Table 2: Prohabilities of falke selection for the tested al algorithms e-good arm identification problem.
Example
Example
Example 2
Example
Dose-finding
Drug Sclection Caption 853
Caption 854
Sample size
1000
4000
2400
12000
400
4000
1600
6000
2600
90000
4000
10000
9400
15000
Algorithms
Equal Allocation
0.54
0.20
0.65
0.28
0.61
0.26
0.46
0.18
0.62
0.37
0.28
0.19
0.14
0.05
APT
0.28
0.17
0.25
0.72
0.49
0.56
0.53
0.74
0.70
0.41
0.35
0.48
0.49
e-good
(ST)*
0.29
0.07
0.35
0.11
0.51
0.06
0.38
0.17
0.64
0.34
0.21
0.10
0.12
0.04
iKG+
0.03
0.29
0.448
0.03
0.34
0.60
0.27
0.10
0.02
0.11
0.03
Table Probabilities of false selection for the tested algorithms in feasible amn identification problem.
Example
Exumple
Example 2
Example
Dose-finding
Drug Selection
Caption 853
Caption 854
Sample
Algorithms
3400
11000
4800
14000
2200
4800
2000
4000
100000
140000
4000
10000
30600
44000
Equal Allocation
0.34 0.26
0.33
0.23
0.22
0.14
0.22
0.18
0.03
0.03
0.36
0.29
0.18
0.07
MD-UCBE
0.27
0.16
0.33
0.26
0.05
00.01
0.200
0.17
0.06
0.06
0.32
0.15
0.06
0.04
feasible
MD-SAR
0.74
0.33
0.68
0.22
0.30
0.03
0.79
0.55
0.06
0.02
0.58
0.19
0.08
0.05
IKG-F
0.23 0.02
0.24
0.01
0.04
0.00
0.14
0.01
0.01
0.01
0.20
0.07
0.05
0.00
of = 0.2279, o3 0.1346, oa = 0.3186, of 0..114, of = 0.0330, o3 0.1337, o3 = 0.3167, 3 0.1858 and ou 0.1478, all calculated by the data. When this example is used for the best arm identification, the best arm is arm 8. When this example is used for c-good arm identification, the 0.05-good arms are arms 4 and 8. When this example is used for feasible arm identification, we will select the captions whose funniness scores are over 1.25, and the feasible arms are arms 4 and 8.
dg
For the tested algorithms, probabilities of false selection (PFS) are obtained based on the average of 100 macro-replications. Tables 1-3 show the PFS of the algorithms under some fixed sample sizes (additional numerical results about the PFS and sampling rates of the tested algorithms provided in the Supplement), The proposed iKG, iKG-e and iKG-F perform the best. For the best arm identification, El tends to allocate too many samples to the estimated best arm, leading to insufficient exploration in the remaining arms, while KG tends to allocate too few samples to the estimated best arm, leading to excessive exploration in the remaining arms. TTEI always allocates approximately one-half budget to the estimated best arm when 3 = 1/2,, leading to the budget not being the best utilized. For the e-good identification, APT and (ST)² are inferior because the former insufficiently pulls the estimate best arm, leading to inaccurate estimates of the threshold, while the latter falls in the fxed-confidence regime that focuses on making guarantees on the probability of false selection instead of minimizing it. For the feasible arm identification, both MD-UCBE and MD-SAR allocate too many samples to the arms near the constraint limits. For the three problems, equal allocation performs the worst in general, because it does not have any efficient sampling mechanisms for identifying the target arms in these problems.
6 Conclusion
This paper studies the knowledge gradient (KG), a popular policy for the best arm identification (BAI). We observe that the KG algorithm is not asymptotically optimal, and then propose remedy for it. The new policy follows KG's manner of one-step look ahead, but utilizes different evidence to identify the best arm. We call it improved knowledge gradient (iKG) and show that it is asymptotically optimal. Another advantage of iKG is that it can be easily extended to variant problems of BAI We use e-good arm identification and feasible arm identification as two examples for algorithm development and analysis. The superior performances of iKG on BAI and the two variants are further demonstrated using numerical examples.
References
[1] D. A. Berry. Modified two-armed bandit strategies for certain clinical trials. Journal of the American Statistical Association, 73(36)):339-345, 1978.
[2] A. Gilotte, C. Calauzènes, T. Nedelec, A. Abraham, and S. Dollé. Offline a/b testing for recommender systems. In Proceedings of the 11th ACM International Conference on Web Search and Data Mining, pages 198-206, 2018
10

---

[3] E. Even-Daa S. Mannor, Y. Mansour, and S. Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(6). 2006.
[4] J.-Y. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi- aemiid bandits. In 23rd Conference on Learning Theory, pages 41 41-53, 2010.
[5] Bubeck, Wang, and N. Viswanathan. Multiple identifications in multi-armed bandits. In International Conference on Machine Learning, pages 258-265. PMLR, 2013.
[6] H. Xiao and S. Gao. Simulation budget allocation for selecting the top-m designs with input uncertainty. IEEE Transactions on Automatic Control, 63(9):317--3132 2018.
[7] P. Auer, C. K. Chiang, R. Ortner, and M. Drugan. Pareto front identification from stochastic bandit feedback. In Artificial Intelligence and Statistics, pages 339-947. PMLR, 2016.
[8] B. Mason, L. Jain, A. Tripathy, and R. Nowak. Finding all e-good arms in stochastic bandits. Advances in Neural Information Processing Systems, 33:20707-20711 2020.
[9] S. Gao and W. Chen. Efficient feasibility determination with multiple performance measure constraints. IEEE Transactions on Automatic Control, 12(1)2113-122, 13-122, 2016
[10] Katz-Samuels and C. Scott. Feasible arm identification. In International Conference on Machine Learning, pages 2535-2545 2543. PMLR, 2018.
[11] S. E. Chick, J. Branke, and C. Schmidt. Sequential sampling to myopically maximize the expected value of information. INFORMS Journal on Computing. 22(1):71-80, 2010.
[12] C. Qin, D. Klabjan, and D. Russo. Improving the expected improvement algorithm. In Proceedings of the s1 International Conference on Neural Information Processing Systems, pages 5387-5397, 2017.
[13] D. Russo. Simple Bayesian algorithms for best arm identification. Operations Research, 68(6) 2020.
[14] I. O. Ryzhov, P. I. Frazier, and W. B. Powell. On the robustness of a one one-period look-ahead policy in multi-armed bandit problems. Procedia Computer Science, 1(1):6635-166 2010.
[15] Y. Li and S. Gao. On the finite-time performance of the knowledge gradient algorithm. In International Conference on Machine Learning, pages 12741-12764. PMLR, 2022.
[16] C. H. Chen, Lin, E. Yücesan, and E. Chick. Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynamic Systems, 10:251-270, 2000.
[17] Gao, Chen, and I.. Shi. new budget allocation framework for the expected opportunity cost. Operations Research, 65(3):787-803, 2017.
[18] Y. Li and S. Gao. Convergence rate analysis for optimal computing budget allocation algorithms. Automatica, 153:11 2023.
[19] S. Gupta and K. Miescke. Bayesian look ahead one stage sampling allocations for selecting the largest normal mean. Statistical Papers, 35(1):169-11) 1994.
[20] P. I. Frazier, W. B. Powell, and S. Dayanik. A knowledge-gradient policy for sequential information collection. SIAM Journal Control and Optimization, 47(5):4400-2499 2008.
[21] P. Frazier, W. Powell, and S. Dayaník. The wewwledge-gradieee policy for correlated normal beliefs. INFORMS Journal on Computing, 21(4):599-6) 613, 2009.
[22] C. Schoppe. Wind and pumped-hydro power storage: Determining optimal commitment policies with knowledge gradient non-parametric estimation. B.Sc. Thesis at Princeton University, 2010.
[23] D. M. Negoescu, P. I. Frazier, and W. B. Powell. The knowledge- -rrdiiet algorithm for sequencing experiments drug discovery. INFORMS Journal on Computing, 23(3)3346-333, 2011.
11

---

[24] J. Galambos. Bonferroni inequalities. The Annals of Probability, pages 577-581, 1977.
[25] Y.-C. Ho, S. Sreenivas, and P. Vakili. Ordinal optimization of deds. Discrete Event Dynamic Systems, 2(1):61-88, 1992.
[26] Y.-C. Ho. An explanation ordinal optimization: Soft computing for hard problems. Informa- fion Sciences, 113(3-4):169-192 1999.
[27] A. Locatelli, M. Gutzeit, and A. Carpentier. An optimal algorithm for the thresholding bandit problem. International Conference on Machine Learning, pages 1690-1698. PMLR, 2016.
[28] M. C. Genovese, P. Durez, H. B. Richards, J. Supronik, E. Dokoupilova, V. Mazurov, J. A. Aelion, S. H. Lee, C. E. Codding, H. Kellner, al. Efficacy and safety of secukinumab in patients with theumatoid arthritis: a phase ii, dose-finding boinle-blind, randomised, placebo controlled study. Annals of the Rheumatic Diseases, 72(6):863 869, 2013.
12


Reviews:
[{"review_id": "8Uip2TN3Uo", "reviewer": "Reviewer_Ye7U", "summary": "The researchers tackle the problem of fixed-budget Best Arm Identification (BAI). Specifically, they observed that typical Knowledge Gradient approaches based on the policy of choosing the step with the best expected one step improvement are not asymptotically optimal. They define a new policy, improved Knowledge Gradient (iKG) that, instead, seeks to improve to create the best one-step improvement in the probability of selecting the best arm. ", "questions": "Can you show comparison algorithms for several other datasets that can duplicate the type of performance seen here? Are there datasets where performance of iKG is worse or not as effective, and can you explain why?", "limitations": "The authors discuss the limitations of KG, but not of their techniques specifically. I think this could be accomplished by showing some contrary datasets or examples.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "iKG has more applicability than standard KG. They specifically show applications to epsilon-good arm identification and feasible arm identification, which KG cannot handle. They show the application of iKG on synthetic and real datasets and the iKG variants perform the best overall.", "weaknesses": "Although I can appreciate the complexity of the numerical examples and the breadth of comparison algorithms for iKG-e and iKG-F, I do not believe there are enough different datasets to talk about the performance generally. The authors should have chosen several datasets of varying natures to show general applicability. It is hard for me to gain a sense of whether these datasets are just lucky examples.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the careful and detailed review and insightful comments. In the following, we provide point-by-point detailed responses.\n\n**Q:** Although I can appreciate the complexity of the numerical examples and the breadth of comparison algorithms for iKG-$\\epsilon$ and iKG-F, I do not believe there are enough different datasets to talk about the performance generally. The authors should have chosen several datasets of varying natures to show general applicability. It is hard for me to gain a sense of whether these datasets are just lucky examples.\n\n**A:** Thanks for the comment. We agree that to better illustrate the empirical performances of iKG-$\\epsilon$ and iKG-F (and iKG), more examples should be tested. During the rebuttal period, we have conducted numerical tests on three additional real examples from two new datasets. Please see our global response for detailed numerical results. We will add these new examples and results to the updated manuscript.\n\n**Q:** Can you show comparison algorithms for several other datasets that can duplicate the type of performance seen here? Are there datasets where the performance of iKG is worse or not as effective, and can you explain why?\n\n**A:** In our first submission, we tested three synthetic datasets and one real dataset, and in all our experiments, iKG performs the best in the compared algorithms. It is probably because iKG is asymptotically optimal while the compared algorithms are not, and this advantage can be inherited by iKG when the number of samples is finite (and small).\n\nAs discussed in our global response, we will compare KG and iKG on three additional real examples in the updated manuscript. It can help us better understand the relative performances of these two algorithms.\n\n**Q:** The authors discuss the limitations of KG, but not of their techniques specifically. I think this could be accomplished by showing some contrary datasets or examples.\n\n**A:** As suggested by the reviewer, in the updated manuscript, we will add three real examples in the numerical experiments. It can help us better understand the relative performances of KG and iKG."}, {"review_id": "G6fcrniQtt", "reviewer": "Reviewer_h3kD", "summary": "The paper considers knowledge gradient (KG) algorithm and its limitations in the best arm identification (BAI) problem. The authors first demonstrate that the KG policy is not asymptotically optimal, highlighting its shortcomings, and then provide the improved knowledge gradient (iKG) policy. The key idea is to select measurements that maximize the one-step improvement in the probability of selecting the best arm, rather than the mean improvement. The paper establishes that iKG is asymptotically optimal, offering a remedy to the limitations of KG. The empirical evidence for the effectiveness of the proposed method is also provided.", "questions": "1. How does the last inequality in Eqn. F.2 hold?", "limitations": "The author has addressed the limitations well.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The theoretical analysis on the KG algorithm on its sub-optimality gap\n2. This work proposed a novel improved KG algorithm with optimality guarantees\n3. Discussion on the variant problems of BAI shows that the proposed iKG method is general and can be used in various scenarios. ", "weaknesses": "1. Some notations are rather unclear, e.g., the definition of subscript $i$ in line 61 is not introduced until line 64, definition of $I_t$\n2. What is the computational complexity comparing with KG? It is beneficial to discuss its relationship with the scale of the problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the careful and detailed review and insightful comments. In the following, we provide point-by-point detailed responses.\n\n**Q:** Some notations are rather unclear, e.g., the definition of subscript $i$ in line 61 is not introduced until line 64, definition of $I_{t}$.\n\n**A:** Thanks for pointing it out. The notation $i$ is the index for the $i$-th arm in the $k$ arms. The notation $I_{t}$ refers to the arm the agent pulls in round $t$. We will explain them when they first appear. We will also improve the notation system and conduct a thorough round of editorial check to improve the readability of the manuscript.\n\n**Q:** What is the computational complexity comparing with KG? It is beneficial to discuss its relationship with the scale of the problem.\n\n**A:** The computational complexities of the iKG and KG algorithms are $O(kn)$ and $O(k^2n)$ respectively, where $k$ is the total number of arms and $n$ is the total number of rounds. Although the two algorithms are based on similar frameworks,\nthe computation of $KG_{t,i}$ is $O(k)$ due to the term $\\max\\{\\mathcal{T}(\\mu_{t,i},i,\\theta_{t,i}), \\max_{i'\\neq i}\\mu_{t,i'}\\}$, greater than that of $iKG_{t,i}$ which is $O(1)$. Therefore, the proposed iKG is actually computationally more efficient than KG and has better scalability for large-scale problems. We will add this discussion to the updated manuscript.\n\n**Q:** How does the last inequality in Eqn. F.2 hold?\n\n**A:** Before Eqn. F.2, with the results in Lines 169 and 177 of the Supplement, we have shown that $|\\mu_{n,i}-\\mu_{i}|<\\delta_{15}$ for any $\\delta_{15}>0$ and $i=1,2,\\ldots,k$. We can find a sufficiently large positive integer $n'$ such that when $n>n'$, $S_{n}^{1}=S^{1}$, $S_{n}^{2}=S^{2}$, $\\mathcal{E}\\_{n,i}^{1}=\\mathcal{E}\\_{i}^{1}$ and $\\mathcal{E}\\_{n,i}^{2}=\\mathcal{E}\\_{i}^{2}$, where $i=1,2,\\ldots,k$ and $j=1,2,\\ldots,m$. Note that $S_{n}^{1}\\cap S_{2}^{2}=\\emptyset$ and $S^{1}\\cap S^{2}=\\emptyset$. If $i\\in S_{n}^{1}=S^{1}$,\n$|iKG_{n,i}^{F}-iKG_{n,i'}^{F}|\\leq2m|\\exp(-w_{i}\\min_{j\\in \\mathcal{E}\\_{n,i}^{1}}\\frac{(\\gamma_{j}-\\mu_{n,ij})^{2}}{2\\sigma_{ij}^{2}})-\\exp(-w_{i'}\\min_{j\\in \\mathcal{E}\\_{n,i'}^{1}}\\frac{(\\gamma_{j}-\\mu_{n,i'j})^{2}}{2\\sigma_{i'j}^{2}})|$$\\leq 2m|\\exp(-w_{i}\\min_{j\\in \\mathcal{E}\\_{i}^{1}}\\frac{(\\gamma_{j}-\\mu_{ij}-\\delta_{15})^{2}}{2\\sigma_{ij}^{2}})-\\exp(-w_{i'}\\min_{j\\in \\mathcal{E}\\_{i'}^{1}}\\frac{(\\gamma_{j}-\\mu_{i'j}+\\delta_{15})^{2}}{2\\sigma_{i'j}^{2}})|$. We have shown \nthat $|iKG_{n,i}^{F}-iKG_{n,i'}^{F}|<\\delta_{18}$ in Line 181. Hence $|w_{i}\\min\\limits_{j\\in\\mathcal{E}\\_{i}^{1}}\\frac{(\\gamma_{j}-\\mu_{ij})^{2}}{2\\sigma_{ij}^{2}}-w_{i'}\\min\\limits_{j\\in\\mathcal{E}\\_{i'}^{1}}\\frac{(\\gamma_{j}-\\mu_{i'j})^{2}}{2\\sigma_{i'j}^{2}}|<\\delta_{19}$ by the continuity of the function $\\exp(\\cdot)$. Similarly, Eqn. F.2 holds if $i\\in S_{n}^{2}=S^{2}$. We will add this explanation to the updated supplement."}, {"review_id": "0Cn8ba7B7K", "reviewer": "Reviewer_2tPM", "summary": "The paper is concerned with the best arm identification (BAI) problem. The main contribution of the paper is the proposal of an improved version of the knowledge gradient algorithm which is also shown to be asymptotically optimal. Moreover, the proposed algorithm is extended to the variant of BAI problem and illustrated on certain applications. ", "questions": "- Can you describe the limitations of the proposed approach, and possibly directions for future research?  \n", "limitations": "No", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The main message and contributions of the paper are clearly stated and demonstrated.  \n- The advantage of the proposed algorithm is theoretically proven, by showing that it is asymptotically optimal. \n- By addressing several variants of the BAI problem, the versatility of the approach is shown, supported by theoretical results. \n- The impact of the proposed method on several applications are shown. \n", "weaknesses": "- The limitations of the proposed method is not discussed\n- The range of the problems the proposed approach can solve might be narrow. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the careful and detailed review and insightful comments. In the following, we provide point-by-point detailed responses.\n\n**Q:** The limitation of the proposed method is not discussed.\n\n**A:** The proposed iKG algorithm improves the KG algorithm to asymptotic optimality. A potential limitation of this research is that, our theoretical development (especially the superiority of iKG over KG) has been established in the asymptotic regime. It is not clear if this result can be extended to the finite-time environment. In fact, it is a common challenge faced by most fixed-budget BAI algorithms, that the finite-time performances are difficult to characterize. \nWe believe that one way to address this issue is to use the numerical test. In our last submission, we compared iKG and KG on three synthetic and one real datasets, and iKG has demonstrated better finite-time performance than KG on all these four examples. In the updated manuscript, we will strengthen the comparison results. Specifically, we will compare iKG and KG on three more real examples: one based on the Drug Review Dataset (https://doi.org/10.24432/C5SK5S) for selecting effective contraceptives, and the other two based on the New Yorker Cartoon Caption Contest Dataset (https://nextml.github.io/caption-contest-data/) for selecting good captions. Please see our global response for more details. These additional real examples will help us better understand the relative performances of iKG and KG.\n\n**Q:** The range of the problems the proposed approach can solve might be narrow.\n\n**A:** We would like to point out that, the setting of this research is common and general. The range of problems that can be solved by the proposed iKG algorithm is actually quite broad. The problems that can be solved by typical BAI algorithms such as KG (Frazier, 2008), EI (Ryzhov, 2016), TTEI (Qin et al., 2017), TTTS (Russo, 2020), etc. can all be solved by the iKG algorithm.\n\nWe believe that one possible reason leading to this concern of the reviewer is that, in our numerical experiments, we only tested the algorithms on one real dataset. In the updated manuscript, we will add three more real examples to the test. Please see our global response for more details. We hope that the new experiments and results can dispel the reviewer's concern about the range of applicability of our algorithms.\n\n**References:**  \nP. I. Frazier, W. B. Powell, and S. Dayanik. A knowledge-gradient policy for sequential information collection. *SIAM Journal on Control and Optimization*, 47(5):2410–2439, 2008.  \nI. O. Ryzhov. On the convergence rates of expected improvement methods. *Operations Research* 64.6 (2016): 1515-1528. \nC. Qin, D. Klabjan, and D. Russo. Improving the expected improvement algorithm. In *Proceedings of the 31st International Conference on Neural Information Processing Systems*, pages 5387–5397, 2017.  \nD. Russo. Simple Bayesian algorithms for best arm identification. *Operations Research*, 68(6):1625–1647, 2020.  \n"}, {"review_id": "YSgoUs6usj", "reviewer": "Reviewer_eJBQ", "summary": "The paper focuses on the fixed-budget best arm identification (BAI) problem, in which an agent aims to correctly identify the best arm (one with the highest mean) among k given arms within a known fixed number of samples. An improved knowledge gradient (iKG) policy is proposed, which prioritizes the arm that maximizes the one-step improvement in the probability of selecting the best arm. The algorithm yields an asymptotically optimal solution, overcoming the limitations of the knowledge gradient (KG) policy that is not rate optimal. The paper also extends iKG to the problem of ε-good arm identification and feasible arm identification examples.", "questions": "Why not comparing iKG with KG, for example in the 'one average' sense? I do understand that one is asymptotically optimal and the other not, but perhaps the cases when KG is not are very rare and thus the choice between iKG and KG would be a wash. \n\nThe datasets are really contrived. Why not getting more real-world data and then tweaking it to fit the purpose? ", "limitations": "NA", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The idea of considering probability instead of expectation is new in this context (even though it has already been used in other contexts). The analyses of extensions is also an added benefit.  ", "weaknesses": "The computational experiments are weak, in particular the choice (more precisely, creation) of datasets bags for more. In short, the experiments are mostly based on synthetic data and some of them come across as very far fetched. \n\nThe concepts are very similar to TTEI which makes the contributions marginal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the careful and detailed review and insightful comments. In the following, we provide point-by-point detailed responses.\n\n**Q:** The computational experiments are weak, in particular the choice (more precisely, creation) of datasets bags for more. In short, the experiments are mostly based on synthetic data and some of them come across as very far fetched.\n\n**A:** Thanks for the comment. We agree that to better illustrate the empirical performances of the proposed algorithms, more examples should be tested. During the rebuttal period, we have conducted numerical tests on three additional real examples from two new datasets. Please see our global response for detailed numerical results. We will add these results to the updated manuscript.\n\n**Q:** The concepts are very similar to TTEI which makes the contributions marginal.\n\n**A:** We agree that in terms of the objective, both TTEI and this paper aim to modify an existing popular BAI algorithm to asymptotic optimality. In fact, we believe that developing (asymptotic) optimal algorithms, either based on new ideas or by improving existing suboptimal algorithms (like in TTEI and this paper), should be the same goal of all BAI (and other) research.\n\nMore importantly, we would like to point out that, how we improve KG to asymptotic optimality is entirely different from that for EI. The iKG algorithm is based on the concept of selecting the measurement that results in the greatest one-step improvement in the probability of choosing the best arm. It gives rise to a completely different acquisition function from KG. It is not just a new idea that can be used to improve KG. It is also an algorithm design framework that can be used for different BAI variant problems, as is shown in the examples of $\\epsilon$-good arm identification and feasible arm identification. TTEI only changes the sampling rate of the best arm of EI. This level of modification to EI is minor compared to the way we modify KG.\n\n**Q:** Why not comparing iKG with KG, for example in the \"one average'' sense? I do understand that one is asymptotically optimal and the other not, but perhaps the cases when KG is not are very rare and thus the choice between iKG and KG would be a wash.\n\n**A:** Now the empirical performances of KG and iKG are based on the average of multiple replications of the algorithms. It is the typical way of reporting and studying the algorithm performances. In the meantime, we appreciate the suggestion of the reviewer. In each replication of the algorithm, due to the uncertainty of the sample path, the relative performances of KG and iKG might deviate from the average pattern. It provides another direction for numerically comparing KG and iKG. From our experience of doing numerical experiments, based on one replication of the two algorithms, if they perform differently, it is highly likely the iKG correctly selects the best arm while KG does not. It is rare to observe the other way. In the updated manuscript, we will report the percentage of the replications when KG correctly selects the best arm while iKG does not, as suggested by the reviewer. We will also discuss the result, seeking to obtain some guidance on choosing between KG and iKG.\n\nOn a related note, as mentioned in our global response, we will strengthen the numerical part of this paper by adding three real examples in the numerical experiments. These additional examples can help us better understand the relative performances of KG and iKG."}, {"review_id": "4XBFDeVJLW", "reviewer": "Reviewer_dyGQ", "summary": "The paper tackles the problem of best arm identification (BAI). The paper introduces \"improved knowledge gradient (iKG)\" that can be shown to be asymptotically optimal. Some numerical results are also provided", "questions": "- In the beginning of Section 2, $i$ refers to the arms and then it is mentioned that $\\sigma_i$ are known variances but then in Equation 1, the sigma is estimated. Can you clarify this?\n\nMinor additional comment:\n- There are few typos/english mistakes: e.g. \"this policy has limitations, causing the algorithm not asymptotically optimal\", \"These algorithms are not optimal in general except there is only one round left\".\n- I know that it is a usual notation to say something like \"$\\mu_1 > \\mu_2 \\ge . . . \\ge \\mu_k$\". But this feels strange as it would (naively seem to) imply that one already knows that the arm i=1 is the best. Is it possible to introduce another notation or do I miss something?\n- Line 70: $\\theta_i$ is defined as \"the random variable following *its* posterior distribution\". Is it the $\\mu$ only or is it for the whole state $S_t$.\n- Line 74: The transition function that depends on two states and one action and deterministically transition to a new state is not entirely clear to me from a formal perspective. $\\theta_{t,i}$ is defined as a random variable following some (posterior) distribution but it is then apparently also a \"state\"? Isn't it a probability distribution over the state space?\n", "limitations": "The limitations are adequately discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The contribution of the paper has an interesting scope of showing limitations of an existing algorithm for best-arm identification (BAI), providing a variant along with theoretical analysis and numerical experiments. The paper also discussed variant problems of BAI making the scope quite large within the multi-arm bandit setting.\nThe paper seem to me scientifically sound and is overall well-written.", "weaknesses": "(minor) Some elements in the formalization, some notations and minor typos could possibly be improved.\n\nDisclaimer: I can't fully assess the novelty as I'm not an expert in the field of the best arm identification problem and I didn't check in details all the proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the careful and detailed review and insightful comments. In the following, we provide point-by-point detailed responses.\n\n**Q:** (minor) Some elements in the formalization, some notations and minor typos could possibly be improved.\n\n**A:** Thanks for the comment. We will conduct a thorough round of editorial check to improve the readability of the manuscript.\n\n**Q:** In the beginning of Section 2, $i$ refers to the arms and then it is mentioned that $\\sigma_{i}^2$ are known variances but then in Equation 1, the sigma is estimated. Can you clarify this?\n\n**A:** In this research, $\\sigma_{i}^{2}$ is the sampling variance of arm $i$ and is assumed to be known. In the Bayesian model, the unknown mean $\\mu_{i}$ is treated as random, and $\\theta_{i}$ is denoted as the random variable following the posterior distribution of $\\mu_{i}$. The term $\\sigma_{t, i}^{2}$ (with subscript $t$, different from the $\\sigma_{i}^{2}$ above) refers to the variance of the random variable $\\theta_{i}$ in round $t$, which needs to be estimated by Eqn. (1). We will make it clear in the manuscript.\n\n**Q:** There are a few typos/english mistakes: e.g. \"this policy has limitations, causing the algorithm not asymptotically optimal\", \"These algorithms are not optimal in general except there is only one round left\".\n\n**A:** Thanks for pointing them out. We will fix them and conduct a thorough round of editorial check and improvement for the manuscript.\n\n**Q:** I know that it is a usual notation to say something like \"$\\mu_{1}>\\mu_{2}\\geq\\ldots\\geq\\mu_{k}$\". But this feels strange as it would (naively seem to) imply that one already knows that the arm i=1 is the best. Is it possible to introduce another notation or do I miss something?\n\n**A:** We agree with the reviewer. In the updated manuscript, we will replace it by \"$\\mu_{\\langle 1 \\rangle}>\\mu_{\\langle 2 \\rangle}\\geq\\ldots\\geq\\mu_{\\langle k \\rangle}$\", with arm $\\langle 1 \\rangle$ being the best arm.\n\n**Q:** Line 70: $\\theta_{i}$ is defined as \"the random variable following its posterior distribution\". Is it the $\\mu$ only or is it for the whole state $S_{t}$.\n\n**A:** The term $\\theta_{i}$ is the random variable for the unknown mean of arm $i$, which follows $\\mathcal{N}(\\mu_{t,i}, \\sigma_{t,i}^{2})$. The  state $S_{t}$ consists of the posterior means and variances of all the $k$ arms in round $t$. We will make it clear in the updated manuscript.\n\n**Q:** Line 74: The transition function that depends on two states and one action and deterministically transition to a new state is not entirely clear to me from a formal perspective. $\\theta_{t,i}$ is defined as a random variable following some (posterior) distribution but it is then apparently also a \"state\"? Isn't it a probability distribution over the state space?\n\n**A:** The agent chooses the measurement that yields the greatest one-step improvement in the probability of selecting the best arm. However, we do not know state $S_{t+1}$ for calculating the probability of selecting the best arm in round $t+1$, so we construct a predictive model to calculate state $S_{t+1}$. We use $\\theta_{t,i}$ (following the normal distribution with posterior mean $\\mu_{t,i}$ and variance $\\sigma_{i}^2$) as the sample of arm $i$ in round $t$. State $S_{t+1}$ is obtained by pulling arm $i$ and generating $\\theta_{t,i}$, and then $\\mathcal{T}(S_t,i,\\theta_{t,i})$ can be computed by Eqn. (1). Hence $\\theta_{t,i}$ is not a \"state\" and is not a probability distribution over the state space either. We will make it clear in the updated manuscript."}]

Author rebuttal:
Multiple reviewers pointed out that the numerical part of this research should be strengthened. During the rebuttal period, we have tested the empirical performances of the proposed iKG, iKG-$\epsilon$ and iKG-F algorithms on three additional real examples from two new datasets. The new test examples and results will be added to the updated manuscript.

The first example is about selecting effective contraceptives based on the Drug Review Dataset (https://doi.org/10.24432/C5SK5S). We consider five contraceptives: Ethinyl estradiol / levonorgest, Ethinyl estradiol / norethindro, Ethinyl estradiol / norgestimat, Etonogestrel and Nexplanon, which can be treated as five arms. The dataset provides user reviews on the five drugs along with related conditions and a $10$ star user rating reflecting overall user satisfaction. We set the means of the five arms as $\mu_{1}=5.8676$, $\mu_{2}=5.6469$, $\mu_{3}=5.8765$, $\mu_{4}=5.8298$ and $\mu_{5}=5.6332$, and the variances of the five arms as $\sigma_{1}^{2}=3.2756$, $\sigma_{2}^{2}=3.4171$, $\sigma_{3}^{2}=3.2727$, $\sigma_{4}^{2}=3.3198$ and $\sigma_{5}^{2}=3.3251$, all calculated by the data. When this example is used for the best arm identification and $\epsilon$-good arm identification, the best arm (with the highest user satisfaction) and 0.003-good arm are both arm 3 (Ethinyl estradiol / norgestimat). When this example is used for feasible arm identification, we will select the drugs whose ratings are over $5.8$, and the feasible arms are arm $1$ (Ethinyl estradiol / levonorgest), arm $3$ (Ethinyl estradiol / norgestimat) and arm $4$ (Etonogestrel).

The second and third examples are about selecting good captions based on the New Yorker Cartoon Caption Contest Dataset (https://nextml.github.io/caption-contest-data/). In the contests, each caption can be treated as an arm. The dataset provides the mean and variance of each arm, which can be used to set up our experiments. Specifically, we will test contests 853 (example two) and 854 (example three).

In example two, we randomly select ten captions as arms. We set the means of the ten arms as $\mu_{1}=1.1400$, $\mu_{2}=1.0779$, $\mu_{3}=1.4160$, $\mu_{4}=1.0779$, $\mu_{5}=1.1081$, $\mu_{6}=1.1467$, $\mu_{7}=1.1333$, $\mu_{8}=1.1075$, $\mu_{9}=1.1026$ and $\mu_{10}=1.4900$, and the variances of the arms as $\sigma_{1}^{2}=0.1418$, $\sigma_{2}^{2}=0.0991$, $\sigma_{3}^{2}=0.4871$, $\sigma_{4}^{2}=0.0728$, $\sigma_{5}^{2}=0.0977$, $\sigma_{6}^{2}=0.1809$, $\sigma_{7}^{2}=0.1843$, $\sigma_{8}^{2}=0.0970$, $\sigma_{9}^{2}=0.0932$ and $\sigma_{10}^{2}=0.4843$, which are all calculated by the data. When this example is used for the best arm identification, the best arm (with the highest funniness score) is arm 10. When this example is used for $\epsilon$-good arm identification, the 0.1-good arms are arms 3 and 10. When this example is used for feasible arm identification, we will select the captions whose funniness scores are over 1.4, and the feasible arms are arms 3 and 10.

In example three, we also randomly select ten captions as arms. We set the means of the ten arms as $\mu_{1}=1.1986$, $\mu_{2}=1.1890$, $\mu_{3}=1.1400$, $\mu_{4}=1.2621$, $\mu_{5}=1.1544$, $\mu_{6}=1.0339$, $\mu_{7}=1.1349$, $\mu_{8}=1.2786$, $\mu_{9}=1.1765$ and $\mu_{10}=1.1367$, and the variances of the arms as $\sigma_{1}^{2}=0.1879$, $\sigma_{2}^{2}=0.2279$, $\sigma_{3}^{2}=0.1346$, $\sigma_{4}^{2}=0.3186$, $\sigma_{5}^{2}=0.1314$, $\sigma_{6}^{2}=0.0330$, $\sigma_{7}^{2}=0.1337$, $\sigma_{8}^{2}=0.3167$, $\sigma_{9}^{2}=0.1858$ and $\sigma_{10}^{2}=0.1478$, all calculated by the data. When this example is used for the best arm identification, the best arm is arm 8. When this example is used for $\epsilon$-good arm identification, the 0.05-good arms are arms 4 and 8. When this example is used for feasible arm identification, we will select the captions whose funniness scores are over 1.25, and the feasible arms are arms 4 and 8.

The three new examples are applied to the three BAI and variant problems for testing, except that Example 1 is not tested for the feasible arm identification due to time limitation. Here we briefly report the results (please see the attachment for more details).

Figures 1(a)-1(c) show how the probabilities of false selection (PFS) of the compared algorithms change with the sample sizes for the best arm identification problem in Examples 1-3. It can be observed that the proposed iKG algorithm performs the best, followed by KG, EI and the equal allocation. On the log scale, the PFS values of the iKG algorithm demonstrate linear patterns, indicating the potentially exponential convergence rates. For both EI and KG, the rates of posterior convergence are not optimal, which might compromise their empirical performances. The equal allocation performs the worst in general.

Figures 2(a)-2(c) show how the probabilities of false selection of the compared algorithms change with the sample sizes for the $\epsilon$-good arm identification in Examples 1-3. It can be observed that the proposed iKG-${\epsilon}$ algorithm performs the best and demonstrates a linear pattern on the log scale. (ST)$^2$ and APT are inferior, and the equal allocation performs the worst.

Figures 3(a)-3(b) show how the probabilities of false selection of the compared algorithms change with the sample sizes for the feasible arm identification in Examples 2 and 3. The results are similar to those in Figures 1(a)-2(c). The proposed iKG-F algorithm has the best performance, followed by the compared MD-UCBE, equal allocation and MD-SAR.

Meta-review: This paper studies best arm identification in multi-armed bandits and proposes an improved version of the knowledge gradient algorithm. It proves asymptotic converge rates that are optimal and which are a strict improvement of the rate of the vanilla knowledge gradient algorithm. The paper further empirically compares the proposed method against baselines on several benchmark problems.

There is consensus that the paper provides a good contribution to the Best Arm Identification problem and the reviewers appreciated the improved convergence rate shown for the proposed iKG variant. Reviewer eJBQ was concerned that the extension in this paper is similar to the TTEI extension for EI. The authors addressed this concern by pointing out the differences. The main concern raised in several reviews is the scope of the experimental evaluation. The authors promised to add 3 additional benchmarks and presented a summary of the results in their rebuttal.

Based on the ACs own reading of the paper and the reviewer discussion, there are however additional issues with the empirical evaluation:
* The results do not show CIs. The authors state that their reported results are averages over 100 replications so the conclusions are probably valid, but uncertainty measures have to be included. The plotted averages in the appendix look somewhat noisy which may suggest that they are not yet converged to the population limit and the CIs may be fairly large, but without actual CIs, that is all speculation.  Statistical confidence quantification (through error bars / confidence regions / p-values) is a must for a NeurIPS paper in 2023. In fact, the authors did not fill out that part of the checklist.
* Given that TTEI with $\beta = 1/2$ has been shown by https://arxiv.org/abs/1705.10033 to perform much better than EI and KG, the authors should include a comparison against it as well. The asymptotic rates suggest that iKG performs as well as TTEI for any $\beta$ so finite-sample empirical evaluations would be very interesting here.
* It is unclear how the sample-sizes were picked that were shown in Table 1 and 2. There was concern that these may be cherry-picked. Looking at the full graphs in the appendix, the AC believes that iKG overall performs on par or better than alternatives on most benchmarks, but definitely understands these concerns and they show that the way the results are presented raise doubts.  To avoid any such concerns, authors should include the full graphs including confidence intervals instead of tables..

Besides these issues related to the empirical evaluation there are also other concerns related to the discussion and presentation:
* As pointed out by reviewer 2tPM, the paper needs a more comprehensive discussion on the limitations of the algorithm and results.
* Up to the direct comparison to TTEI through the way the results are stated, there is very little discussion comparing the rates to those shown for other algorithms.

The active reviewer discussion could not reach a consensus on whether to accept or reject the paper. While the empirical results leave a lot of things to be desired, the main contribution of this paper is of theoretical nature and the convergence rate bounds are indeed interesting. Overall, this makes the paper very much borderline. Since the primary contributions of this paper are the theoretical analysis and algorithm design, which are interesting and significant on their own, this paper is recommended to be accepted. However, the authors do need to address the issues in the empirical evaluation and improve the discussion of the relation to other works in the camera-ready version.
Decision: Accept (poster)