Active Set Ordering

Authors: quoc phong nguyen
sunil  gupta
svetha  venkatesh
bryan  kian
hsiang  low
patrick  jaillet
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:02:47

Abstract: In this paper, we formalize the active set ordering problem, which involves actively discovering a set of inputs based on their orderings determined by expensive evaluations of a blackbox function. We then propose the mean prediction (MP) algorithm and theoretically analyze it  in terms of the regret of predicted pairwise orderings between inputs. Notably, as a special case of this framework, we can cast Bayesian optimization as an active set ordering problem by recognizing that maximizers can be identified solely by comparison rather than by precisely estimating the function evaluations. As a result, we are able to construct the popular Gaussian process upper confidence bound (GP-UCB) algorithm through the lens of ordering with several nuanced insights. We empirically validate the performance of our proposed solution using various synthetic functions and real-world datasets.

Main paper: 
 introduction: 
 In real-world applications, we often encounter the problem of estimating an unknown function, known as a blackbox function, (i.e., those without closed-form expressions or derivatives) using their expensive and noisy evaluations. Under these circumstances, an efficient sequential process of evaluating the function is desired. On one extreme, experimental design (ED) aims to estimate the function in its entire input domain, e.g., by decreasing the uncertainty of the function globally in Bayesian ED [4, 18] . On the other extreme, the renowned Bayesian optimization (BO) targets inputs with the extreme function values such as the maximizers and the minimizers [2, 6, 7] .While the connection between ED and BO is studied in the classic work of [19] , we still lack a problem formulation that strikes a balance between the prohibitively expensive process of estimating the entire function globally in ED and the lack of information about the function away from extreme locations in BO. One may consider a related problem, called level set estimation (LSE), which focuses on estimating inputs with function evaluations above or below a given (or implicit) threshold [1, 3, 8, 14] . However, without domain knowledge of the blackbox function, it is easy to set a threshold that leads to undesirably large or small level sets.Let us consider an environmental monitoring problem of estimating a chemical concentration in a field. The blackbox function is the mapping from locations of the field to the chemical concentration measurement. It can be of a greater interest to estimate the maximizers, the minimizers, the top-k locations (with the highest chemical concentration) and the bottom-k locations. On one hand, these estimates provide more information about the blackbox function than just the maximizers or minimizers in BO. On the other hand, they may require less resource (i.e., evaluations of the blackbox function) than estimating the entire function in ED. Besides, as the top-k locations consist of exactly k locations in the field, it circumvents the issue of undesirably large or small level sets in LSE.Our main contribution in this paper is to formulate the above challenge and resolve it with a theoretically grounded solution. Specifically, we propose the active set ordering problem to capture the above scenario (Sec. 2.1). It aims to estimate subsets of the input domain that are defined based on pairwise comparisons/orderings between the blackbox function evaluations. 1 These subsets include the maximizers, the minimizers, and the top-k inputs with the highest function evaluations. Like Bayesian ED, BO, and LSE, we adopt the pool-based active learning setting [18] in constructing a solution that sequentially selects a sampling input from the domain at each iteration. The knowledge from observing function evaluations at the sampling inputs helps predicting the subsets of interest and directs the algorithm to select the next sampling input. To facilitate the presentation of our method, we begin with the building block of our ordering-based problem: pairwise comparison/ordering between function evaluations in Sec. 3 . Specifically, we propose a new kind of regret to quantify the loss of a pairwise ordering (Sec. 3.1), a prediction of the top-k inputs based on only the posterior mean (Sec. 3.2), and a sampling strategy that is equipped with a theoretical performance guarantee for the proposed prediction (Sec. 3.3) . Subsequently, these concepts of the regret, the prediction, and the sampling strategy are extended to orderings between sets, which ultimately addresses the active set ordering problem in Sec. 4 . Notably, the regret simplifies to the well-known regret in BO (Remark 4.1). Hence, we recover both the theoretical analysis and the GP-UCB algorithm [19] when considering a special case of our problem setting (Remark 4.5). In Sec. 5, we empirically validate the performance of our solution using several synthetic functions and real-world datasets. 
preliminaries and problem statement 2.1 top-k set: 
 Adopting an assumption in existing level set estimation (LSE) works [1, 8] , we consider a blackbox function f : X → R where the domain X is a finite set of n elements in R d . Let S c ≜ X \ S denote the complement of any subset S ⊂ X . In this paper, the ordering between inputs are determined with respect to their corresponding blackbox function evaluations. Hence, we use the term "the ordering between x and x ′ " and "the ordering between f (x) and f (x ′ )" interchangeably. Definition 2.1 (Top-k set). The top-k set, denoted as S(k), is the set of k inputs with the highest function evaluations. Specifically, |S(k)| = k and ∀x ∈ S(k), ∀x ′ ∈ S c (k), f (x) ≥ f (x ′ ).In this work, we propose the active set ordering problem to estimate the top-k set S(k) of a blackbox function f by efficiently gathering noisy function evaluations in a sequential manner. Furthermore, it includes the Bayesian optimization (BO) problem when k = 1 because the top-1 set S(1) contains a maximizer of f .The noisy function evaluation mentioned in the previous section is denoted as y(x) ≜ f (x) + ϵ(x) where the noise ϵ(x) ∼ N (0, σ2 n ) is a Gaussian random variable with a known (or estimated) variance σ 2 n . To obtain the posterior distribution of the unknown function f given these noisy evaluations, we model f using a Gaussian process (GP), that is, every subset of {f (x)} x∈X follows a multivariate Gaussian distribution [16] . A GP is fully specified by its prior mean and its kernel k x,x ′ ≜ cov(f (x), f (x ′ )) which measures the covariance between function values. Let D t denote the set of sampling inputs in the first t-1 iterations. Then, given y Dt ≜ (y(x)) x∈Dt , the predictive distribution of any function evaluation f (x) follows a Gaussian distribution with the following mean and variance:µ t (x) ≜ k t (x) ⊤ (K t + σ 2 n I) -1 y Dt σ 2 t (x) ≜ k(x, x) -k t (x) ⊤ (K t + σ 2 n I) -1 k t (x)wherek t (x) ≜ (k(x, x ′ )) x ′ ∈Dt , K t ≜ (k(x, x ′ ))x,x ′ ∈Dt , and I is the identity matrix [16] .Assuming f belongs to a reproducing kernel Hilbert space with its norm bounded by B > 0, due to [5] , we have the following confidence bound of f (x). 2 Lemma 2.2. Pick δ ∈ (0, 1) and set β t = (B + σ n 2(γ t-1 + 1 + log 1/δ)) 2 . Then, the following event happens with probability of at least1 -δ, ∀x ∈ X , ∀t ≥ 1, l t (x) ≤ f (x) ≤ u t (x)wherel t (x) ≜ µ t (x) -β 1/2 t σ t (x), u t (x) ≜ µ t (x) + β 1/2 t σ t (x), and γ t-1 ≜ max A⊂X :|A|=t-1 I(y A ; f A ) is the maximum information gain of f A ≜ {f (x)} x∈A through ob- serving y A over all subsets A ⊂ X of size |A| = t -1.To ease notational clutter, we denote the above confidence interval of f (x) as C t (x) ≜ [l t (x), u t (x)] and its length as|C t (x)| ≜ u t (x) -l t (x).3 Active Pairwise Ordering: n = 2From Definition 2.1, pairwise orderings (or pairwise comparisons) are the building blocks of our active set ordering problem. Hence, to facilitate the exposition of the key ideas, let us begin with a simplistic setting where the input domain X consists of only n = 2 inputs, i.e., X = {x, x′ } and f (x) ̸ = f (x ′ ). The problem is to determine the top-1 set S(1), i.e., the maximizer of f (equivalently, the minimizer of f ). In essence, the goal is to check if f (x) > f (x ′ ) by strategically collecting noisy evaluations y(x) and y(x ′ ). In particular, at iteration t, the algorithm proposes a sampling input x t ∈ X to obtain a noisy evaluation y(x t ). Then, the GP posterior distribution of f is updated and used to construct a predicted ordering between x and x′ (i.e., the ordering between f (x) and f (x ′ )). The problem boils down to the strategy of selecting the sampling input x t such that a performance metric of the predicted ordering between f (x) and f (x ′ ) is satisfactory. In the next section, we introduce a regret definition to serve as a performance metric.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: The limitations are elaborated as assumptions in the paper including: a finite input domain of the blackbox function (see Sec. 2.1) and the blackbox function belonging to a reproducing kernel Hilbert space with a bounded norm (see Sec. 2.2).Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.• The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
