{'fraction_non_alphanumeric': 0.056356991729178685, 'fraction_numerical': 0.015999580338876357, 'mean_word_length': 3.803460440114228, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 22, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Knowledge Gradient for Selection with Covariates: Consistency and Computation

Knowledge gradient is a design principle for developing Bayesian sequential sampling policies to solve optimization problems. In this paper we consider the ranking and selection problem in the presence of covariates, where the best alternative is not universal but depends on the covariates. In this context, we prove that under minimal assumptions, the sampling policy based on knowledge gradient is consistent, in the sense that following the policy the best alternative as a function of the covariates will be identified almost surely as the number of samples grows. We also propose a stochastic gradient ascent algorithm for computing the sampling policy and demonstrate its performance via numerical experiments.


Introduction
We consider the ranking and selection (R&S) problem in the presence of covariates. A decision maker is presented with a finite collection of alternatives. The performance of each alternative is unknown and depends on the covariates. Suppose that the decision maker has access to noisy samples of each alternative for any chosen value of the covariates, but the samples are expensive to acquire. Given a finite sampling budget, the goal is to develop an efficient sampling policy indicating locations as to which alternative and what value of the covariates to sample from, so that upon termination of the sampling, the decision maker can identify a decision rule that accurately specifies the best alternative as a function of the covariates.
The problem of R&S with covariates emerges naturally as the popularization of data and decision analytics in recent years. In clinical and medical research, for many diseases the effect of a treatment may be substantially different across patients, depending on their biometric characteristics (i.e., the covariates), including age, weight, lifestyle habits such as smoking and alcohol use, etc. (Kim et al. 2011). A treatment regime that works for a majority of patients might not work for the others. Samples needed for estimating treatment effects may be collected from clinical trials or computer simulation. For example, in Hur et al. (2004) and Choi et al. (2014), a simulation model is developed to simulate the effect of several treatment regimens for Barrett's esophagus, a precursor to esophageal cancer, for patients with different biometric characteristics. Personalized medicine can then be developed to determine the best treatment regime that is customized to the particular characteristics of each individual patient. Similar customized decision-making can be found in online advertising (Arora et al. 2008), where advertisements are displayed depending on consumers' web browsing history or buying behavior to increase the revenue of the advertising platform as well as to improve consumers' shopping experience.
Being a classic problem in the area of stochastic simulation, R&S has a vast literature. We refer to Kim and Nelson (2006) and Chen et al. (2015) for reviews on the subject with emphasis on frequentist and Bayesian approaches, respectively. Most of the prior work, however, does not consider the presence of the covariates, and thus the best alternative to select is universal rather than varies as a function of the covariates. There are several exceptions, including Hu and Ludkovski (2017), Pearce and Branke (2017), and Shen et al. (2021).
Among them Shen et al. (2021) take a frequentist approach to solve R&S with covariates, whereas the other two a Bayesian approach. The present paper adopts a Bayesian perspective as well.
This paper considers a sampling policy based on knowledge gradient (KG) for R&S with covariates. KG, introduced in Frazier et al. (2008), is a design principle that has been widely used for developing Bayesian sequential sampling policies to solve a variety of optimization problems, including R&S, in which evaluation of the objective function is noisy and expensive. In its basic form, KG begins with assigning a multivariate normal prior on the unknown constant performance of all alternatives. In each iteration, it chooses the sampling location by maximizing the increment in the expected value of the information that would be gained by taking a sample from the location. Then, the posterior is updated upon observing the noisy sample from the chosen location. The sampling efficiency of KG-type policies is often competitive with or outperforms other sampling policies; see Frazier et al. (2009), Scott et al. (2011), Ryzhov (2016, and Pearce and Branke (2018) among others.
A KG-based sampling policy for R&S with covariates is also proposed in Pearce and Branke (2017). The main difference here is that our treatment is more general. First, we allow the sampling noise to be heteroscedastic, whereas it is assumed to be constant for different locations of the same alternative in their work. Heteroscedasticity is of particular significance for simulation applications such as queueing systems. Second, we take into account possible variations in sampling cost at different locations, whereas the sampling cost is simply treated as constant everywhere in Pearce and Branke (2017). Hence, our policy, which we refer to as integrated knowledge gradient (IKG), attempts in each iteration to maximize a "costadjusted" increment in the expected value of information. These generalizations are straightforward when the variance of the sampling noise and the sampling cost are assumed to be known. We also briefly discuss and show how to deal with the case where they are unknown.
The first main contribution of this paper is to provide a theoretical analysis of the asymptotic behavior of the IKG policy, whereas Pearce and Branke (2017) conducted only numerical investigation. In particular, we prove that IKG is consistent in the sense that for any value of the covariates, the selected alternative upon termination of the sampling will converge to the true best almost surely as the sampling budget grows to infinity. Moreover, we consider a practical variant-termed quasi-IKG-which does not require the intermediate optimization problem in each iteration of IKG to be solved exactly, and prove its consistency under mild conditions. Consistency of KG-type policies has been established in various settings, mostly for problems where the number of feasible solutions is finite, including R&S (Frazier et al. 2008, 2009, Mes et al. 2011, and discrete optimization via simulation (Xie et al. 2016). KG is also used for Bayesian optimization of continuous functions in Wu and Frazier (2016), Poloczek et al. (2017), and Wu et al. (2017).
However, in these papers the continuous domain is discretized first, which effectively reduces the problem to one with finite feasible solutions, in order to facilitate their asymptotic analysis. The finiteness of the domain is critical in the aforementioned papers, because the asymptotic analysis there boils down to proving that each feasible solution can be sampled infinitely often. This, by the law of large numbers, implies that the variance of the objective value estimate of each solution will converge to zero. Thus, the optimal solution will be identified ultimately since the uncertainty about the performances of the solutions will be removed completely in the end.
By contrast, proving consistency of KG-type policies for continuous solution domains demands a fundamentally different approach, since most solutions in a continuous domain would hardly be sampled even once after all. Among the several related papers, Scott et al. (2011) studies a KG-type policy for Bayesian optimization of continuous functions. Assigning a Gaussian process prior on the objective function, they established the consistency of the KG-type policy basically by leveraging the continuity of the covariance function of the Gaussian process, which intuitively suggests that if the variance at one location is small, then the variance in its neighborhood ought to be small too. Toscano-Palmerin and Frazier (2018) prove the consistency of a KG-type policy on a more general problem that can reduce to the problem in Scott et al. (2011), for both discrete and continuous domains.
We cast R&S with covariates to a problem of ranking a finite number of Gaussian processes, thereby having both discrete and continuous elements structurally. As a result, we establish the consistency of the proposed IKG policy by proving the following two facts -(i) each Gaussian process is sampled infinitely often, and (ii) the infinitely many samples assigned to a given Gaussian process drives its posterior variance at any location to zero, thanks to the assumed continuity of its covariance function. The theoretical analysis in this paper is partly built on the ideas developed for discrete and continuous problems, respectively, in Frazier et al. (2008) and Scott et al. (2011) in a federated manner.
Although our proofs share similar structures to those in Scott et al. (2011), our assumptions are substantially simpler and minimal. By contrast, for the proof in Scott et al. (2011) to be valid, technical conditions are imposed to regulate the asymptotic behavior of the posterior mean function and the posterior covariance function of the underlying Gaussian process. Nevertheless, the two conditions are difficult to verify. We do not impose such conditions. We achieve the substantial simplification of the assumptions by leveraging the reproducing kernel Hilbert space (RKHS) theory. The theory has been used widely in machine learning (Steinwart and Christmann 2008). But its use in the analysis of KG-type policies is less common. We develop several technical results based on RKHS theory to facilitate analysis of the asymptotic behavior of the posterior covariance function. 1 The second main contribution of this paper is that we develop an algorithm to solve a stochastic optimization problem that determines the sampling decision of the IKG policy in its each iteration. In Pearce and Branke (2017), this optimization problem is addressed by the sample average approximation method with a derivative-free optimization solver. Instead, we propose a stochastic gradient ascent (SGA) algorithm, taking advantage of the fact that a gradient estimator can be derived analytically for many popular covariance functions. Numerical experiments demonstrate the finite-sample performance of the IKG policy in conjunction with the SGA algorithm.
We conclude the introduction by reviewing briefly the most pertinent literature. A closely related problem is multi-armed bandit (MAB); see Bubeck and Cesa-Bianchi (2012) for a comprehensive review on the subject. The significance of covariates, thereby contextual MAB (or MAB with covariates), has also drawn substantial attention in recent years; see Rusmevichientong and Tsitsiklis (2010), Yang and Zhu (2002), Krause and Ong (2011), and Perchet and Rigollet (2013) among others. There are two critical differences between contextual MAB and R&S with covariates. First, the former generally assumes that the covariates arrive exogenously in a sequential manner, and the decision-maker can choose at which arm (or alternative) to sample but not the value of covariates. By contrast, the latter assumes that the decision-maker is capable of choosing both the alternative and the covariates when specifying sampling locations. A second difference is MAB focuses on minimizing the regret which is caused by choosing inferior alternatives and accumulated during the sampling process, whereas R&S focuses on identifying the best alternative eventually and the regret is not the primary concern.
The rest of the paper is organized as follows. In Section 2 we follow a nonparametric Bayesian approach to formulate the problem of R&S with covariates, introduce the IKG policy, and present the main result. In Section 3 we prove the consistency of our sampling policy in the sense that the estimated best alternative as a function of the covariates converges to the truth with probability one as the number of samples grows to infinity. We then propose to use SGA for computing our sampling policy in Section 4, and demonstrate its performance via numerical experiments in Section 5. We conclude in Section 6 and collect detailed proof and additional technical results and numerical experiments in the Appendix.

Problem Formulation
Suppose that a decision maker is presented with M competing alternatives. For each i = 1, . . . , M , the performance of alternative i depends on a vector of covariates x = (x 1 , . . . , x d ) and is denoted by The performances are unknown and can only be learned via sampling.
In particular, for any i and x, one can acquire possibly multiple noisy samples of θ i (x). The decision maker aims to select the "best" alternative for a given value of x, i.e., identify argmax i θ i (x). However, since the sampling is usually expensive in time and/or money, instead of estimating the performances {θ i (x) : i = 1, . . . , M } every time a new value of x is observed and then ranking them, it is preferable to as a function of x, through a carefully designed sampling process. Equipped with such a decision rule, the decision maker can select the best alternative upon observing the covariates in a timely fashion. In addition, the decision maker may have some knowledge with regard to the covariates. For example, certain values of the covariates may be more important or appear more frequently than others. Suppose that this kind of knowledge is expressed by a probability density function γ(x) on X .
During the offline learning period, we need to make a sequence of sampling decisions {(a n , v n ) : n = 0, 1, . . .}, where (a n , v n ) means that the (n + 1)-th sample, denoted by y n+1 , is taken from alternative a n with covariates value v n (refer it as location v n for simplicity). We assume that given θ a n (v n ), y n+1 is an unbiased sample having a normal distribution, i.e., y n+1 | θ a n (v n ) ∼ N (θ a n (v n ), λ a n (v n )), and is assumed to be known. Moreover, suppose that the cost of taking a sample from alternative i at location x is c i (x) > 0, which is also assumed to be known. Suppose that the total sampling budget for offline learning is B > 0, and the sampling process is terminated when the budget is Remark 1. The assumption of known λ i (x) is critical to the theoretical analysis in this paper. As we will see shortly, with known λ i (x), if we impose a Gaussian process as prior for θ i , then its posterior will still be a Gaussian process, which makes the asymptotic analysis tractable. It would not be the case if λ i (x) also needs to be estimated. In practice, λ i (x) is usually unknown and it is a common issue in the experiment design. We suggest to follow the approach in Ankenman et al. (2010), which fits the surfaces of λ i (x) by running multiple simulations at certain design points and using the sample variances. See more details in the numerical experiments in the Appendix. The unknown sampling cost c i (x) in practice can be handled similarly.
We follow a nonparametric Bayesian approach to model the unknown functions {θ 1 , . . . , θ M } as well as to design the sampling policy. We treat θ i 's as random functions and impose a prior on them under which they are mutually independent, although this assumption may be relaxed. Suppose that where |·| means taking the absolute value component-wise; where · denotes the Euclidean norm; (iv) there exist some 0 < C i < ∞ and ε i , u i > 0 such that for all δ such that δ < u i .
Remark 2. Assumption 1 stipulates that k 0 i is stationary, i.e., it depends on x and x only through the difference x − x . In addition, τ 2 i can be interpreted as the prior variance of θ i (x) for all x, and ρ i (x − x ) as the prior correlation between θ i (x) and θ i (x ) which increases to 1 as x − x decreases to 0. The condition in part (iv) of Assumption 1 is weak. In conjunction with the continuity assumption of ρ i , it implies that the sample paths of the Gaussian process θ i are continuous almost surely if the mean function µ 0 i (x) is continuous; see, e.g., Adler and Taylor (2007, Theorem 1.4.1). The sample path continuity will be used to establish the uniform convergence of the posterior mean functions.
A variety of covariance functions satisfy Assumption 1. Notable examples include the squared exponential where r(δ) = d j=1 α j δ 2 j and α j 's are positive parameters, and the Matérn covariance function where ν is a positive parameter that is typically taken as half-integer (i.e., ν = p+1/2 for some nonnegative integer p), Γ is the gamma function, and K ν is the modified Bessel function of the second kind. The covariance function reflects one's prior belief about the unknown functions. We refer to Rasmussen and Williams (2006, Chapter 4) for more types of covariance functions.

Bayesian Updating Equations
For each n = 1, 2, . . ., let F n denote the σ-algebra generated by (a 0 , v 0 ), y 1 , . . . , (a n−1 , v n−1 ), y n , the sampling decisions and the samples collected up to time n. Suppose that (a n , v n ) ∈ F n , that is, (a n , v n ) depends only on the information available at time n. In addition, we use the notation E n [·] := E[·|F n ], and define Var n [·] and Cov n [·] likewise.
Given the setup of our model, it is easy to derive that {θ 1 , . . . , θ M } are independent Gaussian processes under the posterior distribution conditioned on F n , n = 1, . . . , N (B). In particular, under the prior mutual θ i does not provide information about θ j if i = j. Therefore, a consistent policy under the independence assumption ought to ensure that the number of samples taken from each θ i grows without bounds.

Knowledge Gradient Policy
We first assume temporarily that x is given and fixed, and that c i (x) = 1 for i = 1, . . . , M . Then, is a selection of the best problem having finite alternatives, and each sampling decision is reduced to choosing an alternative i to take a sample of θ i (x). The knowledge gradient (KG) policy introduced in Frazier et al. (2008) is designed exactly to solve such a problem assuming an independent normal prior. Specifically, the knowledge gradient at i is defined there as the increment in the expected value of the information about the maximum at x gained by taking a sample at i, that is, Then, each time the alternative i that has the largest value of KG(i; x) is selected to generate a sample of θ i (x).
Let us now return to our context where (1) the covariates are present, (2) each sampling decision consists of both i and x, and (3) each sampling decision may induce a different sampling cost. Since a sample of θ i (x) would alter the posterior belief about θ i (x ), we generalize eq. (10) and define which can be interpreted as the increment in the expected value of the information about the maximum at v gained per unit of sampling cost by taking a sample at (i, x). Then, we consider the following integrated and define the IKG sampling policy as The integrand of eq. (12) can be calculated analytically, as shown in Lemma 1, whose proof is deferred to the Appendix.
Lemma 1. For all i = 1, . . . , M and x ∈ X , where ∆ n i (v) := µ n i (v) − max a =i µ n a (v), Φ is the standard normal distribution function, and φ is its density function.
We solve eq. (13) by first solving max x IKG n (i, x) for all i and then enumerating the results. The computational challenge in the former lies in the numerical integration in eq. (14). Notice that max x IKG n (i, x) is in fact a stochastic optimization problem if we view the integration in eq. (14) as an expectation with respect to the probability density γ(x) on X . One might apply the sample average approximation method to solve max x IKG n (i, x), but it would be computationally prohibitive if X is high-dimensional. Instead, we show in Section 4 that the gradient of the integrand in eq. (14) with respect to x can be calculated explicitly, which is an unbiased estimator of ∇ x IKG n (i, x) under regularity conditions, thereby leading to a stochastic gradient ascent method (Kushner and Yin 2003).
We now present our main theoretical result -the IKG policy is consistent under simple assumptions.
The proof will be sketched in Section 3 and all details are collected in the Appendix.
Assumption 2. The design space X is a compact set in R d with nonempty interior.
Under Assumptions 1-3, the IKG policy (13) is well defined. This can be seen by noting that the maximum of IKG n (i, x) over x ∈ X is attainable since IKG n (i, x) is continuous in x by Assumptions 1 and 3 together with Lemma 1, and X is compact by Assumption 2. Moreover, the IKG policy (13) is consistent as formally stated in the following Theorem 1. (13) is consistent, that is, under the IKG policy,

Theorem 1. If Assumptions 1-3 hold, then the IKG policy
We conclude this section by highlighting the differences between our assumptions and those in Scott et al. (2011), in which the consistency of a KG-type policy driven by a Gaussian process is proved. First and foremost, they impose conditions on both the posterior mean function and the posterior covariance function to regulate their large-sample asymptotic behavior. Specifically, they assume that uniformly for all n and x, v ∈ X where Corr n means the posterior correlation. 2 The two assumptions are critical for their analysis but nontrivial to verify in practice.
By contrast, we do not make such assumptions. Condition (1) is not necessary in our analysis because the "increment in the expected value of the information" is defined as eq. (12) in this paper, whereas in a different form without integration in Scott et al. (2011). There is no need for us to impose Condition (2) in order to regulate the asymptotic behavior of the posterior covariance function, because instead we achieve the same goal by utilizing reproducing kernel Hilbert space (RKHS) theory.
Second, in Scott et al. (2011) the prior covariance function of the underlying Gaussian process is of SE type. We relax it to Assumption 1, which allows a great variety of covariance functions. We also take into account possibly varying sampling costs at different locations.

Consistency
It is straightforward to show that N (B) → ∞ if and only if B → ∞, since c i (·) is bounded both above and below away from zero on X for each i = 1, . . . , M under Assumptions 2 and 3. Thus, Theorem 1 is equivalent to Theorem 2 as follows.
Theorem 2. If Assumptions 1-3 hold, then under the IKG policy, The bulk of the proof of consistency of the IKG policy lies in part (i) of Theorem 2, i.e., to show that lim n→∞ Var n [θ i (x)] = 0 a.s. for all x ∈ X and i = 1, . . . , M . It consists of two steps, which are summarized into the later Propositions 2 and 3. However, both Propositions 2 and 3 critically relies on the asymptotic behavior of the posterior covariance function, which is characterized in the following Proposition 1.
Proposition 1 shows that irrespective of the allocation of the design points {v : = 0, . . . , n − 1}, k n i (x, ·) converges uniformly as n → ∞ for all x ∈ X . (Note that this does not mean the limit is necessarily zero.) Not only is this result of interest in its own right, but also is crucial for proving the consistency of IKG policy under assumptions weaker than those imposed for previous related problems (Scott et al. 2011).
For example, the uniform convergence preserves the continuity of k n i (x, ·) in the limit, a property that is crucial for the proof of Proposition 2. A more general version of Proposition 1 is given in Bect et al. (2019, Proposition 2.9), but we present a different proof built on RKHS theory in the Appendix. Proposition 1 sets a foundation for analysing the asymptotic behavior of Bayesian sequential sampling policies based on Gaussian processes with minimal assumptions.
Before we formally state Propositions 2 and 3, the following definitions are required. For each i, let η n i denote the (random) number of times that a sample is taken from alternative i regardless of the value of x up to the n-th sample, i.e., Further, let η ∞ i := lim n→∞ η n i , which is well defined since it is a limit of a non-decreasing sequence of random variables. Part (i) of Theorem 2 is an immediate consequence of Propositions 2 and 3. The proofs of parts (ii) and (iii) of Theorem 2 and Propositions 2 and 3 are all collected in the Appendix.
In practice, the IKG policy (13) can only be solved numerically, as discussed in the next section, in which case the obtained solution (ã n ,ṽ n ) is not exactly equal to the true solution (a n , v n ). Inspired by Bect et al.
(2019), we consider the quasi-IKG sampling policy, which chooses the sampling decision (ã n ,ṽ n ) such that where {ε n } is a sequence of non-negative real numbers such that ε n → 0 as n → ∞. It is not difficult to see that such quasi-IKG policy is also consistent, as formally stated in the following Theorem 3, whose proof is collected in the Appendix.

Stochastic Gradient Ascent
We now discuss computation of eq. (13) under Assumptions 1-3. It primarily consists of two steps.
(i) For each i = 1, . . . , M , solve max x∈X IKG n (i, x) to find its maximizer, say v n i .
(ii) Set a n = argmax 1≤i≤M IKG n (i, v n i ) and set v n = v n a n .
Let ξ denote a X -valued random variable with density γ(·), and Then, we may rewrite eq. (14) as which suggests the following sample average approximation, where ξ j 's are independent copies of ξ and J is the sample size. In particular, we will use eq. (18) in step (ii) above for computing a n for given v n i 's. However, the sample average approximation method can easily become computationally prohibitive when applied to solve max x IKG n (i, x) in step (i) if the domain X is high-dimensional. Hence, we consider instead the stochastic gradient ascent method to complete step (i).
Equation (17) means that in step (i) above, we solve the stochastic optimization problem then v n i can be computed approximately using the stochastic gradient ascent (SGA) method; see Kushner and Yin (2003) for a comprehensive treatment and Newton et al. (2018) for a recent survey on the subject. Given an initial solution x 1 ∈ X and a maximum iteration limit K, SGA iteratively computes where Π X : R d → X denotes a projection mapping points outside X back to X , 3 and b k is referred as In general, the choice of b k is crucial for the practical performance of SGA, and it is commonly set as b k = α/k β for some constants α and β.
under mild regularity conditions (L'Ecuyer 1995). The explicit forms of g n i (ξ, x) for several common covariance functions are collected in the Appendix. Besides, in the implementation of SGA algorithm, practical modifications such as mini batch and Polyak-Ruppert averaging (Polyak and Juditsky 1992) can be adopted to achieve better performance. Detailed discussion is collected in the Appendix, together with other implementation issues of IKG policy.

Numerical Experiments
In this section, we evaluate the performance of the IKG policy via numerical experiments due to two reasons. First, the theoretical analysis, albeit establishing the consistency of the IKG policy in an largesample asymptotic regime, does not provide a guarantee on the finite-sample performance of the policy.
Second, the analysis has implicitly assumed that the sampling decisions of the IKG policy in eq. (13) can be computed exactly, while in practice it needs to be solved numerically via methods such as SGA that we have proposed. Additional numerical experiments on other issues, including the computational cost comparison between SGA versus the sample average approximation and the effect of estimated λ i (x), are collected in the Appendix. All the numerical experiments are implemented in MATLAB and the source code is available at https://github.com/shenhaihui/ikg.

Finite-Sample Performance
The numerical experiments are conducted on synthetic problems, with the number of alternatives M = 5 and the dimensionality d = 1, 3, 5, 7. For each i = 1, . . . , M , the true performance of alternative i is the revised Griewank function, Further, we set sampling variance λ i (x) ≡ 0.01, and take prior µ 0 We set the cost function c i (x) ≡ 1 for each i = 1, . . . , M , but will 3 For example, one may set ΠX (x) to be the point in X closest to x.
investigate the impact of a different cost function later.
We consider two density functions for the covariates: (1) uniform distribution on X : γ(x) = 1/|X |; (2) multivariate normal distribution with mean 0 and covariance matrix 4 2 I truncated on X : For convenience, we call the above specifications Problem 1 (P1) and Problem 2 (P2), respectively, depending on the choice of γ(x).
The parameters involved in the SGA algorithm (see details in the Appendix) are given as follows: K = 100d, K 0 = K/4, b k = 200d/k 0.7 , m = 20d, and J = 500d 2 . Moreover, the algorithm is started with a random initial solution. The performance of the IKG policy with respect to the sampling budget B is evaluated via the opportunity cost (OC), that is, the integrated difference in performance between the best alternative and the alternative chosen by the IKG policy upon exhausting the sampling budget.
is the learned decision rule up to the budget B under the IKG policy, ω denotes the samples taken under the policy, and the expectation is with respect to ω. Clearly, where L = 30 is the number of replications, ω l denotes the samples for replication l = 1, . . . , L, and {x 1 , . . . , x J } is a random sample of the covariates generated from a given density function γ(x) with J = 1000d 2 for the purpose of evaluation.
We compare the IKG policy against three other polices: • IKG with Random Covariates (IKGwRC). Recall that in the computation of IKG policy, random solution is used to initiate the SGA algorithm. To check whether such random initialization is a main cause for the effectiveness of IKG, we consider the IKGwRC policy as follows. Let x n 1 , . . . , x n M be the initial solutions for M alternatives used in the SGA algorithm when computing (â n ,v n ), n = 0, 1, . . . Then the IKGwRC policy will sample at (a n , v n ) given by where the same samples are used to compute IKG n as in the IKG policy.
• Binned Successive Elimination (BSE). The BSE policy is proposed by Perchet and Rigollet (2013) for solving nonparametric MAB problems with covariates. In their setting, values of the covaraites arrive randomly, and the policy only determines which alternative to select. To implement BSE in our setting, we randomly generate v n from uniform distribution on X , and then apply the BSE policy to determine a n . The BSE policy divides X into m d parts, where m is the number of uniformly divided regions on each coordinate. For each problem, m is tuned within the set {1, . . . , 10}, while other parameters follows the suggestion in Perchet and Rigollet (2013).
• Pure Random Search (PRS). The PRS policy will sample at (a n , v n ), where a n is randomly generated from the uniform distribution on {1, . . . , M } and v n is generated from the uniform distribution on X .
The performances of the four policies for problems P1 and P2 with d = 1, 3, 5, 7 are shown in Figures 1 and 2, respectively. Several findings are made as follows.
First, the estimated opportunity cost in all the test problems exhibits a clear trend of convergence to zero.
This, from a practical point view, provides an assurance that the IKG policy in conjunction with the SGA algorithm indeed works as intended, that is, the uncertainty about the the performances of the competing alternatives will vanish eventually as the sampling budget grows. Second, the IKG policy can quickly reduce the opportunity cost when the sampling budget is relatively small, but the reduction appears to slow down as the sampling budget increases. This finding is consist with prior research on other KG-type policies such as Frazier et al. (2009), and Xie et al. (2016. Third, the learning task of identifying the best alternative becomes substantially more difficult when the dimensionality of the covariates is large.
This can be seen from the growing sampling budget and the slowing reduction in the opportunity cost as d increases.
Overall, IKG outperforms the other three policies. Specific comparisons are as follows. First, IKG has better performance than IKGwRC, especially when the dimensionality is high, which indicates that the SGA algorithm in IKG for solving v n i (see Section 4) indeed works well and has a significant effect in IKG. Second, BSE has inferior performance than IKG, which may be caused by the fact that BSE only optimizes a n given randomly observed v n , while IKG optimizes both a n and v n at the same time. Third, PRS overall has the worst performance, which is not surprising since it does not utilize any information gained from previous sampling. Note that PRS is a consistent policy, but the consistency does not guarantee any finite-sample performance. This reflects the value of IKG -it is not only provably consistent, but also takes advantage of information gained from previous samples to yield good finite-sample performance.

Effect of Sampling Cost
We are also interested in the effect of sampling costs on the IKG policy. In particular, we consider a different cost function other than the unit cost function: vector of all fives. We set γ(x) to be the uniform density 4 and call this specification Problem 3 (P3). We compare two scenarios: (i) the sampling cost is incorporated correctly; and (ii) one ignores variations in the sampling cost at different locations and mistakenly uses the unit sampling cost when implementing the IKG policy (but the actual sampling consumption follows c i (x)). The comparison is illustrated in Figure 3.
There are two observations. On one hand, despite the misspecification in the sampling cost function, the IKG policy is still consistent, with the associated opportunity cost converging to zero. This is not surprising, because using the unit sampling cost function, i.e., c i (x) ≡ 1, is exactly the setup of Theorem 2. On the other hand, however, the finite-sample performance of the IKG policy indeed deteriorates as a result of the misspecification. Further, the deterioration appears to become more significant as the dimensionality of the covariates increases.

Conclusions
In this paper, we study sequential sampling for the problem of selection with covariates which aims to identify the best alternative as a function of the covariates. Each sampling decision involves choosing an alternative and a value of the covariates, from the pair of which a sample will be taken. We design a sequential sampling policy via a nonparametric Bayesian approach. In particular, following the well-known KG design principle for simulation optimization, we develop the IKG policy that attempts to maximize the "one-step" integrated increment in the expected value of information per unit of sampling cost.
We prove the consistency of the IKG policy under minimal assumptions. Compared to prior work on asymptotic analysis of KG-type sampling policies, our assumptions are simpler and significantly more general, thanks to technical machinery that we develop based on RKHS theory. Nevertheless, to compute the sampling decisions of the IKG policy requires solving a multi-dimensional stochastic optimization problem.
To that end, we develop a numerical algorithm based on the SGA method. Numerical experiments illustrate the finite-sample performance of the IKG policy and provide a practical assurance that the developed methodology works as intended.

A. Proof of Lemma 1
Before proving Lemma 1, we first establish the following Lemma 2.

Proof of Lemma 2. Let h(u)
Part (iii) is due to that lim u→∞ h(u) = 0 and g(s, t) = th(s/t).

B. Proof of Proposition 1
To simplify notation, in this subsection we assume M = 1 and suppress the subscript i unless otherwise specified, but the results can be generalized to the case of M > 1 without essential difficulty. In particular, we use κ to denote a generic covariance function, k 0 the prior covariance function of a Gaussian process, and k n the posterior covariance function. We will collect below several basic results on reproducing kernel Hilbert space (RKHS) and refer to Berlinet and Thomas-Agnan (2004) for an extensive treatment on the subject.
Definition 2. Let X be a nonempty set and κ be a covariance function on X . A Hilbert space H κ of functions on X equipped with an inner-product ·, · Hκ is called a RKHS with reproducing kernel κ, if (i) κ(x, ·) ∈ H κ for all x ∈ X , and (ii) f (x) = f, κ(x, ·) Hκ for all x ∈ X and f ∈ H κ . Furthermore, the norm of H κ is induced by the inner-product, i.e., f 2 Hκ = f, f Hκ for all f ∈ H κ .
Remark 5. By Moore-Aronszajn theorem (Berlinet and Thomas-Agnan 2004, Theorem 3), for each covariance function κ there exists a unique RKHS H κ for which κ is its reproducing kernel. Specifically, . Moreover, the inner-product is defined by The following lemma asserts that convergence in norm in a RKHS implies uniform pointwise convergence, provided that the covariance function κ is stationary.
Lemma 3. Let X be a nonempty set and κ be a covariance function on X . Suppose that a sequence of functions {f n ∈ H κ : n = 1, 2, . . .} converges in norm · Hκ as n → ∞. Then the limit, denoted by f , is in Proof of Lemma 3. First of all, f ∈ H κ is guaranteed as a Hilbert space is a complete metric space. A basic property of RKHS is that convergence in norm implies pointwise convergence to the same limit; see, e.g., Corollary 1 of Berlinet and Thomas-Agnan (2004, page 10). Namely, f n (x) → f (x) as n → ∞ for all x ∈ X .
To show the pointwise convergence is uniform, note that since κ is stationary, there exists a function ϕ : for all n and m, where the first equality follows from the reproducing property.
Since a Hilbert space is a complete metric space, the · Hκ -converging sequence {f n } is a Cauchy sequence in H κ , meaning that f n+m − f n Hκ → 0 as n → ∞ for all m. Since this convergence to zero is independent of x, it follows from eq. (22) that {f n } is a uniform Cauchy sequence of functions, thereby converging to f uniformly in x ∈ X .
In the light of Lemma 3, in order to establish the uniform convergence of k n (x, x ) as a function of x , it suffices to prove the norm convergence of k n (x, ·) in the RKHS induced by k 0 . We first establish this result for a more general case in the following Lemma 4, where k 0 is not required to be stationary.

Lemma 4.
Let H k 0 be the RKHS induced by k 0 . If k 0 (x, x) > 0 for all x ∈ X , then for any x ∈ X , k n (x, ·) converges in norm · H k 0 as n → ∞.
Proof of Lemma 4. Fix x ∈ X . The fact that k n (x, ·) ∈ H k 0 is due to eq. (4). It follows from eq. (8) that {k n (x, x) : n ≥ 1} form a non-increasing sequence bounded below by zero. The monotone convergence theorem implies that k n (x, x) converges as n → ∞. Hence, for all m ≥ 1, where Moreover, note that by eq. (4), Let Σ n := k 0 (V n , V n ) + λ(V n ). Then, it follows from eq. (26) and the reproducing property that where I denotes the identity matrix of a compatible size. Furthermore, note that We now combine eqs. (27) and (28) to have which is the difference between two positive semi-definite matrices. Therefore, by eq. (25), where the second inequality follows from the definition of Σ n+m n and the equality follows from eq. (24).
With Lemmas 3 and 4, we are ready to prove Proposition 1.
Proof of Proposition 1. Fix i = 1, . . . , M . Since k 0 i is stationary, k 0 i (x, x) > 0 for all x ∈ X . Then by Lemma 4, for any x ∈ X , k n i (x, ·) converges in norm · H k 0 as n → ∞. Then by Lemma 3, for the · H k 0 -converging uniformly in x ∈ X as n → ∞.

C. Proof of Proposition 2
Notice that if η ∞ i = ∞ under a sampling policy π, then due to the compactness of X , {v n : a n = i, n = 0, 1, . . .} (i.e., the sampling locations associated with alternative i) must have an accumulation point x acc i ∈ X . Namely, there exists a subsequence of {n : a n = i, n = 0, 1, . . .}, say { i,n } ∞ n=0 , such that i,n → ∞ and v i,n → x acc i as n → ∞. For any > 0, let B(x acc i , ) := {x : x acc i − x ≤ } be the closed ball centered at x acc i with radius . Let Var π,n [·] denote the posterior variance conditioned on F n that is induced by π.
The proof of Proposition 2 is preceded by four technical results, i.e., Lemmas 5-8. In Lemmas 5 and 6, we establish an upper bound on Var π,n [θ i (x)] for x ∈ B(x acc i , ). This result does not rely on the IKG policy per se, but is implied by the existence of the accumulation point x acc i instead. In particular, the upper bound which depends on can be made arbitrarily small as → 0. This basically means that in the light of an unlimited number of samples of alternative i that are taken in proximity to x acc i , the uncertainty about θ i (x acc i ) will eventually be eliminated, thanks to the correlation between θ i (x acc i ) and θ i (x) for x near x acc i . Lemma 7 asserts that IKG n (i, x) is bounded by a multiple of the posterior standard deviation of θ i (x).
This implies that when the posterior variance approaches to zero, the IKG factor does too.
Following the last three lemmas, Lemma 8 asserts that the limit inferior of the IKG factor is zero. The reasoning is as follows. By Lemmas 5 and 6, the posterior variance at those sampling locations that fall inside B(x acc i , ) is small. Then, by Lemma 7, the IKG factor at these locations are also small, so does the limit superior. Since the sampling locations inside B(x acc i , ) is a subsequence of the entire sampling locations, the limit inferior of the IKG factor over all sampling locations is even smaller.
At last, Proposition 2 is proved by contradiction -if there is a location that the posterior variance does not approach zero, then the limit inferior of the IKG factor at the same location must be positive as well.
Lemma 5. Fix i = 1, . . . , M , n ≥ 1, and a compact set S ⊆ X . Suppose that the sampling decisions satisfy a 0 = · · · = a n−1 = i and v 0 , . . . , v n−1 ∈ S. If Assumptions 1-3 hold, then for all x ∈ S, Proof of Lemma 5. Fix x ∈ S. First note that λ max i is well defined under Assumptions 2 and 3. Let V n i be the set of the locations of the samples taken from θ i up to time n. Under Assumption 1, eq. (4) reads where V n i = {v 0 , . . . , v n−1 } due to the assumption that a 0 = · · · = a n−1 = i.

For notational simplicity, let
is a diagonal matrix with nonnegative elements, so it is positive semi-definite. Since A and B are both positive definite, by Horn and Johnson (2012, Corollary 7.7.4 It then follows from eqs. (4) and (29) that Thus, it suffices to prove that for all v 0 , . . . , v n−1 ∈ S.
Since k 0 i (V n i , V n i ) is symmetric, we can always write k 0 i (V n i , V n i ) = Qdiag{α 1 , . . . , α n }Q , where α 1 ≥ α 2 ≥ · · · ≥ α n ≥ 0 are the eigenvalues of k 0 i (V n i , V n i ), and Q is an orthogonal matrix, i.e., QQ = I. Therefore, and If we let β j be the j-th element of the row vector k 0 Here, α j and β j clearly both depend on v 0 , . . . , v n−1 , for j = 1, . . . , n. Moreover, they satisfy the following two conditions. First, n j=1 α j = tr(k 0 i (V n i , V n i )) = nτ 2 i , where the first equality is a straightforward fact that the trace of a matrix equals the sum of its eigenvalues, and the second equality is from Assumption 1.
Proof of Lemma 6. It follows from eq. (8) that {Var π,n [θ i (x)]} ∞ n=0 is a non-increasing sequence bounded below by zero. Hence, Var π,n [θ i (x)] converges as n → ∞ and its limit is well defined.
Fix > 0. Let s i,n := {v ∈ B(x acc i , ) : a = i, = 0, . . . , n − 1} be the number of times that al-ternative i is sampled at a point in B(x acc i , ) under π among the total n samples. Then, we must have s i,n → ∞ since x acc i is an accumulation point. Note that reordering the sampling decision-observation pairs ((a 0 , v 0 ), y 1 ), . . . , ((a n−1 , v n−1 ), y n ) does not alter the conditional variance of θ i (x). Hence, we may assume without loss of generality that the first s i,n samples are all taken from alternative i at locations that belong to B(x acc i , ). Since the posterior variance decreases in the number of samples by eq. (8), we conclude that for all x ∈ B(x acc i , ), where the second inequality follows from Lemma 5.
. It then follows from eq. (33) that Sending n → ∞ completes the proof.
Proof of Lemma 7. Notice that Since k 0 i (x, x ) is a continuous function by Assumption 1, it follows from Assumption 3 and the updating eq. (3) that µ n i (x) is a continuous function for any n. Hence, µ n i (x) is bounded on X by Assumption 2. This implies that the first integral in eq. (34) is finite and can be subtracted from both sides of the inequality.
Then, by the definition eq. (12), It follows from eq. (7) that Moreover, by eq. (7), where the last inequality follows because 0 Proof of Lemma 8. Since X is compact by Assumption 2, the sequence {v n ∈ X : a n = i, n = 0, 1, . . . , } is bounded, and it is of length η ∞ i = ∞. Hence, it has an accumulation point x acc i . Let { i,n } ∞ n=0 be the subsequence of {n : a n = i, n = 0, 1, . . .} such that i,n → ∞ and v i,n → x acc i as n → ∞. Fix > 0. Then, by Lemma 6, lim sup It then follows from Lemma 7 that .
By sending → 0, we have ρ i (2 1) → 1 and thus, lim sup n→∞ IKG i,n (i, v i,n ) ≤ 0. Since the limit inferior of a sequence is no greater than that of its subsequence, Moreover, by the definition of IKG eq. (12) and Jensen's inequality, for each i = 1, . . . , M and x ∈ X , where the equality follows immediately from the updating eq. (5). This, in conjunction with eq. (38), implies that lim inf n→∞ IKG n (i, v n ) = 0. By the definition of the sampling location v n in eq. (13), IKG n (i, v n ) = max x∈X IKG n (i, x). Hence, for any x ∈ X , which completes the proof.
Before we prove Proposition 2, we need one more technical result about the almost sure convergence of µ n i , which is stated in the following Lemma 9. A similar result is also given in Bect et al. (2019, Proposition 2.9), and the proof there directly applies here. We are now ready to prove Proposition 2.
Then, P(Ω 0 ) = 1 by the assumption of Proposition 2 and Lemma 9. Fix an arbitrary x ∈ X . We now prove that, under the IKG policy, which establishes Proposition 2. We prove eq. (40) by contraction and assume that there exists some ω 0 ∈ Ω 0 such that k ∞ i (x, x; ω) > 0. In the remaining proof, we suppress the sample path ω 0 to simplify notation.
It follows from the continuity of k 0 i (x, ·) assumed in Assumption 1 and the updating eq. (4) that k n i (x, ·) is continuous. The uniform convergence of k n i (x, ·) by Proposition 1 then implies that k ∞ i (x, ·) is also continuous. Hence, there exist > 0 such that min v∈B(x, ) k ∞ i (x, v) > 0. The uniform convergence of k n i (x, ·) further implies that there exists δ > 0 such that k n i (x, v) ≥ δ for all v ∈ B(x, ) and n ≥ 1. By eq. (7), Let g(s, t) := tφ(s/t) − sΦ(−s/t); see Lemma 2 for properties of g(s, t), including positivity and monotonicity. Then, for all v ∈ X . Consequently, Lemma 1 implies that for all n ≥ 1, where the second inequality holds because g(s, t) is strictly increasing in t ∈ (0, ∞). Note that lim inf n→∞ IKG n (i, x) = 0 by Lemma 8. Hence, where the second inequality holds due to Fatou's lemma. Furthermore, since for any for all v ∈ B(x, ). Then, in the light of eq. (41) and the fact that g(s, t) is strictly decreasing in s ∈ [0, ∞), This contracts the fact that g(s, t) > 0 for all s ∈ [0, ∞) and t ∈ (0, ∞). Therefore, eq. (40) is proved.

D. Proof of Proposition 3
Let S n := (µ n 1 , . . . , µ n M , k n 1 , . . . , k n M ) denote the state at time n, which fully determines the posterior distribution of (θ 1 , . . . , θ M ) conditioned on F n . The state transition S n → S n+1 is governed by eqs. (5) and (6), which is determined by the sampling decision (a n , v n ). By the following Lemma 10, it is easy to see that at time n, the IKG policy (13) chooses Lemma 10. Fix s ∈ S, i = 1, . . . , M , and x ∈ X where X is compact, Proof of Lemma 10. Notice that by the updating eq. (5), given S n = s, a n = i, v n = x and Z n+1 , where the interchange of integral and expectation is justified by Tonelli's theorem for nonnegative functions, and X max a =i µ a (v)γ(v) dv is finite since µ i (v) is continuous on the compact set X for i = 1, . . . , M .
Thus the result in Lemma 10 follows immediately.
Lemma 11. Fix s ∈ S, i = 1, . . . , M , and x ∈ X where X is compact and α(·) > 0 on X . Then, Q(s, i, x) ≥ V (s) and the equality holds if and only if k i (x, x) = 0.
If k i (x, x) = 0, then in the light of the fact that k i is a covariance function, we must have that Hence,σ n i (v, x) = 0 by eq. (7), so µ n+1 a (v) = µ n a (v) for all a = 1, . . . , M and v ∈ X . Hence, µ n+1 a (v) is deterministic given S n for all a = 1, . . . , M and v ∈ X . Thus, the inequality eq. (43) holds with equality.
Next, assume conversely that Q(s, i, x) = V (s). If k i (x, x) = 0, then the continuity of k i implies that k i (v, x) = 0 for all v ∈X , whereX ⊂ X is an open neighborhood of x. Without loss of generality, we assume that for all v ∈X , k i (v, x) > 0 and thus, By the strict convexity of max(·, ·) and Jensen's inequality, for v ∈X . Hence, eq. (43) becomes a strict inequality since γ(v) > 0 for all v ∈ X . This contradicts Lemma 12. Fix i = 1, . . . , M . If Assumptions 1 and 3 hold, and k ∞ i (x, x) = 0 for some x ∈ X , then η ∞ i = ∞.
Proof of Lemma 12. We prove by contradiction and assume that η ∞ i < ∞. Then, N i := min{n : η n i = η ∞ i } < ∞ and a n = i for all n ≥ N i . Due to the mutual independence between the alternatives, it follows that the posterior distribution of θ i remains the same for n ≥ N i . In particular, It follows from eq. (6) that By the definition of N i , a N i −1 = i. Then by eq. (7), It follows from eqs. (44) and (45) 0 and λ i (v N i −1 ) > 0 in Assumption 3. By induction, we can conclude that k 0 i (x, x) = 0, which contracts the fact that k 0 i (x, x) = τ 2 i > 0 in Assumption 1. Therefore, we must have η ∞ i = ∞.
We are now ready to prove Proposition 3.
which completes the proof.

E. Proof of Theorem 2
Part ( For part (ii), fix an arbitrary x ∈ X . Note that for each i = 1, . . . , M , as n → ∞, where the convergence holds due to the fact that 0 ≤ k n i (x, x) ≤ k 0 i (x, x) from eq. (8) and the dominated convergence theorem. This asserts that µ n i (x) → θ i (x) in L 2 . By Lemma 9, µ n i (x) → µ ∞ i (x) a.s., which implies that θ i (x) = µ ∞ i (x) a.s., due to the a.s. uniqueness of convergence in probability. Thus, µ n i (x) → θ i (x) a.s. as n → ∞.

F. Proof of Theorem 3
The steps to prove Theorem 3 are exactly the same to those for Theorem 2, and we only need to modify the arguments related to the actual sampling decision (which is (a n , v n ) satisfies eq. (13) in the IKG policy, and (ã n ,ṽ n ) satisfies eq. (15) in the quasi-IKG policy). So, we will not repeat the entire proofs, but only point out the modification briefly. Specifically, the two main steps to prove Theorem 3 are summarized as the following Propositions 4 and 5, which are parallel to Propositions 2 and 3. Proof of Proposition 4. All the intermediate lemmas for Proposition 2 directly apply to Proposition 4, except for Lemma 8. Instead, we now need to show that under the quasi-IKG policy, for any x ∈ X , lim inf n→∞ IKG n (i, x) = 0. We first observe that, for the sequence {ṽ n ∈ X :ã n = i, n = 0, 1, . . . , }, we can still show lim inf n→∞ IKG n (i,ṽ n ) = 0 with the same arguments. Then, by the definition of the quasi-IKG policy (15), On the other hand, since IKG n (i, v n ) = max x∈X IKG n (i, x), then for any x ∈ X , eq. (39) is replaced by where the equality is due to lim inf n→∞ IKG n (i,ṽ n ) = 0 and ε n → 0. Finally, the proof of Proposition 4 follows the similar arguments as in the proof of Proposition 2. Notice that S n (ω 0 ) → S ∞ (ω 0 ) pointwise as n → ∞ since ω 0 ∈ Ω 1 . Hence, there exists a finite number n 1 (ω 0 ) > T (ω 0 ) such that for all n ≥ñ 1 (ω 0 ). Since ε n → 0 as n → ∞, there exists a finite numberñ 2 (ω 0 ) > T (ω 0 ) such that ε n < ∆/2 for all n ≥ñ 2 (ω 0 ). Then, we can conclude that at timeñ(ω 0 ) := max(ñ 1 (ω 0 ),ñ 2 (ω 0 )) > T (ω 0 ), quasi-IKG policy must choose alternative i ∈ A. Otherwise, for n =ñ(ω 0 ), ifã n / ∈ A, then by eqs. (42) and (48), IKG n (ã n ,ṽ n ) < IKG n (a n , v n ) − ∆/2 < IKG n (a n , v n ) − ε n , which violates the definition of quasi-IKG policy defined in eq. (15).

H. Implementation Issues
A plain-vanilla implementation of IKG n (i, x) in eq. (18) may encounter rounding errors, since h n i (ξ j , x) may be rounded to zero when evaluated via eq. (16); see Frazier et al. (2009) for discussion on a similar issue.
To enhance numerical stability, we first evaluate the logarithm of the summand and then do exponentiation.
Ifσ n i (ξ j , x) = 0, we compute where Φ(−u j )/φ(u j ) is known as the Mills ratio, and can be asymptotically approximated by u j /(u 2 j +1) for large u j . Moreover, log (1 + x) can be accurately computed by log1p function available in most numerical software packages. At last, we compute log IKG n (i, x) = log j∈J e g j − log(c i (x)) = g * + log j∈J e g j −g * − log(c i (x)), where J := {j :σ n i (ξ j , x) = 0, j = 1, . . . , J}, and g * = max j∈J g j ; we set log IKG n γ (i, x) = −∞ if J is empty. The above procedure is summarized in Algorithm 1.
In the implementation of SGA, we adopt two well-known modifications.
(i) We use mini-batch SGA to have more productive iterations. Specifically, in each iteration eq. (19), instead of using a single g n i (ξ k , x k ) as the gradient estimate, we use the average of m independent estimates g n i (ξ k1 , x k ), . . . , g n i (ξ km , x k ), which is denoted asḡ n i (ξ k1 , . . . , ξ km , x k ).
(ii) We adopt the Polyak-Ruppert averaging (Polyak and Juditsky 1992) to mitigate of the algorithm's sensitivity on the choice of the step size. Specifically, when K iterations are completed, we report 1 K+2−K 0 K+1 k=K 0 x k , instead of x K+1 , as the approximated solution of v n i , where 1 ≤ K 0 ≤ K is a pre-specified integer.
Upon computingv n i ≈ argmax x IKG n (i, x) with SGA for each i, we set a n = argmax 1≤i≤M log IKG n (i,v n i ) andv n =v n a n , exact value of the computational cost, one needs to know the true optimal solution of eq. (13) and control the optimality gap when a specific method is used. Here we simply compare the relative computational cost of two methods by roughly controlling the resulting OC at the same level.
The same problem in Section 5 is considered and we let the dimensionality d increase from 1 to 7. The density function of covariates is the uniform distribution and the cost function is constantly 1. All the parameters for the problem, the IKG with SGA (i.e., method 1) and the evaluation of OC are the same as before. For each d, the sampling policy under the two methods is carried out respectively until the budget B = 100 is exhausted, and the OC(B) curves are obtained. For fair comparison, we let the step (ii) of method 2 be exactly the same (i.e., same sample used) as that of method 1, and tune the sample size in step (i) of method 2 as follows. We gradually increase the sample size of random covariates used in SAA (not the number of samples from alternatives), until the resulting OC(B) curve from method 2 is roughly comparable to that from method 1. Note that for either method the computation time needs to solve eq. (13) depends on the number of samples allocated to each alternative so far, and will increase as the samples accumulate. So, we report the total computation time spent on solving eq. (13) during the entire sampling process (until the budget B = 100 is exhausted, which means eq. (13) is solved for 100 times), averaged on L = 30 replications, for the two methods, which are denoted as T 1 (d) and T 2 (d) respectively.
The following Figure 4 shows the comparison between methods 1 and 2. Left panel of Figure 4 shows the sample sizes of random covariates used to approximately solve v n i = max x∈X IKG n (i, x) for each i in step (i) by the two methods, which are denoted as N 1 (d) and N 2 (d) respectively. Note that N 1 (d) = mK = 20d × 100d = 2000d 2 as specified, and N 2 (d) is tuned so that the performance of method 2 matches that of method 1. Right panel of Figure 4 shows the computation times T 1 (d) and T 2 (d) (in MATLAB, Windows 10 OS, 3.60 GHz CPU, 16 GB RAM). It can be seen that IKG with SGA (i.e., method 1) scales much better in dimensionality d than IKG with pure SAA (i.e., method 2). Recall that for each method, the sample size of covariates in step (ii) is set as 500d 2 . So, even consider the fact that in method 2 the function approximation in step (i) can be directly used in step (ii), which saves the sample of covariates and the relevant computation in step (ii), the entire sample size and the computation time of method 2 still grows much faster than method 1.