Preference-based Pure Exploration
Authors: Apurv Shukla
Debabrota Basu
Venue: NeurIPS 2024 poster (2024)
Keywords: Pure exploration
multi-armed bandits
vector-valued rewards
preferences
Primary area: bandits
TL;DR: A new algorithm for vectorial optimization under bandit feedback

Abstract: We study the preference-based pure exploration problem for bandits with vector-valued rewards and a set of preferences imposed over them. Specifically, we aim to identify the most preferred policy over a set of arms according to the preferences induced on the reward vectors by an ordering cone $C$. First, to quantify the impact of preferences, we derive a novel lower bound on the sample complexity for identifying the most preferred arm with confidence level $1-\delta$. Our lower bound shows that how the geometry of the preferences and reward vectors changes the hardness of this problem. We further explicate this geometry for Gaussian distributions of rewards, and provide a convex reformulation of the lower bound solvable with linear programming. Then, we leverage this convex reformulation of the lower bound to design the Track and Stop with Preferences (TSwP) algorithm that identifies the most preferred policy. Finally, we derive a new concentration result for vector-valued rewards, and show that TSwP achieves a matching sample complexity upper bound.

Preference-based Pure Exploration
Apury Shukla"
Debabrota Basu
Department of ECE, Texas A&M University College Station, TX 77840 apurv. shukla@umich edu
Équipe School, Univ. Lille. Inria, CNRS Centrale Lille, UMR-9189 CRISIAL, France debabrota, basu@inria.
Abstract
We study the preference-based pure exploration problem for bandits with vector- valued rewards. The rewards are ordered using (given) preference cone C and our goal identify the set of Pareto optimal arms. First, quantify the impact of preferences, we derive a novel lower bound on sample complexity for identi- fying the most preferred policy with confidence level 1 5. Our lower bound elicits the role played by the geometry of the preference cone and punctuates the difference in hardness compared to existing best-arm identification variants of the problem. We further explicate this geometry when the rewards follow Gaussian distributions. We then provide a convex relaxation of the lower bound and leverage it to design the Preference-based Track and Stop (Pre'TS) algorithm that identifies the most preferred policy. Finally, we show that the sample complexity of PreTSS is asymptotically tight by deriving new concentration incquality for vector-valued rewards.
1 Introduction
Following COVID-19, the importance of reliable clinical trials and corresponding data acquisition to design effective drugs has gained wider recognition. However, conducting large-scale clinical trials is cost and time intensive as it requires working with large number of patients and following up their medical conditions over time. In the past two decades, this has led to doubling in the cost to bring drug to the market, i.e., $2.6 billion with 12-year drug development horizon and 90% failure rate during the clinical trial (Mullard 2014) [Snn et al. 2022). However, due to the rise of systematic data acquisition about biological systems, pharmaceutical firms interested
in harvesting the collected data for drug discovery (Gaulton et al., 2012 Reker and Schneider 2015). Thus, machine learning-basse -baeed methods increasingly studied and deployed as promising avenue for identifying potentially successful drugs with less patient involvement, increasing the "hit rate", and speeding up the development process (Jayatunga et al. 2022 (Smer-Barreto al.) 2023; Sadybekov and Katritch 2023) Hasselgren and Oprea, 2024). But deciding whether a drug successful depends on multiple and often conflicting objectives regarding safety, efficacy, and pharmacokinetic constraints (Lizotte and Laber, 2016). For example, COV-BOOST (Munro et al. 202T) demonstrates phase If vaccine clinical trial conducted on 2883 participants measure the immunogenicity indicators (e.g. cellular response, anti-spike IgG and 5T of different Covid- 19 vaccines as a booster (third dose). Experts decide how different indicators are preferred over one another, and above different thresholds (Jayatunga et al. 2022). This motivates us to study sequential decision-mi -aainn problem, where we aim to conduct minimum number of experiments to acquire informative data, and to reliably validate hypothesis with multiple objectives by imposing preferences over them.
'This work was when the author was Texas A& University. The author currently at the University of Michigan, Ann Arbor.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Problems of such nature can be modeled as a multi- multi-armed bandit (in brief, bandits), which is an established framework for sequential peccision-making under uncertainty (Lattimore and Szepesvári 2020). In bandits, a learner has access to an instance of K decisions (or arms). Each arm k E (T....; } corresponds to probability distribution Px of feedback (rewards) with unknown mean 14.. At each step & E N, the learner interacts with the instance by taking a decision k, (analogously pulling an arm), and observes a noisy reward RG from the corresponding distribution of rewards Pk.. The goal of the learner is to identify the arm with the highest expected reward over a certain confidence level through minimum number of interactions with the instance. This is popularly known as a fixed- confiddene Best Arm Identification (BAI) in bandit literature (Jamieson and Nowak 2014: Garivier and Kaufmann, 2016; Soare et al. 2014), which is a special case of pure exploration problems (Even-Dat Dar et al.] 20066; Bubeck et al.] 2009 Auer et al. 2016).
The bandit literature spanning over a century mostly focuses on a scalar reward, i.e., a single objective. In our problem, each reward Rg is a real-valued vector of T. E N objectives, and thus, the unknown mean vector of each arm M₁ E TR4,, Since the objectives can be often conflicting, there might not exist a single best arm. Rather, there exists Pareto Optimal Set of arms (Drugan and Nowe 2013 Auer et al. 2016). Given a set of preferences over the objectives, the Pareto Optimal Set consists of arms whose mean vectors dominate the mean vectors of any other arm outside the set. Keeping generality, we assume that preferences are defined by a cone of vectors C R Every induces set of partial incomplete orders over the L objectives (Jahn et al. 2009 Löhne 2011). Given the preference cone C, we aim to exactly identify the complete Pareto Optimal Set with a confidence level (1-8), 8) [0, 1) using as few interactions as possible. We refer to this problem Preference-base Pure Exploration (PrePEx). Recently, Auer et al. (2016); Kone et al. 2023abb); crepon et al.) (2024) consider special case of PrePEx, where the preference is known. To the best of our know ledge,
Ararat and Tekin (2023) mndKKoraazz et al. (2023) are the only studies of PrePEx from frequentist
and Bayesian angles, respectively. Here, we consider a frequentist approach as in (Ararat and Tekin 2023). However, their goal is to identify points that are in the Pareto Optimal Set or very close to it. In contrast, we focus on exactly identifying the Pareto Optimal Set. Additionally, AArart and Tekin (203) propose a gap-based elimination algorithm to solve the problem that generalises the algorithm Even-Dar et al. (2006). But in BAI, there is another paradigm of designing efficient algorithms that solves and tracks the exact lower bound on the expected time to identify the best arm (1 - 5) correctly (Garivier and Kaufmann 2016 Degenne and Koolen 2019). We explore this paradigm for
PrePEx and ask two questions:
What is the exact lower bound of PrePEx for identifying the Pareto Optimal Set, and how design computationally tractable algorithm matching this bound?
We address them affirmatively in our contributions:
Lower Bound for PrePEx. In Theorem 3.1 we study hardness of PrePEx problems by deriving the novel lower bound on the expected sample complexity of any algorithm to yield the exact Pareto Optimal Set with confidence (1 5). The challenge here is to extend the classical BAI lower bound GGariierr and Kaufmann 2016 to set of confusing instances given C. We observe that unlike BAI, distinguishability of two arms in PrePEx depends on their projections on the cone polar to C. We also show that our lower bound generalises the lower bound for pure exploration under known constraints (Carlsson et al. 2024). Additionally, we provide an exact characterization the lower bound further for Gaussian reward distributions in Theorem 3.2. It shows that the hardness depends on the bilinear projection of the mean matrix of arms onto the boundary of a normal cone of policies and the preferences. This is novel w.r.t. the existing gap-dependent lower bounds that hold either for a narrow range of N4a 's (Ararat and Tekin 2023), or fixed preference (Kone et al., (023a).
Algorithm Design. First, we observe that the optimisation problem in our lower bound involves minimisation over non-convex set. We provide a convex relaxation of the problem based on ideas from disjunctive programming (Thcorem 4.1 and 4.2 We then leverage this lower bound to propose a novel Track-and-Stop (Garivier and Kaufmann 2016) style algorithm, called PreTTS (Preference-based Track-and-Siee -Soop). In Theorem 4.3 we devise new stopping rule that can handle the geeference--ligned suboptimality gaps between the arms.
3. Sample Complexity Analysis. Finally, we provide an upper bound on sample complexity of PreTS. This requires us to define a distance metric between two pareto sets of arms, and proving concentration bound with respect to this metric (Theorem In Theorem 5.2 we prove that sample complexity of PreTS matches the convexified lower bound up to constants.
2

---

1.1 Related Works
In the past decade, works on multi-armed bandits also focuses on pure-exploration in addition to regret minimization. Regret minimization and exreeexploration differ in the sense when arms in pure-exploration are immediately discarded upon being deemed as sub-optimal, whereas, in the regret minimization setting, sub-optimal arms may still be played since they provide additional information about other arms. Pure-exploration problems have been considered in two settings: fixed-budget and fixed-confidence. The fixed reed-btdget setting aims at bounding the probability of underestimating the best arm given budget of samples. Audibert and Bubeck (20TO) propose the first algorithm for the fixed budget setting. Here, the budget is divided into K -1 rounds and at the end of every round, the arms with the lowest empirical mean are discarded. On the other hand, best-arm identification is a version of the pure-exploration problem with scalar rewards (Even- -ar et al. 2006). In this setting,
given a 5 E (0, 1) and the goal is to identify the best-arm with probability at least 1 - 8. Several strategies such as those based on elimination, adaptivity, racing, upper-confidence bounds have been proposed minimize the number of expected pulls of an arm in the fixed confidence setting by (Kalyanakrishnan et al. 2012 Gabillon et al. 2012: Jamieson et al., Jedrr Jedra and Proutiere (2020). Arm rewards can be modeled
2014 Garivier and Kaufmann 2016
vector with Gaussian Process (Zuluaga et al. 2016)) linear rewards (Drugan and Nowe 2013 Lu
ct al. 2019), , and non-parametrie rewards (Turgay et al. 2018), which can include contextual bandit formulations (Tekin and Turgay| [017 Shukla 2022). In recent past, the pure exploration techniques
have been successfully applied in hyperparameter tuning et al., 2018) and black-box optimization
problems (Contal et al. 2013 Wang et al. 2021 2022) demonstrating considerable performance
gains.
In a marked deviation, given an instance of the bandit problem, the goal of this paper is to identify the entire Pareto front. A key observation in this regard is that there might be arms, which are sub-optimal for almost every objective but still lie on the Pareto front. Further, since sampling an arm returns a vector of rewards determining an arm-strategy that reduces the uncertainty in the estimate of every reward function is challenging. An immediate consequence of these differences is the fact that the complexity of identifying the Pareto front is different from that of best arm identification. [Auer itt al. (2016) consider the Pareto front identification problem in the multi-armed bandit model and establish sample complexity bounds for the problem in terms of relevant problem parameters in the fxee-confidence setting. The multi-armed bandit problem is further studied under cone- based preferences by Ararat and Tekin (2023). The main contribution of (Ararat and Tekin, 2023) are bounds on the sample complexity of the problem in terms of gap-based notions that depend on the cone. Karagözlú et al.) (2024) builds upon this work to introduce adaptive elimination based algorithms for learning the Pareto front under incomplete preferences. When the reward vectors are Gaussian processes Korkmaz et al. (023) propose an elimination based algorithm based for identifying the Pareto front. The goal in these works is to identify the set of arms that are close to the Pareto front as the sample complexity to identify the exact Pareto set can be very large. Kone et al.) (2023a) consider the problem of identifying a relevant subset of the Pareto set using a single sampling strategy Adaptive Pareto Exploration. along with different stopping rules to consider variations of the Pareto Set Identification problem. crepon et al. (2024) consider the exact Pareto front identification problem in the multi- bandit setting but with fixed and known preference cone. They propose a lower bound and computationally efficient gradient- based algorithm implement track-an and-stop based strategy. To the best of our knowledge, ours is the first work to consider the exact Pareto front identification problem from a pure-exploration perspective. Therefore, our proposed framework can be used for identifying the Pareto front given a preference cone for several variants of the bandit problem including the standard multi-armed bandit problem, linear bandits, etc.
2 Preference-based Pure Exploration Problem
In this section, we formalise the fixed-confidence setting of preference-based pure exploration and introduce the notations.
Notations. For n E N, let [n] denote the set {1, 21. We use || 112, - llz, || oo to denote the -i-nr,, form and norm, respectively. For vector z, 200) denotes its gth component. Let e, denote the vector with in the 9th position and zero otherwise. Ax denotes the simplex on [K].
dx1. (P, Q) measures the KL.-divergence between distributions and Q. (A) is the vectorized version of matrix A. 1 is the vector of all I's. Further details of notations are deferred to Appendix A
3

---

PrePEx: Problem Formulation. In PrePEx, learner can access bandit instance with K arms. Each arm k E [K] corresponds to a reward distribution P. over R with unknown mean Mr RR' and known covariance Σ =
................................ of) Here, 7. denotes the number of objectives corresponding to each arm. Thus, a bandit instance can be specified with the vector of mean rewards {M J For brevity, we represent them with a matrix M E IR
r.x K such that its hhhh column is My. At each time t e N, the learner pulls an arm k E [K] and observes the corresponding reward vector R2 sampled from Vk. In pure exploration, the learner typically focuses on finding the best arm, i.c. the arm with highest mean (Garivier and Kaufmann| 2016). In pure exploration, a more general setting of BAI, the learner aims to find policy и E Ax that dictates the arm-proportion to choose to maximize the expected reward from the instance.
Following the vector optimization literature (Jahn et al. 2009) Ararat and Tekin 2023). we assume that the learner has additionally access to an ordering cone C.
Definition 2.1 (Ordering Cone). A ser C C IR. is called cone if C implies that ou E C for all 2 0. A solid cone has a non-empty interior, i.e., int(C) + V. A pointed cone contains the origin. closed convex, pointed and solid cone is called an ordering cone.
An ordering cone can be both polyhedral and non-polyhedral. Following the literature (Ararat and Tekin 2023 Karagözlü et al. 2024), we consider access to a polyhedral ordering cone.
Definition 2.2 (Polyhederal Ordering Cone). An ordering cone C is polyhedral cone if - {or E R+| Ax 2 0}, where A E KXL with rows o!_ A is called the half-space representation o
Each polyhedral ordering cone induces a set of partial order on the reward vectors in R2, To ignore the redundancies and to focus on the bandit problem, we further assume that A is full row-rank and ||A: = AAarat and Tekin 2023). Hereafter, we call them preference cones, and the vectors the cone as the preferences. We refer to (Jahn et al.) 2009 Löhne 2011) for further details on cones.
Example 2.1 (Preference cones). The positive orthant R4 is a polyhedral ordering cone. This is the one used in the pareto-set identification literature (Auer el al. 2016 Kone et al.) 2023b crepon el al.
2024 The cones with all non-negative entries are called solvency cones and used in finance Kabanov
2009 Another simple example is Cx/3 & {(r cos 0, r sin 0) E RRR |r 2 AA0 E [0,x/3], iee,
the 2 2-dimensional vectors that make an angle less than π. 3/3 with the x-axis.
Definition 2.3 (Partial Order). For every J.. p. E RR,, 1r Ze n¹ if μ E p² + C and e <e p if 14 E μL + (C). Alternatively, f Sc pl is equivalent to 2 (μ - R²) S 02
The partial order induced by C induces further order over the set of arms [K].
Definition 2.4 (Order over arms). Consider two arms i. [K] Arm is weakly dominated by arm j iff M, Ze My. (ii) Arm dominates arm iff M; <cx(0) M,. (iii) Arm strongly dominates arm j iff Mj <c M,
14
n/2
1//
12
Definition 2.5 (Pareto Optimal Set). An arm i E [K] is Pareto Optimal if it is not dominated by any other arm w.E. the cone C. The Pareto Optimal Set P defined as the set of all Pareto Optimal arms.
Given a preference cone, a learner aims identify exactly the Pareto Optimal Set from a finite set of arms [K] whose mean rewards belong to the Pareto Optimal Set w.r.t. C. Alternatively, this vector optimization problem can be represented in the policy space as finding a policy π E AK supported on the Pareto Optimal Set of arms. The following vector optimization problem yields this:
Objectio
Figure 1: Effect of cone selection on size of Pareto optimal set
V(M) A max Mn over C.
(1)
TEAN
In this context, we denote the set of Pareto optimal policies as II* & arg max MT over C. We assume that ITT IT* (M) is non-empty.
Example 2.2 (Pareto Optimal Sets for different cones). Figure illustrates the Pareto Optimal Sets among 2 2-dimensional mean vectors of 200 randomly selected arms under preference cones Ca/2

---

and Cr/33 We observe that the Pareto Optimal Sets for them (in pink and blue respectively), are completely different for the same set of arms. Thus, we have adapt to the available preferences to solve the aforementioned problem. As noted later, the geometry of this cone plays crucial role in determining the Pareto front.
In PrePEx, we consider the problem of Equation ① when the mean matrix M is unknown priori but bounded, i.c.. the entries of M, Ma E [Mminn Mmax] We denote all such mean matrices by M. Identifying the policy will lead us identify the true Pareto front P In the noisy feedback setting, the reward at time t is Rg = Mr, + Tt, where тe E IR- is the noise vector. We assume that the noise vectors ?) are independent of Ms, and also across time. Further, they are Gaussian with parameter a and adapted to the filtration Fi, which is standard assumption in the literature. A policy E C A K is a randomized mapping from the history H4 the probability simplex over the set of arms [K]. In Preference- based Pure EXploration ( (PrePEX) problem, the goal of the learner to identify a Pareto optimal policy in II* (Equation (T) given an instance M and a preference cone C while observing only noisy rewards from the arms, and also using as few observations possible.
Definition 2.6 ((1 - co-rrrt PrePEX). An algorithm for Preference- based Pure Exploration (PrePEx) is said to be (1 -6 5) correct if with probability 1 - 6, it recommends Pareto optimal policy т E IT".
For example, a pareto optimal policy for C2/2 would be a distribution AK with support on the arms corresponding to the pink reward vectors (Figure D. For Ca/3, it would be one with support on blue points. Finally, we make the standard assumption on the mean rewards.
Assumption 2.1 (Single Parameter Exponential Family). Let X (X1,, Xa) be a d-dimensional random vector with a distribution Pa.0 0 E O. Suppose XI...., Xa are jointly continuous. The family of distributions {Po, 0 E O) is said to belong to the one parameter Exponential family if the density of X may be represented in the form (x]00) & h(x) exp (n(()]((z) (0)). We assume that the mean reward for each vector belongs to a single-parameter exponential foonnetiallamillyy with variance bounded by
3 Lower Bound on Sample Complexity
We begin by deriving a KL-divergence based lower bound for PrePEx using techniques from (Garivier) and Kaufmann| 2016). Our lower bound based on establishing a change-of-measure argument in the spirit of (Graves and Lai 1997: Kaufmann et al. 2016). The lower bounds are derived first by defining set of alternating instances A for a given bandit instance and then by trying compute an optimal allocation policy w E Ax that maximises the sum of minimum KL-divergence between any instance in A and the bandit instance under interaction. The key insight of our work to formulate the identification of Pareto Set problem in the policy space rather than in the arm space as done in antecedent literature. This formulation helps us to derive the KL-based lower bound, which is more general than the existing suboptimality gap-based lower bounds (Auer et al. 2016 Ararat and Tekin 2023 crepon et al. 2024).
The Alternating Instances with respect to Pareto Fronts. The learner needs to distinguish between all instance M E M \ {M) for which the Pareto front associated with M is different from the one associated with M. At first, given optimal policy of M, say n², it would appear that the set
of confusing instances is Ar- (M) A M E EM: Mx* zc max M } However, this is fallacious since the instances whose rewards dominate M can also confuse a policy ग. Given a x* the correct alternating set is the set of instances in M whose Pareto optimal set is not dominated by Tt corresponding to M.
Ax (M) a ME M. (M) max Ma Le Mn² well
M E Mi (M) 32 C s.t. max 2 Mm 2 Mn*
xell
With this new alternate set defined, we now establish lower bounds on the performance of any PrePEX algorithm.
Theorem 3.1 (Lower Bound). Given a bandit model M E M, a preference cone C, and a confidence level i E [0, 1), the expected stopping time of any (1 6) co-crrtect PrePEx algorithm, to identify the
5

---

Pareto Optimal Set is
Bir] 2 TM. log
(2)
2.45
where, the expectation is taken over the stochasticity of both the algorithm and the bandit instance. Here, TM.C is called the characteristic time of the PvePEx instance (M,C) C) and is expressed as
( inf inf Σ wxdkE (z SM, z Ms.
(TM.c)
A sup inf WEAR nell((a") MeDs, (Ad) ZEC Ell" (M)
(3)
such that a (M) & Um( {
(M :MEM:32er (vect (z(# te(==x))] vect (M7) = =0]-
Proof Intuition. First, we observe that an instance M is in alternating set if there exists a π E II f and C, such that 2 (TT - ) > O. If π and nt were pure strategies, it would have been exactly inl snrroc) = (M, Ma-) > O. Let us denote the achieving the inf as Finf; i.e., the preference for which M, and M,- are least distinguishable. Thus, we observe that =i M, exactly functions as the mean of the arm a in an instance M, whereas (M - Ma) acts as the suboptimality gap. Now, extend this idea in the classical lower bound scheme get a nested optimization problem with Ax. We further show
inf over C and M in the alternating set, and sup over allocations that the inf for M appears at the boundary of the alternating set defined (A(M).
Discussions. (i) Novelty: In the best of our knowledge, this is the first lower bound for PrePEx with fixed confidence with an explicit KL-based dependence. All the existing lower bounds are gap dependent, and valid for a narrow range on mean vectors or known preference cone, i.e. the right orthant. Our proof does not need such assumptions. The gap-dependent bounds are special case of ours (cf. Theorem 3.2 for the case of Gaussian rewards).
(ii) Geometric Insights. Theorem 3.1 provides multiple geometric insights into the affect of the ordering cone on the characteristic time. First, the alternating set Ag- (M) is piece-wise polyhedral and non-convex. We address consequent issues in Section 4.1] Second, there is an additional minimization over the vectors lying in the cone C. We interpret the minimization over vectors in the cone as a instance- and preference-deeeeden scalarization of the distance between the given instance M and the corresponding most-confusing instance in Ax. (M) Third, the proof, we show that the reward gap using the best policy π and a given policy π for the most confusing instance belongs the polar cone C of the preference cone C. The most confusing lies on the boundary of this polar cone and its projection the policy gaps (x* т). Further insights can be obtained by imagining the polar cone to be orthogonal the cone C. Then, the vector of reward-gaps for the most confusing instance for every objective is orthogonal to the generating rays of C. These novel geometric insights are complementary to the existing algebraic and statistical insights available in the lower bound literature (Kone et al. 2023a Ararat and Tekin 2023).
3.1 Characteraization of Lower Bounds for Gaussians
To understand our lower bound better and to compare it with the literature, present reduction for Gaussian bandits. In Gaussian bandits, we assume that the reward vectors of arm a E [K] are generated from a multivariate Gaussian distribution N M(p,, 2), where the covariance is diagonal matrix: Σ A Diag(of......
Theorem 3.2 (Lower Bound for Gaussian Bandits). 1. Given any πt" E (M) and N(x") being the sei of neighbouring policies of n², the most confusing instance of M belongs the set
o (TT π)k VT E N CV (O)0 [K] [41].
AM E M M.MM)
(M} MA.e- = MR.e
of
where B 2
IT M(
2. The inverse of characteristic time, i.e. (THaaue) for for an instance (M,C C) is
(2 MMT" =
inf min xeN(m') sEC x "ll'' (M)
2Tr E)] |T" -

---

Consequences. Pirst, we observe an interesting phenomenon that a bilinear projection of mean matrix M on the preferences and policy gaps operates as an extension of suboptimality gap in classical BAI. This is reminiscent of the lower bound for pure exploration under known linear constraints as in Carlsson et al. (2024) who show that the hardness of the problem depends only on the projection of the mean vector on the policy gap. In addition to similar projection structure, preferences introduce novel bilinearity here. Second, we show how the lower bound inflates with the covariance matrix for each objective. This shows the richness of our KL-divergence based lower bound as opposed to gap-based bounds which have difficulty accommodating variance related terms directly.
Connection to existing results. Our result generalizes several existing lower bounds for BAL
1. BAI lower bound. Our lower bound is able recover that of Kaufmann al. (2016) for the standard BAI problem with fixed confidence. In the case the standard BAT problem, the ordering cone is given by C & IR+ and therefore the minimization over C in (3) becomes redundant. The definition of the alternating set is then given by the set of instances which have different optimal arm than μa which is exactly the set considered in (Kaufmann et al. (016))
2. Pure exploration under known constraints. Our lower bound is able to recover the lower bound of Carlsson et al. (2023) for the BAI problem with fixed confidence and linear constraints. This the case with L, = and the ordering cone being å R2 making the minimization over 2 in (3) redundant. Ar- (M) becomes Ag- (M) {ī max ğ l 2 p [=T²) and we retrieve exactly their Corollary
4 Algorithm Design: PreTS
In this section, we propose an algorithm that tracks the lower bound. However, this is not straightfor- ward since the alternating set non-convex. We first propose a convex relaxation for this set and then, design Track and Stop style algorithm, called PreTS.
4.1 Convex Relaxation of the Lower Bound
One of the major differences regarding the structure of lower bounds compared to standard BAI problem is that Ag- (M) is a piece-wise polyhedron, i.e., a union of hyperplanes. Each hyperplance corresponds policy π II {π") To make the optimization problem tractable and obtain convex program, we relax Ar- (M) using its convex closure, denoted by ch (Ax- (M)). We note that the construction of such convex relaxation for track-and-stop (when the lower bound problem is non-convex) has been done in the MDP setting Al Marjani and Proutiere (202T). We define disjunctive program, which
ch (Ag- (M)) in Theorem 4.1 by formulating further as a linear program (Balas 1985).
reformulate
Theorem 4.1. Let JF A Uni EMM: E (vect (=T(T (T - T²)) ((---())
vect vec)(())) = =0). Fix
E C such that = = E; agui, Then, we have ch (F)= I, where I is defined as
I (M E M: TT vect(M) 2 70.7 E, uao,vec((o] (æ pom-r"y +))), no I u/ Σ, ano x*). x. (4)
Using the convex hull (Eq. (4)), we quantify the optimal value for given allocation
K
Ve(w M)
min
inf SEC
Σ
wedki
M, (M
M (AA, (M))
Am
The corresponding optimal allocation
wydka. (2 M, M7
wt (M) arg max WEAR
inf -
min
inf
(5)
Mrchh (M)) ZEC x Ell" (M)
Hereafter, consider Equation (5) as the optimization problem to be tracked. To compute Vo(w, M). we need access to the true instance M which is not available to us. Our Track-and-Stoo strategy is based on repeatedly sampling arm to construct estimate of M, i.e. M,, and exploiting continuity properties of Ve(w, M) to show that Ve(w, M,) - Ve(w, M) and the cunulative number of arm plays Nr, > ukk Wk E w= (M). These properties ensure that makes sense to design a Track and Stop style algorithm for this problem.
7

---

Algorithm Preference-based Track-and-Stop (PreTS)
1: Input: Confidence parameter ò, preference cone C
2: if supx; min (aA.; (Ai() minzec Ex ck (z (2MM, M, , (i(ik) 2 B(1, then
3: Compute f arg maX Velw, M,)
4: Play li <- arg [nine[[]] |NR, Ex=1 ws
5: Observe reward rz
6: Construct an empirical estimator Mr
7: end if
8: Construct a Pareto Front Prr from empirical means M,
9: Return: Pr
Theorem 4.2 (Analytical Properties). For all M BLxk and all preference cones C, we get The mapping (w, M) Ve(w, M) is continuous. 2. The characteristic time mapping M + Tar.c is continuous. The set valued function M + 8 (M) is upper-hemicontmmous The set w (M) is convex.
Discussion: Cost of Convexification. For Gaussian bandits, as we can get the analytical form of the most confusing instance (Theorem 3.2) 3.2). we do not pay any extra cost of convexification. In the non-Gaussian settings, where cannot find such analytical forms for the most confusing instances, the minimum value of the inner minimisation problem under the convex hull (Equation (5) can go lower than the minimum value found in the original non-convex set of instances (Equation (3) Thus, the characteristic time attained by solving the convex relaxation might be higher than that of the original lower bound. Hence, algorithm solving the convex relaxation has higher stopping time. However, convexification is essential for the computational feasibility of a lower bound-tracking trade-off will be interesting study in the
algorithm for PrePEx. This computational-statiien future.
4.2 Algorithm: Preference-based Track-and-Stop (PreTS)
We now construct a general recipe to design PrePEx algorithm when we do not have access to the true instance M. The fundamental element of any such recipe constructing an estimate of M. For a given set of observed rewards { RR ) we obtain column-wise empirical average of the observed rewards and use as our estimator of M. Now, we elaborate the three key components of our PrePEx algorithm Preference-based Track and Stop (Pre'TS, Algorithm TT.
Sampling Rule: For the sampling rule, we consider a Track-and-Stop strategy (Garivier and Kaufmann 2016). It tracks the optimal proportion of arm sampling by plugging in the empirical estimates means and empirical count Nr.1 in the convexified lower bound. This leads to an allocation policy with improved information acquisition.
2. Stopping Rule: Our ultimate stopping goal is to identify arms that are the Pareto front. Based on this, we define the confidence set as:
M: min Σ Ne.edxu(2 M(M) M()) B1,,0) sec
o(t,)) a M MEM E::::
(6)
where 3(1,0) = 31n (1 In (Nx.)) + KT In and defined in Equation (7.. Our
first claim is to show that the true instance belongs to the confidence ellipsoid with high probability. Lemma 4.1 (Confidence Ball). For any t E N and c(t, 0) is defined in Equation 66, we have (M & ctt, 8)) < 8.
Thus, we can now formalise the corresponding Chernoff-stopping rule as
NN, (2 STM (K) M (b) 2 (t,
min
min ZEC
M. (M))
Given the estimates M, the problem Equation 7 can be solved efficiently. Next, we show that upon stopping with Equation (7). PreTS returns the true Pareto Front Pd with probability 1 - d. Let

---

Pi denote the estimated Pareto Front at time t, which is constructed using estimates Mr Then at stopping time т, we have
(P=**17 s P
ELEN:
Σ
NR. (=TM, =T(( 2 8((,8)
20
Σ
P
Σ Ref
NR. (2 (aT M/ 2T M() 2 ((t,,) 2
where, the last inequality is true due to Theorem with preference projected mean rewards.
concentration result the KL-divergence
Theorem 4.3. For all 2 (K + 1), 2 E EC and E N, we have that:
(Iolx((51)
P
Σ KE
NK. (z M TM()) 2
S exp (-p)
exp (K + +
K
3. Recommendation Rule: At the end of stopping time т, the algorithm returns an estimate of the Pareto Front Pr..
Upper Bound on Sample Complexity
Now, we prove upper bound on the expected sample complexity of PreTS, This requires us to the Track-an-Stop proof technique. But the challenge is show concentration of the pareto fronts under a suitable metric.
Concentrating to the Pareto Front. To show that upon stopping the algorithm returns the true Pareto Frontier, we need establish a valid metric to show such convergence. Usually, the dis- tance between sets is measured using the Hausdorff metric (Costantimi and Vitolo 1995). i.c.
du (Pr. P) A max ( (suPker, inf || - Mr lloo suPkep inf || - My |loe But
the Hausdorff distance only defines pseudo-distance between sets and 2 may be closed under this metric. To circumvent this issue, we build upon the notion of gap-based metric considered in the antecedent literature (Auer et al. 2016) to measure the distance between the mean reward of an arm and a given Pareto Front. We extend it to a distance metric between elements in the space of Pareto Fronts Z.
Definition 5.1 (Distance from Pareto Front). The distance of the mean of arm k from the Pareto Front Pa is d(k, P*) & infezo such that Mà + el Re MR W. PP Equivalently.
d(k; PT) inf max {o, 0, sup = =T Ma) 3a) zECOB(1)
MEP-
Definition 5.2 (Distance between Pareto Fronts). We define the metric between Pareto Fronts dr (G:),)) x 2 R2o dp (p, pr max (supkee d(k, P"), suprep- d(k: P)}.
In the appendix, establish that (i) d(.; :) is valid metric Z, and (ii) 2 is compact and complete under d). Now, we leverage this metric to show that the Pareto Front defined by the arm-wise constructed estimator M, concentrates towards the true Pareto Front.
Theorem 5.1 (Concentration of mean estimates). For any pair (i.j) E [K] X [K] and z E C, we have
x (M, (M,) -
TT (Ni.. M3r) s (t)(t).
where (t) e 4||=11
log( (xp)
Eaetio) log (4 (oog(((((()))) (Enetio) Nete)) K e
K(K-1) and h(x)) log(z))

---

Proof Sketch. This is consequence of jointly applying a vectorial concentration result for multiple- objectives of each arm (Kaufmann and Koolen 2021). and pairwise time-nnform concentration bounds (Kone et al. 2023a). A key observation here is that the confidence radii depends on the magnitude of the preference vector z and scales with different objectives accordingly.
Sample Complexity of PreTT.. Using this new concentration result for the Pareto Front and the we derive an upper bound on the expected stopping time of PreTS.
stopping rule Equation 7
Theorem 5.2 (Upper Bound Sample Complexity). For any 0 and c(t,5) defined in 7
have that the stopping time satisfies
B log (t)
lim
&TM. M E
The basic outline of the proof follows a general strategy to prove Track-and-Stor result. However, the new arguments lie in establishing that the Pareto fronts converge under a suitable metric sufficiently fast. Our proof implies that PreTSS matches the convex relaxation of the lower bound asymptotically the corresponding risk level 8. Strictly, speaking this is asymptoticallly optimal since, we do not track the exact lower-bound.
Conclusion and Future Works
We study the fxeedcoofidence version of preference- based pure exploration problem under linear stochastic bandit feedback, where each arm corresponds to reward vector ordered according to preference cone. We derive a novel lower bound for this problem. We leverage the lower bound further to derive track-and-stop based algorithm for PrePEx problem. As future work, it would be interesting to verify our results on a real-world datasets.
Additionally, it would be interesting and challenging to study how other asymptotically optimal pure exploration strategies, e.g. gamified explorers (Degenne and Koolen 2019). top-two algorithms (Jour) dan et al. 2022), y can be adapted to this setting. In general, improving the computational efficiency and studying the optimality gap with respect to the non-convex lower-bound problem would be of fundamental interest.
References
Al Marjani, A. and Proutiere, A. (2021). Adaptive sampling for best policy identification in markov decision processes. In International Conference on Machine Learning, pages 7459-7468. PMLR.
Ararat, C. and Tekin, C. (2023). Vector optimization with stochastic bandit feedback. In International Conference on Artificial Intelligence and Statistics, pages 2165-2190. PMLR.
Audibert, J.-Y. and Bubeck, S. (2010). Best arm identification in multi-armed bandits.
Auer, P., Chiang, C.-K., Ortner, R., and Drugan, M. (2016). Pareto front identification from stochastic bandit feedback. In Artificial intelligence and statistics, pages 339-947. PMLR.
Balas, E. (1985). Disjunctive programming and hierarchy relaxations for discrete optimization problems. SIAM Journal on Algebraic Discrete Methods, 6(3):46-4886
Berge, C. (1877). Topological spacex: Including treulment of multi-valued vector spaces and convexity. Oliver & Boyd.
Bubeck, S., Munos, R., and Stoltz, G. (2009). Pure exploration in multi-armed bandits problems. In Algorithmic Learning Theory: 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009, Proceedings 20, pages 23-37. Springer.
Carlsson, E., Basu, D., Johansson, F., and Dubhashi, D. (2024). Pure exploration in bandits with linear constraints. International Conference on Artificial Intelligence and Statistics, pages 334-342. PMLR.
Carlsson, E., Basu, D., Johansson, D., and Dubhashi, D. (2023). Pure exploration bandits with linear constraints. arXiv preprint ar 131:22306.12774
10

---

Contal, E., Buffoni, D., Robicquet, A., and Vayatis, N. (2013). Parallel gaussian process optimization with upper confidence bound and pure exploration. Joint European Conference on Machine Learning and Knowledge Discovery in Databasex, pages 225-240) Springer.
Costantini, C. and Vitolo. P. (1995). On the infimum of the hausdorff metric topologies. Proceedings of the London Mathematical Society, 3(2):411
crepon, e.. Garivier, A., and M Koolen, W. (2024). Sequential learning of the Pareto front for multi- obulti-objective bandits. In Dasgupta. S., Mandt, S., and Li, Y., editors, Proceedings of The 27th International Conference on Arlificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Rexearch, pages 3583-3591, PMLR.
Degenne, R. and Koolen, W. M. (2019). Pure exploration with multiple correct answers. In Neural Information Processing Systems.
Donsker, M. D. and Varadhan, S. S. (1975). Asymptotic evaluation of certain markov process expectations for large time, Communications on pure and applied mathematics, 28(1):1-47.
Drugan, M. M. and Nowe, A. (2013). Designing multi-objective multi-armed bandits algorithms: A study. In The 2013 international joint conference on neural networks (LJCNN), pages 1-8. IEEE.
Even-Dar, E., Mannor, S., and Mansour, Y. (2006). Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(Ju)): (JJu)):109-1)) 1079-1109000 1105.
Gabillon, V., Ghavamzadeh. M., and Lazarie, A. (2012). Best arm identification: A unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems, pages 3212-3220.
Garivier, A. and Kaufmann, (2016). Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 10277
Gaulton, A., Bellis, L. Bento, A. P. Chambers, J., Davies, M., Hersey, A., Light, Y., McGlinchey, S., Michalovich, D., Al-Lazikani, B., et al. (2012). Chembl: a large-scale bioactivity database for drug discovery. Nucleic acids research, 40(D1): 40(D1):D1100-D110 100-D1107.
Graves, T. L. and Lai, incontrolled markov chains. SIAM journal on control and optimization, 35(3):715-743.
(1997). Asymptotically efficient adaptive choice of control laws
Hasselgren, C. and Oprea, T. I. (2024). Artificial intelligence for drug discovery: Are there yet? Annual Review of Pharmacology and Toxicology, 64:527-550.
Jahn, J. et al. (2009). Vector optimization. Springer.
Jamicson, K., Malloy, M. Nowak, R., and Bubeck, S. (2014). lil' ucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439.
Jamieson, K. and Nowak, R. (2014). Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE.
Jayatunga, M. K., Xie, W., Ruder, L., Schulze, U., and Meier, C. (2022). Ai in discovery: a coming wave. Nat. Rev. Drug Discov, 21(3):175-176.
drug
Jedra, Y. and Proutiere, A. (2020). Optimal best-arm identification in linear bandits, Advances in Neural Information Processing Systems, 0000007771017.
Jourdan, M., Degenne, R., Baudry, D., de Heide, R., and Kaufmann, E. (2022). Top two algorithms revisited. Advances in Neural Information Processing Systems, 15:26791-26803.
Kabanov, Y. (2009). Markets with Transaction Costs Mathematical Theory. Springer.
Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. (2012). Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pages 655-662.

---

Karagözlü, E. M., Yildırı, Y. C., Ararat, C., and Tekin, C. (2024). Learning the pareto set under incomplete preferences: Pure exploration in vector bandits. In International Conference on Artificial Intelligence and Statistics, pages 3070-3078. PMLR.
Kaufmann, E., Cappé, O., and Garivier, A. (2016). On the complexity of best arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17:1-42.
Kaufmann, E. and Koolen, W. M. (2021). Mixture martingales revisited with applications sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246):1-44
Kone, C., Kaufmann, E., and Richert, L. (2023a). Adaptive algorithms for relaxed pareto set identification. Advances in Neural Information Processing Systems, 36:35190-35222
Kone, C., Kaufmann, E., and Richert, L. (2023b). Bandit pareto set identification: the fixed budget setting. arXiv preprint arXiv:2311.0399
Korkmaz, O., Ararat, C., and Tekin, C. (2023). Bayesian vector optimization with gaussian processes.
Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.
Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., and Talwalkar, A. (2018). Hyperband: A novel bandit- based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(185):1-52.
Lizotte, D. J. and Laber, E. B. (2016). Multi-objective markov decision processes for data-driven decision support. Journal of Machine Learning Research, 17(210):1-28.
Löhne, A. (2011). Vector optimization with infimum and supremum. Springer Science Business Media.
Lu, S., Wang, G., Hu, Y., and Zhang, L.. (2019). Multi-objective generalized linear bandits. arXiv preprint arXiv: 12879.
Magureanu, S., Combes, R., and Proutiere, A. (2014). Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pages 975-999, PMLR.
Mullard, A. (2014). New drugs cost us $2.6 billion to develop. Nature reviews drug discovery, 13(12).
Munro, A. P., Janani, L., Corneluus, V. Aley, P. K., Babbage, G., Baxter, D., Bula, M., Cathie, K., Chatterjee, K., Dodd, K., et al. (2021). Safety and immunogenicity of seven covid-19 vaccines as a third dose (booster) following two doses of chadox1 ncov-19 bnt162h2 in the uk (cov-boost): blinded, multicentre, randomised, controlled, phase trial. The Lancet,
2276.
Peskun, P. H. (1973). Optimum monte-carlo sampling using markov chains. Biometrika, 60(3):607- 612.
Reker, D. and Schneider, G. (2015). Active-learning strategies in computer-assisted drug discovery. Drug discovery today, 20(4):458-44) 465.
Sadybekov, A. V. and Katritch, V. (2023). Computational approaches streamlining drug discovery. Nature, 6 616(7958):633-685
Shukla, A. (2022). Optimization and Learning in Dynamic Environments: Models and Algorithms. Columbia University.
V., Quintanilla, A., Elliott, R. J., Dawson, J. C., Sun, J., Campa, V. M., Morente-Macian Á. Unciti-Broceta, A., Carragher, N. O., Acosta, J. C., et al. (2023). Discovery of senolytics using machine learning. Nature communications, 14(1):3445.
Soare, M., Lazaric, A., and Munos, R. (2014). Best-arm identification linear bandits, In Advances in Neural Information Processing Systems, pages 828-836.
12

---

Sun. D., Gao, W., Hu, H., and Zhou, S. (2022). Why 90Acta Pharmaceutica Sinica B, 12(7):3049- 3062.
Tekin, C. and Turgay, E. (2017). oulti-objective contextual bandits with a dominant objective. In 2017 IEEE 27th International Workshop on Machine Learning for Signal Processing (MLSP), pages 6. IEEE.
Turgay, E., Oner, D., and Tekin, C. (2018). Multi-objective contextual bandit problem with similarity information. In International Conference Artificial Intelligence and Statistics, pages 1673-1681. PMLR.
Wang. J., Basu, D., and Trummer, I. (2022). Procrastinated tree search: Black-box optimization with delayed, noisy, and multi-fidelity feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 10381-10390.
Wang. J., Trummer, I., and Basu, D. (2021). Demonstrating udo: A unified approach for opti- mizing transaction code, physical design, and system parameters via reinforcement learning. In Proceedings of the 2021 International Conference Management of Data, pages 2794-2797.
Zuluaga, M., Krause, A., et al. (2016). e-pal: An active learning approach to the multi-objective optimization problem. Journal of Machine Learning Research, 17(104):1-32.
13

---

Appendix
Table of Contents
Notations
15
B
Proofs Lower Bounds)
Generie Lower Bound: Proof of Theorem
B.2 Lower Bound for Gaussians: Proof of Theorem
17
B3 Proof of Theorem 4.1
18
B.4
Proof of Theorem 4.2
19
Proof of the Stopping Time
20
Proof Lemma 4.
20
Proof Theorem
20
D Proofs for Sample Complexity Upper Bound
22
D. Pairwise Concentration Bounds
22
D22 Concentration to the Pareto Front
23
D.3 Proof of Theorem|5.2
25
Reduction to Best-arm Identification
Useful Existing Results
28
14

---

A
Notations
Notation
Description
C, Rev(0)
Given convex cone and induced partial order
K L
number of arms and objectives
Pt
Ground truth Pareto set and estimated Pareto set
Space of all Pareto Frontiers on [0, 1]
M E RxI.
matrix with mean reward of K arms observed reward, mean reward and noise Confidence ball at time t with confidence 8 Hausdroff distance between sets X and Y
Tke Ma. 1/
c(t,8)
dx(X, Y)
dp P, P)
Distance metric between Pareto Fronts and P
Allocation vector
II
Family of policies
Me,tt, Myk
Estimated and true of mean rewards
ch (5)
Convex hull of set S
Ay. (M)
Set of alternating instances associated with M
Table 1: Table of Notations
15

---

B Proofs of Lower Bounds
B.1 Generic Lower Bound: Proof of Theorem 3.1
Proof. The proof follows the basic structure of constructing lower bound as in Kaufmann al. (0166). Recall that their inverse of characteristic time is given by
T = sup inf wEll MEA, (MM)
Σ FugdKL (Mes Ma
The main challenge for our setting describing the alternating set AT (M) and scalarization of the given instance M E M. Given matrix of arm-objective mean-rewards M, ordering cone C and family of policies the Pareto front is the set of optimal values (ordered wrt C) of
max MT.
(10)
well
Step 1: Constructing set of alternative instances Let nT E arg max MT.
The set of confusing instances given II and C is the set of all matrices M which have different Pareto front than M when using the policy π². Therefore, the optimal values of (10) with instance M are not-dominated by those of instance M. Hence, the set of alternative instances, Ag (M) is given by:
Aq. (M) = {MI M M max Mw de Ma*
*ell
Let n' E max Mr over which implies Mw Be Mx or equivalently:
E C, π E II (=') s.t. 2J Mn 2J Mn*
Therefore, the alternative set can be written as:
Ar- (M) A Uze { {M E M: ]z 3 C, Mr > xT MT*)
(M M: TM (π n 0}
where, represents a bilinear product and, complement given by:
Ag (M) A OzeuAer) { {M M:
M (π- s $o}
M M M: M (m- (x- EC }
= =
where, ri(C") denotes the relative interior of the polar to C. Since C is polyhederal cone, it is closed and convex and therefore, its polar cone is non-empty, closed and convex. Therefore, Ag. (M) is non-empty.
Step 2: Hardest instance lies on the boundary We now show that given x", and æ, the hardest instances M E .M are such that:
M (a -T) bd(()).
Fix n' E II { and let M E {M EMEM: M (N' = Then,
by convexity of {M :
(T-- - xx) x--)>() 0} there exists M
M E M: M (T'- m*) e bd(co)) such that |2
T M2
2T JM2l 2 - 2T 2TMgl V z
Since dRa. M,.) is decreasing, we have: dRa. (2 Mg, TT =M,) 2 dKL (TM))
JM!).
Using the above arguments we see that the minimum argument of Ex WEdRL (2TM), 2T MM,2TM' M") is
such that M" JMMMA M: M (T x²) E bd(C))}
16

---

The optimization problem now becomes:
sup inf inf
Σ wkdRL (2 Mx. 2 MR)
wEll (M) SEC
k
wxdki (TMMe,2² Ma, Me)
inf wEAK "Ellaa" MEDA, (Ad) SEC
sup inf min
where
a (M) a Uma :MM:: MM -²) =0]
Umar (MEM: 32 E, (vect (z (ir x²)) vect(M)) =0}
(11)
Finally, to accommodate for multiple optimal policies x², the inner minimisation problem becomes
inf Σ wxdka (s & 2 Ms) relli=' MERA, (M) #EC (MM
sup inf WEAR
min
k=1
This concludes the proof.
B.2 Lower Bound for Gaussians: Proof of Theorem 3.2
Proof. Step Simplifying the KL-divergence for Gaussian bandit instance with identical variance across all objectives yields
(u -
I
Ve(w, M)
min MeBA, (M) ZEG
min
wk
(12)
20
Recalling that due to the projection lemma, the achieving the minimum satisfies
(T πT) O, VzEC
(13)
Now, we formulate the Lagrangian of with dual variables 3 for 13 as
ww M, M, 7,
M
Wkk
(2)
+ 12 M (TT x)
V20e
t=1
(1
(2(
ub
+ B2 M (TT x)
(14)
V20e
1=1
Step 2. Taking the derivative w.r.t. M, we have ac
(2(0) 2
(0)
-
+ +/2(00 (TT" T))
aM (2)
wk
20
and setting it to zero, we get
wkk (2(0))
2
(0) M 32(() (TT -x)
1k
20
20? 1 (2(1) (x* - T))a) = p
o73 (x* T)
- MM (6)
pk
(C)
(15)
2wk (2(0))²

---

The last equality holds for any 20) # 0. Therefore, the Lagrangian now becomes
L(w,
3)
K
(0)
2
N
K
Wk
(210)2
PR
+
3
X
M k (T- - T)
V2re
1=1
t=1
k=
(2(0))3
( Thk
8
+
L
(4)
(T T)B 1k Bo 210000x
(2) (m
(x m)
(2(0))
2
k=1
[=1
k=1
82
(xt
x k
o0
Σ
(0)
T) Mk
(2)
2
Wk
Step 3. By taking the derivative with respect to 3, we have
ac
T)
3
(TT -T) 14 (8)
03
wk
Ie Emm
E'm
km
and setting it to zero, leads to:
B El. EK K
k= 2(9) (T
x) -) Pk
(
2 MM
(16)
Σ El= ot
2- x)
3 A 11 Ding(1/w)
where o3 2 -/ 2. and A A n
From 15 excluding for the origin lying within the cone, we get:
(0) - So² (T 7)
M (8)
z² Wkk
(8) of A 2 MA
z we d A Diag(1/w)
Finally, the Lagrangian from
14) leads to
((w,M)
2
= TAMA
(2 MA
2 Al Diag(1/w)
(iag(1/w)
0?21 A13 A Diag(1/w)
(z MA)²
20 ||
Thus, the characteristic time inverse given by,
(2 MA)2
(2 (=TMA)
max inf min WEAK K REN(=') sEC\/O) a "EllI (M)
inf min #EN(=') =6C((0) x" elll" (M)
20 A 1/3 (isg(1/w)
2o
B.3 Proof of Theorem 4.1
This proof follows directly from Theorem 3.1 in Balas 1985). Recall that the set F is given by:
F F U { M E M: (vect(= T (n m")), vect((() o)
Any 2 E C. we have 2 = E,a Rewriting, every hyperplane in F as Pr iM E MM(ivect (E, asti x), vect(M)) = =, azn } Then, by Theorem 3.1 in Balas 1985).
C(F) is given by:
(T <eTeec(MM) (M) 2 7o, 7= E, vea (क m²))
C(F)
% S u; E, a.u! n M M
18

---

B.4 Proof of Theorem 4.2
Recall that:
K
(e M)
min
inf Σ wadKa (z (zT S,M2 MM)
Mech(OA, (M))
SEC
km1
w" (M) A arg max WEAK
inf =E MrcchOs., (M)
min
min
Σ wk. (x (2M,2 M) sEC
M,
For (1) and (2) observe that M) T and M, deL (xT M, x² M are con- tinuous maps for (2, M) E C x M and (z, M, M, E M ch (0A,- (M)). Further, En WAdKL (s (=TM, M, M) is continuous in all its elements. Fix a sequence (Wi, 2ts Mc) 11 C M such that (Wi, Re, Me) (w, M). For any 3t' 2 such that [[ Ze, M,) (w, 2, M) I V t t'. Further, ch (Az- (Mi) + ch (A. (M)). Therefore, for every
é, 3 t" 2 1 such that V t" we
Σ dKL (z) (e,Me, Me. oे M.) Σ wadki. (s M, Me)
s M.VMe M. E RXL
Taking 2 max (1', {"], we have:
inf inf Σ dk. (z) Mes 2J Me)
inf inf Σ EwndkL (=MM, M.) Me (M) sEC
Meds, (M) FEC
inf inf Σ dkki (zI
Me 2J M.)
Σ wkdki. (z 2 M.)
MEBA. (M) sEE
S
For (3), we define f(w, M) inf Mech(an, (M)) infsec Ex wxdkL (2M Mi) and C(w) = 11. Then, from Berge's Theorem (Theorem F.I in Appendix), we get w (M) upper- hemicontinuous.
For (4), the convexity w (MM) follows since the optimal solution
Σ wa. (z (=TM. M, TTTT TM)
max inf wEll MEcA (M1))
inf sec
is concave for any given и and n²
19

---

C Proof of the Stopping Time
C.1 Proof of Lemma 4.1
The proof follows by showing that sec En NR (RTM,,, 2M,s) an appropriate stochastic process and can be bounded using the mixture of martingales technique of Kaufmann and Koolen (2021).
To this end, given a 2 E C, we define the random variable as
Xx(1) A Σ ma Nk, (zihr Mo, The 3 31 + In N
where Zinf - arg inf=ee zec Es dK. (zT MR,,, 2Tk
Since assume MA. belongs to exponential family of distributions, for any given Siaf # 0, 2 Mx being a non-degenerate linear transform also belongs to the exponential family.
Now, plugging in (t) in Theorem 7 of (Kaufmann and Koolen 2021 yields
In (3))
P : Σ
NR. 2 Ma,,, MTe Ms)
2
3 (1 + In (Ne,)) + KT
K
kE[K]
kE[K]
$ 8.
Here, T 1 + + such that
h h1 + x)) + In (2C(2))
T(x) A 2h3/2
(17)
2
with
Vu 2 1, h(u) = u - In(u)
(18)
AS E [1,c], Vo 0, h.(z) eep
11 (x))
if h-1
In(2})
(19)
12(x
(n(nn22))
else
and ((2) = -> 2
C.2 Proof of Theorem
First, we prove the following lemma required to proceed with Theorem 4.3 Lemma C.I. For any = 1, 1,2...., K, let 1 < l I L. Let vj > 0 and define the event:
a CR (Ee[K] (t+ S No. S (1 nj)tt}
and let lo indicate whether the event holds. For (1 K, for all E C we have:
PP
1 Σ
NR.edKL
(MMM,,, Mb) 2
pe
K
exp
-P
K
1 1+
KE[R]
Proof.
Fix ( E RRK and 2 0. Define my,e such that:
m, 30 < m S Mr. s.t. tdka (m, T (MM) = Sk
Maat
00 otherwise
By monotonicity of tdKL (,), ma. is increasing. With t Nk.s have that
NK (mx.Ne..s Mx) = Ca S Ne, (3 TM, Mr). 2 MM. (0) (andkkaaaMaaara
2 meNNu. 32 mx
20

---

where (a) follows from monotonicity of dRL (++)) and (b) follows from monotonicity of m (E)
k.t""
With dRdRa (= (=TM (MM..eeLLo)) =MMs)
and non-negativity of dKL (:--) have: It7
Ne,edk (s MMMss T Ms) 2 Sx
P [
S P [KE(K]
T Jiaa MK,No,es Ct3)
P [KE[(]]
2 ZMune S mL((++)) Cx
W P [nEE[K]
2 T JiM SS ma.(+-))e Cx })
(a)
Σ kE(K]
LydKı. (mX,(1+ Mx)
exp
Sk 1+
Σ KE[K]
exp
where (a) follows from Lemma F.2
Using Lemma R3 with 7x= = NK. (2 MMM, TTa)) and a = (I+1))
we have that:
P Le
Σ
dR. (xMMeeiZ Masez Maa 2 s
pe
K
exp
-P
K
1 n)
RE(K]
This concludes the proof.
Now, we provide the proof of Theorem 4.3.
Proof. Let us define D =
and set D = 11.2..... DD* Let us define [og[1+n]
log(t)
Σ NR. NKL (z MMMas T Ma) 2 P
kE(K]
Ba = i () & NN. S (1+ d)
We have UseD A Ba), hence P(A)) S EaED PAAn Ba). - and p 2 (1 + 11) K, we get + 1. For 17 = p-
Now, we Lemma C.I with 7 - and i (1 )
to obtain for all d E D:
P(An < pe K
-p (1 + m7)
exp
K
By union bound on D, have:
Dpe K
-
((A) <
exp
K
1
Noting that D log(t) log(1 +g)
and 17 p- get:
(eielog(t)) K
((A) S (-p
ct1
21

---

D Proofs for Sample Complexity Upper Bound
D.1 Pairwise Concentration Bounds
Lemma D.1 (Pairwise concentration (Proof of Theorem 5.1 Consider the event:
& - [sEcK] Dases { (t) S = p4 - x M4 S (t)(
(20)
where Liş(t) = =z ( (35,)) (t) and (tş(t) = = (iss. - (3.0) Bey(t), and Big (t) is defined
as
log( Ki
(t)(t) - 4112117 h
+
Σ
log (4 (4+ log((N((t)))
Σ
2
Na(t)
aE
(E(2,))
Here, K1 A k(K-1) h(.) x log(1 + x)). Then, we get
2
P (N 2 1- 6.
Proof. We have the following:
& = ((a)) {Lis S x p4 - MJ S Utd}
((a)) {|= (jig, (3,,)) - (m: 14) s BBy(t)}
where, (i.j) [K] x [K] is the set of pairs. By union bound, have the following:
P ((E.) P (3t 2 E, holds) )
= (31 2 1: |zT (iii - ((j,t)) - = (ur - (ui-)))] 2 Bcy(1)
(332 1: (ps. - 144) =T =((gee (1))1 2 Bc)(1)
(4)
8
Σ
K(K- - 1) (15) 8
(a) follows from
1. z
2T (Pttt 14) is || sub-Gaussian Pi. M4 is 1-sub-Gaussian and
2. Lemma 7 of (Kone et al. 2023a) that states that for two I-sub-Gaussian and centred random variables X and Y, the following holds true with probability
Σ X;
1 Σ Y q
$2
hh
(log()) 2
+ log log(e<p) + log log(e(g))
(
given h(x) ~ + Inx.
We now show that the Pareto fronts under the metric dp-
Lemma D.2. (Z, dp) is a complete metric space.
Proof. From Definition 5.2 for two Pareto fronts PI, 2, we have that:
dp P2) A max
sup (KEP;
d(k, Pı), sup d(k, Pi)
kEP,
where,
(kk,P) inf max
0, sup T (nr - mb) =ECr3(11)
PEP
22

---

1. We first show that dp(P1, is metric. Let P2 E Z. To show that dp is a metric, we show that:
(a) Symmetry: dp(P1,Py symmetric by definition
(b) Triangle Inequality: We show that (P, Ps) S (2), d,, Pa).
dp Ps) max max min Me pxx(3)) - (xi) max min Mer (x((Xx) 1r: (Xx) kEPs k'EP;
kEP; K'Eps
We have that:
max min (ex(ss)) m4x(Xi) kEP, K'Eps
max min He (Xs) + min He (X2) REP1 K'E
max K"EP2
14 (X2) (X,(
K"EP2
max min pe (X3) P42" (X2) + max E"))(X,) K'
min MK" (X2) - (X1
kEP: EMEP(X2)
Using a similar argument:
max min pe (X1) (x(2)) - ExE)(X)) KEP:
max min Me (X1) - M4 (X2) ) + max min par (X2) - (Xx)ss
kEPs KEP
kEPs (TEP(Xx)
Noting that for any positive numbers a, b, c, d, max b, c d} = max (a + c. + d), we have:
(p. Ps)
max
min He (Xs) (X2)
min ("E((X))
ne p (X2) (x())),
E'EP(Xs) K'Pss
max K"EP(X;) NPP:
min (X)) - (xx) max kEPs (MEP(X)) (4)( (xa)
min
max max
min po po (X1) M (X2) + L' ('EP(x)) KEPi
min K'Pi M" (PE()
max
Per (X2) - (x1)..
min pe (Xs) mw (X2)
min kEPs kXE)(X))
max
(x2) (x(xa))
('EP(X))K'PP
(p P2) dp Pa)
(c) We now show that (P, P2) - (p P2) = 0 is immediate. For the other side, note that by Definition 5.2 we have:
Pi P2. The implication P: P2 =
dp (PI, P2) 0
sup A(k, P2) and sup A(k, Pi) 0
REP:
kEPz
Further, supkeP, (k, P2) = implies:
k E Pi. Bc W, KEP2 = VhEPI, kE
A similar agrument using suP*EP, A P1) 0 implies that V k E P2, k te k
2. We now show that Z is compact under the metric dp. Consider a sequence of Pareto fronts P1, P....., P.. Z and P be the candidate for limiting Pareto front.
Boundedness of P is immediate.
P, + P, therefore, V > 0,3 (EE) s.t. V N(E) and dp P) < Let un be limit point of P, i.e., 3 sequence Wksn E P such that Mk.n + jkg. Since dy (Pn, P for each M E P there exists Mk,.m E Pn S.t. Mk,nm
Mk,n. Using diagonalization argument, we can obtain a subsequence (k.nm - Ukg-
Since Pn, is compact, P* must lie in P and therefore, P is closed.
D.2 Concentration to the Pareto Front
Lemma D.3. There exists constants C such that:
((TT) 2K2 1 1 1-exp(-CC
T Texp (-CTV/8).
where Gr G-=-1 -ff {de (Pr.Pr) se].
23

---

Proof. We then have that:
P dr (Prs pm
2() = P max dr (Pr,Pt) .dp
dp (p',
(Pr,Pi) .P.}} 2r)
S PP dp (Pr, p-) 2 6) + P dp Pp", pr: 26)
Focusing on the first term we have:
dp (Pe, P*)
inf sup max kEP, KEP
max (1CrI(()
ZT (Ms Mene))
(a) min max max kEP KEE
T (Mw - Mw + Mw - Mins)
0, max #ECOB(I)
(b)
TT (M MMw..) }
max max K'E
(
0,
max =ECMB(1)
AT (Mer,.- - Meae) }
max max KEP
0,
max =ECCII(()
Recall that G- - dp (P:. 2 c] then using a union bound, we have:
P (②r)
T
Σ (=)(T)
P dp (Pr.P-) 2()
Σ IP (2T
(PTTT(AAss (Mas - M..s) S= (Ma- - MMw) - 5)
(=h(2)
(k,K')
+P (2T (MaL-MW. Me.) 22 (Ma- - Mx) ( +5)
Let T be such that h(T) 2 K2. Since 2 h(T), one has that No.: 2 Vt K.
Then using union bound on each pair and number of arms, as well as a Chernoff bound, we have that each of the terms in the above inequality are bounded as
T (Mae -Mw S T (Mr - -Mx) -E) E)
P
= P P(2 TT (Ma. Mw.)) S2 T (M& - -Mx) - -N,N 2 Vt)
IP (2T (NIR.. - -idw.s) z (Mr - Mx) EE) -b)
-
Σ IP (2T (Mdtes--M - (NWw' Msx) S -E/2 E/2)
-
Σ
P (p(3T (TT(Mins - -Ma) s -1/2) +1P (27T (Mw, - Nww 2 21/2)
sm fi-K
(exp (-sdki. (T - =/2,, TT [Ma)) + exp (-sdki. (= MM + E/2, TT Mx.))
- K
(-(vi- KYdda. (TTMr -//2, IT MM)))
+ exp (-(Vi- K)dKL (2 Mr + =/ TM²))
exp
1 (-pp (2 TM, - = Mx))
1 - 1-exp (isp(-dle (-dka (z My + E/2, =T Mx.))
exp (-dKL (z M2 - =/2 M2)) + 1 1-exp (-dKL. (zT "M + E/2, [[,2)
x exp (-IVE- - ()innnn fik (z T Mr - E/2, T Mx) dKL (2 MM + E/2, T MM
k.k'
24

---

Similarly, we have:
(Mix. Mors) 2 (Mx - Mkr) + +5)
<
expxp exp (-dKL (2 M4 + =/2,=T Mx)) 1 -xxp (-dxL (z Mw E/2,2 Mx))
=1
x exp (((VE - K) fin (z Mr - E/2,, (xx) dKL (z MM E/2, = Mx }
K.k"
Now, we set
C - min {dRL (= (=T Mx + g/2, = dxL (TMM Mr E/2, [M)}}
and
1
1
B A
1 exp ( (-dK1. (z Mr E/2,,
exp (-dKı. (z Mr E/2,2 21 Mx))
(k,)))
1 1- exepp (-dK1. (2 Mg + M,))
1 exp (-dKi. (2 My - E/2, Mx
We observe that B S 2K2 1-exp(-C) Now, we get that
T P ((T & Σ
Bexp CCxp-CVt220 2K²
Texp (-CTL/6)
1 - --exp--C)
t=h(T)
D.3 Proof of Theorem
5.2
Theorem D.1 (Restating Theorem
5.2p. For any a > 0 and c(t, 8) defined 7 we have that the
stopping time satisfies:
[
lim 8-0
S
(M)
log (1)
Proof. Step Good Event Let T E N, and h(T)) = VT, define the good event:
Gr = nf = (dr(Pr, pr) s s(o)
(21)
where, f(e) such that:
d, P*) S ((e
sup w'ew (P,) wewn (P-)
sup
|1 - will Se
Step Concentration of Good Event Lemma D.3 we show that:
(GT) < 2K
T Texp (-CT+)
exp( (xp(-C))
Step Tracking Lemma We have:
Nk.t --taa) s t
Nk.t
Σ
1-1
1 (M,
+ + wiMMi wx(ar)
No.1 +
h(T)
Σ
w (Ma.) w (ax))
t.
K(vt + 1)
l(T))
Σ (. wi(
+
t
t
25

---

From Gaarivier and Kaufmann 2016), we have that:
Σ wkee S (1 (1+ vt)
max
NE.t
Step Complexity of the good event
Assume t 2 Te, and let:
C. (M) A inf Vc (w, M), v(w, M) s.t. 1/w wil 3e, dp (PrsP*) f(e)
wr w',M''
Then, we have that:
Ve (M. 2 (M)
Step 5: Bounding the stopping time for good and bad events
Let T5 be the stopping time, then:
min T) S VT + Σ
1,22
t=T.
From the stopping rule (Equation 7p). we get that:
T
T
Te (.)
VT + Σ
1 (10
t=
t=
B(t,
VT
(M(M)
where, ((t, is defined in Equation 6
Define T3 inf T E N: VT
c(t,5) C.(M) S J Hence, we have:
Texp 2 exp(-C) T exp (-CT-118) ST. +T +2"
T8 TT - T8 +
T=1
Let (nn)=inf([T : : vT 2 (1+m)
Then:
To S ((n) inf TEN: (M. (1+n) 2 s(t,
Step 6: Obtaining the asymptotic bounds Taking limits:
E [8)]
lim inf 6-+0
< Va(
log
26

---

E Reduction to Best-arm Identification
We briefly discuss how the metric dr (+++) extends existing notions of gap in best-arm and Pareto-front identification literature. Specifically, we proceed with the three following observations.
1. Observe that dp (P", O.
Further, iff C represents the component-wise wise ordering as in Pareto-front identification (Auer et al. 2016 Kone et al., 2023a), then 2(() = 1, V [z].
dp ([K) P", PP))
sup kE[K]\P
d(k,P'), sup d [[K] pp, (h)) kEP-
0, min (Meh - Mcke) }. EE(L]
max
sup inf max kE[K]]p
KEEP
0. min (Mek - Mack') } EEIL
sup
inf
max
kEP P
max
sup
inf max (0,
kE[K] KEE
inf max (0, (K. k)) kEP (EK
sup
sup inf max (0, (O,, kEP K-
3. Finally, when there is only a single objective, i.e., |T| = and assuming an unique optimal arm (fairly common assumption in BAI literature), have:
d Pk,,P"), sup d d(K) p R)) }
dp ([K] P", P)))
max
sup KE[K]yP
keP
max
sup RE|K]AA
max {0, (Mi - pk- }}
sup max {0, (14- mw))
min Are
which is exactly the gap for one-dimensional bandit.
27

---

Useful Existing Results
Theorem F.1 (Berge's Maximum Theorem (Berge 1877). )) Let U and V be topological spaces.
f:ll x - R and C' U - V be non-empty compact for all a E U. Then, if C is continuous at u, (u) max,ec(u) {u, v) is continuous and C (u) {u E C(u) (u) f(u, v)}
upper- honper-emiicotiiuuuus.
Theorem F22 (Donsker-Vardhal Variational Formula Donsker and Varadhan, 1975)). For mutual information dgL. (P, Q), have that:
dRL (P.Q) sup Ep [f] In EQQ [exp(f))
Lemma F.1 (Peskun Ordering following are equivalent:
PPssku
1973 ) For any two random variables X, Y on RK the
1. Y
2. For all z ZERK P| x]]
3. For all non-negative functions f1, .e.......f................ we have that: Elu S B
Lemma F.2 (Magureanu et al. (2014)). For any = 1, 2,2.... K, let us define S t S t. Then for
all Ck Mr. we have
p ( { Mon S Ck. tu S Nnxt)) < exp
txkke (Cks Ma)
KEEK]
Lemma F3 Magureanu et al. 20144). Let a > 0 and K 2 2 and Z RK such that for all I
we have:
P(Z2() exp
Σ GK kE[K]
Then, for all p p> K E IR4, we have
aep K exp(-ap)
PP
Zz P
KE[K]
Lemma F.4 (Single-arm concentration valid confidence interval on z p.
Kaufmann and Koolen 2021 ) The following is ô uniformly
(In(z) (In(+))
ExE
T 4
E
a+ 2 2L.0
Σ
eln + In
Nk.
kE[K]
28

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided a proper justification given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] " is not grounds for rejection. While the questions are phrased in binary way, acknowledge that the true answer is often more nuanced, so please just your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
29

---

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, c.g., if the approach was only tested few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency 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, 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 impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
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 cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
30

---

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 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 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 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 replicate the results, access 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 NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (lttps://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
31

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to 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, supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
32

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
33

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsspppppssttteeeeee thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
34

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with humansubjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and 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 the institution conducting the review.
35


Reviews:
[{"review_id": "XoKJ2tlTai", "reviewer": "Reviewer_maY1", "summary": "This paper studies the preference-based pure exploration problem for bandits with vector-valued rewards and a set of preferences imposed over them. The objective is to identify the most preferred policy over a set of arms according to the preferences induced on the reward vectors by an ordering cone C. The technical contributions are three folds. First, a lower bound on the sample complexity for identifying the most preferred arm with confidence level 1 – delta is proved. The lower bound shows how the geometry of the preferences and reward vectors changes the hardness of this problem. This geometry for Gaussian distributions of rewards is further explicated. A convex reformulation of the lower bound solvable with linear programming is provided. This convex reformulation of the lower bound is utilized to design the Track and Stop with Preferences (TSwP) algorithm that identifies the most preferred policy. Third, a new concentration result for vector-valued rewards is proved. It is shown that TSwP achieves a matching sample complexity upper bound.", "questions": "No.", "limitations": "No.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper establishes a lower bound on the sample complexity for identifying the most preferred arm with confidence level 1 – delta. This lower bound reveals the hardness of PrePEx problems. This lower bound also shows how the geometry of the preferences and reward vectors changes the hardness of this problem.  \n\n\nIt is shown that the optimization problem in the lower bound involves minimization with a provably non-convex set. A convex reformulation of the problem based on ideas from disjunctive programming is provided. This convex reformulation of the lower bound is utilized to design the Track and Stop with Preferences (TSwP) algorithm that identifies the most preferred policy. \n\nA new concentration result for vector-valued rewards is proved. It is shown that TSwP achieves a matching sample complexity upper bound.", "weaknesses": "I only identified some minor writing issues such some citation numbers are missing, e.g., line 21.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for appreciating the strength of our contributions. We have rectified the errors, typos, and notational issues in our revised manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2ZGtxFTNOe", "reviewer": "Reviewer_a6bi", "summary": "The paper considers a generalization of the fixed confidence best arm identification. Specifically, in this setting we have a collection of arms each having a mean vector associated with it. Further, we have an ordering that establishes a preferences over the vectors. The objective is to identify the Pareto front according to the preference model. The paper establishes lower bounds, designs an algorithm based on convex relaxation, and establishes upper bounds on its sample complexity.", "questions": "See the points under Weaknesses.", "limitations": "I think the limitation were addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "-The proposed problem is interesting and relevant. \n\n-I did not verify the correctness of the theorems, but the techniques seem involved with lower bounds being established. \n\n-One can see possibly extensions to this setting where we learn a Pareto set.", "weaknesses": "### 1-The major weakness of the paper is the presentation:\n\n (A)There are many broken references. \n\n(B) definition 3 for partial order: twice the definition says $\\mu \\leq_{C} \\mu$, I think the prime is missing after $\\mu$. \n\n(C) In page 4 at times the paper uses $C$ and others $\\mathcal{C}$ but aren’t they both referring to the cone?\n\n(D) \"$c_1=$\" in line 334 is not given. Further, I think Lemma 1 would say There exists a constant $c$ instead of $c_1$. \n\n(E) no space between words in lines 112-116: “settingby”, “)and” \n\n\n### 2-The paper is a bit confusing since not the whole Pareto front needs to be identified only a subset of it, correct? In the end of section 2, what does “active support” mean? How is it different from just saying support?\n\n### 3-What is $\\mathcal{\\bar{T}}_{\\mathcal{F}}$ in Theorem 6? Does this imply that the algorithm achieves almost optimal performance?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for pointing out several avenues for improving our work. We address the concerns below.\n\n**Editorial edits:** We have revised our manuscript to rectify all the errors and typos as mentioned by the reviewer.\n\n**Identification of the Pareto Front:** This paper is about identifying the entire Pareto front. This resonates the line of literature paved by ``Sequential Learning of the Pareto Front for Multi-objective Bandits\", crepon, Garivier, Koolen AISTATS 2024, and ``Pareto Front Identification from Stochastic Bandit Feedback\"\nAuer et. al. AISTATS 2016. They consider similar problems but without generic preferences and linear bandit feedback. Similar but not identical problem was considered in \"Adaptive algorithms for relaxed pareto set identification\", Kone et. al. NeurIPS 2023, wherein an approximation of the Pareto Set has to be identified. Our problem is a non-trivial generalization of those papers in the sense that, we consider generic preferences (described through a preference cone) and linear bandit feedback.\n\n**Terminology:** Thank you for pointing out. The word \"support\" suffices for our purposes. \n\n**Asymptotic Optimality and Theorem 6:** $\\mathcal{T}_{F}$ is the characteristic time associated with PrePEx problem. You are indeed correct, the claim of Theorem 6 is that the proposed algorithm is asymptotically optimal. \n\nWe hope that our response addresses the reviewer's questions. Let us know if you have any other query.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GTghciJobN", "reviewer": "Reviewer_E3uE", "summary": "This paper generalized the strack-and-stop style of best arm identification analysis and algorithm design to the setting of vector-valued bandit problems where the pareto frontier must be found. Novel upper and lower bounds are proposed as well as a convex relaxation of the lower bound that produces an implementable algorithm.", "questions": "What is lost with the convex relaxation? What happens in problem instances where the optimal action is not in the relaxed region?", "limitations": "N/A for societal impact, but I found the discussion on limitations mostly absent.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "While the overall structure closely follows the track-and-stop literature, there seems to be a lot of technical novelty in its extension to the pareto front setting. The characteristic time has a much more complicated geometric structure, which is reflected in the lower bound. New concentration inequalities need to be derived for the pareto frontier estimation (along with a novel distance).\n\nThe explanations are clear and presented in a coherent order. The comparisons with previous track-and-stop papers provides a convenience frame to understand the novelties of this paper.", "weaknesses": "I wish the authors would describe the technical novelties e.g. in the proof techniques in more detail in the main body. Some interesting examples illustrating the geometric insights would greatly aid the reader’s understanding. Finally, the paper needs a thorough proofread - there are many broken references, misplaced or missing periods (especially at the end of equations), etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the strengths and novelty of the contributions along with pertinent questions regarding the computational approach. We respond to them here.\n\n1. **Cost of Convex Relaxation:** In the setting with Gaussian bandits, as we show Theorem~2 in the paper, nothing is lost since we are able to get exact form of the hardest instance analytically. In the non-Gaussian setting, where we cannot find such analytical form for the confusing instance, we observe that the min value of the inner minimisation problem under convex hull can be lower than the minimum value found in the original non-convex set of instances. Thus, the characteristic time attained by the algorithm using the convex relaxation can be higher than that of the original lower bound. Thus, an algorithm solving the convex relaxation might have higher stopping time. Further, please see lines 316-324 in the updated paper. \n\n2. **What happens in problem instances where the optimal action is not in the relaxed region?** Since our approach takes the convex hull of the feasible set, which is a super-set of the true set of alternating instances, the optimal action set always lies in this set. \n\n3. **Technical Novelties and Insights:** The technical novelties of this work can be categorised into three parts: (i) lower bound: taking the policy space perspective, (ii) algorithm design: convexification of the lower bound and a new stopping rule and (iii) proving asymptotic optimality of PreTS requires coming up with a new distance metric and establishing concentration inequalities under these metrics. \n\n\nWe hope that our response addresses your questions. We would be glad to respond if you have any further query.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tuTcQtERSZ", "reviewer": "Reviewer_owBL", "summary": "This work focuses on the setting of multi-armed bandits with vectorized rewards and studies the identification of the Pareto Optimal arms with a fixed confidence. Compared with existing works, this work considers a more general preference definition (i.e., induced by a preference cone) or targets at finding the entire set of Pareto optimal arms. A lower bound is derived, providing both statistical and geometrical implications of the hardness of the problem. Based on the lower bound, a track-and-stop style algorithm is proposed with its efficiency proved by a corresponding upper bound.", "questions": "- I would greatly appreciate some clarification over my confusion on notations listed in Weakness.\n- Also, the algorithm design begins with a convexification of the lower bound, which I have several questions about. (1) Is this design purely to benefit computation? In other words, if letting computation aside, can we directly track the lower bound and obtain an asymptotical upper bound; (2) as the final performance approaches the convexified characteristic time, I am wondering whether it is possible to compare it with the true lower bound so we can understand how much loss is introduced by the convexification (i.e., a tradeoff between computation and performance).", "limitations": "I understand that this work is of a theoretical nature so there are no major societal impacts to be discussed. However, I do not find justifications for related questions in the checklist (e.g., 1. Claims, 2. Limitations, 3. Theory Assumptions and Proofs).", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The studied problem itself is novel and well-motivating due to the commonly existing scenarios with multiple objectives. According to the summarized literature, there have been no efforts in the exact problem setup studied here.\n- The overall flow is clear, and the techniques adopted are reasonable and intuitive, extending the studies from single-objective BAI: starting with the lower bound, and based on it, leveraging track-and-stop style algorithms.\n- Despite certain confusion about the notations/definitions (see weakness), I believe the overall results should be sound.", "weaknesses": "- First, I believe the overall paper needs careful proofreading and some revisions to ensure the readers’ correct understanding. For example, (1) Definition 3: $\\mu$ and $\\mu’$ are not labeled clearly; (2) the maximizations in Equation 1 and subsequent sections are confusing per my understanding (please let me know if I missed the definition somewhere); (3) Eqn. 1, line 231, 233: sometimes there is transpose over $M$ but sometimes not; (4) Eqn. 6: $M$ is a vector on the right-hand side? Also, the minimization is noted over $\\hat{M}_t$ while the expression seems over $M$. \n- Second, while the adopted techniques are sound based on my intuition, it seems they largely follow the original track-and-stop paper. The authors have made efforts to highlight the challenges and differences (e.g., the discussions beneath the lower bound, and the distances introduced in Sec. 5 to accommodate Pareto fronts). However, the overall idea is still the classic track-and-stop one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time spent reviewing and pointing out several notational issues to improve the manuscript. We have done a proofreading of the paper and fixed the typos and issues. We address the other concerns here.\n\n1. **Novelty with respect to Track and Stop:** As pointed out by reviwer E3uE: ``While the overall structure closely follows the track-and-stop literature, there seems to be a lot of technical novelty in its extension to the pareto front setting. The characteristic time has a much more complicated geometric structure, which is reflected in the lower bound. New concentration inequalities need to be derived for the pareto frontier estimation (along with a novel distance).\" We would like to build upon observation and highlight the salient features of our contribution and the relation to existing work. \n2. **Purpose of convexification:** Convexification serves several purposes not limited to providing computational benefits. Without optimising over the convex set, we cannot guarantee that the algorithm is asymptotically optimal. In particular Theorem 4, claim (4) will not hold. Therefore, tracking the lower bound as per Track-and-Stop strategy will not lead to asymptotic optimality. There are other key points which will not hold if we do not optimize over the convex hull. For example, we cannot directly use Donsker-Vardhan in the proof of Lemma 6 but we have to prove compactness and other properties of the original non-convex set.\n\n3. **Convexification of Characteristics Time:** In the setting with Gaussian bandits, as we show Theorem 2 in the paper, nothing is lost since we are able to get exact form of the hardest instance analytically. In the non-Gaussian setting, we need to conduct a separate study, both computational and theoretical, in order to study the gap between solutions of the original optimization problem and the convex relaxation. It will non-trivially depend on the interaction of the preference cone and the space of confusing instances. This would be a interesting avenue for future work.  Further, please see lines 316-324 in the updated paper. \n\n\n4. **Explaining the maximisation problem in Equation (1):** For better understanding, we explain the maximisation problem of Equation (1) as \"Alternatively, this vector optimization problem can be represented in the policy space as finding a policy $\\pi \\in \\Delta_K$ supported on the Pareto optimal set of arms. This is given by...\" (line 189-191 in revised manuscript). Let us know if that clarifies your concerns.\n\n\nWe hope that our rebuttal addresses your concerns and questions. We are eager to discuss if you have further queries.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for providing several valuable comment to improve the presentation and writing of our manuscript. We have incorporated those comments and are uploading a revised version here.

Meta-review: The paper reports a study on preference based pure exploration, with vector based rewards on arms and a set of preferences over these vectors. The overall opinions received from the reviewers are positive. The reviewers acknowledge the novelty of the problem formulation and the technical contribution on the lower bound and upper bound results. I recommend acceptance of the paper, and encourage the authors to revise the paper thoroughly to address all comments from the reviewers.

One thing I would like to point out is that during the rebuttal stage, the authors submit a revised paper pdf file. As specified by the FAQ (https://neurips.cc/Conferences/2024/PaperInformation/NeurIPS-FAQ) of NeurIPS'2024, this is not allowed. After consulting with the SAC, I inform all the reviewers that the submitted pdf file should be ignored and all discussions and decision are based on the textual comments and replies, not on this pdf file. I suggest the authors should carefully check the rule of the conference for submission and rebuttal and comply with the rule in the future.
Decision: Accept (poster)