regret: 
 Let us denote the (unknown) true ordering between x and x′ according to the evaluations of the blackbox function f as π * :π * (x, x′ ) ≜ 1 f (x)≥f (x ′ ) (1)where the indicator function 1 f (x)≥f (x ′ ) = 1 if f (x) ≥ f (x ′ ) and 0 otherwise. For any ordering π : {(x, x′ )} → {0, 1}, we define the following regret of π(x, x′ ):EQUATIONIn particular,r π(x,x ′ )=1 = max(0, f (x ′ ) -f (x)) and r π(x,x ′ )=0 = max(0, f (x) -f (x ′ )).The rationale is to ensure poor performance leads to large regret: The regret is |f (x) -f (x ′ )| (which increases as the gap between f (x) and f (x ′ ) increases) if the ordering π does not align with the true ordering, i.e., π(x, x′ ) ̸ = π * (x, x′ ). On the contrary, the regret is 0 (i.e., the best performance) if π(x, x′ ) = π * (x, x′ ).However, the blackbox function f renders the evaluation of r π(x,x ′ ) impossible. Thus, we resort to relying on the GP posterior distribution of f at iteration t to construct an upper bound of the above regret in the following lemma (proof in Appendix A).Lemma 3.1. For all t ≥ 1, let us defineEQUATIONThen, ρπ(x,x ′ ) is an upper confidence bound of the regret r π(x,x ′ ) , i.e.,P ∀t ≥ 1, r π(x,x ′ ) ≤ ρ (t) π(x,x ′ ) ≥ 1 -δwhere δ is as defined in Lemma 2.2.Definition 3.2 (Predicted pairwise ordering π µt ). Given the above upper bound ρ (t) π(x,x ′ ) of the regret, we would like to make a prediction π µt that minimizes ρ (t) π(x,x ′ ) . Therefore, π µt is defined as followsEQUATIONAs a result, the upper confidence bound of the regret in ( 3) is minimized at π(x, x′ ) = π µt (x, x′ ) and its minimum value isEQUATIONWe note that the upper confidence bound of the regret can be interpreted as a measure of the approximation quality or the uncertainty reduction as discussed in the following two remarks.Remark 3.3 (Approximation quality). Since ρ (t) πµ t (x,x ′ ) ≥ r πµ t (x,x ′ ) for all t ≥ 1 with probability of at least 1 -δ, the regret incurred by the ordering π µt cannot exceed the worst-case regret ρ (t)πµ t (x,x ′ ) as shown in Fig. 1a. Hence, if |f (x) -f (x ′ )| > ρ (t)πµ t (x,x ′ ) , π µt (x, x′ ) is the true ordering, i.e., π µt (x, x′ ) = π * (x, x′ ), with probability of at least 1 -δ.Remark 3.4 (Minimum uncertainty reduction). In Fig. 1b , one can interpret ρ (t) πµ t (x,x ′ ) as the minimum amount that the confidence intervals C t (x) and C t (x ′ ) (representing the uncertainty) reduce so that r πµ t (x,x ′ ) = 0 with probability of at least 1 -δ.Moreover, the prediction π µt can be obtained using only the GP posterior mean (proof in Appendix B), which explains the name of our approach: mean prediction (MP) and the notation π µt . Lemma 3.5 (Mean prediction). The predicted ordering π µt defined in (4) can be determined from the GP posterior meanπ µt (x, x′ ) = 1 µt(x)≥µt(x ′ ) . (6) l t (x ′ ) u t (x ′ ) l t (x) u t (x) ρ (t) πµ t (x,x ′ ) = worst-case regret l t (x ′ ) u t (x ′ ) l t (x) u t (x) ρ (t) πµ t (x,x ′ ) = worst-case regret (a) ρ (t)πµ t (x,x ′ ) is the worst-case regret happening when f (x) = l t (x) and f (x ′ ) = u t (x ′ ).l t (x ′ ) u t (x ′ ) l t (x) u t (x) l ′ t (x) u ′ t (x ′ ) ρ (t) πµ t (x,x ′ ) l t (x ′ ) u t (x ′ ) u ′ t (x ′ ) l t (x) l ′ t (x) u t (x) ρ (t) πµ t (x,x ′ ) (b) r πµ t (x,x ′ ) = 0 when (u t , l t ) are refined to (u ′ t , l ′ t )following an observation, i.e., the reduction in the uncertainty represented as the sum of the two red dashed segments is at least ρ (t)πµ t (x,x ′ ) .Figure 1 : Interpretations of the upper bound ρ (t) πµ t (x,x ′ ) when π µt (x, x′ ) = 1.Given the regret in Sec. 3.1 and the predicted ordering π µt (x, x′ ) in Sec. 3.2, we would like to select a sampling input x t ∈ X = {x, x′ } such that the regret r πµ t (x,x ′ ) of the predicted ordering π µt (x, x′ ) reduces quickly.While r πµ t (x,x ′ ) is unknown, it is bounded by ρ (t) πµ t (x,x ′ ) with probability of at least 1 -δ. Hence, to reduce r πµ t (x,x ′ ) , we aim to reduce ρ (t) πµ t (x,x ′ ) . It is also noted that observing y(x t ) decreases the confidence interval |C t (x t )|. Hence, to induce the reduction in the regret r πµ t (x,x ′ ) through observing y(x t ), we select x t such that its confidence interval |C t (x t )| ≥ ρ (t) πµ t (x,x ′ ) (which guarantees that |C t (x t )| ≥ r πµ t (x,x ′ ) with probability of at least 1 -δ). For instance, choosing x t = x in the left plot of Fig. 1a satisfies this condition, but it does not in the right plot of Fig. 1a . In the following lemma, we show that the following 4 choices of the sampling input satisfy the proposed condition (see Appendix C).Lemma 3.6. Let Q t ≜ {x ▽ x′ , x △ x′ , x ∨ x′ , x ∧ x′ } denote a set 3 of inputs at iteration t where x ▽ x′ ≜ argmax x∈{x,x ′ } u t (x) x △ x′ ≜ argmin x∈{x,x ′ } l t (x) x ∨ x′ ≜ argmax x∈{x,x ′ } |C t (x)| x ∧ x′ ≜ argmin x∈{x▽x ′ ,x△x ′ } |C t (x)| .For anyx t ∈ Q t , |C t (x t )| ≥ ρ (t)πµ t (x,x ′ ) . Theorem 3.7. By sampling the input x t following Lemma 3.6, we obtain the following regret boundP ∀T ≥ 1, ∀(x t ) T t=1 ∈ T t=1 Q t , R T ≜ T t=1 r πµ t (x,x ′ ) ≤ O( T β T γ T ) ≥ 1 -δwhere β T , γ T , and δ are as defined in Lemma 2.2. Remark 3.8 (Sublinear cumulative regret). If γ T is sublinear, our average cumulative regret is sublinear. This requirement is similar to most BO and LSE algorithms. It is noted that γ T is sublinear for many popular kernels. For instance, γ T = O((log T ) d+1 ) for the squared exponential (SE) kernel as discussed in [19] . In this case, our cumulative regret bound R T ≤ O * ( T (log T ) 2d ) is the same as that of GP-UCB [19] (where O * (•) denotes asymptotic expressions up to dimension-independent logarithmic factors and is the dimension of the input).We defer the pseudocode to the next section when n ≥ 2.4 Active Set Ordering: n ≥ 2In this section, we utilize the results in Sec. 3 to present the mean prediction (MP) algorithm for the active set ordering problem with n ≥ 2.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: We have provided the proofs for all theoretical results in the appendix of the paper.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
regret: 
 When X consists of n > 2 inputs, there are multiple pairwise orderings between inputs in X . We overload the ordering notation π * of the true pairwise ordering between 2 inputs in (1) to the ordering between 2 sets as follows: for any subsets X 0 ⊂ X andEQUATIONIt is noted that π * (X 0 , X 1 ) remains undefined if the two cases above are not satisfied. However, this situation does not arise in our solution. We define the regret of a set ordering (i.e., multiple pairwise orderings) as the maximum regret of all pairwise orderings:r π(X0,X1) ≜ max (x,x ′ )∈X0×X1 r π(x,x ′ )=π(X0,X1)where r π(x,x ′ ) is defined in (2) and X 0 × X 1 is the Cartesian product of X 0 and X 1 , i.e., r π(X0,X1) = max 0, (2π(X 0 , X 1 ) -1) maxEQUATIONRemark 4.1. It is noted that r π(X0,X1) coincides with the well-known regret in BO when we consider the problem of predicting a maximizer of f . In particularly, predicting x * as a maximizer of f is equivalent to predicting the set ordering π({x * }, X \ {x * }) = 1. Its regret is r π({x * },X \{x * })=1 = max x∈X f (x) -f (x * ) as shown in Appendix E.1.Following the upper confidence bound of the regret of pairwise orderings in (3), we show in Appendix F that with probability of at least 1 -δ, for all t ≥ 1 and for all subsetsX 0 ⊂ X , X 1 ⊂ X c 0 , r π(X0,X1) ≤ ρ (t) π(X0,X1)whereρ (t) π(X0,X1) ≜ max (x,x ′ )∈X0×X1 ρ (t) π(x,x ′ )=π(X0,X1) .In this section, we generalize the prediction in Sec. 3.2 to set orderings. From Lemma 3.5, there is no contradiction in the pairwise orderings π µt (x, x ′ ) (defined in ( 4)) for all {x, x ′ } ⊂ X . In other words, the transitivity property holds for the binary relationEQUATIONwhere the set ordering π µt (S µt (k), S c µt (k)) is obtained by substituting π * with the pairwise ordering π µt (see Definition 3.2) in (7) . From Lemma 3.5, S µt (k) is basically the set of k inputs with the highest GP posterior mean values.EQUATIONLike in Sec. 3.3, our key idea is to select x t such that the length |C t (x t )| of its confidence interval bounds ρ(t) πµ t (Sµ t (k),S c µ t (k)) (in (10)). Since ρ (t) πµ t (Sµ t (k),S c µ t (k))is the maximum upper confidence bound of the regret of all pairwise orderings involved in defining S µt (k), we first determine the input pair (x t , x′ t ) that incurs the maximum upper confidence bound of the regret. This is also the input pair that π µt most likely makes a mistake, following the intuition from [12] .EQUATIONIt is noted that (x t , x′ t ) is constructed from an input in the predicted top-k set S µt (k) and an input in its complement S c µt (k). As the estimation of the top-k set improves, we expect these 2 inputs to be at both sides of the boundary of the top-k set: inside the top-k set vs. outside the top-k set.Then, extended from Lemma 3.6, the following lemma shows that the above desirable property is satisfied by choosing the sampling input x t from any inputs in the setQt ≜ {x t ▽ x′ t , xt △ x′ t , xt ∨ x′ t , xt ∧ x′ t } (defined in Lemma 3.6). Lemma 4.3. For any x t ∈ Qt , |C t (x t )| ≥ ρ (t) πµ t (Sµ t (k),S c µ t (k)) .The proof is shown in Appendix H. As a result, the cumulative regret incurred by choosing x t in Lemma 4.3 is bounded in the following theorem (proof in Appendix I). Theorem 4.4. By sampling x t following Lemma 4.3, we obtain the following cumulative regret boundP ∀T ≥ 1, ∀(x t ) T t=1 ∈ T i=1 Qt , R T,k ≜ T t=1 r πµ t (Sµ t (k),S c µ t (k)) ≤ O( T β T γ T ) ≥ 1 -δwhere β T , γ T , and δ are as defined in Lemma 2.2.Require: X , D 0 , k, T (x t , x′ t ) = argmax (x,x ′ )∈Sµ t (k)×S c µ t (k) ρ (t) πµ t (x,x ′ ) 5: Select x t ∈ {x t ▽ x′ t , xt △ x′ t , xt ∨ x′ t , xt ∧ x′ t }. ▷ Sampling input 6: y t (D t ) ← y(D t-1 ) ∪ {y(x t )} 7: end for 8: Update GP posterior belief: {µ T +1 (x)} x∈X , {σ T +1 (x)} x∈X . 9: Construct S µ T +1 (k) as top-k inputs with the highest values of µ T +1 . 10: return S µ T +1 (k).We call the algorithm that makes prediction using the GP posterior mean and selects the sampling input x t following Lemma 4.3 the mean prediction (MP) algorithm. Its pseudocode is shown in Algorithm 1. Theorem 4.4 indicates that MP incurs a sublinear cumulative regret for several commonly used kernels with sublinear γ T [19] . Remark 4.5 (Bayesian optimization as an active set ordering problem with k = 1). We show in Appendix E.2 that when k = 1, xt ▽ x′ t ∈ argmax x∈X u t (x), which is the sampling input in the GP-UCB algorithm [19] . Additionally, as discussed in Sec. 4.1, the regret r π(S(1),S c (1)) is the wellknown regret in BO. Hence, we recover both the GP-UCB algorithm and its regret bound when k = 1 (although we consider the regret of the prediction rather than that of the sampling input). Moreover, this new construction of GP-UCB leads to some subtle insights. Firstly, while the GP posterior mean has been used in computing the inference regret of entropy search methods [9, 21] , there has not been any theoretical justification for using the posterior mean. In contrast, the theoretical analysis in our work justifies the use of the maximizer of the GP posterior mean as an estimate of the maximizer of f . Secondly, by predicting the maximizer using the GP posterior mean, x ▽ x′ is not the only sampling input that achieves a sublinear cumulative regret. In fact, there are other choices of the sampling input as shown in Lemma 4.3. Similarly, we note that the LCB algorithm to find the minimizer of a blackbox function can be recovered by setting k = n -1 and x t = x △ x′ . Remark 4.6 (Lower bound of active set ordering problem). Let the lower bound of the active set ordering problem be the lower bound of the cumulative regret of the worst-case problem instance over all possible values of k. Then, it should be at least as large as the lower bound of the special case where k = 1, which is the BO problem according to Remark 4.5. Furthermore, BO has known lower bounds for several common kernels, e.g., for the SE kernel, the lower bound of the cumulative regret is Ω( T (log T ) d/2 ) [17] . Hence, the lower bound of the active set ordering problem is at least Ω( T (log T ) d/2 ). Additionally, similar to Remark 3.8, the cumulative regret of our solution in ). This problem is analogous to finding k contour lines of a blackbox function, where each contour line represents the boundary between S(k i ) and its complement S c (k i ). To solve this problem, we define the following input pairEQUATIONIn other words, we aim to reduce the maximum regret incurred by the predicted pairwise orderings in all m top-k sets. Given ( xt , x′ t ) in (12) , MP proceeds by sampling the input x t according to Lemma 4.3, i.e.,x t ∈ { xt ▽ x′ t , xt △ x′ t , xt ∨ x′ t , xt ∧ x′ t }.The approach is elaborated in Appendix J. We also note that active multiple set ordering is able to find both maximizers S(1) and minimizers S c (n -1) simultaneously, a problem has not been studied in GP-UCB [19] .Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification:We have described the experiments and provided the code and datasets for reproducing the experimental results. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
active set ordering: 
 In this section, we validate the empirical performance of our MP algorithm with different choices of the sampling input in Lemma 4. (k),S c µ t (k)) is used to measure the performance of each algorithm, i.e., the prediction of the top-k set consists of the k inputs with the highest GP posterior mean.To begin with, we visualize sampling inputs and the accuracy of S µt (20) that come from our MP algorithm with x t = xt ∧ x′ t and the Var algorithm in Fig. 2 . In Fig. 2a , the histogram shows that the sampling inputs are at the boundary of S (20) . This is highly desirable as it is challenging to decide if an input at the boundary belongs to S (20) . Similarly, the input pair in (11) also consists of inputs around this boundary (depicted as vertical orange lines). On the other hand, precisely estimating the function evaluations of inputs far from the boundary, e.g., inputs around x = 0.85 (in S(20)) and inputs around x = 0.1 (not part of S( 20)) is unnecessary. We observe that the uncertainty of the GP posterior distribution at these inputs is high in Fig. 2a . Hence, our MP algorithm is able to efficiently concentrate its sampling budget on important inputs at the boundary of the top-k set. Interestingly, this boundary serves as a contour line of the blackbox function, indicating that our solution could potentially be applied to estimate the contour line by specifying the proportion of the input domain where function evaluations exceed this contour. Regarding the Var algorithm (i.e., uncertainty sampling) in Fig. 2b , the histogram shows that sampling inputs are distributed evenly across the input domain. It is because Var aims to reduce the uncertainty of the function evaluation throughout the input domain without considering the current predicted S µt (20) . For example, it is inefficient to select sampling inputs far away from the boundary of S (20) . It is observed that the estimation of function evaluations at the boundary of S(20) using Var is more uncertain than that using the MP algorithm given the same number of sampling inputs. This results in erroneously predicting certain inputs in S(20) (depicted as red dots) and overlooking several inputs in S(20) (depicted as black dots). 4We numerically report the performance using the proposed regret r πµ t (Sµ t (k),S c µ t (k)) . The experiments are conducted on 4 synthetic functions: a function sampled from a GP, Branin-Hoo function, Goldstein-Price function with a noise of σ n = 0.1, and Hartmann-6D function with a nosie of σ n = 0.01 [20] . For the first three synthetic functions, the input domain is discretized into a set of 100 points, whereas for the Hartmann-6D function, it is discretized into a set of 1000 points. Motivated by environmental monitoring problems, we generate 3 active set ordering problems that estimate the top-5 set using the dataset of NO 3 concentration in the Lake Zurich (downloaded from https://wldb.ilec.or.jp/Lake/EUR-06/datalist), the dataset of the phosphorus concentration in the Brooms Barn [22] , and the dataset of the humidity in the Intel Lab (downloaded from https://db.csail.mit.edu/labdata/labdata.html). The environment field is discretized into a set of 100 locations in the experiments with the NO 3 and humidity datasets and 400 locations in the experiment with the phosphorus dataset. The experiments are repeated 15 times to account for the randomness in the generation of the observations. Further details are provided in Appendix K. The average and the standard error of the regret are shown in Figs. 3s:a-g. There is not any significant difference in the performance of MP with different sampling inputs in Lemma 4.3. Nevertheless, the MP algorithm with any choice of the sampling input in Qt outperforms the 2 baselines by converging to lower regret. Var x t ∧ x 0 t x t ∨ x 0 t x t ▵ x 0 t x t ▿ xTo empirically validate the performance of our MP algorithm in solving the problem of estimating multiple top-k sets, we consider the problem of estimating S(1) (i.e., maximizers), S( 10 of synthetic functions and real-world environmental datasets in the previous section to compare the performance of MP with Var and Rand. The plot of the average and standard error of the maximum regret max k∈{1,10,20} (r πµ t (Sµ t (k),S c µ t (k)) ) over 15 repeated experiments are shown in Figs. 3m:a-g. The MP algorithm outperforms the other 2 baselines by converging to lower regret. In some active multiple set ordering experiments (e.g., in Figs. 3m:a, 3m:c ), the performance gaps between MP and Var are smaller than those in the previous active set ordering experiments (e.g., Figs. 3s:a, 3s:c ). It is because estimating multiple top-k sets requires more observations, which makes the performance of MP tend towards that of Var which estimates the entire function.When k = 1, the active set ordering problem reduces to the BO problem and a sampling input of our MP algorithm, i.e., x t = xt ▽x ′ t , is the same as that of GP-UCB [19] . Therefore, this section empirically demonstrates the performance of MP with different sampling inputs (x t ∈ {x t ▽ x′ t , xt △ x′ t , xt ∨ x′ t , xt ∧ x′ t }) in solving BO. Our aim is not to show that MP achieves the state-of-the-art performance as a BO solver, but rather to demonstrate that it performs comparably to the well-known GP-UCB algorithm. In addition to comparing with GP-UCB (equivalently, MP with x t = xt ▽x ′ t ), we also compare with 3 classical BO solutions: probability of improvement (PI) [13] , expected improvement (EI) [15] , and max-value entropy search (MES) [21] . The average and the standard error of the regret r πµ t (Sµ t (1),S c µ t (1)) over 15 repeated experiments are shown in Fig. 4 . We observe that MP performs comparably with the well-known GP-UCB algorithm (labelled as xt ▽x ′ t ). Expectedly, EI and MES outperform GP-UCB (and hence, MP) in some experiments such as in Figs. 4b and 4c .Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: We have provided the source code, datasets, and scripts to reproduce the experiment results.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion: 
 This paper presents a new problem formulation, namely active set ordering, that aims to balance between the expensive estimation of the entire function in ED and that of only the maximizers in BO. We propose the mean prediction (MP) algorithm to address this problem with a theoretical no-regret guarantee. Interestingly, BO can be framed as a special instance of active set ordering, which leads to several new subtle understandings regarding the predicted maximizer and other alternative sampling inputs. Last, the performance of MP is empirically evaluated using various synthetic functions and real-world datasets.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We have provided the URLs where datasets are downloaded and described parameters used in the experiments such as the size of the input domain and the noise variance. Other parameters such as the random seed are configured in the submitted code. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 9. Code Of Ethics• Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We will show that ρ (t) π(x,x ′ ) is an upper confidence bound of the regret r π(x,x ′ ) , i.e.,P ∀t ≥ 1, r π(x,x ′ ) ≤ ρ (t) π(x,x ′ ) ≥ 1 -δ .The regret r π(x,x ′ ) is defined as followsr π(x,x ′ ) ≜ max (0, (2π(x, x′ ) -1)(f (x ′ ) -f (x))) .Furthermore, from Lemma 2.2, with probability of at least 1 -δ, for all t ≥ 1,l t (x) ≤ f (x) ≤ u t (x) l t (x ′ ) ≤ f (x ′ ) ≤ u t (x ′ )Hence, with probability of at least 1 -δ, for all t ≥ 1,f (x) -f (x ′ ) ≤ u t (x) -l t (x ′ ) f (x ′ ) -f (x) ≤ u t (x ′ ) -l t (x)Multiplying both sides with (2π(x, x′ ) -1), we obtain(2π(x, x′ ) -1)(f (x ′ ) -f (x)) ≤ u t (x) -l t (x ′ ) if π(x, x′ ) = 0 u t (x ′ ) -l t (x) if π(x, x′ ) = 1 ≜ ρ (t) π(x,x ′ ) .Therefore, with probability of at least 1 -δ, for all t ≥ 1,r π(x,x ′ ) ≜ max (0, (2π(x, x′ ) -1)(f (x ′ ) -f (x))) ≤ max(0, u t (x) -l t (x ′ )) if π(x, x′ ) = 0 max(0, u t (x ′ ) -l t (x)) if π(x, x′ ) = 1 .B Proof of Lemma 3.5We note that 1 µt(x)≥µt(x ′ ) = 1 happens whenµ t (x) ≥ µ t (x ′ ) ⇔ u t (x) + l t (x) 2 ≥ u t (x ′ ) + l t (x ′ ) 2 ⇔ u t (x) -l t (x ′ ) ≥ u t (x ′ ) -l t (x) ⇔ max(0, u t (x) -l t (x ′ )) ≥ max(0, u t (x ′ ) -l t (x)) ⇔ ρ (t) π(x,x ′ )=0 ≥ ρ (t) π(x,x ′ )=1 . Therefore, 1 µt(x)≥µt(x ′ ) = 1 ρ (t) π(x,x ′ )=0 ≥ρ (t) π(x,x ′ )=1 = argmin a∈{0,1} ρ (t) π(x,x ′ )=a = π µt (x, x′ ) .We will show that ρ (t)EQUATIONwhere ( 13) is becausex ▽ x′ ≜ argmax x∈{x,x ′ } u t (x), (14) is because x ▽ x′ ∈ {x, x′ }, (15) is because u t (x ▽ x′ ) -l t (x ▽ x′ ) ≥ 0.Case 2:EQUATION≤ max(0, min(uEQUATIONwhere ( 18) is becauseEQUATION) is because x △ x′ ∈ {x, x′ }, (20) is because u t (x △ x′ ) -l t (x △ x′ ) ≥ 0.Case 3:EQUATION≥ |C t (x △ x′ )| (23) ≥ ρ (t) πµ t (x,x ′ ) (24)where ( 23) is because x △ x′ ∈ {x, x′ }, (24) is from the above proof of case 2 in (21) .Case 4: 16) and ( 21), it follows thatx t = x ∧ x′ ≜ argmin x∈{x ▽ x′ ,x△x ′ } |C t (x)|. From (|C t (x ∧ x′ )| ≥ ρ (t) πµ t (x,x ′ ) .By choosing x t following Lemma 3.6, with probability of at least 1 -δ, for all t ≥ 1,r πµ t (x,x ′ ) ≤ ρ (t) πµ t (x,x ′ ) ≤ |C t (x t )| = 2β 1/2 t σ t (x t )Hence, with probability of at least 1 -δ, for all T ≥ 1,T t=1 r πµ t (x,x ′ ) ≤ T t=1 2β 1/2 t σ t (x t )Since β t is a non-decreasing sequence, β t ≤ β T for all t ≤ T . Therefore, with probability of at least 1 -δ, for all T ≥ 1,T t=1 r πµ t (x,x ′ ) ≤ 2β 1/2 T T t=1 σ t (x t )From Lemma 4 in [5] ,T t=1 σ t (x t ) ≤ 4(T + 2)γ T = O( T γ T )Hence, with probability of at least 1 -δ, for all T ≥ 1,T t=1 r πµ t (x,x ′ ) ≤ O( T β T γ T ) . i.e., R T ≜ T t=1 r πµ t (x,x ′ ) ≤ O( T β T γ T ) .E Bayesian Optimization as Active Set Ordering with k = 1For a predicted top-1 set S µt (1), π µt (S µt (1), S c µt (1)) = 1. Hence, the regret for predicting S µt (1) is expressed as follows. r πµ t (Sµ t (1),S c µ t (1)) = max 0, max(x,x ′ )∈Sµ t (1)×S c µ t (1) f (x ′ ) -f (x) . Let S µt (1) ≜ {x * } and x * ∈ argmax x∈X f (x).r πµ t (Sµ t (1),S c µ t (1)) = max 0, maxx∈S c µ t (1) (f (x) -f (x * ))= max 0, maxx∈S c µ t (1) f (x) -f (x * ) .Since X = S µt (1) ∪ S c µt (1), there are 2 cases• If x * ∈ S c µt (1), then max x∈S c µ t (1) f (x) = f (x * ) ≥ f (x * ) and r πµ t (Sµ t (1),S c µ t (1)) = max (0, f (x * ) -f (x * )) = f (x * ) -f (x * ) . • If x * ∈ S µt (1), i.e., x * = x * , then max x∈S c µ t (1) f (x) ≤ f (x * ) and r πµ t (Sµ t (1),S c µ t (1)) = 0 = f (x * ) -f (x * ) .We will show thatxt ▽ x′ t ∈ argmax x∈X u t (x) .When k = 1, due to the definition of S µt (k) in Definition 4.2xt ∈ argmax x∈X µ t (x) . Let xt ∈ argmax x∈X u t (x) .We consider the following 2 cases:EQUATION)Let us consider the following upper confidence bounds of pairwise orderings:ρ (t) πµ t (xt,xt) = max(0, u t (x t ) -l t (x t )) = u t (x t ) -l t (x t ) > 0 ρ (t) πµ t (xt,x ′ t ) = max(0, u t (x ′ t ) -l t (x t )) .Furthermore, from the choice of (x t , x′ t ) in ( 11) and xt ∈ S c µt (k),ρ (t) πµ t (xt,x ′ t ) ≥ ρ (t) πµ t (xt,xt) . Hence, max(0, u t (x ′ t ) -l t (x t ) ≥ max(0, u t (x t ) -l t (x t )) = u t (x t ) -l t (x t ) > 0 u t (x ′ t ) -l t (x t ) ≥ u t (x t ) -l t (x t ) u t (x ′ t ) ≥ u t (x t ) which contradicts to the assumption 25. Therefore, u t (x t ) = u t (x ′ t ) and xt ▽ x′ t ∈ argmax x∈X u t (x) .F Upper Confidence Bound of the Regret r π(X 0 ,X 1 )r π(X0,X1) ≜ max (x,x ′ )∈X0×X1 r π(x,x ′ )=π(X0,X1)With probability of at least 1 -δ, for all t ≥ 1 and for all {x,x ′ } ⊂ X , r π(x,x ′ )=π(X0,X1) ≤ ρ (t) π(x,x ′ )=π(X0,X1) . Therefore, with probability of at least 1 -δ, for all t ≥ 1 and for all {x, x ′ } ⊂ X ,r π(X0,X1) ≤ max (x,x ′ )∈X0×X1 ρ (t) π(x,x ′ )=π(X0,X1) ≜ ρ (t) π(X0,X1) .The transitivity property of the binary relation µ πt follows directly from its connection to the GP posterior mean in Lemma 3.5. In particular, we would like to show that ifπ µt (x, x ′ ) = 1 π µt (x ′ , x ′′ ) = 1 (26) then π µt (x, x ′′ ) = 1 .From Lemma 3.5, the premise (26) implies thatµ t (x) ≥ µ t (x ′ ) µ t (x ′ ) ≥ µ t (x ′′ )which implies thatµ t (x) ≥ µ t (x ′′ ) .Applying Lemma 3.5 again, we concludeπ µt (x, x ′′ ) = 1 .Applying Lemma 3.6 to the input pair (x t , x′ t ), by selectingx t ∈ {x t ▽ x′ t , xt △ x′ t , xt ∨ x′ t , xt ∧ x′ t }, |C t (x t )| ≥ ρ (t) πµ t (xt,x ′ t ). Furthermore, from the choice of (x t , x′ t ) in (11) ,ρ (t) πµ t (xt,x ′ t ) = max (x,x ′ )∈Sµ t (k)×S c µ t (k) ρ (t) πµ t (x,x ′ ) = ρ (t) πµ t (Sµ t (k),S c µ t (k) .Therefore, |C t (x t )| ≥ ρ (t( xt , x′ t ) ≜ argmax (x,x ′ )∈∪ m i=1 Sµ t (ki)×S c µ t (ki) ρ (t) πµ t (x,x ′ ) 5: Select x t ∈ { xt ▽ x′ t , xt △ x′ t , xt ∨ x′ t , xt ∧ x′ t }. ▷ Sampling input 6:y t (D t ) ← y(D t-1 ) ∪ {y(x t )} 7: end for 8: Update GP posterior belief:{µ T +1 (x)} x∈X , {σ T +1 (x)} x∈X . 9: Construct {S µ T +1 (k i )} mi=1 as the collection of m top-k sets predicted using µ T +1 . 10:return {S µ T +1 (k i )} m i=1 .I Proof of Theorem 4.4By choosing x t following Lemma 4.3, with probability of at least 1 -δ, for all t ≥ 1,r πµ t (Sµ t (k),S c µ t (k)) ≤ ρ (t) πµ t (Sµ t (k),S c µ t (k)) ≤ |C t (x t )| = 2β 1/2 t σ t (x t ) .Furthermore, from the non-decreasing property of the sequence(β t ) T t=1 , T t=1 r πµ t (Sµ t (k),S c µ t (k)) ≤ T t=1 2β 1/2 t σ t (x t ) ≤ 2β 1/2 T T t=1 σ t (x t )By utilizing the result from [5] like Appendix D, we can obtainT t=1 σ t (x t ) ≤ O( T γ T ) .Therefore, with probability of at least 1 -δ, for all T ≥ 1,T t=1 2β 1/2 T σ t (x t ) ≤ O( T β T γ T ) i.e., R T,k ≜ T t=1 r πµ t (Sµ t (k),S c µ t (k)) ≤ O( T β T γ T ) .The pseudocode of MP algorithm for the active multiple set ordering problem is shown in Algorithm 2.In the rest of this section, we prove the cumulative regret bound of Algorithm 2.We recall that in (12) ,( xt , x′ t ) ≜ argmax (x,x ′ )∈(∪ m i=1 Sµ t (ki)×S c µ t (ki)) ρ (t) πµ t (x,x ′ ) Therefore, ∀i ∈ {1, 2, . . . , m}, ρ (t) πµ t ( xt, x′ t ) ≥ max (x,x ′ )∈S(ki)×S c (ki) ρ (t) πµ t (x,x ′ ) = ρ (t) πµ t (Sµ t (ki),S c µ t (ki))Furthermore, applying Lemma 3.6 to the input pair ( xt , x′ t ), for anyx t ∈ { xt ▽ x′ t , xt △ x′ t , xt ∨ x′ t , xt ∧ x′ t } |C t (x t )| ≥ ρ (t) πµ t ( xt, x′ t ) .Therefore, ∀i ∈ {1, 2, . . . , m},|C t (x t )| ≥ ρ (t) πµ t (Sµ t (ki),S c µ t (ki)). Hence, with probability of at least 1 -δ, for all t ≥ 1, ∀i ∈ {1, 2, . . . , m}, r πµ t (Sµ t (ki),S c µ t (ki)) ≤ ρ(t) πµ t (Sµ t (ki),S c µ t (ki)) ≤ |C t (x t )| . As a result, with probability of at least 1 -δ, for all T ≥ 1, ∀i ∈ {1, 2, . . . , m}, R T,ki ≜ T t=1 r πµ t (Sµ t (ki),S c µ t (ki)) ≤ T t=1 |C t (x t )| ≤ O( T β T γ T )where the last inequality comes from Appendix I.All experiments were conducted on a computer equipped with an AMD Ryzen 7 6800HS processor and 16GB of RAM.To generate a function sampled from a GP, we randomly generate3 observations {(x i , y(x i ))} 3 i=1and fit a GP model to these observations. Then, we sample function evaluations at all inputs in the domain from the GP posterior distribution. These function evaluations are considered the evaluations of the blackbox function. To generate an observation at a sampling input, we add a Gaussian noise (of σ n = 0.1) to the evaluations of the blackbox function at the sampling input.The expressions for the Branin-Hoo and Goldstein-Price functions are described at [20] . We transform the input domain of these functions to [0, 1] 2 and standardize the function evaluations. The input domain is discretized into n = 100 points randomly selected in the domain [0, 1] 2 . The noise is chosen with σ n = 0.1.To perform experiments with the NO 3 dataset from Lake Zurich (available at https://wldb.ilec. or.jp/Lake/EUR-06/datalist), we standardize the NO 3 measurements. Then, a GP model is trained on the standardized dataset to generate the noisy evaluations of the blackbox function over n = 100 randomly chosen locations.We use the logarithmic values of the phosphorus measurements in the soy survey of Brooms Barn [22] to construct a blackbox function. The locations are normalized to the range [0, 1] 2 and the logarithmic values of the phosphorus measurements are standardized. Then, we train a GP model to generate the noisy evaluations of the blackbox function over n = 400 randomly chosen locations.To perform experiments with the humidity dataset, we extract the humidity measurements at different locations with the same mote id of 31167 from the Intel Lab data (available at https://db.csail. mit.edu/labdata/labdata.html). The humidity measurements are standardized. Then, a GP model is trained to this extracted dataset to generate the noisy evaluations of the blackbox function over n = 100 randomly chosen locations.To remove the potential inefficiency due to repeated sampling in Rand and Var, we provide additional experiments by replacing the Rand and Var baselines with RandNoRepl and VarNoRepl, which do not allow repeated sampling. This modification potentially gives RandNoRepl (random sampling without replacement across different iterations) and VarNoRepl (uncertainty sampling without replacement across different iterations) an additional advantage over our solutions which allow repeated sampling. By avoiding repeated sampling, RandNoRepl and VarNoRepl can sample the input domain more uniformly, whereas our methods might re-sample certain input regions. However, as shown in Figure 5 , RandNoRepl and VarNoRepl still do not outperform our solutions. The justification for the efficiency of our solutions is in the nature of noisy observations: With a noise standard deviation of σ n = 0.1, a single observation at each input may not suffice to accurately determine the ordering with its neighboring inputs in terms of the function value. Hence, spreading the sampling budget across the whole input domain may not perform well. In contrast, our approach allocates more sampling inputs to the boundary of the top-k set, where it is particularly challenging to check if inputs belong to the top-k set (see Figure 2 ). Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Existing research on best-k arm identification in the multi-armed bandit literature poses a similar problem, but it often focuses on the pure exploration setting and assumes independent arms which are inadequate for modelling blackbox functions[10][11][12].Alternatively, we may consider using the confidence bounds established in[19].For convenience, we allow duplicate elements in Qt.The complete animation is available in the supplementary materials. 


Decision: The reviewers generally agreed that this was an interesting problem, and the algorithmic tools were solid. The top-k problem clearly has lots of applications. While some reviewers were lukewarm about the work, we had a followup discussion with them and generally all reviewers were ok with accepting the paper for NeurIPS. I want to commend the authors for doing a good job in the discussion. But I want to recommend that particular care is taking in preparing the camera-ready, especially in incorporating the feedback received throughout this review process.

Reviews: review: paper_summary: paper_summary: This paper introduces the "active set ordering" problem, which aims at recovering the top-k actions in a set by strategically sampling actions. The authors formally define the problem in the regret minimization setting and propose an algorithm for that. They authors upper bound the regret and run experiments the test the proposed algorithm.
strength_weakness: strength_weakness: 1. The authors didn't explicitly quantify some problem-dependent quantities in their regret bound, e.g., \gamma_T and \beta_T. How large these quantities are in different settings? 
2. A lower bound analysis is missing, which make it even harder to know if the upper bound is tight or not.
3. While I understand the studied setting is slightly different from top-k arm identification, the proposed algorithm is actually quite similar to algorithms proposed in top-k arm identification: I believe some appropriate acknowledgement is missing in the paper.
4. The wording "set ordering" in misleading: the goal of this paper is not to recover the set ordering but simply identifying the top-k actions in the regret minimization setting.
questions: questions: See comments above.
limitations: limitations: N/A
paper_summary: paper_summary: This paper generalizes the best $k$-arm identification problem to Gaussian processes with the goal to estimate the set of the best $k$ function evaluations $f(x)$ on a finite domain $X$, where $k=1$ corresponds to standard Bayesian optimization. The proposed regret notion is a natural adaptation of the common regret $f(x*)-f(x_t)$ in Gaussian process bandits.

The paper is accompanied by some first experiments on benchmark datasets.
strength_weakness: strength_weakness: Finiteness assumption seems rather strong and limits this work. Also, the significance of the results (Thm 3.7 and 4.4) is not fully clear to me, as the paper seems to be mostly relying on known techniques (for kernelized bandits, and Gaussian process bandits), while the related work is not sufficiently well discussed (see questions and limitations).

Am happy to raise my score, if my concerns are addressed. Specifically about the comparison to previous and related literature.

The definition of $\pi_*(X_0,X_1)$ seems only partial, i.e., what if there exists some $x_0$ that are larger than some $x_1$ and some $x_0'$ that are smaller than some $x_1'$

Minor comments:
* The notation is a bit convoluted. E.g., do you really need double bars and dashes for $x$. Even just tilde&dash is not great. E.g., in the beginning of section 3 you could just do $x,x'$ without the tilde (or you use $y$ etc.).
* Please do not mix definitions (in particular of important notation) and lemmas (e.g., Lemma 3.6, 3.1, ...).
questions: questions: What is the computational complexity/runtime of your approach? Is the runtime exponential in $k$?

How does your work relate to Gaussian bandit papers with correlated/dependent arms (e.g., Gupta et al. 2021, Pandrey et al 2007)

How does the results here relate to e.g., the "Interactive submodular bandit" by Chen et al. [ICML, 2017] (and related), where a submodular function is maximized in a similar fashion (in a GP-style context). Can your $k$ best selection problem be cast as a submodular (or even simply modular) set optimization problem? Are the two regret variants comparable?
limitations: limitations: The finiteness assumption on $X$ seems rather restrictive. Can $X$ be countable, or even say a compact subset / interval? Standard work on Gaussian processes with regret bounds (Srinivas et al., etc.) does not have this restrictions. For finite $X$ less assumptions might be possible, see e.g., Theorem 1 by Krause & Ong (NeurIPS 2011) (for example, no explicit assumptions on the rkhs norm as you do in Lemma 2.2, which they only require for arbitrary domains $X$).

Also in general the related work is not discussed sufficiently well, see questions.

Please, also see the questions.
paper_summary: paper_summary: The paper poses a novel active learning problem formulation of active set ordering, in which we aim to identify the data points that yield the top- and bottom-$k$ values via a given objective function.
This active learning goal serves as a compromise between Bayesian experimental design which focuses solely on learning and Bayesian optimization targeting optimization, and poses as an alternative to level-set estimation, especially in scenarios where a level-set threshold is not easily determined.
The authors first define an appropriate metric of regret, propose using the mean prediction of the surrogate Gaussian process to generate an ordering of the data points to recommend to the user, and finally develop an acquisition function that aims to reduce an approximation of the regret resulting from that posterior predictive ordering.
The paper presents various theoretical results bounding the regret of the proposed algorithm, and experiments are conducted to illustrate the empirical effectiveness of the algorithm.
strength_weakness: strength_weakness: - The presentation of Sections 3 and 4 is a bit hard to follow.
I understand Section 3 serves as the base case where we develop the core tools which are then further extended in Section 4, but the narrative has a jumping-back-and-forth feel that I find somewhat confusing.
- The claims the authors make in Section 1 to motivate the problem might be too strong.
I would say something along the lines of, this work presents an alternative to LSE when setting the threshold is difficult (as opposed to that it should replace it, since sometimes a desirable threshold is known, in which case LSE should be preferred).
- I would include LSE acquisition functions (e.g., STRADDLE) among the baselines in the experiments.
questions: questions: - The search space sizes in the experiments are quite small.
Does the algorithm scale well to large search spaces?
What’s the computational complexity?
Does it take quadratic time with respect to search space size (because we need to iterate over all pairs)?
- Any insights on how the different variants behave and which should be preferred in which situations?
limitations: limitations: Yes.
paper_summary: paper_summary: This submission proposes a novel Mean Prediction (MP) method for active set ordering problem. MP selects pre-defined k inputs with highest Gaussian Process posterior mean values through a novel sampling strategy. Theoretical analysis on the regret, the prediction and the sampling strategy of proposed method is discussed in details, and experiments on synthetic functions and real-life application prove the effectiveness of MP for ordering sets of inputs based on expensive evaluation on black-box function. The submission includes GP-UCB Bayesian optimization as a special case of active set ordering problem.
strength_weakness: strength_weakness: 1.  My first concern regards the dimensionality of the problem setting. The theoretical justification of MP seems valid for any value of $d$ where $d$ is the dimension of the black-box function. However, in the Experiments section all the problems are 2-dimensional, which is insufficient to show how practical the proposed MP method could be in applications. 

2.  This sampling-based method only works on discrete space problems to me. The authors use classic GP model on continuous space as the surrogate model to compute posterior mean, but then sample on the discretized space during inference. This could be one of the major limitations of MP method because a lot of probabilistic information has been missed during the discretization.
questions: questions: 1.  I'm not very convinced by the experiment design. For example the experiment on Goldstein-Price function (lines 248-251), the input domain is discretized into 100 points and a top-5 set based on posterior mean is sampled at each of the 100 iterations. Even repeated sampling is allowed in this paper, I still feel like almost the whole space which only consists 100 points has been sampled by doing so. How do the authors justify the efficiency compared to brute force sampling over the whole sample space?

2.  In all experiment settings, the 100/400 points that represent the input domain $\mathbf{X}$ are randomly sampled from normalized domain $[0, 1]^2$. If I understand correctly, each $\mathbf{X}$ of the 15 repeated experiments is different, which lead to 15 different $S_{\mu_t}(5)$ at the end of iterations. How do the authors decide which one of the $S_{\mu_t}(5)$ is the true top-5 set for the objective black-box problem? (e.g. which 5 locations are the top-5 with highest $NO_3$ concentration in Lake Zurich?)

3.  Could the authors explain how $S_{\mu_t}(k)$ is constructed in line 3 of Algorithm 1? Are the posterior mean of all the points in $\mathbf{X}$ evaluated? Similar for $(\mathbf{\bar{x}_t}, \mathbf{\bar{x}'_t})$ (line 4), are all possible pairs in $S_{\mu_t}(k)$ evaluated?
limitations: limitations: See above for limitations.

Comments: title: Thanks to All Reviewers and the Area Chair
Thank You for Your Reconsideration and Score Enhancement
Thank You for Reconsidering Our Submission and Raising the Score
Thank You and Further Clarification Regarding LSE
Thank You for Your Reconsideration and Improved Score
comment: We would like to thank all reviewers for your time, effort, and valuable feedback in reviewing our work, and to the Area Chair for coordinating the process. We greatly appreciate your patience in considering our responses and for your decision to raise the scores and maintain a supportive evaluation. It is our sincere hope that we have adequately addressed your concerns and questions regarding our paper. We will carefully incorporate your comments and suggestions in our revision.
We're glad to hear that you found our results very interesting. Thank you once again for reviewing our paper. If you have any further questions or insights, please feel free to share them, and we will be happy to address them during the remaining time of the discussion period.
Thank you for the prompt response, the results are very interesting.
Thank you very much for reviewing our response and for appreciating our additional experimental results, as well as for improving the score. We are glad to hear that our new baseline designs align with your suggestions. If time allows, we hope to address any remaining questions. Accordingly, we have conducted experiments with RandNoRepl and VarNoRepl on Branin-Hoo $\mathcal{S}(5)$ with $100$ iterations.
The results are presented below (together with the results of Rand, Var, and MP in the plot in the paper for reference).

| Iteration   | 20         | 40         | 60         | 80         | 100        |
|-------------|------------|------------|------------|------------|------------|
| Rand        | 4.80+-1.49 | 1.11+-0.23 | 0.34+-0.07 | 0.25+-0.06 | 0.32+-0.04 |
| RandNoRepl  | 1.68+-0.39 | 0.58+-0.14 | 0.43+-0.08 | 0.32+-0.05 | 0.20+-0.03 |
| Var         | 0.64+-0.11 | 0.34+-0.07 | 0.34+-0.07 | 0.23+-0.05 | 0.23+-0.03 |
| VarNoRepl   | 0.64+-0.11 | 0.37+-0.07 | 0.39+-0.10 | 0.29+-0.08 | 0.29+-0.08 |
| $\bar{\mathbf{x}}_t \wedge \bar{\mathbf{x}}_t'$    | 0.46+-0.07 | 0.29+-0.06 | 0.17+-0.05 | **0.07+-0.02** | 0.05+-0.02 |
| $\bar{\mathbf{x}}_t \vee \bar{\mathbf{x}}_t'$ | 0.56+-0.10 | 0.19+-0.04 | 0.17+-0.05 | 0.11+-0.03 | 0.12+-0.03 |
| $\bar{\mathbf{x}}_t\ \vartriangle\ \bar{\mathbf{x}}_t'$   | **0.42+-0.07** | 0.23+-0.05 | **0.14+-0.04** | 0.09+-0.03 | **0.04+-0.01** |
| $\bar{\mathbf{x}}_t\ \triangledown\ \bar{\mathbf{x}}_t'$   | 0.44+-0.09 | **0.16+-0.03** | 0.18+-0.05 | 0.13+-0.03 | 0.08+-0.02 |

We observe that RandNoRepl significantly outperforms Rand. However, VarNoRepl performs similarly to Var, as Var is designed to reduce uncertainty across the entire input domain. Due to this characteristic, Var tends not to sample the same input repeatedly when many inputs remain unsampled. Consequently, Var and VarNoRepl behave similarly in the early stages (similar regret). Only when a sufficient number of observations have been made does Var, due to correlations among evaluated inputs, begin to select repeated samples and diverge from VarNoRepl.

However, since Rand, RandNoRepl, Var, and VarNoRepl are not specifically designed to target the top-$5$ set, our solutions continue to outperform them.

We forgot to mention that in both the Branin and Goldstein experiments, all algorithms were initialized with a set of $3$ observations. As a result, in the final $3$ iterations, RandNoRepl and VarNoRepl were required to select repeated samples.

We will incorporate these baselines and the discussion into the revised paper, and we sincerely hope this will address any remaining questions you may have.
Thank the authors for the response. RandNoRepl and VarNoRepl experiments are interesting and they do perform well given 100 iterations as I expected. By performing the additional comparison to them I'm more convinced by seeing how the proposed MP method close up the regret in fewer iterations for the Goldstein-Price case. 

This is an interesting idea in general. I'll raise my score to 5.

If the authors have time, I'm interested in a comparison between RandNoRepl, VarNoRepl and MP methods on case where both MP and other baselines took all iterations budget to close up the regret in original setting. (e.g. compare RandNoRepl, VarNoRepl and MP methods on Branin-Hoo S(5) with 100 iterations)
We sincerely appreciate your reconsideration of our work and the increase in the score. We will carefully incorporate your valuable suggestions into our revisions to enhance the quality of our work. In the meantime, we remain open and eager to provide any further clarifications you may need.
Thank you for your response and for the score in support of our submission. We are eager to address any concerns you may have about our paper, so we would like to provide more details on
1. Why comparing an LSE solution with our proposed solutions in the experiments is not straightforward.
2. While LSE and finding the top-$k$ set are not empirically comparable, our theoretical analysis suggests that our solutions are as efficient as an LSE approach, even though the top-$k$ problem presents greater computational challenges.
3. Our solutions are preferred in the scenario you mentioned, specifically, when setting the threshold as a quantile of the observed data, compared to LSE.

---

**Empirical comparison**

We agree with the reviewer that in practice, the threshold can be set as a reasonable quantile of the observed data. However, in our problem setting, we are only provided with the size of the top-$k$ set (i.e., the number $k$) without any information about the threshold. This lack of threshold knowledge is one of the key motivations behind our proposed problem, as highlighted in the introduction (lines 25-26):

> "However, without domain knowledge of the black-box function, it is easy to set a threshold that leads to undesirably large or small level sets."

Therefore, running LSE with only this information (i.e., $k$) is not feasible.

If we were to apply LSE with a threshold based on a quantile, the resulting superlevel set would differ from the top-$k$ set in our problem, making a direct comparison between the two methods invalid. This is because estimating a larger set often requires more samples than estimating a smaller set empirically. Additionally, even if we were to carefully select a threshold so that the superlevel set matches the top-$k$ set, the comparison would still be unfair, as the threshold is computed using the knowledge of the true top-$k$ set that is assumed to be unknown in our problem setting and should not be utilized by any solution.

---

**Theoretical Implication**

While LSE and finding the top-$k$ set are not empirically comparable for these reasons, our theoretical discussion on the upper bound of cumulative regret suggests that our solutions are as efficient as the LSE approach in [8], which is an improved version of STRADDLE.
This is particularly noteworthy since our problem may be inherently more challenging than LSE. For example, if the black-box function is known, identifying the level set given a threshold can be done by simply comparing all function evaluations against the threshold, which requires a time complexity of $\mathcal{O}(n)$, where $n$ is the size of the input domain. However, finding the top-$k$ set (for $k > 1$) involves using a heap data structure, resulting in a time complexity of $\mathcal{O}(n \log k)$, which is more computationally demanding.

---

**Motivation for Our Solutions over LSE**

Finally, we would like to emphasize that your observation about the practical use of LSE, where the threshold is chosen as a reasonable quantile of the observed data, precisely highlights the need for our work.

For simplicity, consider a scenario where the input domain consists of 100 points, and the desired level set corresponds to the third quartile (i.e., 25\% of the data points have function evaluations at or above this threshold). One could set $k = 100 \times 0.25 = 25$ and use our solutions to discover the top-$25$ set. The boundary of this top-$25$ set should correspond to the level set they wish to find, without the need to estimate the threshold (such as the third quartile).

In contrast, if one were to use LSE, they would need to estimate the threshold as the third quartile from the observed data. This estimation could be inaccurate in practice due to noise in the observation and a limited number of initial observations. Therefore, even aside from sample efficiency, our proposed solutions are more desirable than LSE in such scenarios.
Thank you for the detailed reply. You are also absolutely right, that the problem is not well-defined in the continuous case. I raised my score.
Thank you for your rebuttal.

Regarding LSE, what some do in practice is, for example, to set the threshold to be at some reasonable quantile of the observed data. My goal is to see how much improvement in terms of regret your proposed method leads to compared to naively using LSE in that way in your setting.

Overall, I will keep my score.
Thank you very much for your reconsideration and the improved score. We sincerely hope that any previous concerns have been satisfactorily addressed, as we did not identify any remaining issues in your latest comment. We truly appreciate the discussion and will carefully integrate your valuable feedback into the revised paper. Please do not hesitate to reach out if you require any further clarification until the end of the discussion period.
Thank you for your responses. I have increased my score to 5.